第8章 磁盘存储器的管理.ppt

2020/5/16,Page1,第8章磁盘存储器的管理,8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制习题,2020/5/16,Page2,8.1外存的组织方式/外存分配方式/文件的物理结构,对于任何一个文件，都存在着以下两种形式的结构：(1)文件的逻辑结构(FileLogicalStructure)。(2)文件的物理结构，又称为文件的存储结构，是指逻辑文件在在存储设备（外存）上的存储组织形式，它与存储介质的存储特性有关。(3)文件在逻辑上都可看作是连续的，但在物理设备上存放时却有不同的方式，如连续结构（顺序结构）、链接结构（串联结构）、索引结构等.,2020/5/16,Page3,外存分配方式,连续分配链接分配索引分配,2020/5/16,Page4,1.连续分配连续分配方式下的文件也称顺序结构。它将逻辑上连续的文件信息(如记录)依次连续存放在连续编号的物理块上。只要知道文件的起始物理块号和文件的长度，就可以很方便地进行文件的存取。例如，文件W.TXT占用了50、51、52、53号物理块，系统只需将文件的起始块号50和文件的长度放在文件目录中该文件所对应的文件说明中即可，如图8.1所示。,2020/5/16,Page5,图8.1连续结构,优点：顺序访问容易，连续分配支持直接存取顺序访问速度快。,缺点：连续分配会产生外存碎片，可利用紧凑方法，将碎片拼接成一大片（如同内存的动态分区分配）要求有连续的存储空间必须事先知道文件的长度,2020/5/16,Page6,外存分配方式,连续分配链接分配索引分配,2020/5/16,Page7,2.链接分配链接结构也称串联结构，它将逻辑上连续的文件信息(如记录)存放在不连续的物理块上，每个物理块设有一个指针指向下一个物理块。因此，只要知道文件的第一个物理块号，就可以按链指针查找整个文件。例8.1文件W.TXT占用了60、86、92、103号物理块，文件的起始块号60放在文件说明中，如图8.2所示。,2020/5/16,Page8,图8.2链接结构,优点：可离散分配，解决了碎片问题缺点：只适合于顺序访问，对随机访问极其低效，不支持直接访问，不可靠。,（隐式链接）,2020/5/16,Page9,链接分配,隐式链接,文件名始址末址,jeep925,文件目录,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,1,10,16,-1,25,磁盘空间的链接分配方式,2020/5/16,Page10,为了克服链接文件的随机访问效率太低的问题，提出文件映照的技术，即把链接文件中的链接字集中在一结构中，这样既保持了链接文件的优点，也克服了其缺点，DOS、WINDOWS系统就采用了这样结构。,显式链接,2020/5/16,Page11,链接分配,显式链接,2020/5/16,Page12,链接分配,2020/5/16,Page13,文件分配表（FileAllocationTable,FAT）,磁盘格式化后建立。用于记录外存分配状况，每个盘块（或簇）占一项，放在内存中，整个系统一张FAT.表的序号为物理盘块号或簇号，从0至N-1.分配给一个文件的所有物理块都在该表中标出，文件的第一个盘块号记入文件的FCB中。,2020/5/16,Page14,文件分配表（FileAllocationTable,FAT）,实例对于1.2M磁盘，每个物理块大小为1KB，则共有1.2K个FAT表项，若每个表项占12位（1.5B），则共需1.8KB的空间来保存FAT。显式链接分配优点：便于快速查找缺点：FAT很大，需较大的内存空间,2020/5/16,Page15,外存分配方式,连续分配链接分配索引分配,2020/5/16,Page16,3.索引分配采用索引分配方式可将逻辑上连续的文件信息(如记录)存放在不连续的物理块中。系统为每个文件建立一张索引表，索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在文件对应的文件目录项中。例8.2文件W.TXT占用了60、86、92、103号物理块，文件索引表存放在98号物理块中，W.TXT文件的文件目录项指向文件索引表，如图8.3所示。,2020/5/16,Page17,图8.3索引结构,访问W.TXT文件的过程是：系统按文件名“W.TXT”查找文件目录表，根据索引表的起始地址将索引表块读入内存，按索引表查找对应的物理块号并将物理块读入内存。,2020/5/16,Page18,思考：按照当前的存储条件，文件最大可以达到多少？,结论：无法满足实际应用的需求，需要升级。,分析：物理块的大小为512字节；每个索引表项占4个字节(可表示物理块号的范围从0232-1)，则一个物理块可存放128个索引表项。,64K,2020/5/16,Page19,建立二级（多级）索引分配，该分配方式的结构如图8.5所示。,图8.5二级索引结构,2020/5/16,Page20,二级（多级）索引分配方式支持的文件大小,若每个盘块大小为512B，每个盘块号占4B，则一级索引块中可存放128个盘块号，即对应128个二级索引块。每个二级索引块可对应128个物理磁盘块，采用这种索引方式时每个文件大小不能超过128*128*0.5KB=8MB若每个盘块大小为4K，则最大文件大小为1K*1K*4K=4GB,2020/5/16,Page21,UNIX文件系统采用的是混合索引分配，文件系统中的I节点是基本的构件，它表示文件系统的树型结构的节点。每一个I节点是一个普通文件或目录文件。I节点结构定义如下：,举例：UNIX文件系统的索引结构,什么是混合索引分配?,2020/5/16,Page22,混合索引分配,直接地址（直接索引）为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)iaddr(9)来存放直接地址一次间接地址（二级索引）对于大、中型文件，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式多次间接地址（多级索引）当文件长度大于4MB+40KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式,2020/5/16,Page23,structdinodeushortdi_mode;/*文件控制模式*/shortdi_nlink;/*文件的链接数*/ushortdi_uid;/*文件主用户标识*/ushortdi_gid;/*文件主同组用户标识*/off_tdi_size;/*文件长度，以字节为单位*/chardi_addr40;/*文件索引表，存放文件的物理盘块号*/time_tdi_atime;/*文件最近一次访问时间*/time_tdi_mtime;/*文件最近一次修改时间*/time_tdi_ctime;/*文件创建时间*/,2020/5/16,Page24,UNIX将前13个表项分成如下的4种寻址方式：直接寻址：di_addr数组前10个表项直接指向文件前10个逻辑块的物理盘块地址，称为直接块指针。一级间接寻址：di_addr数组的第11个表项指向文件索引块的地址，即第11个表项登记的不是文件的物理盘块号，而是一个索引块的地址。,2020/5/16,Page25,二级间接寻址：对于长度超过前两种方式所能寻址的文件，超过部分采用二级间接寻址方式。di_addr数组的第12个表项指向第一个具有341个表项的间接索引块的地址，间接索引块的每一个表项又都登记了具有341个表项的索引块的地址，在这级索引块中登记的才是文件的物理块地址，如图8.6所示。,三级间接寻址：对于长度超过前三种方式所能寻址的文件，超过部分采用三级间接寻址方式。di_addr数组的第13个表项指向第一个具有341个表项的二级间接索引块的地址，文件的寻址原理同二级间接寻址。,2020/5/16,Page26,图8.6UNIX文件的索引结构,2020/5/16,Page27,2020/5/16,Page28,索引结构优缺点优点：保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间。缺点：较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间。,2020/5/16,Page29,8.1外存的组织方式小结,连续分配：顺序式的文件结构链接分配：隐式链接和显式链接显式链接：文件分配表FAT索引分配：单级索引、多级索引、混合索引方式,2020/5/16,Page30,文件物理结构的比较,连续文件的优点是不需要额外的空间开销，只要在文件目录中指出文件的大小和首块的块号即可，对顺序的访问效率很高。适应于顺序存取。缺点是动态地增长和缩小系统开销很大；文件创建时要求用户提供文件的大小；存储空间浪费较大。链式文件克服了连续文件的不足之处，但文件的随机访问系统开销较大。适应于顺序访问。DOS系统中改造了链式文件的结构，使其克服了链式文件的不足，但增加了系统的危险性。,2020/5/16,Page31,文件物理结构的比较,索引文件既适应于顺序存访问，也适应于随机访问，是一种比较好的文件物理结构，但要有用于索引表的空间开销和文件索引的时间开销。UNIX系统是使用索引结构成功的例子。在当前流行的一些UNIX操作系统的版本中，同时支持连续文件结构和索引文件结构。DOS、WINDOWS系统支撑类似于文件映照结构,2020/5/16,Page32,(2011),2020/5/16,Page33,如何才能有效地利用外存空间?如何提高对文件的访问速度?如何为新创建的文件分配存储空间？,思考,2020/5/16,Page34,空闲区表法位示图法空闲链表法成组链接法,8.2文件存储空间管理,2020/5/16,Page35,1空闲区表将外存空间上一个连续未分配区域称为“空闲区”。操作系统为磁盘外存上所有空闲区建立一张空闲表，每个表项对应一个空闲区，空闲表中包含序号、空闲区的第一块号、空闲块的块数等信息，如表8.2所示。空闲区表适用于连续文件结构。,8.2文件存储空间管理,2020/5/16,Page36,表8.2空闲区表,2020/5/16,Page37,2.位示图这种方法是在外存上建立一张位示图(bitmap)，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。文件存储器上的物理块依次编号为0，1，2，。假如系统中字长为32位，那么在位示图中的第一个字对应文件存储器上的第0，1，2，31号物理块；第二个字对应文件存储器上的32，33，34，63号物理块；依此类推，如图8.19所示。,2020/5/16,Page38,图8.7位示图例,1,2,3,4,5,15,16,2020/5/16,Page39,1)分配物理块当用户申请磁盘空间时，系统可按如下步骤进行物理块的分配：(1)顺序扫描位示图，查找为0的位。(2)将找到的对应的二进制位转换为物理块号，假定i是位示图的字号，j是位示图中的位号，n代表字长，转换公式如下：块号n(i-1)+j(3)修改位示图，将对应的位置为1。,2020/5/16,Page40,2)释放物理块当用户释放物理块时，系统将对应位置0，其步骤如下：(1)将回收的物理块号转换为对应的位示图的字号i及位示图中的位号j，转换公式如下：i(块号-1)/n+1j(块号-1)MODn+1,(2)修改位示图，将对应的位置为0。这种方法的主要特点是位示图的大小由磁盘空间的大小(物理块总数)决定；位示图的描述能力强，适合各种物理结构。,2020/5/16,Page41,3.空闲块链空闲块链法是指每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上(如管理块中)。该方法不需要磁盘分配表，节省空间。,2020/5/16,Page42,例8.5磁盘分区上有5个空闲物理块，分别为58#、78#、98#、100#和102#，画出采用空闲块链的结构图。文件存储器中的链表头指针中存放的是58，58#物理块存放78，78#物理块存放98，98#物理块存放100，100#物理块存放102，102#物理块存放结束标志null，这就将所有空闲物理块链在了一起，如图8.8所示。,2020/5/16,Page43,图8.8空闲物理块链举例,2020/5/16,Page44,4.成组链接法在UNIX系统中，将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。假如一个组的第一个空闲块号等于0的话，则有特殊的含义，意味着该组是最后一组，即无下一组空闲块。图8.9是UNIX系统的空闲块成组链接示意图。成组链法法分配和释放空闲块的算法如下：1)分配算法流程图(见图8.10)2)释放算法流程图(见图8.11),2020/5/16,Page45,图8.9UNIX系统的成组链接法实例,2020/5/16,Page46,图8.10UNIX系统空闲盘块分配算法流程图,2020/5/16,Page47,图8.11UNIX系统空闲盘块释放算法流程图,2020/5/16,Page48,8.3提高磁盘I/O速度的途径,磁盘存储器不仅容量大，存取速度快，而且可以实现随机存取，是实现虚拟存储器所必需的硬件，因此在现代计算机系统中，都配置了磁盘存储器，并以它为主要的文件存储器。磁盘存储器管理的主要任务是：,2020/5/16,Page49,(1)为文件分配必要的存储空间，使每个文件能“各得其所”。(2)合理地组织文件的存取方式，以提高对文件的访问速度。(3)提高磁盘存储空间的利用率。(4)提高对磁盘的I/O速度，以改善文件系统的性能。(5)采取必要的冗余措施，来确保文件系统的可靠性。,2020/5/16,Page50,目前，几乎所有可随机存取的文件，都存放在磁盘上，磁盘I/O速度的高低，将直接影响文件系统的性能。因此，如何改善磁盘I/O的性能，已成为提高文件系统性能的关键。提高磁盘I/O速度的主要途径有：(1)选择性能好的磁盘。(2)采用好的磁盘调度算法。(3)设置磁盘高速缓冲区。,2020/5/16,Page51,8.3.1块高速缓存1块高速缓存块高速缓存的基本思想是利用内存中的存储空间来暂存从磁盘中读出的一系列盘块信息。因此，块高速缓存是一组逻辑上属于磁盘，而物理上是驻留在内存中的盘块。块高速缓存分为两种形式：(1)在内存中开辟一个单独的存储空间来作为块高速缓存，大小固定，不会受应用程序多少的影响。(2)将所有未利用的内存空间变为一个缓冲池，供请求分页和磁盘I/O时共享。,2020/5/16,Page52,2.数据交付数据交付是将块高速缓存中的数据传送给请求者进程。当某进程请求访问某个盘块中的数据时，由核心先去检查块高速缓存中有无该进程要访问的盘块数据。若有，便直接从块高速缓存提取数据交付给请求者进程，从而避免了访盘操作；若无，则从磁盘将要访问的数据读入块高速缓存并交付给请求者进程。数据交付分直接交付和指针交付两种形式。,2020/5/16,Page53,直接交付：直接将块高速缓存中的数据传送到请求者进程的内存工作区。指针交付：只将块高速缓存中某区域的指针交付给请求者进程。这种方式由于传送的数据少，因而节省了数据传送的时间。,2020/5/16,Page54,3置换算法(1)访问频率。访问联想存储器的频率远远高于访问块高速缓存的频率。(2)可预见性。在块高速缓存中的数据，哪些是较长时间不被访问，哪些是很快被访问，有相当一部分是可预知的。,2020/5/16,Page55,(3)数据的一致性。由于块高速缓存是在内存中，而内存一般是易失性存储器，一旦系统发生故障，存放在块高速缓存中的数据将会丢失，若其中的某些盘块被修改而未写回磁盘，将导致这些数据的不一致性。,2020/5/16,Page56,8.3.2磁盘调度1.磁盘调度磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，为了保证信息的安全，系统每一时刻只允许一个进程启动磁盘进行I/O操作，其余的进程只能等待。常用的磁盘调度算法有：先来先服务、最短寻道时间优先、扫描算法、循环扫描算法等。,2020/5/16,Page57,2.磁盘移臂调度算法1)先来先服务(First-ComeFirst-Served，FCFS)先来先服务是最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。图8.29显示了有若干个进程先后提出磁盘I/O请求时，按FCFS算法进行调度的情况。,2020/5/16,Page58,图8.12中，将进程(请求者)按其发出请求的先后次序排列。这样，平均寻道距离为55.3条磁道。与后面要讲的几种调度算法相比，其平均寻道距离较大。故FCFS算法仅适用于请求磁盘I/O的进程数目较少的场合。,2020/5/16,Page59,图8.12FCFS调度算法示例,2020/5/16,Page60,2)最短寻道时间优先(ShortestSeekTimeFirst，SSTF)SSTF算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。图8.13示出了按SSTF算法进行调度时各进程被调度的次序以及每次磁头的移动距离。,2020/5/16,Page61,图8.13SSTF调度算法示例,2020/5/16,Page62,3)扫描算法(SCAN)扫描算法不仅要考虑欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。图8.14显示了按SCAN算法对若干个进程进行调度及磁头移动的情况。,2020/5/16,Page63,图8.14SCAN调度算法示例,2020/5/16,Page64,4)循环扫描调度算法(CircleSCAN,CSCAN)SCAN算法既能获得较好的寻道性能，又能防止进程饥饿，故被广泛用于大、中、小型机和网络中的磁盘调度。但SCAN也存在这样的问题：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外、然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被严重地推迟。,2020/5/16,Page65,图8.15CSCAN调度算法示例,2020/5/16,Page66,5)N步SCAN算法在SSTF、SCAN及CSCAN几种调度算法中，都可能出现磁臂停留在某位置不动的情况。例如，有一个或几个进程对某一磁道有着较高的访问频率，即它们反复地请求对某一磁道进行I/O，从而垄断了整个磁盘设备。我们把这一现象称为磁臂“粘着”(armxstickiness)。在高密度盘上更容易出现这种情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度按FCFS算法依次处理这些子队列。,2020/5/16,Page67,6)FSCAN算法(FirstSCAN)FSCAN算法实质上是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一个是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个则是在扫描期间新出现的所有请求磁盘I/O进程的队列，它们将插入另一个等待处理的请求队列中。,2020/5/16,Page68,3.磁盘旋转调度算法当移动臂定位后，有多个进程等待访问该柱面时，应当如何决定这些进程的访问顺序呢？这就是旋转调度要考虑的问题。显然，系统应该选择延迟时间最短的进程执行。当有若干等待进程请求访问磁盘上的信息时，旋转调度应考虑如下情况：,(1)进程请求访问的是同一磁头下的不同编号的扇区。(2)进程请求访问的是不同磁头下的不同编号的扇区。(3)进程请求访问的是不同磁头下具有相同编号的扇区。,2020/5/16,Page69,例8.12有6个访问16号柱面的请求进程，其要求如表8.5所示，请给出它们的执行顺序。,1,2,6,3,5,4或1,4,6,3,5,2,2020/5/16,Page70,8.7.3信息的优化分布1优化物理块分布优化物理块分布是指使磁头移动距离最小。尽管链接分配和索引分配都允许将一个文件的物理块分散在磁盘的任意位置上，但是过于分散必然会增加磁头的移动距离。例如，将文件的第一个盘块存放在第1个磁道上，将文件的第二个盘块存放在第190个磁道上，那么磁头移动的距离为189。2优化索引节点分布优化索引节点分布也会使磁头移动距离减少。因为通常访问一个文件需先访问索引节点，然后再访问盘块。,信息优化分布示例,2020/5/16,Page71,2020/5/16,Page72,2020/5/16,Page73,2020/5/16,Page74,磁盘高速缓存,磁盘高速缓存（DiskCache）的形式数据交付方式磁盘缓存置换算法周期性地写回磁盘RAID,2020/5/16,Page75,磁盘高速缓存的形式,DiskCache：并非通常意义上的高速缓存，而是利用内存中的空闲空间，暂存从磁盘中读出的一系列盘块中的信息。逻辑上属于磁盘，物理上驻留内存的磁盘数据块区。两种形式：固定大小的磁盘高速缓存，不受应用程序多少影响。可变大小的磁盘高速缓存“缓冲池”形式,2020/5/16,Page76,数据交付方式,DataDelivery：将磁盘高速缓存中的数据传送给请求者进程。两种方式：数据交付：将数据传送给请求者进程的内存工作区中；指针交付：只将高速缓存中相应数据区的首址指针交付给请求者进程；,2020/5/16,Page77,磁盘缓存置换算法,也称为“访问频率替换算法”要考虑的问题：访问频率、可预见性、数据的一致性较常用的算法：最近最久未使用LRU最近未使用NRU（Clock）最少使用LFU,2020/5/16,Page78,周期性地写回磁盘,后台专用程序，如：UNIX中的SYNC间隔一定时间，强制性地把所有缓存中的已修改的盘块数据写回磁盘。定期自动保存,2020/5/16,Page79,提高磁盘I/O速度的其它方法,提前读（Read-Ahead）延迟写,2020/5/16,Page80,提高磁盘I/O速度的其它方法,优化物理块的分布虚拟盘,2020/5/16,Page81,廉价磁盘冗余阵列RedundantArrayofInexpensiveDisk,并行交叉存取在该系统中，有多台磁盘驱动器，系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储在各个不同盘块的相同位置上。在以后，当要将一个盘块的数据传送到内存时，采取并行传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。例如，在存放一个文件时，可将该文件中的第一个数据子块放在第一个磁盘驱动器上；将第二个数据子块放在第二个磁盘上，将第N个数据子块，放在第N个驱动器上。以后在读取数据时，采取并行读取的方式，即同时从第1-N个数据子块读出数据，这样便把磁盘I/O的速度提高了N-1倍。,2020/5/16,Page82,廉价磁盘冗余阵列,RAID的分级RAID0级RAID7级RAID的优点可靠性高磁盘I/O速度高性价比高,2020/5/16,Page83,8.4文件系统的可靠性与安全性,8.4.1文件系统的可靠性1坏块问题磁盘在使用的过程中可能会出现坏块，对于坏块问题有软件和硬件两种解决方法。硬件方法可以在磁盘上分配一个区，用来登记坏块和替换块的映射。当磁盘控制器第一次被初始化时，读坏块表找一个空闲块代替有问题的块。,2020/5/16,Page84,2转储和恢复文件系统中无论是硬件还是软件都会发生损坏和错误。例如自然界的闪电、电压的突变、火灾和水灾等均可能引起软、硬件的损坏。1)静态转储和动态转储静态转储是指在转储期间不允许对磁盘上的文件进行任何存取、修改操作；动态转储是在转储期间允许对文件进行存取、修改操作，因此，转储和用户访问可并发执行。,2020/5/16,Page85,2)海量转储和增量转储海量转储也称全量转储。该方法是将文件存储器上的所有文件定期(如每天一次)复制到磁带上。这种方法的缺陷是非常耗时。增量转储是指每次只转储上次转储后更新过的文件。,2020/5/16,Page86,3)日志文件在计算机系统的工作过程中，操作系统把用户对文件的插入、删除和修改的操作写入日志文件。一旦发生故障，操作系统的恢复子系统利用日志文件恢复对文件的改变。,2020/5/16,Page87,3文件系统的一致性影响文件系统可靠性的因素之一是文件系统的一致性问题。很多文件系统是先读取磁盘块到内存，在内存进行修改，修改完毕再写回磁盘。,2020/5/16,Page88,通常的解决方案是采用文件系统的一致性检查，一致性检查包括块的一致性检查和文件的一致性检查。1)块的一致性检查在进行块的一致性检查时，检测程序构造一张计数器表，表中为每个块设立两个计数器，初始化都为0。,2020/5/16,Page89,一个计数器跟踪该块在文件中出现的次数，一个跟踪该块在空闲表中出现的次数。检测程序读取全部的文件索引表，每当读到一个块号时，第一个计数器加1；然后检测程序检查空闲块链表或位图，查找全部未使用的块，每当找到一个空闲块，则第二个计数器加1。,2020/5/16,Page90,图8.16文件系统状态(a)一致；(b)块丢失；(c)重复数据块；(d)空闲表中有重复块,2020/5/16,Page91,图(a)状态下的文件系统是一致的。当系统崩溃后，可能会导致如下几种情况：(1)块丢失：如图(b)所示，磁盘块4和9在第一个计数器和第二个计数器中都没有登记，导致块丢失。(2)重复数据块：如图(c)所示，磁盘块10在第一个计数器中的值等于2，意味着系统检测文件索引表时有两个文件同时使用了磁盘块10，导致文件的不一致。(3)空闲表中有重复块：如图(d)所示，磁盘块8在计数器2中的值等于2，意味着系统检测空闲块链表时磁盘块8出现了两次。,2020/5/16,Page92,2)文件的一致性检测除检查每个磁盘块外，文件系统检测程序还检查目录系统，检查文件链接的一致性。下面我们就以UNIX为例讨论。检查目录要用到一张计数器表，每个文件对应一个计数器。程序从根目录开始检查，沿着目录树下降递归，检查文件系统中的每个目录。对每个目录中的文件，其对应的I节点计数器加1。,2020/5/16,Page93,8.8.2文件系统的安全性1系统级安全管理系统级安全管理的主要任务是不允许未经许可的用户进入系统，从而也防止了他人非法使用系统中的各类资源(包括文件)。系统级管理的主要措施有：(1)注册。注册的主要目的是使系统管理员能够掌握要使用的各用户的情况，并保证用户在系统中的惟一性。,2020/5/16,Page94,(2)登录。用户经注册后就成为该系统用户，但在上机时还必须进行登录。登录的主要目的是通过核实该用户的注册名及口令来检查该用户使用系统的合法性。,2020/5/16,Page95,2用户级安全管理用户级安全管理是通过对所有用户分类和对指定用户分配访问权，即对不同的用户、不同的文件设置不同的存取权限来实现的。例如，在UNIX系统中将用户分为文件主、组用户和其他用户。有的系统将用户分为超级用户、系统操作员和一般用户。,2020/5/16,Page96,3目录级安全管理目录级安全管理是为了保护系统中的各种目录而设计的，它与用户权限无关。为保证目录的安全，规定只有系统核心才具有写目录的权利。用户对目录的读、写和执行与对一般文件的读、写和执行的含义有所不同，对于目录的读权限，意味着允许打开并读该目录的信息。,2020/5/16,Page97,4文件级安全管理文件级安全管理是通过系统管理员或文件主对文件属性的设置来控制用户对文件的访问的。通常可设置以下几种属性：只执行：只允许用户执行该文件，主要针对.exe和.com文件。隐含：指示该文件为隐含属性文件。索引：指示该文件是索引文件。修改：指示该文件自上次备份后是否还可被修改。,2020/5/16,Page98,只读：只允许用户对该文件读。读/写：允许用户对文件进行读和写。共享：指示该文件是可读共享的文件。系统：指示该文件是系统文件。,2020/5/16,Page99,8.8.3文件的保护机制在计算机系统中有很多待保护的对象，这些对象可以是硬件，如CPU、内存块、终端、打印机等设备；也可以是软件，如进程、文件、信号、数据库等。系统对每一个对象赋予一个名字，用户通过名字引用对象。而对象有一个有限的、允许进程在其上进行的一组操作，如对文件进行读、写操作。,2020/5/16,Page100,为此，操作系统必须设置保护机制，防止未授权进程访问对象，并限制进程只执行某个保护域中合法操作的子集。所谓保护域，是指(对象，权限)对的集合，每个对标记了一个对象和一个可执行操作的子集。这里，权限表示可执行的操作。图8.17表示了三个保护域以及域中的对象和对象允许的操作权限(读、写、执行)。,2020/5/16,Page101,图8.17保护域示例,2020/5/16,Page102,1.存取控制矩阵理论上，存取控制方法可用存取控制矩阵表示，它是一个二维矩阵，一维列出计算机的全部用户，另一维列出系统中的全部文件。矩阵中每个元素Aij表示第i个用户对第j个文件的存取权限。通常存取权限有可读、可写、可执行以及它们的组合，如表8.3所示。,2020/5/16,Page103,表8.3存取控制矩阵,2020/5/16,Page104,2存取控制表存取控制矩阵由于矩阵太大而往往无法实现。一个改进的办法是按用户对文件的访问权限的差别对用户进行分类，由于某一文件往往只与少数几个用户有关，因而这种分类方法可使存取控制表大为简化。在许多系统中把与每个文件连接的用户分成三类:文件主伙伴(与文件创建者同组的用户)一般用户,2020/5/16,Page105,表8.4用户权限表,2020/5/16,Page106,练习题1.某软盘有40个磁道,磁头从一个磁道移至另一个磁道需要6ms。文件在磁盘上非连续存在，逻辑上相邻数据块的平均距离为13磁道，每块的旋转延迟时间及传输时间分别为100ms，25ms。1）问读取一个100块的文件需要多少时间？2）如果系统对磁盘进行了整理，让同一文件的磁盘块尽可能靠拢，从而逻辑上相邻数据块的平均距离为2磁道，这时读取一个100块的文件需要多少时间？,分析磁盘访问时间由三部分组成，即寻道时间，旋转延迟时间和传输时间，其中，寻道时间是指将磁头从当前位置移动到指定磁道所经历的时间。1）读一块的时间为：13*6+100+25=203ms因此，读取一个100块的文件需要时间：203*100=20300ms2）同理可得，13700ms,2020/5/16,Page107,假定磁盘块的大小为1K，对于540M的硬盘，其文件分配表FAT需要占用多少存储空间？当磁盘容量为1.2G时，FAT需要占用多少空间？分析540M/1k=540k共有540k个盘块5125401024表示0-539个盘块号，需要用20位二进制位表示，即FAT的每个表目为2.5个字节2.5*540k=1350k同理，1.2G磁盘空间占用FAT的空间总数为4.8M,2020/5/16,Page108,习题,1在UNIX系统中，文件File的I节点中有10个直接地址，一级、二级和三级间接索引地址分别为一个。如果间接盘块可以存放256个盘块地址，每个盘块地址长度为4个字节。请回答：(1)若文件File的大小为2MB，那么分别占了多少个直接盘块和间接盘块？(2)若文件File的大小为10MB，那么分别占了多少个直接盘块和间接盘块？(3)若文件File的大小为25MB，那么分别占了多少个直接盘块和间接盘块？,2020/5/16,Page109,2.某文件系统以硬盘作为文件存储器，物理块大小为512B。有文件A包含590个逻辑记录，每个记录占255B，每个物理块存放2个记录。文件A在该文件目录中的位置如图所示。此树形目录结构由根目录节点、作为目录文件的中间节点和作为信息文件的叶子节点组成。每个目录占127B，每个物理块存放4个目录项。根目录的内容常驻内存。若文件采用链接分配方式，如果要将文件A读入内存，至少需要存取几次硬盘，为什么？若文件采用连续分配方式，如果要将文件A的逻辑记录号为480的记录读入内存，至少要存取几次硬盘，为什么？若文件采用索引分配方式，一个索引项占4B，则至少需要几级索引可以寻址文件A？如果要将文件A的逻辑记录号为480的记录读入内存，至少需要存取几次硬盘？,2020/5/16,Page110,3假定磁盘有500个柱面,编号为0499,当前存取臂的位置在206号柱面上,并刚刚完成了150号柱面的服务请求,如果请求队列的先后顺序是：286，225，278，168，296，94，332，414，491，205，246，398。试用SSTF(最短查找时间)算法和SCAN(电梯调度)算法计算移臂总量，写出移臂顺序。,2020/5/16,Page111,4在UNIX系统中，若有如下三种情况：(1)P1进程执行如下代码：fd1=open(/bin/test,o_RDONLY);fd2=open(/usr/bin/wangproc,o_RDWR);(2)P1进程创建的子进程P2执行如下代码：fd3=open(/usr/bin/test.c，o_RDONLY);(3)P3进程执行如下代码：fd1=open(/etc/test,o_WRONLY);,2020/5/16,Page112,请画出进程打开文件表u_ofile、系统打开文件表file和内存索引节点表i_node之间的关系图。5.有6个访问18号柱面的请求进程，要求如表8.8所示。按照旋转调度的原则，请问有多少种可能的顺序？并给出它们的执行顺序。,2020/5/16,Page113,表8.8习题4用表,2020/5/16,Page114,8.设系统有如下请求队列：8，18，27，129，110，186，78，147，41，10，64，12；并假设磁头当前位置在100号磁道下。(1)试用查找时间最短优先算法计算处理所有请求所移动的总柱面数。(2)用电磁调度算法计算处理所有存取请求所移动的总柱面数(分别按升序和降序移动)。,2020/5/16,Page115,7某文件为连接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。现要读出文件的1569字节，请问访问的磁盘块号等于多少？8假如当前磁头位于1号柱面，用户进程对磁盘的请求如表8.9所示。,2020/5/16,Page116,表8.9习题7用表,试分析对这5个请求如何调度，可使磁盘的旋转圈数最少。,2020/5/16,Page117,9假定磁盘有200个柱面，编号为0199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果