操作系统（13）-----文件管理1:https://developer.aliyun.com/article/1511174
索引顺序文件的索引项也不需要按关键字顺序排列，这样可以极大地方便新表项的插入。并且索引顺序表的表项也少了许多。
所以索引文件是定长记录的顺序结构的顺序文件，而索引顺序文件是定长记录的串结构的顺序文件。
用这种策略确实可以让索引表“瘦身”，但是是否会出现不定长记录的顺序文件检索速度慢的问题呢?
一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找(这里指的并不是定长记录、顺序结构的顺序文件)，平均须查找 5000 个记录。
若采用索引顺序文件结构，可把10000个记录分为10000−−−−−√10000=100 组，每组 100个记录。则需要先顺序查找索引表找到分组(共100个分组，因此索引表长度为100，平均需要查50次)，找到分组后，再在分组中顺序查找记录(每个分组100个记录，因此平均需要查50次)。可见，采用索引顺序文件结构后，平均查找次数减少为 50+50=100 次。
同理，若文件共有 10^6个记录，则可分为1000个分组，每个分组1000个记录。根据关键字检索一个记录平均需要查找 500+500=1000次。这个查找次数依然很多，如何解决呢?
多级索引顺序文件：
为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含 106个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项(即10000个定长记录)，再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表顶。
所以顶级索引表中有100个表项，低级索引表每个索引表也有100个表项，每个表项对应多个分组，每个分组中又会对应100个记录。此时，检索一个记录平均需要查找
50+50+50=150 次
四.文件之间应该怎样组织起来
下图的目录就是“文件夹”，用户可以自己创建一层一层的目录，各层目录中存放相应的文件。系统中的各个文件就通过一层一层的目录合理有序的组织起来了。
目录其实也是一种特殊的有结构文件（由记录组成），那么如何实现目录呢？、
五.文件的基本操作
文件的基本操作，也就是操作系统可以向上提供的功能：
1.创建文件（create系统调用）
可以“创建文件”，(点击新建后，图形化交互进程在背后调用了“create 系统调用”)
进行 Create 系统调用时，需要提供的几个主要参数：
1.所需的外存空间大小(如：一个盘块，即1KB)
2.文件存放路径(“D:/Demo”)
3.文件名(这个地方默认为"新建文本文档.txt"）
操作系统在处理 Create 系统调用时，主要做了两件事:
1.在外存中找到文件所需的空间(结合空闲链表法、位示图、成组链接法等管理策略，找到空闲空间)
2.根据文件存放路径的信息找到该目录对应的目录文件(此处就是D:/Demo目录)，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
2.删除文件（delete系统调用）
可以“删除文件”(点了“删除”之后，图形化交互进程通过操作系统提供的“删除文件”功能，即 delete 系统调用，将文件数据从外存中删除)
进行 Delete 系统调用时，需要提供的几个主要参数：
1.文件存放路径(“D:/Demo”
2.文件名(“test.txt”)
操作系统在处理 Delete 系统调用时，主要做了几件事:
1.根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
2.根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。(回收磁盘块时，根据空闲表法、空闲链表法位图法等管理策略的不同，需要做不同的处理)
3.从目录表中删除文件对应的目录项。
3.读文件（read系统调用）
可以“读文件”，将文件数据读入内存，才能让CPU处理(双击后，“记事本”应用程序通过操作系统提供的“读文件”功能，即 read 系统调用，将文件数据从外存读入内存，并显示在屏幕上)
进行 read 系统调用时：
1.需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)。
2.还需要指明要读入多少数据(如：读入1KB)。
3.指明读入的数据要放在内存中的什么位置。
操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
4.写文件（write系统调用）
可以“写文件”，将更改过的文件数据写回外存(我们在“记事本”应用程序中编辑文件内容，点击“保存”后，“记事本”应用程序通过操作系统提供的“写文件”功能，即 write 系统调用,将文件数据从内存写回外存)
进行 write 系统调用时：
1.需要指明是哪个文件(在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)
2.还需要指明要写出多少数据(如:写出1KB)
3.写回外存的数据放在内存中的什么位置
操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。
注：对于"读/写文件"用“文件描述符”(即这一文件在内存中的打开文件表的索引号)即可指明文件，不再需要用到“文件名。
5.打开文件（open系统调用）
可以“打开文件”（读/写文件之前，需要“打开文件”，即open系统调用）这和用户双击触发的read系统调用不同。
只有读文件时才会将文件数据从外存读入内存，继续看就知道了。
进行 open 系统调用时，需要提供的几个主要参数：
1.文件存放路径(“D:/Demo”)
2.文件名(“test.txt”)
3.要对文件的操作类型(如:r只读；rw 读写等)
操作系统在处理open系统调用时，主要做了几件事：
1.根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，同时不同用户对文件的操作权限不同，这些信息记录在目录项中，系统会根据目录项检查该用户是否有指定的操作权限。
若用户有指定的操作权限，则将目录项复制到内存中的“打开文件表”中（打开文件时并不会把文件数据直接读入内存，而是将目录项复制到内存的“打开文件表”）。系统会将文件的索引号（这个“索引号”，也称“文件描述符”）返回给用户。之后用户使用打开文件表的索引号来指明要操作的文件，即之后用户进程再操作文件就不需要每次都重新查目录了，这样可以加快文件的访问速度。
注：这里有两种"打开文件表"
1.系统的打开文件表（整个系统只有一张），这个表中记录了所有被进程使用的文件。
2.另外，每个进程都有自己的一张"打开文件表"，这个表中记录了每个进程打开的文件。这一表中记录了系统索引号。这一索引号对应了系统"打开文件表"的编号。
•系统的打开文件表中记录了"打开计数器"，记录此时有多少个进程打开了此文件。
•用户进程的打开文件表中记录了"读写指针"，记录了该进程对文件的读/写操作进行到的位置。
•用户进程的打开文件表中记录了"访问权限"，如果打开文件时声明的是只读”，则该进程不能对文件进行写操作。
不同进程对同一文件的读写指针（读/写进行到的位置）不同，访问权限不同。
为什么需要在系统中设置打开文件表的总表？
可以方便实现某些文件管理的功能。例如：在Windows系统中，我们尝试删除某个txt文件，如果此时该文件已被某个“记事本”进程打开，则系统会提示我们“暂时无法删除该文件”。其实系统在背后做的事就是先检查了系统打开文件表，确认此时是否有进程正在使用该文件。
读文件与打开文件的联系与区别：
联系：
都会使用到内存中的“文件打开表”，系统会将文件的索引号（这个“索引号”，也称“文件描述符”）返回给用户。之后用户使用打开文件表的索引号来指明要操作的文件，即之后用户进程再操作文件就不需要每次都重新查目录了，这样可以加快文件的访问速度。
区别：
open（打开文件）不会把文件数据直接读入内存，而是将目录项复制到内存的“打开文件表”）
read（读文件）会将文件数据从外存读入内存。
6.关闭文件（close系统调用）
6.可以“关闭”文件（读/写文件结束之后，需要“关闭文件”，即close系统调用）这和用户点击关闭按钮触发的delete系统调用不同。
操作系统在处理Close系统调用时，主要做了几件事：
1.将进程的打开文件表相应表项删除。
2.回收分配给该文件的内存空间等资源。
3.系统打开文件表的打开计数器count减1，若count=0，则删除对应表项。例如，在打开文件示例中的打开计数器由2变为1。
注：可用几个基本操作完成更复杂的操作，比如:“复制文件”：先创建一个新的空文件，再把源文件读入内存，再将内存中的数据写到新文件中。
六.文件的物理结构
1.对非空闲磁盘块的管理
外存与内存相同，外存也是由一个个存储单元组成的，每个存储单元可以存储一定量的数据(如 1B)。每个存储单元对应一个物理地址。
类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”。每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址（ 如本例中，一块包含 2^10 个地址，即 1KB)。
同样类似的是，在内存管理中，进程的逻辑地址空间被分为一个一个页面，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。
于是文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式。操作系统同样需要将逻辑地址转换为外存的物理地址(物理块号，块内地址)的形式（该物理地址用户是不可知的，用户只能通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射）。块内地址的位数取决于磁盘块的大小。（例如这里，一块物理块包含2^10个地址，那么块内地址的位数为10位）。
注：很多操作系统中，磁盘块的大小与内存块、页面的大小相同，那么内存与磁盘之间的数据交换(即读/写操作、磁盘I/O)都是以“块”为单位进行的。即每次读入一块，或每次写出一块。
外存被分为一个个磁盘块，那么该如何存放文件数据呢？这就是我们要探讨的文件的物理结构，即文件分配方式
（1）连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。也就是逻辑相邻的块在物理上也必须相邻。并且依然要保持块间的相对顺序。
用户通过逻辑地址来操作自己的文件，操作系统如何实现从逻辑地址到物理地址的映射?
逻辑地址(逻辑块号，块内地址)→物理地址(物理块号，块内地址)。只需转换块号就行，块内地址保持不变就行了。为了实现地址映射，文件目录表记录了起始块号和长度（占用多少个块），例如"aaa"文件起始块号为4，占用了连续的3个块。
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项(FCB)，通过FCB就得到起始块号，用该起始块号加上逻辑块号
物理块号=起始块号+逻辑块号
例如上图，想要访问"aaa"文件的逻辑块号2，再加上起始块号4，得到物理块号=2+4=6
当然，还需要检查用户提供的逻辑块号是否合法(逻辑块号≥≥长度就不合法)
所以，只要用户提供逻辑块号，可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问(即随机访问)
顺序访问，即，想要访问"aaa"的逻辑块号2，就必须先访问逻辑块号0，1
直接访问，即，想要访问"aaa"的逻辑块号2，不需要访问0，1
连续分配支持顺序访问和直接访问(即随机访问)，这是连续分配的一大优点，还有就是：
读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
由于连续分配的磁盘块在物理上是相邻的，连续分配的文件在顺序读/写时速度最快。
连续分配的缺点：
1.物理上采用连续分配的文件不方便拓展
如下图所示，黄色区域表示物理上连续分配的文件A占用了连续的三个块，橙色区域为其他文件已经占用的磁盘块，绿色区域为空闲磁盘块。
若此时文件A要拓展，需要再增加一个磁盘块(总共需要连续的4个磁盘块)。由于采用连续结构，因此文件A占用的磁盘块必须是连续的。而文件A后面相邻的块已经被其他文件占有，若要拓展文件A，那么必须把文件A迁移到有连续4个空闲磁盘块的区域中。而数据迁移需要很大开销。
所以，物理上采用连续分配的文件不方便拓展。
2.物理上采用连续分配的文件存储空间利用率低
如下图所示，橙色区域为非空闲块，绿色区域为空闲磁盘块。若此时创建的新文件大小为3个块，而连续分配需要连续的3个磁盘块，那么无法为其分配足够的存储空间。
所以物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片。可以用紧凑来处理碎片，但是需要耗费很大的时间代价。
（2）链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
隐式链接:
目录中记录了文件存放的起始块号和结束块号。当然，也可以增加一个字段来表示文件的长度。除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的。
如何实现逻辑块号到物理块号?
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)，从目录项中找到起始块号(即0号块)，将0号逻辑块读入内存，只有将0号块读入内存后，才能得到0号块指向1号块的数据，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置.………..以此类推。
因此，读入i号逻辑块，总共需要i+1次磁盘I/O。
所以，采用链式分配(隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。
采用隐式链接，是否方便拓展文件？
由于文件的块可以离散存放，若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的FCB。
例如下图，要新增8号块，那么将8号块放到磁盘块链尾。
所以，采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题外存利用率高。
总结：
隐式链接---除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。
显式链接:
把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表(FAT, File Allgcation Table)
假设某个新创建的文件“aaa”依次存放在磁盘块2-->5-->0-->1,那么在"aaa"这一文件的FCB（目录项）中，需要记录这一文件存放的起始块号，目录中只需记录文件的起始块号。
而FAT（文件分配表）中，会显式记录文件各个块的链接关系，例如0号物理块下一块为5号块，1号块下一块设置为特殊的值，例如-1，表示1号块是文件的最后一块……
假设某个新创建的文件“bbb”依次存放在磁盘块4-->23-->3
注意：一个磁盘仅设置一张FAT，每个文件都统一存放在这一个FAT表中。开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。
采用显式链接，如何实现文件的逻辑块号到物理块号的转变?
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)，从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT往后找到i号逻辑块对应的物理块号。
例如，访问文件"aaa"，0号逻辑块对应的物理块号为2号物理块，2号物理块对应的下一块是5号物理块（1号逻辑块），依次类推……
逻辑块号转换成物理块号的过程不需要读磁盘操作。
所以，采用链式分配(显式链接)方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块，可以直接通过FAT表查询i号逻辑块存放的地址），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。
显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。
总结：
显式链接---把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT，FileAllocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间。
注：考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配。
（3）索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表--建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
目录中需要记录文件的索引块是几号磁盘块。
假设某个新创建的文件“aaa”的数据依次存放在磁盘块2-->5-->13-->9。
7号磁盘块作为“aaa”文件的索引块,索引块中保存了索引表的内容。
如图所示，“aaa”文件的索引表存放在7号磁盘块中，而实际数据存放在2，5，13，9这些磁盘块中。
注：在显式链接的链式分配方式中，文件分配表FA 是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。
可以用固定的长度表示物理块号(如：假设磁盘总容量为1TB=2^40B，磁盘块大小为1KB，则共有 2^30个磁盘块，则可用4B(4个字节，4*8的32个磁盘块)表示磁盘块号)，因此，索引表中的“逻辑块号”可以是隐含的。
所以我们可以看到，索引表的表项每一行占有4个字节，所以只要知道索引表的起始位置，再根据逻辑块号，就可以知道该逻辑块号对应的物理块号的地址。
如何实现文件的逻辑块号到物理块号的转换?
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB),从中找到这一文件的索引块，再从这一索引块中读出索引表，将索引表从外存读入内存，并查找索引表即可知 i号逻辑块在外存中的存放位置。 而不需要先访问0~i-1号块。
可见，索引分配方式可以支持随机访问。
文件拓展也很容易实现(只需要给文件分配一个空闲块，并增加一个索引表项即可)
但是索引表需要占用一定的存储空间
若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放 256 个索引项。
如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题?有三种方案①链接方案，②多层索引，③混合索引
①链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
我们为文件分配多个索引块，并且在每个索引块中分配一定空间用于指向下一个索引块， 若采用链接方式，索引表中只需要记录第一个索引块的块号即可。
如下图， 若想找到逻辑块号为256对应的物理块号，由于各个索引块中是用链接的方式连接起来，为了找到第二个索引块的块号，需要把第一个索引块读入内存，再根据第一个索引块中的指针，找到第二个索引块的块号，把第二个索引块读入内存，才能得到逻辑块号256对应的物理块号。
假设磁盘块大小为1KB、一个索引表项占4B，则一个磁盘块只能存放256个索引项。若一个文件大小为 256*256KB=65,536 KB=64MB
该文件共有 256*256个块，也就对应256*256个索引项，也就需要256个索引块来存储256个索引表，每个索引表对应256个索引项，这些索引块用链接方案连起来。
若想要访问文件的最后一个逻辑块，就必须找到最后一个索引块(第256个索引块)，而各个索引块之间是用指针链接起来的，因此必须先顺序地读入前255个索引块。
这一方案显然很低效，所以提出了多层索引方案。
操作系统（13）-----文件管理3：https://developer.aliyun.com/article/1511186
