操作系统-磁盘存储管理

1、磁盘存储器的管理,磁盘存储器管理的主要任务： 为文件分配必要地存储空间 合理地组织文件的存取方式，提高对文件的访问速度 提高磁盘存储空间的利用率，提高对磁盘的I/O速度 采取必要地冗余措施，确保文件系统的可靠性。 影响磁盘性能和数据安全性的主要因素： 转速、寻道时间 磁盘控制器：IDE、SCSI磁盘控制器 RAID（廉价磁盘冗余队列）磁盘容错技术 磁盘管理算法：磁盘调度算法和磁盘高速缓存。,磁盘存储器的管理,磁盘性能简述 数据的组织和格式 磁盘设备包括一或多个物理盘片，每个磁盘片分一个或两个存储面(surface)，每个磁盘面被组织成若干个同心环，这种环称为磁道(track)，各磁道之间留有必

2、要的间隙。所有磁道由外向内依次由0开始编号，称为磁道号。 每条磁道上可存储相同数目的二进制位。这样，磁盘密度即每英寸中所存储的位数，显然是内层磁道的密度较外层磁道的密度高。每条磁道又被逻辑上划分成若干个扇区(sectors)，软盘大约为832个扇区，硬盘则可多达数百个。一个扇区称为一个盘块(或数据块)，常常叫做磁盘扇区。各扇区之间保留一定的间隙。 扇区是磁盘进行I/O传输的基本单位，也是磁盘空间分配的基本单位。,磁盘的结构和布局,磁盘的结构和布局,为了在磁盘上存储数据，必须先将磁盘低级格式化。下图磁盘中每条磁道含有30个固定大小的扇区，每个扇区容量为600个字节，其中512个字节存放数据，其余

3、的用于存放控制信息。每个扇区包括两个字段：（1）标识符字段，其中一个字节的SYNCH定界符，利用磁道号、磁头号及扇区号三者来标识一个扇区；CRC字段用于段校验。（2）数据字段，其中可存放512个字节的数据。,磁盘扇区,对磁盘，可以从不同的角度进行分类：硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头(移动头)磁盘等。 固定头磁盘 这种磁盘在每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道，并进行并行读/写，有效地提高了磁盘的I/O速度。这种结构的磁盘主要用于大容量磁盘上。 移动头磁盘 每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该

4、磁头必须能移动以进行寻道。移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其结构简单，故仍广泛应用于中小型磁盘设备中。在微型机上配置的温盘和软盘都采用移动磁头结构。,磁盘的类型,磁盘的访问时间Ta表示为： 访问时间=寻道时间+旋转时间+传输时间 磁盘接收到读指令后，磁头从当前位置移动到目标磁道位置，所需时间为寻道时间 旋转磁盘，定位数据所在的扇区，所需时间为旋转延迟 从磁盘上读取数据，时间为数据传输时间,磁盘访问时间,寻道时间Ts 这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即,Ts = m n +s,其中，m是一常数

5、，与磁盘驱动器的速度有关。对于一般磁盘，m=0.2；对于高速磁盘，m0.1，磁臂的启动时间约为2 ms。 对于一般的温盘，其寻道时间将随寻道距离的增加而增大，大体上是530 ms。,磁盘访问时间,旋转延迟时间Tr 将磁头移动到指定扇区下面所经历的时间。 Tr=1 /(2r)，r为磁盘转速（转数/单位时间，秒） 不同的磁盘类型中，旋转速度至少相差一个数量级，如软盘为300 r/min，硬盘一般为720015 000 r/min，甚至更高。 对于磁盘旋转延迟时间而言，如硬盘，旋转速度为15 000 r/min，每转需时4 ms，平均旋转延迟时间Tr为2 ms； 而软盘，其旋转速度为 300 r/m

6、in或600 r/min，这样，平均Tr为50100 ms。,磁盘访问时间,传输时间Tt 这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每次所读/写的字节数b和旋转速度有关:,其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，即N = 2 * b时，Tt=1/(2r)，Tt与Tr相同。,磁盘访问时间,磁盘的访问时间Ta表示为： 访问时间=寻道时间+旋转时间+传输时间 磁盘接收到读指令后，磁头从当前位置移动到目标磁道位置，所需时间为寻道时间 旋转磁盘，定位数据所在的扇区，所需时间为旋转延迟 从磁盘上读取数据，时间为数据传输时间,

