进程与线程章节概述

本章的基本内容：

进程与线程
- 基本概念
- 状态转换
- 控制
- 通信
CPU调度
- 调度的概念
- 调度的实现
- 调度算法
同步与互斥
- 基本概念
- 信号量机制
- 经典同步问题
死锁
- 死锁预防
- 死锁避免
- 死锁检测和解除

进程与线程

进程的概念

为何引入进程？
- 多道程序环境下，多个程序并发执行，它们需要良好的封闭性、并发性和共享性。
- 进程就是为了更好地描述程序的并发执行，实现并发性和共享性。
进程与进程映像
- 进程映像是静态概念，进程是动态概念。
- 进程映像（进程实体）的构成有程序段、数据段、PCB
进程的特征
- 动态性：进程有着创建、就绪、执行、终止等生命周期。动态性是进程最基本的特征。
- 并发性：多个进程实体能共同存在于内存中并发执行。进程重要特性，OS的重要特性。
- 独立性：进程实体是一个独立运行、获取资源、接收调度的基本单位。
- 异步性：进程按照各自速度向前推进，导致执行结果不可再现性。
进程的状态
- 基本状态
  - 运行态：每个时刻只有1个进程处于运行态。
  - 就绪态：进程已经获得资源，处于就绪队列中，等待调度。
  - 阻塞态：等待某事件而暂停运行，如IO，处于阻塞队列中。
- 创建态：申请PCB->填写控制信息->分配资源->转入就绪态，加入就绪队列
- 终止态
进程状态的切换：见下图

进程控制块PCB

描述：进程创建时分配PCB，该结构常驻内存。PCB是进程实体的一部分，是进程存在的唯一标志。
PCB主要内容：
- 进程描述信息：进程标识符PID、用户标识符UID
- 进程控制和管理信息：状态、优先级；代码入口、外存地址；进入内存时间、运行时间
- 资源分配清单：各个段的指针；文件描述符FD；键盘和鼠标
- 处理机相关信息：通用寄存器、地址寄存器、状态寄存器、标志寄存器、状态字等

进程控制

原语的概念：进程控制的程序段称之为原语。原语在执行期间不允许中断，是一个不可分割的基本单位。
创建原语：
- 描述：父进程创建子进程，子进程继承父进程的资源。
- 步骤：
  1. 分配PID，申请空白PCB。PCB是有限的，如果申请失败，就无法创建。
  2. 分配资源：Mem、I/O、文件、CPU——在PCB中体现。
  3. 初始化PCB：标志信息、处理机状态信息、控制信息、优先级
  4. 加入就绪队列，等待被调度
终止原语
- 引入终止的事件：
  1. 正常结束
  2. 异常结束：如存储越界、计算出错
  3. 外界干预：父进程终止、OS干预等
- 步骤：
  1. 检索出该进程的PCB
  2. 终止其运行，剥夺CPU。
  3. 终止子孙进程运行。
  4. 归还资源给父进程或者操作系统。
  5. 将PCB从所在队列中删除。
阻塞和唤醒
- 阻塞Block：期待的某些事件未发生。进程调用阻塞原语自己把自己阻塞了。
  1. 找到PCB
  2. 保护现场，更换为阻塞态。
  3. 插入等待队列，释放CPU资源。
- 唤醒Wakeup：其它进程调用Wakeup。
  1. 从等待队列中找到PCB。
  2. 从等待队列移除，更改为就绪态。
  3. 插入就绪队列。

复习中断和异常的概念

中断（外中断）：CPU外部事件。
- 可屏蔽中断
- 不可屏蔽中断
异常（内中断）：CPU内部事件。
- 故障：指令执行时的异常。
- 自陷：事先安排好的，用户态调用内核态时发生。
- 终止：硬件故障。如存储器出错。

进程通信

低级通信：PV操作
高级通信
1. 共享存储：对共享空间进行读写。需要通过特殊的系统调用。
2. 消息传递
  1. 直接消息传递：直接发送后，挂在接收进程的消息队列上。
  2. 间接消息传递：发送到中间实体信箱。
3. 管道通信

线程的概念

引入目的：减少并发的时空开销，提高并发性能。
地位：线程是基本的CPU执行单元，是独立调度和分派的基本单位。而进程只是除CPU外的系统资源分配单位。
进程和线程的比较：
- 调度：线程是独立调度的基本单位。切换代价小于进程。
- 并发性：线程提高了OS的并发性。
- 资源：线程不用有系统资源，可以访问进程的资源。同一进程所有线程具有相同地址空间
- 独立性：每个进程拥有独立的地址空间和资源。线程共享地址空间和资源。
- 系统开销：线程切换的开销很小。
TCB内容：TID、寄存器、状态、优先级、堆栈指针

线程实现方式

线程的实现可以分为：用户级线程ULT和内核级线程KLT。

ULT：用户级线程，如下图a所示。
- 特点：线程管理工作都在用户空间完成，内核意识不到线程的存在。
- 优点：
  - 线程切换时无需模式切换，减少切换开销。
  - 进程可以根据自己需求自定义调度算法。
  - 由用户管理线程调度。
- 缺点：
  - 阻塞：线程执行系统调用，会使得该进程内其它线程都阻塞。
  - 无法发挥多处理机优势：每次进程中仅有一个线程被执行。
KLT：内核级别线程，如下图b所示。
- 特点：在内核支持下运行，由内核调度。
- 优点：
  - 发挥多处理机优势，内核能调度同一进程下的不同线程。
  - 没有阻塞问题，一个线程阻塞不影响其它线程。
  - 线程切换开销小
