操作系统二复习大纲

第一次线上考试，考得非常一般。理性分析，4.0大概率没了。

最后侥幸拿了91分……

第四章 存储器管理

4.1 存储器的层次结构

存储器的六层结构：

• CPU寄存器
• 主存储器：高速缓存、主存储器、磁盘缓存（内存中）
• 辅存储器：固定磁盘、可移动磁盘

可执行存储器：寄存器、主存储器

4.2 程序的装入和链接

（自学）程序在系统中运行，需要先装入内存，然后经过以下过程：

• 编译：由编译程序编译形成若干个目标模块

• 链接：将模块与库函数链接在一起，形成完整的装入模块

• 装入：由装入程序将装入模块装入内存

程序的链接：

• 静态链接：在程序运行前完整链接。需要拷贝全部模块。
  • 对每个模块相对地址进行修改

​ - 变换外部调用符号

• 装入时动态链接：边装入边链接。

​ - 便于修改和更新（修改模块时不需要重新打开装入模块）

​ - 便于实现模块的共享（时分复用）

• 运行时动态链接：推迟到执行时链接。只链接实际运行用到的模块，节省内存。

逻辑地址：装入程序的地址都是从0开始

物理地址：主存中一系列存储信息的物理单元的地址

重定位：逻辑地址（相对地址）到物理地址（绝对地址）的映射

程序的装入：

• 绝对装入：

  • 程序编译后直接产生物理地址
  • 适用单道系统

• 可重定位装入(静态重定位)：

  • 装入时根据内存情况对指令地址和数据地址进行相应偏移
  • 地址变换在装入时一次完成，此后不再改变；无需硬件支持
• 动态运行时装入：
  • 装入后仍然是逻辑地址，地址转换推迟到执行时进行
  • 需要重定位寄存器；支持程序在内存中浮动；不要求占用连续空间

4.3 连续分配存储管理方式

• 单一连续分配：用于单用户、单任务的操作系统中。

  • 将内存划分为系统区和用户区
  • 用户区内存由一道程序独占
  • 适合绝对装入方式

• 固定分区分配：将用户内存划分多个分区，每个分区一道程序独占

  • 分区大小相等或不相等
  • 使用分区说明表标识分区分配状态
  • 适合静态重定位装入方式

• 动态分区分配：根据进程实际需要动态分配内存。

  • 存储分配情况的数据结构：空闲分区表、空闲分区链
  • 动态分区分配、回收算法
  • 内存的动态分配和回收，数据结构需要维护

• 动态可重定位分区分配：不修改程序即可进行紧凑，需要硬件支持

  • 紧凑：通过移动内存中作业的位置，把多个小分区拼成大分区的方法
  • 动态重定位及其分区分配算法

内碎片、外碎片

连续分配存储管理方式的分配算法（三大类）：

• 基于顺序搜索的动态分区分配算法☆：

  • 首次适应(first fit)：

    • 优点：简单，保留高地址大空闲区
    • 缺点：外碎片，查找效率低
  • 循环首次适应(next fit)：
    • 优点：减少查找开销，空闲分区分布均匀
    • 缺点：缺乏大空闲分区

  • 最佳适应(best fit)：

    • 优点：保留大空闲分区
    • 缺点：外碎片，查找效率低

  • 最坏适应(worst fit)：

    • 优点：不会出现太小的外碎片
    • 缺点：缺乏大空闲分区

• 基于索引搜索的动态分区分配算法：

  • 快速适应(quick fit)：将空闲分区按容量大小分别建链表

    • 优点：查找O(1)，保留大分区，无外碎片
    • 缺点：归还时算法复杂，仍有一定空间浪费

  • 伙伴系统(buddy system)：按2的幂次分配和回收。适用离散分配方式

  • 哈希算法：unordered_map<分区大小, 空闲分区链表>

• 动态可重定位分区分配算法：

空闲分区总和大于需求但无法找到单一连续可用区间时，进行紧凑

4.4 对换技术

对换：将内存中不能运行的进程或暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把具备运行条件的进程和数据换入内存，也称交换。

对换是改善内存利用率的有效措施

对换类型：

• 整体对换：即处理机低级调度（进程调度），上下文切换，以进程为单位

