第3章 进程之间的并发控制和死锁

1.并发进程的特点

-对资源的共享引起的互斥关系：进程之间本来是相互独立的，但由于共享资源而产生了关系。
-协作完成同一个任务引起的同步关系：一组协作进程要在某些同步点上相互等待发信息后才能继续运行。
-进程之间的前序关系：由于进程之间的互斥同步关系，使得进程之间具有了前序关系，这些关系决定了各个进程创建和终止的时间。

-进程之间的关系
顺序关系、并行关系、一般关系

2.进程之间的低级通信

-进程间的低级通信：通过信号量实现进程之间的互斥和同步关系
-进程间通信问题——IPC问题

2.1 进程之间的互斥

共享资源、临界资源【⼀次仅允许⼀个进程使⽤的系统中共享资源】、临界区【并发进程访问临界资源的那段必须互斥执⾏的程序】
-并发进程进入临界区需要遵循的四个准则
互斥使⽤；让权等待；有空让进；有限等待
-解决进程之间互斥的方法
软件实现方法：共享变量
硬件实现方法：关中断【最简单的⽅法。在进程刚进⼊临界区时，⽴即禁⽌所有中断；在进程要
离开之前再打开中断】、test&set硬件指令
-使用测试和设置硬件指令
所谓变量W：为每个临界资源设置⼀个，以指示其当前状态。W=0，表示资源空闲可⽤；W=1，表示资源已被占⽤
-加锁方法

 Const intn=/*进程数 */
 int w;
 void p(inti){
 while(1){
 while(test&set(w));//加锁
<criticalsection>
 w=0; //开锁
<remaindersection>
 }}

2.2 进程之间的同步

同步的原因：一组进程要合作完成一项任务

2.3 信号量和P、V操作

基本原理：两个或多个进程通过简单的信号进⾏合作，⼀个进程被迫在某⼀位置停⽌，直到它接收到另⼀个进程发来的信号。为了发信号，需要使⽤⼀个称作信号量的特殊变量。
-对信号量S的操作只允许执⾏P、V原语操作；
P操作原语：

//wait(s) ;
 void P (sem &s)
 { s.value = s.value-1; //表示申请⼀个资源（或通过信号量s等消息）
if (s.value < 0)
 { add this process to s.list;
 block( );
 } //资源⽤完，调⽤阻塞原语。“让权等待”
 }

V操作原语：

// signal(s);
 Void V (sem &s) {
 s.value = s.value+1;
 //释放⼀个资源（或通过信号量s发消息） 
if (s.value <= 0) {
 remove a process P from s.list;
 wakeup( );
 }//表示在信号链表中，仍有等待该资源的进程被阻塞。 调⽤唤醒原语。
}

显然，P、V操作的引⼊，克服了加锁test&set(w)操作的忙等现象，提⾼了系统的效率。
阻塞，唤醒
-根据⽤途不同，可以把信号量分为公⽤信号量和私⽤信号量。
-公⽤信号量（互斥信号量）⽤于解决进程之间互斥进⼊临界区。
-私⽤信号量（同步信号量）⽤于解决某⼏个进程之间的同步。

利用信号量实现进程之间的互斥
设置⼀个互斥信号量mutex，初值为1，表示该临界资源空闲。
调⽤P(mutex)申请临界资源。
调⽤V(mutex)释放临界资源。
只需把临界区代码置于P(mutex)和 V(mutex)之间，就可实现临界资源的互斥使⽤了。

操作系统的定义
⽤信号量可以⽅便地解决n个进程互斥地执⾏临界区代码的问题。
信号量的取值范围：+1～ -(n-1)。
信号量值为负时，说明有⼀个进程正在临界区执⾏，其它的正排在信号量等待队列中等待，等待的进程数等于信号量值的绝对值。

生产者和消费者问题
-⽣产者和消费者是相互合作进程关系的⼀种抽象
⽣产者：当进程释放⼀个资源时，可把它看成是该资源的⽣产者；
消费者：当进程申请使⽤⼀个资源时，可把它看成该资源的消费者。

定义：
empty：表示空缓冲区的个数，初值为k；
full：有数据的缓冲区个数，初值为0；
mutex：互斥访问临界区的信号量，初值为1。

