文件管理 File Management.

Presentation on theme: "文件管理 File Management."— Presentation transcript:

1 文件管理 File Management

2 文件 Files 用于数据的输入和输出 应用程序的输出可永久的存储在文件中

3 文件中使用的术语 Field/Item（字段/数据项） Record（记录） basic element of data（数据的基本单位）
contains a single value（存储一个基本信息） characterized by its length and data type（通过长度及类型来标识） Record（记录） collection of related fields（相关字段的集合） treated as a unit（作为一个单元） Example: employee record

4 文件中使用的术语 File Database collection of similar records（相同类型记录集合）
treated as a single entity（作为一个实体） have unique file names（有文件名） may restrict access（可以限制存取权限） Database collection of related data（相关数据集合） relationships exist among elements（元素之间存在关系）

5 文件的类型 按用途 按使用情况 按信息流向 按文件的保护方式 系统文件 只读文件 库文件(*.DLL动态链接库) 读写文件
用户文件( *.doc) 按使用情况 临时文件( *.tmp ~xxx.doc) 档案文件 永久文件 按信息流向 输入文件 输出文件 输入/输出文件 按文件的保护方式 只读文件 读写文件 不保护文件 按Linux中文件的组织形式 普通文件 目录文件 特别文件(如终端/打印机/网络..)

6 文件的命名 短文件名格式（8.3格式）fdisk.exe 长文件名格式 < 255字符 是否区分大小写 Linux 区分大小写
Windows 不区分

7 文件操作 常规文件操作 Create 创建文件 Delete 删除文件 Open 打开文件 Close 关闭文件
Retrieve_All 取全部内容 Retrieve_One 取一条记录 Retrieve_Next 取下一条记录 Retrieve_Previous 取前一记录 Insert_One 插入一条记录 Delete_One 删除一条记录 Update_One 更新一条记录 Seek 指定读/写位置 C语言中文件操作函数 fopen ( ) fclose ( ) fread ( ) fwrite ( ) fseek ( ) feof ( ) fgetc ( ) fgets ( ) fprintf ( ) fputc ( ) fputs ( ) fscanf ( ) ftell ( ) 取文件当前位置 rewind ( ) 置于文件头

8 File Management System
提供用户对文件的存取服务 用户无须开发文件管理软件 为用户提供的其它功能 创建、读写、删除文件 指定其它用户对自己文件的访问权限 受控访问其它用户的文件 重新构建文件 备份文件

9 File System Software Architecture 文件系统的结构
User Program 堆文件 顺序文件 索引顺序文件 索引文件 直接文件 逻辑文件 Pile Sequential Indexed Sequential Indexed Hashed Logical I/O Basic I/O Supervisor(管理程序) Basic File System Disk Device Driver Tape Device Driver

10 文件管理的功能 目录管理 文件内容的组织 文件存储空间的管理 文件操作 文件的共享、保护和保密

11 文件组织的标准 Rapid access（快速存取） Ease of update（易于修改）
needed when accessing a single record not needed for batch mode Ease of update（易于修改） file on CD-ROM will not be updated, so this is not a concern Economy of storage（存储的经济性） should be minimum redundancy in the data（数据最小冗余） redundancy can be used to speed access such as an index（索引会增加冗余但为提高存取速度） Simple maintenance（易于维护） Reliability （可靠）

12 File Organization(文件的逻辑组织)
1、The Pile（堆文件） data are collected in the order they arrive（数据按到达次序堆放） purpose is to accumulate a mass of data and save it（积累数据并保存） records may have different fields（记录即每次获得的数据可能具有不同的结构） no structure（文件没有统计的记录结构） record access is by exhaustive search（信息查找需要遍历） 记录 1 记录2 记录3 记录4 记录5 记录 6

