第1章 计算机系统概述

一、操作系统的基本概念

1、操作系统的概念

• 操作系统：指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合
• 为上层用户，应用程序提供简单易用的服务
• 是计算机系统中最基本的系统软件

2、操作系统的特征

• 并发和共享是最基本的两个特征，两者互为存在条件：
  • 资源共享是以程序的并发为条件的，若系统不允许程序并发执行，则自然不存在资源共享问题
  • 若系统不能对资源共享实施有效的管理，则必将影响到程序的并发执行，甚至根本无法执行
• 如果失去了并发性，则一个时间段内系统中只需运行一道程序，那么就失去了实现虚拟性的意义了。因此，没有并发性，就谈不上虚拟性
• 如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性

（1）并发

• 并发：两个或多个事件在同一时间间隔内发生
• 并行：系统具有同时进行运算或操作的特性，在同一时刻能完成两种或两种以上的工作
  • 可并行的有【处理机与设备】【处理机与通道】【设备与设备】
  • 不可并行的有【进程与进程】
• 引入进程的目的是使程序能够并发执行
• 注意：
  • 单核 CPU 同一时刻只能执行一个程序，各个程序只能并发地执行
  • 多核 CPU 同一时刻可以同时执行多个程序，多个程序可以并行地执行

（2）共享

• 共享：指系统中的资源可供内存中多个并发执行的程序共同使用
  • 互斥共享方式：
    • 规定一段时间内只允许一个进程访问该资源【称为临界资源】
    • A 访问完并释放该资源后，才允许另一进程访问
    • 如：计算机系统中的大多数物理设备及某些软件中所有的栈、变量和表格
  • 同时访问方式：
    • 宏观上，一段时间内由多个进程“同时”访问某类资源
    • 微观上，进程之间可能交替对该资源进行访问
    • 如：磁盘设备，一些可重入代码编写的文件

（3）虚拟

• 虚拟：指将一个物理上的实体变为若干逻辑上的对应物
• 用于实现虚拟的技术称为虚拟技术
  • 时分复用技术：如虚拟处理器
  • 空分复用技术：如虚拟存储器

（4）异步

• 进程的异步性：由于资源有限，进程的执行不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进

3、操作系统的功能和目标

（1）操作系统作为计算机系统资源的管理者

1）处理器管理

• 处理机的分配和运行都以进程（或线程）为基本单位
• 对处理器的管理可归结为对进程的管理
• 主要功能：进程控制+进程同步+进程通信+死锁处理+处理机调度

2）存储器管理

• 为了给多道程序的运行提供良好的环境，方便用户使用及提高内存的利用率
• 主要功能：内存分配与回收+地址映射+内存保护+共享和内存扩充

3）文件管理

• 计算机的信息都是以文件的形式存在的
• 操作系统重负责文件管理的部分称为文件系统
• 主要功能：文件存储空间的管理+目录管理+文件读写管理和保护

4）设备管理

• 主要是完成用户的I/O请求，方便用户使用各种设备，提高设备的利用率
• 主要功能：缓冲管理+设备分配+设备处理+虚拟设备

（2）操作系统作为用户与计算机硬件系统之间的接口

1）命令接口

• 用户利用这些操作命令来组织和控制作业的执行
• 联机命令接口【交互式命令接口】：
  • 适用于分时或实时系统的接口
  • 由一组键盘操作命令组成
  • 用户发送一个命令，系统就执行一次，主要特点是交互性
• 脱机命令接口【批处理命令接口】：
  • 适用于批处理系统的接口
  • 由一组作业控制命令组成
  • 用户一次性发送命令清单，系统按清单执行，中途不能干预

2）程序接口

• 可以在程序中进行系统调用来使用程序接口
• 普通用户不能直接使用程序接口，只能通过程序代码间接使用
  

（3）操作系统实现了对计算机资源的扩充

• 裸机：没有任何软件支持的计算机，仅构成计算机系统的物质基础
• 在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器
• 扩充机器/虚拟机：覆盖了软件的机器

二、操作系统的发展历程

1、手工操作阶段

• 此阶段无操作系统
• 所有工作都要人工干预
• 缺点：
  • 用户独占全机，资源利用率低
  • CPU 等待手工操作，CPU 的利用不充分

2、批处理阶段

• 为了解决人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，出现了批处理系统

（1）单道批处理系统

• 引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出
• 特点：自动性、顺序性、单道性
• 优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升
• 缺点：
  • 内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序
  • CPU 有大量的时间是在空闲等待 I/O 完成，资源利用率依然很低

（2）多道批处理系统

• 允许多个用户将若干个作业提交给计算机系统集中处理
• 当某道程序因请求 I/O 操作而暂停运行时，通过中断机制，CPU 转去运行另一道程序
• 特点：多道、宏观上并行、微观上串行
• 优点：
  • 资源利用率高，多道计算机共享计算机资源，从而使各种资源得到充分利用
  • 系统吞吐量大，CPU 和其他资源保持“忙碌”状态
• 缺点：
  • 用户的响应时间较长
  • 不提供人机交互能力

3、分时操作系统

• 计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互
• 特点：同时性（多路性）、交互性、独立性、及时性
• 优点：
  • 用户请求可以被即时响应，解决了人机交互问题
  • 允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在
• 缺点：
  • 不能优先处理一些紧急任务
  • 操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性

4、实时操作系统

• 为了能在某个时间限制内完成某些紧急任务而不需要时间片排队
• 硬实时系统：某个动作必须绝对地在规定的时刻（或规定的时间范围）发生【飞机的飞行自动控制系统】
• 软实时系统：能够接受偶尔违反时间规定且不会引起任何永久性的损害【飞机订票系统、银行管理系统】
• 特点：及时性、可靠性
• 优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队

5、其他几种操作系统

• 网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享（如文件共享）和各台计算机之间的通信（如：Windows NT 就是一种典型的网络操作系统，网站服务器就可以使用）

• 分布式操作系统：主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务

• 个人计算机操作系统：如 Windows XP、MacOS，方便个人使用

三、操作系统的运行环境

1、处理器运行模式

• CPU 执行两种不同性质的程序：内核程序和应用程序
• 操作系统的内核程序是系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态
• 为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态

（1）两种指令

1）特权指令

• 指不允许用户直接使用的指令
• 如：对 I/O 设备操作指令、存取特殊寄存器的指令、有关访问程序状态的指令、置中断指令、关中断指令、清内存指令、置时钟指令

2）非特权指令

• 允许用户直接使用的指令
• 不能直接访问系统中的软硬件资源，只限于访问用户的地址空间
• 如：访管指令（trap）

（2）两种处理器状态

1）核心态【管态、内核态】

• 此时运行的是内核程序，可以执行特权指令
• 只能在核心态运行的指令和程序：
  • 时钟管理相关的指令【置时钟指令】
  • 中断机制相关的指令【时钟中断程序】
  • 原语相关的指令
  • 系统控制的数据结构与处理【进程调度程序】【进程切换】【缺页处理程序】【系统调用命令】

2）用户态【目态】

• 此时运行的是用户程序，只能执行非特权指令
• 在用户态运行的指令和程序/发生的事件：
  • 命令解释程序【属于命令接口，面向用户】
  • 访管/Trap 指令，跳转指令，压栈指令
  • 广义指令 (系统调用) 的调用
  • 外部中断，缺页

3）如何变态

• 内核态 ---> 用户态：执行一条特权指令——修改 PSW 的标志位为“用户态”，这个动作意味着操作系统将主动让出 CPU 使用权
• 用户态 ---> 内核态：由“中断”引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回 CPU 的使用权
• 注意：
  • CPU 中的程序状态字寄存器（PSW），其中有个二进制位，1 表示“内核态”，0 表示“用户态”
  • 需要操作系统介入的地方，都会触发中断信号

（3）操作系统的内核

• 内核：是计算机上配置的底层软件，是操作系统最基本、最核心的部分。实现操作系统内核功能的那些程序就是内核程序

1）与硬件关联紧密的模块

• 时钟管理：实现计时功能
• 中断处理：负责实现中断机制
• 原语：
  • 是一种特殊的程序
  • 处于操作系统最底层，是最接近硬件的部分
  • 该程序运行具有原子性（运行只能一气呵成，不可中断）
  • 运行时间较短，调用频繁

2）对系统资源进行管理的功能

• 设备管理：完成设备的请求和释放，以及设备启动等功能
• 进程管理：完成进程的创建，撤销，阻塞及唤醒等功能
• 存储器管理：完成内存的分配，回收以及获取作业占用内存区大小及地址等功能

2、中断和异常

（1）基本概念

（2）中断处理和子程序调用的比较

中断处理	子程序调用
中断处理程序与被中断的当前程序是相互独立的	子程序与主程序是同一程序的两部分，它们属于主从关系
中断的产生是随机的	子程序的调用是通过调用指令 (CALL) 引起的，是由程序设计者事先安排的
中断处理的过程需要有专门的硬件	完全属于软件处理过程
中断处理程序的入口地址可由硬件向量法产生向量地址，再由向量地址找到入口地址	子程序的入口地址是由 CALL 指令中的地址码给出的
中断隐指令保存 PC 的内容	CALL 指令保存 PC 的内容，先将当前 PC 值压入栈，再将 PC 设置为入口地址
需对同时检测到的多个中断请求进行裁决	无这种操作

3、系统调用

（1）基本概念

• 操作系统对应用程序和程序员提供的接口
• 系统调用需要触发陷入指令（Trap）
• OS 通过提供系统调用避免用户程序直接访问外设
• 在用户程序中，凡是与资源有关的操作（存储分配、I/O 传输及管理文件等）都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成，保证系统的稳定性和安全性
• 每个系统调用都有唯一的系统调用号

（2）系统调用与库函数的区别

• 库函数：
  • 是语言或应用程序的一部分，可以运行在用户空间中
  • 许多库函数都会使用系统调用来实现功能
  • 有的库函数没有使用系统调用
• 系统调用：
  • 是操作系统的一部分，是内核为用户提供的程序接口，运行在内核空间
  • 系统调用要完成上下文的切换和状态的转换，因此未使用系统调用的库函数，执行效率较高

（3）按功能分类

• 设备管理：完成设备的请求或释放+设备启动
• 文件管理：完成文件的读+写+创建+删除
• 进程控制：完成进程的创建+撤销+阻塞+唤醒
• 进程通信：完成进程之间的信息传递或信号传递
• 内存管理：完成内存的分配+回收+获取作业占用内存区大小及始址

（4）系统调用的过程

1. 传参
2. 陷入指令/Trap/访管【执行系统调用】，发生在用户态
3. 由操作系统内核程序处理系统调用请求，发生在内核态
4. 返回应用程序
   

（5）系统调用与一般过程调用的区别

1）运行状态不同

• 一般过程调用的调用过程和被调用过程运行在同一系统状态【用户态或内核态】
• 系统调用的调用过程是运行在用户态，被调用过程是运行在内核态

2）软中断进入机制

• 一般的过程调用可直接由调用过程转向被调用过程
• 系统调用不允许由调用过程直接转向被调用过程，一般通过软中断机制，先进入操作系统内核，经内核分析后才转向相应命令处理程序

3）返回及重新调度

• 一般过程调用被调用结束后，返回调用点继续执行
• 系统调用被调用完后，要对系统中所有运行进程重新调度
• 只有当调用进程仍具有最高优先权才返回调用过程继续执行

四、操作系统结构

• 微内核定义：只把核心功能放入内核，其余功能用用户进程的形式运行在用户态
• 微内核优点：
  • 内核足够小
  • 基于C/S模式
  • 应用机制与策略分离原理
  • 采用面向对象技术
• 微内核缺点：
  • 执行效率不高
  • 开销较大

五、操作系统引导

• 操作系统引导：指计算机利用 CPU 运行特定程序，通过程序识别硬盘，识别硬盘分区，识别硬盘分区上的操作系统，最后通过程序启动操作系统
  
  常见操作系统的引导过程如下：

1. 激活 CPU：激活的 CPU 读取 ROM 中的 boot 程序，将指令寄存器置为 BIOS (基本输入/
   输出系统) 的第一条指令，即开始执行 BIOS 的指令
2. 硬件自检：BIOS 程序在内存最开始的空间构建中断向量表，接下来的 POST 过程要用到中断功能，然后通过通电自检，检查硬件是否出现故障
3. 加载带有操作系统的硬盘：BIOS 将控制权交给启动顺序排在第一位的存储设备，CPU 将其引导扇区的内容加载到内存中
4. 加载主引导记录（MBR）：硬盘以特定的标识符区分引导硬盘和非引导硬盘【MBR 告诉 CPU 去硬盘的哪个主分区去找操作系统】
5. 扫描硬盘分区表，并加载硬盘活动分区：MBR 包含硬盘分区表，以特定标识符区别活动分区和非活动分区，MBR 识别含有操作系统的硬盘分区（活动分区）后，加载并将控制权交给活动分区
6. 加载分区引导记录（PBR）：读取活动分区的第一个扇区【分区引导记录 PBR】，其作用是寻找并激活分区根目录下用于引导操作系统的程序 (启动管理器)
7. 加载启动管理器
8. 加载操作系统
   注意：

• 自检程序 ---> 引导装入程序/自举装入程序 ---> 引导程序 ---> 操作系统
• 操作系统被装入 RAM 中
• 自举程序 BIOS 装在 ROM 中
• 引导程序装在硬盘中

六、虚拟机

• 虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（VM），每个虚拟机器都可以独立运行一个操作系统

第2章 进程与线程

一、进程与线程

1、进程的概念与特征

（1）进程的定义

• 进程是程序的一次执行过程
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
• 进程是具有独立功能的程序在一个数据集合上运行的过程
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
• 为什么引入进程：
  • 为了使多道程序并发执行，提高资源利用率和系统吞吐量
  • 为了可以对并发执行的程序加以描述和控制，实现操作系统的并发性和共享性

（2）进程的特征

• 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的【最基本的特征】
• 并发性：内存中有多个进程实体，各进程可并发执行
• 独立性：进程是能独立运行、获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进【操作系统要提供“进程同步机制”来解决异步问题】

（3）进程与程序的区别

• 进程：是动态的，是程序的一次执行过程【如：可同时启动多次 QQ】
• 程序：是静态的，就是存放在磁盘里的可执行文件【如：QQ.exe】
• 同一个程序多次执行会对应多个进程

（4）进程的组成

• 一个进程实体（进程映像）由 PCB、程序段、数据段组成
• 进程是动态的，进程实体是静态的
• 进程实体反映了进程在某一时刻的状态

1）进程控制块（PCB）

• 定义：
  • PCB 是进程实体的一部分，是进程存在的唯一标志
  • 进程创建时，操作系统为它新建一个 PCB，该结构常驻内存
• 包含：
  1. 进程描述信息：
     • 进程标识符 PID：标识各个进程，每个进程都有一个并且唯一的标识号
     • 用户标识符 UID：进程归属的用户，用户标识符主要为共享和保护服务
  2. 进程控制和管理信息：
     • 进程当前状态：描述进程状态信息，作为 CPU 调度的依据
     • 进程优先级：描述进程抢占 CPU 的优先级
     • 代码运行入口地址
     • 程序的外存地址
     • 进入内存时间
     • CPU 占用时间
     • 信号量使用
  3. 资源分配清单：
     • 有关内存地址空间和虚拟地址空间的状况
     • 所打开文件的列表和所使用的输入/输出设备信息
  4. 处理机相关信息【CPU 的上下文】：
     • CPU 中各寄存器的值
     • 当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中以便进程重新执行时，能从断点处继续执行
• 组织方式：
  • 链接方式：
    • 把同一状态的 PCB 链成一个队列，不同状态对应不同的队列
    • 也可把处于阻塞态的进程的 PCB，根据阻塞原因，排成多个阻塞队列
  • 索引方式：
    • 将同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB
    • 如就绪索引表，阻塞索引表

2）程序段

• 能被进程调度程序调度到 CPU 执行的程序代码段
• 程序可以被多个进程共享，即多个进程可以运行同一个程序

3）数据段

• 可以是进程对应的程序加工处理的原始数据
• 可以是程序执行时产生的中间或最终结果

2、进程的状态与转换

（1）五种状态

• 运行态 Running：该时刻进程占用 CPU
• 就绪态 Ready：进程获得了除处理机外的一切所需资源，一旦得到处理机，就可以立即运行
• 阻塞态 Blocked：该进程正在等待某一事件发生而暂停运行，如等待某个资源可用（不包括 CPU）或等待 I/O 完成
• 创建态 New：进程正在被创建时的状态
• 结束态 Exit：进程正在从系统中消失时的状态

（2）状态转换

• 就绪态 ---> 运行态：
  • 进程被调度，获得处理机资源（分派处理机时间片）
• 运行态 ---> 就绪态：
  • 时间片用完后，不得不让出处理机
  • 可剥夺的 OS 中，当有更高优先级的进程就绪时，调度程序将正在执行的进程转换为就绪态
• 运行态 ---> 阻塞态：
  • 该过程是主动行为
  • 进程请求某一资源（如外设） 的使用和分配时
  • 等待某一事件的发送时（如 I/O 操作的完成）
  • 进程以系统调用的方式请求 OS 提供服务，这个过程系统从用户态转换为核心态