int mutex=1, empty=k, full=0, i=0, j=0;
int array[k], x, y;
-⽣产者进程（Producer）：
…
produce a product x;
P(empty); //申请⼀个空缓冲
P(mutex); //申请进⼊缓冲区
array[i] = x; //放产品
i = (i+1)mod k; //修改写指针
V(full); //有数据的缓冲区个数加1
V(mutex); //退出缓冲区
…
-消费者进程（Consumer）：
…
P(full); //申请⼀个产品
P(mutex); //申请进⼊缓冲区
y = array[j]; //取产品
j = (j+1)mod k; //修改读指针
V(empty); //释放1个空缓冲
V(mutex); //退出缓冲区
…

注意P操作的次序
若⽣产者进程中的两个P操作的次序交换：
当缓冲区满时，⽣成者将在P(empty)上等待，但不释放对缓冲区的互斥使⽤权；
此后，消费者欲取产品时，由于申请使⽤缓冲区不成功，它将在P(mutex)上等待；
相互等待就会造成系统发⽣死锁现象。

读者和写者问题
读/写问题：
有⼀个多进程共享的数据区，这个数据区可以是⼀个⽂件或者主存的⼀块空间。有⼀些只读取这个数据区的读进程（reader)和⼀些只往
数据区中写数据的写进程（writer)。此外还必须满⾜以下条件：
多个读进程可以同时读这个数据区；
⼀次只有⼀个写进程可以往数据区中写；
若⼀个写进程正在写，禁⽌任何进程读。
信号量的设置：
写互斥信号量wmutex：
实现读写互斥和写写互斥地访问共享⽂件，初值为1。
计数器readcount：
记录同时读的读者数，初值为0。
读互斥信号量rmutex：
使读者互斥地访问计数器readcount，初值为1。
int wmutex=1, readcount=0, rmutex=1;
Reader:
P(rmutex); //互斥访问
readcount
if readcount==0 then P(wmutex);
readcount++;
V(rmutex);
读⽂件;
P(rmutex);
readcount= readcount-1;
if readcount==0 then V(wmutex);
V(rmutex);
Writer： …
P(wmutex);
写⽂件;
V(wmutex)；
…

理发师问题
⼀个理发师和n把空椅⼦。如果没有顾客，则理发师坐在椅⼦上睡觉，当有⼀个顾客到来时，就唤醒理发师，请求理发；如果理发师正在理发，⼜有顾客到来时，只要有空椅⼦，他就坐下来等待理发。请为理发师和顾客各编写⼀段程序来描述他们的同步问题。

设两个同步信号量：
⽤s1制约理发师，初值为0，表示有0个顾客；
⽤s2制约顾客，表示空椅⼦数，初值为n。
理发师：
P(s1); //等顾客
给顾客理发； V(s1); //增加顾客数
V(s2); //释放椅⼦
顾客：
P(s2); //申请椅⼦
V(s1); //增加顾客数
坐椅⼦上等理发；

哲学家进餐问题
典型的同步问题，是⼀⼤类并发控制问题的例⼦
假设有5个哲学家，花费⼀⽣的时光思考和吃饭。
在桌⼦上放着5⽀筷⼦；
⼀个哲学家要分两次去取其左边和右边的筷⼦；
若得到两⽀筷⼦，就开始吃饭；
吃完放下两⽀筷⼦。

int fork[0]=fork[1]=…=fork[4]=1; //五个互斥信号量
第i个哲学家所执⾏的程序：
do{
P(mutex);
P(fork[i]);
P(fork[(i+1)mod5]);
V(mutex);
吃饭
V(fork[i]);
V(fork[(i+1)mod5]);
} while(1)；

3.管程

管程是关于共享资源的数据结果及一组针对该资源的操作过程所构成的软件模块。
管程保证：一次只有一个进程执行管程中的代码。从而提供互斥机制，保证管程数据的一致性。

-管程的组成：
Monitor monitor-name {
…… //局部于该管程的共享变量的说明
condition …… //条件变量
define ……; //本管程内定义的过程名
use ……; //操作条件变量的同步原语
…… //本管程内定义的各过程（函数体）
}