13 File Organization文件的逻辑组织
2、The Sequential File（顺序文件） fixed format used for records(统一记录结构) records are the same length all fields the same (order and length) field names and lengths are attributes of the file one field is the key filed（主键） uniquely identifies the record（唯一标识记录） records are stored in key sequence(按主键排序) new records are placed in a log file or transaction file(先临时放在一个日志文件中） batch update is performed to merge the log file with the master file（周期性地将日志文件中的内容并入主文件中） Record 1 Record 2 Record 3 key1 key2 key3

14 File Organization文件的逻辑组织
3、Indexed Sequential File（索引顺序文件） index provides a lookup capability to quickly reach the vicinity of the desired record（利用索引快速定位到记录） contains key field and a pointer to the main file（索引表存放一个主键值及相应记录位置） index is searched to find highest key value that is equal or less than the desired key value（在索引表中找到最大的<=所要查找的主键值的索引项） search continues in the main file at the location indicated by the pointer（从此处开始往下找）

15 File Organization文件的逻辑组织
Indexed Sequential File （索引顺序文件） new records are added to an overflow file record in main file that precedes it is updated to contain a pointer to the new record the overflow is merged with the main file during a batch update multiple indexes for the same key field can be set up to increase efficiency Index Levels 1 2 n Main File Overflow File

16 File Organization文件的逻辑组织
Comparison of sequential and indexed sequential顺序文件与索引顺序文件的比较 Example: a file contains 1 million records On average 500,00 accesses are required to find a record in a sequential file If an index contains 1000 entries, it will take on average 500 accesses to find the key, followed by 500 accesses in the main file. Now on average it is 1000 accesses

17 File Organization文件的逻辑组织
4、Indexed File（索引文件） uses multiple indexes for different key fields 为不同的关键字域建立索引 may contain an exhaustive index that contains one entry for every record in the main file(穷举索引：所有记录对应一索引项) may contain a partial index（部分索引） Exhaustive Index Exhaustive Index Partial Index

18 File Organization文件的逻辑组织
5、The Direct, or Hashed, File（直接文件） directly access a block at a known address key field required for each record Key 关键字 f Hash Function 哈希函数 Primary File 主文件 Overflow File 溢出文件

19 File Organization文件的逻辑组织
6、分区文件 压缩文件.zip .rar 函数库.lib Part A Part B Part C 索引区 Part A Part C 文件区 Part B

20 File Directories文件目录 Contains information about files 包含文件的信息
attributes 文件属性 location 存储位置 ownership 所有者关系 Directory itself is a file owned by the operating system 目录本身是操作系统拥有的一个文件 Provides mapping between file names and the files themselves提供文件名与文件内容间的映射关系 FCB文件控制块

21 Simple Structure for a Directory 简单的目录结构
List of entries, one for each file 文件入口列表，每个文件一项 Sequential file with the name of the file serving as the key 文件名作为关键字顺序存放 Forces user to be careful not to use the same name for two different files 用户应避免不同文件取相同名称

22 Two-level Scheme for a Directory 二级目录结构
One directory for each user and a master directory 有一个主目录，每一用户对应有一个子目录 Master directory contains entry for each user 主目录包含每一用户目录的入口 provides address and access control information 提供入地址及存取控制信息 Each user directory is a simple list of files for that user 用户子目录为一简单文件列表 Still provides no help in structuring collections of files 仍没有提供文件的结构化管理

23 Hierarchical, or Tree-Structured Directory 多级目录/树形目录结构
Master directory with user directories underneath it 主目录下有用户目录 Each user directory may have subdirectories and files as entries 每一用户目录可包含文件或下一级子目录 Files can be located by following a path from the root, or master, directory down various branches this is the pathname for the file 文件路径 Can have several files with the same file name as long as they have unique path names不同目录可有同名文件 Current directory is the working directory当前工作目录 Files are referenced relative to the working directory 相对路径 ../Help/index.htm

24 Pathname: /User B/Word/Unit A/ABC
Master Directory System User A User B User C Directory User B Directory Draw Word Directory Word Unit A Directory Draw ABC Directory Unit A File Pathname: /User B/Word/Unit A/ABC

25 目录操作 DOS系统命令 Linux系统命令 md mkdir 创建目录 rd rmdir 删除目录 dir ls 显示目录 cd cd
pwd 创建目录 删除目录 显示目录 改变当前目录 建立目录链接 删除链接 显示当前路径

26 File Sharing文件共享 Way to control access to a particular file
Users or groups of users are granted certain access rights to a file

27 Access Rights 存取权限 None 无 Knowledge 知道 Execution 执行 Reading 读
user may not know of the existence of the file user is not allowed to read the user directory that includes the file Knowledge 知道 user can only determine that the file exists and who its owner is Execution 执行 the user can load and execute a program but cannot copy it Reading 读 the user can read the file for any purpose, including copying and execution Appending 增补/追加 the user can add data to the file but cannot modify or delete any of the file contents

28 Access Rights Updating 更新 Deletion 删除 Owners 文件所有者
the user can modify, deleted, and add to the file’s data. This includes creating the file, rewriting it, and removing all or part of the data Changing protection user can change access rights granted to other users Deletion 删除 user can delete the file Owners 文件所有者 has all rights previously listed may grant rights to others using the following classes of users specific user user groups all for public files

29 Simultaneous Access 文件的同时存取
User may lock entire file when it is to be updated 更新时锁定整个文件 User may lock the individual records during the update 更新时锁定个别记录 Mutual exclusion and deadlock are issues for shared access 文件共享引起互斥和死锁问题

30 Record Blocking Methods块记录方式 - Fixed Blocking块大小固定
Track 2 R6 R7 R8 Data Waste due to record fit to block size Gaps due to hardware design Waste due to block size constraint from fixed record size Waste due to block fit to track size

31 Record Blocking Methods - Variable Blocking:Spanned可变大小,可跨跃
Track 1 Track 2 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Data Gaps due to hardware design Waste due to block fit to track size Waste due to record fit to block size Waste due to block size constraint from fixed record size

32 Record Blocking Methods - Variable Blocking:UnSpanned不可跨跃
Track 1 Track 2 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 Data Gaps due to hardware design Waste due to block fit to track size Waste due to record fit to block size Waste due to block size constraint from fixed record size

33 Portion Size 块大小 Contiguity of space increases performance 大块可提高系统性能
Large number of small portions increases the size of tables needed大量的小块需要增大分配表的容量 Fixed-size simplifies the reallocation of space 固定大小可简化空间的分配 Variable-size minimizes waste of unused storage 可变大小可减小空间浪费

34 文件分配方式 Contiguous allocation（连续分配,位图法）
single set of blocks is allocated to a file at the time of creation（文件只被分配在一个区域） only a single entry in the file allocation table starting block and length of the file Fragmentation will occur(磁盘上会产生碎块) Will become difficult to find contiguous blocks of sufficient length

35 Contiguous File Allocation 连续分配
File Allocation Table FileA File Name Start Block Length 1 2 3 4 FileA 2 3 FileB 9 5 5 6 7 8 9 FileC 18 8 FileB FileD 30 2 10 11 12 13 14 FileE 26 3 15 16 17 18 19 FileC 20 21 22 23 24 FileE 25 26 27 28 29 FileD 30 31 32 33 34

36 文件分配方式 Chained allocation(链式分配)
allocation on basis of individual block each block contains a pointer to the next block in the chain only single entry in the file allocation table starting block and length of file No fragmentation(分裂) Any free block can be added to the chain No accommodation(预留) of the principle of locality

37 Chained File Allocation 链式分配
File Allocation Table FileB File Name Start Block Length 1 2 3 4 ... ... ... FileB 1 5 5 6 7 8 9 ... ... ... 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

38 文件分配方式 Indexed allocation(索引分配)
file allocation table contains a separate one-level index for each file the index has one entry for each portion allocated to the file the file allocation table contains block number for the index

39 Indexed Allocation with Block Portions
File Allocation Table FileB File Name Index Block 1 2 3 4 ... ... 5 6 7 8 9 FileB 24 ... ... 10 11 12 13 14 15 16 17 18 19 1 8 20 21 22 23 24 3 14 25 26 27 28 29 28 30 31 32 33 34

40 Indexed Allocation - Variable Length Portions
File Allocation Table FileB File Name Index Block 1 2 3 4 ... ... 5 6 7 8 9 FileC 24 ... ... 10 11 12 13 14 15 16 17 18 19 Start Block Length 20 21 22 23 24 1 3 28 4 14 1 25 26 27 28 29 30 31 32 33 34

41 FAT32 MBR主引导扇区 0面0磁道1扇区 MBR (first sector) layout 主引导扇区 分区表项的结构

42 FAT32 每一个分区的结构 8.3格式的文件目录项结构

43 DOS操作系统FAT32的链式分配 FAT文件分配表

44 LINUX文件系统概述 　　(1) 文件系统的组织是分级树形结构形式。Linux文件系统的结构基本上是一棵倒向的树，这棵树的根是根目录，树上的每个结点都是一个目录，而树的叶则是信息文件。每个用户都可建立自己的文件系统，并把它安装到Linux文件系统上，从而形成一棵更大的树。 当然，也可以把安装上去的文件系统完整地拆卸下来，因而，整个文件系统显得十分灵活、方便。

45 　　(2) 文件的物理结构为混合索引式文件结构。所谓混合索引文件结构，是指文件的物理结构可能包括多种索引文件结构形式，如单级索引文件结构、两级索引文件结构和多级索引文件结构形式。这种物理结构既可提高对文件的查询速度，又能节省存放文件地址所需的空间。 　　(3) 采用了成组链接法管理空闲盘块。这种方法实际上是空闲表法和空闲链法相结合的产物，它兼备了这两种方法的优点而克服了这两种方法都有的表(链)太长的缺点，这样，既可提高查找空闲盘块的速度，又可节省存放盘块号的存储空间。

46 　　(4) 引入了索引结点的概念。在Linux系统中，把文件名和文件的说明部分分开，分别作为目录文件和索引结点表中的一个表项，这不仅可加速对文件的检索过程，减轻通道的I/O压力，而且还可给文件的联接和共享带来极大的方便。

47 　　2．文件系统的结构 　　由于在Linux系统中，文件名和文件属性(说明)分开存放，由文件属性构成文件的索引结点，这使Linux的目录项与一般文件系统的目录项不同，故Linux文件系统的结构也与一般文件有所差异。图10-18示出了引入索引结点后所形成的Linux文件系统结构。其中，根目录中的bin是二进制系统文件的根目录；usr为用户文件的根目录；dev为特殊文件的根目录。

48 图10-18　Linux文件系统的结构

49 　　3．文件系统的资源管理 　　为了在系统中保存一份文件，必须花费一定的资源，当文件处于“未打开”状态时，文件需占用三种资源： 　　(1) 一个目录项，用以记录文件的名称和对应索引结点的编号。 　　(2) 一个磁盘索引结点项，用以记录文件的属性和说明信息，这些都驻留在磁盘上。 　　(3) 若干个盘块，用以保存文件本身。

50 当文件被引用或“打开”时，须再增加三种资源：
(1) 一个内存索引结点项，该项驻留在内存中。 (2) 文件表中的一个登记项。 (3) 用户文件描述符表中的一个登记项。

51 　　由于对文件的读写管理必须涉及到上述各种资源，因而对文件的读写管理又在很大程度上依赖于对这些资源的管理，故可从资源管理的观点来介绍文件系统。这样，对文件的管理就必然包括：① 对索引结点的管理；② 对空闲盘块的管理；③ 对目录文件的管理；④ 对文件表和描述符表的管理；⑤ 对文件的使用。下面我们先介绍文件的物理结构。

52 文件的物理结构 　　1．寻址方式 　　1) 直接寻址 　　在Linux系统中的作业，是以中、小型的作业为主的。根据对大量文件调查的结果得知，文件长度字节数在10 KB以下的占大多数。为了提高对中、小型作业的检索速度，宜采用直接寻址方式。为此，在索引结点中建立了10个地址项i-addr(0)～i-addr(9)，在每个地址项中直接置入该文件占用盘块的编号，如图10-19所示。这相当于第六章所述的单级索引文件的寻址方式。如果盘块的大小为 1 KB，则当文件长度不大于10 KB时，可直接从索引结点中找出该文件的所有盘块号。

