操作系统课件第7章 磁盘存储器管理

1、磁盘存储器管理磁盘存储器管理内容提要内容提要磁盘磁盘i/oi/o外存分配方法外存分配方法空闲存储空间的管理空闲存储空间的管理磁盘容错技术磁盘容错技术文件系统性能的改善文件系统性能的改善数据一致性数据一致性磁盘存储管理的主要任务磁盘存储管理的主要任务为文件分配必要的空间为文件分配必要的空间合理组织文件存取方式合理组织文件存取方式提高磁盘空间的利用率提高磁盘空间的利用率提高对磁盘的提高对磁盘的i/oi/o速度速度采取必要的冗余措施，确保系统可靠性采取必要的冗余措施，确保系统可靠性磁盘磁盘i/oi/o 几乎所有可随机存取的文件，都存几乎所有可随机存取的文件，都存放在磁盘上。磁盘放在磁盘上。磁盘i/o

2、i/o速度的高低，将速度的高低，将直接影响到文件系统的性能。如何改善直接影响到文件系统的性能。如何改善磁盘磁盘i/oi/o的性能，称为提高文件系统性的性能，称为提高文件系统性能的关键。能的关键。提高磁盘提高磁盘i/oi/o速度的主要途径速度的主要途径选择性能好的磁盘选择性能好的磁盘采用好的磁盘调度算法采用好的磁盘调度算法设置磁盘高速缓冲区设置磁盘高速缓冲区磁盘数据组织磁盘数据组织面面磁道磁道扇区扇区每个扇区包括两个字段：每个扇区包括两个字段：标识符字段标识符字段和和数据字段数据字段磁盘的分类磁盘的分类固定头磁盘固定头磁盘移动头磁盘移动头磁盘磁盘访问时间磁盘访问时间寻道时间寻道时间t ts s旋

3、转延迟时间旋转延迟时间t tr r传输时间传输时间t tt t访问时间访问时间t ta a 可表示为：可表示为：磁盘调度算法磁盘调度算法先来先服务先来先服务最短寻道时间优先最短寻道时间优先扫描算法扫描算法循环扫描算法循环扫描算法先来先服务先来先服务fcfs这是最简单的磁盘调度算法这是最简单的磁盘调度算法根据进程请求访问磁盘的先后次序进行根据进程请求访问磁盘的先后次序进行调度调度优点是公平、简单，且每个进程的要求优点是公平、简单，且每个进程的要求都可得到处理都可得到处理由于未对寻道进行优化，致使平均寻道由于未对寻道进行优化，致使平均寻道时间可能较长时间可能较长最短寻道时间优先最短寻道时间优先ss

4、tfsstf该算法选择这样的进程，其要求访问的该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近。磁道与当前磁头所在的磁道距离最近。该算法不能保证平均寻道时间最短。该算法不能保证平均寻道时间最短。进程进程“饥饿饥饿”现象现象 sstf sstf算法虽然获得较好的寻道性能，算法虽然获得较好的寻道性能，但它可能导致某些进程但它可能导致某些进程“饥饿饥饿”。若只。若只要有新进程到达，且其所要访问的磁道要有新进程到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种与磁头当前所在磁道的距离较近，这种新进程的新进程的i/oi/o请求必被优先满足。请求必被优先满足。scanscan算法

5、算法 scan scan算法不仅考虑到欲访问的磁算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。由于这种算法中磁头的当前移动方向。由于这种算法中磁头移动的规律类似电梯的运行，又称磁头移动的规律类似电梯的运行，又称为为电梯调度算法电梯调度算法。循环扫描算法循环扫描算法cscancscan scan scan算法既能获得较好的寻道时算法既能获得较好的寻道时间，又能防止进程饥饿，故被广泛应用。间，又能防止进程饥饿，故被广泛应用。为防止访问刚移动过的磁道的进程被严为防止访问刚移动过的磁道的进程被严重推迟，重推迟，cscancscan算法规

6、定磁头单向移动。算法规定磁头单向移动。n-step-scann-step-scan算法算法 在在sstfsstf、scanscan和和cscancscan几种调度几种调度算法中，都可能出现磁臂停留在某处不算法中，都可能出现磁臂停留在某处不动的情况，称为磁臂粘着。动的情况，称为磁臂粘着。nn步步scanscan算法是将磁盘请求队列分成若干个长度算法是将磁盘请求队列分成若干个长度为为nn的的子队列子队列，磁盘调度将按，磁盘调度将按fcfsfcfs算法算法一次处理这些子队列。每处理一个队列一次处理这些子队列。每处理一个队列时，又按时，又按scanscan算法，对一个队列处理算法，对一个队列处理完后，