• 页面（分段）对换：按页或段进行对换，是请求分页、请求分段存储管理的基础

对换空间的管理

进程的换入换出：

• 换出：

  • 系统选择阻塞状态、优先级低的进程换出

  • 申请对换空间，启动磁盘将程序和数据对换

  • 修改PCB和内存分配表，释放内存

• 换入：

  • 选择就绪的换出进程
  • 申请内存空间，调入程序

4.5 分页存储管理方式

连续内存分配方式：单一连续分配、固定分区分配、动态分区分配、动态可重定位分区分配

离散内存分配方式：分页存储管理方式、分段存储管理方式、段页式存储管理方式

页面与物理块（页框）：

分页存储管理器将逻辑地址按页分割，将物理地址按块分割。以块为单位，将进程的若干个页装入不相邻的物理块中。产生页内碎片。

地址结构：

将逻辑地址分为：页号P | 位移量W。位移量即页内偏移。

页表：

系统为每个进程设立页表。页表实现从页号到物理块号的映射

地址变换机构：P140-141

• 基本的地址变换机构

逻辑地址分割后产生页号和偏移量，通过页表寄存器中页表长度判断是否越界中断，如无中断则通过页表始址查询页表得到物理块号，结合偏移量得到物理地址

• 具有快表的地址变换机构

先查快表(TLB、联想寄存器)再查页表

内存访问的有效时间：

设访问内存时间为 $t$ ，快表查询时间为 $\lambda$ ，命中率为 $a$ ：

• 不使用快表：$EAT=t+t$

• 使用快表： $EAT=a\lambda+\left(1-a\right)\left(\lambda+t\right)+t$

多级页表：

• 多级页表直将需要的页表调入内存

• 不同被调入的页表离散存储在内存空间中

• 外层页表偏移页号指向内层页表地址，最后指向内存空间

反置页表：存进程标识和页号，以物理块号为下标的顺序表

现代计算机系统允许一个进程逻辑地址空间远大于分配的内存空间。此时采用物理块号向页号反向查表更能节省页表的占用空间。在整个反置页表检索进程标识符和页号，找到匹配的页表项则将该项的物理块号（即下标）和页偏移地址合并作为物理地址。如果查不到，则表明该页号缺页，需要检索外部页表，并进行调页。

4.6 分段存储管理方式

分页的意义：使内存的离散分配成为可能，提高内存利用率

分段的意义：

• 方便编程：每个段始址为0，转移直观

• 信息共享：段可以包含完整逻辑，方便共享

• 信息保护：段整体作为保护对象

• 动态增长：数据段的动态增加

• 动态链接：分段是动态链接的前提

分段基本原理：

• 分段：分段地址划分决定了段的最大个数和每个段的最大内存长度（参考子网划分）

• 段表：记录段长和基址（在内存中的起始地址）P147

• 地址变换机构：同分页地址变换机构

分页和分段的区别：

• 页是信息的物理单位，对用户透明；段是信息的逻辑单位，满足用户需要

• 页的大小由系统决定；段的大小由信息性质划分

• 分页的用户程序地址空间是一维的；分段的用户程序地址空间有两维

信息共享：

不同进程需要共享一个段，只需要相同基址即可

4.7 段页式存储管理方式

逻辑地址：段号 | 段内页号 | 页内地址

段表：存放页表大小和页表始址

地址变换过程：P151

段页式存储管理方式中，访问一条指令或数据需要访问三次内存

存储器管理：

• 连续分配方式：

  • 单一连续分配

  • 分区式分配

    • 固定分区分配
    • 动态分区分配
      • 基于顺序搜索的动态分区分配：FF、NF、BF、WF
      • 基于索引搜索的动态分区分配：QF、Buddy、Hash
      • 动态可重定位分区分配

• 离散分配方式：虚拟的必要条件

  • 分页存储管理
    • 基本分页存储管理
    • 请求分页存储管理（虚拟存储器）
  • 分段存储管理
    • 基本分段存储管理
    • 请求分段存储管理（虚拟存储器）
  • 段页式存储管理

第五章 虚拟存储器

5.1 虚拟存储器概述

局部性原理：虚拟内存有效性的前提

