操作系统复习总结

程序员文章站 2022-07-05 08:51:31

...

2019 BUAA 操作系统复习

写在前面

本文整理了北航 2019 年操作系统的课程资料，摘取了个人认为的重点加以总结。全文约 15000 字，远不足以覆盖所有知识点，甚至有些地方我的理解也可能有所偏差。如有错误，望指正。

本文目录太长，这里就不放了。总体顺序是

引论
启动
内存管理
进程管理
设备管理
磁盘管理
文件系统

最开头的部分主要总结了基本概念、各类调度算法以及控制块的相关内容。

总

基本概念

内存

（逻辑）地址空间 逻辑地址的集合。
内存空间 物理地址的集合。
碎片内存中无法被利用的存储空间。
内部碎片 分配给作业的存储空间中未被利用的部分。
外部碎片 系统中无法利用的小的空闲分区。
内存抖动 内存中的页被频繁调换，导致 CPU 只有很少一部分时间用于运算。

页式存储

页逻辑空间被划分成的大小相等（通常为 4KB）的块，是信息的物理单位。
页框内存空间被划分成的和页大小相同的块。
页表项 PTE 一个页与页框的对应关系。
页目录项 PDE 多级页表机制中，存储一个页表与页框的对应关系。
页表每个进程中存放页表项的区域。

段式存储

段组成程序的逻辑单位，如数据段、程序段等。

进程

原语若干条指令组成的不可分割的指令序列。
程序一组可以被执行的指令。
线程程序中的一个可执行单元。
进程程序的一次执行。

进程管理

并发两个程序的执行时间重叠。
并行两个程序在同一时刻同时运行。
竞争多个进程在读写一个共享数据时，运行结果依赖于他们的执行顺序。
临界资源 可能造成竞争的数据。
临界区 进程中访问临界资源的部分代码。
互斥限制某一资源同时只允许一个访问者对其进行访问，但无法保证访问顺序，属于进程间的间接制约关系。
同步在互斥的基础上实现有序访问，属于进程间的直接制约关系。

死锁

死锁一组进程中，每个进程都无限等待其他进程所占有的资源。
活锁由于某些条件没有满足，进程不断尝试又不断失败。
饥饿进程长时间等待执行。
饿死饥饿到丧失进程执行的实际意义。
*进程某个进程由于请求无法满足，而被系统*。

磁盘

扇区 sector 盘片上的许多扇形区域。
磁道 track 盘片上的同心圆。
柱面 cylinder 硬盘中，不同盘片相同半径的磁道所组成的圆柱。
磁头 head 每个磁盘的两面各有一个磁头。

文件系统

目录文件系统层次结构的一个非终结结点，可以包含多个目录项。
目录项 一个目录下的目录或文件。
文件带有文件名的一组信息项的序列；文件系统层次结构的一个终结结点。
记录一组相关数据项的集合。
信息项 构成文件内容的基本单位。

控制块

进程控制块 PCB

每个 PCB 唯一的对应一个进程，是系统感知进程存在的唯一标志。所有进程的 PCB 统一存放在一张进程表中。

基本信息

进程标识符

父进程号

处理机信息

进程上下文

指令计数器

用户栈指针

调度信息

当前运行状态

优先级

阻塞原因

控制信息

程序和数据地址

信号量

资源清单

PCB 使程序称为一个进程，使独立运行基本单位的标志。它可以实现间断性运行；提供进程管理和调度所需的信息；实现同步与通信等。

进程表组织方式

线性表 将所有的 PCB 连续的存放在内存的特定区域，适用于进程数量较少的情况。
索引表 按照进程状态分别建立索引表。
链接表 按照进程状态分别建立调度序列（双向链表）。

文件控制块 FCB

FCB 也就是索引结点或 i 结点。每个 FCB 唯一的对应一个文件，并记录文件的相关信息

基本信息

文件名

物理位置（索引表）

文件逻辑结构

文件物理结构

访问控制

文件所有者

访问权限

使用信息

创建时间

上一次修改时间

索引表中记录了文件对应的磁盘块号。如果文件较大，可以使用多级索引。

调度算法

内存分配

首次适应 First fit

将空白区按存储空间地址递增的顺序构成一个队列。每次从队列头开始查找，分配第一个满足请求的空白块。首次适应会优先利用低地址的分区，留下许多难以利用的碎片。而每次查找又都是从低地址开始，增加了查找开销。

下次适应 Next fit

将空白区构成一个循环链。每次从上次查找结束的位置开始查找，分配第一个满足请求的空白块。可以使空间利用更加均衡，但是会导致缺乏大的空闲分区。

最佳适应 Best fit

总是选择大小最接近请求的空白块进行分配。保留了大的空闲分区，但是会留下许多碎片。

最坏适应 Worst fit

总是分配最大的空白块。最大的空闲分区总是首先被划分，因此大作业的请求往往会得不到满足。

页面置换

最优置换 Optimal

每次将下一次使用时间最晚的页换出。

