File management: the physical structure of files

1.文件的物理结构

逻辑结构：在用户看来,文件内部的数据是如何组织起来的
物理结构：在OS看来,文件的数据是如何放在外存（磁盘）中的

OSIdle and non-idle are required（已存数据）of disk blocks for management
Management of non-free blocks：文件分配方式
Management of free blocks：文件存储空间管理

1.1 文件分配方式

How file data is stored in external storage（磁盘）中
下图来自王道考研操作系统

1.1.1 连续分配

下图来自程序员cxuan

下图来自小林coding

下图来自王道考研操作系统

1.1.2 链接分配

1.1.2.1 隐式链接

下图来自王道考研操作系统

When searching for the next disk block, it is necessary to find the next disk block according to the pointer in the disk block,This requires moving the heads.This form of work makes the access speed not very fast.Implicit linkage supports sequential access,但不支持随机访问

下图来自程序员cxuan

1.1.2.2 显式链接

下图来自王道考研操作系统

文件分配表在内存中,从目录项中找到起始块号,If the logical block number given by the user is valid（The logical block number is greater than0）,则查找FATThen the physical block number corresponding to the logical block number can be obtained,The query process does not need to read the disk.支持随机访问（Get the physical block number to be accessed directly,There is no need to work backwards from the first physical block number of the file）,In fact, sequential access is also supported（从前往后找）

下图来自程序员cxuan
FAT文件分配表

1.1.3 索引分配

FAT需要占用较大的内存空间,在打开某个文件时,Just transfer the disk block number corresponding to the file into memory,完全没有必要将整个FAT调入内存.为此,We lump together all the disk block numbers for each file to form the index block/表（放在磁盘中）

下图来自王道考研操作系统

If a disk block can be stored256个索引项,But one file has more than one index entry256what plan should we adopt？

方案一：链接方案
将多个索引块/link table

To access the last logical block of the file,Then you have to sequentially access all the previous logical blocks,显然效率很低.This leads to a multi-level index

方案二：多层索引

There are secondary index tables in the second layer256个,Each secondary index table corresponds again256个,所以为256*256

The result of the division is the number of logical blocks,The result of the remainder is the number of table entries in the logical block

If it is a two-level index,is required to access the target data block3次磁盘I/O
If it is a three-level index,is required to access the target data block4次磁盘I/O

如果一个文件很小,It is still needed after using two layers of indexes3次读磁盘

方案三：混合索引（Different indexing schemes can be established for files of different sizes）
既包含直接地址索引（直接指向数据块）、又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）

The picture below is from my notesLinux文件系统

下图来自王道考研操作系统