• 时间局部性（短时间多次访问同一处）

• 空间局部性（短时间访问临近地址）

传统存储器的特征：

• 一次性：作业一次性全部装入内存

• 驻留性：作业完整驻留在内存

虚拟存储器：

定义：具有请求调入和置换功能，能从逻辑上对内存容量扩充的存储器系统

特征：

• 多次性：一个作业的程序和数据允许多次调入内存

• 对换性：允许作业的程序和数据在运行时被换进换出

• 虚拟性：能从逻辑上扩充内存容量

5.2 请求分页存储管理方式

硬件支持：

• 页表项除了物理块号外，添加状态位、访问字段、修改位和外存地址

• 缺页中断机构（特殊的中断响应机构）

  • 缺页中断发生在指令执行期并立即响应。普通中断在微操作内不响应
  • 执行一条指令可能发生多次缺页中断(ADD A B最高可达六次)

• 地址变换机构：添加缺页中断、页面写入或置换的过程

内存分配：

• 最小物理块数确定：取决于一次指令最多发生的缺页中断数

• 内存分配策略

  • 固定分配局部置换：进程内存大小固定，置换被分配的页

  • 可变分配全局置换：缺页即获得新的页面，直至内存占满开始置换

  • 可变分配局部置换：置换被分配的页，若缺页太多增加内存大小

• 物理块分配算法

  • 平均分配：进程平均分配内存

  • 按比例分配：进程按需求占比分配

  • 优先权分配：考虑紧迫程度

页面调入策略：何时调入、何处调入、调入过程、缺页率

影响缺页率的因素：页面大小、进程分配物理块数、页面置换算法、程序固有特性

5.3 页面置换算法☆

页面置换算法P163：

• 最佳置换OPT

• 先进先出置换FIFO

• 最近最久未使用LRU：移位寄存器值最小的被替换

• 最少使用LFU：移位寄存器pop_count最小的被替换

• 最近未使用NRU（简单CLOCK置换）：页表设置访问位，指针连成循环链表

• 改进CLOCK置换：页表设置访问位、修改位；访问位优先权高

页面缓冲算法PBA：

影响请求分页存储管理的因素：页面置换算法，磁盘写回频率，内存读入频率

系统保留一片空闲物理块用以降低经常缺页的进程的缺页率：

• 空闲页面链表：将进程换下的未修改页面暂存。减少读入频率

• 修改页面链表：将进程换下的修改页面暂存。减少读入频率；成批写入，减少写回频率

访问内存的有效时间：

设访问/更新快表时间 $\lambda$，访问内存需要时间 $t$ ，缺页中断时间 $\varepsilon$

• 页面在快表中： $EAT=\lambda+t$ 查快表==>访内存查值

• 页面在页表中： $EAT=\lambda+t+\lambda+t$ 查快表==>访内存查页表==>更新快表==>访内存查值

• 缺页：$EAT=\lambda+t+\varepsilon+\lambda+t$ 快表==>页表==>中断==>更新快表==>内存

设命中率 $a$，缺页率 $f$ ，则平均访问时间：

$EAT =a\left( \lambda +t \right)+\left( 1-a \right)\left( \left( 1-f \right)\left( 2\lambda +2t \right)+f\left( 2\lambda +2t+\varepsilon \right) \right)=\left( 2-a \right)\left( \lambda +t \right)+\varepsilon f\left( 1-a \right)$

5.4 抖动和工作集

抖动：在请求分页存储管理中，反复出现从主存中刚换出一页根据请求马上又换入的现象

表现：随着进程数增多，处理机利用率先增大后减小

产生原因：系统中运行进程太多，进程内存分配无法满足正常运行的基本需求

工作集：某段时间里进程实际要访问的页面集合

预防抖动的办法：

• 局部置换：不允许进程扩展页数，将抖动限制在一些进程上（效果差）

• 引入工作集算法：比较各进程工作集大小和实际得到的内存，再决定是否增加进程

• L=S准则：缺页平均间隔=调页平均时间

• 挂起：选择进程暂停

5.5 请求分段存储管理方式

请求分段中的硬件支持：