7、磁盘访问时间,由上式可以看出，在访问时间中，寻道时间和旋转延迟时间与所读/写数据的多少无关，它通常占据了访问时间中的大部分。 例如，假定寻道时间和旋转延迟时间平均为20 ms，而磁盘的传输速率为10 MB/s，如果要传输10 KB的数据，此时总的访问时间为21 ms，可见传输时间所占比例是非常小的。当传输100 KB数据时，其访问时间也只是30 ms，即当传输的数据量增大10倍时，访问时间只增加约50%。 目前磁盘的传输速率已达80 MB/s以上，数据传输时间所占的比例更低。可见，适当地集中数据(不要太零散)传输，将有利于提高传输效率。,磁盘访问时间,磁盘是一种共享设备，当有多个进程共同请求磁

8、盘时，需要采用合理地磁盘调度方法，保证各个进程对磁盘的平均访问时间（寻道时间）最少。即磁盘调度的目标是使磁盘的平均寻道时间最少。 先来先服务(FCFS) 这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。,磁盘调度,FCFS调度算法,磁盘调度,有9个进程先后提出磁盘I/O请求。进程(请求者)按发出请求的先后次序排队。平均寻道距离为55.3条磁道，该方法平均寻道距离较大，故FCFS算法仅适用于请求磁盘I/O的进程数

9、目较少的场合。,最短寻道时间优先(SSTF) 该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。,磁盘调度,SSTF调度算法,磁盘调度,SSTF算法的平均每次磁头移动距离明显低于FCFS的距离，因而较FCFS有更好的寻道性能，曾被广泛采用。,SSTF调度算法,磁盘调度,FCFS调度算法,进程“饥饿”现象 SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。 因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必然优先满足

10、。对SSTF算法修改后形成SCAN算法，即可防止老进程出现“饥饿”现象。,扫描(SCAN)算法,SCAN算法 该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。 例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。 由于在这种算法中磁头移动的规律颇似电梯的

11、运行，因而又常称之为电梯调度算法。,扫描(SCAN)算法,SCAN调度算法示例,扫描(SCAN)算法,SCAN算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大、中、小型机器和网络中的磁盘调度。但SCAN也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。,循环扫描(CSCAN)算法,为了减少这种延迟，CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的

12、磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。采用循环扫描方式后，上述请求进程的请求延迟将从原来的2T减为T + Smax，其中，T为由里向外或由外向里单向扫描完要访问的磁道所需的寻道时间，Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道(或相反)的寻道时间。,循环扫描(CSCAN)算法,CSCAN调度算法示例,循环扫描(CSCAN)算法,CSCAN调度算法示例,循环扫描(CSCAN)算法,SCAN调度算法示例,N_Step SCAN算法 在SSTF、 SCAN及CSCAN几种调度算法中，都可能会出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有较高

13、的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”(Armstickiness)。在高密度磁盘上容易出现此情况。 N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能； 当N=1时，N步SCAN算法便蜕化为FCFS算法。,NStepSCAN和

14、FSCAN调度算法,FSCAN算法 FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。,NStepSCAN和FSCAN调度算法,磁盘高速缓存，并非通常意义下的内存和CPU之间所增设的一个小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此，高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。 磁盘高速缓存

15、的形式 在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响； 把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。此时，高速缓存的大小显然不再是固定的。当磁盘I/O的频繁程度较高时，该缓冲池可能包含更多的内存空间；而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间。 容量大，通常存储全局范围，经常访问的重要数据：文件系统目录，文件分配表等。但是需要由主机进行管理。增加主机的负担。,磁盘高速缓存,数据交付方式 数据交付(Data Delivery)是指将磁盘高速缓存中的数据传送给请求者进程。 当有一进程请求访

