博客原文：uestcwxy.love/2023/06/15/…
进程管理
操作系统的进程管理是整个操作系统管理中的核心，它包含了进程的调度、协调以及进程通信。
进程和线程的概念 、比较
典型的进程定义有：
（1）进程是程序的一次执行。
（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
（3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
线程是进程的一个实体，是独立运行和独立调度的基本单位（CPU上真正运行的是线程）。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈)，但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
对比：
线程只拥有少量在运行中必不可少的资源。
进程占用资源多，线程占用资源少，使用灵活。
线程不能脱离进程而存在，线程的层次关系，执行顺序并不明显，会增加程序的复杂度。
没有通过代码显示创建线程的进程，可以看成是只有一个线程的进程。
进程是资源分配的基本单位，线程是程序执行的基本单位
进程拥有自己的资源空间，而线程与CPU资源分配无关，多个线程共享同一进程内的资源，使用相同的地址空间。
一个进程可以包含若干个线程。
前趋图
进程的基本状态及转换
进程的三种基本状态
就绪状态(Ready)：当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，就可以立即运行，进程这时的状态称为就绪状态。在一个系统中可能多个进程处于就绪状态，通常将它们排成一个队列，称为就绪队列。
执行状态(Running)：进程已获得CPU，其程序正在执行。
阻塞状态(Blocked)：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。
进程五种状态及转换模型
◼就绪：准备执行
◼执行：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）
◼阻塞：等待某事件发生才能执行，如等待I/O完成等
◼新建：进程已经创建，但未被OS接纳为可执行进程，并且程序还在辅存，PCB在内存
◼终止：因停止或取消，被OS从执行状态释放
状态转换
① 空 → 新状态 新创建的进程首先处于新状态。
② 新状态 → 就绪状态 当系统允许增加就绪进程时，操作系统接纳新建状态进程，将它变为就绪状态，插入就绪队列中。
③ 就绪状态 → 执行状态 当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行。
④ 执行状态 → 终止状态 执行状态的进程执行完毕，或出现诸如访问地址越界、非法指令等错误，而被异常结束，则进程从执行状态转换为终止状态。
⑤ 执行状态 → 就绪状态 分时系统中，时间片用完，或优先级高的进程到来，将中断较低优先级进程的执行。进程从执行状态转变为就绪状态，等待下一次调度。
⑥ 执行状态 → 阻塞状态 执行进程需要等待某事件发生。通常，会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待I/O操作、等待另一进程与之通信等事件而阻塞。
⑦ 阻塞状态 → 就绪状态 当阻塞进程等待的事件发生，就转换为就绪状态。进入就绪队列排队，等待被调度执行。
多个进程竞争内存资源
◼内存资源紧张
◼无就绪进程，处理机空闲：I/O的速度比处理机的速度慢得多，可能出现全部进程阻塞,等待I/O
解决办法
◼采用交换技术：换出一部分进程到外存，以腾出内存空间（对换）
◼采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）
使执行的进程暂停执行、静止下来。我们把这种静止状态称为挂起状态（由活动到静止，由内存到外存）。
挂起与阻塞
区分两个概念：
进程是否等待事件，阻塞与否? 进程是否被换出内存，挂起与否？
４种状态组合
就绪：进程在内存，准备执行
阻塞：进程在内存，等待事件
就绪/挂起（静止就绪）：进程在外存，只要调入内存即可执行
阻塞/挂起（静止阻塞）：进程在外存，等待事件
若进程处于阻塞状态，当引起阻塞的条件被解除时，进程状态应变为运行状态。(×)
① 进程由程序和数据两部分组成。（× ）
② 程序的封闭性是指该程序不允许某些进程调用。（ ×）
③ 操作系统中，进程是资源分配 、调度和管理的最小独立单位 ， 操作系统的各种活动都与进程有关。
PCB的作用
为使程序（含数据）能独立运行，应为之配置一进程控制块，即PCB(Process Control Block)； 而由程序段、相关的数据段和PCB三部分便构成了进程实体。所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB。
进程控制块的作用
1） 作为独立运行基本单位的标志；
2） 能实现间断性运行方式；
3） 提供进程管理所需要的信息；
4） 提供进程调度所需要的信息；
5） 实现与其他进程的同步与通信。
PCB(process control block)常驻内存，是进程存在的唯一标志；
进程控制块中的信息
1）进程标识符
2）处理机状态
3）进程调度信息
4）进程控制信息
PCB的组织方式
1）线性方式
将系统中的所有PCB组织在一张线性表中，将该表的首地址存放在一个专用区域中。
2）链接方式
把具有同一状态的PCB，用其中的链接字链接成一个队列，排成就绪队列，若干个阻塞队列以及空白队列。
3）索引方式
系统根据所有进程的状态建立几张索引表。
进程控制的原语操作
原语
是由若干条指令组成的，是用于完成一定功能的一个过程。
➢ 原语是原子操作：一个操作中的所有动作要么全做，要么全不做。（操作不可中断）
➢ 原子操作在系统态下执行，常驻内存。
➢ 原语的作用是为了实现进程的通信和控制，系统对进程的控制如不使用原语会造成其状态的不确定性，达不到进程控制的目的。
进程创建
调用进程创建原语Creat（ ）按下述步骤创建一个新进程：
（1）申请空白PCB。
（2）为新进程分配资源。
（3）初始化进程控制块。包括：①初始化标识信息。②初始化处理机状态信息。③初始化处理机控制信息。
（4）将新进程插入就绪队列。
进程阻塞过程
1)正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block( )把自己阻塞。
2)把进程控制块中的现行状态由“执行”改为“阻塞”，并将PCB插入阻塞队列。
3)转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。
进程的唤醒
当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup（ ），将等待该事件的进程唤醒。
1）首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪。
2）然后再将该PCB插入到就绪队列中。
Block原语和Wakeup是一对作用相反的原语；有前者就必定由后者，否则：被阻塞的进程将会因不能被唤醒而长期处于阻塞状态，从而无法继续运行。
进程的挂起
当出现了引起进程挂起的事件时，系统将利用挂起原语suspend（ ）将指定进程进程挂起。
挂起原语的执行过程是：
•首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；
•对于活动阻塞状态的进程，则将之改为静止阻塞状态。
进程的激活过程
1）当发生激活进程的事件时，则可将在外存上处于静止就绪状态的进程换入内存。
2）系统利用激活原语active（ ）将指定进程激活:
▪激活原语先将进程从外存调入内存，检查该进程的现行状态;
▪若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。
-
原语是指操作系统中的初始化程序。（× ）
-
一个进程可以由系统创建，或者由(父进程 )用创建原语创建。被创建的进程开始处于等待状态。在条件成熟时，采用(调度 ) 原语为它们分配除（处理机）以外的所需资源，并被排列到(就绪 )队列中。
-
进程运行过程中，因为(缺乏资源 )、等待I/O操作等事件发生时，通过( 阻塞)原语将它撤下，排入( 等待)队列，并引起新的( 进程调度)。
进程同步
一次仅允许一个进程访问的资源为临界资源。
每个进程中访问临界资源的那段代码称为临界区
进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。
同步机制应遵循的规则
1)空闲让进
2)忙则等待
3)有限等待
4)让权等待
并发进程可以同时进入临界区，交替访问临界资源。（×）
解决临界区（互斥）问题的几类方法
（1）硬件同步机制
（2）信号量机制
（3）管程机制
信号量机制
1）整型信号量
2）记录型信号量
3）AND型信号量
4）信号量集
整型信号量
定义为一个整型量 ,仅能通过两个标准的原子操作wait（S）和signal（S）来访问。又称为P、V操作。
1）P、V操作(即wait(s)和signal(s))为原语操作——不可中断
2）整型信号量的使用：
① 必须置一次且只能置一次初值，并且初值不能为负数。
② 只能执行P、V操作。
③必须成对使用P、V操作：P操作遗漏则不能保证互斥访问，V操作遗漏则不能在使用临界资源之后将其释放；P，V次序不能错误、重复或遗漏。
3）整型信号量的缺点：未遵循同步机制的“让权等待”一直判断是否处理完，占用处理机。（使程序处于忙等状态，这意味着当一个进程在等待信号量时，它会不断地检查信号量的值，而不是释放CPU资源，这会浪费大量的CPU时间。）
记录型信号量
记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。
记录型信号量的wait（S）操作（ 即P(S) ）
procedure wait(S)
var S: semaphore;
begin
S.value:＝S.value-1;
if S.value＜0 then block(S.L);
end
S.value＜0，该类资源已经分配完毕，进程必须放弃处理机，自我阻塞。
记录型信号量采用了“让权等待”策略，当一个进程在等待信号量时，它会被阻塞并释放CPU资源，直到被唤醒这样就避免了忙等现象。
记录型信号量的signal（S）操作（ 即V(S) ）
procedure signal（S）
var S:semaphore;
begin
S.value:＝S.value+1;
if S.value≤0 then wakeup(S.L);
end
S.value>0表示有S.value个资源可用;S.value=0表示无资源可用。
S.value≤0 ，在信号量链表中，仍有等待该资源的进程被阻塞。
记录型信号量: 若S.value<0，则| S.value|表示S等待队列中的进程个数。
AND型信号量
AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全都地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。 在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。
Swait（S1，S2，···，Sn ） {
while（true）{
if（ S1≥1 and S2≥1 and…and Sn≥1 ）{
for (i = 1 ; i<= n; i++){
Si = Si – 1;
}
break;
}else{
调用进程进入第一个小于1的信号量的等待队列Sj.queue;阻塞调用进程;
}
}
Ssignal（S1，S2，···，Sn）{
for( i = 1; i<= n; i++ ){
Si = Si+1;
for (each process P waiting in Si.queue)
从等待队列Si.queue中取出进程P放入就绪队列;
}
}
信号量集
一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请
Swait（S1，t1，d1，…，Sn，tn，dn）（满足ti≥ di）
if( S1 ≥t1 &…& Sn≥tn){
for( i =1; i<=n; i++){
Si ＝Si － di;
}
}else{
调用进程进入第一个小于1的信号量的等待队列Sj.queue;阻塞调用进程;
}//end if
}//end Swait
tn为资源下限值，dn为需求量
Ssignal（S1，d1，···，Sn，dn）{
for( i =1; i<= n; i++){
Si = Si + di；
for (each process P waiting in Si.queue)
从等待队列Si.queue中取出进程P放入就绪队列;
}
}
信号量应用
利用信号量实现进程互斥
利用信号量实现前趋关系
p1( ){ S1； signal（a）；signal（b）；}
p2( ){ wait(a); S2；signal（c）；signal（d）; }
p3( ){ wait（b）；S3；signal（e）；}
p4( ){ wait（c）；S4；signal（f）；}
p5( ){ wait（d）；S5；signal（g）；}
p6( ){ wait（e）；wait（f）；wait（g）；S6；}
void main( ){
semaphore a,b,c,d,e,f,g;
a.value=b.value=c.value=0;
d.value=e.value=f.value=g.value=0;
cobegin
p1( ); p2( ); p3( ); p4( ); p5( ); p6( );
coend;
}
信号量的物理意义是当信号量大于零时表示（资源的数目 ）；当信号量小于零时，其绝对值为（ 等待该资源的进程数目） 。
有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号
量值的变化范围是（ [1-m，1]）。
经典进程同步问题
◼生产者——消费者问题
◼哲学家进餐问题
◼读者——写者问题
生产者——消费者问题
生产者和消费者进程共享一个大小固定的缓冲区，其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个消费者从缓冲区中取数据。
◆假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。
◆分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取数据的存储单元
生产者－消费者之间满足的条件：
◆ 消费者想接收数据时，有界缓冲区中至少有一个单元是满的（同步问题）
◆ 生产者想发送数据时，有界缓冲区中至少有一个单元是空的（同步问题）
◆ 有界缓冲区是临界资源（互斥问题）
full=0; 表示当前队列中已有的数据个数
empty=n; 表示当前队列中还可以放的数据个数
利用记录型信号量解决生产者一消费者问题
int in=0, out=0;
item buffer [n];
semaphore mutex=1, empty=n, full=0;
void producer();
void consumer();
void main(){
cobegin
producer(); consumer();
coend
}
void producer( ){
do{
…
Produce an item in nextp;
…
wait(empty);
wait(mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
signal(mutex);
signal(full);
}while(TRUE);
}
void consumer{
do{
wait(full);
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
Consumer the item in nextc;
……
}while(TRUE);
}
wait(empty)是一个同步P操作，因为它用于同步生产者和消费者之间的操作。当缓冲区已满时，生产者需要等待消费者从缓冲区中取出一个产品，才能继续向缓冲区中添加新的产品。wait(mutex)是一个互斥P操作，因为它用于保护对共享资源（即缓冲区）的互斥访问。当生产者或消费者需要访问缓冲区时，它们必须先获得对缓冲区的互斥访问权。
① P.V操作必须成对出现，有一个P操作就一定有一个V操作；
② 当为互斥操作时，PV处于同一进程；
③ 当为同步操作时，则PV不在同一进程中出现；
④ 如果P(S1)和P(S2)两个操作在一个进程中，那么P操作的顺序至关重要，一个同步P操作与一个互斥P操作在一起时,同步P操作在互斥P操作之前；
⑤ 两个V操作的顺序无关紧要。
利用AND信号量解决生产者—消费者问题
int in=0, out=0;
item buffer[ n ];
semaphore mutex=1, empty=n, full=0;
void producer( ){
do{
…
produce an item in nextp;
…
Swait(empty, mutex);
buffer[in] = nextp;
in = (in+1) % n;
Ssignal(mutex, full);
}while(TRUE);
} //end producer
void consumer{
do{
Swait(full, mutex);
nextc = buffer[out];
out = (out+1) % n;
Ssignal(mutex, empty);
consumer the item in nextc;
}while(TRUE);
}
哲学家进餐问题
5个哲学家围绕一张圆桌而坐，每个哲学家前面有一碟空心面，由于面很滑，所以要两把筷子才能夹住。相邻两个碟子之间有一把筷子。哲学家只有两种活动，在感觉到饿时，分两次取左边和右边的筷子（不分次序），如果成功的得到两把筷子，就吃饭，吃完后继续思考。
利用记录型信号量解决哲学家进餐问题
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do {
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
// Eat
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
// Think
} while (TRUE);
虽然上述解法可以保证不会有两个相邻的哲学家同时进餐。但却有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子的时候，就会使五个信号量chopstick均为零。当他们在试图去拿右边的筷子，都将因为无筷子可拿而无限期的等待。
解决办法：
- 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
- 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
- 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。
利用AND信号量解决哲学家进餐问题
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do {
// ...
think;
Sswait(chopstick[(i + 1) % 5], chopstick[i]);
// Eat
Ssignal(chopstick[(i + 1) % 5], chopstick[i]);
} while (TRUE);
读者——写者问题
问题描述：对于系统中的共享对象，把只要求读该文件的进程称为“reader进程”，其它进程称为“writer进程”。所谓读者——写者问题，是指保证一个write进程必须与其它进程互斥地访问共享对象的同步问题。
利用记录型信号量解决读者—写者问题
semaphore rmutex=1, wmutex = 1;
int readcount = 0;
void reader() {
do {
wait(rmutex);
if (readcount == 0) then wait(wmutex);
readcount = readcount + 1;
signal(rmutex);
// Perform read operation
wait(rmutex);
readcount = readcount - 1;
if (readcount == 0) then signal(wmutex);
signal(rmutex);
} while (TRUE);
}
void writer() {
do {
wait(wmutex);
// Perform write operation
signal(wmutex);
} while (TRUE);
}
void main() {
cobegin
reader();
writer();
coend
}
信号量集解决读者—写者问题
int RN;
Semaphore L = RN, mx = 1;
// RN标示同时允许多少读进程存在
void reader() {
do {
swait(L, 1, 1);
swait(mx, 1, 0);
// Perform read operation
ssignal(L, 1);
} while (TRUE);
}
void writer() {
do {
swait(mx, 1, 1;L, RN, 0);
// Perform write operation
ssignal(mx, 1);
} while (TRUE);
}
void main() {
cobegin
reader();
writer();
coend
}
课堂练习
有一个理发师，一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师进行理发；如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编一段程序描述他们的行为。
使用三个信号量：
◼ customers用来记录等候理发的顾客数（不包括正在理发的顾客），其初值为0；
◼ barbers记录正在等候顾客的理发师数，其值为0或1；
◼ mutex用于实现共享变量的互斥访问，其初值为1。
◼ 共享变量count，它也用于记录等候的顾客数，它实际上是customers的一个备份，之所以使用count是因为无法读取信号量的当前值。
semaphore customers = 0; // 等候的顾客数
semaphore barbers = 0; // 等候顾客的理发师数
semaphore mutex = 1;
int count = 0; // 等候的顾客数（还没理发）
main() {
cobegin
barbers();
customers();
coend
}
barber() {
while (true) {
p(customers); // 是否有等候的顾客
p(mutex);
count = count - 1; // 顾客数减1
v(barbers); // 理发师开始理发
v(mutex);
理发;
}
}
customer() {
p(mutex);
if (count < n) {
count = count + 1; // 若有空椅子则等候的顾客数加1
v(customers);
v(mutex);
p(barbers);//无理发师,顾客坐着
理发;
} else {
v(mutex); // 无空椅子则离开
}
}
进程通信
进程通信——是指进程之间的信息交换。由于每个进程都有自己独立的地址空间，因此一个进程无法直接访问另一个进程的变量或数据结构。
进程通信的类型
1.共享存储器系统
（1）基于共享数据结构的通信方式。
（2）基于共享存储区的通信方式。
2.消息传递系统
• 是目前的主要通信方式，信息单位：消息（报文）
• 实现：一组通信命令（原语），具有透明性→同步的实现。
实现方式的不同，而分成：
（1）直接通信方式
这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。
系统提供下述两条通信命令（原语）：
Send （Receiver， message）；Receive（Sender， message）；
例：解决生产—消费问题。
do{
…
produce an item in nextp;
…
send(consumer, nextp);
}while(TRUE);
do{
receive( producer, nextc);
…
consumer the item in nextc;
}while(TRUE);
（2）间接通信方式
指进程之间利用信箱的通信方式。发送进程发送给目标进程的消息存放信箱；接收进程则从该信箱中，取出对方发送给自己的消息；消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。系统为信箱通信提供了若干条原语，分别用于信箱的
创建、撤消和消息的发送、接收等。
Send (mailbox, message);Receive (mailbox, message)
3.管道（Pipe）通信
管道：连接一个读进程和一个写进程之间通信的共享文件。
功能：大量的数据发收。
4.信号
在生产者—消费者问题中，如果缺少了signal(full)或signal(empty)，对执行结果将会有何影响？
如果缺少了signal(full)，则消费者进程将无法从缓冲区中取出产品。这是因为消费者进程在每次取出产品之前，都会调用wait(full)来检查缓冲区中是否有产品。如果缺少了signal(full)，则缓冲区中的产品数量将永远为0，消费者进程将一直被阻塞。如果缺少了signal(empty)，则生产者进程将无法向缓冲区中添加新的产品。这是因为生产者进程在每次生产新产品之前，都会调用wait(empty)来检查缓冲区是否有空闲位置。如果缺少了signal(empty)，则缓冲区中的空闲位置数量将永远为0，生产者进程将一直被阻塞。
尝试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore num = 4;
void philosopher(int i) {
while (true) {
wait(num);
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
// 进行进餐操作
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
signal(num);
// 进行思考操作
}
}
试修改下面生产者—消费者问题解法中的错误
void producer() {
do {
// 生成一个项目 nextp
wait(mutex);
wait(full);
buffer[in] = nextp;
signal(mutex);
} while (TRUE);
}
void consumer() {
do {
wait(mutex);
wait(empty);
nextc = buffer[out];
out = (out + 1) % n;
signal(mutex);
// 消费 nextc 项目
} while (TRUE);
}
void producer() {
do {
// 生成一个项目 nextp
wait(empty);
wait(mutex);
buffer[in] = nextp;
in = (in + 1) % n;
signal(mutex);
signal(full);
} while (TRUE);
}
void consumer() {
do {
wait(full);
wait(mutex);
nextc = buffer[out];
out = (out + 1) % n;
signal(mutex);
signal(empty);
// 消费 nextc 项目
} while (TRUE);
}
