Day-29 Massive Storage Management

Massive Storage Management

其实这块要讲的就是有关Disk的内容，前面说明Disk的时候就有提到他的构造以及Disk Access Time，也有一张专门说明各种RAID的差别，如果不记得的话底下有几只图片可以复习。

Hard Disk构造	Disk Access Time	RAID

这篇第一件事情要讲的事情是OS如何管理空闲的空间，主要有两种方式，其中一种又会延伸出另外两种做法，以下一一解释：

Uploading file..._04mfils1w

我们用一堆Bit来表示每个Block是否空闲，1代表正在被占用，0代表目前空闲。

这种做法简单又很好寻找连续的Free Space，但是不适合用在大型的Disk，如果Block数量太多，管理的空间就要很大，甚至只能放在Disk中无法放在Memory，效率会大幅下降。

这是一种熟悉的资料结构，每个node会记录下一个Free Space的位置。

这样子的做法就适合用在大型的Disk，因为只会使用空闲的Block数量，实施方式也不麻烦，不过不太适合用在寻找连续的Free Space，也不太好寻找大量的Free Space。

基於以上的缺点，Link List的做法有两种延伸做法，分别为Grouping以及Counting。

不让一个node只有一个Free Sapce的位址，而是存放多个Free Space位址，如此一来找寻大量Free Space的速度就增加了。

另一个是着重於找寻连续的Free Block，在纪录Free Sapce位址时，也顺便纪录後面有多少个Free Space，这样找寻连续Free Block就比较简单。

虽然上面的图说的是档案的起始位置跟大小，不过概念是一样的。

由於Process会发出许多Disk的需求，这时候OS就要负责哪个需求先处理，以下用表格简单说明。

法则	作法	效益
FCFS	First Come First Serve，谁先来谁就先处理。	可能导致读取头需要左右来回读取，Seek Time较长。但简单实施，并且公平。
SSTF	Short Seek Time First，找距离目前最近的先处理。	Seek Time变少，但不一定最佳，并且可能发生Starvation(一直有读取头附近的需求，远处的轮不到)。
SCAN	读取头来回跑到底，经过有需求的位址就回传资料。	效果不错，公平且适合用在大量需求的状况，但走到尽头有点浪费时间。
C-SCAN	类似SCAN，不过永远回到开头往後扫描。
Look	类似SCAN，不过扫到最後一个需求位置就往回折返。	可以省去跑到底的时间。
C-Look	类似Look，不过扫到最後一个需求位置之後，直接跳到开头继续扫描。