一、文件的结构

        1.逻辑结构

                在用户看来，文件内部的数据应该如何组织。

                ①无结构文件：文件内部的数据是一系列二进制流/字符流组成，又称“流式文件”，如txt文件。

                ②有结构文件：由一组相似的记录组成，又称“记录式文件”，如数据库表。每一条记录有一个数据项可作为关键字；又可分为定长记录和可变长记录。

                        Ⅰ顺序文件

                                文件记录一个接一个排列；可以是定长/可变长的；物理上采用顺序存储/链式存储。

                                可分为：串结构（记录顺序与关键字无关）、顺序结构（记录顺序按关键字顺序排列）

                        Ⅱ索引文件

                                建立一张索引表，每条记录对应一个索引项；文件在物理存储中离散的存放。

                                索引表本身是定长记录的顺序文件；主要用于对信息处理及时性要求较高的场合。可以用不同数据项建立多个索引表。

                                缺陷：索引表可能很大，占用过多内存。（甚至比文件本身都大）

                        Ⅲ索引顺序文件

                                同样会建立索引表，但是不是每个记录对应一个索引表项，而是一组记录对应一个索引表项（不需要按关键字顺序排列，可以很方便的更新表项）

                                 先分组，再建立索引表；查找的时候就可以先查分组再在分组内查询。节省查找次数。也可以建立多级索引表继续降低次数。

        2.物理结构

                在系统看来，文件的数据应该如何存放。

                磁盘块：类似于内存分页；磁盘块大小与内存块、页面的大小相同

                文件逻辑地址：同样被划分为一个个文件“块”，可以表述为（逻辑块号，块内地址） 

                        操作系统更为文件分配存储空间都是以块为单位，操作系统提供逻辑块号与物理地址的映射

                ①连续分配

                        每个文件在磁盘上占有一组连续的块。

                        地址转换：（逻辑块号，块内地址）->（物理块号，块内地址）仅需转换快号就行，块内地址保持不变。        物理块号 = 起始块号 + 逻辑块号

                        文件目录：

                        优点：支持顺序访问和直接访问（随机访问）；在顺序读/写时速度最快

                        缺点：不方便文件的扩展（连续分配造成的）；磁盘利用率低，会产生磁盘碎片，虽然可以通过紧凑来处理碎片，但是开销极大。

                ②链接分配

                        采用离散分配的方式，分为显式链接和隐式链接。未标明的情况下默认为隐式链接

                        Ⅰ隐式链接：每个逻辑块都会有一个指针链接到下一个逻辑块，这些指针对用户是透明的。

                                地址转换：从起始目录找到起始块号（0号块），从0号块一直读到i号块（需要i+1次操作）

                                优点：查找效率较低，同时需要额外空间来存放指针。方便文件扩展；且不会产生磁盘碎片，利用率高。

                                缺点：只支持顺序访问，不支持随机访问。

                        Ⅱ显示链接：单独建立一张链接表（文件分配表FAT）

                                 一个磁盘仅需设一张FAT；且开机时，FAT会被读入内存并常驻内存。

                                地址转换：匹配FAT在其中找到对应的物理块号，此过程不需要读磁盘操作。

                                优点：支持顺序访问和随机访问，显示链接访问速度快过隐式链接；且不会产生磁盘碎片，磁盘利用率高。

                                缺点：FAT需要占用一定的存储空间。

                ③索引分配

                                系统会为每个文件建立一张索引表，索引表中记录了文件各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块，数据存放的磁盘块称为数据块。

                                索引表与FAT的区别是，一个系统仅有一个FAT，但索引表是每个文件对应，索引表的逻辑块号可以是隐含的。

                                索引分配支持随机访问。也易实现文件扩展。

                                若文件大小超过了索引块容量，可以采用以下方案：

                                        ①链接方案：分配多个索引块，并将其链接起来（添加尾指针）

                                                缺陷：不允许随机访问内部逻辑块（仅可依次访问）

                                        ②多层索引：建立多层索引表，采用k层索引结构时，访问一个内存快仅需操作k+1次I/O。

                                        ③混合索引：一个文件的顶级索引表中可能包含多种索引类型（直接索引、间接索引）

                                                 对于小文件，仅需要少量读磁盘操作即可访问到目标数据块。

        3.文件目录

                ①文件控制块

                        目录也是一种特殊的文件。目录文件中的一条记录就是一个“文件控制块”（FCB）

                        FCB的有序集合称“文件目录”，一个FCB即为文件目录项。

                        FCB中包含文件的基本信息（文件名、物理地址、逻辑地址、物理结构），存取控制信息（只读/可写、禁止访问名单）、使用信息（建立时间、修改时间）

                        FCB实现了文件名和文件之间的映射，实现了用户的按名存取。

                ②目录结构

                        Ⅰ单级目录结构：整个系统仅建立一张目录表。支持按名存取，但不允许文件重名

                                不适用于多用户操作系统

                        Ⅱ两级目录结构：分为主文件目录和用户文件目录。

                                 采用此结构后，允许不同用户的文件重名；但是依旧缺乏灵活性，用户不能自己对文件进行分类

                        Ⅲ多级目录结构：又称树形目录结构。

                                 用户访问某个文件时要用文件路径名标识文件，路径名是一个字符串，各级目录间以 / 隔开。从根目录出发的路径为绝对路径。

                                操作系统会根据目录一层一层地找到下一级目录。会从外存中读取对应的目录表，找到对应的目录后再想下一级寻找，直至找到文件（从绝对目录开始，有几级就需要读几次）为了解决从根目录开始查找缓慢的问题，也可以设置“当前目录”（从当前目录开始的被称为相对路径）

                                缺点：不便于实现文件的共享

                        Ⅳ无环图目录结构：树形结构的基础上，增加了指向同一节点的有向边

                                 可以用不同的文件名指向同一文件/同一目录（共享）

                                要求为每个共享结点设置一个共享计数器，当用户请求删除时，只删除该用户的FCB且共享计数器减一，而非直接删除共享结点。

                                共享文件 ≠ 复制文件

                ③索引结点

                        对FCB的改进，只提取关键信息；仅在文件名匹配时才会去读取其他信息。可以提升文件检索速度。