53 图10-19　直接寻址和间接寻址

54 　　2) 一次间接寻址方式 　　采用间接寻址方式是基于这样的事实：有不少文件，其长度可能达到几十千字节、几十兆字节甚至更长。如果全部采用直接寻址方式，就必须在索引结点中设置几百个或更多的地址项，这显然是不现实的。为了节省存放文件盘块号所占用的存储空间，在Linux系统中又提供了所谓的“一次间接”寻址方式，即在i-addr(10)地址项中，存放的不再是存放文件的一个物理盘块号，而是将存放了直接地址的1～256个物理盘块号的盘块的编号放于其中，这相当于第6章所述的两级索引文件中的寻址方式。假定一个盘块仍为1 KB， 一个盘块号占用32位，这样，i-addr(10)的寻址范围可达256 KB。

55 　　3) 多次间接寻址 　　为了进一步扩大寻址范围，又采用了二次间接和三次间接寻址方式，使用的地址项分别为索引结点中的i-addr(11)和i-addr(12)。二次间址相当于三级索引文件中的寻址方式，若盘块大小仍为1 KB，则可将寻址范围扩大到64 MB+256 KB；三次间址则可将寻址范围扩大到16 GB。

56 　　2．地址转换 　　1) 将字节偏移量转换为文件逻辑块号 　　在Linux文件系统中，文件被视为流式文件，每个文件有一个读、写指针，用来指示下一次要读或写的字符的偏移量。该偏移量是从文件的头一个字符的位置开始计算的。在每次读、写时，都要先把字节偏移量转换为文件的逻辑块号和块内位移量。其转换方法是：将字节偏移量除以盘块大小的字节数，其商即为文件的逻辑块号，余数为块内位(偏)移量。