• 阻塞态 ---> 就绪态：
  • 该过程是被动行为，需要其他相关进程的协助
  • I/O 操作结束或中断结束时
  • 发送了阻塞队列等待的事件，如发送了 V 操作，信号量+1，然后阻塞队列被唤醒到就绪队列中

3、进程控制

• 进程控制：主要功能是对系统中的所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能
• 原语：进程控制用的程序段【执行期间不允许中断，是一个不可分割的基本单位】
  • 可以用 “关中断指令”和“开中断指令”这两个特权指令实现原子性

（1）进程的创建

1）定义及过程

• 允许一个进程创建另一个进程
• 允许子进程继承父进程所拥有的资源
• 创建原语：
  • 为新进程分配一个进程标识号，申请一个空白的 PCB【PCB 是有限的】
  • 为该进程分配运行时所必需的资源，如内存、文件、I/O 和 CPU 时间等
  • 初始化 PCB，如标志、状态、控制、优先级信息
  • 将 PCB 插入就绪队列

2）对应事件

• 用户登录：分时系统中，用户登录成功，系统会为其建立一个新的进程
• 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
• 系统提供服务：用户向操作系统提出某些请求时，会建立一个进程处理该请求
• 用户程序的应用：由用户进程主动请求创建一个子进程
• 注意：设备分配不需要创建进程

（2）进程的终止

1）定义及过程

• 当子进程被终止时，其在父进程处继承的资源应当还给父进程
• 当父进程被终止时，该父进程的子进程就变为孤儿进程
• 终止原语：
  • 查找需要终止的进程的 PCB
  • 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程
  • 如果其还有子进程，全部终止
  • 将该进程所拥有的全部资源都归还给操作系统
  • 将其从 PCB 所在队列中删除

2）对应事件

• 正常结束：进程任务完成并自己准备退出运行
• 异常结束：进程运行时发生了异常事件
• 外界干预：如操作系统干预、父进程请求或父进程终止

（3）进程的阻塞

1）定义及过程

• 当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待
• 一旦被阻塞等待，只能由另一个进程唤醒
• 阻塞原语：
  • 找到将要被阻塞进程标识号对应的 PCB
  • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
  • 将该 PCB 插入到阻塞队列中去

2）对应事件

• 需要等待系统系统分配某种资源
• 需要等待相互合作的其他进程完成工作

（4）进程的唤醒

1）定义及过程

• 进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成
• 处于阻塞状态的进程是绝对不可能叫醒自己
• 如果某进程正在等待 I/O 事件，需由别的进程发消息给它
• 只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它
• 唤醒原语：
  • 在该事件的阻塞队列中找到相应进程的 PCB
  • 将其从阻塞队列中移出，并置其状态为就绪状态
  • 把该 PCB 插入到就绪队列中，等待调度程序调度
• 注意：阻塞原语和唤醒原语必须成对使用

2）对应事件

• 等待的事件发生

4、进程通信

• 进程通信：指进程之间的信息交换
• 各进程拥有的内存地址空间相互独立
• 为了保证安全，一个进程不能直接访问另一个进程的地址空间

（1）低级通信方式

• PV 操作

（2）高级通信方式

1）共享存储

• 设置一个共享内存区域，并映射到进程的虚拟地址空间
• 要互斥地访问共享空间【通信进程自己负责实现】
• 基于数据结构的共享：
  • 比如共享空间里只能放一个长度为 10 的数组
  • 速度慢、限制多
  • 是一种低级通信方式
• 基于存储区的共享：
  • 操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统
  • 灵活性高、速度快
  • 是一种高级通信方式

2）信息传递

• 进程间的数据交换以格式化的消息（Message）为单位
• 进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换
• 隐藏了通信实现细节，对用户透明，简化了通信程序的设计
• 应用最广泛
• 直接通信方式：发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从队列取得消息
• 间接通信方式：发送进程将消息发送给某个中间实体【信箱】

3）管道通信

• 管道只能采用半双工通信，某一时间段内只能实现单向的传输【如果要实现双向同时通信，则需要设置两个管道】
• 各进程要互斥地访问管道【由操作系统实现】
• 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程
• 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程
• 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱，解决方案：
  1. 一个管道允许多个写进程，一个读进程
  2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）
• 管道是一种特殊文件，可以克服使用文件通信的两个问题：
  1. 限制管道的大小：管道文件是一个固定文件大小的缓冲区
  2. 读进程也可能工作得比写进程快
• 管道只能由创建进程访问【子进程可继承父进程的管道，并可用它来与父进程通信】
• 从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据

5、线程和多线程模型

（1）线程的基本概念

• 线程可理解为轻量级进程
• 线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位
• 引入线程后的变化：
  • 并发性：进程内的各线程之间也可以并发，从而进一步提升了系统的并发度
  • 资源分配、调度：进程是资源分配的基本单位，线程是处理机调度的基本单位
  • 系统开销：线程间并发，如果是同一进程内的切换，则不需要切换进程环境，系统开销小
• 多 CPU 计算机中，各个线程可占用不同的 CPU
• 每个线程都有一个唯一的标识符和一个线程控制块【记录线程执行的寄存器和栈等现场状态】
• 不同的线程可以执行相同的程序
• 线程也有就绪、阻塞、运行三种基本状态，和进程之间的转换是一样的
• 线程共享进程地址空间和资源，线程自己没有独立的地址空间

（2）线程的组成和控制

1）线程控制块 TCB

• 功能：每个线程配置一个 TCB，用于记录控制和管理线程的信息
• 组成：
  • 线程标识符
  • 一组寄存器，包括程序计数器、状态寄存器和通用寄存器
  • 线程运行状态
  • 优先级
  • 线程专有存储区，线程切换时用于保存现场
  • 堆栈指针，用于过程调用时保存局部变量及返回地址

2）线程的控制

• 创建线程：
  • 用户程序启动时，通常仅有一个称为初始化线程的线程正在执行，其主要功能是用于创建新线程
• 终止线程：
  • 通常，线程被终止后并不立即释放它所占有的资源，只有当进程中的其他线程执行了分离函数后，被终止线程才与资源分离，此时的资源才能被其他线程利用
  • 被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行

（3）线程的实现方式

1）用户级线程（ULT）

• 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
• 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预
• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在【“用户级线程”就是“从用户视角看能看到的线程”】
• 优点：
  • 线程切换不需要转到内核空间，节省了模式切换的开销
  • 调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法
  • 与操作系统平台无关，对线程管理的代码是属于用户程序的一部分
• 缺点：
  • 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
  • 不能发挥多 CPU 的优势，内核每次分配给一个进程的仅有一个 CPU，因此进程中仅有一个线程执行
• 形成多对一模型
  

2）内核级线程（KLT）

• 内核级线程的管理工作由操作系统内核完成
• 内核级线程的切换必然需要在核心态下才能完成
• 操作系统会为每个内核级线程建立相应的TCB，通过 TCB 对线程进行管理【“内核级线程”就是“从操作系统内核视角看能看到的线程”】
• 优点：
  • 能发挥多 CPU 的优势，内核能同时调度同一进程的多个线程并行执行
  • 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用 CPU，也可以运行其他进程中的线程
  • 内核支持线程具有很小的数据结构和栈，线程切换快、开销小
  • 内核本身也可采用多线程技术，可以提高系统的执行速度和效率
• 缺点：
  • 同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大【用户进程的线程在用户态执行，而线程调度和管理是在内核实现】
• 形成一对一模型
  

3）组合方式

• 内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程
• 用户级线程通过时分多路复用内核线程实现
• 结合 KLT 和 ULT 的优点，又克服各自的不足
• 线程库：为程序员提供创建和管理线程的 API，实现方法：
  • 在用户空间中提供一个没有内核支持的库【调用库内的一个函数只导致用户空间中的一个本地函数的调用】
  • 实现由操作系统直接支持的内核级的一个库【调用库中的一个 API 函数通常会导致对内核的系统调用】
• 形成多对多模型

（4）多线程模型

• 由于用户级线程和内核级线程的连接方式不同，从而形成了三种不同的多线程模型
• 操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位
  

1）多对一模型

• 定义：多个用户级线程映射到一个内核级线程，且一个进程只被分配一个内核级线程
• 优点：
  • 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
• 缺点：
  • 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
  • 任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个CPU 上运行

2）一对一模型

• 定义：一个用户级线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程
• 优点：
  • 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强
  • 多线程可在多核处理机上并行执行
• 缺点：
  • 每创建一个用户线程，就要创建一个对应的内核线程，开销大
  • 线程切换由操作系统内核完成，需要切换到核心态，线程管理的成本高，开销大

3）多对多模型

• 定义：n 用户及线程映射到 m 个内核级线程（n >= m），每个用户进程对应 m 个内核级线程。
• 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点
• 用户级线程是“代码逻辑”的载体
• 内核级线程是“运行机会”的载体
• 一段“代码逻辑”只有获得了“运行机会”才能被CPU 执行
• 内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有所有内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

二、CPU 调度

1、调度的概念

（1）基本概念

• 调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将 CPU 分配给它运行，以实现进程并发地执行
• CPU 调度是多道程序操作系统的基础，是 OS 设计的核心问题

（2）调度的层次

1）高级调度（作业调度）

• 是内存与辅存的调度，从外存上处于后备队列的作业中调度
• 每个作业只调入调出一次
• 通常存在于多道批处理系统中
• 内存与磁盘之间交换数据的转态转换：就绪态到挂起态

2）中级调度（内存调度）

• 目的：提高内存利用率和系统吞吐量
• 将暂时不能运行的进程调到外存等待，设为挂起态
• 当具备运行条件且内存稍有空闲时，重新调入内存，修改状态为就绪态，挂在就绪队列上
• 是存储器管理中的对换功能

3）低级调度（进程调度）

• 从就绪队列中选取一个进程，调用频率很高
• 各种 OS 都必须配置这种调度

4）三种调度的联系

• 作业调度为进程活动做准备，进程调度使进程正常活动
• 中级调度将暂时不能运行的进程挂起，中级调度处于另外两个调度之间
• 调用频率：作业调度 < 内存调度 < 进程调度
• 进程调度是最基本的，不可或缺

2、调度的实现

（1）调度程序（调度器）

• 调度程序：用于调度和分配 CPU 的组件
  
• 组成：
  • 排队器：按策略将就绪进程排成一个或多个队列
  • 分派器：从就绪队列中取出进程，并分配 CPU
  • 上下文切换器：在对处理机进行切换时，会发生两对上下文的切换：
    • 第一对：将当前进程的上下文保存到 PCB 中，再装入分派程序的上下文，以便分派程序运行
    • 第二对：移出分派程序的上下文，将选新进程的 CPU 现场信息装入 CPU 的各个相应寄存器

（2）调度的时机

1. 需要进行进程调度与切换的情况：
   • 当前运行的进程主动放弃处理机：
     • 进程正常终止
     • 运行过程中发生异常而终止
     • 进程主动请求阻塞（如等待 I/O）
   • 当前运行的进程被动放弃处理机：
     • 分给进程的时间片用完
     • 有更紧急的事需要处理（如 I/O 中断）
     • 有更高优先级的进程进入就绪队列
2. 不能进行进程调度与切换的情况：
   • 在处理中断的过程中【中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换】
   • 进程在操作系统内核程序临界区中【内核程序临界区一般是用来访问某种内核数据结构的，若不尽快释放访问的临界资源，可能会影响到 OS 内核的其他管理工作】
   • 在原子操作过程中（原语）

（3）进程调度的方式

1. 非抢占调度方式【非剥夺方式】：只允许进程主动放弃处理机
   • 优点：实现简单，系统开销小，适用于早期的批处理系统
   • 缺点：不适合分时和大多数的实时系统
2. 抢占调度方式【剥夺方式】：当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程
   • 优点：提高系统吞吐率和响应率
   • 缺点：必须遵循一定的原则（优先权、短进程优先、时间片原则等）

（4）进程的切换与过程

• 狭义的进程调度：从就绪队列中选中一个要运行的进程【这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换】
• 广义的进程调度：包含了选择一个进程和进程切换两个步骤，进程切换的过程主要完成了：
  1. 对原来运行进程各种数据的保存
  2. 对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）
• 闲逛进程：
  • 在进程切换时，如果系统中没有就绪进程，就会调用闲逛进程一直运行【PID 为 0】，并在指令周期后测试中断
  • 优先级最低，只要有进程就绪，就会立即让出 CPU
  • 不需要 CPU 之外的资源，不会被阻塞

（5）两种线程的调度

• 用户级线程调度：
  • 内核不知道线程的存在，选择一个进程，并给予时间控制
  • 由进程中的调度程序决定哪个线程运行
  • 线程切换在同一进程中进行，仅需少量的机器指令
• 内核级线程调度：
  • 内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程
  • 超过时间片，强制挂起该线程
  • 需要完整的上下文切换、修改内存映像、使高速缓存失效，导致若干数量级的延迟

3、进程的上下文切换

（1）基本概念

• 进程上下文切换：
  • 完成 CPU 切换到另一个进程时，保存当前进程状态并恢复另一个进程的状态的任务
  • 采用进程 PCB 表示，包括寄存器的值、进程状态和内存管理信息等
  • 内核将旧进程状态保存在其 PCB 中，然后加载经调度而要执行的新进程的上下文
  • 进程的运行环境发生实质性变化
• 上下文切换通常是计算密集型的，需要消耗大量的 CPU 时间
• 有些处理器提供多个寄存器组，上下文切换只需要简单改变当前寄存器组的指针，不需要用到磁盘和主存

（2）上下文切换的场景

• 某个进程时间片耗尽时
• 进程在系统资源不足时，要等到资源满足后才可以运行
• 进程通过 sleep 将自己主动挂起
• 有优先级更高的基础运行时
• 发送硬件中断时

（3）上下文切换的流程

1. 挂起一个进程，保存 CPU 上下文，包括 PC 和其他寄存器
2. 更新 PCB 信息
3. 把进程的 PCB 移到相应的队列（如就绪队列，阻塞队列）
4. 加载另一个进程执行，更新其 PCB
5. 跳转到新进程 PCB 中的 PC 所指向的位置执行
6. 恢复处理机上下文
   

（4）上下文切换和模式切换

• 模式切换时，CPU 逻辑上可能还在执行同一进程
• 上下文切换只能发生在内核态【多任务 OS 的一个必需特性】
• 用户态与内核态之间的切换为模式切换【没有改变当前的进程】

（5）调度和切换的区别

• 先有资源的调度，才有进程的切换
• 调度：决定资源分配给哪个进程的行为；是一种决策行为
• 切换：实际分配的行为；是一种执行行为

4、调度的目标

（1）CPU 利用率

• CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}
• 利用率=\frac{忙碌的时间}{总时间}
  
  注意：计算作业完成时间时，要注意 CPU 与设备、设备与设备之间时可以并行的

（2）系统吞吐量

• 表示单位时间内 CPU 完成作业的数量
• 系统吞吐量=\frac{总共完成了多少作业}{总共花了多少时间}
  

（3）周转时间

• 周转时间包括四个部分：
  • 作业在外存后备队列上等待作业调度（高级调度）的时间
  • 进程在就绪队列上等待进程调度（低级调度）的时间
  • 进程在 CPU 上执行的时间
  • 进程等待 I/O 操作完成的时间
• 后三项在一个作业的整个处理过程中，可能发生多次
• 周转时间=作业完成时间-作业提交时间
• 平均周转时间=\frac{作业1的周转时间+...+作业n的周转时间}{n}
• 带权周转时间=\frac{作业周转时间}{作业实际运行时间}
• 平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}

（4）等待时间

• 指进程/作业处于等待处理机状态时间之和
• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间
• 对于作业来说，等于建立进程后的等待时间 + 作业在外存后备队列中等待的时间

（5）响应时间

• 指从用户提交请求到首次产生响应所用的时间
• 在交互式系统中，一般采用响应时间作为衡量调度算法的准则之一

5、调度算法

（1）先来先服务 FCFS

1）算法思想

• 主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）

2）算法规则

• 按照作业/进程到达的先后顺序进行服务
  

3）用于作业/进程调度

• 用于作业调度时，考虑的是哪个作业先到达后备队列
• 用于进程调度时，考虑的是哪个进程先到达就绪队列

4）是否可抢占

• 非抢占式

5）优缺点

• 优点：
  • 公平、算法实现简单
  • 有利于 CPU 繁忙型作业
  • 一般适用于早期批处理系统
• 缺点：
  • 对长作业有利，对短作业不利【排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好】
  • 不利于 I/O 繁忙型作业

6）是否会导致饥饿

• 不会
• 饥饿：某进程/作业长期得不到服务

（2）短作业优先 SJF

1）算法思想

• 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

2）算法规则

• 最短的作业/进程优先得到服务【要求服务时间最短】
  

3）用于作业/进程调度

• 即可用于作业调度，也可用于进程调度
• 用于进程调度时称为“短进程优先（SPF, Shortest Process First）算法

4）是否可抢占

• SJF 和 SPF 是非抢占式算法
• 短剩余时间优先算法（SRTN）是抢占式的
  

5）优缺点

• 优点：
  • 在所有进程都几乎同时到达时，采用 SIF/SPF 调度算法的平均等待时间、平均周转时间最少
  • 抢占式的 SJF/SPF 调度算法【最短剩余时间优先算法】的平均等待时间、平均周转时间最少
  • 一般适用于早期批处理系统
• 缺点：
  • 对短作业有利，对长作业不利
  • 可能产生饥饿现象
  • 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