优点页错误率最低。
缺点无法被实现。

先进先出 FIFO

每次将在内存中存在最久的页换出。

优点实现简单。
缺点性能较差，且有 Belady 现象。

Belady 现象

FIFO 算法的共有现象：队列长度增加但命中率下降。

Second Chance

FIFO 算法的改进。为每个页面增加一个标志位，在置换之前检查。如果标志位为 1，说明该页被访问过，则将其清零并移至队列尾部。

Clock

FIFO 算法的改进。将 Second Chance 中的队列改为环形队列，避免了元素移动。

最近最久不用 LRU

换出最后一次使用时间最早的页。

最近最少使用 LFU

换出自上次调入以来，使用频率最低的页。

进程调度

批处理系统

先来先服务 FCFS

按照进程上一次变为就绪状态的先后次序非抢占式分配 CPU。特点

有利于长作业
有利于 CPU 密集型作业

最短作业优先 SJF

优先将 CPU 分配给预计执行时间短的进程。

优点改善平均周转时间，缩短作业的等待时间；提高系统吞吐量。
缺点对长作业非常不利；不能划分优先级；难以估计进程执行时间。

最短剩余时间优先 SRTF

优先将 CPU 抢占式分配给剩余执行时间短的进程。缺点是长作业长时间得不到运行。

最高响应比优先 HRRF

选择相应比 RP 最大的作业投入运行。
$RP = 1 + \frac{已等待时间}{剩余运行时间}$
算法效果

等待时间相同时，短作业的相应比更高。
剩余时间相同时，等待时间越长相应比越高。（长作业得以运行）

缺点是计算相应比使性能降低。

交互式系统

时间片轮转 RR

通过实践片轮转，提高进程并发性，降低响应时间，从而提高资源利用率。时间片长度

过长退化为 FCFS，响应时间长。
过短上下文切换次数增加，响应时间长。

多级队列 MQ

引入多个就绪队列。通过各队列的区别对待，达到综合调度的目标。

多级反馈队列 MFQ

设置多级队列，规定第一个队列的优先级最高、优先级越低的队列时间片越长。新进程首先加入第一个队列。如果一个时间片内没有执行完，就将优先级降低，加入另一个队列。队列内按照 FCFS 调度。仅当高优先级的队列为空，才抢占式调度低优先级的队列。

优点对短进程有利；适应 I/O 进程特点；不必估计进程的执行时间。

实时调度

对任务集 $S = \{t_1, t_2, \dots, t_n\}$ ， $T$ 是周期， $c$ 是执行时间， $D$ 是截止时间。通常有 $D_i = T_i$ 。定义 CPU 利用率
$U = \sum_{i=1}^n \frac{c_i}{T_i}$
前提条件

任务集已知，且任务间相互独立。
所有任务都是周期性的，且在限定时间内完成。
调度时，进程切换的时间忽略不计。

静态表调度 Static table-driven

实现确定任务调度方案。

优点无需计算，开销小。
缺点灵活性低，只适用于完全固定的任务场景。

单调速率调度 RMS

静态最优调度算法，开销小，灵活性好。规定任务周期越小，其优先级越高，也就越早被调度。

最早截止时间优先 EDF

优先调度任务截止时间早的进程。

磁盘调度

先来先服务 FCFS

优点简单，公平。
缺点效率低，增加机械磨损。

最短寻道时间优先 SSTF

优点缩短了磁盘平均服务时间。
缺点可能导致某些访问长时间得不到服务。

扫描算法 SCAN

磁头在磁盘上来回扫描，每次服务完最远端的请求后折返。

优点可以避免饥饿现象。
缺点不利于原理磁头一端的访问请求。

循环扫描算法 CSCAN

磁头从 0 号柱面开始扫描。每次服务完最远端的请求后，快速回到 0 号柱面。返回过程中不提供服务。

优点避免了SCAN算法的不公平性。

引论

基本类型

批处理系统

批处理系统是加载在计算机上的一个系统软件。它可以控制计算机自动的、成批的处理作业。按照输入输出系统是否脱离主机（CPU）控制，批处理系统又可以分为以下两个阶段。

联机批处理系统

优点利用磁带实现了作业到作业的自动转接，减少了手工操作的时间。
缺点在作业输入和结果输出时，主机处于忙等状态。

脱机批处理系统

优点利用卫星机缓解了主机与设备的矛盾。
缺点内存中只有一道作业，如果发出 IO 请求，会导致 CPU 空闲。

多道程序系统

允许多个程序同时进入内存，并交替在 CPU 中运行。所有程序共享系统中的软硬件资源。当一道程序因 IO 请求被阻塞时，CPU 转而执行另一道程序。

多道程序设计技术提高了整个系统的资源利用率和系统吞吐量。

多道批处理系统

多道批处理系统（简称批处理系统），是在批处理系统中引入多道程序设计技术后形成的。它具有以下两个特点

多道系统内可以同时容纳多个作业，按照一定的调度原则自动转接。
成批作业一旦进入系统，就不允许用户直接干预其运行。