• 请求段表机制：

  • 段名、段长、段基址

  • 存取方式：控制读写执行，实行逻辑保护

  • 访问字段：访问频繁程度

  • 修改位：是否被修改

  • 存在位：是否在内存中

  • 增补位：该段是否在运行中发生了动态增长

  • 外存始址：盘块号

• 缺段中断机构

• 地址变换机构

分段的共享与保护：

• 共享：

  • 段表中增加进程计数count（参考shared_ptr）

  • 每个进程存取控制字段独立

  • 每个进程使用自己的段号访问

  • 共享：count++，增加表项；回收：count—，删除表项

• 保护：

  • 越界检查：检查段长

  • 存取控制检查：检查读写执行权限

  • 环保护机构：为段设置编号，高编号不允许调用低编号的段

第六章 输入输出系统

6.1 IO系统的功能、模型、接口

IO系统：用于管理诸如打印机扫描仪等IO设备，和诸如磁盘驱动器等存储设备

IO系统的基本功能：

• 方便用户使用（隐藏性）

  • 隐藏物理设备细节：IO设备是怎么进行读写的

  • 与设备的无关性：允许用户和OS适应不同的IO设备，即插即用

• 提高CPU和IO设备利用率（效率）

  • 提高CPU和IO设备利用率：设备间的独立性 ==> CPU-IO并行、IO-IO并行
  • 控制IO设备：独立进行IO而无需CPU干预，向上层提供统一接口

• 方便用户共享，保证系统有条不紊运行（正确性）

  • 确保对设备的正确共享：对独占设备（打印机）和共享设备（磁盘）的管理
  • 错误处理：处理电气偶然性错误

IO系统的层次结构：

• 用户层软件：属于应用程序

  • 向用户提供交互接口、库函数
  • 产生IO请求、格式化IO、Spooling

• 设备独立性软件：属于IO系统

  • 实现用户程序和设备驱动程序的统一接口、设备命名保护分配释放、分配存储空间

  • 映射、保护、分块、缓冲、分配

• 设备驱动程序：属于IO系统

  • 具体实现系统对设备发出的操作指令，驱动IO设备工作
  • 设置设备寄存器、检查设备状态
  • 将上层发来的IO请求转化为对IO设备的具体命令和参数

• 中断处理程序：属于IO系统

  • 用于保护被中断进程的CPU环境，在处理完毕后进行恢复

  • IO系统最底层，直接与硬件交互

• 设备控制器：属于硬件

  • 执行IO操作

IO系统接口：位于用户层软件和设备独立性软件之间

• 块设备接口：为磁盘等以块为基本单位提供数据传输的接口

• 流设备接口：为字符设备提供数据传输的接口

• 网络接口：为网络通信提供数据传输的接口

软硬件接口（RW/HW接口）：位于中断处理控制器和设备控制器之间

6.2 设备控制器和IO设备

IO设备：执行IO操作的机械部分（IO设备） + 控制IO的电子部件（IO设备控制器）

IO设备类型：

• 块设备（有结构可寻址）、字符设备（无结构不可寻址）、网络设备

• 独占设备（打印机）、共享设备（磁盘）、虚拟设备

• 存储设备、IO设备（输入设备、输出设备、交互设备）

• 低速设备、中速设备（打印机）、高速设备

IO设备与设备控制器的接口：

• 数据信号线：外部数据 ==> 转换器 ==> 缓冲器 ==> 数据信号线 ==> 设备控制器

• 控制信号线：规定设备即将执行的操作

• 状态信号线：设备在读、在写、或准备完成

设备控制器：

• 接收和识别命令（控制寄存器接受并译码）

• CPU、设备控制器与IO设备之间的数据交换

• 识别和报告设备状态（状态寄存器）

• 地址识别（地址译码器）

• 数据缓冲和差错控制

内存映像IO：内存地址和设备寄存器地址合并编址，简化设备控制器地址识别

IO通道：一种只具备IO处理能力的特殊处理机，减轻CPU负担

• 字节多路通道：多个设备以字节为单位轮转。适合低速设备

• 数组选择通道：一次只允许一个设备工作。适合高速设备

• 数组多路通道：两者结合

IO通道的瓶颈问题：由于通道昂贵，独占性且数量较少，造成其为系统吞吐量的瓶颈。