7、又处理其它队列，以避免粘着现完后，又处理其它队列，以避免粘着现象。象。fscanfscan算法算法fscanfscan算法实质上是算法实质上是nn步步scanscan算法的算法的简化简化它将磁盘请求队列分成两个子队列它将磁盘请求队列分成两个子队列一是当前所有请求磁盘一是当前所有请求磁盘i/oi/o进程形成的进程形成的队列，按队列，按scanscan算法进行处理算法进行处理另一个队列是新出现的进程队列，将它另一个队列是新出现的进程队列，将它们排入另一个等待处理的请求队列，新们排入另一个等待处理的请求队列，新请求都将被推出到下一次扫描时处理请求都将被推出到下一次扫描时处理分配外存空间的主要问题分配

8、外存空间的主要问题怎样才能有效地利用外存空间怎样才能有效地利用外存空间提高对文件的访问速率提高对文件的访问速率常用的外存分配方法常用的外存分配方法连续分配连续分配链接分配链接分配索引分配索引分配连续分配连续分配fscanfscan算法实质上是算法实质上是nn步步scanscan算法的算法的简化简化它将磁盘请求队列分成两个子队列它将磁盘请求队列分成两个子队列一是当前所有请求磁盘一是当前所有请求磁盘i/oi/o进程形成的进程形成的队列，按队列，按scanscan算法进行处理算法进行处理另一个队列是新出现的进程队列，将它另一个队列是新出现的进程队列，将它们排入另一个等待处理的请求队列，新们排入另一个

9、等待处理的请求队列，新请求都将被推出到下一次扫描时处理请求都将被推出到下一次扫描时处理磁盘空间的连续分配磁盘空间的连续分配count01234567f8910111213141516171819tr202122232425262728293031maillistfilestartlengthcounttrmaillistf0214319628642目录目录连续分配的主要优点连续分配的主要优点顺序访问容易顺序访问容易顺序访问速度快顺序访问速度快连续分配的主要缺点连续分配的主要缺点要求有连续的存储空间要求有连续的存储空间必须事先知道文件的长度必须事先知道文件的长度链接分配链接分配在采用链接分配方式

10、时，可通过在每在采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链文件的多个离散的盘块链接成一个链表，由此形成的物理文件称为链接文表，由此形成的物理文件称为链接文件件链接分配采取离散分配方式，从而消链接分配采取离散分配方式，从而消除了外部碎片除了外部碎片链接方式可分为：链接方式可分为：隐式链接隐式链接和和显式链显式链接接两种两种磁盘空间的连续分配磁盘空间的连续分配count01234567f8910111213141516171819tr202122232425262728293031maillistfilestart

11、endjeep925目录目录1625110-1隐式链接分配的主要问题隐式链接分配的主要问题它只适于顺序访问，对随机访问是极它只适于顺序访问，对随机访问是极其低效的其低效的只通过链接指针来将一大批离散的盘只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差块链接起来，其可靠性较差为提高检索速度和减小指针所占用的为提高检索速度和减小指针所占用的存储空间，可将几个盘块组成一个簇存储空间，可将几个盘块组成一个簇显式链接显式链接 这是把用于链接文件各物理块的这是把用于链接文件各物理块的指针，显式地存放在内存的一张链接指针，显式地存放在内存的一张链接表。该表在整个磁盘仅设置一张，该表。该表在整个磁盘仅

12、设置一张，该表称为文件分配表表称为文件分配表fatfat。ms-dosms-dos及及os/2os/2等操作系统都采用等操作系统都采用fatfat。显式链接结构显式链接结构fcb2物理块号物理块号fat0123450451ms-dosms-dos的文件物理结构的文件物理结构fcb a40fcb b9123456789fat611105eofeof链接分配方式存在的问题链接分配方式存在的问题不能支持高效地直接存取不能支持高效地直接存取fatfat需占用较大的内存空间需占用较大的内存空间索引分配的引入索引分配的引入为每个文件分配一个索引块，记录分为每个文件分配一个索引块，记录分配给该文件的所有盘块

13、号配给该文件的所有盘块号索引分配方式支持直接访问索引分配方式支持直接访问索引分配方式的主要问题，是可能花索引分配方式的主要问题，是可能花费较多的外存空间费较多的外存空间对较大文件而言，索引分配方式是优对较大文件而言，索引分配方式是优于链接分配的；但对小文件而言，索于链接分配的；但对小文件而言，索引块的利用率极低引块的利用率极低索引分配方法索引分配方法count01234567f8910111213141516171819202122232425262728293031file块序号块序号jeep19目录目录19161102511119两级索引分配两级索引分配主索引主索引740360112536

14、07401125105106254356357985第二级索引第二级索引985012105106254356357磁盘空间磁盘空间空闲存储空间管理的引入空闲存储空间管理的引入系统应为分配存储空间而设置相应的数系统应为分配存储空间而设置相应的数据结构据结构系统应提供对存储空间进行分配和回收系统应提供对存储空间进行分配和回收的功能的功能常用的空闲空间管理方法包括：空闲表常用的空闲空间管理方法包括：空闲表法、空闲链表法、位示图法及成组链接法、空闲链表法、位示图法及成组链接法法空闲表法空闲表法系统为外存所有空闲区建立一张空闲表，系统为外存所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项。每个空闲区