多道批处理系统的优缺点

优点系统吞吐量大，资源利用率高。
缺点平均周转时间长，没有交互作用能力。

分时系统（交互式系统）

分时技术指，把处理机的运行时间分成很短的时间片，按时间片轮转把处理机分配给各联机作业使用。分时系统具有以下特点

多路性 多个用户可以同时使用同一台计算机。
交互性 用户可以根据系统对请求的相应结果，进一步向系统提出新的请求。
独立性 用户之间相互独立，互不干扰。
及时性 系统对请求的响应时间短。

UNIX 属于分时操作系统。

网络化系统

网络操作系统

在传统 OS 上增加软件层，主要提供联网功能和资源的远程访问，实现多机互联。

分布式操作系统

多台机器统一管理，形成单一系统。相比网络操作系统，分布式操作系统对用户和应用高度透明。

数据透明
执行透明
保护透明

实时系统

实时系统具有确定的相应时间，同时也要求所提供的服务具有确定性。

特征

并发性

并发指，两个或多个时间在同一时间间隔内发生。多个程序的执行在宏观上并行，微观上串行。并发通过分时实现。

共享性

系统中的软硬件资源可以被多个并发执行的程序共同使用。资源共享通过互斥访问和同时访问实现。

虚拟性

虚拟处理机技术

利用多道程序设计技术，为每道程序建立一个进程。多道程序并发执行，分时使用一台处理机。

虚拟内存技术

建立一个地址固定、空间巨大的逻辑内存空间让应用程序运行。

虚拟设备技术

将一台物理设备虚拟为多台逻辑设备，允许多个用户同时访问。

异步性

多个程序的执行顺序不确定。
每个程序的执行时间不确定。

系统引导

基本地址空间

/*
 o 4G --> +-------------------+-----------------------
 o        |      Mapped       |  kseg2
 o        +-------------------+------------0xc000 0000
 o        | Unmapped uncached |  kseg1
 o        +-------------------+------------0xa000 0000
 o        |  Unmapped cached  |  kseg0
 o        +-------------------+------------0x8000 0000
 o        |    User space     |  kuseg
 o  0 --> +-------------------+ ----------------------
*/

段	MMU	cache	内容
kuseg	$\checkmark$	$\checkmark$
kseg0	$\times$	$\checkmark$	操作系统内核
kseg1	$\times$	$\times$
kseg2	$\checkmark$

可以看出，在 MMU 和 cache 都没有被设置好的情况下，kseg1 是唯一可以正常使用的地址空间。

ROM/Flash 启动时的入口向量是 0xBFC00000，属于 kseg1 。清除高三位后，这一地址映射到物理内存的 0x1FC00000 。

引导加载程序

Bootloader 是系统加电后运行的第一段软件代码，运行在操作系统内核之前。大多数引导加载程序分为 stage1 和stage2 两部分

stage1 用于初始化，依赖于 CPU 体系结构，用汇编语言实现。
stage2 用于实现复杂功能，用 C 语言实现。

内存管理

内存管理的功能有

内存的分配与回收
存储保护
地址转换
动静态重定位
存储共享
虚拟内存

存储管理方式

分区存储

把内存分为一些分区，每个应用程序占用其中的一个或几个分区。内核占用其中一个分区。分区存储适用于多道程序系统和分时系统，支持并发，但难以实现共享。

固定分区

把内存划分为多个固定大小的连续分区，分区大小不一定相等。采用分区表记录分区大小和使用情况。

优点易于实现。
缺点造成内碎片浪费；限制了并发数（分区数）。

可变分区

分区的大小可变，适应程序需要。可变分区不会产生内碎片，但会产生外碎片。

空间管理

内核需要跟踪内存的使用情况。

位图表示法

给每个分配单元分配一个二进制位表示使用情况。

优点空间成本固定；时间成本低。
缺点没有容错能力。

链表表示法

将分配单元按照是否限制链接成一个链表。

优点有一定容错能力。
缺点空间成本取决于程序数量；扫描链表效率低。

页式存储

把一个逻辑地址连续的程序分散存放到若干不连续的内存区域内，既可以充分利用内存空间，有可以减少移动带来的开销。

每个逻辑地址被分为高位虚页号 VPN 和低位页内偏移。当进程要访问某个逻辑地址时，地址变换机构首先根据 VPN 在也表中找到与之对应的实页号 PPN。如果找不到，则产生地址越界中断。将 PPN 与页内偏移相加，即可得到物理地址。

段式存储

段式存储具有以下优点

方便编程
信息共享 共享以信息的逻辑单位为基础。
信息保护
动态增长 程序的某些段可以实现（数据段）。
动态链接 程序运行时才把主程序和目标程序段链接起来。

段页式存储

用分段的方法来管理逻辑地址，用分页的方法来管理物理地址。

虚拟存储

虚拟存储为每个进程提供了一个大的、一致的、连续的和私有的地址空间，让每个进程认为自己在独占系统的存储资源。虚拟存储的基本原理是