-用管程解决临界资源的互斥适用
Monitor mutexshow {
boolean busy=false; //临界资源是否可⽤标志
condition nonbusy; //等待队列的条件变量
definerequest, release; //管程中的过程说明
use wait, signal; //引⽤外部模块
}
调⽤wait()的进程会阻塞在条件变量nonbusy的等待队列上；
调⽤signal()会唤醒⼀个阻塞进程，若⽆阻塞进程则signal()不起作⽤。

局限性
管程是编程语言的组成部分，编译器知道它们的特殊性，因此对其操作做出互斥安排。

4.进程的高级通信

低级通信的缺点：P、V操作的适用增加了程序的复杂性；
P、V操作使用不当，易导致死锁；
当程序非正常撤离时，查找只做了P操作而未做V操作的程是很困难的。
-高级通信：
-是指进程采用操作系统提供的多种通信方式来实现通信；
-如消息缓冲、信箱、管道、共享主存区等。
-发送进程和接收进程的消息通信方式：
-阻塞发送：发送进程阻塞，直到消息被接收
-非阻塞发送：发送消息并继续运行
-阻塞接收：接收进程阻塞，直到有消息可用
-非阻塞接收：收到一个有效消息或空消息

4.1 消息缓冲通信

-实现方法：
-系统设置一个消息缓冲池，其中每个缓冲区可以存放一个消息；
-每当进程欲发送消息时，向系统申请一个缓冲区，将消息存入缓冲区，然后把该缓冲区链接到接收进程的消息队列上；
-消息队列通常放在接收进程的进程控制块中；
-属于直接通信方式。
（1）消息缓冲区的类型
struct message_buffer{
xx sender; //发送进程标识符
xx size; //消息长度
xx text; //消息正文
struct message_buffer *next; //指向下一个消息缓冲区的指针
}
（2）PCB中有关通信的数据项描述
struct PCB{
…
mq; //消息队列队⾸指针
mutex; //消息队列互斥信号量
sm; //消息队列同步信号量
…
}
消息队列通常放在进程控制块中。
（3）发送、接收系统调用
send(接收者，被发送消息始址)
receive(发送者，接收区始址)
-发送者先在⾃⼰的地址空间形成⼀个消息发送区，将消息写⼊其中，然后调⽤发送原语；
-发送原语：从系统缓冲区申请⼀个消息缓冲区，将消息从发送区传⼊其中， 然后挂到接收进程的消息队列上；
-接收原语：将消息接收到自己的接收区

-消息缓冲通信*
send(receiver, a){ //发送原语
getbuf(a.size, i)； //据a区消息⻓度来申请⼀系统缓冲区i
i.sender=a.sender;
i.size=a.size;
i.text=a.text; i.next=0;
getid(PCB set, receiver, j); //获得接收进程的内部标识符j
P(j.mutex);
insert(j.mq, i); //将i挂在接收进程j的消息队列mq上(临界资源）
V(j.mutex);
V(j.sm); //消息队列同步信号量sm
}d

receive(b){ //接收原语
j=get caller’s internal name; //内部标识符
P(j.sm); //等消息
P(j. mutex);
remove(j.mq, i); //从⾃⼰的消息缓冲队列mq中摘下第⼀个消息缓冲
区i。
V(j.mutex);
b.sender=i.sender;
b.size=i.size;
b.text=i.text;
}

信箱通信
发送进程将消息发送到中间媒介——信箱，接收进程从中去的消息。
间接通信方式：
-发送原语：send(A,Msg) 将一个消息Msg发送到信箱A
-接收原语：receive(A,Msg) 从信箱A中接收一个消息Msg

管道通信
是指⽤于连接⼀个读进程和⼀个写进程的共享⽂件，⼜称pipe⽂件。OS强制实施互斥。
是通过OS管理的环形缓冲区。先进先出。
命令⽅式的管道通信；程序⽅式的管道通信。

共享存储区
诸进程为了相互交换⼤量数据，申请创建⼀块共享存储区，并将共享存储区映射到各⾃的地址空间，通过读或写共享存储区中的数据来实现通信。

5.死锁

5.1 死锁的定义和产生的必要条件

-资源的特性
-可抢占资源：当资源从占⽤进程剥夺⾛时，对进程不产⽣什么破坏性的影响。如主存、CPU
-不可抢占资源（临界资源）：⼀旦分配，不能强收回，只能由其⾃动释放。如打印机、磁带机。

