操作系统是计算机系统中最重要的系统软件，为了能正确地进行管理和控制，其本身是不能被破坏的。为此，系统应能建立一个保护环境。当用户程序执行时，应有所限制，其所需资源必须向操作系统提出请求，自己不能随意取用系统资源，如不能直接启动外部设备的工作，更不能改变机器状态等。因此系统必须区分处理机的工作状态，即区分当时正在执行的程序的类别。

中断与俘获的概念、类型

IRQ (Interrupt ReQuest)：外部中断请求（时钟中断、I/O 完成中断）
SystemCall：系统调用，访管中断
Exception：异常（单条指令中，回到异常指令继续执行 i.e. 除 0 异常、缺页异常）

🌟 中断响应的定义及实质

定义

中断响应是当中央处理机发现已有中断请求时，中止现行程序执行，并自动引出中断处理程序的过程。

实质

中断响应的实质是交换用户程序和处理该中断处理程序的指令执行地址和处理器状态（受保护的状态转移）。

🌟 软件中断处理过程

当硬件完成中断响应后，由相应的中断处理程序得到控制权，进入软件的中断处理。过程主要包括：

保护现场和传递参数
执行相应的中断服务例程
恢复和退出中断

向量中断

向量中断是一种识别中断源的技术或方式。识别中断源的目的即找到中断向量（中断处理程序地址）。

操作系统的用户接口

处理应用程序的步骤

编辑
编译（CSAPP 中预处理、编译、汇编、链接）
连接
运行

连接的类型

静态链接是指在编译阶段直接把静态库加入到可执行文件中去。可执行文件大但不依赖外部库。

动态链接则是指链接阶段仅仅只加入一些描述信息，而程序执行时再从系统中把相应动态库加载到内存中去。可执行文件小但依赖外部库。

操作系统提供的接口

命令接口：用户使用命令接口来组织工作流程和控制程序的运行。<i.e. shell 命令>
程序接口：用户程序在其运行过程中，使用系统功能调用来请求操作系统的服务。<i.e. read, write>

🌟 系统调用的定义及实现过程

定义

系统功能调用是用户在程序一级请求操作系统服务的一种手段，它是带有一定功能号的 ”访管指令“。其功能是由操作系统中的程序完成的，即由软件方法实现的。

与普通库函数调用区别

系统调用有访管中断

进程及进程管理

程序的顺序执行（定义、特点）

计算

程序的一次执行过程称为一个计算，它由许多简单操作所组成。

定义

一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。

特点

顺序性
封闭性
可再现性

程序的并发执行

定义

若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的。

特点

失去程序的封闭性和可再现性
程序与计算不再一一对应
程序并发执行的相互制约
- 间接——资源共享
- 直接——公共变量

与时间有关的错误

程序并发执行时，若共享了公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，这就是与时间有关的错误。

进程

定义

所谓进程，就是一个程序在给定的活动空间和初始环境下，在一个处理机上的执行过程。

进程与程序的区别

程序是静态的，进程是动态的
进程是一个独立运行的活动单位
进程是竞争系统资源的基本单位
一个程序可以对应多个进程，一个进程至少包含一个程序

🌟 进程状态

进程的组成、进程控制块定义及其作用

组成

程序与数据
进程控制块（Process Control Block，PCB）

进程控制块

描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构，称为进程控制块。

基本进程控制原语

创建原语
撤销原语
等待原语
唤醒原语

🌟 临界资源、临界区、互斥、进程同步的定义

临界资源

一次仅允许一个进程使用的资源称为临界资源。

临界区

临界区是进程中对公共变量进行审查与修改的程序段，称为相对该公共变量的临界区。

互斥

在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或修改存储区的内容，否则就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。

进程同步

并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步

🌟 信号灯的定义，P、V 操作原语的功能

信号灯

信号灯是一个确定的二元组 (s, q)，s 是一个具有非负初值的整型变量，q 是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。

P 操作

对信号灯 s 的 P 操作记为 P(s)。【原语操作】取信号灯 s 值减一，若相减结果为负，则调用 P(s) 的进程被阻塞，并插入到该信号灯的等待队列中，否则可以继续执行。

V 操作

对信号灯 s 的 V 操作记为 V(s)。【原语操作】取信号灯 s 值加一，若相加结果小于等于 0 则帮助唤醒等待队列上的一个进程，进程然后继续执行。

🌟 用信号灯的 P、V 操作实现进程互斥

sem_t mutex = 1;

process() {
	P(mutex);
	// 临界区
	V(mutex);
}