装入程序时，只加载当前需要执行的部分页和段到内存，即可开始执行。
程序执行过程中，如果需要访问的地址发生缺页，则触发缺页中断，由内核完成调页。
内核可以将暂时不用的页换出，从而调入新页或段。

虚拟存储的特征有

离散性 物理内存和虚拟地址空间的不连续。
多次性 程序分为多次被调入内存运行。
对换性 允许作业运行时被换入换出，提高内存利用率。
虚拟性 程序可以从逻辑角度访问存储器。

优缺点

优点可以在较小的内存中执行大作业；提高并发性；对程序员透明；进程虚拟空间大。
缺点时间开销大（CPU 开销和内存交换开销）。

页面调入

预调页 同时将需要的所有页调入内存。
按需调页 仅当需要时才将页调入内存。

缺页错误

当进程执行时需要访问的页面不在内存中时，会引发缺页中断，由内核将页调入。执行过程如下

现场保护 陷入内核，保存必要的信息。
页面定位 查找发生页面中断的虚拟页面（cp0_epc 寄存器）。
权限检查 检查虚拟地址的有效性。
查找页框 查找一个空闲的页框，或根据置换算法换出一个页框。
旧页面写回 如果要换出的页框被修改，需要将其写回磁盘。
页面调入 将保存在磁盘上的页复制到页框中。
更新页表
恢复现场 恢复缺页中断发生前的状态。
继续执行 程序跳回引发缺页中断的指令，进行访存。

地址转换

页表

哈希页表

哈希页表常用于处理超过 32 为的地址空间。页表的每项包含一个链表，链表中的元素有三个域

VPN
PPN
指向下一元素的指针

反置页表

一般情况下，内核为每个进程创建一个页表，并将 VPN 作为索引。这种方法的缺点是造成了空间浪费。反置页表使用 PPN 作为索引，对应进程号和进程内的 VPN。可以加入哈希表来降低页表检索的时间开销。

优点页表大小只与物理内存有关。
缺点地址变换需要遍历整个页表进行检索；很难共享内存。

多级页表

如果逻辑地址空间很大，划分的页就会比较多，页表的占用空间会很大。对于 32 位系统，如果页面大小为 4KB，那么逻辑地址空间由 $2^{20}$ 页构成，页表需要占据 4MB 空间。为了解决这个问题，可以使用多级页表，只将当前需要的部分页表调入内存。多级页表中的每一级，记录的都是物理页号。

由于存在自映射，多级页表的实际占用空间可以和一级页表相等。

MMU

如果系统采用 N 级页表，一次访存操作需要实际访存 $N+1$ 次。为了提高地址转换的效率，CPU 内部使用 MMU 加速。MMU 内部包含的主要部件有

TLB 页表 cache，用于存放 VPN 和 PPN 的部分对应关系。
TLB 控制单元 控制 TLB 的填充、刷新与越界检查。
页表遍历单元 用于查找多级页表，并将结果送给 TLB 控制单元。

MMU 的工作流程是

根据 va 在 TLB 中查找。如果没有的应的 PTE，页表遍历单元工作。
如果找到 PTE，检查访问权限，并返回物理地址。否则说明该地址尚未映射到内存，触发缺页中断。

主要技术

覆盖技术

覆盖技术主要用在早期 OS 中。它把一个程序划分为多个功能相对独立的程序段，共享主存的同一个区域。一般要求作业各模块之间有明确的调用关系，覆盖操作对程序员不透明。

交换技术

交换技术用在现代 OS 中。它把暂时不用的某些程序及数据从主存转移到辅存中，以便读入指定的程序和数据。

优点增加并发运行的程序数目；对程序员透明。
缺点对换操作增加时间开销。

进程管理

进程

一个程序可以对应多次计算，每一次计算对应一个进程。进程是系统进行资源分配的最小单位。

特征

动态性
并发性 多个进程实体可以在一段时间内同时运行。
独立性 在传统 OS 中，进程是独立运行的最小单位。（线程）
异步性 进程之间相互制约，并以各自独立的不可预知的速度执行。

状态

就绪状态 等待分配处理及资源并执行
执行状态 占用处理机资源
阻塞状态 正在执行的进程，处于某些原因放弃处理机暂停执行

内核通过调度，轮流的将就绪状态的进程设置为执行状态，并将执行状态的进程置为就绪状态。阻塞状态用于等待-唤醒机制，即进程进入阻塞状态等待被某一时间唤醒。

控制

进程控制的主要任务是进程的创建、状态转换和撤销，由内核实现。

fork

fork()函数通过系统调用创建一个与原来进程几乎完全相同的进程。为了节约开销，Linux系统采取写时复制技术 COW完成父子进程的内存拷贝。fork()函数与一般函数最主要的区别是一次调用，两次返回。子进程中返回值为 0；父进程中返回值为子进程号。

子进程中，可以使用execve()原语装载程序并运行。

上下文切换