解决方法：复联增加设备到主机间的通路而不增加通道

6.3 中断处理程序和中断机构

中断是设备管理的基础：

• 外中断：CPU暂停正在执行的程序，而执行IO设备的中断处理程序，事后恢复

• 内中断（陷入）：计算故障、非法指令等，来源为CPU内部

中断向量表：为每种设备配备中断处理程序，将程序入口地址存放在中断向量表中

中断优先级：多中断源处理方式：屏蔽中断、嵌套中断

中断处理程序：进行上下文切换、对中断信号源测试、读取设备状态、修改进程状态

中断过程：

• 测定是否有未响应中断信号

• 保护被中断进程的CPU环境

• 查询中断向量表，转入相应的设备处理程序

• 进行中断处理

• 恢复CPU现场

6.4 设备驱动程序

主要任务：抽象

• 接收上层发来的抽象IO请求并转化为具体请求发送给设备控制器进行数据传送

• 检查IO请求合法性，了解IO设备状态，传递操作参数

• 对空闲的IO设备发出IO命令，或将请求挂在等待队列中

• 相应设备控制器的中断请求，并根据类型处理

对IO设备的处理方式：

• （轮询）程序IO方式：CPU不断查询IO状态直至设备空闲允许IO

• 中断驱动IO方式：设备控制器完成一字符IO后发送中断请求（CPU、IO并行）

• DMA方式：一批连续数据块全部传送结束时才中断CPU

• IO通道方式：控制多台设备与内存数据交换，完全接管CPU

6.5 设备独立性软件

设备独立性：应用程序中所用的设备，不局限于使用具体某个物理设备

主要任务：实现OS的物理设备独立性，可适应性和可扩展性

• 提供设备驱动程序的统一接口

• 缓冲管理：单缓冲、双缓冲、循环缓冲、公用缓冲池

• 差错控制：重试暂时性错误、记录永久性错误

• 对独立设备的分配和回收

• 独立于设备的逻辑数据块

设备分配中的数据结构：

• 设备控制表DCT：类似PCB理解，记录设备基本信息和当前状态

• 控制器控制表COCT：记录设备控制器的基本信息和当前状态

• 通道控制表CHCT：记录通道的基本信息和当前状态

• 系统设置表SDT：记录系统中所有设备类型和DCT入口等信息

设备分配考虑的因素：

• 设备固有属性：独占、共享、虚拟（独占设备改造成可共享的虚拟设备）

• 设备分配算法：FCFS、高优先级优先

• 安全性问题：可能造成死锁

6.6 用户层的IO软件

系统调用和库函数：

• 系统调用：应用程序取得OS任何服务的唯一途径，汇编级

• 库函数：对系统调用的进一步封装

假脱机系统Spooling：

多道程序系统使用若干个进程接管IO设备的IO，使用磁盘进行数据暂存

• 输入输出井：磁盘上开辟的区域，用于接收和传输数据

• 输入输出缓冲区：内存上开辟的区域，用于缓冲CPU和磁盘速度差异

• 输入输出进程：管理IO设备、缓冲区和输入输出井的数据流动

• 井管理程序：井的创建和取消

Spooling特点：

• 提高了IO速度：使用磁盘缓解了CPU和低速IO设备的速度差异

• 独占设备改造为共享设备：多个进程共享独占设备（如打印机）

• 实现了虚拟设备功能：多个进程认为独占了设备

6.7 缓冲区管理

缓冲区：用内存或硬件组成的小的存储区域

• 缓和CPU和IO设备速度不匹配的矛盾

• 减少CPU中断频率

• 解决数据粒度不匹配问题

• 提高CPU和IO设备之间的并行性

缓冲区管理：组织好缓冲区，并提供获得和释放缓冲区的手段

• 单缓冲区：缓冲区被填满后需要被取用才能继续填写

• 双缓冲区：第二块缓冲区填满后才被阻塞；或同时允许I、O操作

• 环形缓冲区：n缓冲区，采用队列的数组存储形式

• 缓冲池：缓冲池公用缓冲区以减少不同IO进程对内存的浪费

缓冲池组成：空白缓冲队列emq、输入队列inq、输出队列outq

缓冲区工作方式：hin收容输入、sin提取输出、hout收容输出、sout提取输出

