计算机操作系统中的磁盘存储器管理

外部存储设备管理是I／O系统设备管理的一个重要内容。外部存储设备中，磁盘存储器因其容量大、存取速度快、可随机存取等特点，是当前存放大量程序和数据的主要设备。在现代计算机系统中都配置了磁盘存储器，并以它为主来存放文件，因此对文件的操作都将涉及对磁盘的访问。磁盘I／O速度的高低和磁盘系统的可靠性，都将直接影响到系统性能，因此存储器管理成为现代操作系统的重要任务之一，优化的磁盘调度算法、采用高速缓存、虚拟盘、廉价磁盘冗余阵列等是提高磁盘I／O速度的主要技术和方法。

6.6.1 磁盘性能

1.磁盘结构

磁盘存储器由一个盘片或若干盘片组成的盘片组构成，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一张盘片和最下面的一张盘片的外侧不用以外，其他每张盘片的上下两面都可以存放数据，为记录盘面，每个记录盘面上有很多同心圆磁道，数据就存放在这些磁道上。对于活动臂硬盘，如图6-14所示，每个记录盘面都有一个读写磁头，它们都被安装在同一个活动臂上，随着活动臂向内或向外做径向移动，磁头从一个磁道移动到另一个磁道，任意时刻，所有记录盘面的磁头停留在各个记录盘面的半径相同的磁道上（也称柱面）。一个磁道被划分为若干扇区，一个扇区是一次读写的最小数据量，也叫一个数据块或盘块。相邻扇区间存在间隙，磁头通过间隙识别扇区的结束。如果每个磁道存放相同的数据量，则内层磁道的密度高于外层。为了提高磁盘的存储容量，充分利用外层磁道，可以将内外磁道划分成非相同数目的扇区，但为了减少这种几何形式变化对驱动程序的影响，大多数磁盘都隐藏了这些细节，向操作系统提供的是虚拟的磁盘规格，而不是实际的物理几何规格。

图6-14 磁盘结构

一个磁盘的容量由记录盘面数、每个记录盘面的磁道数、每个磁道的扇区数和每个扇区的字节数决定，或是由柱面数、每个柱面的磁道数、每个磁道的扇区数和每个扇区的字节数决定。

2.磁盘访问时间

磁盘设备在工作时主轴以恒定速率旋转，为了读或写，磁头必须先移动到所要求的磁道上，并等待所要求的扇区的开始位置旋转到磁头下，然后再开始读或写数据，因此磁盘的一次访问时间由三部分组成：

式中，T seek是寻道时间，是指把磁头移动到指定磁道上所经历的时间，该时间取决于磁头移过的磁道数，一般是5～30 ms；T latency是平均等待时间，是指扇区移动到磁头下所需的时间，硬盘一般为2～8 ms，软盘为50～100 ms；T t是数据传输的时间，与每次传输的字节数和盘片旋转速度有关。在这三部分中，寻道时间和平均等待时间基本上都与所传输数据的多少无关，而且它们通常占据了访问时间的大部分，数据传输所占用的时间很小，因此应尽量将相关信息集中存放，并尽量存放在相同磁道上或相邻磁道上，以减少活动臂移动缩短T seek的时间。

6.6.2 磁盘调度

磁盘因受制于机械部分，使得其处理速度的增长远不及CPU和内存速度的增长，磁盘的相对低速，使得磁盘管理成为提高磁盘系统性能的重要方法。磁盘是共享设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于访问磁盘的时间花费主要是在寻道时间上，因此磁盘调度的主要目标是使磁盘的平均寻道时间最少，另外平均相应时间、相应时间的可预期性也是调度策略的决策因素。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先及扫描等算法。

1.先来先服务（first come first served，FCFS）算法