6）是否会导致饥饿

• 会
• 如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象
• 如果一直得不到服务，则称为“饿死”

（3）高响应比优先

1）算法思想

• 综合考虑作业/进程的等待时间和要求服务的时间

2）算法规则

• 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
• 响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}
  

3）用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

4）是否可抢占

• 非抢占式的算法
• 因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

5）优缺点

• 等待时间相同时，要求服务时间越短，响应比越高，有利于短作业，类似于 SJF
• 要求服务时间相同时，等待时间越长，响应比越高，类似于 FCFS
• 响应比可以随等待时间的增加而提高，克服了饥饿现象
• 适用于分时操作系统

6）是否会导致饥饿

• 不会

（4）优先级

1）算法思想

• 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

2）算法规则

• 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

3）用于作业/进程调度

• 既可用于作业调度，也可用于进程调度

4）是否可抢占

• 非抢占式：直到由于自身原因而让出 CPU 时，更高优先级的进程才可运行
• 抢占式：有更高优先级的进程进入就绪队列时，立即停止正在运行的进程
  • 静态优先级：
    • 优先级是在创建时确立的
    • 优点：简单易行，系统开销小
    • 缺点：不够精确，可能出现优先级低的进程长时间得不到调用
  • 动态优先级：
    • 优先级随进程的推进或等待时间的增加而改变，以获得更好的性能
    • 系统进程 > 用户进程
    • 交互型进程 > 非交互型进程
    • I/O 型进程 > 计算型进程

5）优缺点

• 优点：
  • 用优先级区分紧急程度、重要程度，适用于实时操作系统
  • 可灵活地调整对各种作业/进程的偏好程度
• 缺点：
  • 若源源不断地有高优先级进程到来，则可能导致饥饿

6）是否会导致饥饿

• 会

（5）时间片轮转 RR

1）算法思想

• 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

2）算法规则

• 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100 ms）
• 若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

3）用于作业/进程调度

• 用于进程调度
• 只有作业放入内存建立了相应的进程后，才能被分配处理机时间片

4）是否可抢占

• 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法
• 由时钟装置发出时钟中断来通知 CPU 时间片已到

5）优缺点

• 优点：
  • 公平，响应快
  • 适用于分时操作系统
• 缺点：
  • 由于高频率的进程切换，因此有一定开销
  • 不区分任务的紧急程度
• 若时间片足够大：所有进程都能在一个时间片内执行完毕，退化为 FCFS
• 若时间片足够小：CPU 将在进程间过于频繁的切换，使 CPU 的开销增大

6）是否会导致饥饿

• 不会

（6）多级队列

1）算法思想

• 在系统中设置多个就绪队列
• 按不同类型或性质的进程固定分配到不同的就绪队列
• 每个队列可实施不同的调度算法
• 在多 CPU 系统中，可以很方便为每个 CPU 设置一个单独的就绪队列

（7）多级反馈队列

1）算法思想

• 对其他调度算法的折中权衡

2）算法规则

1. 设置多级就绪队列，赋予每个队列不同的优先级【第 1 级队列最高，依次降低】
2. 赋予各个队列的进程运行时间片的大小各不相同【优先级越高的队列，每个进程的时间片越小】
3. 每个队列采用 FCFS 算法：
   • 新进程进入内存后，首先放入第 1 级队列的队尾，等待调度
   • 在第一个时间片结束时尚未完成，将其转入第 2 级队列的末尾，依次类推
   • 当进程被降到第 n 级队列后，采用时间片轮转方式运行
4. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片

3）用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

4）是否可抢占

• 抢占式的算法
• 在 k 级队列的进程运行过程中，若更上级的队列（1~k-1 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾

5）优缺点

• 对各类型进程相对公平（FCFS 的优点）
• 每个新到达的进程都可以很快就得到响应（RR 的优点）
• 短进程只用较少的时间就可完成（SPF 的优点）
• 不必实现估计进程的运行时间（避免用户作假）
• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程
• 拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样I/O 型进程就可以保持较高优先级

6）是否会导致饥饿

• 会

（8）常见算法的对比

三、同步与互斥

1、基本概念

• 因为并发进程是异步的，为了协调进程之间的相互制约关系，所以引入同步互斥
• 同步【直接制约关系】：
  • 指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系
• 互斥【间接制约关系】：
  • 当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许访问临界资源
• 临界资源：一次仅允许一个进程使用的资源，对其访问过程分为：
  • 进入区：负责实现互斥，设置标志
  • 临界区：进程中访问临界资源的那段代码
  • 退出区：负责实现互斥，清楚标志
  • 剩余区：代码中的其余部分
• 同步机制应遵循的准则：
  • 空闲让进：临界区空闲，允许一个进程进入【运行进程访问空闲的临界资源】
  • 忙则等待：有进程进入临界区时，其他进程需等待【两个进程不能同时进入临界资源】
  • 有限等待：请求访问的进程应保证在有限时间内进入临界区，防止无限等待【进程等待进入临界区的时间是有限的】
  • 让权等待【原则上遵循，非必须】：进程不能进入临界区时，应该立即释放处理器，防止进程忙等待【不能进入临界区的执行态进程立即放弃 CPU】

2、实现临界区互斥的方法

（1）软件实现方法

1）单标志法

• 设置一个公用整型变量 turn，指示允许进入临界区的进程编号
• 每次只允许一个进程进入临界区
  
• 违背“空闲让进”

2）双标志先检查法

• 设置一个布尔型数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿
  
• 违背“忙则等待”【进入区“检查”后，“上锁”前可能发生进程切换】

3）双标志后检查法

• 先“上锁”，后“检查”，避免上诉问题
  
• 解决“忙则等待”
• 违反“空闲让进”和“有限等待”，会导致饥饿现象

4）Peterson 算法

• 利用 flag 解决互斥访问问题，利用 turn 解决饥饿问题
  
• 违反“让权等待”

（2）硬件实现方法

1）中断屏蔽法

• 关中断：防止其他进程进入临界区
  
• 优点：简单、高效
• 缺点：
  • 限制了 CPU 交替执行程序的能力，因此系统效率会明显降低
  • 不适用于多处理机
  • 只适用于操作系统内核进程，不适用于用户进程【因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险】

2）硬件指令——TestAndSet 指令（TS 指令）

• 为每个临界资源设置一个共享布尔变量 lock，表示该资源的两种状态【true 表示被占用】
  
• 若刚开始 lock 是 false，则 TS 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区
• 若刚开始 lock 是 true，则执行 TS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”
• 优点：
  • 实现简单，TS 指令将“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作
  • 适用于多处理系统
• 缺点：不满足“让权等待”原则

3）硬件指令——Swap 指令（XCHG 指令）

• 为每个临界资源设置一个共享布尔变量 lock，初值 false
• 在每个进程中设置一个局部变量 key，初值 true，用于与 lock 交换信息
  
• 优点：
  • 简单，容易验证其正确性
  • 适用于多处理机系统
  • 支持系统中有多个临界区，只需为每个临界区设立一个布尔变量
• 缺点：
  • 不满足“让权等待”原则
  • 从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，导致饥饿

3、互斥锁

• 是解决临界区最简单的工具
• 通常采用硬件机制实现
• 获得锁：acquire，释放锁：release，都是原子操作
• 使用互斥锁解决经典同步问题
  
• 优点：
  • 进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高
  • 适用于多处理系统
• 缺点：忙等待

4、信号量

（1）PV 操作定义

• 信号量：表示系统中某种资源的数量
• P 操作【wait() 原语】：将信号量值 S 减 1，表示申请占用一个资源
• V 操作【signal() 原语】：将信号量值 S 加 1，表示释放一个资源，即使用完资源后归还资源

（2）信号量分类

1）整型信号量

• 该信号量被定义为一个用于表示资源数目的整型量 S
• 该机制不遵循“让权等待” 的准则【只要 s≤0，就会不断循环测试】
  

2）记录型信号量

• 需要一个用于代表资源数目的变量 value
• 需要一个进程链表 L，用于链接所有等待该资源的进程
• S.value 的初值表示系统中某种资源的数目
  
• P 操作【wait () 原语】：
  • 如果 S.value<0，表示已经没有可用资源，则进程调用block原语进行自我阻塞【运行态 ---> 阻塞态】，主动放弃处理机，并插入该类资源的 S.L
  • 遵循“让权等待”
• 举例：当信号量的值为 2 时，表示有 2 个资源可以使用；当信号量的值为-2 的时候，表示有两个进程正在等待使用这个资源
• V 操作【signal () 原语】：
  • 如果加 1 后 S.value≤0，表示仍有进程正在等待该资源，调用 wakeup 原语唤醒 S.L 中的第一个进程【阻塞态 ---> 就绪态】

（3）信号量的应用

1）利用信号量实现互斥

• 互斥信号量 S 初始值=1，表示临界区只允许一个进程进入，从而实现互斥
• 把对临界资源的访问操作置于 P (S) 和 V（S）之间
• P 操作和 V 操作必须成对出现
• 缺少 P 操作：不能保证对临界资源的互斥访问
• 缺少 V 操作：导致临界资源永远得不到释放，使因等待该资源而阻塞的进程永远得不到唤醒
  

2）利用信号量实现同步

• 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
• 设置同步信号量 S 的初始值 = 0
• 在“前操作”之后执行 V (S)
• 在“后操作”之前执行 P (S)
  
  

3）利用信号量实现前驱关系

• 信号量用来描述程序或语句之间的前驱关系
• 要为每一对前驱关系各设置一个同步信号量
• 在“前操作”之后对相应的同步信号量执行 V 操作
• 在“后操作”之前对相应的同步信号量执行 P 操作
  

5、经典同步问题【王道 25 版 p103】

（1）生产者——消费者问题

1）问题描述

• 一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区
• 进程每次从缓冲区中取出一个产品并使用
• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待
• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待
• 缓冲区是临界资源，各进程必须互斥地访问

2）问题分析

• 关系分析：
  • 生产者和消费者对缓冲区的互斥访问是互斥关系
  • 生产者和消费者之间相互协作，是同步关系
• 整理思路：确定 P、V 操作的大致顺序
  
• 信号量设置：
  • 互斥信号量：mutex 初始值 1，用于控制互斥访问缓冲池
  • 同步信号量：full 初始值 0，表示非空缓冲区（产品）的数量
  • 同步信号量：empty 初始值 n，表示空闲缓冲区的数量
    
• 注意：
  • 实现互斥的 P 操作一定要在实现同步的 P 操作之后
  • V 操作不会导致进程阻塞，因此两个 V 操作顺序可以互换

6、管程

（1）基本概念

• 引入管程的原因：
  • 信号量机制存在的问题：编写程序困难、易出错
  • 管程的特性保证了互斥，程序员无须自己实现，并提供条件变量，更灵活地实现进程同步
• 管程：定义了共享数据结构和能为并发进程执行（在该数据结构上）的一组操作
• 管程的组成：
  • 管程的名称
  • 局部于管程内部的共享数据结构或者共享变量说明
  • 对管程内的数据结构进行操作的一组过程（函数）
  • 对局部于管程内部的共享数据设置初始值的语句
• 管程的基本特征：
  • 局部于管程的数据只能被局部于管程的过程所访问
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程，从而实现互斥【编译器实现该特性】
    

（2）管程中设置的条件变量

• 定义：将一个进程进入管程后被阻塞的原因定义为条件变量 condition
• 管程中设置了多个条件变量，每个条件变量保存了一个等待队列【记录因该条件变量而阻塞的所用进程】
• 两种操作：
  • x.wait：x 对应的条件不满足，将正在调用管程的进程插入到 x 条件的等待队列，并释放管程
  • x.signal：唤醒一个因 x 条件而阻塞的进程
• 与信号量的相似点：
  • wait/signal 类似于信号量的 P/V 操作，实现进程的阻塞/唤醒，但不能说和 PV 操作相同
• 与信号量的不同点：
  • 条件变量没有值，仅实现“排队等待”功能
  • 信号量有值，这个值反映了剩余资源数
  • 在管程中，剩余资源数用共享数据结构记录
    

四、死锁

1、死锁的概念

（1）基本概念

• 死锁：指多个进程因为竞争资源而造成的一种僵局【互相等待对方手里的资源】
• 死锁的充分条件：资源分配图中每种资源只有 1 个，出现了环路
• 死锁和饥饿的共同点：都是进程无法顺利向前推进的现象
• 死锁和饥饿的不同点：
  • 发生饥饿的进程可以只有 1个；发生死锁的进程必然大于等于 2 个
  • 发生饥饿的进程能处于就绪态【长期得不到 CPU】，也可能处于阻塞态【长期得不到 I/O 设备】；发生死锁的进程必然处于阻塞态

（2）死锁产生的原因

1. 系统资源的竞争【空间上】：
   • 系统中不可剥夺资源（磁带机、打印机等）不足以满足多个进程
   • 只有对不可剥夺资源的竞争才可能产生死锁
2. 进程推进顺序非法【时间上】：
   • 请求和释放资源的不当，会导致死锁
   • 信号量使用不当，会导致死锁

（3）死锁产生的必要条件

产生死锁必须同时满足以下四个条件：

• 互斥条件：
  • 只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）
  • 像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）
• 不可剥夺条件：
  • 进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
• 请求并保持条件：
  • 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
• 循环等待条件：
  • 存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

（4）死锁的处理策略

• 死锁预防：破坏死锁产生的四个必要条件中的一个或几个
• 死锁避免：用某种方法防止系统进入不安全状态，从而避免死锁
• 死锁检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁
  

2、死锁预防

1. 破坏互斥条件：

   • 不可行
   • 有些资源（打印机等临界资源）根本不能同时访问
   • 为了系统安全，很多时候必须保护这种互斥性

2. 破坏不可剥夺条件：

   • 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请
   • 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺
   • 缺点：
     • 实现起来比较复杂
     • 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU
     • 反复地申请和释放资源会增加系统开销，降低系统吞吐量
     • 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

3. 破坏请求并保持条件：

   • 采用预先静态分配法：
     • 进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行
     • 一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了
   • 缺点：资源利用率低，可能导致饥饿
   • 改进：允许进程只获得运行初期所需的资源后，便可开始运行

4. 破坏循环等待条件：

   • 采用顺序资源分配法：
     • 首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源
     • 同类资源（编号相同）一次申请完
   • 原理分析：
     • 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源
     • 已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象
   • 缺点：
     • 不方便增加新的设备，因为可能需要重新分配所有的编号
     • 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
     • 必须按规定次序申请资源，用户编程麻烦

3、死锁避免

（1）系统安全状态

• 安全序列：
  • 指如果系统按照这种序列分配资源，则每个进程都能顺利完成
  • 只要能找出一个安全序列，系统就是安全状态
  • 安全序列可能有多个
• 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利的执行下去【如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态】
• 处于不安全状态未必发生死锁
• 发生死锁时一定是处于不安全状态

（2）银行家算法

• 详见王道书 25 版 p152
  

• 例题
  
  
  

4、死锁检测和解除

（1）死锁的检测

• 资源分配图：
  • 圆圈代表进程，框表示一类资源
  • 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源
  • 从资源到进程的有向边称为分配边，表示该类资源已有一个资源分配给该进程
    
• 简化资源分配图可检测系统状态是否为死锁：
  • 在资源分配图中，找出既不阻塞又不是孤点的进程 Pi【即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量】
  • 然后消去该进程所有请求边和分配边
  • 若能消去图中所有的边，则该图可完全简化
• 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

（2）死锁的解除

1. 资源剥夺法：挂起某些死锁进程，并抢占它的资源
2. 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源
3. 进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非剥夺

第3章 内存管理

一、内存管理概念

1、基本原理和要求

（1）基本概念

• 内存管理：是操作系统对内存的划分和动态分配
• 目的：
  • 为了更好地支持多道程序并发执行
  • 方便用户
  • 提高内存利用率
• 功能：
  • 内存空间的分配与回收：由 OS 完成主存储器空间的分配与管理
  • 地址转换：存储管理将逻辑地址转换为物理地址
  • 内存空间的扩充：利用虚拟存储技术从逻辑上扩充内存
  • 内存共享：允许多个进程访问内存的同一部分
  • 存储保护：保证多道作业在各自的存储空间运行，互不干扰
• 分配方式：
  • 连续分配：
    • 单一连续分配 ---> 固定分区分配【单道发展到多道 OS】 ---> 动态分区分配【为了适应大小不同的程序】
  • 不连续分配：
    • 分页存储管理 ---> 分段存储管理 ---> 段页存储管理

（2）程序的链接与装入

• 创建进程首先要将程序和数据装入内存，将用户源程序变为可在内存中执行的程序，需要的步骤如下：
  

1. 编译：由编译程序将用户源代码编译成若干目标模块
2. 链接：由链接程序将编译后形成的一组目标模块，以及它们所需的库函数链接在一起，形成一个完整的装入地址，有三种方式：
   • 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开
     
   • 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
     
   • 运行时动态链接：在程序执行中需要改目标模块时，才对它进行链接，优点时便于修改和更新，便于实现对目标模块的共享
     