57 　　2) 把文件逻辑块号转换为物理盘块号 　　(1) 直接寻址。当文件的逻辑块号小于或等于10时，索引结点中所存放的是直接地址。将逻辑块号转换为物理块号的方法是：首先，将文件的逻辑块号转换为索引结点中地址项的下标；其次，从该下标所指的地址项中，即可获得物理盘块号。 　　例如，某进程要访问其字节偏移量为9000处的数据，为此，核心须先将9000转换成文件逻辑块号8，块内偏移量为808。由于逻辑块号小于10，故可直接从相应的地址项i-addr(8)中找到物理盘块号为367的块(见图10-20)，在该块中的第808字节处即为文件的第9000字节处。

58 　　(2) 一次间址。当文件系统中的逻辑块号大于10而小于或等于256+10时，为一次间址寻址方式。其地址转换过程分为两步：
　　第一步，由于一次间址的地址项下标为10，所以可以从i-addr(10)中得到一次间址盘块号，由bread过程读间址块。 　　第二步，计算一次间址中文件的逻辑块号，即将文件的逻辑块号减10，根据一次间址中的逻辑块号得到间址块号中地址项的下标，再从相应下标的地址项中得到物理盘块号。

59 　　例如，进程要访问偏移量为14 000字节处的数据。核心先将14 000转换为逻辑块号13及块内偏移量688。由于10<13<266，故应属于一次间址。这样，再从i-addr(10)中得到一次间址的盘块号为428，调用bread过程读该盘块，计算一次间址块中的文件逻辑块号为3，从中可得到盘块号为952。于是，该块中的第688字节处便是要访问的文件的第14 000字节处，见图10-20所示。

