《计算机操作系统第八章》由会员分享，可在线阅读，更多相关《计算机操作系统第八章（20页珍藏版）》请在金锄头文库上搜索。
1、第八章 磁盘存储器的管理第一节 文件的物理结构和外存的分配方式 一、概述 磁盘是一种可直接存取的随机存储器（这一点与内存相似），一个 逻辑盘可以看作一片连续的存储空间。确定外存空间的分配方式 （组织文件的物理结构 ）主要考虑：提 高文件的访问速度、有效地利用外存空间。常用的外存分配方法有：连续分配、链接分配、索引分配。-1丄二- 一一 u_盘面9盘面8 盘面7 盘面6 盘面5盘面斗盘面3盘面2盘面1盘面0磁盘说明图 1盘块（扇区）是磁盘上的最小存储分配单位，每个盘块有唯一编号；地址是：磁道（柱面）号+扇区号+盘面号；从盘块编号到地址的转换由硬件完成，在OS中一个盘块的地址就是盘块编号般一个盘块
2、的大小与内存分页中页（内存块）的大小一致，一页存放到一个盘块中。三、连续分配 1、思想方法为每个文件分配一组位置相邻接的盘块（磁盘上的地址连续/盘块 编号连续的盘块），文件中的逻辑页被顺序地存放到邻接的各物理盘 块中。这保证了文件中的逻辑顺序与文件占用盘块顺序的一致性。这 样物理结构的文件称为顺序文件；每个文件都从分配给它的一个盘块 的第一个字节开始存放。文件地址：在文件的目录中，存放该文件的 第一个记录所在的盘块号和文件的长度（共占多少块）。?159371591 1 9 9 9 cum 048260481 1 9 9二 2Q 6=10Q1418mail2226list303 f7 ntr15
3、19232731filecounttrmaillistf1400 c 312 6length23642图 8-1 磁盘空间的连续分配2、优缺点存取容易，存取速度较快；必须事先知道文件的长度，不利于文件的动态增长存放一个文件要求足够大的连续存储空间；存储空间的管理存在“碎片”问题，须定时整理。四、链接分配1、思想方法：为每个文件分配一组位置离散的盘块，每个盘块中存 放文件的一个逻辑页；通过给每个盘块设置一个指针，将属于同一个 文件的盘块链接在一起，链接的顺序和文件的逻辑页的顺序一致。这 样物理结构的文件称为链接文件。保存链接指针的方式有两种，形成了隐式链接和显式链接。2、隐式链接链接指针如何存放
4、图 8-2 磁盘空间的链接式分配页块号下一页下一页的指针（块号）091161162121310310425425无-1文件的每一个盘块内都含有指向下一个逻辑页存放地址的指针 （盘块号）。文件地址：在文件的目录中，存放指向文件第一个盘块的 指针和文件长度。隐式链接的问题： P553、显式链接链接指针如何存放每个磁盘（逻辑盘）有一张文件分配表（FAT）,它是记录磁盘分配使 用情况的数据结构（记录文件的链接指针序列）。磁盘包含N个盘块， FAT就有N个表项。表项顺序编号0N-1,对应盘块的编号0N-1。文件地址：每个文件占用的 第一个盘块的编号存放在文件目录 中；文件占用的其他盘块的编号存放在FAT
5、中；文件占用的每一个 盘块对应的FAT表项，其中存放指向该文件的下一个盘块的指针（即 盘块编号）；文件占用的最后一个盘块对应的FAT表项中存放文件结 束标志；（文件的FCB+FAT表为每个文件记录的两个信息）目录和 FAT 一起记录了哪些盘块分给了这个文件，以及这些盘 块中内容的逻辑顺序。FCB物理块弋FAT02 一L* -124345例如，MS-DOS的文件物理结构FCB A FAT图 8-4 MS-DOS 的文件物理结构5、优缺点优点：与内存的分页式存储管理相似，提高了磁盘空间利用率不存在外存碎片问题有利于文件动态扩充缺点：较多的寻道次数和寻道时间，存取速度相对慢些存在可靠性问题，如指针出
6、错.不能支持高效的直接存取。要对一个较大的文件进行直接存取 .须首先在FAT中顺序地查找许多盘块号。FAT需占用较大的存储空间.6、从 FAT12至U FAT32 NTFS： P61-62，65，68，70-72五、索引分配1、思想方法为每个文件分配一组位置离散的盘块，每个盘块中存放文件的一 个逻辑页；为每个文件建立一个物理结构的索引表（类似于内存管理 的页表），记录分配给该文件的物理盘块，以及这些盘块和文件逻辑 页顺序的对应关系。建立一个文件时，要初始化它的索引表，并将索 引表的地址放到文件的目录中。打开一个文件时，文件的索引表也被 同时读入内存。这样物理结构的文件称为索引文件。这种结构的文
7、件，支持直接访问。coun44口8 口125 co9LZ；!13 I：16；718元二I1202122242514261123file?eDoo?jeep19?29 匚二| 30图 8-6 索引分配方式2、单级索引每个文件一张索引表，这张索引表放在一个盘块中（因此也称索引块，索引表的长度不能超过一块的容量）。缺点：要花费一定的外存空间存放索引表； 文件的长度受到了限制。.3、多级索引对于一个长文件的长索引表（单个盘块放不下），可以将它存放在 若干个离散的盘块中。再为这些索引块建立一个索引表，存放在一个 盘块中，这样就形成了一个文件的两级索引。同理，还可以构造多级 索引。第二级索引主索引磁盘空间
8、360254985图 6-12 两级索引分配3563571051060124、混合索引文件系统混合使用多种分配方式。文件的目录中可以存放不同形 式的地址信息：直接地址，文件数据的盘块号；一次间接地址，文件索引块的盘块号；二次间接地址，文件二级索引块的盘块号modeowners (2)da tasizeda tablock counti.addr (0)-i.addr (1)- direct blocksda tada tasingle indirectdouble indirecttriple indirectda tada takda ta?Ada tada ta?da tatime sta
9、mps (3)图 6-13 混合索引方式5、索引分配的优缺点优点：保持了链接结构的优点，又解决了其缺点：既能顺序存取，又能 随机存取，满足了文件动态增长缩短、插入删除的要求，也能充分利 用外存空间。缺点：较多的寻道次数和寻道时间，索引表本身带来了系统开销，如： 内外存空间，存取时间。第二节 文件存储空间管理一、文件存储空间管理涉及到的问题1、外存上的空闲块按什么方式组织起来（存储管理的数据结构）2、如何为一个文件分配存储空间3、怎样回收被释放的存储空间 注意：文件存储器基本的分配和回收单位是磁盘块、簇，而不是字节。二、空闲表（空白文件目录）管理法1、空闲块的组织：将磁盘空间上每一片连续空闲区（
10、包含若干个连续 编号的空闲块）看作一个“空白文件”，系统建立一个空闲表（空白文 件目录），每个空白文件在表中占一行。序号第一空闲盘块号空闲盘块数124293315542、存储空间的分配与回收 方法与内存的动态分区分配类似 （连续分配 ），也有首次适应算 法、循环首次适应算法、最佳适应算法等。这样的存储分配方法，文件的物理结构是顺序文件。在内存管理上，连续分配方式很少采用，但在外存管理上，由于 它具有较高的分配速度，磁盘访问速度也较快，这种管理方法仍然可 能被采用。三、空闲链表法1、空闲块链法：将磁盘上所有的空闲块拉成一条链，在链首设一个 分配指针，在链尾设一个回收指针。空闲块的分配与回收分别在
11、链的 首尾进行。2、空闲区链法：将磁盘上所有的 空闲区（包含若干连续空闲块）拉成 一条链，空闲区中要记录本区包含的空闲块数，链收尾分别设分配、 回收指针。存储空间的分配与回收与内存的动态分区分配类似。四、位示图法1、空闲块的组织：为每一个文件存储器 （逻辑盘）建立一张位示图。 磁盘的每一个物理块都有一个二进制位与之对应。该位值是“0”为 空闲、“1”为已分配。开机后位示图常驻内存，存在连续若干个字中。123456789101112131415161110001110010011020001111110000111311100011111100.004i、存储空间的分配与口收 位示图需要多少个字
12、，取决于一个逻辑盘包含的盘块数（簇 ） 。 分配物理块时，可以在位示图中顺序查找一个或若干其值为 0 的 位，计算并返回每位对应的物理块号，分配物理块，并将位示图中对 应的位置“1”； P130 回收物理块时，将回收的物理块号逆计算，得出块在位示图中的 位置，并将对应的位置“0”。 P131五、成组链法201 301 7801 7901图 8-11 空闲盘块的成组链接法1、空闲块的组织：将系统的所有空白块每N个形成一组（例如N=100；这N个空白 块位置不必连续）； 将所有的空白块组链接起来。链接的方法是：每一组的第一个空 白块存放前一组的盘块总数和包含的每一个盘块号； 由于第一组的前面已无其
13、他组存在，因此，第一组的块数为 N-1 块；由于存储设备的空间块不一定正好是N的整倍数，因而最后一组 可能不足 N 块。由于该组后面已无另外的空闲块组，所以，该组的 盘块号与总块数组织成堆栈，放在管理文件存储设备用的文件资源表 中； 系统在初启时把文件资源表复制到内存，从而使文件资源表中存 放有最后一组空闲块的块号与总块数的堆栈被进入内存，空闲块的分 配与释放在内存进行。2、存储空间的分配 堆栈指针 i 的初值等于最后一组的空闲块数。 当申请者提出空闲块需求时，按照后进先出的原则，分配程序取 走 i 所指的块号，将对应盘块分配出去，然后再做一次 i=i-1 操作， 并将空闲块数减 1。 这个过程一直持续到本次任务所要求的块都已分配完毕或堆栈中 只剩下最后一个空闲块的块号。 当堆栈中只剩下最后一个空闲块号时，系统启动 I/O 管理程序， 将该块中存放的前一组的块号与总块数读入内存堆栈中，之后将该块 分配给申请者。然后，系统重新设置i指针，分配程序继续为申请者 进程分配空闲块，直到满足本次任务。3、存储空间的回收 在系统回收空闲盘块时，盘块回收过程首先进行 i=i+1 操作，将 回收盘块的盘块号记入堆栈的顶部