FCFS根据进程请求访问磁盘的先后次序进行调度，算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。以有9个进程先后提出磁盘I／O请求为例，被请求访问的磁道依次为55，58，39，18，90，160，150，38，184，表6-4显示了采用FCFS算法进行调度时各进程被调度的次序、每次磁头移动的距离，以及磁头的平均移动距离。与其他几种调度算法相比，其平均寻道距离较大，故FCFS算法仅适用于请求磁盘I／O的进程数目较少的场合。

当进程提出的访问请求较均匀地遍布整个盘面，不具有集中倾向时，FCFS算法趋向于随机调度算法。由于FCFS算法未进行访问优化，在对磁盘访问请求较多的情况下，可能致使平均寻道时间和响应时间较长。该算法适用于请求访问磁盘的进程数目较少的情况。

2.最短寻道时间优先（shortest seek time first，SSTF）算法

该算法选择要求访问的磁道与当前磁头所在的磁道距离最近的进程作为下一个服务进程，以使每次的寻道时间最短。表6-4显示了按SSTF算法进行调度时，对9个进程进行调度的次序及磁头移动的情况。与FCFS算法对比可以看出，SSTF算法的平均磁头移动距离明显低于FCFS，因而SSTF比FCFS有更好的寻道性能。其缺点是对用户进程的请求响应机会不是均等的，对中间磁道的访问请求将得到最快的响应，对内外两侧磁道的访问请求响应较慢，在服务请求很多的情况下，对内外边缘磁道的请求将会被无限地延迟，因此有些请求的响应时间不可预期。另外这种算法不能保证平均寻道时间最短。

3.扫描（SCAN）算法

SCAN算法也叫电梯调度算法。通常电梯的运行是保持按一个方向运动，直到没有请求为止，然后改变方向，SCAN算法也是如此，算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑磁头当前的移动方向，当磁头正在自里向外移动时，算法所考虑的下一个访问对象应是其磁道既在当前磁道之外，又是距离最近的，这样自里向外直到再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择磁道在当前位置以内距离最近者进行访问，这样磁头又逐步地从外向里移动直到再无更里面的磁道要访问为止，从而避免了请求的相应时间不可预期的情况。表6-4显示了按SCAN算法对9个进程进行调度的次序及磁头移动的情况。

SCAN算法保持了SSTF算法平均响应时间小的优点，克服了集中服务于中间磁道和一些请求响应时间不可预期的缺点，但由于采用的是摆动式的扫描方法，两侧磁道被访问的频率仍然低于中间磁道，只是不像SSTF算法那么严重。

4.循环扫描（CSCAN）算法

对SCAN算法稍作改进，CSCAN算法规定磁头总是按同一方向单向移动。例如，只是自里向外移动，当磁头移到最外的磁道并访问后，立即返回到最里的欲访问的磁道，进行单向反复扫描。采用循环扫描方式后，SCAN算法中请求进程的请求延迟将从原来的2T减为T＋S max，其中，T为由里向外或由外向里单向扫描完要访问的磁道所需的寻道时间，而S max是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道（或相反）的寻道时间。

模拟研究的结果显示，在磁盘访问负荷较小的情况下，SCAN算法是最好的；而在中等以上负荷的情况下，CSCAN算法效果更佳。表6-4显示了CSCAN算法对9个进程调度的次序及每次磁头移动的距离。

调度算法的优劣与磁盘的使用环境因素有关，上述四种调度算法的性能比较见表6-4。

5.NStepSCAN算法

在SSTF、SCAN及CSCAN调度算法中，都可能会出现磁臂停留在某处不动的情况，例如，当进程对某一磁道有较高的访问频率，反复请求对某一磁道的I／O操作时，从而垄断了整个磁盘设备，这种现象被称为“磁臂黏着”（armstickiness）。在高密度磁盘上容易出现此情况。NStepSCAN算法也叫N步SCAN算法，是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列，当正在处理某子队列时，若又出现新的磁盘I／O请求，便将新请求进程放入其他队列，这样就可避免出现黏着现象。当N取很大值时，会使N步SCAN算法的性能接近于SCAN算法的性能；当N＝1时，N步SCAN算法便蜕化为FCFS算法。