15、对应一个空闲表项。空闲表包括：序号、该空闲区空闲表包括：序号、该空闲区空闲盘块表空闲盘块表序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数12342493155空闲链表法空闲链表法空闲链表法是将所有的空闲盘区拉成一空闲链表法是将所有的空闲盘区拉成一条空闲链。条空闲链。有两种链表形式：空闲盘块链和空闲盘有两种链表形式：空闲盘块链和空闲盘区链区链空闲盘块链空闲盘块链将空闲存储空间以盘块为基本单元拉成将空闲存储空间以盘块为基本单元拉成一条链表一条链表优点是用于分配和回收一个盘块的过程优点是用于分配和回收一个盘块的过程非常简单非常简单缺点是空闲盘块链可能很长缺点是空闲盘块链可能很长空闲盘区链空

16、闲盘区链将所有的空闲盘区将所有的空闲盘区( (每个盘区包含若干每个盘区包含若干个盘块个盘块) )拉成一条链。在每个盘区上隐拉成一条链。在每个盘区上隐含用于指示下一个盘区的指针外，还标含用于指示下一个盘区的指针外，还标有指明本盘区大小的信息有指明本盘区大小的信息盘区分配方法采用首次适应算法盘区分配方法采用首次适应算法该方法与空闲盘块链的优缺点刚好相反，该方法与空闲盘块链的优缺点刚好相反，即分配和回收过程较复杂，但空闲盘区即分配和回收过程较复杂，但空闲盘区链较短。链较短。位示图法位示图法位示图是利用一位二进制数来表示磁盘位示图是利用一位二进制数来表示磁盘中一个盘块的使用情况中一个盘块的使用情况当其

17、值是当其值是0 0时，表示盘块空闲；为时，表示盘块空闲；为1 1时，时，表示盘块已分配。表示盘块已分配。由磁盘所有盘块所对应的位构成的集合，由磁盘所有盘块所对应的位构成的集合，称为位示图。称为位示图。位示图位示图1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 00 0 0 1 1 1 1 1 1 0 0 0 0 1 1 11 1 1 0 0 0 1 1 1 1 1 1 0 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16123416var map: array 1m, 1n成组链接法成组链接法 成组链接法结合了空闲表法和空闲成组链接法结合了空闲

18、表法和空闲链法的优点，而克服了两种方法均有的链法的优点，而克服了两种方法均有的表太长的缺点，在表太长的缺点，在unixunix中被采用。中被采用。空闲盘块的组织空闲盘块的组织空闲盘块栈，用来存放可用的空闲盘块空闲盘块栈，用来存放可用的空闲盘块号和盘块数号和盘块数所有空闲盘块被分成若干组所有空闲盘块被分成若干组将每组含有的盘块数和该组所有的盘块将每组含有的盘块数和该组所有的盘块号记入前一组的第一盘块中号记入前一组的第一盘块中磁盘容错技术磁盘容错技术容错技术是通过在系统中设置冗余部件容错技术是通过在系统中设置冗余部件来提高系统可靠性的一种技术。来提高系统可靠性的一种技术。磁盘容错技术是通过增加冗余

19、的磁盘驱磁盘容错技术是通过增加冗余的磁盘驱动器、磁盘控制器等，来提高磁盘系统动器、磁盘控制器等，来提高磁盘系统的可靠性。的可靠性。磁盘容错技术通常也称为系统容错技术磁盘容错技术通常也称为系统容错技术磁盘容错技术的级别磁盘容错技术的级别sft-sft-是低级磁盘容错技术，主要用于是低级磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢防止磁盘表面发生缺陷所引起的数据丢失失sft-sft-是中级磁盘容错技术，主要用于是中级磁盘容错技术，主要用于防止磁盘驱动器和磁盘控制器故障所引防止磁盘驱动器和磁盘控制器故障所引起的系统不能正常工作起的系统不能正常工作sft-sft-是高级系统容错技术是高级系

20、统容错技术第一级容错技术第一级容错技术 第一级容错技术第一级容错技术sft-sft-是最早出现是最早出现的、也是最基本的一种磁盘容错技术。的、也是最基本的一种磁盘容错技术。它包含双份目录、双份文件分配表及写它包含双份目录、双份文件分配表及写后校验等措施。后校验等措施。双份目录和双份文件分配表双份目录和双份文件分配表在不同的磁盘或磁盘的不同区域中，分在不同的磁盘或磁盘的不同区域中，分别建立两份目录表和别建立两份目录表和fatfat。一份称为主目录及主一份称为主目录及主fatfat；另一份称为；另一份称为备份目录及备份备份目录及备份fatfat。一旦磁盘表面缺陷而造成损坏时，系统一旦磁盘表面缺陷而

