操作系统第6章文件管理(5)

1、Operating SystemOperating SystemPage 12022-5-20Operating SystemOperating SystemPage 22022-5-20q文件和文件系统文件和文件系统q文件的逻辑结构文件的逻辑结构q外存分配方式外存分配方式q目录管理目录管理q文件存储空间的管理文件存储空间的管理q文件共享与文件保护文件共享与文件保护q数据一致性控制数据一致性控制Operating SystemOperating SystemPage 32022-5-206.5 文件存储空间的管理文件存储空间的管理 解决的问题：如何为新创建的文件分配存储空间？解决的问题：如何为

2、新创建的文件分配存储空间？解决的方法：（分配的基本单位都是磁盘块）。解决的方法：（分配的基本单位都是磁盘块）。1、分配方式：、分配方式：（1）连续分配：访问速度高，但会产生外存零头。）连续分配：访问速度高，但会产生外存零头。（2）离散分配：访问速度慢，但能有效利用外存空间。）离散分配：访问速度慢，但能有效利用外存空间。2、分配时数据结构、分配时数据结构3、分配回收算法、分配回收算法Operating SystemOperating SystemPage 42022-5-20q空闲表法和空闲链表法空闲表法和空闲链表法q位示图法位示图法q成组链接法成组链接法Operating SystemOper

3、ating SystemPage 52022-5-20q文件存储空间管理的基本分配单位是盘块文件存储空间管理的基本分配单位是盘块q空闲表法空闲表法v空闲表属于空闲表属于连续分配方式连续分配方式，与内存的动态分配方，与内存的动态分配方式雷同，为每个文件分配一个连续的存储空间式雷同，为每个文件分配一个连续的存储空间v为外存上的所有空闲区建立一张空闲表，每个空为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个闲表项，将所有空闲区按起始盘闲区对应于一个闲表项，将所有空闲区按起始盘块号递增的顺序排列块号递增的顺序排列v存储空间的分配与回收可采用存储空间的分配与回收可采用首次适应算法、循首次适应算法

4、、循环首次适应算法环首次适应算法等等v如对换方式中对如对换方式中对对换空间对换空间的分配就采用连续分配，的分配就采用连续分配，主要目的是提高速度，主要目的是提高速度，p113v系统中的系统中的较小文件较小文件也也采用连续采用连续分配方式，如分配方式，如“簇簇”Operating SystemOperating SystemPage 62022-5-206.5 文件存储空间的管理文件存储空间的管理 6.5.1 空闲表法和空闲链表法空闲表法和空闲链表法 1. 空闲表法空闲表法属于连续分配，系统为外存上的所有空闲区建立一张空闲表，属于连续分配，系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一

5、个空闲表项，包括：每个空闲区对应一个空闲表项，包括： 图图 6-20 空闲盘块表空闲盘块表 序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数12429331554Operating SystemOperating SystemPage 72022-5-20q存储空间的分配与回收存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等采用首次适应算法、循环首次适应算法等q在系统为某新创建的文件分配空闲盘块时，先顺在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大序地检索

6、空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户小能满足要求的空闲区，再将该盘区分配给用户(进程进程)，同时修改空闲表。系统在对用户所释放，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的存储空间进行回收时，也采取类似于内存回收的方法，即要的方法，即要考虑回收区是否与空闲表中插入点考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并的前区和后区相邻接，对相邻接者应予以合并Operating SystemOperating SystemPage 82022-5-202. 空闲链表法空闲链表法 将所有空闲盘区，拉成一条空闲

7、链，根据构成链所用的将所有空闲盘区，拉成一条空闲链，根据构成链所用的基本元素的不同，可把链表分成基本元素的不同，可把链表分成2种形式：种形式：（1） 将磁盘上所有空闲区空间，为盘块为单位拉成一条链，将磁盘上所有空闲区空间，为盘块为单位拉成一条链，当用户因创建文件而请求分配存储空间时，系统从链首开始，当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块链给用户。当用户因删除文件依次摘下适当数目的空闲盘块链给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。的末尾。：分配和回收一个盘块的

8、过程非常简单。分配和回收一个盘块的过程非常简单。：但在为一个文件分配盘块时，可能要重复多次操作。但在为一个文件分配盘块时，可能要重复多次操作。（2）Operating SystemOperating SystemPage 92022-5-202. 空闲链表法空闲链表法 将所有空闲盘区，拉成一条空闲链，根据构成链所用的将所有空闲盘区，拉成一条空闲链，根据构成链所用的基本元素的不同，可把链表分成基本元素的不同，可把链表分成2种形式：种形式：（1）：分配和回收一个盘块的过程非常简单。分配和回收一个盘块的过程非常简单。：但在为一个文件分配盘块时，可能要重复多次操作。但在为一个文件分配盘块时，可能要重复