5.1.1 死锁的定义

⼀组进程是死锁的，是指这⼀组中的每个进程都正在等待该组中的其他进程所占⽤资源时，可能引起的⼀种错误现象。

5.1.2 死锁产生的必要条件

-互斥条件：独占性的资源；
-保持和等待条件：进程因请求资源而阻塞时，对已经获得的资源保持不放；
-不剥夺条件：已分配给进程的资源不能被剥夺，只能有进程自己释放；
-循环等待条件：存在一个进程循环链，链中每个进程都在等待链中的下一个进程所占用的资源。

5.1.3 死锁产生的原因

-系统资源配置不⾜，引起进程竞争资源。
-并发进程请求资源的随机性，包括所请求资源的类别和数量。
-各并发进程在系统中异步向前推进，造成进程推进顺序的不合理性。
产⽣死锁的根本原因：是对独占资源的共享，并发进程的同步关系不当。

5.2 解决死锁的方法

5.2.1 鸵鸟算法

最简单的解决⽅法是鸵⻦算法：把头埋进沙⼦⾥，假装毫⽆问题。
如果死锁平均每5年发⽣⼀次，⽽每个⽉系统都会因硬件故障、编译器错误或者操作系统故障⽽崩溃⼀次，那么⼤多数⼯程师不会花费代价去防⽌系统死锁。

5.2.2 死锁的预防

因产生死锁需四个必要条件。若能破坏其中的一个或几个条件，则不产生死锁。
-破坏互斥条件
-资源的互斥使⽤条件是由资源本⾝性质决定的，不能破坏。
-如果采⽤spooling技术，借助磁盘空间，就可以将⼀台独享设备改造成多台设备，以满⾜多个进程的共享需求。如打印机。
-实际中，不是所有设备都能采⽤spooling技术的。即使采⽤了该技术，由于多个进程竞争磁盘空间，磁盘空间的不⾜，仍可能导致死锁。
-破坏保持和请求条件
-让进程在开始运行前，就获得所需的全部资源。若系统不能满足，则该进程等待。
-属静态分配，资源利用率低。
-许多进程在开始运行之前，不能精确提出所用资源数量。
-破坏非剥夺条件
-当⼀个进程已占有某些资源，⼜申请新的资源⽽得不到满⾜时，则在进⼊阻塞状态前强⾏使其释放已经占有的资源。以后运⾏时，再重新申请。
-显然也不⾏，因为保护进程放弃资源时的现场以及之后的恢复现场，系统要付出很⾼的代价。
-破坏循环等待条件
-将将系统全部资源按类进⾏全局编号排序。进程对资源的请求必须按照资源的序号递增顺序进⾏。这样，就不会出现进程循环等待资源，预防死锁。
-但找到能满足所有进程要求的资源编号是不可能的。

5.3 死锁的避免

基本思想：允许进程动态地申请资源，⼀次申请⼀部分资源。系统在进⾏资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进⼊不安全状态，便将资源分配给进程；否则，进程等待。

银行家算法
-安全状态：是指系统能按某种顺序，来为每个进程分配其所需资源，直⾄最⼤需求，使每个进程都可顺利完成。
银行家算法详情可见视频链接银行家算法

-检查一个状态是否安全：
-检查剩余请求矩阵R是否有⼀⾏，其剩余请求向量⼩于等于系统剩余资源向量A。若不存在这样的⾏系统将会死锁。
-若找到这样⼀⾏，则可以假设它获得所需的资源并运⾏结束，并将其占⽤资源归还系统。
-重复以上两步，直到所有进程都标记为终⽌；或者直到死锁发⽣，出现不安全状态。

5.4 死锁的检测和恢复

-死锁的检测和恢复技术：
-死锁的检测和恢复技术：
-是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。
-死锁的检测——用进程资源图检测死锁
-检查由进程和资源构成的有向图是否包含一个或多个环路，若是，则存在死锁，否则不存在。
资源图格式如图：进程资源图规范,提取码6wgy

死锁的恢复
-故障终止一些进程
-故障终止所有死锁进程——简单。
-一次终止一个死锁进程，直到死锁解除为止。
-资源剥夺
-夺⾛⼀个进程的资源，给另⼀个进程使⽤。
-将⼀死锁进程滚回到获得资源之前的执⾏点。为进程设置执⾏点是指将进程在该点的执⾏状态信息到⼀个⽂件中，便于以后从该执⾏点启动进程执⾏。