3. 装入：由装入程序将装入模块装入内存运行，有三种方式：
   • 绝对装入：
     • 在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码装入程序按照装入模块中的地址，将程序和数据装入内存
     • 程序中的逻辑地址与实际内存地址完全相同
     • 只适用于单道程序环境
       
   • 可重定位装入【静态重定位】：
     • 编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址
     • 装入时对地址进行“重定位”，将逻辑地址变换为物理地址【地址变换是在装入时一次完成的】
     • 装入时，必须给作业分配所要求的全部内存空间
       
   • 动态运行时装入【动态重定位】：
     • 编译、链接后的装入模块的地址都是从 0 开始的
     • 装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行
     • 因此装入内存后所有的地址依然是逻辑地址
     • 这种方式需要一个重定位寄存器的支持
       

（2）逻辑地址与物理地址

• 逻辑地址【相对地址】：编译后，每个目标模块都从 0 号单元开始编址，这称为该目标模块的逻辑地址
• 逻辑地址空间【虚拟地址空间】：链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始的编址空间【32 位系统，范围 0 ~ 2^{32}-1 】
• 物理地址空间：内存中物理单元的集合，它是地址转换的最终地址
• 地址重定位：装入程序将可执行代码装入内存时，将逻辑地址转换成物理地址的过程
• 不同进程可以有相同的逻辑地址，这些逻辑地址映射到主存的不同位置
• 进程运行时，看到和使用的是逻辑地址

（3）进程的内存映像

• 当一个进程调入内存运行时，就构成了进程的内存映像
• 组成要素：
  • 代码段：程序的二进制代码【代码段是只读的，可以被多个进程共享】
  • 数据段：程序运行时加工处理的对象，包括全局变量和静态变量
  • 进程控制块 PCB：存放在系统区，OS 通过 PCB 控制和管理进程
  • 堆：用来存放动态分配的变量【通过调用 malloc 函数动态地向高地址分配空间】
  • 栈：用来实现函数调用的【从用户空间的最大地址往低地址方向增长】
    
    

（4）内存保护

• 目的：确保每个进程都有一个单独的内存空间
• 方法一：在 CPU 设置一对上、下限寄存器，存放用户进程在主存中的上限和下限地址，判断 CPU 访问的地址是否越界
• 方法二：采用重定位寄存器（也称基址寄存器）和界地址寄存器（也称限长寄存器）
  • 重定位寄存器存放进程的起始物理地址
  • 界地址寄存器存放进程的最大逻辑地址
  • 逻辑地址 + 重定位寄存器的值 = 实际物理地址
    

（5）内存共享

• 只有只读区域的进程空间可以共享
• 可重入代码【也称纯代码】：允许多个进程同时访问但不允许被任何进程修改的代码，不属于临界资源
• 可重入程序通过减少交换数量来改善系统性能
• 实现方式：段的共享，内存映射文件，基于共享内存的进程通信

2、内存空间的分配管理方式

（1）连续分配方式

• 定义：为一个用户程序分配一个连续的内存空间
• 特点：
  • 用户程序在主存中都是连续存放的
  • 存储密度大
• 外部碎片：内存中产生的小内存块，存在于所有分区的外部
• 内部碎片：分配给某进程的内存区域中，没有被用上的部分

1）单一连续分配

• 定义：内存被分为系统区与用户区
  • 系统区：仅供 OS 使用，通常在低地址部分
  • 用户区：内存中仅有一道用户程序
• 优点：
  • 简单、无外部碎片
  • 不需要进行内存保护
• 缺点：
  • 只能用于单用户、单任务的操作系统
  • 有内部碎片
  • 存储器的利用率极低
    

2）固定分区分配

• 定义：将用户内存空间大小划分若干固定大小的分区，每个分区只装入一道作业
• 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
• 分区大小不等：增加了灵活性，可以满足不同大小的进程需求，根据常在系统中运行的作业大小情况进行划分
• 为了方便分配与回收，建立一张分区使用表，每个表项对应一个分区，包括分区大小、起始地址及状态
  
• 优点：实现简单，无外部碎片
• 缺点：
  • 程序太大可能放不下任何一个分区
  • 程序太小也要占用一个完整分区，产生内部碎片
  • 不能实现多进程共享一个主存区，存储空间利用率低

3）动态分区分配

• 定义：进程在装入内存时，根据进程的实际需要，动态地为之分配内存，并使分区的大小正好适合进程的需要
• 优点：支持多道程序，无内部碎片
• 缺点：有外部碎片【可通过紧凑技术处理】
• 回收内存分区时，可能会遇到四种情况【原则：相邻的空闲分区要合并】：
  • 回收区之后有相邻的空闲分区
  • 回收区之前有相邻的空闲分区
  • 回收区前、后都要相邻的空闲分区
  • 回收区前、后都没有相邻的空闲分区
• 基于顺序搜索的分配算法：

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序
最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片，算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程，算法开销大（原因同上）
邻近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列（可排列成循环链表）	不用每次都从低地址的小分区开始检索，算法开销小（原因同首次适应）	内存低、高地址部分的空闲分区以同等概率被分配，划分为小分区，导致内存高地址部分没有大空闲区可用

• 基于索引搜索的分配算法【大、中型系统】：

算法	算法思想	优点	缺点
快速适应算法	首先根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表；然后从链表中取出第一块进行分配	查找效率高、不产生内部碎片	回收分区时，需要有效合并分区，算法比较复杂，系统开销较大
伙伴系统	规定所有分区的大小均为 2 的 k 次幂 操作系统学习笔记（九）：连续内存分配——伙伴系统_伙伴系统是一种内存分配算法,其特点是-CSDN博客
哈希算法	根据空闲分区链表的分区规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针。分配时，根据所需分区大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链表

（2）基本分页存储管理

1）分页思想

• 将内存空间分为若干固定大小（如 4 KB）的分区，称为页框、页帧或物理块
• 内存空间中的每个页框有一个编号，称为页框号、物理块号，从 0 开始
• 进程的逻辑地址空间也分为与块大小相等的若干区域，称为页或页面
• 进程的逻辑地址空间中的每个页面有一个编号，称为页号，从 0 开始
• 进程在执行时需要申请内存空间，即要为每个页面分配内存中的可用页框，形成一一对应的关系
• 特点：
  • 不产生外部碎片
  • 产生内部碎片（很小）
  • 分页是面向计算机的

2）页表

• 为了能知道进程的每个页面在内存中存放的位置，OS 要为每个进程建立一张页表
• 进程的每个页面对应一个页表项
• 每个页表项由页号和块号组成【大小相同】，记录了页面在内存中对应的物理块号
• 页表项连续存放，因此页号可以是隐含的，不占用存储空间【i 号页表项存放地址=页表始址 + i * 页表项大小】
• 页表的作用是实现从页号到物理块号的地址映射
  
• 计算：每个页表项占多少字节？
  

3）地址结构

• 页号 + 页内偏移量
  
• 如果有 K 位表示“页内偏移量”，则说明该系统中，一个页面的大小是 2^K 个内存单元
• 如果有 M 位表示“页号”，则说明在该系统中，一个进程最多允许有 2^M 个页面
• 地址结构决定了虚拟内存的寻址空间有多大
• 页号 = 逻辑地址 / 页面长度（取除法的整数部分）
• 页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）
• 页面大小刚好是 2 的整数幂有什么好处？
  • 逻辑地址的拆分更加迅速：如果每个页面大小为 2^k B，用二进制数表示逻辑地址，则不需要除法运算可知，末尾 k 位为页内偏移量，其余部分是页号
  • 物理地址的计算更加迅速：根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可得到最终的物理地址
• 页面太小会使进程的页面数过多，页表过长，占用大量内存，增加硬件地址转换的开销，降低页面换入/换出的效率
• 页面太大会使页内碎片增多，降低内存的利用率

4）基本地址变换机构

• 任务：将逻辑地址转换为内存中的物理地址
• 页表寄存器（PTR）：
  • 存放页表在内存的始址 F 和页表长度 M
  • 单 CPU 系统中只设置一个
  • 进程未执行时，F 和 M 存放在本进程的 PCB 中；当进程被调度执行时，将装入 PTR
    
• 设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下：
  1. 计算页号 P = A / L、页内偏移量 W = A % L
  2. 判断页号是否越界：若 P >= M，产生越界中断，否则，继续执行
  3. 在页表中查询页号对应的页表项，确定页面存放的物理块号【页号 P 对应的页表项地址 = F + P * 页表项长度，取出该页表项内容 b，即为物理块号 】
  4. 计算物理地址 E = b * L + W，并用物理地址访存【页面在内存中的始址 = b * L 】
• 整个地址变换过程均由硬件自动完成
• 页式管理中地址空间是一维的
• 两次访存：
  • 第一次：访问页表，确定所存取的数据或指令的物理地址
  • 第二次：访问目标内存单元

5）具有快表的地址变换机构

• 快表（TLB）【相联存储器】：
  • 具有并行查找能力的高速缓冲存储器
  • 用来存放当前访问的若干页表项，以加速地址变换的过程
  • 基于局部性原理
    

1. 计算页号、页内偏移量
2. 检查页号合法性
3. 查快表，若找到匹配的页号，直接读出对应的物理块号，一次访存
4. 若没有找到，访问主存的页表，读出页表项后，同时将其存入快表，两次访存
   

6）两级页表

• 逻辑地址结构：一级页号 + 二级页号 + 页内偏移量
  
  
• 在页表的每个表项中，存放的是进程的某页对应的物理块号
• 在外层页表（页目录）的每个表项中，存放的是每个页表分页的始址
• 需要增设一个外层页表寄存器【页目录基址寄存器】，用于存放页目录始址
• 利用页目录和页表实现从逻辑地址到物理地址的转换：
  • 从 PCB 中读出页目录表始址
  • 根据页目录号查页目录表，从而找到对应页表的地址【第一次访存】
  • 根据二级页号查页表，从而找到对应的页表项【第二次访存】
  • 将页表项中的物理块号和页内偏移量拼接，即为物理地址，再访问对应内存单元【第三次访存】
• 注意：一般来说各级页表的大小不能超过一个页面
  
• 若没有快表机构，N 级页表访问一个逻辑地址需要 N + 1 次访存

（3）基本分段存储管理方式

1）分段思想

• 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从 0 开始编址
• 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以互不相邻【段内要求连续，段间不要求连续】
• 由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高
• 特点：
  • 方便编程、信息保护和共享
  • 方便动态链接、增长
  • 会产生外部碎片

2）段表

• 每个进程都有一张逻辑空间与内存空间映射的段表
• 进程的每个段对应一个段表项，记录了该段在内存中的起始位置【基址】和段的长度
• 各个段表项的长度相同，因此段号可以是隐含的，不占用存储空间
• 段表用于实现从逻辑段到物理内存区的映射
  

3）地址结构

• 段号 + 段内偏移量
  
• 段号的位数决定了每个进程最多可以分几个段
• 段内偏移量的位数决定了每个段的最大长度是多少
• 段号和段内偏移量必须由用户显示提供【在高级程序设计语言中，这个工作由编译程序完成】

4）地址变换机构

• 任务：实现进程从逻辑地址到物理地址的变换功能
• 段表寄存器：
  • 存放段表始址 F 和段表长度 M
  • 存放于进程的 PCB 中
    
• 地址变换过程：
  1. 从逻辑地址 A 中取出前几位为段号 S，后几位为段内偏移量 W
  2. 判断段号是否越界，若段号 S >= 段表长度 M，则产生越界中断，否则继续执行
  3. 在段表中查询段号对应的段表项【段号 S 对应的段表项地址 = F + S * 段表项长度】，取出该段的段长 C，若 W >= C，则产生越界中断，否则继续执行
  4. 取出段表项中该段的始址 b，计算物理地址 E = b + W，用物理地址去访存
• 地址空间是二维的
• 两次访存：
  • 第一次：查内存中的段表
  • 第二次：访问目标内存单元

5）分页和分段的对比

• 页是信息的物理单位，分页的主要目的是提供内存利用率，分页完全是系统行为，对用户不可见
• 段是信息的逻辑单位，分段的主要目的是更好地满足用户需求，用户按照逻辑关系将程序划分为若干段，分段对用户是可见的
• 页的大小固定且有系统决定
• 段的长度不固定，具体取决于用户编写的程序
• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址
• 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址
• 分段比分页更容易实现信息的共享和保护

6）段的共享与保护

• 共享实现：
  • 在每个进程的段表中设置一个段表项，指向被共享的同一物理段
  • 为了防止程序在执行时修改共享代码，在每个进程中都必须配以局部数据区，将在执行过程中可能改变的部分复制到数据区
• 保护实现：
  • 存取控制保护
  • 地址越界保护：两次越界判断【段号、段内偏移】

（4）段页式存储管理方式

1）段页思想

• 分页存储管理能有效提高内存利用率，分段存储管理能反映程序的逻辑结构并有利于段的共享和保护，于是将两种方式结合起来
• 进程的地址空间：首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页
• 内存空间：和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位
  

2）地址结构

• 段号 + 页号 + 页内偏移量
  
• 段号的位数决定了每个进程最多可以分几个段
• 页号位数决定了每个段最大有多少页
• 页内偏移量决定了页面大小、内存块大小是多少

3）地址变换机构

• 每个进程建立一张段表，每个段对应一个段表项，每个段表项至少包括段号、页表长度和页表始址【每个段表项长度相等，段号隐含】
• 每个段有一张页表，每个页面对应一个页表项，每个页表项至少包括页号、页面存放的内存块号【每个页表项长度相等，页号隐含】
• 系统中有一个段表寄存器，指出进程的段表始址和段表长度【用于寻址和判断越界】
  
• 地址空间是二维的
• 三次访存：
  • 第一次：查段表
  • 第二次：查页表
  • 第三次：访问目标内存单元

二、虚拟内存管理

1、虚拟内存

（1）传统存储管理方式的特征

• 一次性：
  • 作业必须一次性全部装入内存，才能开始运行
• 驻留性：
  • 作业被装入内存后，就一直驻留在内存中，直到作业结束
  • 运行中的进程会因等待 I/O 而被阻塞，可能处于长期等待状态

（2）局部性原理

• 时间局部性：
  • 程序中的某条指令一旦执行，不久后该指令可能再次运行
  • 原因是程序中存在着大量的循环结构
• 空间局部性：
  • 程序在一段时间内所访问的地址，可能集中在一定的范围内
  • 因为指令通常是顺序存放、顺序执行的
• 局部性原理既适用于程序结构，又适用于数据结构

（3）虚拟存储器

• 定义：系统为用户提供的一个比实际内存容量大得多的存储器
  • 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
  • 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存【请求调页/段】，然后继续执行程序
  • 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存【页面/段置换】
• 特征：
  • 多次性：只需将当前运行的那部分程序和数据装入内存即可开始运行【最重要的特征】
  • 对换性：作业无需一直常驻内存，暂不使用的从内存调至外存的对换区（换出），要用时换入
  • 虚拟性：从逻辑上扩充内存的容量【最重要的目标】
• 注意：
  • 虚拟内存的最大容量是由计算机的地址结构（CPU 寻址范围）确定的
  • 虚拟内存的实际容量 = min（内存和外存容量之和，CPU 寻址范围）
    

（4）虚拟内存的实现

• 方式 【离散分配】：
  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理
• 需要的东西：
  • 一定的硬件支持，一定容量的内存和外存
  • 页表/段表机制，作为主要的数据结构
  • 中断机制，当程序要访问的部分还未调入内存时，产生中断
  • 地址变换机构

2、请求分页管理方式

（1）基本概念

• 只要求将当前一部分页面装入内存，便可启动作业运行，不需要一次全部装入
• 在作业执行的过程中，当访问的页面不存在时，再通过调页功能将其调入
• 相比基本分页管理，增加的功能：
  • 请求调页功能：将要用的页面调入内存【调入】
  • 页面置换功能：将不用的页面换出到外存【调出】

（2）页表机制

• 页表的构成：页号 + 页框号 + 状态位 P + 访问字段 A + 修改位 M + 外存地址【新增后四个字段】
  
• 状态位/合法位 P：标记该页是否已被调入内存中供程序访问时参考，用于判断是否触发缺页异常
• 访问字段 A：记录本页在一段时间内被访问的次数供置换算法换出页面时参考
• 修改位 M：标识该页在调入内存后是否被修改过当页面被淘汰时，若页面数据没有修改，则不用写回外存
• 外存地址：用于指出该页在外存上的地址，通常是物理块号供写回外存和从外存中调入此页时参考

（3）缺页中断机构

• 缺页：
  • 是在 CPU 执行某条指令过程中，进行取指令或读写数据时发生的一种故障，是内中断【异常】
  • 每当要访问的页面不在内存中时，便产生一个缺页中断，请求 OS 将所缺的页调入内存
  • 缺页中断是访存指令引起的，说明所要访问的页面不在内存中
  • 进行缺页中断处理并调入所要访问的页后，访存指令应该重新执行
  • 特点：
    • 在指令执行期间而非一条指令执行完后产生和处理中断信号
    • 一条指令在执行期间，可能产生多次缺页中断
• 处理过程：
  • 假设此时要访问逻辑地址=（页号，页内偏移量）=（0, 1024）
  • 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
  • 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
  • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
  • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存【未修改过的页面不用写回外存】

（4）地址变换机构

• 相比基本分页管理，增加的步骤：
  • 请求调页（查到页表项时进行判断）
  • 页面置换（需要调入页面，但没有空闲内存块时进行）
  • 需要修改请求页表中新增的表项
    

