文件存储空间管理

文件存储管理 - 图1

存储空间的划分和初始化

安装Windows操作系统的时候，一个必经步骤是———为磁盘分区(C: 盘、D: 盘、E: 盘等)

存储空间的划分:将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)

文件存储管理 - 图2

空闲表法

适用于连续分配方式

文件存储管理 - 图3

如何分配磁盘块:与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

如何回收磁盘块:与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况

回收区的前后都没有相邻空闲区;
回收区的前后都是空闲区;
回收区前面是空闲区;
回收区后面是空闲区。

总之，回收时需要注意表项的合并问题。

空闲链表法

文件存储管理 - 图4

如下图所示：

文件存储管理 - 图5

空闲盘块链

文件存储管理 - 图6

操作系统保存着链头、链尾指针。

如何分配: 若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

如何回收: 回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。

空闲盘区链

文件存储管理 - 图7

操作系统保存着链头、链尾指针。

如何分配:若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区,分配给文件。

若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

如何回收:若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

位示图法

连续分配、离散分配都适用

文件存储管理 - 图8

位示图:每个二进制位对应一一个盘块。在本例中，“0” 代表盘块空闲,“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用(字号，位号)对应一个盘块号。当然有的题目中也描述为(行号，列号)

重要重要重要:要能自己推出盘块号与(字号位号)相互转换的公式。

注意题目条件:盘块号、字号、位号到底是从0开始还是从1开始。如本例中盘块号、字号、位号从0开始，若n表示字长，则…

(字号,位号)=(i, j)的二进制位对应的盘块号b=ni+j

b号盘块对应的字号i=b/n,位号i= b%n

如何分配:

若文件需要K个块

①顺序扫描位示图，找到K个相邻或不相邻的“0”;
②根据字号、位号算出对应的盘块号，将相应盘块分配给文件;
③将相应位设置为“1”。

如何回收:

①根据回收的盘块号计算出对应的字号、位号;
②将相应二进制位设为“0”

成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

文件存储管理 - 图9

文件存储管理 - 图10

如何分配?

Eg:需要1个空闲块

检查第一个分组的块数是否足够。1<100，因此是足够的。
分配第一个分组中的1个空闲块，并修改相应数据

查找后分配最后一个201块。

Eg:需要100个空闲块

检查第一个分组的块数是否足够。100=100，是足够的。
分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超
级块中。

第一组块全部分配出去之后，但300块连接着后面的块，所以不能直接分配出去，而是需要复制后面一组的块在超级块中。

如何回收？

分组没满
分组满了

如何回收?
Eg:假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。需要将超级块中的数据复制到
新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。也就是合并再加入。

总结

文件存储管理 - 图17

文件的基本操作

文件存储管理 - 图18

文件创建

进行Create系统调用时，需要提供的几个主要参数:

所需的外存空间大小(如:一个盘块，即1KB)
文件存放路径(D:/Demo)

文件名(这个地方默认为“新建文本文档.txt” )

操作系统在处理Create系统调用时，主要做了两件事:

在外存中找到文件所需的空间(结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间)
根据文件存放路径的信息找到该目录对应的目录文件(此处就是D:/Demo目录)，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

删除文件

进行Delete系统调用时，需要提供的几个主要参数:

文件存放路径(“D:/Demo ”)
文件名(“test.txt” )

操作系统在处理Delete系统调用时，主要做了几件事:

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。(回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理)
从目录表中删除文件对应的目录项。

打开文件

在很多操作系统中，在对文件进行操作之前，要求用户先使用open系统调用“打开文件”，需要提供的几个主要参数:

文件存放路径(“D:/Demo” )
文件名(“test.txt” )
要对文件的操作类型(如: r只读; .rw读写等)

操作系统在处理open系统调用时，主要做了几件事:

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。

进程和系统的打开文件表

可以方便实现某些文件管理的功能。例如:在Windows系统中，我们尝试删除某个txt文件，如果此时该文件已被某个“记事本”

进程打开，则系统会提示我们“暂时无法删除该文件”。其实系统在背后做的事就是先检查了系统打开文件表，确认此时是否有进程正在用该文件。

文件存储管理 - 图19

读写指针：记录读/写操作进行到的位置。

访问权限：如果打开文件时声明的是**只读**，则该进程不能对文件进行写操作。

关闭文件

进程使用完文件后，要关闭文件

操作系统在处理Close系统调用时，主要做了几件事：

将进程的打开文件表相应表项删除
回收分配给该文件的内存空间等资源
系统打开文件表的打开计数器count减1，若count=0，则删除对应表项。

读文件

进程使用read系统调用完成写操作。需要指明是哪个文件(在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)

还需要指明要读入多少数据(如:读入1KB)。
指明读入的数据要放在内存中的什么位置。
操作系统在处理read系统调用时会从读指针指向的外存中,将用户指定大小的数据读入用户指定的内存区域中。

文件共享

文件存储管理 - 图20

注意:

多个用户共享同一个文件，意味着系统中只有一份文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

如果是多个用户都复制了同一个文件，那么系统中会有好几份文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

硬链接

索引结点中设置一个链接计数变量count,用于表示链接到本索引结点上的用户目录项数。

文件存储管理 - 图21

软链接

文件存储管理 - 图22

当User3访问ccc 时，操作系统判断文件ccc属于Link类型文件，于是会根据其中记录的路径层层查找目录，最终找到User1的目录表中的aaa 表项，于是就找到了文件1的索引结点。

文件1删除，但是文件2依然存在，只是通过C:/User1/aaa这个路径已经找不到文件1了。

软链接就是Windows的快捷方式。