习题

1.程序顺序执行的特点。
一次只运行一道程序。具有封闭性、可再现性的特点。
-封闭性：程序在运⾏时独占全机资源，因此，这些资源的状态只由⼀个程序决定和改变，不受外界因素影响。
-可再现性：只要初始条件相同，⽆论程序连续运⾏，还是断断续续地运⾏，程序的执⾏结果不变。

2.何谓进程，进程由哪些部分组成？试述进程的四大特性（动态性、独立性、并发性、结构性）及程和程序的区别。
-进程：又叫任务，是程序的一次执行过程，程序在一个数据集合上顺序执行时发生的活动。
-动态性：进程是程序的一次执行过程，是临时的，有生命期的。
-独立性：进程是系统进⾏资源分配和调度的⼀个独⽴单位。
-并发性：多个进程可在处理机上交替执⾏。
-结构性：系统为每个进程建⽴⼀个进程控制块。
-进程和程序的区别：
-进程是动态的，程序是静态的。
-进程是暂时的，程序是永久的。
-进程包括程序、数据和进程控制块。
-通过多次执⾏，⼀个程序可对应多个进程；通过调⽤关系，⼀个进程可包括多个程序。进程可创建其他进程，⽽程序不能形成新的程序。

3.进程控制块的作用是什么?它主要包括哪几部分内容?
-PCB是进程存在的唯一标识，通常，一个进程的信息包括：
-一个可执行程序(**.exe)
-一个度里的地址空间
-一个执行栈区（子程序调用，系统调用，进程切换）
-打开的文件、申请使用的I/O设备等
-包括如下内容：
-进程标识数: 用于唯一地标识一个进程，通常是一个整数。外部标识符，由用户使用。如：send进程，print进程等。
-进程的状态、调度、存储器管理信息: 调度进程所必需的信息，包括进程状态、优先级、程序在存住地址、在外存的地址等。
-进程使用的资源信息: 分配给进程的I/O设备、正在打开的文件等。 [ ] CPU现场保护信息: 保存进程运行的现场信息。包括: 程序计数器(PC)、程序状态字、通用寄存器、堆栈指针等。
-记账信息: 包括使用CPU时间、帐务等。
-进程之间的家族关系: 类Unix系统，进程之间存在着家族关系、父/子进程。Windows进程之间不具有父子关系。
-进程间链接指针: 链接相同状态的进程。

4.进程的基本状态，试举出使进程状态发生变化的事件并描绘它的状态转换图。
-运行态(running): 进程正在CPU上运行。单CPU系统一次只有一个运行进程; 多CPU系统可能有多个运行进程。
-阻塞态(blocked): 又称等待态。当进程因等待某个事件发生而不能运行时所处的状态。等待I/O完成，等待一个消息。
-就绪态(ready): 已获得除CPU之外的全部资源，只要再获得CPU，就可执行。
-创建态: 刚刚建立，未进入就绪队列。
-终止态: 已正常结束或故障中断，但尚未撤销。暂留在系统中，方便其后进程去收集该进程的有关信息。

5.什么是原语?什么是进程控制?
-原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。
-进程控制是指系统使用一些具有特定功能的程序段来创建、撤销进程，以及完成进程各状态之间的转换。

6.进程调度的功能、方式、时机、算法。作业调度、交换调度。作业的周转时间和作业的带权周转时间?
-功能：
-管理系统中各进程的执行状况
-选择就绪进程占有CPU
-进行进程上下文的切换
-方式：
-非抢先方式(非剥夺方式)
-抢先方式(剥夺方式)
-时机：
-进程完成或错误终止；
-提出I/O请求，等待I/O完成时；
-在分时系统，按照时间片轮转，分给进程的时间片用完时；
-优先级调度，有更高优先级进程就绪；
-进程执行了某种原语操作，如阻塞原语和唤醒原语，都可能引起进程调度。
-调度算法：
-先来先服务(FCFS)
-最短作业优先(SJF)
-响应比高者优先(HRN)
-优先级调度法(priority scheduling)
-轮转法(Round Robin)
-多级反馈队列轮转法(Round Robin with Multiple Feedback)
-作业调度： 高级调度。多道批处理系统。多个用户作业提交到外存，形成后备作业队列。被作业调度选中进内存，就处于运行态。
-交换调度: 中级调度。将主存中暂不具备运行条件的进程换出到外存交换区；或将外存交换区中的已具备运行条件的进程换入主存。
-进程调度: 低级调度。为进程分配处理机。
-指从作业进入系统到作业退出系统所用的时间。(等待时间+运行时间)
-带权周转时间是指作业的周转时间与系统为它提供服务的时间之比。