6.FSCAN算法

FSCAN算法是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列，一个是由当前所有请求磁盘I／O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I／O的进程放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。

表6-4 四种调度算法的性能比较

常用磁盘调度算法特点描述见表6-5。

表6-5 常用磁盘调度算法特点描述(www.xing528.com)

6.6.3 提高磁盘I／O速度的方法

由于磁盘的I／O速度远低于对内存的访问速度，除了采用合适的磁盘调度算法进行寻道优化管理外，磁盘高速缓存也是目前提高磁盘I／O的主要技术之一。为了提高磁盘的访问速度，在内存中开辟一个区域来保存从磁盘中读出的一系列盘块中的信息，利用最近访问的即将被再次访问的可能性很大这个原理，所有的访问都不直接访问物理介质而是在这一区域中进行，当这一区域的访问达到系统预先设定的某一值时或者低速度设备空闲时，才刷新到物理介质，这样就大大提高了磁盘的访问速度。

1.磁盘高速缓存的形式

磁盘高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。在内存中的高速缓存可分成两种形式，第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I／O时（做磁盘高速缓存）共享，此时高速缓存的大小显然不再是固定的。当磁盘I／O的频繁程度较高时，该缓冲池可能包含更多的内存空间，而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间。

2.数据交付方式

数据交付指将磁盘高速缓存中的数据传送给请求者进程。当有一进程请求访问某个盘块中的数据时，首先检查磁盘高速缓存中是否有该盘块数据的拷贝，若有其拷贝，便直接从高速缓存中提取数据交付给请求者进程；否则，被请求的盘块数据就首先被写进磁盘高速缓存，然后再从高速缓存中提取并交付给进程，这样就避免了访盘操作，从而提高磁盘I／O速度。

系统可以采取两种方式将磁盘高速缓存中的数据交付给请求进程：

（1）数据交付。直接将高速缓存中的数据传送到请求者进程的内存工作区中。

（2）指针交付。只将指向高速缓存中某区域的指针传送给请求者进程。

显然后一种方式节省了数据从磁盘高速缓存到进程的内存工作区的时间，也允许其他进程共享读／写高速缓存数据。

3.磁盘高速缓存中数据的置换算法

如同请求调页（段）一样，在将磁盘中的盘块数据读入高速缓存时，同样会出现因高速缓存中已装满盘块数据而需要将该部分数据先换出的问题，因此也必然存在着采用哪种置换算法的问题。较常用的置换算法仍然是最近最久未使用算法LRU、最近未使用算法NRU，以及最少使用算法LFU等。但由于请求调页中的联想存储器与磁盘高速缓存的工作情况不同，因而置换算法中所考虑的因素也有所差异。目前不少系统在设计其磁盘高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还兼顾了以下因素。

1）访问频率

联想存储器的访问频率远远高于磁盘高速缓存的访问频率。通常，每执行一条指令时，便可能访问一次联想存储器，因此联想存储器的访问频率基本上与指令执行的频率相当。而对高速缓存的访问频率则与磁盘I／O的频率相当。

2）可预见性

预见高速缓存中的各盘块数据哪些可能很快就再被访问，哪些可能在较长时间内不会再被访问。会有相当一部分是可预知的，例如，对二次地址及目录块等，在它被访问后，可能会很久都不再被访问。又如，正在写入数据的未满盘块，可能会很快又被访问。

3）数据的一致性

由于高速缓存在内存中，而内存一般又是一种易失性的存储器，一旦系统发生故障。存放在高速缓存中的数据将会丢失，而其中有些盘块（如索引结点盘块）中的数据已被修改，但尚未拷回磁盘，因此当系统发生故障后，可能会造成数据的不一致性。