1. 先检索快表，若命中，从相应表项中取出该页的物理块号，并修改页表项中的访问位，以供置换算法换出页面时参考
2. 若快表未命中，则要到页表中查找，若找到，则从相应表项中取出物理块号，并将该页表项写入快表，若快表已满，则需采用某种算法替换
3. 若在页表中未找到，则需要进行缺页中断处理，请求系统将该页从外存换入内存，页面被调入内存后，由 OS 负责更新页表和快表，并获得物理块号
4. 根据形成的物理地址访存
   
   注意：

• 只有“写指令”才需要修改“修改位”，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表【这样可以减少访存次数】
• 换入/换出页面都需要启动慢速的 I/O 操作，可见，如果换入/换出太频繁，会有很大的开销
• 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中

3、页框分配策略

（1）驻留集

• 驻留集：给一个进程分配的物理页框（也叫做物理块）的集合
• 驻留集越小：驻留在内存的进程就越多，可以提高多道程序的并发度，但分配给每个进程的页框太少，会导致缺页率较高，CPU 需耗费大量时间处理缺页
• 驻留集越大：分配的页框过多时，对缺页率的改善不明显，反而是浪费内存空间，还会导致多道程序并发度下降

（2）页面分配、置换策略

• 两种内存分配策略：
  • 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，驻留集大小不变，分配的算法有：
    • 平均分配算法
    • 按比例分配算法
    • 优先权分配算法
  • 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，驻留集大小可变
• 两种页面置换策略：
  • 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
  • 局部置换：发生缺页时只能选进程自己的物理块进行置换
    
• 固定分配局部置换：
  • 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面
  • 缺点：很难在刚开始就确定应为每个进程分配多少个物理块才算合理
• 可变分配全局置换：
  • 刚开始会为每个进程分配一定数量的物理块，操作系统会保持一个空闲物理块队列
  • 当某进程发生缺页时，从空闲物理块中取出一块分配给该进程
  • 优点：只要某进程发生缺页，都将获得新的物理块
  • 缺点：被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加
• 可变分配局部置换：
  • 刚开始会为每个进程分配一定数量的物理块
  • 当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存
  • 根据发生缺页的频率来动态地增加或减少进程的物理块【频率高，多分配几个物理块】

（3）何时调入页面

• 预调页策略【运行前调入】：
  • 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效
  • 主要用于进程的首次调入，由程序员指出应该先调入哪些部分
• 请求调页策略【运行时调入】：
  • 进程在运行期间发现缺页时才将所缺页面调入内存
  • 优点：调入的页面一定会被访问到
  • 缺点：每次只能调入一页，每次都要磁盘 I/O 操作，开销较大

（4）从何处调页

• 对换区：存放对换页面，采用连续分配方式，速度更快
• 文件区：存放文件，采用离散分配方式，速度更慢

1. 系统拥有足够的对换区空间：
   • 页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快
   • 在进程运行前，需将进程相关的数据从文件区复制到对换区
     
2. 系统缺少足够的对换区空间：
   • 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可
   • 对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入
     
3. UNIX 方式：
   • 运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入
   • 若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入
     

（5）如何调入页面

• 情况 1：所访问的页面不在内存时 ---> 缺页中断 ---> 无空闲物理块 ---> 决定淘汰页 ---> 调出页面 ---> 调入所缺页面
• 情况 2：所访问的页面不在内存时 ---> 缺页中断 ---> 有空闲物理块 ---> 调入所缺页面

（6）其他概念

1）抖动 （颠簸）现象

• 定义：在页面置换时，出现频繁的页面调度行为
• 产生原因：
  • 系统中同时运行的进程太多，分配给每个进程的物理块太少，导致进程在运行时频繁出现缺页，出现频繁的页面调度行为
  • 主要原因是因为页面置换算法不合理
• 解决办法：
  • 撤销部分进程
  • 增加磁盘交换区大小和提高用户进程优先级都与抖动无关

2）工作集

• 定义：在某段时间间隔内，进程实际访问的页面集合
• 如何确定：基于局部性原理，用最近访问过的页面来确认
• 作用：
  • 工作集反映了进程在接下来一段时间内很可能频繁访问的页面集合
  • 为了防止抖动现象，要使分配给进程的物理块数 【驻留集大小】>= 工作集大小
    

4、页面置换算法

（1）最佳置换算法 OPT

• 基本思想：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率
• 特点：
  • 可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面
  • 操作系统无法提前预判页面访问序列，因此，最佳置换算法是无法实现的
    

（2）先进先出置换算法 FIFO

• 基本思想：每次选择淘汰的页面是最早进入内存的页面
• 实现方法：
  • 把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可
  • 队列的最大长度取决于系统为进程分配了多少个内存块
• 特点：
  • Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象
  • 只有 FIFO 算法才会出现 Belady 异常
  • 实现简单
  • 与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问，故算法性能差
    

（3）最近最久未使用置换算法 LRU

• 基本思想：每次淘汰的页面是最近最久未使用的页面
• 实现方法：
  • 赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间 t
  • 当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面
• 特点：
  • 堆栈类算法
  • 需要寄存器和栈的硬件支持
  • 实现困难，开销大
  • 算法性能好
    

（4）时钟置换算法 CLOCK

• 基本思想：基于访问位和循环队列，考虑一个页面最近是否被访问过，又称为最近未用算法（NRU）
• 实现方法：
  • 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列
  • 当某页被访问时，其访问位置为 1
  • 当需要淘汰一个页面时，只需检查页的访问位
    • 如果是 0，就选择该页换出
    • 如果是 1，则将它置为 0，暂不换出，继续检查下一个页面
  • 若第一轮扫描中所有页面都是 1，则将这些页面的访问位依次置为 0 后，再进行第二轮扫描
• 特点：
  • 选择一个淘汰页面最多会经过两轮扫描
  • 性能和开销较为均衡
  • 实现简单
  • 未考虑页面是否被修改
    
    

（5）改进型的时钟置换算法

• 基本思想：
  • 对于 NRU 算法，如果被淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存【只有被淘汰的页面被修改过时，才需要写回外存】
  • 增加一个置换代价——修改位
  • 优先淘汰既未使用又未修改过的页面
• 实现方法：
  • 用 （访问位，修改位） 的形式表示各页面状态【如（1，1）表示一个页面近期被访问过，且被修改过】
  • 将所用可能被置换的页面排成一个循环队列
  • 第一轮：从当前位置开始扫描到第一个 （0，0）【第一优先级】 的帧用于替换，本轮扫描不修改任何标志位
  • 第二轮：若第一轮扫描失败，则重新扫描，查找第一个 （0，1）【第二优先级】 的帧用于替换，本轮将所有扫描过的帧访问位设为 0
  • 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）【原本（1，0）第三优先级】的帧用于替换，本轮扫描不修改任何标志位
  • 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0，1）【原本（1，1）第四优先级】的帧用于替换
• 特点：
  • 选择一个淘汰页面最多会进行四轮扫描
  • 可减少磁盘的 I/O 操作次数
  • 算法开销较小，相比 NRU 稍有增加

5、其他概念

（1）内存映射文件

• 定义：

  • 是 OS 向应用程序提供的一个系统调用
  • 与虚拟内存有些相似，在磁盘文件与进程的虚拟地址空间之间建立映射关系

• 特性：

  • 进程可使用系统调用，请求 OS 将文件映射到进程的虚拟地址空间
  • 以访问内存的方式读文件【将一个文件当作内存中的一个大字符数组，不通过 I/O 访问，更便利】
  • 磁盘文件的读入/写出操作由 OS 负责完成，对进程透明
  • 当映射进程的页面时，不会实际读入文件的内容【访问时才被每次一页地读入】
  • 当进程退出或关闭文件映射时，所用被改动的页面才被写回磁盘文件
  • 多个进程可以映射一个文件，方便共享
    

• 优点：

  • 程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可
  • 文件数据的读入/写出完全由 OS 负责，I/O 效率可以由 OS 负责优化

（2）虚拟存储器性能影响因素

1. 页面较大 ---> 缺页率较低 ---> 可以减少页表长度，但使得页内碎片增大
2. 页面较小 ---> 缺页率较高
   • 可以减少内存碎片，提高内存利用率
   • 使得页表过长，占用大量内存
3. 分配给进程的物理块数越多，缺页率就越低
4. 分配给进程的物理块数超过某个值时，对缺页率的改善并不明显
5. 好的页面置换算法可以使进程在运行过程中具有较低的缺页率
6. LRU，CLOCK 将未来可能要用到的进程保存在内存中，可以提高页面的访问速度
7. 在系统建立一个已修改换出页面的链表，这些页面暂不写回磁盘，仅当换出页面数达到给定值时，才一起写回磁盘，可以显著减少磁盘的 I/O 次数
8. 编写程序的局部化程度越高，执行时的缺页率越低
9. 存储和访问尽量使用相同的访问方式（如按行存储就进行按行访问）

（3）地址翻译

• 见王道书 2025 版 p223，举例较为清晰

第4章 文件管理

一、文件

1、基本概念

（1）定义

• 文件：
  • 是以硬盘为载体的存储在计算机上的信息集合，可以是文本文档、图片、程序等
  • 用户进行的输入、输出操作中，以文件为基本单位
• 文件的结构【自底向上进行定义】：
  • 数据项：文件系统中最低级的数据组织方式，分为：
    • 基本数据项：描述一个对象的某种属性的一个值，是数据中的最小逻辑单位
    • 组合数据项：由多个基本数据项组成
  • 记录：一组相关的数据项的集合，用于描述一个对象在某方面的属性
  • 文件：由创建者所定义的、具有文件名的一组相关元素的集合，分为：
    • 有结构文件：文件由若干个相似的记录组成【如数据库表】
    • 无结构文件：文件被视为一个字节流【如二进制文件或字符文件】

（2）属性

• 文件名：由创建文件的用户决定，为了方便用户找到文件，同一目录下不允许有重名文件
• 类型：被支持不同类型的文件系统所使用
• 创建者：文件创建者的 ID
• 所有者：文件当前所有者的 ID
• 位置：指向设备和设备上文件的指针
• 大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值
• 保护：对文件进行保护的访问控制信息
• 创建时间、最后一次修改时间、最后一次存取时间：用于保护和跟踪文件

2、文件的数据结构

（1）文件控制块 FCB

• 文件控制块：用来存放控制文件需要的各种信息的数据结构，以实现按名存取
• 文件目录：FCB 的有序集合【文件与 FCB 一一对应，一个 FCB 就是一个文件目录项】
• 目录文件：一个文件目录也被视为一个文件
• 每当创建一个新文件，系统就要为其建立一个 FCB，用来记录文件的各种属性
  
• FCB 主要包含以下信息：
  • 基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构
  • 存取控制信息：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限
  • 使用信息：文件的建立时间、上次修改时间等

（2）索引节点

• 索引节点：包含了除文件名之外的所有信息，每个文件对应一个索引节点
• 文件目录的目录项中仅由文件名和相应的索引节点号（或索引节点指针）构成
• 优点：使用索引节点，目录项长度减小，因此每个磁盘块可以存放更多个目录项，减少了索引文件时磁盘 I/O 的次数
• 分类：
  • 磁盘索引节点：
    • 指存放在磁盘上的索引节点【外存中】
    • 每个文件有一个唯一的磁盘索引节点
    • 包含：文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件链接计数、文件存取时间
  • 内存索引节点：
    • 指存放在内存中的索引节点
    • 文件被打开时，将磁盘索引节点复制到内存的索引节点，便于以后使用
    • 新增：索引节点号、状态、访问计数、逻辑设备号、链接指针

3、文件的操作

（1）创建文件（create 系统调用）

• 需要提供的主要参数：
  • 所需的外存空间大小（如：一个盘块，即 1 KB）
  • 文件存放路径（“D:/Demo”）
  • 文件名（这个地方默认为“新建文本文档.txt”）
• OS 的处理过程：
  • 在外存中找到文件所需的空间
  • 根据文件存放路径的信息找到该目录对应的目录文件（此处就是 D:/Demo 目录），在目录中创建该文件对应的目录项

（2）删除文件（delete 系统调用）

• 需要提供的主要参数：
  • 文件存放路径（“D:/Demo”）
  • 文件名（“test.txt”）
• OS 的处理过程：
  • 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
  • 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块
  • 从目录表中删除文件对应的目录项

（3）打开文件（open 系统调用）

• 需要提供的主要参数：
  • 文件存放路径（“D:/Demo”）
  • 文件名（“test. Txt”）
  • 要对文件的操作类型（如：r 只读；rw 读写等）
• OS 的处理过程：
  • 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限
  • 将目录项从外存复制到内存中的“打开文件表” 的一个表目中，并将该表目的索引号（也称文件描述符）返回给用户
• 注意：
  • 只要完成了 open 系统调用，之后对文件的操作（read，write，Lseek，close 等）均使用文件描述符，这样可以加快文件的访问速度
  • 打开文件表整个系统只有一张
  • 对于访问打开文件表的索引号，UNIX 称之为文件描述符，Windows 称之为文件句柄
• 打开文件所具有的关联信息：
  • 文件指针：
    • 系统跟踪上次的读写位置作为当前文件位置的指针
    • 这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存
  • 文件打开计数：
    • 计数器跟踪当前文件打开和关闭的数量
    • 因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件
  • 文件磁盘位置：
    • 大多数文件操作要求系统修改文件数据
    • 查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息
  • 访问权限：
    • 每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等）
    • 该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的 I/O 请求

（4）关闭文件（close 系统调用）

• OS 的处理过程：
  • 将进程的打开文件表相应表项删除
  • 回收分配给该文件的内存空间等资源
  • 系统打开文件表的打开计数器 count 减 1，若 count =0，则删除对应表项
• 内存中文件的系统结构：
  • 在多个不同进程可以同时打开文件的操作系统中，通常采用两级表：
    • 整个系统的打开文件表：包含与进程无关的信息，如文件在磁盘上的位置、访问日期和文件大小
    • 每个进程的打开文件表：保存的是进程对文件的使用信息，如文件的当前读写指针、文件访问权限，并包含指向系统表中适应条目的指针
  • 一旦有进程打开了一个文件，系统表就包含该文件的条目
  • 当另一个进程执行调用 open 时，只不过是在其文件打开表中增加一个条目，并指向系统表的相应条目
  • 通常，系统打开文件表为每个文件关联一个打开计数器（Open Count）, 以记录多少进程打开了该文件
  • 每个关闭操作 close 使 count 递减，当打开计数器为 0 时，表示该文件不再被使用，并且可从系统打开文件表中删除相应条目
    

（5）读文件（read 系统调用）

• 根据文件名查找目录【open 之后通过文件描述符】，找到指定文件的目录项后，再利用目录项中的读指针进行读操作
• 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域
• 外存 ---> 内存

（6）写文件（write 系统调用）

• 根据文件名查找目录【open 之后通过文件描述符】，找到指定文件的目录项后，再利用目录项中的写指针进行写操作
• 从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存
• 内存 ---> 外存

4、文件保护

（1）基本概念

• 保护的目的：解决对文件的读、写、执行的许可问题
• 一个文件的访问常由用户访问权限和文件属性（包括保存在 FCB 中对文件访问的控制信息）共同设置

（2）非访问控制方法

• 都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型

1）口令保护

• 定义：用户建立一个文件时需要提供口令【附在 FCB 上】，用户请求访问时必须提供相应口令
• 优点：时间和空间开销不多
• 缺点：口令直接存在系统内部，不安全

2）加密保护

• 定义：对文件进行加密，被访问时需要使用秘钥
• 优点：保密性强，节省了存储空间
• 缺点：编码和译码需要时间

（3）访问控制方法

• 访问类型：读、写、执行、添加、删除、列表清单
• 方法：
  • 根据用户身份进行访问控制
  • 为每个文件和目录增加一个访问控制表 ACL，以规定每个用户名及其所允许的访问类型
  • 优点：可以使用复杂的访问方法
  • 缺点：长度无法预计并且可能导致复杂的空间管理
• 注意：
  • 上述的文件保护可以只在低层提供
  • 对文件的重命名、复制、粘贴等控制方式【高层功能】，可通过系统程序调用低层系统调用实现
• 精简的访问控制列表：
  • 解决 ACL 的问题，包含三种用户类型：
    • 拥有者：创建文件的用户
    • 组：一组需要共享文件且具有类似访问的用户
    • 其他：系统内的所有其他用户
      
  • 每项占用一个二进制位，只需 3 * 4 位的矩阵即可描述三类用户的权限
  • 创建文件时，系统将文件拥有者的名字、所属组名记录在该文件的 FCB 中

4、文件的逻辑结构

• 指从用户角度出发所看到的文件的组织形式

（1）无结构文件

• 基本概念：
  • 最简单的文件组织形式
  • 文件内部的数据就是一系列二进制流或字符流，又称流式文件
  • 其长度以字节为单位
  • 如：系统中运行的大量源程序、可执行文件、库函数等
• 访问方式：
  • 通过读/写指针来指出下一个要访问的字节
  • 没有结构，因此对记录的访问只能通过穷举搜索的方式

（2）有结构文件

• 基本概念：

  • 指由一个以上的记录构成的文件，又称记录式文件
  • 各记录由相同或不相同的数据项组成