7.线程的定义，线程与进程的比较。系统对线程的支持（用户级线程、核心级线程、两级组合）。
-线程是操作系统能够调度运行的最小单位，是包含在进程中的一个单一顺序的控制流。
-线程与进程的比较
-拥有的资源：
-进程拥有一个独立的地址空间，用来存放若干代码段和数据段。拥有打开的文件，以及至少一个线程。
-一个进程内的多个线程共享该进程的所有资源，线程自己拥有很少资源。
-调度
-进程调度需进行进程上下文的切换，开销大。
-同一进程内的线程切换，仅把线程拥有的小部分资源变换即可，效率高。同一进程内的线程切换比进程切换快得多。不同进程的线程切换…
-并发性
-引入线程后，使得系统的并发执行程度更高。进程之间，进程内的多线程之间可并发执行。
-安全性
-同一进程的多线程共享进程的所有资源，一个线程可以改写另一个线程的数据，共享数据方便。多线程实现安全性好。

-系统对线程的支持
-用户级线程
-有关线程的所有管理工作都由用户程序通过调用在用户态运行的线程库完成。系统内核并不知道线程的存在。
-系统内核以进程为单位进行调度。一个线程阻塞，其依附的进程也阻塞。
-多线程对应核心一级一个进程。
-如，POSIX的Pthread线程库。
-核心级线程
-有关线程的管理工作都由内核完成。应用程序通过系统调用来创建或撤销线程。
-一个线程的阻塞，不影响其他线程的执行。
-Windows、Linux多处理机系统。
-两级组合
-既支持用户级线程，也支持核心级线程。
-用户级多个线程对应核心级多个线程。
-当内核了解到一个线程阻塞后，通知运行时系统，重新调度其他线程。

8.并发执行的进程在系统中通常表现为几种关系?各是在什么情况下发生的?
-对资源的共享引起的互斥关系:
-进程之间本来是相互独立的，但由于共享资源而产生了关系。间接制约关系，互斥关系。
-协作完成同一个任务引起的同步关系：
-一组协作进程要在某些同步点上相互等待发信息后才能继续运行。直接制约关系，同步关系。
-进程之间的前序关系：
-由于进程之间的互斥同步关系，使得进程之间具有了前序关系，这些关系决定了各个进程创建和终止的时间。

9.什么叫临界资源?什么叫临界区?对临界区的使用应符合的四个准则。
-临界资源：一次仅允许一个进程使用的系统中共享资源。
-临界区：并发进程访问临界资源的那段必须互斥执行的程序。
-四个准则：
-不能同时有两个进程在临界区内执行；
-等待进入临界区的进程，应释放处理机后阻塞等待；
-在临界区外运行的进程不应阻止其他进程进入临界区；
-不应使要进入临界区的进程无限期等待在临界区之外。

10.解决进程之间互斥的办法：硬件方法，软件方法。
-硬件实现方法：关中断、test&set硬件指令
-关中断：在进程刚进⼊临界区时，⽴即禁⽌所有中断；在进程要离开之前再打开中断。
-test&set硬件指令测试（读取）锁位变量的值。
-软件实现方法：共享变量

