文件管理
文件系统基础
文件的概念
- 文件的定义：
以计算机硬盘为载体的存储在计算机上的信息集合。系统运行时，计算机以进程为基本单位进行资源的调度和分配，而在用户进行的输入输出中，则以文件为基本单位。当用户把文件用于用户程序的输入输出时，希望还可以访问，修改，保存文件等，实现对于文件的维护管理，需要OS中的文件系统。
文件由存储空间中的数据，分类和索引信息，访问权限信息组成。用户通过文件系统建立文件，提供程序的输入输出，对资源进行管理，首先了解文件结构，通过自底向上的方式来定义：
①数据项：文件系统中最低级的数据组织形式，分为基本数据项（描述一个对象某个值，是数据中可命名的最小逻辑数据单元，即原子数据）和组合数据项（由多个基本数据项组成）。
②记录：一组相关数据项集合，描述一个对象在某方面的属性（考生信息一系列域）。
③文件：指由创建者所定义的一组相关信息集合，逻辑上分为有结构文件（文件由一组相似记录组成，又叫记录式文件）和无结构文件（视为一个字符流，又称流式文件）。
- 文件的属性：
系统不同属性也不同，但通常包括：
①名称：文件名称唯一，以易读取形式保存。
②标识符：标识文件系统内文件的唯一标签，通常为数字，对人不可读。
③类型：被支持不同类型的文件系统所使用。
④位置：指向设备和设备上文件的指针。
⑤大小：文件当前大小，也可包括文件允许的最大值。
⑥保护：对文件进行保护的访问控制信息。
⑦时间，日期和用户标识：文件创建，上次修改，上次访问的相关信息，用于保护跟踪文件使用。
所有文件的信息都保存在目录结构中，目录结构保存在外存中，文件信息需要时才调入内存，通常，目录条目包括文件名称以及唯一标识符，二标识符定位其他属性信息。 - 文件的基本操作：
OS提供系统调用，对文件进行创建，写，读，重定位，删除，截断等操作。（基本操作组合可以执行其他文件操作）
①创建文件（create系统调用）：①文件系统为文件找到空间。②目录中为文件创建新条目，记录文件名称和标识符等其他信息。
②写文件（write系统调用）：执行系统调用，指明文件名称和要写内容，系统维护一个写位置的指针，写操作时更新写指针。
③读文件（read系统调用）：执行系统调用，指明文件内容和要读文件快的内存位置，系统维护一个读位置的指针，读操作时更新读指针，读写使用同一个指针。
④文件重定位：按照某条件搜索目录，把当前文件位置设置为给定值，并且不会读写文件。
⑤删除文件（delete系统调用）：从目录找出删除文件的目录项，实质称为空项目，回收文件存储空间。
⑥截断文件：允许文件所有属性不变，并删除文件内容，即长度设置为0并释放其空间。
- 文件打开open和关闭close：
许多系统要求首次使用文件时，系统调用open将指明文件的属性从外存复制到内存，打开文件表的一个条目，把表目编号返回给用户，OS维护一个包含所有打开文件信息的表（打开文件表），需要文件操作时可以通过该表的一个索引指定文件，省略搜索环境，不再使用可以关闭它，OS打开文件表删除这个条目。open会根据文件名搜索牡蛎，并把目录条目复制到打开文件表，open返回一个指向打开文件表中的一个条目的指针，通过这个指针进行所有IO操作，之后对于文件任何操作不需要文件名字，只需要open调用返回的指针。
通常OS还用一个文件打开计数器Open Count，记录多少进程打开了该文件，打开计数器为0标识不再使用，系统回收系统资源。若文件被修改过，文件写回外存，并把打开文件表相应条目删除，最后释放文件的文件控制块FCB。
每个打开文件都有相关关联信息：
①文件指针：文件当前位置的指针，打开文件某个进程是唯一的。
②文件打开计数：上文解释过。
③文件磁盘位置：绝大数文件操作要求改变文件，该信息保存在内存中，以免每个操作都从磁盘中获取。
④访问权限：每个进程打开文件都要有访问模式（创建，只读，读写等），该信息保存在进程打开文件表中，以便OS可以允许/拒绝IO请求。文件的逻辑结构
- 逻辑结构就是用户观点看到的文件组织形式。物理结构则是实现观点出发看到的文件在外存上的存储组织形式。逻辑结构上，文件划分无结构文件和有结构文件两种：
- 无结构文件（流式文件）：
最简单的文件组织形式，把数据按照顺序组织成记录并积蓄保存，它是有序相关信息项的集合，以字节为单位。记录访问只能穷举搜索，适用于对基本信息单位操作不多的文件（如源程序文件，目标代码文件等） - 有结构文件（记录式文件）：
按照记录的组织形式可以分为：
①顺序文件：记录顺序排列，通常是定长的，可以顺序/链式存储，访问时顺序搜索文件。有两种结构：第一种是串结构：存入时间先后排列。第二种是顺序结构：按照关键字顺序排列。对于记录批量操作时，顺序文件操作效率最高，此外也只有顺序文件才能存在磁带上，但对于单条记录操作就比较困难。
②索引文件：对于定长记录文件和可变长记录文件，查找第i条记录地址不一样。变长记录文件只能顺序查找，系统开销大，为此可以建立一张索引表加速检索。 
③索引顺序文件：顺序和索引两种组织形式结合，把顺序文件所有记录分为若干组，建立一张索引表，表为每组第一个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。同一组的关键字可以无序，但组索引必须有序，先找到组再顺序查找。 
提高了查找效率，但配置索引表增加了存储空间。
甚至可以建立多级索引表
④直接文件/散列文件（Hash File）：给定记录的键值/通过散列函数转换的键值直接决定记录的物理地址，没有顺序的特性，有很高的存取速度但有冲突。目录结构
- 包含文件信息，这些信息由OS管理。用户角度：目录需要在文件名和文件之间有映射，目录存取效率直接影响系统性能，所以要提高用户检索速度，共享系统中，目录还需要提供用于控制访问文件的信息，重名也是合理的要求，通过树形结构来解决和实现。
- 文件控制块和索引结点：
为了实现目录管理，OS引入了文件控制块的数据结构。
①文件控制块FCB，用来存放控制文件所需要各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项，创建新文件则分配一个FCB并存放在文件目录中，成为目录项。主要包括：基本信息（名字，物理位置，逻辑结构等），存取控制信息（文件存取权限等），使用信息（创建修改时间等）。
②索引结点：检索目录文件过程中，只用到了文件名，仅当找到一个目录项时，才需要从该目录读取其物理地址，也就是其他描述信息没用到，所以有的OS采用文件名和描述分开方法，描述信息单独形成一个称为索引结点的数据结构，在文件目录中每个目录项仅由文件名和指向该文件的所对应i结点的指针构成。存放在磁盘上的索引结点称为磁盘索引结点，UNIX每个文件都由一个唯一的磁盘索引结点，主要包括：文件主标识符，文件类型，文件存取权限，文件物理地址，文件长度（以字节为单位），文件链接计数（指向该文件的指针计数），文件存取时间。
文件被打开时，磁盘索引结点复制到内存的索引结点以便于使用，在内存索引节点又增加了内容：索引结点编号（标识内存索引结点），状态（结点是否上锁或修改），访问计数，逻辑设备号，链接指针。
- 目录结构：
考虑目录层次的操作:搜索，创建文件，删除文件，显示目录，修改目录。考虑以下几种目录结构：
①单级目录结构：
整个文件系统只有一个目录表，每个文件占一个目录项。
访问文件，先按照文件名找到对应FCB，创建文件必须检索所有目录项以确保没有重名，删除文件回收存储空间再清楚目录项。单级目录实现了“按名存取”，但速度慢，无重名，不便于用户共享。
②两级目录结构：
把文件目录分为主文件目录MFD和用户文件目录UFD。
主文件目录记录用户名和相应文件目录所在存储位置，而用户文件目录记录相应用户文件目录的FCB信息，当用户相对其文件访问时只需要搜索该用户对应的UFD，解决了重名问题，保证安全，但缺乏灵活性，不能对文件分类。
③多级目录结构（树形目录结构）：
用户访问某个文件，用文件路径名标识文件，用“/”分隔开，从根目录出发的路径为绝对路径。而从当前目录出发到所找文件通路的路径为相对路径。
很方便对于文件分配，层次清晰，但查找时需要逐次访问中间结点，增加磁盘访问次数，影响速度。
④无环图目录结构：
树形结构不利于文件共享，所以在树形结构基础上增加指向同一结点的有向边，使得整个目录成为一个有向无环图，为了实现文件共享。
文件共享
使多个用户共享同一个文件，系统只需要保留一个副本。常用两种方法： - 基于索引结点的共享方式（硬链接）：
在树形结构目录中，当两个或多个用户要共享一个子目录/文件时，必须把共享文件或子目录链接到这些用户目录中，才能方便找到该文件。
文件的其他信息都放在索引结点中，而目录中只有文件名和指向相应索引节点的指针，索引节点还有count来计数链接到本索引结点的用户目录项数。
- 利用符号链实现文件共享（软链接）：
系统创建一个LINK类型的新文件，写入共享用户B的目录中，实现B的目录与文件F的链接，新文件中只包含被链接文件的路径名，这种方法称为符号链接。新文件中的路径名视为符号链，根据路径名读取文件，从而实现对文件的共享。
在利用符号链方式实现文件共享时，只有文件拥有者才拥有指向其索引节点的指针，而共享该文件的其他用户只有该文件的路径名。但仍然有一点问题，删除该文件且再次创建一样文件，软链接仍然有效。有个优点就是网络共享只需要提供该文件所在及其的网络地址及该及其中的文件路径。
类似于快捷方式。删除源文件则软链接失效。文件保护
为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读，写，执行的许可问题，为此必须在文件系统中建立相应的文件保护机制。文件保护通过口令保护，加密保护，访问控制等方式实现，其中口令和加密为了防止用户文件被他人存取或窃取，而访问控制用于控制用户对于文件访问方式。 - 访问类型：
读，写，执行（文件装入内存并执行），添加，删除，列表清单（列出文件名和属性），还有其他高级操作（通过掉哟个底层系统调用来实现）。 - 访问控制：
最常用方法就是根据用户身份进行控制，为每个文件FCB增加一个访问控制列表ACL，以规定每个用户名及其所允许的访问类型，精简的访问列表有：拥有者（创建文件用户），组（一组内需要共享文件且具有类似访问的用户），其他（系统内的所有其他用户）。用三个域列出访问表三类用户访问权限。
- 口令和密码时另外两种访问控制：
①口令指用户建立一个文件时提供一个口令，系统为其建立FCB时附上口令，且告诉共享文件的其他用户，用户请求访问时必须提供相应口令，缺点是口令存在系统内部不安全。
②密码则是对文件加密，访问需要密钥，保密性强但编码和译码需要花费时间。 - 总结：
文件系统的实现
文件系统层次结构
现代OS有很多种文件系统类型，因此文件系统层次结构也不尽相同。
- 用户调用接口：
文件系统为用户提供与文件及目录有关的调用。此层由若干程序模块组成，每个模块对应一条系统调用，用户发出一条调用，控制即转入相应的模块。 - 文件目录系统：
管理文件目录，任务有管理活跃文件目录表，管理读写状态信息表，打开文件表，管理与组织存储设备上的文件目录结构，调用下一级存取控制模块。 - 存取控制验证模块：
实现文件保护主要由该级软件完成，把用户访问和FCB中访问控制权限进行比较，确认合法性。 - 逻辑文件系统和文件信息缓冲区：
根据文件逻辑把用户读写的记录转换成文件逻辑结构内相应块号。 - 物理文件系统：
把逻辑记录所在的相对块号转换成实际物理地址。 - 辅助分配模块：
管理辅存空间。 - 设备管理程序模块：
分配设备，分配设备读写缓冲区，磁盘调度，启动设备，处理设备中断等。
目录实现
常用基本方法是线性列表和哈希表两种，目录实现的目的就是为了查找，因此对应线性查找和哈希查找。查询通过磁盘反复搜索完成的，开销大，复制进内存降低磁盘操作次数，提高系统速度。 - 线性列表：
使用存储文件名和数据块指针的线性表。 - 哈希表：
根据文件名得到值，返回一个指向线性列表中元素的指针。文件实现——文件分配方式
文件分配对应文件的物理结构，如何为文件分配磁盘块，常见分配有连续分配，链接分配，索引分配。文件分配方式——对于磁盘非空闲块的管理。
- 连续分配：
要求每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上的一个线性排序，这种排序使得作业访问磁盘需要的寻道数和时间最小。一个文件目录条目包括开始的块的地址和长度。连续分配支持顺序访问和直接访问，优点就是实现简单，存取速度快，缺点就是文件长度不宜动态增加，反复增删产生外部碎片。
- 链接分配：
离散分配的方式，消除外部碎片，增删改查方便，分为隐式链接和显式链接两种形式：
①隐式链接：
每个文件对应一个磁盘块链表，每个盘块都有指向下一个盘块的指针，这些指针对用户是透明的，目录包括文件的第一块指针和最后一块指针。创建新文件时，目录中增加一个新条目，每个目录项都有指向文件首块的指针，该指针初始化为NULL以表示空文件，写文件会同空闲空间管理系统找到空闲块，把该块链接到文件尾部，读文件则通过块间指针顺序读块。缺点就是无法直接访问，只能顺序访问，且软件/硬件错误导致指针丢失也会使得数据丢失。
②显式链接：
指把用于连接文件各物理块的指针，从物理块末尾提取出来放在链接表中，仅一张称为文件分配表FAT，每个表项存放对应块的下一块指针，即下一个块号，第一个块号存在目录中，后续通过FAT查找得到。用-1表示文件最后一块，-2表示这个磁盘块是空闲的。因此FAT不仅记录了文件各块先后关系，还标记了空闲磁盘块。FAT在系统启动的时候就被读入内存，因此查找FAT是在内存中进行的，不仅显著提高了检索速度，而且减少了访问磁盘次数。
③总结： 
- 索引分配：
链接分配不能解决直接访问，而索引分配解决了这个问题，它把每个文件所有盘块号都集中放在一起形成索引块。每个文件都由其索引块，这是一个磁盘块地址的数组，目录条目包括索引块的地址，第i块就是第i个条目的指针来查找和读入所需的块。创建文件时，所有索引块的指针都设置为空，首次写入第i块时需要从空闲空间中取得一个块，然后把其地址写入索引块的第i个条目。
索引块大小很重要，每个文件必须有一个索引块，尽可能小，但太小无法支持大文件，采用以下机制解决问题：
①链接方案：多个索引块链接起来处理大文件。
②多层索引：第一层索引指向第二次，以此类推。
③混合索引：多种索引分配方式结合的分配方式（有索引直接地址，有一级间接，二级间接） - 三种文件分配方式比较：
文件实现——文件存储空间管理
- 文件存储器空间的划分与初始化：
一般来说，一个文件存储在一个文件卷中，文件卷可以是物理盘一部分，也可以是整个物理盘。一个文件卷中，文件数据信息的空间和存放文件控制信息FCB的空间时分离的。
- 文件存储器空间管理：
文件存储设备分成大小相同的物理块，并以块为单位交换信息，因此文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织，分配，回收等问题。 - 空闲表法：
连续分配方式，为每个文件分配一块连续的内存空间，系统为外存的所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项，包括表项序号，该空闲区第一个盘块好，块数等信息，再递增排列。空闲盘区的分配和内存动态分配类似，同样采用首次适应算法/循环首次适应算法等。系统对用户释放的存储空间进行回收时，也采取类似用于内存回收的方法，考虑回收区是否和空闲表中插入点的前区和后区相邻接，对相邻接者予以合并。
- 空闲链表法：
所有空闲盘区拉成一条空闲链，根据构成链所有基本元素不同，分为两种形式：空闲盘块链和空闲盘区链。
①空闲盘块链：把磁盘上所有空闲空间以盘块为单位拉成一条链，当用户因为创建文件而请求分配存储空间时，从链首开始一次摘下合适数目空闲盘块分配给用户，删除则把回收盘块放在链末尾。
②空闲盘区链：把磁盘上所有空闲空间以盘区为单位拉成一条链，盘区含有指向下一个盘区指针和盘区大小信息，分配和内存动态分配一样，采用首次适应算法，回收时也是把回收区和相邻接的空闲盘区合并。 - 位示图法：
利用二进制的一位表示磁盘中的一个盘块的使用情况，0表示空闲，1表示已分配。分配和回收只需要修改二位数组的1/0即可。
- 成组链接法：
UNIX使用，结合空闲表和空闲链表，克服表太大的缺点。思想:顺序的n个空扇区地址保存在第一个空扇区中，其后一个空闲扇区则保存另一个顺序空闲扇区的地址，之后一个空闲扇区内则保存另一个顺序空闲扇区的地址，如此继续，直到所有空闲扇区链接完成。
磁盘组织与管理
磁盘的结构
- 磁盘分类：
磁盘调度算法
一次磁盘读写操作时间由寻道时间，旋转延迟时间，传输时间决定。
- 寻道时间，活动头磁盘读信息之前，把磁头移动到指定磁道所需要的时间，这个时间除了跨越n条道的时间外，还包括启动磁臂的时间。
- 旋转延迟时间，磁头定位到某磁道的扇区需要时间，设磁盘旋转速度为r，则t=1/2r。
- 传输时间，从磁盘读出或向磁盘写入数据经历的时间，取决于每次读写字节数b和磁盘旋转速度t=b/rN。
其中寻道时间和磁盘调度算法相关，而其他都与磁盘旋转速度有关。以下几种磁盘调度算法： - 先来先服务FCFS：
按照先后顺序进行访问磁盘调度。
- 最短寻找时间优先算法SSTF：
与当前磁道最近的磁道优先调度，但会产生“饥饿现象”。
- 扫描算法SCAN：
在当前移动方向上寻找与当前磁头最近的对象，就是SSTF基础上规定了磁头运动方向。
- 循环扫描算法C-SCAN：
扫描算法基础上规定磁头单项移动来提供服务，返回直接快速移动到起始端而不服务请求。
- LOOK算法：
扫描算法就是磁头严格一个方向从一端到另一端，而改进之后磁头移动只需要到达最远端而不需要到达磁盘端点，这就是LOOK算法。（默认SCAN为LOOK算法）
- C-LOOK算法：
对应C-SCAN类似，到达最远端点之后直接移动到起始端点而不提供服务请求。（默认C-SCAN为C-LOOK算法）
- 算法比较：
磁盘的管理
- 磁盘初始化：
磁盘存储数据之前，必须分成扇区以便磁盘控制器能进行读和写的操作，这个过程称为低级格式化。低级格式化为磁盘的每个扇区采用特别的数据结构，每个扇区的数据结构通常由头，数据区域，尾部组成。为了使得磁盘存储文件，OS还需要把自己的数据结构记录在磁盘上，第一步把磁盘分为由一个或多个柱面组成的分区（C盘，D盘等），第二部对物理分区进行逻辑格式化（创建文件系统），OS把初始文件系统数据结构存储在磁盘上，这些数据结构包括空闲和已分配空间及一个初始为空的目录。
- 引导块：计算机启动时运行初始化程序，初始化各类资源等，接着就启动OS。引导的这个自举程序的磁盘称为启动磁盘/系统磁盘。
- 坏块：硬件故障，OS处理不了。
