进程管理
⭐ 主要考点
- 进程前趋图
- 进程页面置换算法
进程管理也称处理机管理。
进程是资源分配和独立运行的基本单位。
程序与进程
程序可以顺序和并发执行。
程序顺序执行的特征是：
- 顺序性
- 封闭性
- 可再现性
程序并发执行的特征是：
- 失去了程序的封闭性
- 程序和机器的执行程序的活动不再一一对应
- 并发程序之间的相互制约性
由于程序的并发执行，破坏了程序的封闭性和可再现性，为了解决这一问题，需要研究进程间的同步和互斥问题。
进程的组成
进程是程序的一次执行，该程序可以和其他程序并发执行。
进程通常由程序、数据和进程控制块（PCB，process control block）组成。
PCB：进程存在的唯一标识。
进程的状态及切换
进程的三态模型：
- 运行
对于单处理机系统，处理运行状态的进程只有一个。
- 就绪
一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则此进程处于就绪状态。
- 阻塞
进程正在等待某一事件的发生（请求I/O）而暂停运行，即使吧处理机分配给进程也无法运行，则进程处于阻塞状态。
进程的五态模型：
- 新建
- 就绪
- 运行
- 阻塞
- 终止
进程的新建即为一个新进程创建必要的管理信息。
进程的终止即等待操作系统进行善后处理，以及释放主存。
进程的控制
进程的控制是由操作系统内核（kernel）中的原语(primitive)完成的。
原语是由若干条机器指令组成的，用于完成特定功能的程序段。
原语的特点是执行时不能被分割，即属于原子操作。
进程间通信
进程通信是指各个进程交换信息的过程。
- 同步和互斥
进程的互斥是指系统中多个进程因争用临界资源而互斥执行。
有些资源一次只能供一个进程使用，称为临界资源（critical resource， CR）
- 信号量机制
⭐ p136, 关于信号量的相关知识，可以了解
- 高级通信原语
临界区管理的原则
临界区（critical Section，CS）是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下：
- 有空即进
- 无空则等
- 有限等待
- 让权等待
进程调度
进程调度是指当有更高优先级的进程到来时如何分配CPU。
在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。
常用的调度算法有：
- 先来先服务
- 时间片轮转
- 优先级调度
- 多级反馈调度
进程优先级的确定，通常考虑如下情况：
- 对于I/O进程，让其进入最高优先级队列
- 对于计算型进程，每次都执行完时间片后进入更低级队列
死锁
所谓死锁，是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。
⭐ P141 /p143 页死锁例题
产生死锁的原因及4个必要条件：
- 互斥条件
- 请求保持条件
- 不可剥夺条件
- 环路条件
线程
线程是进程中的一个实体，是被系统独立分配和调度的基本单位。
⚡ 相关真题
2014年24/25
假设某计算机系统中资源R的可用数为6，系统中有3个进程竞争R，且每个进程都需要i个R，该系统可能会发生死锁的最小i值是（24）。
若信号量S的当前值为-2，则R的可用数和等待R的进程数分别为（25）。
(24) A.1 B.2 C.3 D.4
(25) A.0、0 B.0、1 C.1、0 D.0、2
【答案】C D
【解析】本题考查操作系统进程管理信号量方面的基础知识。
(24) C是正确的，因为，每个进程都需要3个资源 R，系统为3个进程各分配2个，系统中资源R的可用数为0, 3个进程再申请1个资源R得不到满足，故发生死锁；
(25) 早在1965年荷兰学者Dijkstra提出信号量机制是一种有效的进程同步与互斥工具。
目前，信号量机制有了很大的发展，主要有整型信号暈、记录型信号量和信号量集机制。
对于整型信号量可以根据控制对象的不同被赋予不同的值。
通常将信号量分为公用信号量和私用信号量两类。
其中，公用信号量用于实现进程间的互斥，初值为1或资源的数目；私用信号量用于实现进程间的同步，初值为0或某个正整数。
⚡ 信号量S的物理意义：
- S≥0表示某资源的可用数
- 若S<0,则其绝对值表示阻塞队列中等待该资源的进程数。
本题由于信号量S的当前值为-2, 则意味着系统中资源R的可用个数M=0, 等待资源R的进程数N=2。
2014年26题
某计算机系统页面大小为4K，若进程的页面变换表如下所示，逻辑地址为十六进制1D16H。该地址经过变换后，其物理地址应为十六进制（26）。
(26)A.1024H B.3D16H C.4D16H D.6D16H
【解析】B
根据题意页面大小为4K，逻辑地址为十六进制1D16H其页号为1，页内地址为D16H,查页表后可知物理块号为3,
该地址经过变换后，其物理地址应为物理块号3拼上页内地址D16H，即十六进制3D16H。
2015年23-35题
进程P1、P2、P3、P4和P5的前趋图如下所示：
若用PV操作控制进程P1、P2、P3、P4和P5并发执行的过程，则需要设置5个信号量S1、S2、S3、S4和S5,且信号量S1～S5的初值都等于零。
下图中:
a、b和c处应分别填写（23）；
A. V（S1）、P（S1）和V（S2）V（S3）
B. P（S1）、V（S1）和V（S2）V（S3）
C. V（S1）、V（S2）和P（S1）V（S3）
D. P（S1）、V（S2）和V（S1）V（S3）
p1执行完，通知p2进程，所以a 为 V(S1), 即唤醒下一个进程
p2 需要检查p1是否完成，所以b 为 P(S1)
p2执行完，需要通知 p3、p4，所以c为V(S2) V(S3)
d和e处应分别填写（24）
A. V（S2）和P（S4）
B. P（S2）和V（S4）
C. P（S2）和P（S4）
D. V（S2）和V（S4）
f和g处应分别填写（25）
A. P（S3）和V（S4）V（S5）
B. V（S3）和P（S4）和P（S5）
C. P（S3）和P（S4）P（S5）
D. V（S3）和V（S4）和V（S5）
【答案】A B C
【解析】本题考察进程的前趋图？
所谓前趋图 (Precedence Graph)，是指一个有向无循环图，可记为DAG (Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。
记住以下概念即可：
- P(X)：这个主要就是检查上一个进程是否完成
- V(X)：就是唤醒当前进程指向的下一个进程
- 线(箭头)代表信号量， 先V后P， VP一对
2015年26题
某进程有4个页面，页号为0~3，页面变换表及状态位、访问位和修改位的含义如下图所示。
若系统给该进程分配了3个存储块，当访问的页面1不在内存时，淘汰表中页号为（26）的页面代价最小。
(26)A.0 B.1 C.2 D.3
【答案】D
根据题意，页面变换表中状态位等于0和1分别表示页面不在内存或在内存**，所以0、2和3号页面在内存**。
当访问的页面1不在内存时，系统应该首先淘汰未被访问的页面
因为根据程序的局部性原理，最近未被访问的页面下次被访问的概率更小；
如果页面最近都被访问过，应该先淘汰未修改过的页面。
因为未修改过的页面内存与辅存一致，故淘汰时无须写回辅存，使系统页面置换代价小。
经上述分析，0、2和3号页面都是最近被访问过的，但0和2号页面都被修改过而3号页面未修改过，故应该淘汰3号页面。
⚡ 提示：
先淘汰访问次数最少的页面，若访问次数相同，再淘汰未被修改的页面。
先看访问位，访问位一样的话，再看修改位。