**11.若信号量S表示某一类资源，则对S执行P、V操作的直观含意是什么? 当进程对信号量S执行P、V操作时，S的值发生变化，当S>0、S=0、和S<0时，其物理意义是什么?**
-P 操作：
-直观含义：请求一个资源。
-实际操作：将 S 的值减 1。
-如果 S 的新值为负，则表示没有可用的资源，进程需要阻塞等待资源可用。
-V 操作 (Verhogen 或 Signal)：
-直观含义：释放一个资源。
-实际操作：将 S 的值加 1。
-如果 S 的新值不再是负数，则表示有进程可以从阻塞队列中唤醒，因为有资源可用了。
-信号量 S 的值及其物理意义：
-当 S > 0：表示有 S 个资源可用，任意进程可以执行 P 操作并获得资源而无需等待。
-当 S = 0：表示没有可用资源，如有进程要执行 P 操作，则必须等待，表示资源完全被占用。
-当 S < 0：表示有 |S| 个进程在等待资源。每一个负值代表一个因为没有资源而被阻塞的进程。例如，S = -3 表示有 3 个进程在等待资源。

12.在用P/V操作实现进程通信时，应根据什么原则对信号量赋初值？
-资源计数
-写互斥信号量wmutex：
-实现读写互斥和写写互斥地访问共享⽂件，初值为1。
-计数器readcount：
-记录同时读的读者数，初值为0。
-读互斥信号量rmutex：
-使读者互斥地访问计数器readcount，初值为1。

-进程同步
-同步信号量：⽤于解决某⼏个进程之间的同步。初值可以为0，执行后为1.

-生产者-消费者问题
-空缓冲区计数信号量：初值设为缓冲区的总数量，表示所有缓冲区最初都是空的。
-满缓冲区计数信号量：初值设为 0，表示最初没有产品。
-互斥信号量：用于保护对缓冲区的访问，初值设为 1。

13.经典的IPC问题。
生产者-消费者问题：
-⽣产者和消费者是相互合作进程关系的⼀种抽象
-⽣产者：当进程释放⼀个资源时，可把它看成是该资源的⽣产者；
-消费者：当进程申请使⽤⼀个资源时，可把它看成该资源的消费者。
-解决方案：
使用两个计数信号量 Empty 和 Full 分别表示空缓冲区和满缓冲区的数量，另一个互斥信号量 Mutex 保护缓冲区的访问。

Semaphore Empty = N; // 缓冲区大小
Semaphore Full = 0;
Semaphore Mutex = 1; // 互斥信号量

Producer:
  while (true) {
    produceItem(); // 生成一个新产品
    P(Empty);      // 等待有空的缓冲区
    P(Mutex);      // 进入临界区
    putItemInBuffer(); // 将产品放入缓冲区
    V(Mutex);      // 离开临界区
    V(Full);       // 增加满缓冲区计数
  }

Consumer:
  while (true) {
    P(Full);       // 等待有满的缓冲区
    P(Mutex);      // 进入临界区
    removeItemFromBuffer(); // 从缓冲区取出产品
    V(Mutex);      // 离开临界区
    V(Empty);      // 增加空缓冲区计数
    consumeItem(); // 消费产品
  }

哲学家就餐问题:
-问题描述：
五个哲学家围坐在圆桌，每个哲学家有一只叉子，每个哲学家必须同时拥有左右两只叉子才能进餐。需要防止死锁和饥饿。
-解决方案：
使用一个互斥信号量 Mutex 来保护对叉子的获取，另有一个信号量数组 Chopstick。

Semaphore Mutex = 1; // 保护对叉子的访问
Semaphore Chopstick[5] = {1, 1, 1, 1, 1};

Philosopher(i):
  while (true) {
    think();          // 哲学家思考
    P(Mutex);         // 进入临界区
    P(Chopstick[i]);  // 拿起左边的叉子
    P(Chopstick[(i+1) % 5]); // 拿起右边的叉子
    V(Mutex);         // 离开临界区
    eat();            // 哲学家进餐
    V(Chopstick[i]);  // 放下左边的叉子
    V(Chopstick[(i+1) % 5]); // 放下右边的叉子
  }

读者-写者问题
-问题描述：
多个读者可同时读取共享资源，但写者在写入时不得有其他读者或写者访问共享资源。
-解决方案：
使用计数信号量 Mutex 和 Wr，以及读者计数器 ReadCount。

Semaphore Mutex = 1; // 保护对 ReadCount 的访问
Semaphore Wr = 1;    // 保护对共享资源的访问
int ReadCount = 0;

