第8章 磁盘存储器的管理2

第八章磁盘存储器的管理回顾目录管理目录管理的要求实现“按名存取”。提高对目录的检索速度。文件共享。允许文件重名。第八章磁盘存储器的管理UNIX文件系统由四部分构成：1243引导块=0#块超级块=1#块索引节点表=2--k#块数据区=k+1--n#块第八章磁盘存储器的管理UNIX目录结构--分层的倒置树状结构/devusrsbinetctmphomebinbinbin1manteam1team2第八章磁盘存储器的管理目录中的文件与磁盘文件的对应：1076108022763476aa.cbb.cff.c….目录中内容aa.c索引表…………文件数据块指针aa.c索引节点aa.c磁盘设备第八章磁盘存储器的管理56.5文件存储空间的管理文件管理要解决的重要问题之一是如何为新创建的文件分配存储空间。其解决方法与内存的分配情况有许多相似之处连续分配方式离散分配方式存储空间的基本分配单位都是磁盘块而非字节。数据结构分配和回收功能为了实现存储空间的分配，首先必须记住空闲存储空间的使用情况。第八章磁盘存储器的管理文件存储空间的管理方法空闲表法和空闲链表法位示图法成组链接法重点难点第八章磁盘存储器的管理8.2.1空闲表法和空闲链表法空闲表法属于连续分配方式。与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，再将所有空闲区按其起始盘块号递增的次序排列与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。应该说明，虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地。空闲表分配与回收序号第一空闲盘块号空闲盘块数12429331554——第八章磁盘存储器的管理这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次。这是将磁盘上的所有空闲盘区拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小的信息。分配盘区的方法与内存动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻的空闲盘区相合并。在采用首次适应算法时，为提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。8.2.1空闲表法和空闲链表法空闲链表法空闲盘块链空闲盘区链第八章磁盘存储器的管理9说明:在内存分配上，虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍然占有一席之地。第八章磁盘存储器的管理101601531空闲块链表第八章磁盘存储器的管理8.2.2位示图法是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为0时表示对应的盘块空闲，为1时表示已分配（Linux)。有的系统则相反。磁盘上的所有盘块都有一个二进制位与之对应，这样由所有盘块所对应的位构成一个集合，称为位示图。通常可用m*n个位数来构成位示图，并使m*n等于磁盘的总块数。位示图二维数组Varmap：array[1…m,1…n]ofbit第八章磁盘存储器的管理0000111111000111111000011111100001100100111000111615141312111098765432116..4321位示图盘块的分配顺序扫描位示图。以找到一个或一组其值为“0”的二进制位;第八章磁盘存储器的管理0000111111000111111000011111100001100100111000111615141312111098765432116..4321位示图盘块的分配顺序扫描位示图。以找到一个或一组其值为“0”的二进制位;第八章磁盘存储器的管理0000111111000111111000011111100001100100111000111615141312111098765432116..4321位示图盘块的分配将所找到的一个或一组二进制位转换成盘块号b=列数n*（i-1）+j;第八章磁盘存储器的管理0000111111000111111000011111100001100100111000111615141312111098765432116..4321位示图盘块的分配b=3;b=4;b=5第八章磁盘存储器的管理0000111111000111111000011111100001100100111111111615141312111098765432116..4321位示图盘块的分配修改位示图。Map[i,j]=1第八章磁盘存储器的管理位示图盘块的回收将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i=(b-1)DIVn+1j=(b-1)MODn+10000111111000111111000011111100001100100111000111615141312111098765432116..4321第八章磁盘存储器的管理位示图盘块的回收0000111111000111111000011111100001100100111000111615141312111098765432116..4321修改位示图Map[i,j]=0;第八章磁盘存储器的管理位示图盘块的回收修改位示图Map[i,j]=0;0000111111000111111000011001100001100100111000111615141312111098765432116..4321第八章磁盘存储器的管理位示图优点从位示图中很容易找到一个或一组相邻接的空闲盘块。此外，由于位示图很小，占用空间少，因而可将它保存在内存中，从而在每次进行盘区分配时，无需首先把磁盘分配表读入内存，从而省掉许多磁盘的启动操作。位示图常用于微型机和小型机中，如Linux0000111111000111111000011001100001100100111000111615141312111098765432116..4321第八章磁盘存储器的管理8.2.3成组链接法空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。在UNIX系统中采用的是成组链接法，这是将上述两种方法结合而形成的一种空闲盘块管理方法，它兼备了上述方法的优点而克服了表太长的缺点。第八章磁盘存储器的管理成组链接法空闲盘块的组织空闲盘块的分配与回收第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401空闲盘块号栈。用来存放当前可用的一组空闲盘块的盘块号（最多含100个号），以及栈中尚有的空闲盘块号数N。N还兼具栈顶指针用。例如当N=100时，它指向S.free(99)。S.free(0)是栈底，栈满时栈顶为S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。信号量第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401文件存储空间中的所有空闲盘块，被分成若干个组，比如，将每100个盘块作为一组，假定盘上共有10000个盘块，将会分成100个组，其中第201-7999号盘块用于存放文件，即作为文件区第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401第一组为201-300第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401第二组为301-400；第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401次末组为7801-7900第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401该区的最末一组的盘块号应为7901-7999第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401将每一组含有的盘块总数N和该组的盘块号，记入其前一组的第一个盘块的S.free(0)~S.free(99)中。这样由各组的第一个盘块形成了一条链。第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………空闲盘块的组织100300299…202201100400399…301100500499…401最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)~S.free(99)中，而在S.free(0)中则存放0，作为空闲盘块链的结束标志。第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…799909920129930039940079007899799930178017901………100300299…202201100400399…301100500499…401分配当系统要为用户分配盘块时，须调用分配过程来完成。首先检查空闲盘块号栈是否上锁，如没有，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。第八章磁盘存储器的管理019899空闲盘块号栈S.free7901…7999099201299300399400790