二、文件存储空间管理

        对空闲空间的管理（对应非空闲的文件管理）

        1.存储空间的划分和初始化

                        存储空间的划分：将物理磁盘划分为文件卷（C盘、D盘等）

                        文件卷内部划分：分为目录区（存放FCB、磁盘信息等内容）、文件区（存放文件数据）

                                系统支持超大型文件，可支持将多个物理磁盘合并成一个文件卷

        2.管理方法

                ①空闲表法

                        建立空闲盘块表，适用于“连续分配”

                        分配：为文件分配连续存储空间（首次适应、最佳适应、最坏适应等）

                        回收：回收时注意表项合并问题

                ②空闲链表法

                        Ⅰ空闲盘块链：以盘块为单位组成一条空闲链。

                                空闲盘块记录着下一个空闲盘块的指针。

                                系统保存有链头、链尾指针。

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

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

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

                        Ⅱ空闲盘区链：以盘区为单位组成一条空闲链。

                                空闲盘区的第一个盘块内记录了盘区长度、下一个盘区的指针。

                                系统保存有链头、链尾指针。

                                分配：若文件申请k个盘块，则从链头开始使用分配算法找到合适的空闲区分配给文件

                                           若没有合适的内存区，可以将多个空闲区分配给同一文件；分配完成后需要修改链头指针、盘区大小等数据。

                                回收：若回收区有相邻的空闲盘区，则将之合并

                                           若回收区没有相邻的空闲盘区，则将其作为单独空闲空间挂在链尾

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

                ③位示图法

                        建立位示图，每个二进制位对应一个盘块。以0/1代表盘块是否已分配。可以由字号和位号推出其对应的盘块号。

                        分配：扫描位视图，找到K个不为0的位；根据字号和位号推算其盘块号，并将其分配给文件；将标志置为已分配。

                        回收：根据回收的盘号，算出对应的字号、位号；将对应的位示图置为未分配。

                        适用于连续、离散分配。

                ④组成链法

                        上述分配方法①②③并不适用于超大型文件系统

                        文件卷的目录区专门用一个磁盘作为超级块，系统启动时将超级块读入内存（要保证内存和外存中超级块的一致性）

                         分配：从头开始检测盘块数是否满足，若满足直接操空闲块块内部即可。

                                    若分配的内容挤占了整个空闲块，因为空闲块内包含下一个空闲块的信息，所以要将其复制到超级块当中。

                         回收：若超级块中的分组未满时，直接将其挂载到超级块内即可。

                                    若超级块中分组已满，则需要将超级块中的数据复制到新块中，并修改超级块内容，使之成为第一个分组。

 三、文件基本操作

        1.创建文件

                进行create操作时需要提供以下参数：①所需外存大小 ②文件存放路径 ③文件名

                系统会执行以下操作：①在外存中找到文件所需的磁盘空间 ②找到文件夹对应的目录表，在其中插入文件的目录项。

        2.删除文件

                进行delete操作时需要提供以下参数：①文件存放路径 ②文件名

                系统会执行以下操作：①找到文件名对应的目录项 ②回收文件占用的磁盘块 ③删除文件的目录项。

        3.打开文件

                 进行open操作时需要提供以下参数：①文件存放路径 ②文件名 ③操作类型（r只读、rw读写）

                系统会执行以下操作：①找到文件对应的目录项，检查用户是否有指定的操作权限 ②将目录项复制到内存中的“打开文件表”中，将目录表的编号返回给用户。之后用户以编号来操作文件，用户之后操作文件就不需要再访问目录表了，大大提升了访问速度。

                打开文件表的索引号又可称为“文件描述符”

                打开文件时并不会将数据直接写入内存。

                打开文件表分为两种：①进程打开文件表 ②系统打开文件表（整个系统仅有一张）

        4.关闭文件

                ①将进程的打开文件表相应的表项删除 ②回收其资源 ③将系统打开表中对应项的计数器-1，若为0则删除表项。

        5.读文件

                （打开文件为前置操作） 进行read操作时需要提供以下参数：①指明需要读取文件的打开文件表编号。②指明需要读入的数据大小、内存中的存放位置。

        6.写文件

                进行write操作时需要提供以下参数：①指明要写的文件（打开文件表编号）。②需要写回的数据大小、内存位置。