🌟 生产者—消费者问题

int main() {
	sem_t empty = 1; // 空信号灯
	sem_t full = 0;  // 满信号灯
	sem_t mutex = 1; // 缓冲区互斥量
	cobegin
		producer();
		consumer();
	coend
}

producer() {
	while (true) {
			// 生产产品
			P(empty);
			P(mutex);
			// 将产品放入缓冲区
			V(mutex);
			V(full);
	}
}

consumer() {
	while (true) {
		P(full);
    P(mutex);
    // 在缓冲区中取出
    V(mutex);
    V(empty);
    // 消费产品
	}
}

线程的概念

线程是比进程更小的活动单位，它是进程中的一个执行路径。

资源分配与调度

死锁的定义及举例

引起死锁的原因

系统资源不足
进程推进顺序非法

🌟 产生死锁的必要条件

互斥
占有且申请
不剥夺
环路

🌟 死锁的预防、避免与检测

死锁的预防

一次性分配所有资源（静态）

死锁的避免

有序资源分配法
银行家算法

处理机调度

处理机的多级调度

宏观上：作业调度
对存放在辅存设备上的大量作业，以一定的策略进行挑选分配主存等必要的资源，建立作业对应的进程，使其投入运行。
微观上：进程调度
对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。

作业调度（评估 + 算法）

评估指标——周转时间

周转时间 = 完成时间 - 到来时间

评估指标——带权周转时间

带权周转时间 = 周转时间 / 作业时间

先来先服务 FCFS

按照作业到来的先后次序进行调度。

短作业优先调度

每次总选择一个请求运行时间最小的作业调入内存。

响应比高者优先调度算法

响应比 = 相应时间 / 执行时间 = 1 + 等待时间 / 执行时间

优先数调度算法

综合考虑各方面因素设置优先数，选择优先数最大的作业调入

进程调度

进程调度方式

非剥夺方式：实现简单
剥夺方式：响应紧急任务

常用的进程调度算法

优先数调度算法：某种规则赋予进程优先数，处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最法的进程占用 CPU
循环轮转调度算法：系统的响应时间分成若干时间片。每个进程被调度后，占用一个时间片，时间片用完后，该进程让出 CPU，排在就绪队列的队尾。多个进程循环轮转。
多级反馈算法：多个简单算法的综合和发展

调度用的进程状态变迁图

调度效果：

优先照顾了 I/O 量大的进程
适当照顾了计算量大的进程

主存管理

逻辑地址、程序地址空间、物理地址、主存（物理地址）空间

物理地址：物理地址是计算机主存单元的真实地址，又称为绝对地址或实地址
主存空间：物理地址的集合所对应的空间组成了主存空间
逻辑地址：用户的程序地址均为逻辑地址
程序地址空间：用户程序所有的逻辑地址集合对应的空间

🌟 地址映射的概念及类型

概念

将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射。

类别

编程或编译时确定地址映射关系
在程序装入时确定地址映射关系【静态地址重定位】
- 程序装入时
- 软件重定位
- 花费较多 CPU 时间
- 不灵活
在程序运行时确定地址映射关系【动态地址重定位】
- 程序执行时
- 需硬件地址变换机构
- 地址变换快
- 灵活

界地址保护方法

上、下界保护
基址、限长保护

动态分区存储管理的思想

在处理程序的过程中，建立分区，依照用户请求的大小分配分区。

🌟 适应算法与空闲区队列结构

判断对请求序列用算法合适不合适时，“合适” “不合适” 是术语

首次适应算法

放置策略：放置到主存里第一个足够装入它的地址最低的空闲区
队列结构：空闲区地址由低到高排序
特点：尽可能利用存储器中低地址的空闲区

最佳适应算法

放置策略：将输入的程序放置到主存中与它所需大小最接近的空闲区
队列结构：空闲区大小由小到大排序
特点：尽可能地利用存储器中小的空闲区

最坏适应算法

放置策略：将输入程序放置到主存中与它所需大小差距最大的空闲区中
队列结构：空闲区大小由大到小排序
特点：尽可能利用存储器中大的空闲区

动态分区管理的碎片问题

什么是碎片问题

在已分配区之间存在着一些没有被充分利用的空闲区。

解决：拼接技术

所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。

🌟 页面、内存块、页表的概念

页面

程序的地址空间被等分成大小相等的片，称为页面（虚页）

主存块

主存被等分成大小相等的片，称为主存块，又称为实页

页表

