进程的同步与互斥
在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。
一、进程间制约关系
1.竞争关系
源于资源共享，多个不存在逻辑关系的进程因共享资源而产生制约关系。
若一个进程要求使用某一资源，而该资源正被另一个进程使用，并且这一资源不允许两个进程同时访问，那么该进程只有等待，只有这一资源释放后才能使用。
2.协作关系
源于进程间的协作。
一组进程为完成共同任务分工协作，各进程都独立以不可预知速度推进，在执行的先后次序就有约束，在一些关键点上协调工作。若一个进程运行到某关键点时，在尚未收到另一协作进程发来的信息前应阻塞自己，等协作进程发来消息后方可继续执行。
进程间这种相互依赖又相互制约，相互协作又相互竞争的关系，主要表现在进程互斥和进程同步两方面
二、进程互斥
引例： 宿舍电话的使用
打印机的使用
1、临界资源
一次仅允许一个进程使用的资源称为临界资源。
引例中的电话和打印机都属于临界资源。还有光盘刻录机、绘图仪、共享变量、共享的数据结构等等也是临界资源。
2、临界区：
每个进程中访问临界资源的那段程序段称为临界区。（临界段）
３、进程互斥
进程应互斥访问同一临界资源，即进程应互斥的进入临界区。当一进程正在访问某临界区时，就不允许其它进程进入，试图进入临界区的另一进程必须等待。进程之间的这种相互制约的关系称为进程互斥。
4、进入临界区的准则：
每次至多有一个进程进入临界区内执行；
若已有进程在临界区中，试图进入此临界区的其他进程应等待；
进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入。
进程同步
互斥的概念来自于诸进程对临界资源的竞争，同步来源于多个进程的协作。在人类社会中竞争与协作是永恒的。
进程同步：几个进程相互协作，一个进程到达某点后，若另一进程尚未完成某些操作，就必须停下来等待，只有等另一进程的这些操作完成了才能继续执行。协作进程间需要在某些关键点上排定执行先后次序而等待、传递信号或消息所产生的协作关系称为进程同步。
进程互斥的实现
一、实现进程互斥的软件算法
现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。
软件解法的缺点
1. 忙等待
2. 实现过于复杂，需要较高的编程技巧
二、实现进程互斥的硬件设施
用软件解决很难，现代计算机大多提供一些硬件指令。
利用关中断实现进程互斥
利用Test-and-Set指令实现互斥
利用swap指令实现进程互斥
1.利用关中断实现进程互斥
进程进入临界区时关中断，在进程退出临界区时开中断。
关中断方法简单有效
关中断方法的缺点
2.Test-and-Set（TS）指令实现互斥
TS指令
bool TS(bool &x)
{
if(x)
{
x=false;
return true;
}
else
return false;
}
TS指令实现进程互斥
bool s=true;
cobegin
process Pi( ) { //i=1,2,...,n
while(!TS(s)); //上锁
{临界区};
s=true; //开锁
}
coend
变量s代表了临界资源的状态，可把它看成一把锁。S初值设为true，表示没有进程在临界区，资源可用。进入临界区前，首先用TS指令测试s，若没有进程在临界区，则可进入，否则循环测试直至s的值为true；当进程退出临界区时，把s的值置为true。
3.swap指令实现进程互斥
swap指令
又称交换指令，在Intel x86中称为XCHG。
功能是交换两个字的内容。
void SWAP(bool &a,bool &b)
{
bool temp=a;
a=b;
b=temp;
}
利用swap实现进程互斥
为每一临界资源设置一个全局布尔变量lock，其初值为false，表示无进程在临界区内。在每个进程中有局部布尔变量keyi。
bool lock=false;
cobegin
Process Pi( ){ //i=1,2,...,n
bool keyi=true;
do {
SWAP(keyi,lock);
}while(keyi); //上锁
{临界区};
SWAP(keyi,lock); //开锁
}
coend
实现进程互斥的软件算法太过复杂，效率低下；
实现进程互斥的硬件方法虽简单有效，但采用忙式等待，白白浪费cpu时间；将测试能否进入临界区的责任推卸给各进程，会削弱系统的可靠性，加重用户的编程负担；且这些方案只能解决进程互斥问题，却不能解决进程同步问题。
信号量与PV操作
管理和控制铁路和公路交通的重要工具是信号灯，利用信号灯的颜色控制各种车辆的正常通行。在操作系统中引入了信号灯（信号量）的概念，让多个进程通过信号量展开交互。
一、信号量的概念
信号量的概念是由荷兰科学家Dijkstra于1965年提出的。
1.信号量的定义
是一个结构型数据结构，定义如下：
struct semaphore
{
int value; //信号量的值
struct pcb *list; //信号量队列的头指针
}
信号量说明：
semaphore s;
信号量必须置一次且只能置一次初值，初值不能为负数。
对信号量只能执行P、V操作
2.P、V操作
对信号量仅能执行P、V操作。
对信号量的P操作记为：P(S)，P操作是一个原子操作。
对信号量的V操作记为：V(S), V操作是一个原子操作。
在实际系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。
P(s)：
s.value--；
若s.value≥0，则执行P(s)的进程继续执行；
若s.value<0，则执行P(s)的进程被阻塞，并把它插入到等待信号量s的阻塞队列中。
V(s)：
s.value++；
若s.value>0 ，则执行V(s)的进程继续执行；
若s.value≤0，则执行V(s)的进程从等待信号量s的阻塞队列中唤醒头一个进程，然后自己继续执行。
操作系统正是利用信号量的状态对进程和资源进行管理。从物理意义上理解，P操作相当于申请资源；V操作相当于释放资源。
二、用信号量实现进程互斥
1. 两个进程间的互斥
semaphore S；
S =1；
cobegin
Process P1( ) Process P2( )
{ …… { ……
P（S） P（S）
V（S） V（S）
…… ……
} }
coend
信号量取值范围：m~m-n
信号量的含义：
S>0表示有S个资源可用
S=0表示无资源可用
S<0则| S |表示S等待队列中的进程个数
三、用信号量实现进程的同步
1.进程同步模型
进程P1到达L1这一点时，若进程P2还未执行到L2点，进程P1就必须停下来等待，等到进程P2到达L2这一点时，P1才能继续运行。也就是进程P1在L1这一点要与进程P2同步。
（P1等待P2）
semaphore s；
S=0
Cobegin
process P1（） process P2（）
{ …… { ……
L1:P(s) ……
…… L2:V(s)
…… ……
} }
coend
在操作系统中，同步有各种各样，归纳起来有两类：
保证一组合作进程按确定的次序执行
保证共享缓冲区的合作进程的同步。
2.合作进程的执行次序
若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求。
为了描述方便，可以用一个图来描述诸进程合作完成某一任务的次序。——进程流图
四、互斥和同步对信号量操作方法的差异
互斥和同步都是通过对信号量的P、V操作来实现的，但这两种控制机制对信号量的操作策略是不同的。
互斥的实现：
是不同进程对同一信号量进行P、V操作。进入临界区之前执行P操作，退出临界区后执行V操作。
同步的实现：
Pa进程要同步等待Pb需设置一信号量，Pa进程中实行P操作，Pb进程实行V操作。
若进程Pb也要同步等待Pa，则要设置另一个信号量。
P.V操作必须成对出现，有一个P操作就一定有一个V操作
当为互斥操作时，它们同处于同一进程
当为同步操作时，则不在同一进程中出现
总结：
P.V操作必须成对出现，有一个P操作就一定有一个V操作。
当为互斥操作时，它们同处于同一进程。
当为同步操作时，则不在同一进程中出现。
如果两个P操作在一起，那么P操作的顺序至关重要。
一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前。
而两个V操作在一起时顺序无关紧要。
进程通信
进程通信(Interprocess Communication,IPC)是指进程之间的信息交换。
信号量及P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。
进程间通信的方式
信号(signal)通信机制
管道(pipeline)通信机制
消息传递(message passing)通信机制
信号量(semaphore)通信机制
共享主存(shared memory)通信机制
前两种是UNIX最早的版本就提供的进程通信机制。信号通信机制只能发送单个信号而不能传递数据；管道通信虽能传送数据，却只能在进程家族内使用，应用范围有限。
一、管道通信机制
管道通信是UNIX的传统进程通信方式，也是UNIX发展最有意义的贡献之一。
所谓管道，是指用于连接一个读进程和一个写进程的特殊文件，称pipe文件。
发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。
管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。
但写进程和读进程间的相互协调单靠文件系统机制解决不了，读写进程相互同步，必须做到以下几点：
（1）互斥，即一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待；
（2）发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。
（3）同步，指当写进程把一定量的数据发送后，便睡眠等待，直到读进程把管道中数据取走后，在把它唤醒。反之当读进程读空管道时，也被阻塞，直到写进程将数据写入管道后，才将它唤醒。
二、共享主存通信机制
在主存中开辟一个公用存储区，要通信的进程把自己的虚地址空间映射到共享主存区。发送进程将信息写入共享主存区的某个位置上，接收进程可从此位置读取信息。
三、消息传递通信机制
进程间的数据交换以消息为单位，程序员利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。因而得到广泛应用。
消息传递通信机制可分为：
直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。
间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。也称信箱通信，在网络中称为电子邮件系统。
1.直接通信的实现
发送或接收消息的进程必须指出消息发给谁或从谁那里接收消息。至少需要提供两条原语：
原语send（P，消息）：把一个消息发送给进程P
原语receive（Q，消息）：从进程Q接收一个消息
直接通信的实现在操作系统空间设置一组缓冲区。
当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系统。
操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。
发送进程返回到用户态继续执行。
在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管中断进入操作系统。
由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收。
接收进程返回到用户态继续进行。
2.间接通信的实现
Send实现
send（MailBox，M）：把信件M送到指定的信箱MailBox中
步骤：
查找指定信箱MailBox ；
若信箱未满，则把信件M送入信箱且唤醒“等信件”者；
若信箱已满置发送信件进程为“等信箱”状态；
Receive实现
receive（ MailBox ，X）：从指定信箱MailBox中取出一封信，存放到指定的地址X中
步骤：
查找指定信箱MailBox ；
若信箱有信，则取出一封信存于X中且唤醒“等信箱”者；
若信箱无信件则置接收信件进程“等信件”状态；
死锁
在一组进程中，每个进程都等待被该组进程中其他进程所占有的资源，从而无限期陷入僵持的局面，这种现象称为死锁。
如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。
2.产生死锁的原因
竞争资源
进程间推进顺序不当
3.产生死锁的必要条件
互斥条件：系统中存在临界资源，进程应互斥地使用这些资源。
占有和等待条件：进程在请求资源得不到满足而等待时，不释放已占有的资源。
不剥夺条件：进程已占有的资源只能由属主释放，不能强行剥夺。
循环等待条件：存在循环等待链，链中的每一个进程都在等待下一进程所持有的资源。
4.处理死锁的基本方法
（1）死锁防止（deadlock prevention）
通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。
`较易实现，广泛使用，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。
（2）死锁避免
不事先采取限制措施去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
只需事先施加较弱的限制条件，可获得较高的资源利用率和系统吞吐量，但在实现上有一定难度。在较完善的系统中常用此方法。
（3）检测死锁
事先并不采取任何限制，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源。
（4）解除死锁
与检测死锁相配套，当检测到发生死锁时，采用一定的方法解除死锁。
实现难度大，但可获得较好的资源利用率和系统吞吐量。
二、死锁防止
设法破坏产生死锁的四个必要条件之一。
条件1（互斥条件）是由设备的固有特性所决定的，不仅不能改变，还应加以保证。
破坏条件2（占有和等待条件）
采用资源的静态分配策略。
静态分配是指进程必须在执行前一次性地申请在所需的全部资源，若系统有足够资源则完全分配。若分配时只要有一种资源不能满足，则不分配任何资源，而让进程等待。
优点：简单、易于实现且安全。
缺点：资源严重浪费，严重降低资源的利用率；使进程延迟运行。
破坏条件3（不剥夺条件）
采用剥夺式调度方法。
占有资源的进程，再提出新资源请求时，若有则分配，否则剥夺此进程已占有的所有的资源，并让进城进入等待状态，资源充足后再唤醒它重新申请所需资源。
实现复杂、要付出很大的代价。
破坏条件4（循环等待条件）
资源按序分配：把系统中的所有资源编号，所有分配请求必须以序号上升的次序进行。
例如：系统中有下列设备：输入机（1），打印机（2），穿孔机（3），磁带机（4），磁盘（5）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。
优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。
缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。
三、死锁避免
各种死锁防止方法能够防止死锁发生，但由于所加限制条件太严格，会导致系统资源利用率和系统吞吐量的降低。
另一种解决死锁问题的方法称为避免死锁。
避免死锁基本思想：把系统状态分为安全状态和不安全状态，只要系统一直处于安全状态即可避免死锁的发生。
1.系统状态
（1）安全状态
如果系统能按某种进程顺序（如P1，P2，…,Pn）为每个进程分配其所需的资源，直至所有进程都能运行完成，此时称系统处于安全状态。进程序列称为安全序列。
（2）不安全状态
若不存在这样一个安全序列称系统处于不安全状态。
系统进入不安全状态后，就有可能进而进入死锁状态，反之，只要系统处于安全状态，便可避免进入死锁状态。
死锁避免实质：
允许进程动态地申请资源，但系统在资源分配前先检查此次分配后系统的安全性，若分配后系统仍处于安全状态，则将资源分配给进程，否则不分配，令进程等待。
2.银行家算法
最有代表性的避免死锁算法，由Dijkstra提出。
3.安全性测试算法
四、死锁的检测和解除
以上讨论的各种处理死锁的技术均是事先预防的方法，保证系统不会发生死锁。
死锁的检测和解除技术允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生，一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。
1.死锁的检测
（1）进程-资源分配图
用有向图描述系统状态，准确、形象
（2）死锁检测
系统状态和资源分配图一一对应，可通过资源分配图检测系统是否发生死锁。
a.如果进程-资源分配图中无环路，则此时系统没有发生死锁。
b.如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。
c.如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。未必发生死锁。
进程-资源分配图化简
在进程-资源分配图中找出一个即不阻塞又非独立的进程，消去此进程的所有请求边和分配边，成为孤立结点。重复上述过程，经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。
死锁定理
系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理。
二、死锁的解除
结束所有进程的执行，重新启动操作系统。方法简单，但以前工作全部作废，损失很大。
撤销陷于死锁的所有进程，解除死锁继续运行。
逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除。
剥夺陷于死锁的进程占用的资源，但并不撤销它，直至死锁解除。可仿照撤销陷于死锁进程的条件来选择剥夺资源的进程
根据系统保存的检查点，让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制。
当检测到死锁时，如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，有可能释放足够的资源来解除死锁。