9、多次操作。（2） 将磁盘上所有空闲盘区拉成一条链，在每个盘区上包含将磁盘上所有空闲盘区拉成一条链，在每个盘区上包含若干用于指示下一个空闲盘区的指针，指明盘区大小的信息。若干用于指示下一个空闲盘区的指针，指明盘区大小的信息。 分配盘块时，通常采用首次适应算法（显式链接法）。分配盘块时，通常采用首次适应算法（显式链接法）。 在回收时，要将回收区与空闲盘区相合并。在回收时，要将回收区与空闲盘区相合并。Operating SystemOperating SystemPage 102022-5-20q空闲表法和空闲链表法空闲表法和空闲链表法q位示图法位示图法q成组链接法成组链接法Operating Sy

10、stemOperating SystemPage 112022-5-20q位示图位示图v用用二进制的一位二进制的一位来表示磁盘中一个盘块的使用来表示磁盘中一个盘块的使用情况情况v0表示盘块空闲，表示盘块空闲，1表示盘块已分配表示盘块已分配v由所有盘块所对应的二进制位构成的一个集合由所有盘块所对应的二进制位构成的一个集合称为位示图，通常可用称为位示图，通常可用m*n个位数来构成位示个位数来构成位示图，并使图，并使m*n等于磁盘总块数等于磁盘总块数Operating SystemOperating SystemPage 122022-5-20Operating SystemOperating Sy

11、stemPage 132022-5-20q盘块的分配盘块的分配v顺序扫描位示图，从中找出一个或一组其值为顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位的二进制位(“0”表示空闲时表示空闲时)v将所找到的一个或一组二进制位，将所找到的一个或一组二进制位， 转换成与之转换成与之相应的盘块号。假定找到的其值为相应的盘块号。假定找到的其值为“0”的二进的二进制位，位于位示的第制位，位于位示的第i行、第行、第j列，则其相应的列，则其相应的盘块号应按下式计算盘块号应按下式计算b = n(i - 1) + jv修改位示图，修改位示图， 令令mapi,j=1Operating SystemOpera

12、ting SystemPage 142022-5-20q盘块的回收盘块的回收v将回收盘块的盘块号转换成位示图中的行号和列号。将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为转换公式为i = (b - 1) DIV n + 1j = (b - 1) MOD n + 1v修改位示图，修改位示图， 令令map i,j=0 （当（当“0”表示盘块空闲时）表示盘块空闲时）v如上例中，第如上例中，第16号物理块，可计算得号物理块，可计算得i = (16 - 1) DIV 16 + 1 = 1j = (16 - 1) MOD 16 + 1 = 16v同理，第同理，第17块可计算得块可计算得i =

13、(17 - 1) DIV 16 + 1 = 2j = (17 - 1) MOD 16 + 1 = 1 Operating SystemOperating SystemPage 152022-5-20q空闲表法和空闲链表法空闲表法和空闲链表法q位示图法位示图法q成组链接法成组链接法Operating SystemOperating SystemPage 162022-5-20q在大型文件系统中，空闲表或空闲链表太长，在在大型文件系统中，空闲表或空闲链表太长，在UNIX系统中，两种方法结合形成系统中，两种方法结合形成成组链接法成组链接法q空闲盘块的组织空闲盘块的组织v将将空闲表空闲表和和空闲链表空

14、闲链表结合形成的空闲盘块管理方结合形成的空闲盘块管理方法法v空闲盘块号栈空闲盘块号栈 用来存放当前可用的一组空闲盘块用来存放当前可用的一组空闲盘块号以及栈中尚有的空闲盘块号以及栈中尚有的空闲盘块数数Nv文件区中的所有空闲盘块被分成若干个组，如文件区中的所有空闲盘块被分成若干个组，如100块块/组组v将每组含的有盘块数和该组所有盘块号记入前一将每组含的有盘块数和该组所有盘块号记入前一组第一个盘块中组第一个盘块中v将第一组的空闲盘块数和所有盘块号记入空闲盘将第一组的空闲盘块数和所有盘块号记入空闲盘块号栈块号栈Operating SystemOperating SystemPage 172022-5

