第一部分：中断机制
1、中断的概念
所谓中断是指处理器对系统中或系统外发生的异步事件的响应。
中断是所有要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。
一个计算机系统提供的中断源的有序集合一般被称为中断字，
Intel 的 x86 微处理器能处理 256 种不同的中断。
2、中断机制：
（1）能充分发挥处理器的使用效率。
（2）提高系统的实时能力
（2）相似概念：异常
3、中断和异常的区别
中断是由外部事件引发的，而异常则是由正在执行的指令引发的。
4、典型的中断包括：
1）时钟中断
2）输入输出（I/O）中断
3）控制台中断
4）硬件故障
5、典型的异常包括：
1）程序性中断
2）访管指令异常
6、中断系统
概念：
中断系统是现代计算机系统的核心机制之一，它不是单纯的硬件或者软件的概念，而是硬件
和软件相互配合、相互渗透而使得计算机系统得以充分发挥能力的计算模式。
组成：
中断系统的硬件中断装置和软件中断处理程序。
硬件中断装置负责捕获中断源发出的中断请求，并以一定的方式响应中断源，然后将处理器
的控制权移交给特定的中断处理程序。
中断处理程序则针对对中断事件的性质而执行相应的一系列操作。
7、中断请求响应的工作过程是：
①处理器接收中断信号；
②保护现场，将中断断点的程序状态字 PSW 和程序计数器 PC 值存入系统堆栈；
③分析中断向量，取得中断处理程序的入口地址；
④将处理器的 PC 值置为中断处理程序的入口地址；
⑤调用中断处理程序。
8、中断处理的内容
其中包括检查 I/O 相关的状态信息，操纵 I/O 设备或者在设备和内存之间传送数据等。
在中断处理程序结束工作之后，
1）处理器会检测到一条中断返回指令。
2）处理器会把原先被中断的程序的上下文环境从系统堆栈中恢复。
3）处理器状态也从管态恢复成被中断时的目态。
4）整个中断处理结束。
5）处理器开始一个新的指令周期，继续执行原来被中断的程序。
9、中断处理的步骤/过程（接收、响应、处理的过程）
1）接收和响应中断
2）保护中断断点现场
3）分析中断向量
4）调用中断处理程序
5）中断处理结束恢复现场
6）原有程序继续执行。
10、几种典型中断的处理
（1）I/O 中断
I/O 中断通常可分成两大类：I/O 操作正常结束以及 I/O 异常。
（2）时钟中断
①维护软件时钟。
②处理器调度。
③控制系统定时任务。
④实时处理
助记：定时维护，实时调度。
（3）硬件故障中断
硬件故障一般是由硬件的问题引起的，排除此类故障通常需要人工的干预，
例如复位硬件或者更换设备等。
需要做的工作是保存现场，使用一定的手段警告管理员并提供一些辅助的诊断信息。
（4）程序性中断
第一类为程序性中断，只能由操作系统完成。
第二类为程序性中断，可以由程序自己完成。
（5）系统服务请求（自愿性中断）
系统服务请求一般由处理器提供的专用指令（又称访管指令）来激发。
11、多级中断与中断优先级
现代的微处理器都提供有多级中断系统，在多级中断系统中，硬件决定了各个中断的优先级
别。
作用：
1）对各类中断信号依据其紧急程度和重要性划分级别。
2）解决如果有重要程度相当的多个中断信号同时到达时，如何选择首个被处理的中断信号
的问题。
在同一中断级中的多个设备接口中同时都有中断请求时，一般有两种办法可以采用：
1）固定的优先数 2）轮转法
12、中断屏蔽
PWS 中的中断屏蔽位决定，这些屏蔽位标识了被屏蔽的中断类或者中断。
机器故障中断不可屏蔽。比如内存奇偶校验错，以及掉电等使得机器无法继续操作一类的故
障。
一旦发生这类不可屏蔽的中断，不管程序状态字中的屏蔽位是否建立，处理器都要立即响应
这类中断，并进行处理。
13、 中断嵌套
1）禁止其他中断
这种处理方法可以用软件简单地实现
2）中断嵌套
允许优先级较高的中断打断优先级较低的中断处理过程，
第二部分：系统调用
1、系统调用的概念
用户在程序中调用操作系统所提供的一些子功能。这是一种特殊的过程调用，这种调用通常
是由特殊的机器指令实现的，并且将系统转入特权方式（管态）。
系统调用程序被看成是一个低级的过程，只能由汇编语言直接访问。
系统调用是操作系统提供给编程人员的唯一接口。
编程人员利用系统调用，动态请求和释放系统资源，调用系统中已有的系统功能来完成与计
算机硬件部分相关的工作以及控制程序的执行速度等。
2、系统调用与函数调用的区别
（1）运行在不同的系统状态
（2）状态的转换
（3）返回问题
（4）嵌套调用
3、系统调用的分类
通常，一个操作系统的功能分为两大部分：一部分是系统自身所需要的；另一部分功能是作
为服务提供给用户的，有关这部分功能可以从操作系统所提供的系统调用上体现出来。
（1）进程控制类系统调用
（2）文件操作类系统调用
（3）进程通信类系统调用
（4）设备管理类系统调用
（5）信息维护类系统调用
4、用户程序和系统程序之间的参数传递几种常用的实现方法。
（1）由陷入指令自带参数。
（2）通过有关通用寄存器来传递参数。
（3）在内存中开辟专用堆栈区来传递参数。
UNIX 类操作系统通常采用通用寄存器传递参数。
第三部分：进程和线程
1、程序的顺序执行的特点
1）顺序性
2）封闭性
3）程序执行结果的确定性
4）程序执行结果的可再现性
2、程序的并发执行
所谓程序并发执行，是指两个或两个以上程序在计算机系统中，同时处于已开始执行且尚未
结束的状态。
（同一时刻 OR 同一时间段）
3、程序的并发执行的特征
1）在执行期间并发程序相互制约
2）程序与计算不再一一对应
一 切 顺
序 程 序
所 应 具
有 的 特
性
一切顺序程序所应具有的特性
3）并发程序的执行结果不可再现
4）程序的并行执行与程序的并发执行
4、多道程序设计环境的特点
1）独立性
2）随机性
3）资源共享性
5、多道程序设计的缺陷
1）可能延长程序的执行时间
2）系统的效率的提高程度是有限的
6、 进程的定义
进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和
调度的一个独立单位。（运行的程序）
从操作系统角度来看，可将进程分为系统进程和用户进程两类。
系统进程执行操作系统程序，完成操作系统的某些功能。
用户进程运行用户程序，直接为用户服务。
系统进程的优先级通常高于一般用户进程的优先级。
7、进程与程序的联系和区别
进程和程序既有联系又有区别。
（1）进程和程序的联系
程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序，如果没有程
序，进程就失去了其存在的意义。从静态的角度看，进程是由程序、数据和进程控制块（PCB）
三部分组成的。（进程=程序+数据+进程控制块（PCB））
（2）进程和程序的区别
程序是静态的，而进程是动态的。
进程是程序的一个执行过程。程序的存在是永久的（这里不讨论人为删除程序等行为）。而
进程是为了程序的一次执行而暂时存在的。进程有生命周期，有诞生，亦有消亡。
8、三状态进程模型
（1）运行状态（Running）
（2）就绪状态（Ready）
（3）等待状态（Waiting）
也称阻塞状态或封锁状态。
1）就绪—运行
2）运行—就绪
3）运行—等待
4）等待—就绪
9、五状态进程模型
1）运行状态（Running）
2）就绪状态（Ready）
3）阻塞状态（Blocked）
4）创建状态（New）
5）结束状态（Exit）
五状态进程模型中的主要状态转换：
1）创建新进程
2）提交（Admit）
3）调度运行（Dispatch）
4）释放（Release）
5）超时（Timeout）或被抢占
6）事件等待（Event Wait）
7）事件出现（Event Occurs）
10、七状态进程模型（重点）
1）就绪状态（Ready）：进程在内存且可立即进入运行状态。
2）阻塞状态（Blocked）：进程在内存并等待某事件的出现。
3）阻塞挂起状态（Blocked，Suspend）：进程在外存并等待某事件的出现。
4）就绪挂起状态（Ready，Suspend）：进程在外存，但只要进入内存，即可运行。
在七状态进程模型中，新引入的状态转换有挂起和激活两类，意义有变化的转换有事件
1）挂起（Suspend）：把一个进程从内存转到外存；
可能有以下几种情况。
1、阻塞到阻塞挂起
2、就绪到就绪挂起
3、运行到就绪挂起
2）激活（Activate）：把一个进程从外存转到内存；
可能有以下几种情况。
1、就绪挂起到就绪
2、阻塞挂起到阻塞
3）事件出现（Event Occurs）：进程等待的事件出现；如操作完成、申请成功等；
可能的情况如下。
1、阻塞到就绪：针对内存进程的事件出现。
2、阻塞挂起到就绪挂起：针对外存进程的事件出现。
4）提交（Admit）：完成一个新进程的创建过程，新进程进入就绪状态或就绪挂起状态。进
入就绪挂起的原因是系统希望保持一个大的就绪进程表（挂起和非挂起）。
七状态进程模型
好处：
1）提高处理器效率：就绪进程表为空时，有空闲内存空间用于提交新进程，可提高处理器
效率。
2）可为运行进程提供足够内存：资源紧张时，可把某些进程对换至外存。
3）有利于调试：在调试时，挂起被调试进程，可方便对其地址空间进行读写。
11、进程控制块
为了便于系统控制和描述进程的活动过程，在操作系统核心中定义了一个专门的数据结构，
称为进程控制块（Process Control Block，PCB）。
- PCB 的内容
进程控制块的内容可以分成调度信息和现场信息两大部分。
调度信息（进程名、进程号、地址空间信息、优先级、当前状态、资源清单、“家族”关系、
消息队列指针、进程队列指针和当前打开文件）等。 - 进程的组成
进程由程序、数据和进程控制块三部分组成。
PCB 是进程的“灵魂”;
程序和数据是进程的“躯体” - PCB 组织
（1）线性方式
（2）索引方式
（3）链接方式 - 进程的队列
（1）就绪队列
（2）等待队列
（3）运行队列 - 进程队列的组成
进程队列可以用进程控制块的链接来形成。
常用链接的方式有两种：单向链接和双向链接。
位置分类：
（1）队首进程出队
（2）非队首（或队尾）进程出队
（3）队尾进程出队
进程入队时，根据应插入的位置也可分成三种：
1）从队首入队成为新的队首进程；
2）从队尾入队成为新的队尾进程；
3）插入到队列中某两个进程之间。
12、进程控制
1、原语
所谓原语，是由若干条指令所组成的一个指令序列，用来实现某个特定的操作功能。
原语是操作系统核心（由一组程序模块所组成的、完成操作系统中基本功能）的一个组成部
分。原语必须在管态下执行，并且常驻内存。
原语和系统调用都可以被进程所调用，两者的差别在于原语有不可中断性，它是通过在其执
行过程中关闭中断实现的，而且原语往往是被系统进程所调用。 - 进程控制原语（重点）
用于进程控制的原语一般有：创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒
进程以及改变进程优先级等。
（1）创建原语
过程：先申请一空闲 PCB 区域，然后将有关信息填入 PCB，置该进程为就绪状态，最后把它
插入就绪队列中。
（2）撤销原语
过程：找到要被撤销进程的 PCB，将它从所在队列中消去，撤销属于该进程的一切“子孙进
程”，释放被撤销进程所占用的全部资源，并消去被撤销进程的 PCB。
（3）阻塞原语
过程：由于进程正处于运行状态，因此首先应中断处理器的执行，把处理器的当前状态保存
在 PCB 的现场信息中，然后把进程的当前状态置为等待状态，并把它插入到该事件的等待队
列中去。
（4）唤醒原语
过程：在等待队列中找到该进程，将进程的当前状态置为就绪状态，然后将它从等待队列中
撤出并插入到就绪队列中排队，等待调度执行。
14、 线程的属性
1）—个线程在被创建后便开始了它的生命周期，直至终止；
2）每个线程有一个唯一的标识符和一张线程描述表，线程描述表记录了线程执行的寄存器
以及栈等现场状态。
3）不同的线程可以执行相同的程序，即同一个服务程序被不同用户调用时操作系统为它们
创建不同的线程。
4）同一个进程中的各个线程共享该进程的内存地址空间。
5）线程是处理器的独立调度单位，多个线程是可以并发执行的。在单处理器的计算机系统
中，各线程可交替地占用处理器；
15、引入线程的好处
1）创建一个新线程花费时间少（结束亦如此）。创建线程不需另行分配资源，因而创建线
程的速度比创建进程的速度快，且系统的开销也少。
2）线程之间的切换花费时间少。
3）由于同一个进程内的线程共享内存和文件，所以线程之间相互通信无须调用内核，故不
需要额外的通信机制，使通信更简便，信息传送速度也快。
4）线程能独立执行，能充分利用和发挥处理器与外部设备并行工作能力。
5、线程具有许多传统进程所具有的特征，故又称为轻量级进程（Light-Weight Process）
或进程元；
把传统的进程称为重量级进程（Heavy-Weight Process），它相当于只有一个线程的任务。
在引入了线程的操作系统中，通常一个进程都有若干个线程，至少也需要有一个线程。
16、线程实现机制 - 用户级线程
第一种实现方式是用户级线程（User-Level Threads），这种线程不依赖于内核。
用户级线程只存在于用户态中，对它的创建、撤销和切换不会通过系统调用来实现，因而这
种线程与内核无关。相应地，内核也并不知道有用户级线程的存在，从内核角度考虑，就是
按正常的方式管理，即单线程进程。
优点：用户级线程包可以在不支持线程的操作系统上实现。（函数库实现线程） - 内核级线程
第二种实现方式是内核级线程（Kernel-Supported Threads），这种线程依赖于内核。
内核级线程依赖于内核，即无论是在用户进程中的线程，还是系统进程中的线程，它们的创
建、撤销和切换都由内核实现。
在内核中保留了一个线程控制块，系统根据该控制块而感知该线程的存在并对线程进行控
制。
用户级线程和内核级线程
（1）线程的调度与切换速度
核心级线程的调度和切换与进程的调度和切换十分相似。
用户级线程的切换通常是发生在一个应用进程的诸线程之间，
（2）系统调用
用户进程调用系统调用，用户状态—>核心状态，用户进程封锁，返回系统调用时唤醒
（用户线程相同）
内核级线程：调度以线程为单位，只封锁该线程，调度其他线程执行
（宏观上看，进程是调度的状态）
（3）线程执行时间
用户级线程的系统，调度是以进程为单位进行的。
核心级线程，其调度是以线程为单位进行的， - 混合实现方式
有一些系统同时实现了用户级线程和内核级线程。
17、进程调度即处理器调度。
进程调度的任务是控制、协调进程对处理器的竞争，按照一定的调度算法，使某一就绪进程
获得 CPU 的控制权，转换成运行状态。 - 进程调度的主要功能
1）记录系统中所有进程的执行状况；
2）根据一定的调度算法，从就绪队列中选出一个进程，准备把处理器分配给它；
3）把处理器分配给进程。 - 进程调度的时机
1）正在执行的进程运行完毕。
2）正在执行的进程由于某种错误而终止。
3）时间片用完，即有一个进程从运行状态变为就绪状态。
4）正在执行的进程调用阻塞原语将自己阻塞起来，即一个进程从运行状态进入阻塞状态。
5）创建了新的进程，即有一个新的进程进入就绪队列。
6）正在执行的进程调用了唤醒原语操作激活了等待资源的进程，
即一个等待状态的进程变为就绪状态。
5 和 6 是抢占式的
18、调度算法设计原则 - 进程行为
几乎所有进程的（磁盘）I/O 请求或计算都是交替突发的计算密集型（Compute-bound），
典型的计算密集型进程具有较长时间的处理器集中使用和较小频度的 I/O 等待。
I/O 密集型（I/0-boimd），I/O 密集型进程是 I/O 类的，因为这种进程在 I/O 请求之间较少
进行计算，并不是因为它们有特别长的 I/〇请求。 - 系统分类
批处理、交互式和实时系统。
1）批处理系统在商业领域仍在广泛应用，用来处理薪水册、存货清单、账目收人、账目支
出、利息计算（在银行）、索赔处理（在保险公司）和其他的周期性的进程。
（非抢占式、抢占式都可以接受）
2）交互式用户环境中，抢占是必须的。
3）实时系统中，非抢占式
实时系统与交互式系统的差别：
实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的
非协作甚至是有恶意的程序。 - 调度算法的设计目标
1）设计调度算法的目标取决于环境，
2）另一个共同的目标是保持系统的所有部分尽可能忙碌。
1）批处理进程：吞吐量、周转时间以及处理器利用率
2）交互式系统，特别是分时系统和服务器，最重要的是最小响应时间
3）实时系统：必须满足截止时间
19、 进程调度算法（重点 ） - 先来先服务算法
在所有调度算法中，最简单的是非抢占式的先来先服务（First-Come First-Served，FCFS）
算法。
（单链表的方式
主要优点：
易于理解并且便于在程序中运用。
缺点：
等待很长时间，不利于用户的交互体验。 - 最短进程优先算法
现在来看一种适用于运行时可以预知的另一个非抢占式的批处理调度算法——最短进程优
先（Shortest Job First，SJF）算法。 - 最短剩余时间优先算法
最短进程优先算法的抢占式版本是最短剩余时间优先（Shortest Remaining Time Next，
SRTN）算法。 - 最高响应比优先算法
最高响应比优先算法（Highest Response Rate First，HRRF）的性能是介于先来先服务和
最短进程优先算法之间的折中的算法，
响应比的计算式为：
响应比 Rp=（等待时间+预计运行时间）/预计运行时间=周转时间/预计运行时间
这种算法较好地适应了长短进程混合的系统，使得调度的性能指标趋于合理。 - 轮转算法（1904 真题 32）
轮转（Round-Robin，RR）算法最早来自分时系统。
【注意】在轮转算法中，时间片 Q 长度的选取非常重要，将直接影响系统开销和响应时间。
如果时间片长度很小，则调度程序剥夺处理器的次数频繁，加重系统开销；
反之，如果时间片长度选择过长，算法就退化成先来先服务
下面是影响时间片值设置的几个主要因素。
1）系统响应时间
2）就绪进程的数目
3）计算机的处理能力 - 最高优先级算法
最高优先级（Highest Priority First，HPF）进程调度算法每次将处理器分配给具有最高
优先级的就绪进程。
进程的优先级由进程优先数决定。
进程优先数的设置可以是静态的，也可以是动态的。
最高优先级算法还可以和不同的处理器调度方式结合起来，从而形成可抢占式最高优先级算
法和不可抢占式最高优先级算法。 - 多级反馈队列算法
多级队列反馈法就是综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法
的一种进程调度算法。
多级反馈队列法的基本思想有如下几个基本要点。
1）被调度队列的设置。
2）在同一个队列之内的调度原则。
3）在不同队列之间的调度原则。
4）进程优先级的调整原则。
10、系统内核
为了提高系统的运行效率、保护系统的关键部分不被破坏，一般把操作系统中提供支持系统
运行的各种基本操作和基础功能的一组程序模块集中安排，形成一个操作系统的核心，称为
系统核心或系统内核，简称内核（Kernel）。
通常，内核只占整个操作系统代码中的一小部分，内核是操作系统中最接近裸机的部分。
系统内核本身并不是进程，是系统进程和用户进程赖以活动的基础。
系统内核提供下列功能：
1）中断处理程序
2）进程同步与互斥
3）进程调度
4）控制与通信
5）存储管理的基本操作
6）时钟管理等。
对内核的各种功能调用通过执行原语操作来实现。
第四部分：死锁
1、死锁的定义
所谓死锁是指在多道程序系统中的一种现象，一组进程中的每个进程均无限期地等待被该组
进程中的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状
态，简称死锁。
处于死锁状态的进程称为死锁进程。
系统发生死锁时，死锁进程的个数至少为两个；
所有死锁进程都在等待资源，并且其中至少有两个进程已占有资源。
2、产生死锁的原因主要有两个:
1）竞争资源，系统资源在分配时出现失误，进程间对资源的相互争夺而造成僵局；
2）多道程序运行时，进程推进顺序不合理。 - 资源的概念
按照资源的使用性质，分成两类:
1）永久性资源（可重用资源），是指系统中可供进程重复使用、长期存在的资源；
2）临时性资源（消耗性资源），是指由某个进程所产生、只为另一个进程使用一次或经过
短暂时间后便不再使用的资源，
永久性资源和临时性资源都可能导致死锁发生。
申请不同类资源产生死锁。
申请同类资源产生死锁。
P、V 操作使用不当产生死锁
对临时性资源的使用不加限制而引起的死锁
对于永久性资源，产生死有四个必要条件：
1）互斥条件
2）不可剥夺条件，又称不可抢占或不可强占
3）请求和保持条件，又称部分分配或占有申请。
4） 循环等待条件，又称环路等待
只要系统发生死锁，则以上四个条件一定成立。
3、解决死锁的方法：
1）不让死锁发生；（预防）
2）检测死锁是否发生，再加以解决（解决）
1 预防死锁 2 避免死锁 3 检测与解除死锁 4 忽略
4、死锁预防
是指在任何系统操作前（例如分配资源、调度进程等），事先评估系统的可能情况，严格采
取措施使得死锁的四个必要条件不成立。
5、死锁避免
基本思想是:
系统对进程发出的每一个系统能够足的资源中请进行动态检查，并根据检查结果决定是否分
配资源;
如果分配后系統可能发生死锁，则不予分配，否则予以分配。
这是一种保证系统不进入死锁状态的动态策略。
6、死锁避免和死锁预防的区别：
死锁预防是设法至少破坏产生死锁的四个必要条件之一，严格地防止死锁的出现。
死锁避免是在系统运行过程中注意避免死锁的最终发生。
7、银行家算法
为保证资金的安全，银行家规定如下。
1）顾客资金需求<=银行家现有资金——>可接纳该顾客。
2）贷款总数<=最大需求量——>顾客可以分期贷款
3）银行家现有资金<=贷款总数当——>可推迟支付顾客贷款（时间有限）
4）有限的时间里归还所有的资金。
顾客=进程 银行家=操作系统
8、死锁的检测与解除
操作系统在运行过程中，不断地监督进程的执行和资源占用状态，判定死锁是否真的发生；
并且，一旦死锁发生，则采取专门的措施解除死锁，并以最小代价使整个系统恢复正常，这
就是死锁的检测和解除。
9、死锁检测的时机
操作系统可定时运行一个“死锁检测”程序，
检测死锁的实质是确定是否存在“循环等待”条件，检测算法确定死锁的存在并识别出与死
锁有关的进程和资源，以供系统采取适当的解除死锁措施。
方法：
1）死锁检测在资源分配后，在每次调度后，或者利用定时器定时运行检测
2）当系统中某个进程长期位于阻塞态或阻塞进程过多时，启动死锁检测程序。
10、死锁检测的算法。
1）为每个进程和每个资源指定唯一编号。
2）设置一张资源分配状态表（资源号、进程号）资源分配表中记录了每个资源正在被哪个
进程所占有。
3）设置一张进程等待分配表，（进程号、等待资源号）
4）算法规则：当任一进程 Pj 申请一个已被其他进程占用的资源 ri 时，进行死锁检测。
11、 为解除死锁就要剥夺资源，此时，需要考虑以下几个问题。
1）选择一个牺牲进程
2）重新运行或回退到某一点开始继续运行
3）怎样保证不发生“饿死”现象
4）“最小代价”，即最经济合算的算法，使得进程回退带来的开销最小。 - 剥夺资源
使用挂起/激活机制挂起一些进程，剥夺它们占有的资源给死锁进程，以解除死锁，待以后
条件满足时，再激活被挂起的进程。（顺序可以是以花费最小资源数为依据）
经常使用的方法如下。
1）还原算法，即恢复计算结果和状态。
2）建立检查点主要是用来恢复分配前的状态。 - 撤销进程
撤销死锁进程，将它们占有的资源分配给另一些死锁进程，直到死锁解除为止。
以下几点可作为衡量撤销代价的标准。
1）进程优先数，即被撤销进程的优先数。
2）进程类的外部代价。
3）运行代价。
撤销法的优点是简单明了，但有时可能撤销一些甚至不影响死锁的进程。
当死锁的进程中包含有操作系统的进程单元时，死锁会变得复杂，可能会导致系统重新启动，
从而付出较高代价。
12、资源分配图（要会描述资源分配图）
是死锁的一种准确而形象地描述，通过资源分配图，可以对当前系统资源分配和申请情况一
目了然，便于对死锁进行分析并采取对策。
资源分配图是一张有向图，
一个系统资源分配图 SRAG（System Resource Allocation Graph）可定义为一个二元组，
即 SRAG=（V，E），其中 V 是顶点的集合，而 E 是有向边的集合。
顶点集合可分为两种部分：
P=（P1，P2，…，Pn），是由系统内的所有进程组成的集合，每一个 Pi 代表一个进程；
R=（r1，r2，…，rm）是系统内所有资源组成的集合，每一个 ri 代表一类资源。
13、死锁定理。
1）如果资源分配图中没有环路，则系统没有死锁。
2）如果资源分配图中出现了环路，则系统中可能存在死锁。
①如果处于环路中的每个资源类中均只包含一个资源实例，则环路的存在即意味着死锁的存
在。此时，环路是死锁的充分必要条件。
如果处于环路中的每个资源类中资源实例的个数不全为 1，则环路的存在是产生死锁的必要
条件而不是充分条件。
14、资源分配图化简方法
1）在资源分配图中，找出一个既非等待又非孤立的进程结点 Pi，由于 Pi 可获得它所需要
的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去 Pi 所有的申
请边和分配边，使之成为既无申请边又无分配边的孤立结点。
2）将 Pi 所释放的资源分配给申请它们的进程，即在资源分配图中将这些进程对资源的申请
边改为分配边。
3）重复 1）、2）两步骤，直到找不到符合条件的进程结点。
第五部分：虚拟存储技术
1、虚拟存储技术
虚拟存储技术的基本思想是利用大容量的外存来扩充内存，产生一个比有限的实际内存空间
大得多的、逻辑的虚拟内存空间，简称虚存，以便能够有效地支持多道程序系统的实现和大
型程序运行的需要，从而增强系统的处理能力。
2、实现虚拟存储器需要以下的硬件支持。
1）系统有容量足够大的外存。
2）系统有一定容量的内存。
3）最主要的是，硬件提供实现虚-实地址映射的机制。
支持页式存储管理的硬件部件通常称为“存储管理部件”（Memory Management Unit，MMU）。
3、物理内存的分配与回收
1）查看空闲物理页面数是否能满足程序要求。
2）若能满足，则根据需求从位示图中找出一些为 0 的位，把这些位置成 1，
3）从空闲页面数中减去本次分配的页面数
4）按照找到的位计算出对应的物理页面号。
当找到一个为 0 的位后，根据它所在的字号、位号，按如下公式就可计算出对应的块号：
物理页面号=字号×字长+位号
把程序装入到这些物理页面中，并为该程序建立页表。
- 根据归还的物理页面号计算出该物理页面在位示图中对应的位置
- 将占用标志修改成 0
- 再把回收的物理页面数加入到空闲物理页面数中。
假定归还块的块号为，则在位示图中对应的位置为：
4、页式存储管理的地址转换
页表控制寄存器（页表始址寄存器、页表长度寄存器）+高速缓冲存储器的支持。
1）页表始址寄存器，用于保存正在运行进程的页表在内存的首地址，
2）页表长度寄存器，用于保存正在运行进程的页表的长度。
页表的作用：
1）指出该程序虚拟地址中的页号与所占用的物理页面号之间的对应关系。
2）页表又是硬件进行地址转换的依据，每执行一条指令时按虚拟地址中的页号查页表。
物理地址的计算公式为：
物理地址=物理页面号×块长+页内地址
需要强调的是，物理页面号又称为页帧和页框号。
5、页表项
在虚拟页式存储管理中，页表项的设计如下。
•物理页面号：页面在内存中时所对应的物理页面号。
•有效位：又称驻留位、存在位，表不该页是在内存还是在磁盘。
•访问位：访问位表示该页在内存期间是否被访问过。
•修改位：修改位表示该页在内存中是否被修改过。
•保护位：是否能读/写。
6、页表
（1）多级页表
大多数操作系统中采用二级页表，即由页表页和页目录一起构成进程页表。
第一级表示页目录，保存页表页的地址；
字长 ，位号 字长 字号 i mod i
=
=
第二级表示页表页，保存物理页面号。
（2）散列页表
当地址空间大于 32 位时，一种常见的方法是使用以页号为散列值的散列页表。
其中每个表项都包含一个链表，该链表中元素的散列值都指向同一个位置。
散列页表中的每个表项都包含三个字段：
（a）虚拟页号，（b）所映射的页框号，（c）指向链表中下一个元素的指针。
（3）反置页表
每个物理页框对应一个表项。每个表项包含与该页框相对应的虚拟页面地址，以及拥有该页
面进程的信息。
特点：
1）整个系统中只存在一个页表，并且每个页框对应其中一个表项
2）需要在反置页表中存放地址空间标志符
7、转换检测缓冲区（TLB）
按给定的虚拟地址进行读写时，必须访问两次内存。
第一次按页号读出页表中对应的块号，
第二次按计算出来的绝对地址进行读写。
两次访问内存显然延长了指令的执行周期，降低了执行速度。
为了提高存取速度，有两种方法：
1）在地址映射机制中增加一组高速寄存器保存页表
2）在地址映射机制中增加一个小容量的联想寄存器（相联存储器），它由高速缓冲存储器
组成。
8、缺页异常处理
若在页表中发现所要访问的页面不在内存，则产生缺页异常。
1）操作系统必须在内存中选择一个页面将其移出内存，
2）页面在内存期间已经被修改过，就必须把它写回磁盘
3）该页没有被修改过，不需要写回，调入的页直接覆盖被淘汰的页。
整个缺页处理过程简单阐述如下。
5）修改页表及内存分配表，表示该页已在内存。
6）如果内存中无空闲页，则按某种算法选择一个已在内存的页面，把它暂时调出内存
7）恢复现场，重新执行被中断的指令。
（1）调入策略
虚拟存储器的调入策略决定了什么时候将一个页由外存调入内存之中。
①请求调页（Demand Paging）:只调入发生缺页时所需的页面。
优点：
实现简单，
缺点：
容易产生较多的缺页，造成对外存 I/O 次数多，时间开销过大，容易产生颠簸现象。
②预调页（Prepaging）:在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。
优点：
高了调页的 I/O 效率，减少了 I/O 次数。
缺点：
造成浪费。
关于调入页面来源，通常有以下两种做法：
1）进程装入时，将其全部页面复制到交换区，以后总是从交换区调入。
2）凡是未被修改的页面，都直接从文件区读入，而被置换时不需调出；已被修改的页面，
被置换时需调出到交换区，以后从交换区调入。
（2）置页策略
当线程产生缺页时，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定
最佳位置的一组规则称为“置页策略”。
（3）置换策略
如果缺页发生时物理内存已满，“置换策略”被用于确定哪个虚页面必须从内存中移出为新
的页面腾出空位。
在虚拟页式存储管理方案中，可采用两种分配策略，即固定和可变分配策略。
在进行置换时，也可以采用两种策略，即全局置换和局部置换。将它们组合起来，有如下三
种策略。
将它们组合起来，有如下三种策略：
①固定分配局部置换（Fixed Allocation，Local Replacement）。
②可变分配全局置换（Variable Allocation，Global Replacement）。
③可变分配局部置换（Variable Allocation，Local Replacement）。
9、页面置换算法
颠簸的概念
如果刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久
又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”或称“颠簸”。
（1）理想页面置换算法（Optimal replacement，OPT）——最佳
OPT 算法淘汰以后不再需要的或者在最长时间以后才会用到的页面。这一算法一般不可能实
现，但它可以作为衡量其他页面淘汰算法优劣的一个标准。
（2）先进先出页面置换算法（First-In First-Out，FIFO）
优点：FIFO 算法简单，容易实现
缺点：最先装入内存的一页，不等于说这一页是不常使用的。很少使用纯 FIFO 算法。
（3）第二次机会页面置换算法
检查进入内存时间最久页面的 R 位，如果是 0，那么这个页面既老又没有被使用，可以立刻
置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改其进入时间，然后继
续搜索。
这一算法称为第二次机会（Second Chance）算法，其基本思想是寻找一个最近的时钟间隔
以来没有被访问过的页面。
（4）时钟页面置换算法（Clock）
（5）最近最少使用页面置换算法（Least Recently Used，LRU）
在缺页发生时，首先淘汰掉最长时间未被使用过的页面。这个策略称为 LRU 页面置换算法。
最近最少使用页面置换算法总是选择距离现在最长时间内没有被访问过的页面先调出。
这种实现方法必须对每一页的访问情况时时刻刻地加以记录和更新，实现起来开销比较大，
但 LRU 算法是在效果上最接近 OPT 算法的算法。
10、虚拟页式存储管理的优点缺点（重点）
优点：
1）有效地解决了碎片问题。2）提高了内存的利用率，3）利于组织多道程序执行。
缺点：
存在页面空间的浪费问题。这
11、虚拟存储管理的性能问题
引入虚拟存储管理，把内存和外存统一管理，其真正目的是把那些访问概率非常高的页放入
内存，减少内外存交换的次数。
在虚存中，页面可能在内存与外存之间频繁地调度，有可能出现抖动或颠簸。
原因：：
1）颠簸是由于缺页率高而引起的。
2）分配给一个进程的内存物理页面数太少
第六部分：控制方式
1、程序控制方式也称为 PI〇（Programmed I/O，程控 I/O）方式，
是指由用户进程直接控制处理器或内存和外围设备之间进行信息传送的方式，也称为“忙-
等”方式、轮询方式或循环测试方式；
这种方式的控制者是用户进程。
优点：
1）处理器和外设的操作能通过状态信息得到同步
2）硬件结构比较简单；
缺点：
1）处理器效率较低
2）对外部出现的异常事件无实时响应能力。
2、采用中断控制方式，可以做到以下内容。
1）处理器与外设在大部分时间内并行工作，有效地提高了计算机的效率。
2）具有实时响应能力，可适用于实时控制场合。
3）及时处理异常情况，提高计算机的可靠性。
4）如要采用中断方式进行数据传送，则处理器和设备控制器就应具备中断机构。
处理器一侧应具备的功能包括：
1）具备识别中断请求的能力，在每条指令执行结束应检测有无中断请求发生；
2）具备响应中断的能力（自动关中断、保留断点、转中断处理程序）；
3）当需要时，能拒绝响应外部中断请求；
4）具备按优先级响应中断请求的能力。
上述功能需要相应的电路支持，即需要设置寄存中断状态的“中断允许触发器”、能保留断
点和恢复断点的具有先进后出功能的堆栈、中断判优电路及其他相关电路。
设备控制器一侧应具备的功能包括：
1）具备寄存外设中断请求的能力
2）具备可屏蔽本级中断请求的能力
3、DMA 方式一般用于高速传送成组的数据。
优点：
1）操作均由硬件电路实现，传输速度快；
2）可以减少大批量数据传输时处理器的开销；
3）处理器与外设并行工作，效率高。
缺点：
DMA 方式也有一定的局限性，这是因为 DMA 方式在初始化和结束时仍由处理器控制，
4、通道（Channel）（1904 真题 35 题）
是一个特殊功能的处理器，它有自己的指令和程序，可以实现对外围设备的统一管理和外围
设备与内存之间的数据传送。
引入通道的目的是为了进一步减少数据输入输出对整个系统运行效率的影响。
与 DMA 方式相比：
1）通道方式增加了处理器与通道操作的并行能力；
2）增加了通道之间以及同一通道内各设备之间的并行操作能力；
3）为用户提供了灵活增加外设的可能性。
选择通道
一种高速通道，在物理上它可以连接多个设备，但是这些设备不能同时工作，在某一段时间
内通道只能选择一个设备进行工作。
选择通道主要用于连接高速外围设备，如磁盘、磁带等，信息以成组方式高速传输。
优点：以数据块为单位进行传输，传输率高；
缺点：通道利用率低。
数组多路通道
它的基本思想是当某个设备进行数据传送时，通道只为该设备服务；
当设备在执行寻址等控制性动作时，通道暂时断开与这个设备的连接，挂起该设备的通道程
序，去为其他设备服务，即执行其他设备的通道程序。
优点：
1）以数据块为单位进行传输，传输率高；
2）又具有多路并行操作的能力，通道利用率高。
缺点：控制复杂。
字节多路通道
一种简单的共享通道，在分时的基础上为多台低速和中速设备服务。
它的主要特点是：
1）以字节为单位交替进行的，各设备轮流占用一个很短的时间片；
2）多路并行操作能力与数组多路通道相同。
通道具有如下功能
1）接受处理器的指令，按指令要求与指定的外围设备进行通信。
2）从内存读取属于该通道的指令，并执行通道程序，向设备控制器和设备发送各种命令。
3）组织外围设备和内存之间进行数据传送，并根据需要提供数据缓存的空间，以及提供数
据存入内存的地址和传送的数据量。
4）从外围设备得到设备的状态信息，形成并保存通道本身的状态信息，根据要求将这些状
态信息送到内存的指定单元，供处理器使用。
5）将外围设备的中断请求和通道本身的中断请求，按序及时报告处理器。
第七部分：需要背的 pv 操作
1、读者写者问题
读者进程：
while（true）{
P（mutex）；
read_count=read_count+1；
If（read_count=1）P（write）；
V（mutex）；
读文件；
P（mutex）；
read_count=read_count-1；
If（read_count=0）V（write）；
V（mutex）；
}
写者进程：
while（true）{
P（write）；
写文件；
V（write）；
}
2、哲学家就餐问题
P（chopstick[i]）； {拿左筷子}
P（chopstick[（i+1）MOD 5]）； {拿右筷子}
用餐；
V（chopstick[i]）； {放左筷子}
V（chopstick[（i+1）MOD5]）； {放右筷子}
Until false；
Repeat
思考；
P（chopstick[1]）； {拿右筷子}
P（chopstick[5]）； {拿左筷子}
用餐；
V（chopstick[1]）； {放右筷子}
V（chopstick[5]）； {放左筷子}
Until false；