6.8 磁盘存储器的性能和调度

数据的组织格式：

• 盘片≠盘面：1磁盘片有1-2个磁盘面

• 磁道=柱面：传统磁盘中内磁道存储密度高

• 扇区=盘块：一条磁道由若干扇区组成

磁盘类型：固定磁头磁盘（快），移动磁头磁盘（慢）

磁盘访问时间：

• 寻道时间： $T_s=m\times n+s$

• 旋转延迟时间： $T_\tau=\frac{1}{2r}$

• 传输时间： $T_t=\frac{b}{rN}$

平均访问时间： $T_a=T_s+T_\tau+T_t$

磁盘调度算法：

• 先来先服务FCFS：效果很差

• 最短寻道时间优先SSTF：产生饥饿现象

• 扫描算法（电梯调度）SCAN：由外而内扫描再由内而外扫描

• 循环扫描CSCAN：一直同向扫描，避免极端情况等待时间过长

• NStepSCAN：N个队列间FCFS，队列内SCAN。解决高密度磁盘磁壁粘着现象

• FSCAN：N=2的NStepSCAN，当前队列和新增需求队列

第七章 文件管理

7.1 文件和文件系统

文件系统：操作系统中与管理文件有关的软件和数据。

数据的组成部分：数据项、记录、文件

• 数据项：最低级的数据组织方式

  • 基本数据项：用于描述一个对象的某种属性
  • 组合数据项：基本数据项的组合

• 记录：一组相关数据项的组合，用于描述对象的某方面属性

• 文件：文件系统最大的数据单位，描述一个对象集

  • 有结构文件：记录项的集合

  • 无结构文件：字符流

  • 文件属性：类型、长度、物理位置、建立时间

  • 文件名和扩展名

  • 文件类型：

    • 用途（系统、用户）
    • 数据形式（源、目标、可执行）

    • 存取属性（只执行、只读、读写）

    • 组织方式（普通、目录、特殊）

文件系统的层次结构：

• 对象及其属性（底层）：管理文件及其物理地址

• 对对象操纵和管理的软件集合（中间层）：管理存储，权限，共享，逻辑==>物理转化

• 文件系统的接口（最高层）：向用户提供命令接口和程序接口

文件操作：

• 基本文件操作：

  • 创建：分配外存空间，父目录创建目录项，目录项记录文件名和外存地址等属性
  • 删除：删除父目录下对应目录项，回收外存空间
  • 读：根据文件名查找目录得到外存位置

  • 写：根据文件名查找目录得到外存位置

  • 设置文件读写位置：文件目录项中存有读写指针

• 打开和关闭操作：避免在多次读写时重复检索目录

  • 打开：将文件的属性从外存拷贝到内存的文件打开表表项中，并将编号返回用户

  • 关闭：把文件从文件打开表表目中删除

• 其他文件操作：

  • 修改文件属性：改变文件名、拥有者、权限，查询文件状态等

  • 目录操作：创建目录，删除目录，更改工作目录

  • 实现文件共享，对文件进行系统操作

7.2 文件的逻辑结构

文件的逻辑结构：区别于文件的物理结构，是从用户角度出发所观察到的文件组织形式。文件的逻辑结构管理的是记录。

文件逻辑结构分类：

• 按结构分类：

  • 有结构文件（记录式文件）：定长记录、不定长记录（记录长度而非文件长度）

  • 无结构文件（流式文件）：长度以字节为单位

• 按组织方式分类：在用户看来，文件是什么结构

  • 顺序文件：定长随机访问，不定长查找一条记录平均检索 $\frac{N}{2}$ 次

  • 索引文件：针对不定长记录建立索引表，以根据索引进行折半查找，索引速度快

  • 索引顺序文件：$u$ 级顺序索引平均检索 $\frac{u}{2}\sqrt[u]{N}$ 次

  • 直接文件、哈希文件

7.3 文件目录

文件目录：文件控制块的有序集合

目录文件：存放文件目录的文件

目录管理：实现按名存取、提高目录检索速度、文件共享、允许不同用户的文件重名

文件控制块FCB：用于描述和控制文件的数据结构

• 基本信息：文件名、物理位置、逻辑结构、物理结构