• 根据各记录的长度是否相等，可分为：

  • 定长记录：
    • 文件中所有记录的长度相同
    • 各数据项都在记录中的相同位置，具有相同的长度
    • 特点：检索记录的速度快，方便用户对文件进行处理，广泛用于数据处理中
  • 变长记录：
    • 文件中各记录的长度不一定相同
    • 记录中所包含的数据项数目可能不同，数据项本身的长度可能不同
    • 特点：检索记录只能顺序查找，速度慢

• 根据记录的组织形式，可分为：

1）顺序文件

• 文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的
• 各个记录在物理上有两种存储方式：
  • 顺序存储：
    • 逻辑上相邻的记录物理上也相邻
    • 可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找
    • 定长记录：
      • 可以实现随机存取
      • 若采用串结构，无法快速找到某关键字对应的记录
      • 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
  • 链式存储：
    • 逻辑上相邻的记录物理上不一定相邻（类似于链表）
    • 无论是定长/可变长记录，都无法实现随机存取
• 顺序文件中记录的排列有两种结构：
  • 串结构：各记录之间的顺序与关键字无关
  • 顺序结构：记录之间的顺序按关键字顺序排列
• 注意：
  • 对记录进行批量操作，即每次要读或写一大批记录时，顺序文件的效率是所有逻辑文件中最高的
  • 对于顺序存储设备（如磁盘），只有顺序文件才能被存储并能有效地工作
  • 在需要经常增删改查单个记录的场合，性能较差

2）索引文件

• 建立一张索引表，为主文件的每个记录在索引表中分别设置一个索引表项，其中包含指向记录的指针和记录长度
• 索引表按关键字排序，其本身也是一个定长记录的顺序文件
• 将对变长记录顺序文件的检索转变成对记录索引文件的随机检索，从而加快了记录的检索速度
• 主要用于对信息处理的及时性要求比较高的场合
  

3）索引顺序文件

• 是索引文件和顺序文件思想的结合
• 先将变长记录顺序文件中的所有记录分为若干组，然后为文件建立一张索引表
• 为每组中的第一个记录建立一个索引项，包含该记录的关键字和指向该记录的指针
• 同一组内的关键字可以无序，组与组之间的关键字必须有序
  
• 检索效率分析：
  

4）直接文件或散列文件（Hash File）

• 给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址
• 这种映射结构不同于顺序文件或索引文件，没有顺序的特性
• 散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同

5、文件的物理结构

• 用户通过逻辑地址来操作自己的文件，操作系统如何实现从逻辑地址到物理地址的映射？
• （逻辑块号，块内地址）--->（物理块号，块内地址）【只需转换块号就行，块内地址保
  持不变】

（1）连续分配

• 文件的目录项记录起始块号和所占用的块数
• 要求每个文件在磁盘上占有一组连续的块
• 磁盘地址定义了磁盘上的一个线性排序，使作业访问磁盘时需要的寻道数和寻到时间最小
• 优点：
  • 支持顺序访问和直接访问（即随机访问）
  • 连续分配的文件在顺序访问时速度最快
• 缺点：
  • 文件长度不宜动态增加
  • 存储空间利用率低，反复增删文件后会产生外部碎片
  • 很难确定一个文件需要的空间大小，因此只适用于长度固定的文件
    

（2）链接分配

1）隐式链接

• 目录项中记录了文件存放的起始块号和结束块号
• 每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方
• 除最后一个盘块外，每个盘块都含有指向文件下一个盘块的指针，这些指针对用户是透明的
• 优点：
  • 方便文件拓展，不会有碎片问题，外存利用率高
• 缺点：
  • 只适合顺序访问，不支持随机访问，查找效率低
  • 稳定性问题，文件盘块中的任何一个指针出问题，都会导致文件数据的丢失
  • 指向下一个盘块的指针也要耗费一定的存储空间
• 为了提高查找速度和减小指针所占空间，可以将几个盘块组成一个簇，按簇分配，可以大幅减少查找时间，但增加了内部碎片
  

2）显式链接

• 指把用于链接文件各物理块的指针，从每个物理块的末尾中提取出来，显式地存放在内存的一张链接表
• 该表在整个磁盘中仅设置一张，称为文件分配表 FAT
• 开机时文件分配表放入内存，并常驻内存
• 文件目录中只需记录文件的起始块号，后续块号可通过查 FAT
• 优点：
  • 很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问
  • 相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高
• 缺点：
  • 文件分配表的需要占用一定的存储空间
    

（3）索引分配

1）单级索引分配

• 将每个文件所有的盘块号集中地放在一起，当访问到某个文件时，将该文件对应的盘块号一起调入内存
• 为每个文件分配一个索引块（表），存放分配给该文件的所有盘块号
• 假如盘块大小为 4 KB，每个盘块号占 4 B，则一个索引块中可放 1024 个盘块号，支持最大文件为 1024 * 4 KB = 4 MB
• 优点：
  • 支持直接访问
  • 不会产生外部碎片
• 缺点：
  • 索引块增加了额外的存储空间开销
  • 当文件很小时，比如只有数个盘块，此时索引块的利用率很低
  • 当文件很大时，若其盘块号占用若干索引块，可通过链指针将各索引块按序链接起来，但是很查找效率低下
    

2）多级索引分配

• 文件太大而索引块太多时，为这些索引块再建立一级索引，称为主索引
• 采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块需要 K+1 次读磁盘操作
• 假如盘块大小为 4 KB，每个盘块号占 4 B，则一个索引块中可放 1024 个盘块号，支持最大文件为 1024 * 1024 * 4 KB = 4 GB
• 优点：极大加快了对大型文件的查找速度
• 缺点：当访问一个盘块时，其所要启动磁盘的次数随着索引级数的增加而增多
  

3）混合索引分配

• 全面照顾到小型、中星、大型和特大型文件
• 直接地址：
  • 地址项 0~9 存放直接地址，即文件数据块的盘块号
  • 假如每个盘块大小为 4 KB，适用于不大于 40 KB 的文件
  • 提高了对小文件的检索速度
• 一次间接地址：
  • 地址项 10 提供，即采用一级索引分配
  • 一次间接地址中记录了文件的一次间址块号，一次间址块就是索引块，记录了文件数据块的盘块号
  • 一次间址块中可存放 1024 个盘块号，允许最大文件长度 4 MB + 40 KB
• 多次间接地址：
  • 地址项 11 提供二次间接地址，即采用两级索引分配
  • 允许最大文件长度 4 GB + 4 MB + 40 KB
    

二、目录

1、文件目录的实现

• 一个文件对应一个 FCB，一个 FCB 就是一个目录项，多个 FCB 组成文件目录
• 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
• 目录管理的基本要求：
  • 从用户角度，实现“按名存取”
  • 提高对目录的检索速度
  • 多用户系统中，提供用于控制访问文件的信息，允许文件共享
  • 允许不同用户对不同文件采用相同的名字

2、目录结构

（1）单级目录结构

• 定义：
  • 整个文件系统只建立一张目录表
  • 每个文件占一个目录项
• 优点：实现了 “按名存取”
• 缺点：
  • 查找速度慢、文件不允许重名、不便于文件共享
  • 对于多用户的操作系统不适用
    

（2）两级目录结构

• 定义：
  • 文件目录分为主文件目录 MDF 和用户文件目录 UFD
  • MDF 记录用户名及相应 UFD 所在的存储位置
  • UFD 记录用户所有文件的 FCB
• 优点：
  • 解决了多用户之间的文件重名问题
  • 文件系统可以在目录上实现访问限制
• 缺点：
  • 缺乏灵活性，不能对文件分类

（3）树形目录结构

• 定义：
  • 当用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成
  • 从根目录出发的路径称为绝对路径
  • 当层次较多时，每次从根目录查询会浪费时间，于是加入了当前目录（又称工作目录），进程对各文件的访问都是相对于当前目录进行的
  • 当用户要访问某个文件时，使用相对路径标识文件
  • 不同的用户的文件，文件名可相同可不同
  • 大多 OS 采用这种目录结构
• 优点：
  • 可以很方便的对文件进行分类
  • 能够有效地进行文件的管理和保护
• 缺点：
  • 不便于实现文件共享
  • 查找文件增加了磁盘访问次数，会影响查询速度
• 下图是 Linux 操作系统的目录结构，"/dev/hda” 就是一个绝对路径
• 若当前目录为 “/bin”，则 "./Is” 就是一个相对路径，其中符号 "." 表示当前工作目录
  

（4）无环图目录结构

• 定义：
  • 在树形目录结构上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
  • 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录【共享同一目录下的所有内容】
  • 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点
  • 用户提出删除结点的请求时，只是删除该用户的 FCB、并使共享计数器减 1，并不会直接删除共享结点
  • 只有共享计数器减为 0 时，才删除结点
• 优点：实现了文件共享
• 缺点：使得系统管理变得更加复杂
  

3、索引节点

• 除了文件名之外的所有信息都放到索引节点中，每个文件对应一个索引节点
• 目录项中只包含文件名、索引节点指针，因此每个目录项的长度大幅减小
• 每个磁盘块可以存放更多个目录项，因此线索文件时磁盘 I/O 的次数就少了很多

4、文件共享

• 文件共享使多个用户共享同一个文件，系统只需保留该文件的一个副本

（1）基于索引节点的共享方式（硬链接）

• 定义：
  • 硬链接就是多个指针指向一个索引节点
  • 文件的物理地址和其他文件属性信息放在索引节点中
  • 索引节点中需要有链接计数 count
  • 某用户想删除文件时，只是删除该用户的目录项，count--
  • 只有 count == 0 时才能真正删除文件数据和索引节点，否则会导致指针悬空
• 特点：
  • 不可用于跨文件系统
  • 查找速度比软链接快
    

（2）基于符号链的共享方式（软链接）

• 定义：
  • 在一个 Link 型的文件中记录共享文件的存放路径（类似于 Windows 系统中的快捷方式）
  • OS 根据路径一层层查找目录，最终找到共享文件
  • 只有文件主才拥有指向索引节点的指针
  • 共享文件的其他用户只有该文件的路径名，并不拥有指向其索引节点的指针
• 特点：
  • 访问共享文件时可能多次地读磁盘，增加了访问文件的开销
  • 实现网络文件共享时，只需提供该文件所在机器的网络地址及文件路径名
    

三、文件系统

1、文件系统的基本概念

• 概念：
  • 文件系统是 OS 中负责管理持久数据的子系统
  • 文件系统 = 与文件管理有关的软件 + 被管理的文件 + 试试文件管理所需的数据结构
  • 文件系统需先挂在到某个目录才可正常使用
  • 文件的基本操作单位就是数据块
• 目标：
  • 用户角度：实现对文件的基本操作，如按名存储和查找文件 + 组织成合适的结构 + 文件共享 + 文件保护
  • OS 角度：
    • 管理与磁盘的信息交换 + 完成逻辑结构和物理结构的变换
    • 组织文件在磁盘上的存放 + 采取好的文件排放顺序和磁盘调度方法
• 分类：
  • 磁盘的文件系统：
    • 它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统
  • 内存的文件系统：
    • 这类文件系统的数据不是存储在硬盘的，而是占用内存空间
    • 我们经常用到的 /proc 和 /sys 文件系统都属于这一类
    • 读写这类文件，实际上是读写内核中相关的数据
  • 网络的文件系统：
    • 用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等

2、文件系统结构

（1）王道 ppt 版

• 假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后 100 条记录：
• 用户接口：用户需要通过操作系统提供的接口发出上述请求
• 文件目录系统：由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项
• 存取控制模块（存取控制验证层）：不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限
• 逻辑文件系统与文件信息缓冲区：验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址
• 物理文件系统：知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址
• 设备管理程序模块： 要删除这条记录，必定要对磁盘设备发出请求
• 辅助分配模块：删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收
  

（2）王道书版

• I/O 控制：
  • 设备驱动程序：将输入的命令翻译成底层硬件的特定指令
  • 中断处理程序：利用指令使 IO 设备与系统交互
• 基本文件系统：
  • 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块
  • 管理内存缓冲区，保存各种文件系统，目录和数据块的缓冲
• 文件组织模块：
  • 组织文件及其逻辑块和物理块
  • 可以将逻辑地址转换为物理地址
  • 有空闲空间管理器，以跟踪未分配的块，根据需要提供给文件组织模块
• 逻辑文件系统：
  • 用于管理元数据信息（包括文件系统的所有结构，不包括文件内容）
  • 管理目录结构
  • 通过 FCB 维护文件结构
  • 负责文件保护
    

3、文件系统布局

（1）文件系统在磁盘中的结构

• 文件系统存放在磁盘上，多数磁盘划分为一个或多个分区
• 每个分区中有一个独立的文件系统
• 文件系统可能包含如下信息：
  
• 主引导记录（MBR）：
  • 位于磁盘的 0 号区，用来引导计算机
  • MBR 后面是分区表，给出每个分区的起始和结束地址
  • 表中的第一个分区被标记为活动分区，当计算机启动时，计算机读入并执行 MBR
  • MBR 做的第一件事就是确定 1 活动分区，读入它的第一块，即引导块
• 引导块：
  • Windows 系统称之为分区引导扇区
  • MBR 执行引导块中的程序后，该程序负责启动该分区中的操作系统
  • 每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统
  • 除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的
• 超级块：
  • 包含文件系统的所有关键信息
  • 比如：分区的块的数量、块的大小、空闲块的数量和指针、空闲的 FCB 数量和 FCB 指针等
  • 在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存
• 文件系统中空闲块的信息：使用位示图或指针链接的形式给出
• i 节点：每个文件对应一个 i 节点，说明了文件的方方面面
• 根目录：存放文件系统目录树的根部
• 最后，磁盘的其他部分存放了其他所有的目录和文件

（2）文件系统在内存中的结构

• 内存中的信息用于管理文件系统并通过缓存来提高信息
• 这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃
• 这些结构的类型可能包括：
  • 内存中的安装表：包含每个已安装文件系统分区的有关信息
  • 内存中的目录结构的缓存：包含最近访问目录的信息
  • 整个系统的打开文件表
  • 每个进程的打开文件表

3、外存空闲空间管理

• 一个磁盘可以划分为多个分区，每个分区够可以有单独的文件系统
• 卷：
  • 包含文件系统的分区【可以是磁盘的一部分/整个磁盘/多个磁盘组成的 RAID 集】
  • 文件区：存放文件数据的空间
  • 目录区：FCB 的空间
  • 卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块
    
• 文件存储设备分成许多大小相同的物理块，并以块为单位交换信息
• 文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题

（1）空闲表法

• 属于连续分配方式，为每个分区文件分配一块连续的存储空间
• 在外存上为所有空闲区建立一张空闲表
• 每个空闲区对应一个空闲表项，包括：
  • 表项序号
  • 该空闲区的第一个空闲盘块号
  • 该空闲区的空闲盘块数
• 按起始盘块号递增的次序对空闲区排列
  
• 如何分配磁盘块：
  • 与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间
  • 同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间
• 如何回收磁盘块：
  • 与内存管理中的动态分区分配很类似，有四种情况
  • 回收时需要注意表项的合并问题

（2）空闲链表法

1）空闲盘块链

• 将磁盘上的所有空闲空间以盘块为单位拉成一条链
• 每个盘块都有指向下一个空闲盘块的指针
• 当用户请求分配存储空间时：系统从链首开始，依次摘下适当数目的空闲盘块分配给用户
• 当用户释放存储空间时：系统将回收的盘块依次插入空闲盘块链的末尾
• 优点：
  • 分配和回收一个盘块的过程非常简单
  • 适用于离散分配的物理结构
• 缺点：
  • 在为一个文件分配盘块时可能要重复操作多次，效率较低
  • 以盘块为单位，链会很长
    

2）空闲盘区链

• 指将磁盘上的所有空闲盘区拉成一条链，每个盘区包含若干相邻的盘块
• 每个盘区含有下一个空闲盘区的指针和本盘区的盘块数
• 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法
• 回收盘区时，同样也要将回收区与相邻接的空闲盘区合并
• 优点：是分配与回收的效率较高，且空闲盘区链较短
• 缺点：是分配与回收的过程比较复杂
  

（3）位示图法

• 利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应【0 代表盘块空闲，1 代表盘块已分配】
• 盘块的分配：
  1. 顺序扫描位示图，从中找出一个或一组其值为 “0” 的二进制位
  2. 将找到的一个或一组二进制位，转换成与之对应的盘块号 b = n (i - 1) + j
  3. 修改位示图 0 --> 1
• 盘块的回收：
  • 将回收盘块的盘块号转换成位示图中的行号和列号：
    • i = (b - 1) DIV n + 1
    • j = (b - 1) MOD n + 1
  • 修改位示图 1 --> 0
• 优点：
  • 很容易在位示图中找到一个或一组相邻接的空闲盘块
  • 占用空间少，可将其保存在内存中，节省磁盘启动的开销
• 缺点：
  • 位示图大小会随着磁盘容量的增加而增大，故常用于小型计算机
    

（4）成组链接法

• 基本思想：
  • 将空闲盘块分成若干个组，每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号
  • 由各组的第一个盘块可以链接成一条链
  • 第一组的空闲盘块总数和空闲盘块号保存在内存的专用栈中，称为空闲盘块号栈
• 盘块的分配：
  • 根据空闲盘块号栈的指针，将与之对应的盘块分配给用户，同时移动指针
  • 若该指针指向的是栈底的盘块号，则由于该盘块号对应的盘块中保存的是下一组空闲盘块号，因此要将该盘块的内容读入栈中，作为新的空闲盘块号栈的内容，并将原栈底盘块号对应的盘块分配出去 ( 其中有用的数据已读入栈中)
  • 最后，将栈中的空闲盘块数减 1
