计算机操作系统第八章-磁盘存储器的管理

第八章磁盘存储器的管理第一节文件的物理结构和外存的分配方式一、概述磁盘是一种可直接存取的随机存储器(这一点与内存相似)，一个逻辑盘可以看作一片连续的存储空间。确定外存空间的分配方式(组织文件的物理结构)主要考虑：提高文件的访问速度、有效地利用外存空间。常用的外存分配方法有：连续分配、链接分配、索引分配。二、磁盘存储空间的结构磁盘说明图1盘块(扇区)是磁盘上的最小存储分配单位，每个盘块有唯一编号；地址是：磁道(柱面)号+扇区号+盘面号；从盘块编号到地址的转换由硬件完成，在OS中一个盘块的地址就是盘块编号。一般一个盘块的大小与内存分页中页(内存块)的大小一致，一页存放到一个盘块中。三、连续分配1、思想方法为每个文件分配一组位置相邻接的盘块(磁盘上的地址连续/盘块编号连续的盘块)，文件中的逻辑页被顺序地存放到邻接的各物理盘块中。这保证了文件中的逻辑顺序与文件占用盘块顺序的一致性。这样物理结构的文件称为顺序文件；每个文件都从分配给它的一个盘块的第一个字节开始存放。文件地址：在文件的目录中，存放该文件的第一个记录所在的盘块号和文件的长度(共占多少块)。1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62????trf图8-1磁盘空间的连续分配2、优缺点存取容易，存取速度较快；必须事先知道文件的长度，不利于文件的动态增长；存放一个文件要求足够大的连续存储空间；存储空间的管理存在“碎片”问题，须定时整理。四、链接分配1、思想方法：为每个文件分配一组位置离散的盘块，每个盘块中存放文件的一个逻辑页；通过给每个盘块设置一个指针，将属于同一个文件的盘块链接在一起，链接的顺序和文件的逻辑页的顺序一致。这样物理结构的文件称为链接文件。保存链接指针的方式有两种，形成了隐式链接和显式链接。2、隐式链接----链接指针如何存放页块号下一页下一页的指针(块号)091161162121310310425425无-1图8-2磁盘空间的链接式分配文件的每一个盘块内都含有指向下一个逻辑页存放地址的指针(盘块号)。文件地址：在文件的目录中，存放指向文件第一个盘块的指针和文件长度。隐式链接的问题：P553、显式链接----链接指针如何存放每个磁盘(逻辑盘)有一张文件分配表(FAT)，它是记录磁盘分配使用情况的数据结构(记录文件的链接指针序列)。磁盘包含N个盘块，FAT就有N个表项。表项顺序编号0~N-1，对应盘块的编号0~N-1。文件地址：每个文件占用的第一个盘块的编号存放在文件目录中；文件占用的其他盘块的编号存放在FAT中；文件占用的每一个盘块对应的FAT表项，其中存放指向该文件的下一个盘块的指针(即盘块编号)；文件占用的最后一个盘块对应的FAT表项中存放文件结束标志；(文件的FCB+FAT表为每个文件记录的两个信息)目录和FAT一起记录了哪些盘块分给了这个文件，以及这些盘块中内容的逻辑顺序。例如，MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCBA4FCBB9图8-4MS-DOS的文件物理结构5、优缺点优点：与内存的分页式存储管理相似，提高了磁盘空间利用率不存在外存碎片问题有利于文件动态扩充缺点：较多的寻道次数和寻道时间，存取速度相对慢些存在可靠性问题，如指针出错不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。FAT需占用较大的存储空间。6、从FAT12到FAT32，NTFS：P61-62，65，68，70-72五、索引分配1、思想方法为每个文件分配一组位置离散的盘块，每个盘块中存放文件的一个逻辑页；为每个文件建立一个物理结构的索引表(类似于内存管理的页表)，记录分配给该文件的物理盘块，以及这些盘块和文件逻辑页顺序的对应关系。建立一个文件时，要初始化它的索引表，并将索引表的地址放到文件的目录中。打开一个文件时，文件的索引表也被同时读入内存。这样物理结构的文件称为索引文件。这种结构的文件，支持直接访问。123056749101181314151217181916212223202526272429303128countfile?éDòo?jeep19????91611025￡1￡1￡119图8-6索引分配方式2、单级索引每个文件一张索引表，这张索引表放在一个盘块中(因此也称索引块，索引表的长度不能超过一块的容量)。缺点：要花费一定的外存空间存放索引表；文件的长度受到了限制。3、多级索引对于一个长文件的长索引表(单个盘块放不下)，可以将它存放在若干个离散的盘块中。再为这些索引块建立一个索引表，存放在一个盘块中，这样就形成了一个文件的两级索引。同理，还可以构造多级索引。012?????105106254356357985105106254740356357?1125985360740?1125?主索引360第二级索引磁盘空间图6-12两级索引分配4、混合索引文件系统混合使用多种分配方式。文件的目录中可以存放不同形式的地址信息：直接地址，文件数据的盘块号；一次间接地址，文件索引块的盘块号；二次间接地址，文件二级索引块的盘块号。modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)directblockssingleindirectdoubleindirecttripleindirectdatadatadatadata??datadata???datadatadatadata图6-13混合索引方式5、索引分配的优缺点优点：保持了链接结构的优点，又解决了其缺点：既能顺序存取，又能随机存取，满足了文件动态增长缩短、插入删除的要求，也能充分利用外存空间。缺点：较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间。第二节文件存储空间管理一、文件存储空间管理涉及到的问题1、外存上的空闲块按什么方式组织起来(存储管理的数据结构)2、如何为一个文件分配存储空间3、怎样回收被释放的存储空间注意：文件存储器基本的分配和回收单位是磁盘块、簇，而不是字节。二、空闲表(空白文件目录)管理法1、空闲块的组织：将磁盘空间上每一片连续空闲区(包含若干个连续编号的空闲块)看作一个“空白文件”，系统建立一个空闲表(空白文件目录)，每个空白文件在表中占一行。序号第一空闲盘块号空闲盘块数12429331554——2、存储空间的分配与回收方法与内存的动态分区分配类似(连续分配)，也有首次适应算法、循环首次适应算法、最佳适应算法等。这样的存储分配方法，文件的物理结构是顺序文件。在内存管理上，连续分配方式很少采用，但在外存管理上，由于它具有较高的分配速度，磁盘访问速度也较快，这种管理方法仍然可能被采用。三、空闲链表法1、空闲块链法：将磁盘上所有的空闲块拉成一条链，在链首设一个分配指针，在链尾设一个回收指针。空闲块的分配与回收分别在链的首尾进行。2、空闲区链法：将磁盘上所有的空闲区(包含若干连续空闲块)拉成一条链，空闲区中要记录本区包含的空闲块数，链收尾分别设分配、回收指针。存储空间的分配与回收与内存的动态分区分配类似。四、位示图法1、空闲块的组织：为每一个文件存储器(逻辑盘)建立一张位示图。磁盘的每一个物理块都有一个二进制位与之对应。该位值是“0”为空闲、“1”为已分配。开机后位示图常驻内存，存在连续若干个字中。2、存储空间的分配与回收•位示图需要多少个字，取决于一个逻辑盘包含的盘块数(簇)。•分配物理块时，可以在位示图中顺序查找一个或若干其值为0的位，计算并返回每位对应的物理块号，分配物理块，并将位示图中对应的位置“1”；P130•回收物理块时，将回收的物理块号逆计算，得出块在位示图中的位置，并将对应的位置“0”。P131五、成组链法100400399301300100300299?202201299?100400399?201301???9907999790179007899?78017999?7901???D?ì?éo???S.free019899图8-11空闲盘块的成组链接法1、空闲块的组织：•将系统的所有空白块每N个形成一组(例如N=100；这N个空白块位置不必连续)；•将所有的空白块组链接起来。链接的方法是：每一组的第一个空白块存放前一组的盘块总数和包含的每一个盘块号；•由于第一组的前面已无其他组存在，因此，第一组的块数为N-1块；•由于存储设备的空间块不一定正好是N的整倍数，因而最后一组可能不足N块。由于该组后面已无另外的空闲块组，所以，该组的盘块号与总块数组织成堆栈，放在管理文件存储设备用的文件资源表中；•系统在初启时把文件资源表复制到内存，从而使文件资源表中存放有最后一组空闲块的块号与总块数的堆栈被进入内存，空闲块的分配与释放在内存进行。2、存储空间的分配•堆栈指针i的初值等于最后一组的空闲块数。•当申请者提出空闲块需求时，按照后进先出的原则，分配程序取走i所指的块号，将对应盘块分配出去，然后再做一次i=i-1操作，并将空闲块数减1。•这个过程一直持续到本次任务所要求的块都已分配完毕或堆栈中只剩下最后一个空闲块的块号。•当堆栈中只剩下最后一个空闲块号时，系统启动I/O管理程序，将该块中存放的前一组的块号与总块数读入内存堆栈中，之后将该块分配给申请者。然后，系统重新设置i指针，分配程序继续为申请者进程分配空闲块，直到满足本次任务。3、存储空间的回收•在系统回收空闲盘块时，盘块回收过程首先进行i=i+1操作，将回收盘块的盘块号记入堆栈的顶部，并执行空闲盘块数加1操作。•当堆栈中空闲盘块数目已达到N时，表示栈已满、本组回收已结束。如果这时如果又有一个新的空闲盘块待回收，便将目前堆栈中的内容(N个盘块号和盘块总数)，记入新回收的盘块中；然后重置i值为1、空闲盘块数初值1，再将新回收的盘块号存进栈底，另起一个组。•存放空闲块号与块总数的堆栈是一个临界资源，应该互斥访问。第三节提高磁盘I/O速度的途径一、提高文件系统的访问速度，可以从三方面着手：P263二、磁盘高速缓存目前，磁盘的访问速度远低于内存访问速度，磁盘I/O成为了计算机系统的瓶颈。于是，出现了磁盘的高速缓存。这里的高速缓存是在内存中为磁盘的盘块设置一个缓冲区，在其中保存某些盘块的副本。对信息进出内存，采取提前读和推迟写。P2631、磁盘高速缓存的形式在内存中高速缓存可分成两种形式：•第一种是在内存中开辟一个单独的存储空间，作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；•第二种是将所有空闲的内存空间供请求分页系统和磁盘高速缓存共享。此时高速缓存的大小不再是固定的。当磁盘I/O较频繁时，该缓冲区可能包含更多的内存空间；而在应用程序运行得较多时，该缓冲区可能只剩下很少的内存空间。2、数据交付：P178系统可以采取两种数据交付方式：•数据交付。这是直接将高速缓存中的数据复制到请求者进程的内存工作区中。•指针交付。只将指向高速缓存中某区域的指针(地址)，交付给请求者进程。后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存空间到进程的内存工作区的时间。3、置换算法高速缓存的容量是有限的，满了以后再继续使用，也需要进行存储块的置换。这里解决的是缓冲区中的盘块内容，何时往磁盘上写。常用的算法与页面置换算法基本相同。除了考虑到最近最久未使用这一原则外，还考虑了以下几点：(1)访问频率。(2)可预见性。(3)数据的一致性。4、周期性地回写磁盘根据置换算法，高速缓存中经常被访问的块会一直存放在其中，不会有机会被换出(写回磁盘)。而内存是易失性存储器。为了保证数据不丢失，OS要经常主动将数据写回磁盘上。例如：在UNIX系统中专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块