15、-20100400399301300100300299-202201299-100400399-20130110007999790179007899-78017999-7901空闲盘块号栈空闲盘块号栈S.free019899栈顶栈顶指针指针Operating SystemOperating SystemPage 182022-5-20q设每设每100盘块为盘块为1组，系统共组，系统共10000个盘块，从个盘块，从201至至7999用于文件区，则第用于文件区，则第1组为盘块号组为盘块号201-300，第，第2组为组为301-400，.，最后一组为，最后一组为7901-7999q每一组的盘块总数每

16、一组的盘块总数N和盘块号记入前一组的第一和盘块号记入前一组的第一个盘块个盘块S.free(0)S.free(99)q将第一组盘块总数和盘块号记入空闲盘块号栈将第一组盘块总数和盘块号记入空闲盘块号栈q最末一组的最末一组的S.free(0)为为“0”，表示空闲盘块链，表示空闲盘块链结束结束Operating SystemOperating SystemPage 192022-5-20q空闲盘块的分配与回收空闲盘块的分配与回收v分配分配检查空闲盘块号栈是否上锁，如未上锁，便检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，

17、然后将栈顶指针下移一格块分配给用户，然后将栈顶指针下移一格若该盘块号已是栈底，若该盘块号已是栈底， 即即S.free(0)，这是当，这是当前栈中最后一个可分配的盘块号前栈中最后一个可分配的盘块号调用磁盘读过程，将栈底盘块号所对应盘块调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去并把原栈底对应的盘块分配出去分分配一相应的缓冲区配一相应的缓冲区把栈中的空闲盘块数减把栈中的空闲盘块数减1并返回并返回Operating SystemOperating SystemPage 202022-5-20q空闲盘

18、块的分配与回收空闲盘块的分配与回收v回收回收将回收盘块的盘块号记入空闲盘块号栈的将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加顶部，并执行空闲盘块数加1操作操作当栈已满时，记入新回收的盘块中，再将当栈已满时，记入新回收的盘块中，再将其盘块号作为新栈其盘块号作为新栈底底Operating SystemOperating SystemPage 212022-5-20q文件和文件系统文件和文件系统q文件的逻辑结构文件的逻辑结构q外存分配方式外存分配方式q目录管理目录管理q文件存储空间的管理文件存储空间的管理q文件共享与文件保护文件共享与文件保护q数据一致性控制数据一致性控制Operat

19、ing SystemOperating SystemPage 222022-5-20q基于索引结点的共享方式基于索引结点的共享方式q利用符号链实现文件共享利用符号链实现文件共享q文件的保护机制文件的保护机制q磁盘容错技术磁盘容错技术Operating SystemOperating SystemPage 232022-5-20q 文件共享形式与目的文件共享形式与目的v定义：系统应允许多个用户共享同一份文件，定义：系统应允许多个用户共享同一份文件，在系统中只保留一份共享文件的备份在系统中只保留一份共享文件的备份v共享形式共享形式被多个用户使用，由存取权限控制被多个用户使用，由存取权限控制被多个程

20、序使用，但各用自己的读写指针被多个程序使用，但各用自己的读写指针被多个程序使用，但共享读写指针被多个程序使用，但共享读写指针多个用户用相同或不同的名字来访问同一多个用户用相同或不同的名字来访问同一文件文件v目的目的: :节省时间和存储空间，减少了用户工作节省时间和存储空间，减少了用户工作量；进程间通过文件交换信息量；进程间通过文件交换信息Operating SystemOperating SystemPage 242022-5-20Operating SystemOperating SystemPage 252022-5-20q文件共享的实现文件共享的实现v建立值班目录建立值班目录由系统目录实

21、现对文件的共享由系统目录实现对文件的共享用户通过全路径名共享地访问这些文件用户通过全路径名共享地访问这些文件v采用链访技术采用链访技术对要共享的文件进行连接对要共享的文件进行连接: : 通过通过“连接（连接（LinkLink）”命令，在用户自己命令，在用户自己的目录项中对要共享的文件建立起相应的的目录项中对要共享的文件建立起相应的表目，即建立两个文件的等价关系表目，即建立两个文件的等价关系Operating SystemOperating SystemPage 262022-5-20q基于索引结点共享基于索引结点共享v将诸如文件的物理地址和其它文件属性等将诸如文件的物理地址和其它文件属性等信息

22、放在索引结点中，在文件目录中只设信息放在索引结点中，在文件目录中只设置文件名及指向相应索引结点的指针，另置文件名及指向相应索引结点的指针，另外在索引结点中增加链接计数外在索引结点中增加链接计数count，表，表示共享的用户数，删除时必须示共享的用户数，删除时必须count=0，方可。方可。Operating SystemOperating SystemPage 272022-5-20Wang用户文件目录用户文件目录Test rLee用户文件目录用户文件目录Test rcount 2文件物理地址文件物理地址索引结点索引结点Test 基于索引结点的共享方式基于索引结点的共享方式 Operating

