操作系统

按照王道书的框架进行整理联系 继续引用小林coding大佬的图解进行理解！🙏膜大佬 加入错题里面的例题重点理解

文件：是以计算机硬盘为载体的存储在计算机上的信息集合，包括文档、图片、程序等。 文件系统（文件管理系统）：为实现用户对于文件的访问、修改、保存等功能，对文件进行维护管理，操作系统提供一个文件管理系统。 组成：与文件管理有关的软件、被管理文件和实施文件管理所需的数据结构。 功能：实现对文件的基本操作，用户按名存储和查找文件，组织成合适结构，具有文件共享和文件保护功能。

系统提供系统调用，对文件进行创建、写、读、重定位、删除、截断等操作。（系统调用 create、delete、open、close、read、write） 我们打开文件后，os会为每个进程维护一个打开文件表，每一项代表文件描述符。

os在打开文件表中维护着打开文件的状态和信息： 1.文件指针：系统跟踪上次读写位置为当前文件位置指针，上面有提到，同时对于打开文件的某个进程来说是唯一的。 2.文件打开计数：文件关闭时，os必须重用其打开文件表条目，否则表内空间会不够用。所以count等于0时删除条目。 3.文件磁盘位置：绝大多数文件操作都要求修改文件数据，该信息保存内存中，避免每个操作从磁盘中读取。 4.访问权限：（创建、只读、读写）该信息保存在进程打开文件表中，便于os能允许或拒绝之后的I/O操作。

文件系统的基本操作单位是 数据块。 os不关心用户想存在磁盘上的数据结构，只在意如何把文件数据和磁盘块对应，所以在用户以字节读写文件时，os用数据块读写文件。

逻辑结构与物理结构相对应，逻辑结构是对于用户层面的，而物理结构是操作系统层面的，相较于数据结构中的线性表（用户），物理结构又可以是顺序表和链表。 文件的按照逻辑结构，可划分为无结构文件（流式文件）和有结构文件。

无结构文件：以字节为单位，对记录的访问只能是穷举搜索，所以不适用于大多数应用。同时，对于基本信息单位操作不多的文件较适用于采用字符流的无结构方式，如源程序文件、*.txt等

有结构文件：

按照记录是否定长，分为定长和变长文件。记录通常是定长的可以顺序存储和链表存储。仅有顺序存储中的定长文件可以实现随机存取。 按照是否按照关键字排序，又分为串结构（无关）和顺序结构（所有记录按关键字顺序排序）

优点：对记录进行批量操作时，顺序文件效率最高，只有顺序文件存储在磁带上。 缺点：增删改查操作都困难

有一张索引表，里面存放文件记录的长度和所在逻辑文件的起始地址。

优点：可以随机访问，易于文件的增删 缺点：增加了存储空间的开销

结合索引和顺序文件。 索引顺序文件将顺序文件中所有记录分为若干组，为顺序文件建立索引表，并为第一个记录建立索引项（包含该记录的关键字与索引指针） 索引表按关键字顺序排列 逻辑文件是顺序文件，组间关键字有序排列。

优点：大大提高顺序存取速度 缺点：索引表增加存储开销

直接文件（散列文件）：

直接通过关键字的值找到记录的物理地址，没有顺序的特性。

优点：很高的存取速度 缺点：会出现因不同关键字的散列函数值相同而引起冲突。

前面介绍了文件的内部逻辑结构，下面是多个文件“外部”在逻辑上的结构问题。

实现“按名存取”：（最基本的功能，文件系统对用户的最基本服务） 提高检索速度：目录结构合理设计 允许文件同名：通过不同工作目录区分同名文件 允许文件共享：同时保证不同权限用户取得相应的文件操作权限

文件控制块（FCB）：保存文件属性信息的数据结构

基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构 存取控制信息：权限 使用信息：文件建立、修改时间

索引结点：

检索目录时，常只用到文件名，所以用文件名与文件描述信息分开，将文件描述信息单独形成索引结点。 文件目录中的每个目录项由文件名和指向该文件结点的指针构成。 磁盘块可以存放更多的目录项，使得启动磁盘次数减少，减小开销。 文件被打开时，磁盘索引结点复制到内存的索引结点中。

整个文件系统只有一个目录表 优点：实现了“按名存取” 缺点：查找速度慢、文件不许重名、不便于文件共享