60 　　(3) 多次间址。当文件的逻辑块号大于266，又小于或等于64 266时，应采用二次间址；逻辑块号大于64 266时应采用三次间址。多次间址的转换方法和一次间址时相似，但要多次循环，这里不再赘述。 　

61 图10-20　文件的地址映射示例

62 10.6.3　索引结点的管理 　　1．超级块(Superblock) 　　在Linux系统中，通常把每个磁盘或磁带看做是一个文件卷，在每个文件卷上可存放一个文件系统。文件卷可占用许多物理盘块，其中0#盘块一般用于系统引导；1#块为超级块。磁盘块和索引结点的分配与回收，将涉及到超级块。超级块是专门用于记录文件系统中盘块和磁盘索引结点使用情况的一个盘块，其中含有以下各字段： 　　(1) 文件系统的盘块数目。 　　(2) 空闲盘块号栈，即用于记录当前可用的空闲盘块编号的栈。

63 　　(3) 当前空闲盘块号数目，即在空闲盘块号栈中保存的空闲盘块号的数目。它也可被视为空闲盘块编号栈的指针。
　　(4) 空闲磁盘i结点编号栈，即记录了当前可用的所有空闲i结点编号的栈。 　　(5) 空闲磁盘i结点数目，指在磁盘i结点栈中保存的空闲i结点编号的数目，也可视为当前空闲i结点栈顶的指针。 　　(6) 空闲盘块编号栈的锁字段，是对空闲盘块进行分配与回收时的互斥标志。

64 　　(7) 空闲磁盘i结点栈的锁字段，是对空闲磁盘i结点进行分配与回收时的互斥标志。
　　(8) 超级块修改标志，用于标志超级块是否被修改，若已被修改，则在定期转储时，应将超级块内容从内存复制到文件系统中。 　　(9) 修改时间，指记录超级块最近一次被修改的时间。

65 　　2．磁盘索引结点的分配与回收 　　1) 分配过程ialloc 　　该过程的主要功能是每当核心创建一个新文件时，都要为之分配一个空闲磁盘i结点。若分配成功，便再分配一内存i结点。其分配过程如下： 　　(1) 检查超级块上锁否。超级块是临界资源，诸进程必须互斥地对它进行访问。因此在进入ialloc过程后，要首先检查它是否已被上锁，若已被锁住，进程便睡眠等待。 　　(2) 检索i结点栈空否。若发现i结点栈中已无空闲i结点编号，则应从盘中再调入一批结点号进栈。若盘中也已无空闲i结点，便做出错处理后返回。

