第二章-进程管理
2.1.1 进程
进程是程序的一次执行过程，是系统资源分配和调度的基本单位
PCB：进程控制块，描述进程信息和状态。创建进程即创建PCB，是进程存在的唯一标志
进程的状态
创建态：申请空白PCB，写入控制管理进程的信息，分配资源。进入就绪态
就绪态：进程获得除了CPU以外的一切资源，进入就绪队列
运行态：进程在CPU上运行。一旦时间片到了或者有更高优先级的进程，就回到就绪态；缺少资源，主动进入阻塞态
阻塞态（等待态）：进程缺少非CPU的资源或等待io，暂停运行。满足条件后，被动进入就绪态
结束态：回收资源
闲逛进程idle：当没有其他就绪态进程时，运行闲逛进程，不访存
进程的控制
进程的状态转换，使用原语
创建：新建PCB，分配资源，加入就绪队列
终止：正常结束、异常结束、kill
阻塞：PCB加入阻塞队列；
唤醒：PCB从阻塞队列到就绪队列
进程切换：保存上下文，将PCB放入队列，选择另一进程的PCB，更新页表等内存管理数据结构，恢复上下文
父进程和子进程的关系
父进程终止，子进程有两种选择：1.终止；2.子进程被init进程领养
子进程终止，资源归还父进程
父进程和子进程可以共享部分资源，不能同时使用临界资源
父进程能给子进程分配虚拟地址空间，但不共享虚拟地址空间
进程的组织
一个进程由pcb，程序段和数据段三部分构成
PCB的内容
- 进程号
- 进程状态，优先级
- 进程队列指针
- 程序和数据地址
- CPU现场保护区
PCB的组织方式：
- 链式：按照进程状态分成多个队列，每个队列里PCB相连
- 索引方式：索引表
程序段：进入CPU的程序代码段
数据段：包括程序原始数据和执行时产生的结果
进程的通信
低级通信：低级通信指的就是通过PV操作控制信号量这个动作本身。只能传输少量信息，通常用于通知事件发生。
高级通信：用来传输大量数据
共享存储：两进程独立的虚拟地址空间映射到一块相同的物理地址空间，使用同步互斥工具（PV）进行读写控制
- 低级方式：基于数据结构的共享
- 高级方式：基于存储区的共享
消息传递：内核中存在若干消息队列，由标识符ID标记。写进程可以向队列中添加消息，读进程可以读取消息。消息是格式化的：[消息头|消息体]
- 直接通信：直接把消息挂在接收进程的消息缓冲队列
- 间接：有中间实体转发（信箱）
管道通信：管道是内存中一个特殊的pipe文件，也是一个固定大小的缓冲区，大小一般为内存中的一页4KB。半双工通信，同一时刻只能单向。
管道的同步互斥：管道写满时，写进程的write系统调用被阻塞，读进程才能读取；管道为空时，读进程的read调用被阻塞，写进程才能写
socket通信
2.1.2 线程
进程一旦阻塞，整个进程就会挂起，即使里面有部分函数不依赖于等待的资源也不能执行。于是引入线程，作为CPU调度的基本单位，一个进程分成多个线程。线程的本质就是函数的执行
1.线程的组织与控制
线程的状态：运行态，就绪态，阻塞态
每个线程有自己的线程控制块TCB：包括
- 线程标识符
- 寄存器值：PC，状态寄存器，通用寄存器
- 线程运行状态
- 优先级
- 线程专有存储区：线程切换时保存现场
- 堆栈指针：过程调用时保存局部变量和返回地址
线程的创建，终止
- 同一进程的所有线程共享进程的堆、静态变量、全局变量、文件，可直接通信，切换开销小
- 每个线程有自己的栈空间（存局部变量），局部变量不能共享，也不能共享线程专有的堆栈指针
2.线程的实现方式
用户级线程：
- 存在在用户空间中
- 应用程序通过线程库来管理用户级线程，线程库提供线程函数接口
- 操作系统内核意识不到线程的存在，所以只能仍然以进程为单位分配CPU，不能利用多核CPU。用户级线程切换无需进入内核态
一个最简单的线程库，可以实现并发。
while(true){
if(i==0)视频聊天;
if(i==1)文字聊天;
if(i==2)文件传输;
i=(i+1)%3;
}
并且可见，一个用户线程被阻塞，其余的都会被阻塞
内核级线程：
- 内核管理内核级线程
- 线程控制块组成的线程表在内核空间中
- 每个内核级线程对应用户空间的一个用户级线程
- 可以使用多核CPU并行执行
- 缺点是线程切换时，需要用户态和内核态之间的切换，系统开销大
总结：内核级线程是CPU调度的基本单位
3.多线程模型
多对一模型：一个内核级线程对应多个用户级线程。一个线程被阻塞，整个进程被阻塞。
一对一：一个内核级线程对应一个用户级线程。一个线程被阻塞，其他的继续执行。操作系统给每个用户线程一个线程控制块
多对多：用户级线程数>=内核级线程数
线程池
线程池是一种多线程处理形式，提前维护多个线程，避免了处理短时间任务时创建销毁线程的代价
协程
过多的线程会导致内存不够用，并且线程切换会有大量时间开销
协程本质上是代码块的相互切换执行，是线程内部的分时复用，一个线程包含多个协程。协程也有自己的栈，一般几十KB
2.2 处理机调度
调度程序通过调度算法从就绪队列选择一个进程执行，并决定时间片大小
调度的三个层次：
（1）作业调度：从外存挑选作业到内存
（2）进程调度：就绪队列-》运行
（3）中级调度：将暂时不运行的程序挂起，调出内存到外存
调度的时机
不能进程调度的情况：
- 处理中断过程中
- 进程在os内核程序临界区中（不是普通的临界区！！！）
- 在屏蔽中断的原子操作过程中
能调度的时机
- 发生调度条件，当前进程无法进行下去
- 中断处理结束后
进程调度方式
抢占方式：一个进程执行时，有更重要的进程来，立即暂停进程
非抢占方式：继续执行，直到结束或进入阻塞态才会调度
典型的调度算法
先来先服务FCFS：每次从就绪队列中选择最先进入队列的进程。适合CPU密集型，不适合io密集型，对短进程不利
短作业优先SJF
优先级调度：静态优先级（创建进程时确定），动态（能够调整优先级）
高响应比优先调度：
综合了短作业优先（服务时间越短响应比越高），避免了饥饿现象（等待时间越长响应比越高）
时间片轮转调度：时间片用完后，必须释放CPU给下一个进程，适用于分时系统，不会导致饥饿现象
多级反馈队列调度：设置多个优先级不同的就绪队列，优先级越高时间片越小。
新进程先放入第一级队列，若时间片用完时未完成，则进入第二级队列，第一级为空时才能运行第二列。不同用户均能满意
多级队列调度：按进程类型设置多个队列
例题：P64(18)，画甘特图，纵轴是各个进程的编号，横轴是时间，只要是在运行就画实线。
2.3 进程同步互斥
进程并发执行的异步性：并发的进程速度不可预知
临界资源：一次仅允许一个进程使用的资源
访问临界资源的过程分为：
- 进入区：检查能否使用临界资源，若可则加锁
- 临界区：访问临界资源的一段代码
- 退出区：解锁
- 剩余区：代码其余部分
同步：各进程必须有一个执行顺序，产生直接制约关系
互斥：间接制约关系，一个退出临界区另一个才能执行
1.互斥的四个原则
- 空闲让进：空闲资源允许进程访问
- 忙则等待：两个进程不能同时进入临界区
- 有限等待：进程等待进入临界区的时间有限，保证不会饥饿
- 让权等待：当进程无法进入临界区时，应立即释放CPU资源，而不是忙等（一直while(true)）。让权等待原则不必须遵循
2.硬件和软件实现进程互斥
1.软件实现
（1）单标志法：turn标志，使用完让给对方。违反“空闲让进”，即一个进程不想进入临界区，另一个进程也进入不了
（2）双标志法先检查：先检查对方是否想进入，再上锁。可能会二者都进入临界区
（3）双标志法后检查：先上锁，再检查。二者都无法进入临界区
以上问题的关键在于上锁和检查两个操作被分隔开了
（4）Peterson法：
Pi(){
flag[i]=true;turn=j;//表明自己想进入，又表示可以让给对方
while(flag[j]&&turn==j);
临界区;
flag[i]=false;
}
Pj(){
flag[j]=true;turn=i;
while(flag[i]&&turn==i);
临界区;
flag[j]=false;
}
- 先表明自己想进入，又表示可以让给对方。如果对方也想进入，且自己是最后谦让的，那么就真的让给对方，自己循环等待。
- 可以解决单、双标志法的问题，实现临界区互斥，但仍不满足让权等待，会忙等
- 没有饥饿问题
2.硬件实现
（1）中断屏蔽法：一个进程想访问临界区时，屏蔽中断，禁止切换其他进程。缺点是只能屏蔽一个CPU的中断，多核时其他CPU运行的进程可以访问临界区
（2）TSL指令（test and set）：使用原子操作，使得上锁和检查两个操作不可分割。缺点：不满足让权等待，会忙等
（3）swap指令：和tsl逻辑相同
3.信号量，PV操作
信号量S（semaphore），使用wait和signal两种原语对信号量进行操作，分别简写为荷兰语的P和V
int S=1;
wait(S);//P：先检查后上锁（因为是原语所以不可分割）
使用资源;
signal(S);//V：释放资源
（1）整型信号量：S是一个整数，代表资源数量。不满足让权等待原则，仍需要忙等
wait(S){//新进程到来
while(S<=0);
S--;
}
signal(S){
S++;
}
（2）记录型信号量：信号量S记录资源数量，同时维护一个阻塞队列
当进程申请不到资源时，不会忙等，而是加入阻塞队列中，当有资源被释放时，会从阻塞队列中唤醒一个进程。满足了让权等待原则
S的绝对值就是当前被阻塞的进程数
每当一个进程被阻塞，S的值-1；每当V操作一次，S的值+1，一个进程从阻塞队列进入就绪队列
typedef struct{
int value;
struct process *L;
}semaphore;
semaphore S;
S.value=1;
wait(S){
S.value--;
if(S.value<0){
当前进程加入阻塞队列S.L
block(S.L);//阻塞进程
}
}
signal(S){
S.value++;
if(S.value<=0){
从阻塞队列中移出一个进程P
wakeup(P);//唤醒进程P，阻塞态到就绪态
}
}
信号量实现同步、互斥
同步：将信号量初始化为0。希望P1的代码y在P2的x之后执行，在y前面检查是否有资源，x完成后释放资源
semaphore mutex=0;
P1(){
x;
V(mutex);
}
P2(){
P(mutex);
y;
}
互斥：信号量初始为1，用P和V操作夹紧临界区
semaphore mutex=1;
P1(){
P(mutex);
P1进入临界区;
V(mutex);
}
P2(){
P(mutex);
P2进入临界区;
V(mutex);
}
信号量实现同步关系
对有向无环图（节点是进程）的每条边都设置一个信号量
对于每个进程，首先检查前驱节点（P），进行操作，最后释放后继节点（V）。
4.管程和条件变量
管程：其实就是把同步互斥操作封装起来，成为一个类，每次只需要直接通过这个类的过程（函数）即可。
互斥由编译器负责，同步需要提前设置条件变量
condition full,empty;
int count=0;
void insert(item){
if(count==n){
wait(full);
}
count++;
insert_item(item);
if(count==1){
signal(empty);
}
}
item remove(){
if(count==0){
//当没有产品时不能remove，因此wait函数将调用wait操作的消费者进程加入条件变量empty的阻塞队列中
wait(empty);
}
count--;
if(count==n-1){
signal(full);
}
return remove_item();
}
producer(){
while(1){
item=生产一个产品;
insert(item);
}
}
consumer(){
while(1){
item=remove();
消费item;
}
}
例如上面的代码，已经写好ProducerConsumer类，由编译器保证同时只能有一个进程使用类里面的insert或remove函数，实现互斥。（java的synchronize关键字）生产者和消费者直接调用函数即可
对于同步，则采用wait和signal函数（即P和V）来实现对条件变量empty和full的同步访问。与信号量不同的是，条件变量没有数值
5.经典同步互斥问题
生产者-消费者问题
缓冲区内有n个缓冲单元
两个同步关系：
缓冲区没满，生产者才能将数据放入缓冲区。设置同步信号量empty，表示空的缓冲单元个数，初始为n
缓冲区不空，消费者才能取走数据。设置同步信号量full，表示满的缓冲单元个数，初始为0
注：并非缓冲区全空，生产者才能生产
一个互斥关系：
- 任何两个进程不能同时访问缓冲区。设置互斥信号量mutex
不能改变P(empty)和P(mutex)的顺序，因为先检查缓冲区没满，才能继续上锁生产。否则当缓冲区满了，生产者已经上锁并且被阻塞（卡在empty），消费者也被阻塞（卡在mutex），造成死锁
semaphore mutex=1;//缓冲区互斥锁
semaphore empty=n;//空的缓冲单元数量
semaphore full=0;//满的缓冲单元数量
producer(){//生产者
while(1){
生产数据；
P(empty);//检查是否有空的缓冲单元数，若有，则空缓冲单元-1
P(mutex);
将数据放入缓冲区；
V(mutex);
V(full);//满缓冲区+1
}
}
consumer(){//消费者
while(1){
P(full);//检查满的缓冲单元数量，若有，则满缓冲单元-1
P(mutex);
取走一个数据；
V(mutex);
V(empty);//空缓冲区+1
消费数据；
}
}
读者-写者问题
读者和写者地位不同。没有同步关系
一个写进程和其他进程互斥：信号量rw实现
（1）读进程优先法
count：记录读者数量
mutex：保证对count的检查和count++两个操作不可分割
rw:一个写进程和其他进程互斥
第一个到来的读者进行rw上锁，最后一个读者进行rw解锁
int count=0;
semaphore mutex=1;
semaphore rw=1;
writer(){
while(1){
P(rw);
writing;
V(rw);
}
}
reader(){
while(1){
P(mutex);
if(count==0){//第一个读者负责上锁
P(rw);
}
count++;
V(mutex);
reading;
P(mutex);
count--;
if(count==0){//没有连续的读者了，才能解锁
V(rw);
}
V(mutex);
}
}
（2）读写公平法
信号量w保证到来的不同进程进入一个阻塞队列，先进先出，不会出现读进程后来但是优先于写进程的情况，保证读写公平
如果读者在写者前到来，此时读者在reading，写者会卡在P(rw)
如果写者在读者前到来，此时写者在writing，读者被卡在P(w)
int count=0;
semaphore mutex=1;
semaphore rw=1;
semaphore w=1;
writer(){
while(1){
P(w);
P(rw);
writing;//此时读者或其他写者被卡在P(w);
V(rw);
V(w);
}
}
reader(){
while(1){
P(w);
P(mutex);
if(count==0){
P(rw);
}
count++;
V(mutex);
V(w);
reading;//此时写者被卡在P(rw);其他读者则跳过P(rw)也访问临界区
P(mutex);
count--;
if(count==0){
V(rw);
}
V(mutex);
}
}
哲学家就餐问题
n个哲学家围坐，中间n根筷子，拿起两根才能进餐。专门解决临界资源数量>1的问题
三种方法防止死锁
- 至多允许n-1个人同时进餐
- 奇数号哲学家先拿左边筷子再拿右边，偶数号相反，这样避免了一些人占有一只筷子再等待另一只
- 仅当左右筷子都可用时才能拿起筷子
//方法一
semaphore chopstick[n];
semaphore mutex=n-1;//至多允许n-1个人同时进餐
for(int i=0;i<n;++i){
chopstick[i]=1;
}
Pi(){
while(1){
思考；
P(mutex);
P(chopstick[i]);//左手的筷子
P(chopstick[(i+1)%n]);//右手的筷子
就餐；
V(chopstick[i]);
V(chopstick[(i+1)%n]);
V(mutex);
}
}
//方法三
semaphore chopstick[n];
semaphore mutex=1;//拿起左右筷子的原子锁
for(int i=0;i<n;++i){
chopstick[i]=1;
}
Pi(){
while(1){
思考；
P(mutex);
P(chopstick[i]);//左手的筷子
P(chopstick[(i+1)%n]);//右手的筷子
V(mutex);
就餐；
V(chopstick[i]);
V(chopstick[(i+1)%n]);
}
}
利用PV操作解题
先分析同步互斥关系，几个关系几个信号量。对于互斥，用PV夹紧互斥行为；对于同步，在a进程末尾加V，在b进程开始加P。
两个同步关系，一个互斥关系，需要三个信号量。
初始有几个资源，信号量就是初始化为几
2.4 死锁
多个进程因竞争资源造成相互等待。（区分：饥饿只是一个进程；死循环不是操作系统原因）
死锁产生的四个必要条件
- 互斥条件：一段时间内资源只能被一个进程占有
- 不剥夺条件：资源只能被主动释放，不能被抢夺
- 请求并保持条件：进程一边保持资源不放，一边请求新的资源
- 循环等待条件：存在循环等待链
死锁预防：破坏四个条件
- 破坏互斥条件：互斥资源转为共享
- 破坏不剥夺条件：必须释放；强行剥夺
- 破坏请求并保持条件：开始一次性申请全部资源
- 破坏循环等待条件：顺序资源分配法，把资源编号，拥有小编号才能申请大编号
死锁预防不改变进程之间的关系
死锁避免：银行家算法
事先计算本次分配的安全性（需要知道资源需求），避免进入不安全状态。
银行家算法用来试探分配（而不是限制顺序），避免进入死锁状态，但无法判断当前是否处于死锁状态
安全状态：进程推进的一个序列，使得可以顺序完成。（例如先让P2执行，完成后归还资源，再让其他执行。）进入安全状态一定不会发生死锁，不安全状态不一定死锁
银行家算法：现在已知每个进程对资源的最大需求量，已分配的资源量。
如果当前剩余可用资源>=一个进程的最大需求量-已分配资源量，则可以把该进程加入安全序列，然后当前剩余可用资源+=该进程已分配的资源量。进行迭代查询
死锁检测：画资源分配图
请求边：进程节点->资源节点：申请一个资源
分配边：资源节点->进程节点：已经分配了资源
死锁检测需要基于死锁定理：
如果某个进程申请各个资源数<=剩余资源数，则删掉它相连的所有边，称为孤立节点。如果最后所有点都是孤立的，则称图是可完全简化的，一定不会死锁；否则会发生死锁
死锁解除
资源剥夺法：挂起死锁进程，抢占死锁进程资源；
撤销进程法：强制撤销死锁进程
进程回退法：进程回退到无死锁时
总结
死锁预防的破坏循环等待条件会限制进程申请资源的顺序
死锁避免（银行家算法）需要每个进程运行所需资源总量信息，死锁检测并不关心总量
死锁检测（死锁定理）会给可能导致死锁的进程分配资源，死锁避免不会
计算题
求不会发生死锁的最小资源数：sum{每个进程的最大需求量-1}+1