21、造成损坏时，系统启用备份文件目录及备份启用备份文件目录及备份fatfat，从而保，从而保证磁盘上的数据仍是可访问的，并将损证磁盘上的数据仍是可访问的，并将损坏区写入坏块表中。坏区写入坏块表中。热修复重定向热修复重定向系统将一定的磁盘容量作为热修复重定系统将一定的磁盘容量作为热修复重定向区，用于存放当前盘块有缺陷时的代向区，用于存放当前盘块有缺陷时的代写数据写数据对写入该区的所有数据进行登记，以便对写入该区的所有数据进行登记，以便于以后对数据进行访问。于以后对数据进行访问。写后读校验方式写后读校验方式为保证数据都能写入完好的盘块中，每为保证数据都能写入完好的盘块中，每次写入一个数据块后，应立即从

22、磁盘上次写入一个数据块后，应立即从磁盘上读出送入另一缓冲区，再将该缓冲区与读出送入另一缓冲区，再将该缓冲区与内存中仍保留的数据进行比较。内存中仍保留的数据进行比较。若两者相等，则此次写入成功；否则，若两者相等，则此次写入成功；否则，重写。重写。若重写后两者仍不一致，则表示该盘块若重写后两者仍不一致，则表示该盘块有缺陷。有缺陷。第二级容错技术第二级容错技术 sft- sft-只能用于防止由磁盘表面部只能用于防止由磁盘表面部分故障造成的数据丢失。但如果磁盘驱分故障造成的数据丢失。但如果磁盘驱动器发生故障，则动器发生故障，则sft-sft-便无能为力。便无能为力。为避免数据丢失，增设了磁盘镜像功能。

23、为避免数据丢失，增设了磁盘镜像功能。磁盘镜像示意图磁盘镜像示意图主机主机磁盘控制器磁盘控制器通道通道磁盘驱动器磁盘驱动器磁盘双工磁盘双工磁盘双工是指两台磁盘驱动器分别接到磁盘双工是指两台磁盘驱动器分别接到两个磁盘控制器上，同样地使这两台磁两个磁盘控制器上，同样地使这两台磁盘机镜像成对。盘机镜像成对。文件服务器同时将数据写到两个处于不文件服务器同时将数据写到两个处于不同控制器下的磁盘上，使两者有着完全同控制器下的磁盘上，使两者有着完全相同的位像图。相同的位像图。读数据时，可采取分离搜索技术。读数据时，可采取分离搜索技术。磁盘双工示意图磁盘双工示意图主机主机通道通道磁盘驱动器磁盘驱动器磁磁 盘盘控

24、制器控制器通道通道磁磁 盘盘控制器控制器廉价磁盘冗余阵列廉价磁盘冗余阵列 廉价磁盘冗余阵列廉价磁盘冗余阵列raidraid是利用一是利用一台磁盘阵列控制器，来统一管理和控制台磁盘阵列控制器，来统一管理和控制一组磁盘驱动器，组成一个高度可靠的、一组磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。现已经被广泛快速的大容量磁盘系统。现已经被广泛地应用于大、中型计算机系统和计算机地应用于大、中型计算机系统和计算机网络中。网络中。并行交叉存取并行交叉存取在该系统中，系统将每一盘块中的数据在该系统中，系统将每一盘块中的数据分为若干个盘块数据，再把每一子盘块分为若干个盘块数据，再把每一子盘块的数据分别

25、存储到各个不同磁盘中的相的数据分别存储到各个不同磁盘中的相同位置。同位置。读取数据时，采用并行传输方式，将各读取数据时，采用并行传输方式，将各盘块的子盘块数据同时向内存传输，从盘块的子盘块数据同时向内存传输，从而使传输时间大大减少。而使传输时间大大减少。磁盘并行交叉存取方式磁盘并行交叉存取方式123nraidraid的优点的优点可靠性高可靠性高磁盘磁盘i/oi/o速度高速度高性能性能/ /价格比高价格比高后备系统后备系统 虽然磁盘系统的容量很大，但系统虽然磁盘系统的容量很大，但系统运行一段时间后，可能将磁盘装满。因运行一段时间后，可能将磁盘装满。因此，每隔一定的时间，就将磁盘上的大此，每隔一定的时间，就将磁盘上的大部分数据，转储到后备系统中；而后备部分数据，转储到后备系统中；而后备系统中的数据，需每隔一段时间重新进系统中的数据，需每隔一段时间重新进行拷贝，以防止由于自然因素使后备系行拷贝，以防止由于自然因素使后备系统中的数据逐渐消失。统中的数据逐渐消失。后备系统的类型后备系统的