16、问某个盘块中的数据时，先去查看磁盘高速缓存，查看是否存在所需的盘块数据的拷贝。若有，直接从高速缓存中提取数据并交付给请求者进程，由此避免了访盘操作，提高了访问速度； 否则，应先从磁盘中将所要访问的数据读入并交付给请求者进程，同时也将数据送高速缓存。当以后再需要访问该盘块的数据时，便可直接从高速缓存中提取。,磁盘高速缓存,数据交付给请求进程的方式： 数据交付：直接将高速缓存中的数据，传送到请求者进程的内存工作区中。 指针交付：只将指向高速缓存中某区域的指针交付给请求者进程。该方式由于所传送的数据量少，节省了数据从磁盘高速缓存到进程的内存工作区的时间。,磁盘高速缓存,磁盘高速缓存置换算法 在将磁盘

17、中的盘块数据读入高速缓存时，会出现因高速缓存中已装满盘块数据而需要将该数据先换出的问题。相应地，也必然存在着采用哪种置换算法的问题。 常用的置换算法是： 最近最久未使用算法LRU 最近未使用算法NRU 最少使用算法LFU等,磁盘高速缓存,置换算法的考虑因素 访问频率 通常，每执行一条指令时，便可能访问一次联想存储器，亦即联想存储器的访问频率，基本上与指令执行的频率相当。而对高速缓存的访问频率，则与磁盘I/O的频率相当。因此，高速缓存的访问频率远远低于联想存储器的访问频率。 可预见性 在高速缓存中的各盘块数据，有哪些数据可能在较长时间内不会再被访问，又有哪些数据可能很快就再被访问，会有相当一部分

18、是可预知的。例如，对目录块，在它被访问后，可能会很久都不再被访问。而正在写入数据的未满盘块，可能会很快又被访问。 数据的一致性 高速缓存一种易失性的存储器，一旦系统发生故障，存放在高速缓存中的数据将会丢失；而其中有些盘块(如索引结点盘块)中的数据已被修改，但尚未拷回磁盘，因此，当系统发生故障后，可能会造成数据的不一致性。,磁盘高速缓存,置换方法 基于上述因素，可以将高速缓存中的所有盘块数据组织成一条LRU链。对于那些会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们能被优先写回磁盘，以减少发生数据不一致性的概率，或者可以尽早腾出高速缓存的空间。 对于那

19、些可能在不久之后还要使用的盘块数据，挂在LRU链的尾部，以便在不久以后需要时，只要该数据块尚未从链中移至链首而被写回磁盘，便可直接到高速缓存中(即LRU链中)去寻找这些数据块。,磁盘高速缓存,LRU链中任一元素在被访问之后，总是又被挂到链尾而不被写回磁盘；只是一直未被访问的元素，才有可能移到链首并被写回磁盘。那些经常要被访问的盘块数据，可能会一直保留在高速缓存中，长期不会被写回磁盘。 例如，一位学者一上班便开始撰写论文，并边写边修改，他正在写作的论文一直保存在高速缓存的LRU链中。如果在快下班时，系统突然发生故障，这样，存放在高速缓存中的已写论文将随之消失，致使他枉费了一天的劳动。 为了解决这

20、一问题，UNIX系统增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC,强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30 s。 在MS-DOS中所采用的方法是: 只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-through cache)。MS-DOS所采用的写回方式，几乎不会造成数据的丢失，但须频繁地启动磁盘。,周期性地写回磁盘,提前读(Read-ahead) 用户(进程)对文件进行访问时，经常采用顺序访问方式，即顺序地访问文件各盘块的数据。在这种

21、情况下，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式，即在读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入缓冲区。 这样，当下一次要读该盘块中的数据时，由于该数据已被提前读入缓冲区，此时便可直接从缓冲区中取得下一盘块的数据，而不需再去启动磁盘I/O，从而大大减少了读数据的时间。这也就等效于提高了磁盘I/O的速度。 “提前读”功能已被广泛采用，如在UNIX系统、OS/2都已采用该功能。,提高磁盘I/O速度的其它方法,延迟写 延迟写是指在缓冲区A中的数据，本应立即写回磁盘，但考虑到该缓冲区中的数据在不久之后可能还会再被本进程或其它进程访问(共享资源)，因而并不立即将