主文件目录和用户文件目录 优点：解决多用户间的文件重名问题，在目录上实现访问限制（不同用户不能访问别人用户文件目录） 缺点：不能对文件分类，缺乏灵活性

用户要访问某个文件时，使用相对路径标识文件，相对路劲由从当前目录出发到所找文件通路上所有目录名与数据文件用分隔符 “ / ” 优点：对文件分类、层次清晰，有效进行文件管理和保护 缺点：增加了磁盘访问次数，影响速度

2）①条件：E有访问文件Q的权限。通过相对路径来访问，用户E通过自己的主目录E找到父目录C，在访问C的父目录（根目录），然后依次通过D,G,K,O访问文件Q。访问路径：“…/…/D/G/K/O/Q”。 ②用户G要访问目录K和目录P，再能访问文件S,T。提高访问速度，在G目录下建立两个链接文件，分别连接ST，这样G可直接访问这两个文件。 ③能，在文件I的存取控制表中，只留下E的访问权限，其他用户对I无操作权限，即达到目的。

基于树形结构不便实现文件 共享，引出无环图 增加了指向同一结点的边，代表共享。 用户提出删除该结点时，只有共享结点为0时，才删除结点，否则仅删除请求用户的共享链。 注意与拷贝的区别，拷贝有副本，共享仅一个文件。

上面简单的提到的文件共享可以在有向无环图实现，下面在了解一下硬链接和软链接的共享方式。

索引结点的链接：在上面例题中，用户E要共享Q文件（或子目录），要将Q文件（或子目录）链接到E的目录中。 这种共享方式中，文件的物理地址及其他文件属性等信息放在索引结点中。文件目录只设置文件名和指向相应索引结点的指针。同时索引结点中增加count连接计数。 删除时，count不为0时，文件拥有者不能删除文件，否则会使别的用户指向该文件的指针悬空，只是count-1，直至count为0时，系统负责删除文件。

符号链接（软链接）：对于B用户想共享A用户的F文件，可以系统创建一个link类型的新文件，也取名F，并将F写入用户B的目录中。在新文件中只包含被链接文件F的路径名，路径名即符号链。 在软链接中，仅有文件拥有者才有被链接文件的索引结点的指针，共享文件的用户只有路径名，不拥有指针。 删除时，文件拥有者将共享文件删除，其他共享用户通过符号链进行访问时，就会访问失败，再删除符号链。

优点：网络共享：只需提供该文件所在机器的网络地址和该机器的文件路径。 存在的问题： 某个文件A被其拥有者删除后，它的位置重新创建了一个同名文件，此时共享文件A的用户再次通过符号链寻找，访问的文件已经改变，出错。 缺点：共享的用户读共享文件时，增加时间开销，同时符号链索引结点也耗费磁盘空间。

以上文件共享实现后，就要维护好文件，控制用户对文件的操作，所以产生了文件保护机制。

文件保护通过口令保护、加密保护、访问控制等方式实现。 保护可以只在底层实现，比如一个文件具有读的访问权限，那么高层的复制、打印权限都可以实现。

优点：使用复杂的访问方法 缺点：长度无法估计且造成复杂的空间管理问题

优点：时空开销小 缺点：口令存在系统中，不安全

优点：保密性强。节省存储空间 缺点：编码和译码消耗时间

注意： 口令和密码没有限制用户对文件的访问类型。 对于多级目录结构来说，不仅需要保护单个文件，还需要保护子目录的文件，提供目录保护机制。 用户访问权限是指用户有没有权限访问文件 用户优先级是多个用户同时请求该文件应先满足谁。

用户层↓

特殊的⽂件，经常⽤到的⽬录，它是如何保存的，和普通⽂件不同的是，普通⽂件的块⾥⾯保存的是⽂件数据，⽽⽬录⽂件的块⾥⾯保存的是⽬录⾥⾯⼀项⼀项的⽂件信息 目录包括两种实现 线性表和哈希表

下面来理解一下上面出现优缺点的过程。

文件存放在磁盘连续的物理空间中，读写效率很高。 文件目录条目包括开始块地址和文件长度。 这种方式存在磁盘空间碎片（外部碎片）以及不易扩展的问题。 空间碎片类比上一篇的内存碎片，都是存在空闲空间之和大于当前文件大小，文件却无法存放的问题。 不易扩展与上面问题都需要挪动来解决，但是磁盘挪动文件非常耗时。所以引出非连续分配方式。