进程上下文指的是一个进程在执行时的环境。当发生进程切换时，内核需要保存当前进程的所有状态，将其记录到进程的 PCB 中，以便再次执行该进程时能够恢复当前状态。进程上下文可以分为三个部分

用户级上下文 程序正文、数据、用户栈等
寄存器上下文 通用寄存器、程序寄存器、处理器状态寄存器等
系统级上下文 进程控制块、内核栈等

进程上下文切换通常发生在进程调度时，由调度器执行。而陷入内核由中断异常引发，只需要改变 CPU 模式（保存现场），相比上下文切换较为简单。

线程

线程与进程的最主要区别在于，同一进程的多个线程之间共享相同的地址空间，因此进程是资源拥有者而线程是可执行单元。线程在共享数据的同时，可以拥有私有堆栈。

线程的出现使资源与计算分离。由于线程本身不拥有资源，因此切换线程时减少了并发的时空开销，提高了并发效率。同时进程不需要通过 IPC 进行通信，容易实现同步。

竞争

并发执行不可避免的产生了多个进程对同一个共享资源的访问，造成了资源的争夺。

Bernstein 条件

Bernstein 条件给出了并发进程无关的充分条件

$S_i :=$ 第 i 个进程
$R(S_i) :=$ $S_i$ 中被读取的变量的集合
$W(S_i) :=$ $S_i$ 中被写入的变量的集合