• 盘块的回收：
  • 将回收的盘块号存入空闲盘块号栈的顶部，同时移动指针，并将栈中的空闲盘块数加 1
  • 当栈中的空闲盘块数已达 100 时，表示栈已满，将现有栈中的 100 个空闲盘块号存入新回收的盘块，并将新回收的盘块号作为新栈底，再将栈中的空闲盘块数置为 1
    

4、虚拟文件系统

• 虚拟文件系统（VFS）：屏蔽了不同文件系统的差异和操作细节，向上为用户提供了文件操作的同一调用接口
  
• 特点：
  • 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
  • VFS 要求下层的文件系统必须实现某些规定的函数功能（open/read/write）
  • 一个新的文件系统想要在某 OS 上被使用，则必须满足 VFS 的要求
  • 每打开一个文件，VFS 就在主存中新建一个 vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统【vnode 的功能指针指向具体文件系统的函数功能】
    

5、文件系统挂载

• 文件系统挂载（mounting）：文件系统在进程使用之前必须先挂载到某个目录，此后便可通过这个目录来访问设备上的文件
• 注意：这里的设备是逻辑上的设备，如一个磁盘上的不同分区都可视为不同的设备
• 挂载过程：
  1. 在 VFS 中注册新挂载的文件系统，内存中的挂载表包含每个文件系统的相关信息，包括文件系统类型、容量大小等
  2. 新挂载的文件系统，要向 VFS 提供一个函数地址列表
  3. 将新文件系统加到挂载点，也就是将新文件系统挂载到某个父目录下

第5章 输入输出管理

一、I/O 管理概述

1、I/O 设备

（1）设备的分类

1）按信息交换的单位

• 块设备：
  • 信息交换以数据块为单位，如磁盘、磁带
  • 基本特征：传输速率较高、可寻址，即对它可随意地读/写任意一块
  • 属于有结构设备
• 字符设备：
  • 信息交换以字符为单位，如交互式终端机、打印机
  • 基本特征：传输速率低、不可寻址，常采用中断 I/O 方式
  • 属于无结构设备

2）按设备的传输速率

• 低速设备：键盘、鼠标
• 中速设备：激光打印机
• 高速设备：磁盘机、光盘机

3）按设备的共享属性

• 独占设备：
  • 一个时刻只能由一个进程占用
  • 所有字符设备都是独占设备
  • 速度慢，利用率低
  • 如输入机、打印机、磁带机
• 共享设备：
  • 同一时间段内允许多个进程同时访问的设备
  • 共享设备必须是可寻址和可随机访问的设备
  • 如软硬盘、磁盘、光盘
• 虚拟设备：
  • 通过 SPOOLing 技术将独占设备改造为共享设备
  • 将一个物理设备变为多个逻辑设备，从而可将设备同时分配给多个进程
  • 实质上还是独占设备

4）按设备的使用特性

• 存储设备：
  • 存储信息的外部设备
  • 如磁盘、磁带、光盘
• 输入/输出设备：
  • 输入设备：向计算机输入外部信息，如键盘、鼠标、扫描仪
  • 输出设备：计算机向外输出数据信息，如打印机
  • 交互式设备：集成两种功能，如触控显示器

（2）设备控制器（I/O 接口）

1）主要功能

• 接受和识别 CPU 发出的命令
• 向 CPU 报告设备的状态
• 数据交换
• 地址识别
• 数据缓冲
• 差错控制

2）组成

• 设备控制器与 CPU 的接口：
  • 用于实现 CPU 与控制器之间的通信，有三类信号线
  • 数据线：传送的是读/写数据、控制信息和状态信息
  • 地址线：传送的是要访问 I/O 接口中的寄存器编号
  • 控制线：传送的是读/写等控制信号
• 设备控制器与设备的接口：
  • 用于实现控制器和设备之间的通信
  • 控制器中有一个或多个设备接口
  • 每个接口都可传输数据、控制和状态三种类型的信号
• I/O 逻辑：
  • 用于实现对设备的控制
  • 通过一组控制线与 CPU 交互，对从 CPU 收到的 I/O 命令进行译码
  • CPU 启动设备时，将启动命令发送给控制器，同时通过地址线将地址发送给控制器，由控制器的 I/O 逻辑对地址进行译码，并对所选设备进行控制
    

3）类型

• 按数据传送方式：
  • 并行接口
  • 串行接口
• 按主机访问 I/O 设备的控制方式：
  • 程序查询接口
  • 中断接口
  • DMA 接口
• 按功能选择的灵活性：
  • 可编程接口
  • 不可编程接口

（3）I/O 端口

1）基本概念

• I/O 端口：指设备控制器中可被 CPU 直接访问的寄存器，有三种类型
  • 数据寄存器：用于缓存从设备送来的输入数据，或从 CPU 送来的传输数据
  • 状态寄存器：保存设备的执行结果或状态信息，以供 CPU 读取
  • 控制寄存器：由 CPU 写入，以便启动命令或更改设备模式
• I/O 端口要想能够被 CPU 访问，就要对各个端口进行编制，每个端口对应一个端口地址

2）寄存器编址方式

• 独立编址：

  • 指为每个端口分配一个 I/O 端口号
  • I/O 端口的地址空间与主存地址空间独立
  • 两者范围可以重叠，相同地址可能属于不同的地址空间
  • 只有 OS 使用特殊的 I/O 指令才能访问端口【普通用户程序不能访问端口】
  • 优点：
    • I/O 端口数比主存单元少得多，只需少量地址线，使得 I/O 端口译码简单，寻址速度更快
    • 使用专用 I/O 指令，可使程序更加清晰，便于理解和检查
  • 缺点：
    • I/O 指令少，只提供简单的传输操作，所以程序设计的灵活性较差
    • CPU 需要提供两组独立的存储器和设备的读/写控制信号，增加了控制的复杂性

• 统一编址：

  • 又称内存映射 I/O
  • 指将主存地址空间分出一部分给 I/O 端口进行编址，I/O 端口和主存单元在同一地址空间的不同分段中
  • 根据地址范围就能区分访问的是 I/O 端口还是主存单元
  • 用统一的访存指令就可访问 I/O 端口
  • 优点：
    • 不须专门的 I/O 指令，使得 CPU 访问 I/O 的操作更加灵活方便
    • 使端口有较大的编址空间
  • 缺点：
    • 端口地址占用了部分主存地址空间，使主存的可用容量变小
    • 识别 I/O 端口时全部地址线都需参加译码，使译码电路更加复杂，降低寻址速度

2、I/O 控制方式

• I/O 控制：指控制设备和主机之间的数据传送
  

（1）程序直接控制方式

• CPU 对 I/O 设备的控制采用轮询的 I/O 方式，又称程序轮询方式
• CPU 干预的频率：
  • 很频繁，I/O 操作开始之前、完成之后需要 CPU 介入
  • 在等待 I/O 完成的过程中 CPU 需要不断地轮询检查
• 数据的传送单位：每次读/写一个字
• 数据的流向：
  • 读操作（数据输入）：I/O 设备 ---> CPU 寄存器 ---> 内存
  • 写操作（数据输出）：内存 ---> CPU 寄存器 ---> I/O 设备
• 优点：实现简单
• 缺点：
  • CPU 和 I/O 设备只能串行工作
  • CPU 需要一直轮询检查，长期处于“忙等”状态，CPU 利用率低
    

（2）中断驱动方式

• 基本思想：允许 I/O 设备主动打断 CPU 的运行并请求服务，从而“解放”CPU，使得其向 I/O 控制器发送读命令后可以继续做其他有用的工作
• CPU 干预的频率：
  • 每次 I/O 操作开始之前、完成之后需要 CPU 介入
  • 等待 I/O 完成的过程中 CPU 可以切换到别的进程执行
• 数据的传送单位：每次读/写一个字
• 数据的流向：
  • 读操作（数据输入）：I/O 设备 ---> CPU 寄存器 ---> 内存
  • 写操作（数据输出）：内存 ---> CPU 寄存器 ---> I/O 设备
• 优点：
  • I/O 控制器会通过中断信号主动报告 I/O 已完成，CPU 不再需要不停地轮询
  • CPU 和 I/O 设备可并行工作，CPU 利用率明显提升
• 缺点：
  • 每个字在 I/O 设备与内存之间的传输，都需要经过 CPU
  • 频繁的中断处理会消耗较多的 CPU 时间
    

（3）DMA 方式

• 基本思想：是在 I/O 设备和内存之间开辟直接的数据交换通路，彻底"解放” CPU
• CPU 干预的频率：
  • 仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预
  • 整块数据的传送是在 DMA 控制器的控制下完成的
• 数据的传送单位：每次读/写一个或多个块【连续的】
• 数据的流向：
  • 读操作（数据输入）：I/O 设备 ---> 内存
  • 写操作（数据输出）：内存 ---> I/O 设备
• 优点：
  • 数据传输以“块”为单位，CPU 介入频率进一步降低
  • 数据的传输不再需要先经过 CPU 再写入内存，数据传输效率进一步增加
  • CPU 和 I/O 设备的并行性得到提升
• 缺点：
  • CPU 每发出一条 I/O 指令，只能读/写一个或多个连续的数据块
  • 如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU 要分别发出多条I/O 指令，进行多次中断处理才能完成
    

（4）通道控制方式

• I/O 通道是一种特殊的处理机，可执行一系列通道指令
• 与 CPU 相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说通道与 CPU 共享内存
• CPU 干预的频率：
  • 极低
  • 通道会根据 CPU 的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求 CPU 干预
• 数据的传送单位：每次读/写一组数据块
• 数据的流向【在通道的控制下进行】：
  • 读操作（数据输入）：I/O 设备 ---> 内存
  • 写操作（数据输出）：内存 ---> I/O 设备
• 优点：
  • CPU、通道、I/O 设备可并行工作，资源利用率很高
  • 一个通道可以控制多台设备与内存的数据交换
• 缺点：实现复杂，需要专门的通道硬件支持
  

3、I/O 软件层次结构

• 将系统中的设备管理模块分为若干个层次，每层都利用其下层提供的服务，完成输入/输功能中的某些子功能，并屏蔽这些功能的实现细节，向高层提供服务
  

（1）用户层软件

• 用户层软件实现了与用户交互的接口
• 用户可直接使用该层提供的、与 I/O 操作相关的库函数对设备进行操作
• 用户层软件将用户请求翻译成格式化的 I/O 请求，并通过系统调用请求操作系统内核【下三层】的服务

（2）设备独立性软件

• 设备独立性：又称设备无关性，使得应用程序独立于具体使用的物理设备
• 为实现设备独立性，引入了逻辑设备和物理设备两个概念
• 使用逻辑设备名的好处：
  • 增加设备分配的灵活性
  • 易于实现 I/O 重定向，用于 I/O 操作的设备可以更换 ，而不必改变应用程序
• 为实现设备独立性，必须在驱动程序之上设置一层设备独立性软件，主要功能：
  • 向上层提供统一的调用接口（如 read/write 系统调用）
  • 设备的保护
  • 差错处理
  • 设备的分配与回收
  • 数据缓冲区管理
  • 建立逻辑设备名到物理设备名的映射关系，根据设备类型选择调用相应的驱动程序

（3）设备驱动程序

• 与硬件直接相关，负责具体实现系统对设备发出的操作命令，驱动 I/O 设备工作的驱动程序
• 每类设备设置一个设备驱动程序，它是 I/O 进程与设备控制器之间的通信程序，通常以进程的形式存在
• 设备具体的差别被设备驱动程序所封装，设备驱动程序向上层用户程序提供一组标准接口，用于接收上层软件发来的抽象 I/O 要求（如 read /write 命令），转换为具体要求后，发送给设备控制器，控制 I/O 设备工作
• 它也将由设备控制器发来的信号传送给上层软件，从而为 I/O 内核子系统隐藏设备控制器之间的差异

（4）中断处理程序

• 保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断进程
  

4、应用程序 I/O 接口

（1）I/O 接口的分类

• 字符设备接口：
  • 字符设备：指数据的存取和传输是以字符为单位的设备（如键盘、打印机等）
  • 基本特征：
    • 传输速率较低、不可寻址
    • I/O 通常采用中断驱动方式
• 块设备接口：
  • 块设备：指数据的存取和传输是以数据块为单位的设备（如磁盘）
  • 基本特征：
    • 传输速率高、可寻址
    • I/O 通常采用 DMA 方式
• 网络设备接口：
  • 又称网络套接字（socket）接口
  • 套接字接口的系统调用使应用程序创建的本地套接字连接到远程应用程序创建的创建的套接字，通过此连接发送和接收数据

（2）阻塞 I/O 和非阻塞 I/O

• 阻塞 I/O ：
  • 指当用户进程调用 I/O 操作时，进程就被阻塞，需要等待 I/O 操作完成，进程才被唤醒继续执行
  • 大多数 OS 提供的 I/O 接口都是采用阻塞 I/O
  • 优点：操作简单，实现难度低，适合并发量小的应用开发
  • 缺点：I/O 执行阶段进程会一直阻塞下去
• 非阻塞 I/O ：
  • 指用户进程调用 I/O 操作时，不阻塞该进程，但进程需要通过轮询的方式来查询 I/O 操作是否完成
  • 优点：进程在等待 I/O 期间不会被阻塞，可以做其他事情，适合并发量大的应用开发
  • 缺点：轮询方式询问 I/O 结果，会占用 CPU 的时间

二、设备独立性软件

1、设备独立性软件

• 与设备无关的软件是 I/O 系统的最高层软件，它的下层是设备驱动程序，其间的界限因操作系统和设备的不同而有所差异

2、高速缓存与缓冲区

（1）磁盘高速缓存

• 操作系统中使用磁盘高速缓存技术来提高磁盘的 I/O 速度，对访问高速缓存要比访问原始磁盘数据更为高效
• 磁盘高速缓存逻辑上属于磁盘，物理上是驻留在内存中的盘块
• 磁盘高速缓存在内存中分为两种形式：
  1. 在内存中开辟一个独立的空间作为磁盘高速缓存。大小固定
  2. 把未利用内存空间作为一个缓冲池，仅供请求分页系统和磁盘 I/O 时共享

（2）缓冲区

• 引入缓冲区的目的：
  • 缓和 CPU 与 I/O 设备间速度不匹配的矛盾
  • 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制
  • 解决基本数据单元大小（即数据粒度）不匹配的问题
  • 提高 CPU 和 I/O 设备之间的并行性
• 实现方法：
  • 采用硬件缓冲器，但由于成本太高，除一些关键部位外，一般不采用硬件缓冲器
  • 采用缓冲区（位于内存区域）
• 根据系统设置缓冲区的个数，缓冲技术可以分为：

1）单缓冲

• T时间：数据从磁盘 ---> 缓冲区
• M时间：数据从缓冲区 ---> 用户
• C 时间：CPU 对一块数据处理的时间
  
• 注意：
  • 当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出
  • 当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出
    
• 结论：采用单缓冲策略，处理一块数据平均耗时 Max (C, T)+M

2）双缓冲

• 假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空
  
• 结论：采用双缓冲策略，处理一个数据块的平均耗时为 Max (T, C+M)

3）循环缓冲

• 将多个大小相等的缓冲区连接成一个循环队列
• 下图中橙色表示已充满数据的缓冲区，绿色表示空缓冲区
• 当需要向缓冲区中冲入数据时，只要找到in指针指向的空缓冲区，向其中冲入数据，然后再把in指针指向下一个空缓冲区
• 当需要取出满缓冲区的内容时，找到 out 指针执行的满缓冲，读完数据后，将指针指向下一个满缓冲区。
  

4）缓冲池

• 缓冲池由系统中共用的缓冲区组成
• 缓冲区按使用状况可以分为：
  • 空缓冲队列
  • 输入队列：存储的是从设备发送给内存的数据
  • 输出队列：存储的是从内存发送给设备的数据
• 根据一个缓冲区在实际运算中扮演的功能不同分为四种工作缓冲区：
  • 用于收容输入数据的工作缓冲区（hin）
  • 用于提取输入数据的工作缓冲区（sin）
  • 用于收容输出数据的工作缓冲区（hout）
  • 用于提取输出数据的工作缓冲区（sout）
    
• 收容输入：
  • 输入进程需要输入数据时，从空缓冲队列的队首摘下一个空缓冲区，作为收容输入工作缓冲区，然后将数据输入其中，装满后再将它挂到输入队列的队尾
• 提取输入：
  • 计算进程需要输入数据时，从输入队列的队首取得一个缓冲区，作为提取输入工作缓冲区，从中提取数据，用完该数据后将它挂到空缓冲队列的队尾
• 收容输出：
  • 计算进程需要输出数据时，从空缓冲队列的队首取得一个空缓冲区，作为收容输出工作缓冲区，当其中装满数据后，再将它挂到输出队列的队尾
• 提取输出：
  • 输出进程需要输出数据时，从输出队列的队首取得一个装满输出数据的缓冲区，作为提取输出工作缓冲区，当数据提取完后，再将它挂到空缓冲队列的队尾

（3）高速缓存与缓冲区的对比

3、设备分配与回收

• 设备分配：指根据用户的 I/O 请求分配所需的设备

（1）设备分配的策略

1）设备分配原则

