1、第7章 磁盘盘存储储管理本章要点 磁盘调度问题 磁盘分配方法 空闲存储空间的管理磁盘存储器不仅容量大，存取速度快，而且可以实现随机存取，是当前存放大量程序和数据的理想设备，所以在现代计算机系统中，都配置了磁盘存储器，并以它为主来存放信息。这样，对信息的操作，都将涉及到对磁盘的访问。磁盘I/O速度的高低和磁盘系统的可靠性，都将直接影响到系统性能。因此，设法改善磁盘系统的性能，已成现代操作系统的重要任务之一。磁盘管理的主要任务是：为文件分配必要的存储空间、合理组织文件的存储方式、提高磁盘存储空间的利用率、提高I/O速度、保证文件存储的可靠性。通过前面各章节及本章的学习，系统地了解和掌握操作系统对各
2、种资源的管理。7.1磁盘存储器概述7.1.1磁盘盘性能简简述1.数据的组织和格式磁盘设备可包括一个或多个盘片，每片分两面，每面可分成若干条磁道(其典型值为3003000)，各磁道之间留有必要的间隙。为使处理简单起见，在每条磁道上可存储相同数目的二进制位。这样，关于磁盘密度(每英寸中所存储的位数)，显然是内层磁道的密度较外层磁道的密度高（现代磁盘为了突破容量的限制，采用内外层磁道可存储不同数目的二进制位）。每条磁道又分成若干个扇区（其典型值为10100），各扇区之间保留一定的间隙。每个扇区的大小相当于一个盘块，如图7-1所示。为了在磁盘上存储数据，必须先将磁盘格式化。图7-2示出了一种温盘(温切
3、斯特硬盘)中一条磁道格式化的情况.其中每条磁道含有30个固定大小的扇区，每个扇区容量为600个字节,其中512个字节存放数据，其余的用于存放控制信息。每个扇区包括两个字段：(1)标识符字段。其中一个字节的Synch具有特定的位图像，作为该字段的定界符，利用Track#（磁道号）、Head#（磁头号）及Sector#（扇区号）三者来标识一个扇区；CRC字段用于段校验；Gap1、Gap2、Gap3分别为各扇区之间和扇区内各字段之间的定界符。(2)数据字段。存放512个字节的数据。2.磁盘的类型对磁盘，可以从不同的角度进行分类。最常见的有：将磁盘分成硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头(移
4、动头)磁盘等。下面仅对固定头磁盘和移动头磁盘做些介绍。(1)固定头磁盘。这种磁盘在每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道，并进行并行读/写，有效地提高了磁盘的I/O速度。这种结构的磁盘主要用于大容量磁盘上。第7章磁盘存储管理操作系统(2)移动头磁盘。每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其结构简单，故仍广泛应用于中小型磁盘设备中。在微型机上配置的温盘和软盘，都采用移动磁头结构，故本节主要针对这类磁盘的I/O进行讨论。3.磁
5、盘访问时间磁盘设备在工作时，以恒定速率旋转。为了读或写，磁头必须能移动到所要求的磁道上，并等待所要求的扇区的开始位置旋转到磁头下，然后再开始读或写数据。故可把对磁盘的访问时间分成以下三部分。(1)寻道时间Ts。这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即Ts=mn+s其中，m是一常数，与磁盘驱动器的速度有关，对一般磁盘，m=0.2；对高速磁盘，m0.1，磁臂的启动时间约为2 ms。这样，对一般的温盘，其寻道时间将随寻道距离的增加而增大，大体上是530 ms。(2)旋转延迟时间T。这是指定扇区移动到磁头下面所经历的时间。对于硬盘
6、，典型的旋转速度大多为5400 r/min，每转需时11.1 ms，平均旋转延迟时间T为5.55 ms；对于软盘，其旋转速度为300 r/min或600 r/min，这样，平均T为50100 ms。(3)传输时间T。这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每次所读/写的字节数b和旋转速度有关：rNbTt其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与T相同，因此，可将访问时间T表示为：rNbrTTs21由上式可以看出，在访问时间中，寻道时间和旋转延迟时间基本上都与所读/写数据的多少无关，而且它通常占据了访问时间中
7、的大头。例如，假定寻道时间和旋转延迟时间平均为20 ms，而磁道的传输速率为10 MB/s，如果要传输10 KB，此时总的访问时间为21 ms，可见传输时间所占比例是非常小的。当传输100 KB数据时，其访问时间也只是30 ms，即当传输的数据量增大10倍时，访问时间只增加约50。目前磁盘的传输速率已达80 MB/s以上，数据传输时间所占的比例更低。可见，适当地集中数据(不要太零散)传输，将有利于提高传输效率。7.1.2磁盘调度磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁
8、盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有：先来先服务、最短寻道时间优先及扫描等算法。下面逐一介绍。1.先来先服务FCFS(First Come，First Served)这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。图7-3示出了有10个进程先后提出磁盘I/O请求时，按FCFS算法进行调度的情况。这里，将进程号(请求者)按他们发出请求的先后次序排队。这样，平均寻道距离为50.3条磁道
9、，与后面即将讲到的几种调度算法相比，其平均寻道距离较大，故FCFS算法仅适用于请求磁盘I/O的进程数目较少的场合。2.最短寻道时间优先SSTF(Shortest Seek Time First)该算法选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短。图7-4示出按SSTF算法进行调度时，各进程被调度的次序、每次磁头移动的距离，以及10次磁头平均移动距离。比较图7-3和图7-4可以看出，SSTF算法的平均每次磁头移动距离，明显低于FCFS的距离，因而SSTF较之FCFS有更好的寻道性能，故过去曾一度被广泛采用。3.扫描(S
10、CAN)算法(1)进程“饥饿”现象。SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(starvation)现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须优先满足，这样老进程的访问请求就会一直得不到满足而导致“饥饿”。对SSTF算法略加修改后所形成的SCAN算法，即可防止老进程出现“饥饿”现象。(2)SCAN算法。该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是既在当前磁道之外，又是距离最近的磁道。这样
11、自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。图7-5示出了按SCAN算法对10个进程进行调度及磁头移动的情况。4循环扫描(CSCAN)算法SCAN算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大、中、小型机器和网络中的磁盘调度，但也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道
12、，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。为了减少这种延迟，CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。采用循环扫描方式后，上述请求进程的请求延迟将从原来的减为，其中为由里向外或由外向里单向扫描完要访问的磁道所需的寻道时间，而是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道的寻道时间(或相反)。图7-6示出了CSCAN算法对10个进程调度的次序及每次磁头移动的距离。5.
13、N-Step-SCAN和FSCAN调度算法(1)N-Step-SCAN算法。在SSTF、SCAN及CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。这一现象被称为“磁臂粘着”(Arm-Stickiness)。在高密度磁盘上容易出现此情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘I/O请求
14、，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能；当N=1时，N步SCAN算法便退化为FCFS算法。(2)FSCAN算法。FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。7.1.3磁盘高速缓存(Disk Cache)目前，磁盘的I/O速度远低于对内存的访问速度，通常要低上46个数
15、量级。因此，磁盘的I/O已成为计算机系统的瓶颈。于是，人们便千方百计地去提高磁盘I/O的速度，其中最主要的技术，便是采用磁盘高速缓存。1.磁盘高速缓存的形式这里所说的磁盘高速缓存，并非通常意义下的内存和CPU之间所增设的一个小容量高速存储器，而是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。高速缓存在内存中可分成两种形式。第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘
16、高速缓存)共享。此时高速缓存的大小，显然不再是固定的。当磁盘I/O的频繁程度较高时，该缓冲池可能包含更多的内存空间；而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间。2.数据交付方式数据交付(Data-Delivery)是指将磁盘高速缓存中的数据传送给请求者进程。当有一进程请求访问某个盘块中的数据时，由操作系统内核去查看磁盘高速缓冲器，看其中是否存在进程所需访问的盘块数据的拷贝。若有其拷贝，便直接从高速缓存中提取数据交付给请求者进程，这样，就避免了访盘操作，从而使本次访问速度提高46个数量级；否则，应先从磁盘中将所要访问的数据读入并交付给请求者进程，同时也将数据送高速缓存。当以后又需
17、要访问该盘块的数据时，便可直接从高速缓存中提取。系统可以采取两种方式，将数据交付给请求进程：(1)数据交付。这是直接将高速缓存中的数据，传送到请求者进程的内存工作区中；(2)指针交付。只将指向高速缓存中某区域的指针，交付给请求者进程。后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存到内存工作区的时间。3.置换算法同请求调页(段)一样，在将磁盘中的盘块数据读入高速缓存时，同样会出现因高速缓存中已装满盘块数据而需要将高速缓存中的数据先换出的问题。相应地，也必然存在着采用哪种置换算法的问题。较常用的置换算法仍然是最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU等。由于请
18、求调页中的联想存储器与高速缓存(磁盘I/O中)的工作情况不同，因而使得在置换算法中所应考虑的问题也有所差异。因此，现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：(1)访问频率。通常，每执行一条指令时，便可能访问一次联想存储器，亦即联想存储器的访问频率基本上与指令执行的频率相当。而对高速缓存的访问频率，则与磁盘I/O的频率相当。因此，对联想存储器的访问频率远远高于对高速缓存的访问频率。(2)可预见性。在高速缓存中的各盘块数据，有哪些数据可能在较长时间内不会再被访问，又有哪些数据可能很快就再被访问，会有相当一部分是可预知的。例如，对二次地址及目录块
19、等，在它被访问后，可能会很久都不再被访问。又如，正在写入数据的未满盘块，可能会很快又被访问。(3)数据的一致性。由于高速缓存是做在内存中的，而内存一般又是一种易失性的存储器，一旦系统发生故障，存放在高速缓存中的数据将会丢失；而其中有些盘块(如索引结点盘块)中的数据已被修改，但尚未拷回磁盘。因此，当系统发生故障后，可能会造成数据的不一致性。基于上述考虑，在有的系统中便将高速缓存中的所有盘块数据，拉成一条LRU链。对于那些会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们能被优先写回磁盘，以减少发生数据不一致性的概率，或者可以尽快地腾出高速缓存的空间。对于
20、那些可能在不久之后便要再使用的盘块数据，应挂在LRU链的尾部，以便在不久以后需要时，只要该数据块尚未从链中移至链首而被写回磁盘，便于直接到高速缓存中(即LRU链中)去找到它们。4.周期性地写回磁盘还有一种情况值得注意：那就是根据LRU算法，那些经常要被访问的盘块数据，可能被一直保留在高速缓存中，长期不会被写回磁盘。注意，LRU链意味着链中任一元素在被访问之后，总是又被挂到链尾而不被写回磁盘；只是一直未被访问的元素，才有可能移到链首而被写回磁盘)。例如，一位学者一上班便开始撰写论文，并边写边修改，他正在写作的论文就一直保存在高速缓存的LRU链中。如果在快下班时，系统突然发生故障，存放在高速缓存中
21、的已写论文将随之消失，致使他枉费了一天的劳动。为了解决这一问题，在UNIX系统中专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30 s。这样，因系统故障所造成的工作损失不会超过30 s的劳动量。而在MS-DOS中所采用的方法是：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-through cache)。MS-DOS所采用的写回方式，几乎不会造成数据的丢失，但需频繁地启动磁盘。7
22、.1.4提高磁盘I/O速度的其他方法在系统中设置了磁盘高速缓存后，能显著地减少等待磁盘I/O的时间。本小节再介绍几种能有效地提高磁盘I/O速度的方法，这些方法已被许多系统采用。1.提前读(Read-Ahead)用户(进程)对文件进行访问时，经常采用顺序访问方式，即顺序地访问文件的各盘块的数据。在这种情况下，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式，即在读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入缓冲区。这样，当下一次要读该盘块中的数据时，由于该数据已被提前读入缓冲区，因而此时便可直接从缓冲区中取得下一盘块的数据，而不需再去启动磁盘I/O，从而大大减少了读
23、数据的时间。这也就等效于提高了磁盘I/O的速度。“提前读”功能已被广泛采用，如在UNIX系统、OS/2，以及在3 Plus和Netware等的网络OS中，都已采用。2.延迟写延迟写是指在缓冲区A中的数据，本应立即写回磁盘，但考虑到该缓冲区中的数据在不久之后可能还会再被本进程或其他进程访问(共享资源)，因而并不立即将该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾。随着空闲缓冲区的使用，缓冲区也缓缓往前移动，直至移到空闲缓冲区队列之首。当再有进程申请到该缓冲区时，才将该缓冲区中的数据写入磁盘，而把该缓冲区作为空闲缓冲区分配出去。当该缓冲区A仍在队列中时，任何访问该数据的进程，都可直接
24、读出其中的数据而不必去访问磁盘。这样，又可进一步减小等效的磁盘I/O时间。同样，“延迟写”功能已在UNIX系统、OS/2等OS中被广泛采用。3.优化文件物理块的分布 另一种提高磁盘I/O速度的重要措施，是优化文件物理块的分布，使磁头的移动距离最小。虽然链接分配和索引分配方式，都允许将一个文件的物理块分散在磁盘的任意位置，但如果将一个文件的多个物理块安排得过于分散，会增加磁头的移动距离。例如，将文件的第一个盘块安排在最里的一条磁道上，而把第二个盘块安排在最外的一条磁道上，这样，在读完第一个盘块后转去读第二个盘块时，磁头要从最里的磁道移到最外的磁道上。如果将这两个数据块安排在属于同一条磁道的两个盘
25、块上，显然会由于消除了磁头在磁道间的移动，而大大提高对这两个盘块的访问速度。对文件盘块位置的优化，应在为文件分配盘块时进行。如果系统中的空白存储空间层采用位示图方式表示时，要将同属于一个文件的盘块安排在同一条磁道上或相邻的磁道上是十分容易的事。这时，只要从位示图中找到一片相邻接的多个空闲盘块即可。但当系统采用线性表(链)法来组织空闲存储空间时，要为一文件分配多个相邻接的盘块，就要困难一些。此时，可以将在同一条磁道上的若干个盘块组成一簇，例如，一簇包括4个盘块，在分配存储空间时，以簇为单位进行分配。这样就可以保证在访问这几个盘块时，不必移动磁头或者仅移动一条磁道的距离，从而减少了磁头的平均移动距
26、离。4.虚拟盘所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序，也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。换言之，用户们并不会发现这与真正的磁盘操作有什么不同，而仅仅是略微快些而已。虚拟盘的主要问题是：它是易失性存储器，故一旦系统或电源发生故障，或系统再启动时，原来保存在虚拟盘中的数据将会丢失。因此，虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。虚拟盘与磁盘高速缓存的主要区别在于：虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。例如，RAM盘在开始时是空的，仅当用户(程序)在RAM
27、盘中创建了文件后，RAM盘中才有内容。4.虚拟盘所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序，也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。换言之，用户们并不会发现这与真正的磁盘操作有什么不同，而仅仅是略微快些而已。虚拟盘的主要问题是：它是易失性存储器，故一旦系统或电源发生故障，或系统再启动时，原来保存在虚拟盘中的数据将会丢失。因此，虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。虚拟盘与磁盘高速缓存的主要区别在于：虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。例如，RAM盘在开始
28、时是空的，仅当用户(程序)在RAM盘中创建了文件后，RAM盘中才有内容。7.2磁盘分配方法由于磁盘具有可直接访问的特性，故当利用磁盘来存放文件时，具有很大的灵活性。在为文件分配外存空间时所要考虑的主要问题是怎样才能有效地利用外存空间和如何提高对文件的访问速度。目前常用的外存分配方法有连续分配、链接分配和索引分配三种。通常在一个系统中，仅采用其中的一种方法来为文件分配外存空间。如前所述，文件的物理结构直接与外存分配方式有关。在采用不同的分配方式时，将形成不同的文件物理结构。例如，在采用连续分配方式时的文件物理结构，将是顺序式的文件结构；链接分配方式将形成链接式文件结构；而索引分配方式则将形成索引
29、式文件结构。7.2.1连续分配1.连续分配方式 连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2，。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中
30、文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图7-7示出了连续分配的情况，图中假定记录与盘块的大小相同。file1的第一个盘块号是0，文件长度为2，因此是在盘块号为0和1的两盘块中存放file1的数据。如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(
31、Repack Routine)，由它将磁盘A上的大量文件复制到一张软盘B或几张软盘(C，D，)上，并释放原来的A盘，使之成为一个空闲盘。然后再将软盘B(C，D，)上的文件复制回A盘上。这种方法能将含有多个文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。2.连续分配的主要优缺点 连续分配的主要优点如下：(1)顺序访问容易。访问一个占有连续空间的文件，非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的
32、文件中的第i个盘块的内容，就可直接访问第b+i号盘块。(2)顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。连续分配的主要缺点如下：(1)要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。(2)必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将
33、文件装入。在有些情况下，知道文件的大小是件非常容易的事，如可复制一个已存文件。但有时却很难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的复制，需再要求用户重新估算，然后再次执行，这样显然既费时又麻烦。这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得多，显然，这会严重地浪费外存空间。对于那些动态增长的文件，由于开始时文件很小，在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存储空间长期地空闲。7.2.2链接分配同内存管
34、理一样，连续分配所存在的问题就在于：必须为一个文件分配连续的磁盘空间。如果在将一个逻辑文件存储到外存上时，并不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块中，这样也就可以消除上述的缺点。在采用链接分配(Chained Allocation)方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。由于链接分配是采取离散分配方式，消除了外部碎片，故而显著地提高了外存空间的利用率；又因为是根据文件的当前需要，为它分配必需的盘块，当文件动态增长时，可动态地再为它分配盘块，故而无须事先知道文件的大小。此外，对文件的增、
35、删、改也十分方便。链接方式又可分为隐式链接和显式链接两种形式。1.隐式链接在采用隐式链接分配方式时，在文件目录的每个目录项中，都需含有指向链接文件第一个盘块和最后一个盘块的指针。图7-8中示出了一个占用5个盘块的链接式文件。在相应的目录项中，指示了其第一个盘块号是9，最后一个盘块号是25。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块9中设置了第二个盘块的盘块号是16；在16号盘块中又设置了第三个盘块的盘块号1。如果指针占用4个字节，对于盘块大小为512字节的磁盘，则每个盘块中只有508个字节可供用户使用。隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效
36、的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块，就这样顺序地查找直至第i块。当i=100时，需启动100次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度多么低!此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。比如，一个簇可包含4个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位。这样将会成倍地减小查找指定块的时间，而且也可减小指针所占用的存储空间，但却增大了内部
37、碎片（由于被装入的文件小于簇从而使得簇内部有空间浪费），而且这种改进也是非常有限的。2.显式链接 这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，如图7-9所示。表的序号是物理盘块号，从0开始，直至N-1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文
38、件分配表FAT(File Allocation Table)。MS-DOS、Windows及OS/2等操作系统都采用了FAT。图7-10示出了MS-DOS的文件物理结构。这里示出了两个文件：文件A占用三个盘块，其盘块号依次为4、6、11；文件B则依次占用9、10及5号三个盘块；每个文件的第一个盘块号放在自己的FCB中。整个系统有一张文件分配表FAT。在FAT的每个表项中存放下一个盘块号。对于容量为1.2 MB的软盘，盘块大小为1 KB，每个FAT表项占12位，在每个FAT中共含有1.2 K个表项，故共需1.8 KB。而对于200 MB的硬盘，共含有200 K个盘块，因此，FAT的每个表项需2.
39、5个字节，故共需占用500 KB。但如果磁盘容量为12 GB、盘块的大小为4 KB时，应共有3 M个盘块；而FAT的每个表项需三个字节，总共需占用9 MB的内存。7.2.3索引分配1.单级索引分配链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题。(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，需首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的盘块号。当磁盘容量较大时，FAT可能要占用数兆字节以上的内存空间，这是令人难以接
40、受的。事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，便需要在为之建立的目录项中，填上指向该索引块的指针。图7-11示出了磁盘空间的索引分配图。图7-11索引分配方式索引分配方式支持直接访问。当要读文件的第i个盘块时，可以方便地直接从索引块中找到第i个盘块的盘块号；此外，索引分配方式也不会产生外部碎片。当
41、文件较大时，索引分配方式无疑要优于链接分配方式。索引分配方式的主要问题是：可能要花费较多的外存空间。每当建立一个文件时，便需为之分配一个索引块，将分配给该文件的所有盘块号记录于其中。但在一般情况下，总是中、小型文件居多，甚至有不少文件只需12个盘块，这时如果采用链接分配方式，只需设置12个指针。如果采用索引分配方式，则同样仍需为之分配一索引块。通常是采用一个专门的盘块作为索引块，其中可存放成百个、甚至上千个盘块号。可见，对于小文件采用索引分配方式时，其索引块的利用率将是极低的。2.多级索引分配当OS为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS便为该文件分配
42、另一个索引块，用于将以后继续为之分配的盘块号记录于其中。以此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块等索引块的盘块号，填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。图7-12示出了两级索引分配方式下各索引块之间的链接情况。如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放266个盘块号。这样，在两级索引时，最多可包含的存放文件的盘块的盘块号总数N=256
43、265=64 K个盘块号。由此可得出结论：采用两级索引时，所允许的文件最大长度为64 MB。倘若盘块的大小为4 KB，在采用单级索引时所允许的最大文件长度为4 MB；而在采用两级索引时所允许的最大文件长度可达4 GB。3.混合索引分配方式所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIX System V的索引结点中，共设有13个地址项，即iaddr(0)iaddr(12)，如图7-13所示。在BSD UNIX的索引结
44、点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。(1)直接地址。为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据的盘块的盘块号。假如每个盘块的大小为4 KB，当文件不大于40 KB时，便可直接从索引结点中读出该文件的全部盘块号。(2)一次间接地址。对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入
45、其中。在一次间址块中可存放1K个盘块号，因而允许文件长达4 MB。(3)多次间接地址。当文件长度大于4 MB+40 KB时(一次间址与10个直接地址项)，系统还需采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4 GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4 TB。7.3空闲存储空间的管理文件管理要解决的重要问题之一是如何为新创建的文件分配存储空间。其解决方法与内存的分配情况有许多相似之处，即同样可采取连续分配方式
46、或离散分配方式。前者具有较高的文件访问速度，但可能产生较多的外存零头；后者能有效地利用外存空间，但访问速度较慢。不论哪种分配方式，存储空间的基本分配单位都是磁盘块而非字节。为了实现存储空间的分配，系统首先必须能记住存储空间的使用情况。为此，系统应为分配存储空间而设置相应的数据结构；其次，系统应提供对存储空间进行分配和回收的手段。下面介绍几种常用的文件存储空间的管理方法。7.3.1空闲空间表法(1)空闲表法属于连续分配方式，它与内存的动态分配方式类似，它为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号
47、、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，如图7-14所示。(2)空间的分配与回收。空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。应该说明，在内存分配上，虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问
48、磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地。例如，在前面所介绍的对换方式中，对对换空间，一般都采用连续分配方式。对于文件系统，当文件较小(14个盘块)时，仍采用连续分配方式，为文件分配相邻接的几个盘块；当文件较大时，便采用离散分配方式。7.3.2空闲块链接法空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。(1)空闲盘块链。这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依
49、次插入空闲盘块链的末尾。这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次。(2)空闲盘区链。这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。7.3.3空闲块成组链接法空闲表法和空闲链表法，都不适用于大型文件系统，
50、因为这会使空闲表或空闲链表太长。在UNIX系统中采用的是成组链接法，这是将上述两种方法相结合而形成的一种空闲盘块管理方法，它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。1.空闲盘块的组织(1)空闲盘块号栈。用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块号数N。顺便指出，N还兼作栈顶指针用。例如，当N=100时，它指向S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。图7-15左部示出了空闲盘块号栈的结构。其中，S.free(0)是栈底，栈满时的栈顶为S.free(99)。(2)文件区中的所有空闲盘块，被