66 　　(3) 从空闲i结点编号栈中分配一个i结点，并且加以初始化，填写有关文件的属性。
　　(4) 分配内存i结点。在Linux系统中，每当创建一个新文件后，便随之把它打开。因此在分配了磁盘i结点后，便调用iget过程再为之分配一个内存i结点，并对它进行初始化， 然后把磁盘i结点的内容复制到内存i结点中。 　　(5) 将磁盘i结点总数减1，并在置超级块的修改标志后返回。

67 　　2) 回收过程ifree 　　当一个文件已不再被任何进程需要时，应将该文件从磁盘上删除，并回收其所占用的盘块及相应的磁盘i结点。过程ifree便是用于回收磁盘i结点的。其所包括的操作有： 　　(1) 检查超级块上锁否。若已上锁便直接返回，即不能把本次回收的i结点号记入空闲i结点编号栈中。 　　(2) 检查i结点编号栈满否。若栈中的i结点编号的个数已等于100，则表示栈已满，无法再装入新的i结点号，也须立即返回。 　　(3) 若i结点编号栈未满，便使回收的i结点的编号进栈，并使当前空闲i结点数加1。 　　(4) 置超级块修改标志后返回。

68 　　3．内存索引结点的分配与回收 　　1) 分配过程iget 　　该过程的主要功能是在打开文件时，为之分配内存i结点。由于允许文件被共享，因此，如果一文件早已被其他用户打开并有了内存i结点，此时便只需将该i结点中的引用计数加1；如果文件尚未被其他用户打开，则由iget过程为该文件分配一个内存i结点，并调用bread过程将其磁盘i结点的内容拷贝到内存i结点中，同时进行初始化。

69 　　2) 回收过程iput 　　每当进程要关闭某文件时，须调用iput过程先对该文件的内存i结点中的引用计数做减1操作。若结果为0，便回收该内存i结点，再判断其磁盘的i结点的联接计数，若其结果也为0，便删除此文件，并回收分配给该文件的盘块和磁盘i结点。

70 10.6.4　空闲磁盘空间的管理 　　1．文件卷的组织 　　在Linux系统中的文件存储介质，可采用磁盘或磁带。通常可把每个磁盘或磁带看做是一个文件卷，每个文件卷上可存放一个具有独立目录结构的文件系统。一个文件卷包括许多物理块，并按照块号排列成如图10-21所示的结构。

71 图10-21　文件卷的组织

72 　　在文件卷中，0#块一般用于系统引导或空闲；1#块为超级块(Superblock)，用于存放文件卷的资源管理信息，包括整个文件卷的盘块数、磁盘索引结点的盘块数、空闲盘块号栈和空闲盘块号栈指针、空闲盘块号栈锁、空闲索引结点栈和空闲索引结点栈指针，以及空闲索引结点栈锁等。从2#块起存放磁盘索引结点，直到K#块。每个索引结点为64个字节，当盘块大小为1 KB时，每个盘块中可存放16个索引结点；从(K+1) #块起及其以后各块都存放文件数据，直至文件卷的最后一块即(N-1)#块。

73 　　2．空闲盘块的组织  　　Linux系统采用了成组链接法，对空闲盘块加以组织。该方法是将若干个(如100个)空闲盘块划归为一个组，将每一组中的所有盘块号存放在其前一组的第一个空闲盘块中，而仅把第一组中的所有空闲盘块号放入超级块的空闲盘块号栈中。例如，在图10-22所示的空闲盘块的组织中，将第四组的盘块号409、406、403等存入第三组的第一个即310号盘块中；又将第三组的盘块号310、307、304等放入第二组的第211号盘块中；而第一组的盘块号109、106、103等则放入超级块的空闲盘块号栈中。

74 图10-22　空闲盘块的组织

75 　　3．空闲盘块的分配与回收 　　1) 空闲盘块的分配 　　空闲盘块的分配是由alloc过程完成的，该过程的主要功能是从空闲盘块号栈中获得一空闲盘块号。当核心要从文件系统中分配一个盘块时，首先检查超级块中的盘块号栈是否已经上锁。若已锁上，便调用sleep过程睡眠；否则，将超级块的空闲盘块号栈顶的盘块号(如95号)分配出去。如果所分配的空闲盘块号是在栈底(如109号)，由于在该号盘块中又包含了第二组盘块的所有盘块号(如211、208等)，于是核心在给超级块上锁后，应先调用bread过程将该栈底盘块号对应盘块中的内容读出，作为新栈的内容进栈；然后，再将原有栈底所对应的盘块作为空闲盘块分配出去(即109号盘块)；最后，将超级块解锁，唤醒等待超级块解锁的进程。