Reader:
  while (true) {
    P(Mutex); 
    ReadCount++;
    if (ReadCount == 1) P(Wr); // 第一个读者阻止写者
    V(Mutex); 
    read(); // 读取共享资源
    P(Mutex); 
    ReadCount--;
    if (ReadCount == 0) V(Wr); // 最后一个读者释放写者
    V(Mutex);
  }

Writer:
  while (true) {
    P(Wr); 
    write(); // 写入共享资源
    V(Wr);
  }

14.进程高级通信有哪些实现机制？
-消息缓冲通信
-系统设置⼀个消息缓冲池，其中每个缓冲区可以存放⼀个消息
-每当进程欲发送消息时，向系统申请⼀个缓冲区，将消息存⼊缓冲区，
-然后把该缓冲区链接到接收进程的消息队列上
-消息队列通常放在接收进程的进程控制块中
-属于直接通信⽅式
-信箱通信
-发送进程将消息发送到中间媒介—信箱，接收进程从中取得消息。
-管道通信
-是指⽤于连接⼀个读进程和⼀个写进程的共享⽂件，⼜称pipe⽂件。OS强制实施互斥。
-是通过OS管理的环形缓冲区。先进先出。
-命令⽅式的管道通信；程序⽅式的管道通信。
-共享存储区
-诸进程为了相互交换⼤量数据，申请创建⼀块共享存储区，并将共享存储区映射到各⾃的地址空间，通过读或写共享存储区中的数据来实现通信。

15.死锁产生的必要条件及解决死锁的方法
-死锁产生的必要条件：
-互斥条件：独占性的资源
-保持和等待条件：进程因请求资源⽽阻塞时，对已经获得的资源保持不放
-不剥夺条件：已分配给进程的资源不能被剥夺，只能由进程⾃⼰释放
-循环等待条件：存在⼀个进程循环链，链中每个进程都在等待链中的下⼀个进程所占⽤的资源
-解决死锁的方法：
-鸵⻦算法：忽略死锁
-死锁的预防：通过破坏产⽣死锁的四个必要条件中的⼀个或⼏个，来防⽌发⽣死锁
-死锁的避免：是在资源的动态分配过程中，⽤某种⽅法去防⽌系统进⼊不安全状态，从⽽避免发⽣死锁
-死锁的检测和恢复
-允许死锁发⽣。通过设置检测机构，及时检测出死锁的发⽣，然后采取适当措施清除死锁

16.理解银行家算法的实质。能够利用银行家算法避免死锁。
-银行家算法的关键概念
-安全状态：如果系统存在某个安全序列，使得所有的进程可以顺序地完成其执行而不发生死锁，则该状态为安全状态。
-不安全状态：如果不存在这样的安全序列，则该状态为不安全状态。不安全状态并不一定会导致死锁，但有可能演变为死锁。
-数据结构
-Available：长度为 m 的数组，表示每种资源类型当前剩余的可用资源数量。
-Max：n x m 的矩阵，表示每个进程对每一种资源的最大需求量。
-Allocation：n x m 的矩阵，表示当前已经分配给每个进程的各类资源数量。
-Need：n x m 的矩阵，表示每个进程还需要的资源数量，计算公式为 Need[i][j] = Max[i][j] - Allocation[i][j]。
-算法步骤
-安全性算法
-1.初始化：
-Work = Available（系统可供资源数）。
-Finish[i] = false（初始化表示所有进程都未完成）。
-2.查找进程：
-找到一个满足下述条件的进程 P_i：Finish[i] == false 且 Need[i] <= Work。如果找到这样的进程，执行以下步骤，否则转到步骤 4。
-3.假设分配：
-Work += Allocation[i]（假设 P_i 请求了其需求的所有资源并完成）。
-Finish[i] = true。
-返回步骤 2。
-4.判断安全性：
-如果所有的 Finish[i] = true，则系统处于安全状态；否则，系统处于不安全状态。
-请求资源算法
-请求合法性检查：
-如果 Request[i] > Need[i]，则为非法请求，拒绝。
-如果 Request[i] > Available，则需阻塞进程 P_i。
-预分配资源：
-临时分配资源：Available -= Request[i]；Allocation[i] += Request[i]；Need[i] -= Request[i]。
-安全性检查：
-使用安全性算法判断预分配后的状态。如果是安全状态，则正式分配资源；否则，恢复先前状态（即回滚预分配），进程 P_i 继续等待。