- 缺点：
  - 同一进程线程切换需要模式切换（因为是在内核调度），切换开销大。
组合方式：如下图c所示。
- 特点：用户线程时分多路复用内核线程。

多线程模型

在同时支持用户线程和内核线程的系统中，用户线程和内核线程的连接方式不同，形成了三种多线程的模型。

多对一：
- 描述：一个内核级线程对应多个用户级线程。
- 优点：线程管理在用户态，效率高
- 缺点：如果一个线程访问内核时阻塞，整个进程阻塞；任何时候只能有一个线程访问内核
一对一
- 描述：每个用户级线程对应一个内核级线程。
- 优点：无阻塞问题，并发能力强。
- 缺点：创建开销大，每次创建一个用户线程就要对应创建一个内核线程。
多对多
- 描述：n个用户线程映射到m个内核线程，n>=m
- 具有两种模型的优点

处理机调度

调度的概念：
- 处理机调度指的是从就绪队列中按照一定的算法，以公平和高效的原则，选择一个进程并将处理机分配给它运行。
三级调度：一个作业的调度往往要经过三级调度。
1. 高级调度（作业调度）：从外存上的后备队列选择一个作业，分配资源并建立进程。
  1. 调度本质：位于辅存和内存之间的调度。
  2. 适合场景：多道批处理系统。
2. 中级调度（内存调度）：将暂时不运行的进程调入外存等待（挂起态）
  1. 调度本质：存储器管理中的对换功能。
    1. 将暂时不运行的进程调入外存等待（挂起态）
    2. 把外存上具备运行条件的就绪进程重新调入内存，并修改状态为就绪态，挂在就绪队列中。
  2. 目的：提高内存利用率和系统吞吐量。
3. 低级调度（进程调度）：从就绪队列中挑选一个进程分配处理机。

调度目标

调度算法的评价标准有如下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级别。
- 上下文切换的流程：
  1. 挂起一个进程，保存CPU上下文，更新PCB。
  2. 将进程PCB移入到就绪队列/阻塞队列。
  3. 选择一个进程，更新其PCB。
  4. 跳到新进程的PC位置运行。
  5. 恢复上下文
模式切换
- 两状态：
  - 内核态：也叫做管态和系统态。
  - 用户态：也叫做目态。用户程序只能运行在目态。
- 描述：用户态和内核态之间的切换。可能还在同一个进程中。
- 关系：上下文切换只能发生在内核态

同步与互斥

基本概念

临界资源：多进程共享的资源中，仅允许一个进程使用的资源。
- 例如：变量、数据、打印机
临界区：访问临界资源的那段代码，称之为临界区。
同步：协调工作次序而等待、传递信息所产生的直接制约关系。
互斥：间接制约关系。

同步机制遵循的原则

空闲让进：临界区空闲时，进程可以进入。
忙则等待：已有进程进入临界区，其它进程必须等待。
有限等待：请求访问的进程，有限时间内要能够进入临界区。
让权等待：不能进入临界区时，要释放处理机，防止忙等。

实现临界区互斥的方法

硬件实现方法：

中断屏蔽法：进入临界区前关中断，但是效率很会很低，而且把这个权利给用户不明智。
硬件指令法：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资源。
破坏请求并保持：预先静态分配法，进程一次性申请所有资源，如果资源不够先不给运行。
1. 举例：哲学家就餐问题中一次性分配两只筷子。
破坏循环等待：顺序资源分配法。限制了新类型设备的添加，用户编程也麻烦。

死锁避免：银行家算法

死锁避免是在资源的动态分配下功夫，防止系统进入不安全状态。

系统安全状态

安全序列：系统按照某种进程推进顺序为每个进程分配资源，直到满足每个进程对资源的最大需求，使得每个进程都可以顺利完成。
- 我们可以将安全序列类比为借贷和还贷的过程，这一点王道书上讲的不错。
不安全状态：无法找到一个安全序列。
- 不安全状态可能发生死锁，只要处于安全状态就可以避免进入死锁。
- 避免死锁的本质是不进入不安全状态。

银行家算法

思想：
- OS视作银行家，资源就是资金，进程请求分配资源就是贷款。
- 进程运行前先声明最大需求量，如果进程执行中申请资源，OS会测试该进程已占用资源数和本次申请资源数之和，是否超过了最大需求量。如果超过了就不分配。
- 不超过就测试库存能否满足该进程的需要的最大资源量，如果满足就分配，如果不满足就延迟分配。
概念：
- 需求矩阵 = 最大需求矩阵 - 分配矩阵
- 剩余资源数向量
步骤：
- 根据max矩阵和allocation矩阵计算出Need矩阵。
- 将Work向量和Need矩阵逐行对比，找到一个全部维度都比work向量小的行。
- 此时我们可以选择这行，回收其资源，给各元素加上allocation矩阵中对应行。而这一行的下表就可以添加到安全序列中去。
- 重新这个过程，直到得到一个安全序列。

死锁检测和解除

资源分配图

死锁定理

在资源分配图中找到既不阻塞又不孤立的进程，消去它所有的请求边和分配边，使它成为孤立的节点。
释放的资源可以唤醒某些阻塞的进程，继续消去，如果图中边能完全消去，则为可完全简化。

死锁定理：死锁当且仅当资源分配图不可简化。

死锁解除

资源剥夺法：挂起死锁进程，抢占其资源。
撤销进程法：强制撤销某些进程并抢占其资源。
进程回退法：回退到足以避免死锁的地步。