76 　　2) 空闲盘块的回收 　　空闲盘块的回收是由free过程完成的。在回收空闲盘块时，首先检查超级块中的盘块号栈是否已经上锁，若已上锁，便调用sleep睡眠；否则，再检查空闲盘块号栈是否已满。如果空闲盘块号栈未满，可直接将回收盘块的编号记入空闲盘块号栈中；若栈已满，须调用betblk过程申请一个缓冲区，将栈中的所有空闲盘块号复制到新回收的盘块中，再将新回收盘块的编号作为新栈的栈底块号进栈。

77 10.6.5　文件表的管理 　　1．用户文件描述符表的管理 　　1) 用户文件描述符表 　　为了方便用户和简化系统的处理过程，在Linux系统Ⅴ中，在每个进程的U区中都设置了一张用户文件描述符表。核心先对其打开请求做仔细检查后，便在该进程的用户文件描述符表中分配一个空项，取其在该表中的位移量作为文件描述符fd(file discriptor)返回给用户。以后，当用户再访问该文件时，只需提供该文件描述符fd，系统根据fd便可找到相应文件的内存索引结点。

78 　　2) ufalloc过程 　　用户文件描述符表项的分配是由ufalloc过程来完成的。该过程首先是从用户文件描述符表中查找一个空项，若找到，便将该表项的序号fd作为文件描述符写入进程的U区，然后返回；否则，置出错标志后返回“NULL”。

79 　　2．文件表的管理 　　1) 文件表 　　系统为了对文件进行读/写，设置了一个确定读/写位置偏移量的读/写指针。该读/写指针应放在何处，是否可放在用户文件描述符表中，我们对此做了简单的分析。用户在读写文件时，可采用三种方式： 　　第一种方式，多个用户读/写各自的文件，见图10-23中的上部； 　　第二种方式，多个用户共享一个文件，但彼此独立地对文件进行读/写，见图10-23的中部； 　　第三种方式，多个用户共享一个文件，且共享一个读/写指针，见图10-23的下部。

80 图10-23　对文件的三种读/写方式

81 　　这样，若将读/写指针设置在文件描述符表项中，对前面两种情况固然可行，但要实现对读/写指针的共享就很困难了。为解决此问题，在Linux系统中引入了文件表，在其表项中存放各用户的读/写指针。这样，对上述三种读/写方式的读/写要求都能很好地满足。在文件表项中，除了读/写偏移量f-offset外，还设置了文件引用计数f-count，用于指示正在利用该文件表项的进程数目，以及用于指向对应内存索引结点的指针f-inode和读/写标志f-flag。

82 　　2) falloc过程 　　该过程的功能是分配文件表项。进入falloc过程后，调用ufalloc过程分配用户文件描述符表项。若未分配成功，便返回NULL；否则，继续从文件表中查找一个空闲文件表项。若找到空闲文件表项，便将该项的始址置入用户文件描述符表项中。在设置完文件描述符表项的初始值后便返回(fp)。若未找到空闲文件表表项，则返回NULL。

83 10.6.6　目录管理 　　1．构造目录项 　　每当某用户(进程)要创建一个新文件时，内核便应在其父目录文件中为之构造一个目录项；另外，当某进程需要共享另一用户的某文件时，内核也将为要共享该文件的用户建立一个目录项。因此，当一个共享文件与N个用户相联接时，该文件将有N个目录项。下面我们介绍在第一种情况下的目录构造过程。

84 　　在Linux系统中，构造目录的任务是由过程makenode完成的。在创建一个新文件时，由系统调用creat过程来为文件构造一个目录项。makenode过程首先调用ialloc过程为新文件分配一个磁盘i结点及内存i结点。若分配失败便返回。当分配成功时，须先设内存i结点的初值(含拷贝)，然后又调写目录过程wdir，将用户提供的文件名与分配给该文件的磁盘i结点号一起，构成一个新目录项，再将它记入其父目录文件中。

