进程同步与互斥

进程同步

我们知道为了实现并发，进程就有了异步性这个概念，异步性就是以不可预知的速度和方向进行的，但是有的时候我希望各个进程是可以共同合作的，就是有一定顺序的进行，就比方说管道通信，我就想先写再读而不是不知道是先读还是先写，这个时候就要引入进程同步来解决这个问题。

进程同步：有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的顺序

进程互斥

进程互斥就是当一个进程使用某一资源时，其他进程只能等待，只有当这一进程用完了，将资源释放了，下一进程才能使用，也就是互斥。那某一资源是啥？这就是下面要讲的一个概念——临界资源

临界资源：一个时间段内只允许一个进程使用的资源，如很多物理设备——打印机，摄像头，此外还有很多变量，数据，内存缓冲区都属于临界资源

对临界资源的互斥访问，可以在逻辑上分为如下四个部分

进入区：负责检查是否可以进去临界区，若可以进入，则应该设置正在访问临界资源的标志(可以理解为上锁)

临界区：访问临界资源的那段代码

退出区：负责接触正在访问临界资源的标志(可理解为解锁)

剩余区：做其他处理

现在我们来想一个问题，要是我这个进程暂时进不了临界区，但是他还站着处理机，我可以一直让他一直占着吗。为了保证整体系统的性能，就要引入我的四个原则

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区

忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待

有限等待：对请求访问的进程，应保证能在有限的时间内进入临界区(不会饥饿)

让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待(占用着处理机却不能进临界区而忙碌地等待)

进程互斥的软件实现方法

先给出框图，再详细讲

单标志法:

int turn = 0;
P0进程：                               P1进程：
while(turn!=0);   (1)                 while(turn!=1);   (5)  //进入区
critical section; (2)                 critical section; (6)  //临界区
turn = 1;         (3)                 turn = 0;         (7)  //退出区
remainder section;(4)                 remainder section;(8)  //剩余区

首先我们来推一下这个方法是怎么实现互斥的，我们定义了turn为0，这个turn就是单标志，即刚开始只允许P0先进入临界区。若P1先上处理器运行，他会一直循环5，直到时间片用完，发生调度，回到P0，P0可以进入临界区，在P0运行过程中，若切换回P1，仍会继续循环在5，只有P0在退出区将turn转为1时，P1才能进临界区，因此可以实现互斥。

但是我们可以很容易就发现我把TURN 定义成0后，对于临界区的访问，只能是P0->P1->P0->P1…,这样的轮流进入临界区带来的问题就是，当只允许P0进，但P0一直不进，P1想进却进不了，就不满足空闲让进的原则。

双标志先检查法:

bool flag[2];  //表示进入临界区的意愿的数组
flag[0]=false;
flag[1]=false;
P0进程：                               P1进程：
while(flag[1]);   (1)                 while(flag[0]);    (5) //进入区
flag[0]=true;     (2)                 flag[1]=true;      (6)
critical section; (3)                 critical section;  (7) //临界区
flag[0]=false;    (4)                 flag[1]=false;     (8) //退出区
remainder section;                    remainder section;     //剩余区

flag[0],flag[1]为双标志，谁要是想进先检查对方想不想进，对方想，那他就一直卡在那，直到时间片用完，对方不想，那他就把自己的标志设为true(上锁)，直到他来到退出区将他的标志设为false，别的进程才能用临界区。对比单标志法，这里因为在进入临界区前上了锁就是只有他想进入临界区时才会设置成true,这样就避免了违反空闲让进原则

但想想要是按照152637这样的顺序进行，产生这种方式的原因是异步性，这样的话就是说P0，P1可以同时进入临界区，违反了忙则等待的原则，导致这种情况的原因就死检查和上锁没有一气呵成，有可能因为进程切换导致这样的结果

双标志后检查法:

bool flag[2];  //表示进入临界区的意愿的数组
flag[0]=false;
flag[1]=false;
P0进程：                               P1进程：
flag[0]=true;     (1)                 flag[1]=true;      (5) //进入区
while(flag[1]);   (2)                 while(flag[0]);    (6)
critical section; (3)                 critical section;  (7) //临界区
flag[0]=false;    (4)                 flag[1]=false;     (8) //退出区
remainder section;                    remainder section;     //剩余区

对比双标志先检查法可以发现，这个无非就是颠倒了一下顺序，先上锁后检查，这样的话我先上了锁表明我想进，然后另一个要是想进，那我就等待因此的确是避免了同时进入的可能，但是如果我还是因为异步，按照1526的顺序，就会导致谁也进不去，这就违背了空闲让进，和有限等待原则，会因各进程都长期无法访问临界资源而产生饥饿现象。

Peterson算法:

bool flag[2];  //表示进入临界区的意愿的数组
int turn=0;
flag[0]=false;
flag[1]=false;
P0进程：                               P1进程：
flag[0]=true;     (1)                 flag[1]=true;     (6)  
turn=1;           (2)                 turn=0;           (7)
while(flag[1]&&turn==1);  (3)         while(flag[0]&&ruen==0);  (8)
critical section;     (4)             critical section;  (9)
flag[0]=false;     (5)               flag[1]=false;      (10)
remainder section;                    remainder section;

这个算法可以理解成一种孔融让梨的思路，比如说1,6是表明自己想要进临界区，2,7却是我愿意让出临界区，123456或者1623都能满足互斥。

最后说一下这四个算法都有的一个毛病，就是在他们进行死循环进不了临界区的shihou9，他们都占着处理机，就造成了忙等，也就是违背了让权等待

进程互斥的硬件实现方法

中断屏蔽方法:

利用开/关中断指令实现，与原语实现思想相同，即在进程从开始访问临界区到结束访问这中间不允许发生进程切换，因此不能发生两个同时访问临界区的情况

···

关中断

临界区

开中断

···

优点：简单高效

缺点：不适合多处理机，假如说我处理机1弄了关中断，那处理机1当然不会有问题，别的进程进不了临界区，但是如果我其他的处理机想进入临界区，那因为中断是相对于某个处理机，那么也就是说处理机2上的进程也可以进入处理机1的这个临界区，就没有实现互斥了

再者，因为开/关中断指令只能运行在核心态，如果让用户态可以随意调用很危险，所以只适用于操作系统内核进程，不适用于用户进程

TextAndSet指令:

TSL指令是用硬件实现的，执行过程中不允许被中断，将检查和上锁操作一气呵成

优点：适用于多处理机，实现简单，不用想软件实现方法那样严格检查是否会有逻辑漏洞

缺点：和软件实现方法一样，可能会出现占用处理机进行死循环的状态，形成忙等待，即不满足让权等待的原则

Swap指令:

逻辑上与TSL指令类似，优缺点也一样，只不过步骤不太一样。