当下列条件同时成立时，两个进程 $S_1$ 和 $S_2$ 可并发
KaTeX parse error: Unknown column alignment: * at position 23: …{\begin{array}{*̲*rcl**} R(S_1)…

临界区管理

内核管理临界区时应满足以下条件

没有进程处于临界区时，进程可以随意进入。
任何两个进程不能同时进入临界区。
任何一个进程进入临界区的要求应在优先时间内得到满足。
当一个进程不能进入临界区时，应进入阻塞状态，避免忙等。

信号量

为了实现进程的互斥与同步，Dijkstra 提出了一种新的变量类型，称为信号量。信号量是一个确定的二元组

class Semaphore {
    int count;
    queue<Env> queue;
public:
    Semaphore(int count);
    ~Semaphore();
    semWait();
    semSignal();
}

其中 $s$ 为可用物理资源的总数， $q$ 为阻塞进程的队列。当进程从阻塞队列中释放时，根据释放顺序可以定义强信号量（采用 FIFO 策略）和弱信号量（无序）。

PV 操作

程序只允许对信号量进行原子操作 P 或 V。P 操作对应荷兰语 proberen (test)，也被称为 semWait 或 Down 操作；V 操作对应荷兰语 verhogen (increment)，也被称为 semSignal 或 Up 操作。PV 操作属于进程的低级通信。

void Semaphore::semWait()
{
    if (this.count-- <= 0) 
    {
        this.queue.push(env);
        syscall_set_env_status(0, ENV_NOT_RUNNABLE);
    }
}

void Semaphore::semSignal()
{
    if (this.count++ < 0) 
    {
        struct Env e = this.queue.pop();
        unsigned int envid = syscall_getenvid(e);
        syscall_set_env_status(envid, ENV_RUNNABLE);
    }
}

由于物理资源和进程是一一对应的，因此当 $s\le 0$ 时 $s$ 也可以表示当前被阻塞的进程个数。

应用情景

互斥 Mutual exclusion

当 $s$ 的取值仅为 0 或 1 时，该信号量也被称为二元信号量。

static Semaphore s(1);

void process1()
{
    s.semWait();
    // ...
    s.semSignal();
}

void process2()
{
    s.semWait();
    // ...
    s.semSignal();
}

用于实现互斥时，一个进程中的 PV 操作总是配对的。

有限并发 Bounded concurrency

限制最多 n 个进程并发执行

struct Semaphore s(n);

进程同步 Synchronization

只有进程 $P_j$ 执行完 $a_j$ 操作后，进程 $P_i$ 才能执行 $a_i$ 操作

struct Semaphore s(0);

void process_i()
{
    s.semWait();
    // a_i
}

void process_j()
{
    // a_j
    s.semSignal();
}

经典问题

生产者-消费者问题

若干进程通过优先的共享缓冲区交换数据。其中，生产者每次生产 1 件产品；消费者每次消费 1 件产品。设一个缓冲区有 N 个单元，任何时刻只能有一个进程可以对缓冲区操作。

#define N /* buffer size */
#define T /* item type */
Semaphore full(0);
Semaphore empty(N);
Semaphore mutex(1); // mutual exclusion
T buffer[N];
int in = 0, out = 0;

void produce()
{
    while (1)
    {
        // produce next product np
        P(empty);
        P(mutex);
        buffer[in++ % N] = np;
        V(mutex);
        V(full);
    }
}

void consumer() 
{
    while (1)
    {
        P(full);
        P(mutex);
        np = buffer[out++ % N];
        V(mutex);
        V(empty);
        // consume next product np
    }
}

读者-写者问题

对共享资源的操作，任一时刻只允许一个写者，而读者可以有多个。

int readcount = 0;
Semaphore rmutex(1); // readcount
Semaphore wmutex(1);

void read()
{
    while (1)
    {
        P(rmutex);
        if (readcount++ == 0) P(wmutex);
        V(rmutex);
        // read
        P(rmutex);
        if (--readcount == 0) V(wmutex);
        V(rmutex);
    }
}

void write()
{
    while (1)
    {
        P(wmutex);
        // write
        V(wmutex);
    }
}

哲学家就餐问题

五个哲学家围绕圆桌而坐，每两个哲学家之间放一只筷子。哲学家的动作包括思考和进餐，如何让哲学家有序进餐。

睡觉的理发师问题

理发店里有一位理发师和 N 把供顾客等待的椅子。理发师在理发时，新来的顾客如果有空位就坐下，否则离开。

#define N /* n chairs */
int waiting = 0;
Semaphore consumer(0);
Semaphore barber(0);
Semaphore mutex(1);

void comsume()
{
    P(mutex);
    if (waiting < N) 
    {
        waiting++;
        V(consumer);
        V(mutex);
        P(barber);
        get_haircut();
    } else V(mutex);
}

void barber()
{
    while (1)
    {
        P(customer);
        P(mutex);
        waiting--;
        V(barber);
        V(mutex);
        cut_hair();
    }
}

死锁

产生条件

互斥条件 进程占有的资源只能被当前进程使用。
请求和占有条件 进程已经占有至少一个资源，但又请求已被其他进程占有的资源。
不可剥夺条件 进程占有的资源只能由自身释放。
环路等待条件 存在一个进程序列，每个进程都在等待由后一个进程占用的资源。最后一个进程的后继是第一个进程。

处理方法

预防 prevention

破坏死锁的产生条件，是静态策略。

允许进程同时访问某些资源
只有当前进程所需的全部资源都不被占有时，才一次性进行分配，否则不分配任何资源。
当进程的资源请求不能被满足时，需要释放所占有的全部资源，以后重新申请。
将进程按序分配，防止进程形成环路占用资源

避免 avoidance

在资源分配之前进行判断，是动态策略。

安全序列

一个进程序列 $\{P_1, P_2, \dots, P_n\}$ 是安全的，如果
$\forall i \in \{1, 2, \dots, n\},\ max(P_i) \le possess(system) + \sum_{k = 1}^i possess(P_k)$
其中， $max$ 表示进程所需的总资源， $possess$ 表示进程当前占有的资源。

如果系统中存在这样一个安全序列，就称系统是安全的。系统进入不安全状态是死锁发生的必要条件。

银行家算法

当一个进程需要的总资源数小于等于当前系统拥有的资源数时，系统就可以进行分配；否则进程阻塞。

检测 detection

检测并解除死锁。

资源分配图 RAG

使用有向图 $G = (P\cup R, E)$ 描述进程和资源的请求情况，其中 $P$ 为所有进程构成的集合， $R$ 为所有资源构成的集合， $E$ 为边集且满足
$E \sub (P \times R) \cup (R \times P)$
对 $e \in E$ 定义
$e \in P \times R \Rightarrow e\ 为请求边 \\ e \in R \times P \Rightarrow e\ 为分配边$

化简方法 如果进程顶点只有分配边，删去这些边；如果非*进程有请求边，可以将其变为分配边。
可完全化简 经过一系列化简后可以消去图中的所有边。
死锁定理 系统处于死锁状态的充要条件是 t 时刻的资源分配图是不可完全化简的。

死锁解除

目标是以最小的代价恢复系统的运行，实质是让释放资源的进程能够继续运行。方法有

撤销进程 按某种算法撤销进程，直到死锁状态打破。
剥夺资源 挂起一些进程，剥夺他们的资源以解除死锁。等到条件满足时再**他们。

CPU 调度

CPU 调度的任务时从就绪队列中选择一个进程，并把 CPU 的控制权交给被选中的进程。

调度时机

新进程被创建
一个进程运行完毕
一个进程由于某个原因被阻塞
I/O 中断产生（I/O 操作完成）
时钟中断产生

切换过程

保存进程上下文，包括寄存器等
更新当前进程 PCB
把进程移至合适的队列
选择另一个要执行的进程
更新新进程 PCB
装载新进程并执行

调度算法

性能准则

吞吐量

单位时间内所完成的作业数
$\frac{作业数}{总执行时间}$

周转时间

作业从提交到完成所经历的时间
$作业完成时刻 - 作业提交时刻$

带权周转时间

$\frac{周转时间}{服务（执行）时间}$

平均周转时间

对于 n 个进程
$\frac{\sum\limits_{i=0}^n 进程\ i\ 周转时间}{n}$

平均带权周转时间

对于 n 个进程
$\frac{\sum\limits_{i=0}^n 进程\ i\ 带权周转时间}{n}$

响应时间

用户输入一个请求到系统给出首次相应的时间
$请求时间 - 首次响应时间$

高级调度

又称作业调度或长程调度，只有批处理系统中才存在。高级调度是根据某种算法，把外存上的作业调入内存。时间以分钟或小时为单位。

中级调度

又称平衡负载调度或中程调度。中级调度可以将进程在辅存和主存之间对换，以提高内存利用率和系统吞吐量。

优先级算法

平衡各进程对响应时间的要求，设置优先级队列。

静态优先级 根据进程类型、资源需求、用户要求等确定，直到进程终止都不再改变。
动态优先级 进程运行过程中自动改变优先级，如等待时间延长等。

低级调度

又称微观调度或短程调度，是最基本的调度。时间以毫秒为单位。

非抢占式 一旦处理器分配一个进程，其他进程不能主动切入。
抢占式 就绪队列中一旦有优先级高于当前进程的进程存在，立即切换。

设备管理

硬件组成

总线
控制器 对控制端口、总线或者设备的电子集成部件进行控制。
- 状态寄存器
- 控制寄存器 由主机填写内容，以执行命令或改变设备模式。
- 数据寄存器 由主机读写，获得或发送数据。
处理机 操纵控制器，使设备完成 I/O 传输。

通信方式

内存映像编址

控制器的内存/寄存器作为内存空间的一部分。

优点可以将 I/O 请求视为普通的内存访问。
缺点不允许对控制寄存器的内容进行高速缓存。

I/O 独立编址

Intel 体系中，单独为 I/O 端口分配了 64K 地址空间，需要通过特殊的 in out 指令进行读写。

优点外设不占用内存的地址空间；易于区分内存操作与 I/O 操作。
缺点外设操作的指令类型少，操作不灵活。

控制技术

轮询 PIO

由 CPU 代表进程向 I/O 模块发出指令，然后进入忙等状态，直到操作完成。

中断驱动

I/O 操作完成后，由设备控制器通知设备驱动程序。

直接存储访问方式 DMA

由专门的控制器完成数据在设备和内存间的传输。

通道技术 Channel

通道是 DMA 的进一步简化，操作系统只需要向通道指明操作类型、对象等必要信息，就可以转而进行其他运算。I/O 操作完成后，通道会以中断形式通知 CPU。

软件设计

将 I/O 软件组织成多个层次

用户进程层 执行输入输出系统调用。
服务进程层 实现设备命名、保护等。
设备驱动程序 设置设备寄存器并检查设备的执行状态。
中断处理程序 I/O 完成时唤醒设备驱动程序，进行中断处理。
硬件层 实现物理操作。

设备独立性

引入逻辑设备和物理设备两个概念。实现设备独立性

设备分配更灵活
易于实现 I/O 重定向

逻辑设备表 LUT

系统需要具有将逻辑设备名称转换为物理设备名称的功能，因而设置 LUT。每个表想包含

逻辑设备名
物理设备名
驱动程序入口地址

内核 I/O 子系统

缓冲技术

使用缓冲技术可以提高外设利用率，因为

匹配 CPU 与外设的速度
减少 CPU 的中断次数
提高 CPU 与 I/O 设备间的并行性

单缓冲

每当用户进程发出一个 I/O 请求，内核便在主存中分配一个缓冲区。

系统对一块数据的处理时间为

$max(C, T) + M$

双缓冲

当 CPU 和外设的速度相近时，二者都可以连续处理而无需等待对方。处理一块数据的时间可以粗略认为是

$max(C, T)$

环形缓冲

如果 CPU 和外设的处理速度差较大，双缓冲效果不理想，可以使用多缓冲。将多缓冲组织成循环缓冲的形式就是环形缓冲。

缓冲池

上述缓冲区仅用于特定进程，属于专用缓冲。系统较大时，许多这样的循环缓冲会消耗大量的内存空间。缓冲池将这些缓冲区统一管理，进程间共享。

为了管理方便，将相同类型的缓冲区链接成一个队列，形成

空缓冲 emq
输入队列 inq
输出队列 outq

缓冲池可以收容或提取程序或用户的输入输出。

Spooling 技术

Spooling 技术也被称为假脱机技术，用于将独享设备编程具有共享特征的虚拟设备，从而提高设备利用率。这一技术依赖于 Spooling 系统对 I/O 的封装

当外设中有数据时，Spooling 程序将其读取并加以缓冲，以便应用程序读取。
当应用程序有输出请求时，Spooling 程序接收之并加以缓冲，在适当的时候输出到外设。

这样，应用程序进行的 I/O 操作实际是和 Spooling 程序的数据交换，因此也可以称为虚拟 I/O。

磁盘管理

磁盘工作原理

磁盘访问时间

磁盘的总访问时间

$T_a = T_s + T_r + T_t$

寻道时间

磁头从当前位置移动到指定磁道上所经历的时间

$T_s = m \times n + s$
其中， $m$ 为常数， $n$ 为磁头移动的磁道数目， $s$ 为启动磁盘的时间。

旋转延迟时间

对应扇区转到磁头处所需的时间
$T_r = \frac{1}{2r}$
其中， $r$ 为旋转速度。

以硬盘为例，设旋转速度 $r = 3600 r/min$ ，则每转需时 $16.7ms$ ，平均旋转延迟时间 $T_r = 8.3ms$ 。

传输时间

磁盘读写数据所需要的时间
$T_t = \frac{b}{rN}$
其中， $b$ 为读写的字节数， $N$ 为磁道上的字节数。

典型的 $N$ 值为一个扇区，也就是 $512B$ 。

空间管理

位图用一串二进制位对应磁盘块的分配情况。
空闲表法 将所有空闲块记录在一个空闲表中。表中记录一片连续未分配磁盘空间的起始块号和盘块数。
空闲链表法 将所有空闲块串联成一个链表。

成组链接法

这个方法比较复杂，需要加深理解。

成组 100 个空闲盘块分为一组，连续存储。
链接每组中含有一个指向下一组的指针。

整体的数据结构可以看作一个链表，链表的每个元素是一个包含 100 个空闲盘块指针的组。链表的第一个元素存储在内存中，称为空闲盘块号栈；其余元素存储在磁盘中，等待被调入内存，成为空闲盘块号栈。空闲盘块号栈的数据接口可以理解如下

struct stack {
    int nfree;
    int s_free[100];
}

其中，nfree记录了s_free中有效元素的个数，初始值为 100 。由于栈结构的特性，数组总是保证从高位分配数据，因此nfree同时可以作为栈顶的指针使用。s_free[0]是一个特殊的指针，它指向的磁盘块并不是空闲盘块，而是下一个空闲盘块组。如果s_free[0]的值是 0，说明本组已经是链表的最后一组了。

此外，由于栈是临界资源，每次只允许一个进程访问。因此系统为栈设置了一把锁。

空闲盘块的分配

首先检查空闲盘块号栈是否上锁。
将栈顶指针上移，得到与之对应的磁盘块号。如果栈顶指针非零，将磁盘块分配给用户。
若栈顶指针归零，说明本组空闲磁盘块已经全部被分配。如果盘块号非零，需要将刚刚分配的磁盘块读入空闲盘块号栈，并将这一磁盘块分配给用户。
否则，没有更多磁盘块可以用来分配，分配失败。

空闲盘块的回收

首先检查空闲盘块号栈是否上锁。
如果栈大小未达到 100，将磁盘块压栈，栈顶指针下移。
否则表明栈已满，将空闲盘块号栈存入新回收的磁盘块中，记录盘块号，刷新栈大小。

独立硬盘冗余阵列 RAID

把多个相对偏移的硬盘组合成一个硬盘阵列，提升性能。RAIN 被分为不同等级

RAID 0

条带化存储 有 N 个磁盘的 RAID0 在多个磁盘上并行读写，数据传输率是单个磁盘的 N 倍。但它没有数据冗余，不算是真正的 RAID 结构。

RAID 1

镜像存储 在承兑的独立磁盘上产生互为备份的数据。当原始数据繁忙时，直接从镜像拷贝中读取，以提高读取性能和安全性。

RAID 2

海明码校验条带存储 将数据条块化，存储在不同硬盘上，额外存储海明码来进行错误检查和恢复。需要多个磁盘存放检查及恢复信息。

RAID 3-6

奇偶校验条带存储 使用 XOR 校验完成冗余。

文件系统

为了长期存储大量的可共享的数据，人们提出文件这一概念。文件是数据的存储和访问单元。

文件

一切皆文件

文件的本质是一组字节序列。而 I/O 设备也可以看作字节序列的载体，因此所有的 I/O 设备也可以抽象为文件进行操作。

组织形式

逻辑结构

文件的逻辑结构是用户看到的文件的组织形式，与存储介质无关。

流式文件（无结构文件）

流式文件是最简单的文件形式。它以字节为单位存储，适用于对基本信息单位操作不多的文件，如目标代码文件等。

记录式文件（有结构文件）

用户把文件内的信息按逻辑上独立的含义划分为信息单位，每个单位称为一个逻辑记录，简称记录。记录由以下部分组成

逻辑地址 该记录在文件中的相对位置。
记录名
键记录的唯一标识符。
属性 / 属性值

物理结构

文件在外存上的存储组织形式。

顺序结构（连续文件）

连续文件是最早使用的一种文件结构。它使用物理上的顺序存储来实现文件的逻辑次序。如果两个记录在逻辑上连续，那么他们在物理上也是连续的。

优点结构简单；连续存取时速度较快。
缺点不利用文件的动态增加和修改。

因此连续文件结构多用于磁带设备或变化不大的顺序访问的文件。

随机结构（索引文件）

系统为每个文件建立一个索引表，并将物理块号记录在表中。

链表结构（串联文件）

在每个磁盘块后附加一个指针指向下一个磁盘块。

优点空间利用率高；易于顺序存取和修改。
缺点随机存取效率较低；指针需要占用额外存储空间。