• 存取控制信息：拥有者、核准用户、一般用户的读写执行权限

• 使用信息：建立日期、修改日期、打开状态、状态信息

索引节点inode：减少目录文件占用的盘块数，加快检索

使用了inode后的文件目录只存储文件名和inode编号，通过inode编号可以在inode区找到具体的文件信息

磁盘索引节点和内存索引节点

目录结构：

• 单级目录结构：整个文件系统就一张目录表，每个文件占一项

• 两级目录结构：主目录MFD记录每个用户文件目录UFD的信息

• 树形目录结构：主目录为根目录，数据为树叶，目录项记录文件或目录的FCB

  • 路径名：从根目录到目标文件的路径

  • 当前目录：工作目录

  • 相对路径：从当前目录到目标文件的路径

  • 绝对路径：从根目录到目标文件的路径

  • 目录操作：创建、删除（空/非空）、改变当前目录、移动目录、链接、查找

目录查询技术：

• 线性检索法P239：在每个文件目录中顺序查找目录项

• Hash方法

7.4 文件共享

文件共享：允许多个用户（进程）共享同一份文件而只保留一份副本。

• 基于DAG的文件共享：拷贝文件的物理地址（拷贝FCB）

• 硬链接：文件目录存同一份inode编号，inode进行链接计数。删除一份不会消失

• 软链接（符号链接）：建立LINK文件储存被共享文件路径

7.5 文件保护

第八章 磁盘存储器管理

8.1 文件的物理结构

外存的组织方式：决定了文件的物理结构

• 连续组织方式：（连续）每个文件分配一片连续的盘块

  • 文件目录项存储第一个盘块和长度

  • 优点：便于顺序访问，速度快，支持定长记录文件随机存取

  • 缺点：盘块连续，预知文件大小，增删记录慢，不能动态增长，需要紧凑

• 链接组织方式：（离散）将文件存储到离散的盘块中

  • 隐式链接：每个盘块存储下一个盘块的指针

    • 文件目录项存储第一个盘块和最后一个盘块的指针
    • 优点：离散存储，便于顺序访问

    • 缺点：随机存取效率低

    • 改进：多个连续盘块形成一个簇，减少指针开销并提高检索速度

  • 显式链接：在内存中建长度为物理块数的FAT表，表项存放下一盘块指针，而凡是某个文件的起始盘块号都存放在文件FCB的“物理地址字段”中 ==> 7.3

    • 优点：查找记录在内存中进行，大量减少磁盘访问，检索速度快
    • 缺点：FAT很大，占用内存空间，仍然不支持随机存储

  • FAT与NTFS的概念

  • 优点：消除外碎片，支持文件动态增长，适合增删改

  • 缺点：只适合顺序存储，可靠性差，读取时寻道次数多，额外存储空间开销大

• 索引组织方式：（离散）为每个文件分配索引块（一盘块），顺序存储全部盘块号

  • 单级索引组织：索引块顺序存储各盘块号，文件容量较小

  • 多级索引组织：一级索引块存储二级索引盘块号，小容量文件浪费存储空间

  • 增量索引式组织：混合索引，全面照顾大中小型文件
    • 直接地址10个
    • 一次间址、二次间址、三次间址各1个

8.2 文件存储空间管理

任何文件组织方式都必须要为文件分配盘块，需要知道磁盘中哪些盘块是可供分配的。

• 空闲表法：（连续）存第一块空闲盘号和盘块数 ==> 4.3

• 空闲链表法：

  • 空闲盘块链：（离散）将空闲盘块组成链表，效率很低
  • 空闲盘区链：（连续）将连续的盘块组成盘区，记录块首地址、盘块数、双向链表

• 位示图法：使用1bit标识盘块使用情况，本质是一个二维数组

• 成组链接法：（大型系统）内存常驻空闲盘块号栈（记录栈和栈顶指针，栈内存空闲盘块号）。分配到最后一个时取出栈底盘块中的有用信息替换栈后再分配；回收满了则将栈信息存入当前回收的盘块并将当前回收盘块作为新栈底。

8.3 提高磁盘IO速度的途径

8.4 提高磁盘可靠性的技术

8.5 数据一致性控制