• 设备固有属性决定了设备的使用方式（充分发挥设备的使用效率，尽可能让设备忙碌）
• 设备独立性可以提高设备分配的灵活性和设备的利用率（设备独立性是指用户使用设备的透明性，即用户程序与实际使用的物理设备无关）
• 设备安全性可以保证分配设备时不会导致永久阻塞（要避免造成进程死锁）

2）设备的固有属性

• 独占设备：将它分配给某个进程后，便由该进程独占，直至进程完成或释放该设备
• 共享设备：可将它同时分配给多个进程，需要合理调度各个进程访问该设备的先后次序
• 虚拟设备：属于可共享设备，可将它同时分配给多个进程使用

3）设备分配算法

• FCFS 算法：根据设备提出请求的先后次序
• 最高优先级算法：根据设备的优先级

4）设备分配的方式

• 静态分配：
  • 主要用于对独占设备的分配
  • 进程运行前为其分配全部所需资源，运行结束后归还资源
  • 一旦分配，这些设备、控制器就一直为该作业所占用，直到该作业被撤销
  • 特点：不会出现死锁，但设备的使用效率低
• 动态分配：
  • 进程运行过程中通过系统调用命令动态申请设备资源
  • 一旦用完，便立即释放
  • 特点：有利于提高设备利用率，但若分配算法使用不当，则有可能造成进程死锁

5）设备分配中的安全性

• 设备分配安全性是指设备分配中应防止发生进程死锁

• 安全分配方式：

  • 每当进程发出 I/O 请求后，便进入阻塞态，本次 I/O 完成后才将进程唤醒
  • 在一个时间段内每个进程只能使用一个设备
  • 优点：破坏了请求等待条件，不会死锁，设备分配安全
  • 缺点：对于一个进程来说，CPU 和 I/O 设备只能串行工作，系统资源利用率低

• 不安全分配方式：

  • 进程发出 I/O 请求后，系统为其分配 I/O 设备，进程可继续执行，之后还可以发出新的 I/O 请求，只有某个 I/O 请求得不到满足时才将进程阻塞
  • 一个进程可以同时使用多个设备
  • 优点：进程的计算任务和 I/O 任务可以并行处理，使进程推进
  • 缺点：有可能发生死锁

（2）设备分配的数据结构

• “设备、控制器、通道”之间的关系：一个通道可控制多个设备控制器，每个设备控制器可控制多个设备
  

1）设备控制表（DCT）

• 系统为每个设备配置一张 DCT，用于记录设备情况
  

2）控制器控制表（COCT）

• 每个设备控制器对应一张 COCT
• OS 根据 COCT 的信息对控制器进行操作和管理
  

3）通道控制表（CHCT）

• 每个通道对应一张 CHCT
• OS 根据 CHCT 的信息对通道进行操作和管理
  

4）系统设备表（SDT）

• 记录了系统中全部设备的情况
• 每个设备对应一个表目
  

（3）设备分配的步骤

• 以独占设备为例：

1. 分配设备：
   • 首先根据 I/O 请求中的物理设备名，查找 SDT，从中找出该设备的 DCT
   • 再根据 DCT 中的设备状态字段，可知该设备的状态：
     • 若忙，则将该进程 PCB 挂到设备等待队列
     • 若不忙，则根据一定的策略将该设备分配给该进程
2. 分配控制器：
   • 根据 DCT 找到 COCT，查询控制器的状态：
     • 若忙，则将该进程 PCB 挂到控制器等待队列
     • 若不忙，则将控制器分配给该进程
3. 分配通道：
   • 根据 COCT 找到 CHCT，查询通道的状态：
     • 若忙，则将进程 PCB 挂到通道等待队列
     • 若不忙，则将通道分配给该进程

• 注意：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动 I/O设备进行数据传送

（4）逻辑设备名到物理设备名的映射

• 目的：为了实现设备的独立性，进程中使用逻辑设备名来请求某类设备
• 逻辑设备表（LUT）：
  • 用于将逻辑设备名映射为物理设备名
  • 每个表项包含 3 项内容：
    • 逻辑设备名
    • 物理设备名
    • 设备驱动程序的入口地址
  • 两种方式：
    1. 整个系统只设置一张 LUT：
       • 所有进程的设备分配情况都记录在同一张 LUT 中
       • 要求所有用户不能使用相同的逻辑设备名
       • 主要适用于单用户系统
    2. 为每个用户设置一张 LUT：
       • 同时在多用户系统中都配置系统设备表
       • 不同用户可以使用相同的逻辑设备名
         

4 、SPOOLing 技术（假脱机技术）

（1）脱机技术

• 批处理阶段引入了脱机输入/输出技术（用磁带完成）
• 引入目的：
  • 缓解了 CPU 与慢速 I/O 设备的速度矛盾
  • 实现预输入、缓输出
• 组成：外围控制机 + 更高速的设备（磁带）
  

（2）假脱机技术的实现

• 假脱机技术：又叫 SPOOLing 技术，用软件的方式模拟脱机技术，不需要外围机，是一项将独占设备改造成共享设备的软件技术
  

1）输入井和输出井

• 在磁盘上开辟出的两个存储区域
• 输入井：模拟脱机输入时的磁盘，用于收容 I/O 设备输入的数据
• 输出井：模拟脱机输出时的磁盘，用于收容用户程序的输出数据
• 一个进程的输入（或输出）数据保存为一个文件
• 所有进程的数据输入（或输出）文件链接成一个输入（或输出）队列

2）输入缓冲区和输出缓冲区

• 在内存中开辟的两个缓冲区
• 输入缓冲区：暂存由输入设备送来的数据，以后早传送到输入井
• 输出缓冲区：暂存从输出井送来的数据，以后再传送到输出设备

3）输入进程和输出进程

• 用于模拟脱机技术的外围控制机
• 输入进程：
  • 将用户要求的数据从输入设备传送到输入缓冲区，再存放到输入井中
  • CPU 需要输入数据时，直接从输入井中读入内存
• 输出进程：
  • 将用户要求输入的数据从内存传送到输出井
  • 待输出设备空闲时，再将输出井中的数据经输出缓冲区输出至输出设备。

4）井管理程序

• 用于控制作业与磁盘井之间信息的交换

5）SPOOLing 系统的特点

• 提高了IO速度，将对低速IO设备执行的IO操作演变为对磁盘缓冲区中数据的存取
• 将独占设备变为共享设备，且实际上没有为任何进程分配设备
• 提高了独占设备的利用率，缓和了CPU和低速IO设备之间的速度不匹配的矛盾
• 实现了虚拟设备功能，对每个进程而言，都认为自己独占了一个设备
• 以空间换时间，需要磁盘空间（输入输出井）和内存空间（输入输出缓冲区）

（3）共享打印机的实现

• 打印机是独占设备，只允许各个进程串行使用设备，一段时间内只能满足一个进程的请求
• 利用用 SPOOLing 技术将其改造成“共享设备”，实现原理：
  • 当用户进程请求打印输出时，SPOOLing 系统同意打印，但是并不真正立即把打印机分配给该进程，而由假脱机管理进程完成两项任务：
    1. 在磁盘缓冲区中为之申请一个空闲盘块，并将要打印的数据送入其中暂存
    2. 为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到假脱机文件队列上
  • 当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求打印数据从输出井传送到输出缓冲区，再输出到打印机打印
• 虽然系统中只有一台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于一个逻辑设备）使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享
  

5、设备驱动程序接口

• 设备驱动程序：是 I/O 系统的上层与设备控制器之间的通信程序
• 具有的功能：
  • 接收由上层软件发来的命令和参数，并将抽象要求转换为与设备相关的具体要求【例如，将抽象要求中的盘块号转换为磁盘的盘面号、磁道号及扇区号】
  • 检查用户 IO 请求的合法性，了解设备的工作状态，传递与设备操作有关的参数，设置设备的工作方式
  • 发出 I/O 命令，若设备空闲，则立即启动它，完成指定的 I/O 操作；若设备忙，则将请求者的 PCB 挂到设备队列上等待
  • 及时响应由设备控制器发来的中断请求，并根据其中断类型，调用相应的中断处理程序进行处理
• 与普通应用/系统程序的差异：
  • 设备驱动程序将抽象的I/O 请求转换成具体的 I/O 操作后，传送给设备控制器，并将设备控制器中记录的设备状态和 I/O操作的完成情况及时地反馈给请求进程
  • 设备驱动程序与设备采用的 I/O 控制方式紧密相关，常用的 I/O 控制方式是中断驱动方式和 DMA 方式
  • 设备驱动程序与硬件密切相关，对于不同类型的设备，应配置不同的设备驱动程序
  • 由于设备驱动程序与硬件紧密相关，目前很多设备驱动程序的基本部分已固化在 ROM
  • 设备驱动程序应允许同时多次调用执行
• 如何使所有的设备驱动程序都有统一的接口：
  • 要求每个设备驱动程序与操作系统之间都有相同或相近的接口，便于添加新的设备驱动程序和编制设备驱动程序
  • 要将抽象的设备名转换为具体的物理设备名，并且进一步找到相应的设备驱动程序入口
  • 对设备进行保护
    
• 对于每种设备类型，例如磁盘，OS 都要定义一组驱动程序必须支持的函数（读、写、格式化等）
• 驱动程序包含一张表格，具有针对这些函数指向驱动程序自身的指针
• 装载驱动程序时，OS 记录这个函数指针表的地址，当 OS 调用一个函数时，可通过这张表格发出间接调用
• 函数指针表定义了驱动程序与操作系统其余部分之间的接口

三、磁盘与固态硬盘

1、磁盘

（1）磁盘、磁道、扇区

• 磁盘的表面是由一些磁性物质组成，可以用这些磁性物理记录二进制数据
• 磁盘表面被划分成多个磁道
• 每个磁道被划分为多个扇区，每个扇区就是一个“磁盘块”
• 每个扇区的数据量相同（如 1 KB）
  

（2）盘面、盘柱

• 磁盘是由多个盘片摞起来的，每个盘片有两个盘面
• 每个盘面都对应一个磁头，所有的磁头都连在同一个磁臂上
• 磁臂可以沿着盘面作径向运动，从而带动磁头到达不同的磁道来对不同扇区的读写操作
• 所有盘面中的相对位置相同的磁道组成了柱面
  

（3）在磁盘中读/写数据

• 在磁盘中读写数据，需要借助磁头
  • step 1：将磁头移动到想要读/写的扇区所在的磁道
  • step 2：磁盘会转动，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作

（4）磁盘的物理地址

• 使用 （柱面号，盘面号，扇区号） 来定位任意一个磁盘块
• 文件数据存放在外存中的几号块，这里的块号就可以转换为（柱面号，盘面号，扇区号）的地址形式
• 根据物理地址读取一个“块”：
  1. 根据柱面号移动磁臂，让磁头指向指定柱面
  2. 激活指定盘面对应的磁头
  3. 磁盘旋转的过程，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读写

（5）磁盘的分类

• 根据磁头是否可以活动划分：
  • 活动头磁盘
  • 固定头磁盘
• 根据盘面是否可以更换划分：
  • 可换磁盘
  • 固定盘磁盘

2、磁盘的管理

（1）磁盘初始化

• 低级格式化【物理格式化】：
  • 在磁盘可以存储数据之前，将它分为扇区，以便磁盘控制器能够进行读写操作
  • 每个扇区通常由头部、数据区域（通常为 512 B 大小）和尾部组成
  • 头部和尾部包含了一些磁盘控制器的使用信息：
    • 利用磁道号、磁头号和扇区号标志一个扇区
    • 利用 CRC 字段对扇区进行校验

（2）分区

• 将磁盘分为由一个或多个柱面组成的分区 (如 C 区，D 区)，每个分区的起始扇区和大小都记在磁盘主引导记录的分区表
• 对物理分区进行逻辑格式化【创建文件系统】，操作系统将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲空间和己分配的空间以及一个初始为空的目录
• 簇：
  • 将多个相邻的扇区组合在一起，提高效率
  • 一簇只能存放一个文件的内容
  • 文件所占用的空间只能是簇的整数倍
  • 文件大小小于一簇（甚至是 0 字节），也要占用一簇的空间

（3）引导块

• 计算机启动时需要运行初始化程序（自举程序） 来初始化 CPU、寄存器、设备控制器和内存等，接着启动 OS
• ROM 中存放很小的自举装入程序：避免改变自举代码而需改变 ROM 硬件
• 完整的自举程序存放在磁盘的启动块（引导块/启动分区）上，启动块位于磁盘的固定位置
• 拥有启动分区的磁盘称为启动磁盘或系统磁盘（C: 盘）
• 计算机开机工作：先运行“自举装入程序”，通过执行该程序就可找到引导块，并将完整的“自举程序”读入内存，完成初始化

（4）坏块的管理

• 简单的磁盘：逻辑格式化时将坏块标记出来
• 复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区

3、磁盘调度算法

• 磁盘调度算法的目的：为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的
• 寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，可以节省一些不必要的寻道时间，从而提高磁盘的访问性能
• 绝大数 OS 为改善磁盘访问时间，以簇（一组块）为单位进行空间划分

（1）一次磁盘读/写操作需要的时间

1）寻道时间 Ts

• 在读/写数据前，需要将磁头移动到指定磁道所花费的时间
• 分两步：
  1. 启动磁头臂消耗的时间 s
  2. 移动磁头消耗的时间：假设磁头匀速移动，每跨越一个磁道消耗时间为 m，共跨越 n 条磁道
• Ts=s+m×n

2）延迟时间 Tr

• 通过旋转磁盘，使磁头定位到目标扇区所需要的时间
• 设磁盘转速 r（单位：转/秒）
• Tr= \frac{1}{2}*\frac{1}{r}=\frac{1}{2r}
• 1/r 就是转一圈所需的时间，找到目标扇区平均需要转半圈，因此再乘以 1/2

3）传输时间 Tt

• 从磁盘读出或向磁盘写入数据所经历的时间
• 设磁盘转速 r，此次读/写的字节数为 b，每个磁道上的字节数为 N
• Tt=\frac{1}{r}*\frac{b}{N}=\frac{b}{rN}
• 每个磁道可存 N 字节数据，因此 b 字节数据需要 b/N 个磁道【扇区】才能存储
• 平均传输时间等于一个扇区划过磁头下方所需要的时间【2022 大题】
• 读/写一个磁道所需的时间刚好是转一圈的时间 1/r

4）总的平均时间

• T= T_s+\frac{1}{2r}+\frac{b}{rN}
• 无法通过操作系统优化延迟时间和传输时间，所以只能优化寻道时间

（2）调度算法

• 假设有一个请求序列，每个数字代表磁道的位置：98，183，37，122，14，124，65，67，初始磁头当前的位置是在第 53 磁道

1）先来先服务算法 FCFS

• 思想：先到来的请求，先被服务
• 优点：
  • 公平，简单
  • 请求访问的磁道比较集中的话算法性能还算可以
• 缺点：
  • 比较简单粗暴
  • 如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散
  • 算法在性能上就会显得很差，因为寻道时间过长
• 处理顺序：98，183，37，122，14，124，65，67
  

2）最短寻找时间算法 SSTF

• 思想：优先选择从当前磁头位置所需寻道时间最短的请求
• 优点：
  • 是贪心算法的思想，只是选择眼前最优，但是总体未必最优
  • 比 FCFS 效果好
• 缺点：
  • 存在饥饿现象
  • 产生饥饿的原因是磁头在一小块区域来回移动
• 处理顺序：65，67，37，14，98，122，124，183
  

3）扫描/电梯算法 SCAN

• 思想：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向
• 优点：
  • 性能较好，寻道时间较短
  • 不会产生饥饿现象
• 缺点：
  • 中间部分的磁道会比较占便宜
  • 中间部分相比其他部分响应的频率会比较多
  • 也就是说每个磁道的响应频率存在差异
• 处理顺序：
  • 假设扫描调度算先朝磁道号减少的方向移动
  • 磁头先响应左边的请求
  • 直到到达最左端后，才开始反向移动，响应右边的请求
  • 7，14，0，65，67，98，122，124，183
• 改进 LOOK 算法：只要在磁头移动方向上不再有请求，就立即改变磁头方向
  

4）循环扫描算法 C-SCAN

• 思想：
  • 只有磁头朝某个特定方向移动时，才处理磁道访问请求
  • 而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头
  • 这个过程是很快的，并且返回中途不处理任何请求
  • 特点：磁道只响应一个方向上的请求
• 优点：对于各个位置磁道响应频率很平均
• 缺点：相比于 SCAN 算法，平均寻道时间更长
• 处理顺序：
  • 假设循环扫描调度算先朝磁道增加的方向移动
  • 磁头先响应了右边的请求
  • 直到碰到了最右端的磁道 199，就立即回到磁盘的开始处
  • 但这个返回的途中是不响应任何请求的
  • 直到到达最开始的磁道后，才继续顺序响应右边的请求
  • 65，67，98，122，124，183，199，0，14，37
• 改进 C-LOOK 算法：只要在磁头移动方向上不再有请求，就立即改变磁头方向
  

（3）减少磁盘延迟时间的方法

• 磁头读入一个扇区数据后需要一小段时间处理
• 如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”

1）交替编号

• 思想：让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小
  
• 思考：磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）
• 读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间
  

2）错位命名

• 思想：让相邻盘面的扇区编号错位
  

（4）固态硬盘