为了实现程序地址空间到物理主存的映像，系统建立的记录页与内存块之间对应的地址变换机构称为页面映像表，简称页表。

组成：

TLB（Transfer Look-aside Buffer）快表，旁路地址转换器
主存区域慢表

🌟 页式地址变换过程

🌟 置换算法

最佳算法（OPT）

当要调入新页而必须先淘汰一旧业时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。

先进先出淘汰算法（FIFO）

总是选择在主存中居留时间最长的一页进行淘汰。

最久未使用淘汰算法（LRU）

总是选择最长时间未被使用的那一页进行淘汰。

实现：

硬件方法：计数器
软件方法：页号栈

LRU 近似算法

🌟 段页式系统及其地址结构

I/O 管理

🌟 设备独立性

定义

所谓设备独立性，是指用户在程序中使用的设备与实际使用的设备无关，也就是在用户程序中仅使用逻辑设备名。

逻辑设备名

逻辑设备名是用户自己指定的设备号，它是暂时的、可更改的。

物理设备名

物理设备名，是系统提供的设备的标准名称，它是永久的、不可更改的。

优点

方便用户
改善设备利用率
提高系统的可扩展性和可适应性

设备控制块

系统为每一台设备都配置了一个用来记录设备的硬件特性、连接和使用情况的一组数据，称为设备控制块。

I/O 控制功能

设备驱动

缓冲技术

定义

缓冲是两种不同速度的设备之间传输信息时平滑传输过程的常用手段。

类别

缓冲器：是用来暂时存放数据的一种存储装置，容量小，速度快
软件缓冲：在 I/O 操作期间用来存放 I/O 数据的一块存储区域

常用的缓冲技术

双缓冲
环形缓冲（环形队列）
缓冲池

UNIX 缓冲技术

目的

加快系统响应、增加系统吞吐量
减少对磁盘的 I/O 操作次数

思路

预先缓存
延迟发送

数据结构

缓存数组——含有磁盘上数据的存储器数组
缓存首部——描述缓冲区特性的数据结构

🌟 虚拟分配

虚拟技术

所谓虚拟技术，是在一类物理设备上模拟另一类物理设备的技术，是将独占设备转化为共享设备的技术。

虚拟设备

通常把用来代替独占型设备的那部分外存空间（包括有关的控制表格）称为虚拟设备。

虚拟分配

当进程需要与独占型设备交换信息时，系统将分配磁盘空间，并建立相应的数据结构，这种分配方法称为设备的虚拟分配。

🌟 SPOOLING 系统

设计思想

预输入：应用需要数据前，OS 已将所需数据预先输入到辅存输入井中存放。当应用程序需要数据时，可直接从辅存中读入主存。
缓输出：在应用程序执行时，将输出数据写入辅存输出井中。当应用程序执行完毕（或需要数据时），由操作系统将数据输出

什么是 SPOOLING 系统

利用通道和中断技术，在主机的控制下，由通道完成输入输出工作。系统提供一个软件系统（包括预输入程序、缓输出程序、井管理程序、预输入表、缓输出表）。它提供输入收存和输出发送的功能，使外部设备可以并行操作。这一软件系统称为 SPOOLING 系统。

SPOOLING 系统的优点

提供虚拟设备
外围设备同时联机操作
加快作业处理速度

实现 SPOOLING 系统的基础

输入输出井——大容量的辅存空间
通道、中断——硬件基础
预输入表、缓输出表——数据结构

文件是具有符号名的信息项的集合
文件是具有符号名的记录的集合

管理文件所需的数据结构（目录表、文件控制块、存储分配表）
管理程序
一组操作

功能

从用户角度——按名存取
从系统角度——
- 辅存空间管理（文件块、空闲块、分配算法）
- 文件集合管理（构造文件结构、文件存取、文件共享和访问）
- 文件保护（数据可靠和安全）

特点

使用简单
安全可靠
既能共享，又能保密

选择工作性能良好、设备利用率高的物理文件形式
系统按照文件的物理结构形式和外部设备打交道，控制信息的传输

🌟 连续文件、串联文件、FAT 文件、索引文件的定义、结构图以及特点

连续文件

定义：连续文件结构是由一组分配在磁盘连续区域的物理块组成的
结构图：
![image-20220106000656565](/Users/mac/Library/Application Support/typora-user-images/image-20220106000656565.png)
特点：
- 结构简单，实现容易，连续存取时速度较快
- 创建文件时要给出文件大小，文件长度一经固定变不易改变，动态增加和修改不易
- 存储空间利用率不高（碎片）