四、文件共享

        1.基于索引结点（硬链接）

                索引结点：将除文件名以外的其他信息放入索引结点中。

                索引结点的计数器用户表示链接到此结点上的用户目录项目数。

                采用此种方法，用户删除文件时，系统仅将索引结点的count减一，当其归零才会删除文件。

        2.基于符号链（软链接）

                Link类型文件类似于快捷方式。

                软链接指向的文件即使被删除，Link文件依旧存在，只是链接失效。软链接由于会一层层查找目录，所以会产生多次I/O访问。

五、文件保护

        1.口令保护

                为文件设置一个口令(字符串)，用户访问该文件时必须提供“口令”；口令一般存放在文件对应的FCB/索引结点中，用户访问文件前必须先验证口令，由系统进行对比通过后才能访问文件

                优点：保存/验证口令时开销小。

                缺点：正确的口令存放在系统内部，不够安全

        2.加密保护

                使用密码对文件进行加密，访问文件时必须提供密码才能对文件进行解密

                优点：保密性强，不需要在系统中存储密码

                缺点：加密/解密需要花费一定时间。

        3.访问控制

                在文件的FCB中增加一个控制列表，该表中记录了各用户可以对该文件执行的操作

                精简的访问列表：以组为单位，标记各组用户可以对文件执行的操作。

                优点：实现灵活，可以实现复杂的文件保护

六、文件系统的层次结构