85 　　2．删除目录项 　　对于一个只由某用户独享的文件，在该用户不再需要它时，应将它从文件系统中删除，以便及时腾出存储空间。 　　对于一个可供若干个用户(进程)共享的文件，为了表示有多个用户(进程)要共享此文件，内核将利用link系统调用为各用户分别建立一个与该文件的联接，并设置联接计数nlink，使之等于要共享该文件的进程数目。 如有6个进程要共享该文件，则应设置nlink为6。 对于共享文件，由于该文件在某时刻可能正在被若干个用户所访问，因而不允许任何一个用户(进程，包括文件主)将该文件删除，这也正是Linux系统中不存在一条用于删除文件的系统调用的原因。

86 　　如果某时刻任何一个用户(进程)已不再需要某个共享文件，则只能利用去联接系统调用unlink，请求系统将本进程与该文件间的联接断开。此时， 系统须对该文件的联接计数nlink执行减1操作，并相应地删除该用户(进程)的一个指名的文件目录。仅当所有联接到该文件上的用户都不再需要该文件时，其nlink值必为0，系统才执行删除此共享文件的操作。相应地，将此文件的最后一个目录项从其文件目录中删除。

87 　　3．检索目录 　　在Linux系统中，用户在第一次访问某文件时，须使用文件的路径名，系统按路径名去检索文件目录，得到该文件的磁盘索引结点，且返回给用户一个文件描述符。以后，用户便利用该文件描述符来访问该文件，这时系统不再去检索文件目录。 　　对文件目录的检索是由namei过程完成的。该过程可被许多不同的系统调用所调用， 如有creat、open、link、chdir、chmod等，但它们对namei的要求并不完全相同。可将这些系统调用分成三类，分别用flag=0、flag=1和flag=2来表示。

88 　　对于flag=0的类，是由chmod、chdir等调用namei；如果namei查找到指名文件，便返回其相应的内存索引结点指针。
　　对于flag=1的类，主要是由creat调用namei；如果namei未找到指名文件，便做正常返回。 　　对于flag=2的类，主要是由unlink调用；在正常情况下，应返回由路径名所指出的父目录文件的内存i结点指针。这样就使得namei过程变得非常复杂，成为Linux系统中最复杂的过程。

89 　　检索目录的过程namei是根据用户给出的文件路径名，从高层到低层顺序地查找各级文件目录，寻找指定文件的索引结点号。在检索路径名时，对于以“/”开头的路径名，须从根目录开始检索；否则，应从当前目录开始检索，并把与它对应的i结点作为工作索引结点，然后用文件路径名中的第一分量名与根或当前目录文件中各目录项的文件名逐一进行比较。 由于一个目录文件可能占用多个盘块，因此，在检索完一个盘块中的所有目录项而又未找到匹配的文件分量名时，须调用bmap和bread过程，将下一个盘块中的所有目录项读出后，再逐一检索。若检索完该目录文件的所有盘块而仍未找到匹配的目录项时，才认为无此文件分量名。 　　

90 　　在未找到指定分量名的匹配目录项时，可分成以下几种情况处理:
　　第一种情况：对于最后一个路径分量名(要找的)，若flag≠1，做出错处理后返回；否则，属于正常情况。此时使namei过程继续执行，去检查其父目录文件是否允许写，父目录文件中是否有空目录项，若有，便分配一个空目录项，然后返回NULL。

91 　　第二种情况：若指定分量名不是最后一个路径分量名，也做出错处理后返回。
　　第三种情况：如果找到匹配项，便把该目录项中所指示的索引结点作为工作索引结点，并取出文件路径名的下一个分量名，继续重复上述过程，直至路径名中的所有分量名全部查找完毕，最后便可得到指名文件的索引结点。

92 Windows NT File System Sector(扇区：512字节) - smallest unit of storage on a disk Cluster(簇) - one or more contiguous sectors（大小可变） Volume(卷：最大264字节) - logical partition on a disk（可以跨磁盘）

93 NTFS Volume Layout Partition boot sector:每个分区的引导扇区；
File Area System Files Master File Table partition boot sector Partition boot sector:每个分区的引导扇区； Master File Table（MTF）:主文件表，存放本分区中的所有文件（包括目录）的列表，以及可用磁盘空间； System Files（系统文件）：MTF映射区，日志文件，卷位图，属性表

94 Windows NTFS Components
Virtual Memory Manager Cache Log File Service Disk Driver Flush the log file Write the cache Log the transaction Read/write the file Access the mapped file or flush the cache Load data from disk into memory I/O Manager Read/write a mirrored or striped volume the disk NTFS Driver Fault Tolerant Driver