基于上述考虑，提出了一种频率优先权重优先的替换算法，将高速缓存中的所有盘块数据按写回磁盘的优先顺序拉成一条LRU链，对于那些会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们能被优先写回磁盘，以减少发生数据不一致性的概率，或者可以尽早地腾出高速缓存的空间；对于那些可能很快就要再使用的盘块数据，应挂在LRU链的尾部，以便在不久以后需要时，只要该数据块尚未从链中移至链首而被写回磁盘，便可直接在LRU链中找到它们。

4.高速缓存中的数据需周期性地写回磁盘

根据LRU算法，链中任一元素在被访问之后，总是又被挂到链尾而不被写回磁盘，那些一直未被访问的元素，才有可能移到链首，并被写回磁盘，而那些经常被访问的盘块数据可能会一直保留在高速缓存中，长期不会被写回磁盘。

为了解决这一问题，在UNIX系统中专门增设了一个修改（update）程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC，该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30 s。这样因系统故障所造成的工作损失不会超过30 s的劳动量。而在MS-DOS中所采用的方法是，只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”（write-through cache）。MS-DOS所采用的写回方式，几乎不会造成数据的丢失，但须频繁地启动磁盘。

在系统中设置了磁盘高速缓存后，能显著地减少等待磁盘I／O的时间。除此之外还有以下几种能有效提高磁盘I／O速度的方法。

1）提前读

用户（进程）对文件进行访问时，经常采用顺序访问方式，即顺序地访问文件各盘块的数据，在这种情况下，在读当前块时可以预知下一次要读的盘块，因此可以采取预先读方式，即在读当前块的同时，将下一个盘块（提前读的块）中的数据也读入缓冲区，这样当下一次要读该盘块中的数据时，由于该数据已被提前读入缓冲区，因而此时便可直接从缓冲区中取得下一盘块的数据，而不需再去启动磁盘I／O，从而大大减少了读数据的时间，这也就等效于提高了磁盘I／O的速度。如在UNIX系统、OS／2，以及3Plus和Netware等网络OS中都已采用了“提前读”功能。

2）延迟写

延迟写是指在缓冲区A中的数据，本应立即写回磁盘，但考虑到该缓冲区中的数据在不久之后可能还会再被本进程或其他进程访问（共享资源），因而并不立即将该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾，随着空闲缓冲区的使用，缓冲区也缓缓往前移动，一直移至空闲缓冲队列之首。当再有进程申请到该缓冲区时，才将该缓冲区中的数据写入磁盘，而把该缓冲区作为空闲缓冲区分配出去。当该缓冲区A仍在队列中时，任何访问该数据的进程都可直接读出其中的数据而不必去访问磁盘，这样又可进一步减小等效的磁盘I／O时间，同样“延迟写”功能已在UNIX系统、OS／2等OS中被广泛采用。

3）优化文件物理块的分布

另一种提高磁盘I／O速度的重要措施是优化文件物理块的分布，使磁头的移动距离最小。虽然链接分配和索引分配方式都允许将一个文件的物理块分散在磁盘的任意位置，但如果将一个文件的多个物理块安排得过于分散，必然会增加磁头的移动距离。例如，将文件的第一个盘块安排在最里的一条磁道上，而把第二个盘块安排在最外的一条磁道上，这样，在读完第一个盘块后转去读第二个盘块时，磁头要从最里的磁道移到最外的磁道上。如果能将这两个数据块安排在属于同一条磁道的两个盘块中，显然会因减少磁头在磁道间的移动而大大提高访问速度。对文件盘块位置的优化，应在为文件分配盘块时进行。

4）虚拟盘

虚拟盘是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行不是在磁盘上而是在内存中。这些对用户都是透明的，即用户并不会发现这与真正的磁盘操作有什么不同，而仅仅是略微快些而已。虚拟盘的主要问题是，它是易失性存储器，一旦系统或电源发生故障或系统再启动时，原来保存在虚拟盘中的数据将会丢失。因此虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。虚拟盘与磁盘高速缓存的主要区别在于：虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。例如，RAM盘在开始时是空的，仅当用户（程序）在RAM盘中创建了文件后，RAM盘中才有内容。