22、该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾。随着空闲缓冲区的使用，缓冲区也缓缓往前移动，直至移到空闲缓冲队列之首。当再有进程申请到该缓冲区时，才将该缓冲区中的数据写入磁盘，而把该缓冲区A作为空闲缓冲区分配出去。当该缓冲区A仍在队列中时，任何访问该数据的进程，都可直接读出其中的数据而不必去访问磁盘。 “延迟写”可进一步减小磁盘I/O时间。UNIX系统、OS/2等OS中广泛采用了“延迟写”技术。,提高磁盘I/O速度的其它方法,优化物理块的分布 另一种提高磁盘I/O速度的重要措施是优化文件物理块的分布，使磁头的移动距离最小。 链接分配和索引分配方式都允许将一个文件的物理块分散在磁盘

23、的任意位置，但如果将一个文件的多个物理块安排得过于分散，会增加磁头的移动距离。 例如，将文件的第一个盘块安排在最里的一条磁道上，而把第二个盘块安排在最外的一条磁道上，这样，在读完第一个盘块后转去读第二个盘块时，磁头要从最里的磁道移到最外的磁道上。 如果将这两个数据块安排在属于同一条磁道的两个盘块上，显然会由于消除了磁头在磁道间的移动，而大大提高对这两个盘块的访问速度。,提高磁盘I/O速度的其它方法,盘块优化方法： 对文件盘块位置的优化，应在为文件分配盘块时进行。如果系统中的空白存储空间是采用位示图方式表示的，则从位示图中找到一片相邻接的多个空闲盘块,将同属于一个文件的盘块安排在同一条磁道上或相

24、邻的磁道上。,提高磁盘I/O速度的其它方法,但当系统采用线性表(链)法来组织空闲存储空间时，要为一文件分配多个相邻接的盘块，就相对困难。此时，可以将在同一条磁道上的若干个盘块组成一簇， 例如，一簇包括4个盘块，在分配存储空间时，以簇为单位进行分配。这样就可以保证在访问这几个盘块时，不必移动磁头或者仅移动一条磁道的距离，从而减少了磁头的平均移动距离。,虚拟盘 又称为RAM盘，是指利用内存空间去仿真磁盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。 虚拟盘的主要问题是：它是易失性存储器，故一旦系统或电源发生故障，或系统再启动时，

25、原来保存在虚拟盘中的数据将会丢失。因此，虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。 虚拟盘与磁盘高速缓存的主要区别在于: 虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。例如，RAM盘在开始时是空的，仅当用户(程序)在RAM盘中创建了文件后，RAM盘中才有内容。,虚拟盘,RAID(Redundant Array of Independent Inexpensive Disks)： 廉价磁盘冗余阵列或者独立磁盘冗余阵列 “独立”强调RAID阵列的重要性和可靠性 “廉价”强调RAID磁盘阵列中采用的是相对较小和便宜的磁盘。 RAID阵列能够以较低的成本，提供大

26、容量、快速和安全可靠地磁盘存储系统。 RAID包括以下部分： 一组可以并行工作的磁盘构成的磁盘阵列 磁盘阵列管理软件，该软件把逻辑上连续的一组数据交叉分布存储在磁盘阵列中的各个磁盘上。,廉价磁盘冗余阵列,并行交叉存取 为了提高对磁盘的访问速度，已把在大、中型机中应用的交叉存取(Interleave)技术应用到了磁盘存储系统中。在该系统中，有多台磁盘驱动器，系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。 当要将一个盘块的数据传送到内存时，采取并行传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。 例如，在存放一个文件时，可将该文件中的第一个数据子块放在第一个磁盘驱动器上；将文件的第二个数据子块放在第二个磁盘上；将第N个数据子块，放在第N个驱动器上。以后在读取数据时，采取并行读取方式，即同时从第1N个数据子块读出数据，这样便把磁盘I/O的速度提高了N-1倍。,廉价磁盘冗余阵列,磁盘并行交叉存取方式,廉价磁盘冗余阵列,RAID的分级 RAID在刚被推出时分成6级，即RAID 0级至RAID 5级，后来又增加了RAID 6级和RAID 7级。 RAID 0级。本级仅提供了并行交叉存取。它虽能有效地提高磁盘