链接分配可以消除外部碎片和扩展问题，对于新增只需找到一个空闲块链接到原文件链表上。

每个文件对应磁盘块的链表，每个盘块有指向下一个的指针（除末盘块外）目录里存放第一块和最后一块的指针。 缺点：⽆法直接访问数据块，只能通过指针顺序访问⽂件（不支持随机访问），以及数据块指针消耗了⼀定的存储空间。 可能出现稳定性问题：运行中指针丢失或损坏，文件数据丢失。

解决隐式链接的指针丢失问题，单独存放。

把用于链接文件各物理块的指针，提取出来，存放在内存的一张链表中。即文件分配表（FAT）。 FAT常驻内存，提高检索速度。既可以找文件，又可以标记出空闲磁盘块。 支持随机访问

为了直接访问，还可以采用索引分配。 k层索引结构需要k+1次访问磁盘。

把文件所有盘块号集中放在一起构成索引块，这是一个磁盘块地址的数组。

解决索引块放不下的问题： 链接方案，将几个索引块连接起来，处理大文件问题。

多层索引：类比于文件管理。

混合索引：多种索引分配方式结合，易出题。

某文件索引结点有7个地址项，4个直接地址索引，2个一级间接地址索引，1个二级间接地址索引，每个地址项为4B，若磁盘索引块与磁盘数据块都是256B，则可表示的单个文件大小是 每个磁盘索引块有256/4=64个地址项 直接地址：4*256 一级间接地址：64 * 256 * 2 二级间接地址：64 * 64 * 256 相加即可 1057KB

文件存储空间的管理

类比于内存管理，采用首次适应算法等

空闲表法就是为所有空闲空间建⽴⼀张表，表内容包括空闲区的第⼀个块号和该空闲区的块个数，这个⽅式是连续分配的。

空闲盘块链和空闲盘区链都是链表式，不能随机存取 缺点：在链上增加或移动空闲块时需要做很多 I/O 操作，同时数据块的指针消耗了⼀定的存储空间。

是利⽤⼆进制的⼀位来表示磁盘中⼀个盘块的使⽤情况，磁盘上所有的盘块都有⼀个⼆进制位与之对应。 0：空闲 1：分配 注意盘块号和行列的计算（看题从0还是1开始排列）

解决空闲表和空闲链表都不能解决的大型文件系统问题，提出了成组链接法。 文件卷的目录区里有“超级块”，启动时读入内存。 超级块中记录了空闲盘块数 以及空闲块号 分配：检查当前超级块中下一级第一个分组中的空闲盘块数是否满足，然后分配空闲盘块，把该空闲盘块号删除，同时空闲盘块个数减一，分配之前要把该分组指向下一个分组的链接信息复制超级块中。 回收：有两种情况，要注意能否直接加入空闲块号，如果分组满了，要继续回收，新回收的块作为新分组，要复制当前超级块到新分组当中，此时新回收的块成为第一个分组，修改超级块，空闲块数为1，指向新分组。

一次磁盘读写操作时间包括： 寻找时间（寻道时间）：启动磁臂，移动磁头所花的时间（磁盘调度算法影响的指标）。 延迟时间：将目标扇区转到磁头下面所花的时间。 传输时间：读/写数据花费的时间。

按访问请求到达的先后顺序进行处理。 （对于先来先服务可以看做是可能随时改变磁头的运动方向）

优点：公平 缺点：平均寻道距离大

每次都优先响应距离磁头最近的磁道访问请求。 贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短。

缺点：可能导致饥饿。

只有磁头移动到最边缘的磁道时才可以改变磁头移动方向。

优点：解决了饥饿问题 缺点：对各个位置磁道的响应频率不平均。

加入单向移动，固定的一端到另一端。 只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求。

原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区。

原理：与交替编号的原理相同，错位命名法可降低延迟时间。

磁盘地址结构的设计： 理解为什么要用（柱面号，盘面号，扇区号）的结构，而不是（盘面号，柱面号，扇区号）的结构？ 读取地址连续的磁盘号时，采用前者的地址结构可以减少磁头移动消耗的时间。可以看磁盘的结构理解。

磁盘初始化