七、磁盘

            1.磁盘结构

                ①基础概念

                        磁盘：表面由磁性物质组成，可以通过磁性物质来记录二进制数据

                        磁道：

                        扇区：一个扇区即为一个磁盘块

                        由于每个扇区存储数据大小一致；越往内侧，数据密度越大。

                ②读/写操作

                        目标扇区从磁头下方划过

                ③盘面、柱面

                ④物理地址

                        可以根据柱面号、盘面号、扇区号转换出物理地址。

                ⑤分类

                        活动磁头盘：磁头可以通过磁臂带动

                        固定磁头盘：每个磁道有一个固定式磁头

         2.磁盘调度算法

                ①磁盘操作时间

                        Ⅰ寻找时间：读/写前将磁头移动到指定磁道所花费的时间

                                ①启动磁头臂的时间

                                ②移动磁头花费的时间

                        Ⅱ延迟时间：旋转磁道使磁头定位到目标扇区

                                磁盘转速越高，延迟时间越小

                        Ⅲ传输时间：读出/写入数据经历的时间

                 ②调度算法

                        Ⅰ先来先服务(FCFS)：根据进程请求访问磁盘的先后顺序进行调度

                                优点：公平

                                缺点：如果有大量进程竞争访问磁盘，请求访问的磁道又很分散，性能就会很差

                        Ⅱ最短寻找时间优先算法(SSTF)：优先处理离当前磁头最近的磁道；可以保证每次寻道时间最短，但是不能保证总寻道时间最短

                                优点：性能较好

                                缺点：可能造成饥饿

                        Ⅲ扫描算法(SCAN)：磁头只有移动到最内侧才能向外移动，只有移动到最外侧才能向内移动（单向移动），又称为电梯算法。

                                优点：性能较好，不会产生饥饿

                                缺点：只有触碰边界才能变换方向，但实际上可能并不需要触碰边界（浪费路程）；对各部分的磁道响应时间不平均。

                        ⅢLOOK调度算法：在SCAN算法的基础上，如果当前磁头移动方向上没有其他请求，可以立刻调转磁头移动方向。

                                优点：进一步缩短寻道时间

                        Ⅳ循环扫描算法(C-SCAN)：磁头仅向特定方向移动时才会处理访问请求，在返回起始位置的过程中会快速返回而不处理任何请求。

                                优点：各个位置的磁道响应时间更平均

                                缺点：只有触碰边界才能变换方向，但实际上可能并不需要触碰边界（浪费路程）；

                        ⅤC-LOOK算法：基于C-SCAN算法，但磁头仅向特定方向移动时才会处理访问请求，在返回起始位置的过程中会快速返回而不处理任何请求。

        3.减少磁盘延迟时间

                磁盘读入一个扇区数据后需要一小段时间处理，读入连续的扇区就会有较高的延迟时间

                交替编号：使逻辑相邻的扇区在屋里上有一定的间隔

                错位命名：让相邻盘面编号错位

        4.磁盘管理

                ①磁盘初始化

                        低级格式化（物理格式化）：将磁盘的各个磁道划分为扇区；一个扇区由头、数据区域、尾三个部分组成；管理扇区的数据结构存放在头、尾两个部分（包含奇偶校验、CRC循环冗余校验码等）

                        磁盘分区：每个分区由若干柱面组成（即分盘）

                        逻辑格式化：创建文件管理系统

                ②引导块

                        计算机开机时需要执行初始化程序（自居程序）来完成初始化工作。

                        现代操作系统会在ROM上存放自举装入程序，完整的自举程序放在磁盘的引导块/启动分区中；启动块位于磁盘的固定位置上。

                        拥有启动分区的磁盘被称为启动磁盘/系统磁盘

                ③坏块管理

                        坏块：无法使用的扇区，属于硬件故障

                        操作系统无法修复坏块，会将其标记出来，避免错误的使用到它

                        对于简单的磁盘，可以在逻辑格式化时标明坏块（如在FAT上标注）；

                        对于复杂的磁盘而言，磁盘控制器会维护坏块链表。磁盘出厂的时候会保留一些备用扇区用于替换坏块，此方案称为扇区备用，坏块操作对系统上透明的。