操作系统复习笔记（I）：进程管理
进程与线程章节概述
本章的基本内容：
- 进程与线程
- 基本概念
- 状态转换
- 控制
- 通信
- CPU调度
- 调度的概念
- 调度的实现
- 调度算法
- 同步与互斥
- 基本概念
- 信号量机制
- 经典同步问题
- 死锁
- 死锁预防
- 死锁避免
- 死锁检测和解除
进程与线程
进程的概念
- 为何引入进程？
- 多道程序环境下，多个程序并发执行，它们需要良好的封闭性、并发性和共享性。
- 进程就是为了更好地描述程序的并发执行，实现并发性和共享性。
- 进程与进程映像
- 进程映像是静态概念，进程是动态概念。
- 进程映像（进程实体）的构成有程序段、数据段、PCB
- 进程的特征
- 动态性：进程有着创建、就绪、执行、终止等生命周期。动态性是进程最基本的特征。
- 并发性：多个进程实体能共同存在于内存中并发执行。进程重要特性，OS的重要特性。
- 独立性：进程实体是一个独立运行、获取资源、接收调度的基本单位。
- 异步性：进程按照各自速度向前推进，导致执行结果不可再现性。
- 进程的状态
- 基本状态
- 运行态：每个时刻只有1个进程处于运行态。
- 就绪态：进程已经获得资源，处于就绪队列中，等待调度。
- 阻塞态：等待某事件而暂停运行，如IO，处于阻塞队列中。
- 创建态：申请PCB->填写控制信息->分配资源->转入就绪态，加入就绪队列
- 终止态
- 基本状态
- 进程状态的切换：见下图
进程控制块PCB
- 描述：进程创建时分配PCB，该结构常驻内存。PCB是进程实体的一部分，是进程存在的唯一标志。
- PCB主要内容：
- 进程描述信息：进程标识符PID、用户标识符UID
- 进程控制和管理信息：状态、优先级；代码入口、外存地址；进入内存时间、运行时间
- 资源分配清单：各个段的指针；文件描述符FD；键盘和鼠标
- 处理机相关信息：通用寄存器、地址寄存器、状态寄存器、标志寄存器、状态字等
进程控制
- 原语的概念：进程控制的程序段称之为原语。原语在执行期间不允许中断，是一个不可分割的基本单位。
- 创建原语：
- 描述：父进程创建子进程，子进程继承父进程的资源。
- 步骤：
- 分配PID，申请空白PCB。PCB是有限的，如果申请失败，就无法创建。
- 分配资源：Mem、I/O、文件、CPU——在PCB中体现。
- 初始化PCB：标志信息、处理机状态信息、控制信息、优先级
- 加入就绪队列，等待被调度
- 终止原语
- 引入终止的事件：
- 正常结束
- 异常结束：如存储越界、计算出错
- 外界干预：父进程终止、OS干预等
- 步骤：
- 检索出该进程的PCB
- 终止其运行，剥夺CPU。
- 终止子孙进程运行。
- 归还资源给父进程或者操作系统。
- 将PCB从所在队列中删除。
- 引入终止的事件：
- 阻塞和唤醒
- 阻塞Block：期待的某些事件未发生。进程调用阻塞原语自己把自己阻塞了。
- 找到PCB
- 保护现场，更换为阻塞态。
- 插入等待队列，释放CPU资源。
- 唤醒Wakeup：其它进程调用Wakeup。
- 从等待队列中找到PCB。
- 从等待队列移除，更改为就绪态。
- 插入就绪队列。
- 阻塞Block：期待的某些事件未发生。进程调用阻塞原语自己把自己阻塞了。
复习中断和异常的概念
- 中断（外中断）：CPU外部事件。
- 可屏蔽中断
- 不可屏蔽中断
- 异常（内中断）：CPU内部事件。
- 故障：指令执行时的异常。
- 自陷：事先安排好的，用户态调用内核态时发生。
- 终止：硬件故障。如存储器出错。
进程通信
- 低级通信：PV操作
- 高级通信
- 共享存储：对共享空间进行读写。需要通过特殊的系统调用。
- 消息传递
- 直接消息传递：直接发送后，挂在接收进程的消息队列上。
- 间接消息传递：发送到中间实体信箱。
- 管道通信
线程的概念
- 引入目的：减少并发的时空开销，提高并发性能。
- 地位：线程是基本的CPU执行单元，是独立调度和分派的基本单位。而进程只是除CPU外的系统资源分配单位。
- 进程和线程的比较：
- 调度：线程是独立调度的基本单位。切换代价小于进程。
- 并发性：线程提高了OS的并发性。
- 资源：线程不用有系统资源，可以访问进程的资源。同一进程所有线程具有相同地址空间
- 独立性：每个进程拥有独立的地址空间和资源。线程共享地址空间和资源。
- 系统开销：线程切换的开销很小。
- TCB内容：TID、寄存器、状态、优先级、堆栈指针
线程实现方式
线程的实现可以分为：用户级线程ULT和内核级线程KLT。
- ULT：用户级线程，如下图a所示。
- 特点：线程管理工作都在用户空间完成，内核意识不到线程的存在。
- 优点：
- 线程切换时无需模式切换，减少切换开销。
- 进程可以根据自己需求自定义调度算法。
- 由用户管理线程调度。
- 缺点：
- 阻塞：线程执行系统调用，会使得该进程内其它线程都阻塞。
- 无法发挥多处理机优势：每次进程中仅有一个线程被执行。
- KLT：内核级别线程，如下图b所示。
- 特点：在内核支持下运行，由内核调度。
- 优点：
- 发挥多处理机优势，内核能调度同一进程下的不同线程。
- 没有阻塞问题，一个线程阻塞不影响其它线程。
- 线程切换开销小
- 缺点：
- 同一进程线程切换需要模式切换（因为是在内核调度），切换开销大。
- 组合方式：如下图c所示。
- 特点：用户线程时分多路复用内核线程。
多线程模型
在同时支持用户线程和内核线程的系统中，用户线程和内核线程的连接方式不同，形成了三种多线程的模型。
- 多对一：
- 描述：一个内核级线程对应多个用户级线程。
- 优点：线程管理在用户态，效率高
- 缺点：如果一个线程访问内核时阻塞，整个进程阻塞；任何时候只能有一个线程访问内核
- 一对一
- 描述：每个用户级线程对应一个内核级线程。
- 优点：无阻塞问题，并发能力强。
- 缺点：创建开销大，每次创建一个用户线程就要对应创建一个内核线程。
- 多对多
- 描述：n个用户线程映射到m个内核线程，n>=m
- 具有两种模型的优点
处理机调度
- 调度的概念：
- 处理机调度指的是从就绪队列中按照一定的算法，以公平和高效的原则，选择一个进程并将处理机分配给它运行。
- 三级调度：一个作业的调度往往要经过三级调度。
- 高级调度（作业调度）：从外存上的后备队列选择一个作业，分配资源并建立进程。
- 调度本质：位于辅存和内存之间的调度。
- 适合场景：多道批处理系统。
- 中级调度（内存调度）：将暂时不运行的进程调入外存等待（挂起态）
- 调度本质：存储器管理中的对换功能。
- 将暂时不运行的进程调入外存等待（挂起态）
- 把外存上具备运行条件的就绪进程重新调入内存，并修改状态为就绪态，挂在就绪队列中。
- 目的：提高内存利用率和系统吞吐量。
- 调度本质：存储器管理中的对换功能。
- 低级调度（进程调度）：从就绪队列中挑选一个进程分配处理机。
- 高级调度（作业调度）：从外存上的后备队列选择一个作业，分配资源并建立进程。
调度目标
调度算法的评价标准有如下5个：
CPU利用率
CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}
系统吞吐量
系统吞吐量：单位时间CPU完成作业的数量。
- 长作业：会降低吞吐量。
- 短作业：会提升吞吐量。
周转时间
周转时间：
周转时间=作业完成时间-作业提交时间
平均周转时间：多个作业的周转时间的平均值。
带权周转时间：周转时间比上实际运行时间
带权周转时间=\frac{作业周转时间}{作业实际运行时间}
等待时间
进程处于等处理机的时间之和。最简单的考察方式。
响应时间
交互式系统看重这个指标。
调度实现
调度器 = 排队器 + 分派器 + 上下文切换器
- 排队器：按照策略将就绪进程加入就绪队列。
- 分派器：从就绪队列取出进程，分配给CPU。
- 上下文切换器：
- 第一次上下文切换：当前进程上下文保存到PCB中。
- 第二次上下文切换：将新进程的CPU现场装入各寄存器。
调度实际、切换与过程
调度时机：
- 正常结束
- 异常结束
- IO请求
- 时间片用完
不能进行进程调度和切换的情况：
- 在处理中断的过程中。
- 进程进入OS内核临界区时（加锁访问）
- 其它需要完全屏蔽中断的原子操作过程中。
应该进行调度和切换的情况：
- 发生引入调度的条件并且当前进程无法继续运行，非剥夺调度。
- 中断结束或者trap结束，返回中断进程的用户态执行前，如果置上请求调度标志，则可以马上调度和切换。属于剥夺式调度。
进程调度方式
非抢占式调度：不适合分时系统，实时系统。
抢占式调度：遵循一定原则。
闲逛进程
没有就绪进程，就会调度闲逛进程。不需要CPU外的资源，不会被阻塞。
调度算法
FCFS调度
- 支持范围：作业调度、进程调度
- 描述：选择最早进入队列的作业/进程调入内存。
- 类型：不可剥夺算法。
- 优点：算法简单，相对公平。
- 缺点：对长作业（CPU繁忙型）有利，对短作业（IO繁忙型）不利。
SJF调度
- 描述：从队列中选择估计运行时间最短的作业调入内存。
- 优点：平均等待时间和平均周转时间最少。
- 缺点：
- 对长作业不利。可能会出现饥饿现象。
- 未考虑作业的紧迫性。
- 作业的长短是根据用户所提供的估计执行时间确定。
优先级调度
- 优先级：描述作业的紧迫性。
- 描述：每次从队列中选择优先级最高的分配处理机。
- 分类：
- 非抢占式优先级调度算法：如果正在运行即使来了更急的任务，也不暂停。
- 抢占式优先级调度算法：立刻暂停，分配给高优先级的任务
- 静态优先级：创建进程时确定。
- 动态优先级：动态调整。
- 优先级的设置：
- 系统 > 用户
- 交互 > 非交互
- I/O > 计算：让I/O尽快工作，提升整体效率
高响应比调度
- 适用范围：作业调度。
- 描述：对FCFS和SJF的综合平衡，考虑了作业的等待时间和估计运行时间。
- 响应比公式：
响应比=\frac{等待时间+要求时间}{要求时间}
- 等待时间相同，要求时间越短，响应比越高。有利于短作业。
- 要求时间相同，等待时间越长，响应比越高。类似于FCFS
RR调度
- 适用范围：分时系统。
- 描述：将就绪进程按照FCFS策略排成就绪队列，每次选第一个进程执行，每次只能执行一个时间片例如50ms，使用完后必须释放处理机，同时排到队尾。
- 特点：
- 如果时间片太大，退化为FCFS。
- 如果时间片太短，切换开销太大。
多级反馈队列调度
- 思想：
- 设置多个就绪队列，赋予不同优先级。第一级最高，依次降低。
- 赋予各个队列的时间片大小不同，优先级越高时间片越小。
- 各个队列采用FCFS算法。如果时间片内没完成，降级到下一级队尾。
- 第一级队列为空，才执行第二级，以此类推。
- 优点：兼顾了长短作业，响应时间好，可行性强。
进程切换
进程切换有两种，一个是上下文切换，一个是模式切换。
- 上下文切换
- 上下文：CPU的寄存器和PC的值。
- 描述：保存当前运行进程状态到PCB，恢复另一个进程的状态。
- 特点：计算密集型，每次切换都是ns级别。
- 上下文切换的流程：
- 挂起一个进程，保存CPU上下文，更新PCB。
- 将进程PCB移入到就绪队列/阻塞队列。
- 选择一个进程，更新其PCB。
- 跳到新进程的PC位置运行。
- 恢复上下文
- 模式切换
- 两状态：
- 内核态：也叫做管态和系统态。
- 用户态：也叫做目态。用户程序只能运行在目态。
- 描述：用户态和内核态之间的切换。可能还在同一个进程中。
- 关系：上下文切换只能发生在内核态
- 两状态：
同步与互斥
基本概念
- 临界资源：多进程共享的资源中，仅允许一个进程使用的资源。
- 例如：变量、数据、打印机
- 临界区：访问临界资源的那段代码，称之为临界区。
- 同步：协调工作次序而等待、传递信息所产生的直接制约关系。
- 互斥：间接制约关系。
同步机制遵循的原则
- 空闲让进：临界区空闲时，进程可以进入。
- 忙则等待：已有进程进入临界区，其它进程必须等待。
- 有限等待：请求访问的进程，有限时间内要能够进入临界区。
- 让权等待：不能进入临界区时，要释放处理机，防止忙等。
实现临界区互斥的方法
硬件实现方法：
- 中断屏蔽法：进入临界区前关中断，但是效率很会很低，而且把这个权利给用户不明智。
- 硬件指令法：TestAndSet原子操作，读取指定标志后设置为True
- 进入前，使用TestAndSet，如果没人在，则标志为False，可以进入。同时关闭临界区，把标志设置为True。退出时要手动赋值为False。
while(TestAndSet(&lock));
// 进入临界区 do sth...
lock = false;
互斥锁
- 描述：进入临界区的时候获得锁，退出临界区的时候释放锁。
- 操作：每个互斥锁有一个变量
available表示锁是否可用。获得锁和释放锁都是原子操作。 - 缺点：拿不到锁就忙等待。
acquire(){
while(!available); // 忙等待
available = false;
}
release(){
available = true;
}
信号量
信号量机制可以用来解决同步互斥问题，只能被PV操作这两个原语访问。
两种信号量
- 整数型信号量：会让进程处于忙等待。
- 不满足让权等待，会让进程一直处于忙等。
wait(S){
while(S<=0);
s -= 1;
}
signal(S){
s +=1;
}
- 记录型信号量：
- 组成：资源数目的整型变量value；等待进程的链表。
- 好处：实现了让权等待。
typedef struct{
int value;
struct process *list;
} semaphore;
void wait(semaphore S){
S.value --;
// < ，因为减完<0说明原来是1
if(S.value<0){
addToList();
block(S.list); // 放弃处理机，遵循让权等待。
}
}
void signal(semaphore S){
S.value ++;
if(S.value <=0){
removeFromList();
wakeup(P);
}
}
进程同步和互斥
信号量实现同步：
- 信号量初始值：S=0。
- 关键：前V后P
semaphore S=0;
P1(){ // 先
// do sth
V(S);
}
P2(){ //后
P(S);
// do sth
}
信号量实现互斥：
- 信号量初始值：S=1。
- 关键：PV包裹
semaphore S=1;
P1(){
P(S);
//...
V(S);
}
P2(){
P(S);
//...
V(S);
}
信号量实现前驱图：
- 关键：每个边一个信号量；出边V，入边P；P完才能继续V。
经典同步问题
生产者-消费者
- 问题描述：
- 一组生产者进程和一组消费者进程共享一个初始为空，空间为n的缓冲区。
- 没满才能生产，没空才能消费。
- 生产者和消费者互斥。
简单生产者消费者：明确信号量即可
- 三个对象：临界区、生产者、消费者
- 关系：临界区互斥，生产者消费者同步
- 起始信号量：
- 互斥 = 1，满的为0，空的为n
semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;
producer(){ // 关注empty
while(1){
p(empty);
p(mutex);
// ...
v(mutex);
v(full);
}
}
consumer(){ // 关注full
while(1){
p(full)
p(mutex)
// ...
v(mutex)
v(empty)
}
}
复杂生产者消费者
- 描述：两个生产者两个消费者，一个临界区
- 问题描述：桌上有个盘子（临界区），只能向其中放一个水果。爸爸放苹果，妈妈放橘子，儿子消费橘子，女儿消费苹果。
- 问题分析：
- 互斥关系：爸爸和妈妈。
- 同步关系：女儿和爸爸；儿子和妈妈。
- 信号量设置：
- plate：是否允许向盘中放水果。
- apple：同步
- orange：同步
semaphore plate = 1;
semaphore orange = 0;
semaphore apple = 0;
dad(){
p(plate);
v(apple);
}
mom(){
p(plate);
v(orange);
}
son(){
p(orange);
v(plate);
}
daughter(){
p(apple);
v(plate);
}
读者-写者问题
- 问题描述：
- 允许多个读者同时读
- 只允许一个写者写
- 写者写时不允许读者进程或者写者进程进入
- 写者执行写前，要让已有的读者和写者都退出。
读者优先
- 问题分析：
- 读写互斥
- 写写互斥
- 读者和读者不互斥：计数器。
- 信号量：
- rw：实现读写互斥
- count：记录读者数量。
- mutex：互斥访问count的访问
int count = 0;
semaphore mutex = 1;
semaphore rw = 1;
reader(){
p(mutex);
if(count == 0){
p(rw);
}
count++;
v(mutex);
// read
p(mutex);
count--;
if(count == 0){
v(rw);
}
v(mutex);
}
writer(){
p(rw);
// write
v(rw);
}
读写公平
新增信号量：
- w实现写优先，可以理解为一个队列。
int count = 0;
semaphore mutex = 1;
semaphore rw = 1;
semaphore w = 1;
writer(){
p(w); // 表示谁先来
p(rw);
v(rw);
v(w);
}
reader(){
p(w); // 核心：无写进程的时候才进入。
p(mutex);
if(count == 0){
p(rw);
}
count ++;
v(mutex);
v(w); // 这时其他写进程也可以进来排队
//read
p(mutex);
count--;
if(count == 0){
v(rw);
}
v(mutex);
}
哲学家就餐
- 问题描述：哲学家之间对筷子的访问时互斥的。
- 信号量：
chopstick数组。 - 制定策略：最多只允许4个哲学家就餐，就可以了。
semaphore chopstick[5] = {1,1,1,1,1};
semaphore max= 4; // 最多允许四个哲学家就餐
process_i(){
do{
p(max); // 互斥信号
p(chopstick[i]); // 取左边
p(chopstick[(i+1)%5]); // 取右边
// ...eat
v(max); // 不取了
v(chopstick[i]); // 放左边
v(chopstick[(i+1)%5]); //放右边
// ... think
}while(1);
}
吸烟者
- 描述：单生产者多消费者问题。要保证消费者1消费完成才会继续向后面的消费者进行生产。
- 信号量：
- 消费是否完成的同步信号量
finished - 提供者的同步信号量
offer1 offer2 offer3
- 消费是否完成的同步信号量
semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finished = 0;
int num = 0; // 随机数
producer(){
while(1){
num++;
num%=3;
if(num == 0)
v(offer1);
if(num == 1)
v(offer2);
if(num == 2)
v(offer3);
p(finished);
}
}
consumer1(){
while(1){
p(offer1);
// ...
v(finished);
}
}
consumer2(){
while(1){
p(offer2);
// ...
v(finished);
}
}
consumer3(){
while(1){
p(offer3);
// ...
v(finished);
}
}
死锁
死锁的定义
- 死锁的概念：多个进程在竞争资源的时候造成的互相等待的局面。
- 死锁产生的原因：
- 系统资源的竞争
- 进程推进顺序非法
- 死锁的条件：
- 互斥条件：共享资源只允许一个进程访问，一般无法破坏这个条件。
- 不剥夺条件：进程只能主动释放资源，不可被抢夺。
- 请求并保持条件：进程已经持有一个资源，仍然请求下一个资源，且不释放原资源。
- 案例：哲学家就餐问题中一次性分配左右两支筷子。
- 循环等待条件：存在循环等待链。（有循环等待链不一定死锁，死锁一定有循环等待链）
- 死锁处理的三种策略：
- 死锁预防：破坏4条件中的1个。
- 死锁避免：合理的分配资源，如银行家算法。
- 死锁检测和解除
死锁预防：破坏四个条件
- 破坏互斥条件：不太可行。
- 破坏不剥夺条件：会造成前段时间工作失效，不适合IO资源。
- 破坏请求并保持：预先静态分配法，进程一次性申请所有资源，如果资源不够先不给运行。
- 举例：哲学家就餐问题中一次性分配两只筷子。
- 破坏循环等待：顺序资源分配法。限制了新类型设备的添加，用户编程也麻烦。
死锁避免：银行家算法
死锁避免是在资源的动态分配下功夫，防止系统进入不安全状态。
系统安全状态
- 安全序列：系统按照某种进程推进顺序为每个进程分配资源，直到满足每个进程对资源的最大需求，使得每个进程都可以顺利完成。
- 我们可以将安全序列类比为借贷和还贷的过程，这一点王道书上讲的不错。
- 不安全状态：无法找到一个安全序列。
- 不安全状态可能发生死锁，只要处于安全状态就可以避免进入死锁。
- 避免死锁的本质是不进入不安全状态。
银行家算法
- 思想：
- OS视作银行家，资源就是资金，进程请求分配资源就是贷款。
- 进程运行前先声明最大需求量，如果进程执行中申请资源，OS会测试该进程已占用资源数和本次申请资源数之和，是否超过了最大需求量。如果超过了就不分配。
- 不超过就测试库存能否满足该进程的需要的最大资源量，如果满足就分配，如果不满足就延迟分配。
- 概念：
- 需求矩阵 = 最大需求矩阵 - 分配矩阵
- 剩余资源数向量
- 步骤：
- 根据max矩阵和allocation矩阵计算出Need矩阵。
- 将Work向量和Need矩阵逐行对比，找到一个全部维度都比work向量小的行。
- 此时我们可以选择这行，回收其资源，给各元素加上allocation矩阵中对应行。而这一行的下表就可以添加到安全序列中去。
- 重新这个过程，直到得到一个安全序列。
死锁检测和解除
资源分配图
死锁定理
- 在资源分配图中找到既不阻塞又不孤立的进程，消去它所有的请求边和分配边，使它成为孤立的节点。
- 释放的资源可以唤醒某些阻塞的进程，继续消去，如果图中边能完全消去，则为可完全简化。
死锁定理：死锁当且仅当资源分配图不可简化。
死锁解除
- 资源剥夺法：挂起死锁进程，抢占其资源。
- 撤销进程法：强制撤销某些进程并抢占其资源。
- 进程回退法：回退到足以避免死锁的地步。
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 AjaxZhan
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果