23、 SystemOperating SystemPage 282022-5-20C的目录的目录owner ccount 1链接前链接前C的目录的目录owner ccount 2链接后链接后B的目录的目录B的目录的目录owner ccount 1拥有者删除文件后拥有者删除文件后进程进程B链接前后的情况链接前后的情况 Operating SystemOperating SystemPage 292022-5-20q基于索引结点的共享方式基于索引结点的共享方式q利用符号链实现文件共享利用符号链实现文件共享q文件的保护机制文件的保护机制q磁盘容错技术磁盘容错技术Operating SystemOpera

24、ting SystemPage 302022-5-20q为使为使B能共享能共享C的一个文件的一个文件F，可以由系统创建一，可以由系统创建一个个LINK类型的新文件类型的新文件，也取名为，也取名为F，以实现，以实现B的的目录中与文件目录中与文件F的链接。在新文件中只包含被链的链接。在新文件中只包含被链接文件接文件F的路径名。这种链接方法称为的路径名。这种链接方法称为符号链接符号链接（Symbolic Linking）q在利用符号链方式实现文件共享时，在利用符号链方式实现文件共享时， 只是文件主只是文件主才拥有指向其才拥有指向其索引结点索引结点的指针；而共享该文件的的指针；而共享该文件的其他用户，

25、则只有该文件的路径名，并不拥有指其他用户，则只有该文件的路径名，并不拥有指向其索引结点的指针向其索引结点的指针q可用于计算机网络上共享文件可用于计算机网络上共享文件Operating SystemOperating SystemPage 312022-5-20q符号链实现文件共享优缺点符号链实现文件共享优缺点v优点：方便地链接任一文件（用路径名）优点：方便地链接任一文件（用路径名）v缺点：访问共享文件时开销大（多次读盘，缺点：访问共享文件时开销大（多次读盘，消费盘空间），每一共享文件都要增加一文消费盘空间），每一共享文件都要增加一文件名（因路径名各不相同件名（因路径名各不相同）Operatin

26、g SystemOperating SystemPage 322022-5-20q基于索引结点的共享方式基于索引结点的共享方式q利用符号链实现文件共享利用符号链实现文件共享q文件的保护机制文件的保护机制q磁盘容错技术磁盘容错技术Operating SystemOperating SystemPage 332022-5-20q文件保护用于提供安全性的特定的操作系统机文件保护用于提供安全性的特定的操作系统机制制q对拥有权限的用户，应该让其进行相应操作，对拥有权限的用户，应该让其进行相应操作，否则，应禁止否则，应禁止q防止其他用户冒充对文件进行操作防止其他用户冒充对文件进行操作q实现实现v用户验证用

27、户验证v存取控制存取控制Operating SystemOperating SystemPage 342022-5-20q基于索引结点的共享方式基于索引结点的共享方式q利用符号链实现文件共享利用符号链实现文件共享q文件的保护机制文件的保护机制q磁盘容错技术磁盘容错技术Operating SystemOperating SystemPage 352022-5-20q影响文件安全的主要因素影响文件安全的主要因素v人为因素人为因素v系统因素系统因素v自然因素自然因素q可采取的措施可采取的措施v通过通过存取控制存取控制机制来防止由人为因素所造成机制来防止由人为因素所造成的文件不安全性的文件不安全性v通

28、过通过磁盘容错技术磁盘容错技术，来防止由磁盘部分的故，来防止由磁盘部分的故障所造成的文件不安全性障所造成的文件不安全性v通过通过“后备系统后备系统”来防止由自然因素所造成来防止由自然因素所造成的不安全性的不安全性Operating SystemOperating SystemPage 362022-5-20q容错技术容错技术是通过在系统中是通过在系统中设置冗余设置冗余部件的办法来部件的办法来提高系统可靠性的一种技术提高系统可靠性的一种技术q磁盘容错技术也称为磁盘容错技术也称为系统容错技术（系统容错技术（System Fault Tolerance, SFT），是通过增加冗余的磁，是通过增加冗余的磁盘驱动器、磁盘控制器等方法来提高磁盘系统可盘驱动器、磁盘控制器等方法来提高磁盘系统可靠性的一种技术靠性的一种技术qSFT的级别的级别vSFT-I 低级磁盘容错技术低级磁盘容错技术，防止因磁盘表面发，防止因磁盘表面发生缺陷所引起的数据丢失生缺陷所引起的数