第五章、进程同步——让多个进程推进的合理有序
一、什么是进程同步
生产者——消费者模型
就拿这个最最基础的模型举例，什么是生产者，显而易见是产生资源的部分，消费者是消耗资源的部分，那么如何让生产者产生的资源不过剩，消费者消耗的资源不超额呢，这就需要考虑如何**“同步”**——即，互相不可见的两部分的相互配合配合
二、如何实现进程同步
地址隔离策略导致了进程之间是相互不可见的，这就导致了无法直接的实现同步配合，所以我们就需要引入一个或多个全局的变量来作为进程同步的信号，以写入和读取共享缓冲区中的内容为例：
counter定义为全局的“缓冲区容量计数器”，当counter==BUFFER_SIZE是，表明缓冲区空间已满，此时生产者进程睡眠（进入阻塞态），counter ==0时，表明缓冲区读取完成，消费者进程睡眠（进入阻塞态）。counter ==1时，表明缓冲区中有一个新内容，此时唤醒消费者读取这个内容，消费者读取完后，counter变为0，消费者又进入睡眠，进程切换给生产者。
这样的过程就实现了进程之间的同步，使得二者的配合井然有序，但是也存在问题，多变的调度情况下，这种信号控制走与停的方法不能很好的应用于复杂的调度场景
于是就出现了信号量（可用于复杂的场景）
三、信号量实现进程同步
1.什么是信号量
信号量是在信号上关联的一组整数，可以根据这个整数来决定进程的阻塞或唤醒。
更具体一点点
（1）信号量就是一个整型变量，用来记录和进程同步有关的重要信息
（2）能让进程阻塞睡眠到这个信号量上
（3）需要同步的进程通过操作（加一或减一）信号量实现进程的阻塞和唤醒，即进程间的同步
因此，信号量就是一个数据对象以及操作这个对象的两个操作，其中数据对象是信号量数值以及相应的阻塞进程队列
2.信号量的伪代码
struct semaphore{
int value;
PCB *queue;
}
P(semaphore s){
s.value--;
if(s.value<0)
sleep_on(s.queue);
}
V(semaphore s){
s.value++;
if(s.value<=0)
wake_up(s.queue);
}
不难看出P对信号量减一，V对信号量加一
根据信号量加一或减一后的数值决定是否唤醒进程。
full表示缓冲区有多少个单元被占用了，empty表示缓冲区还有多少个单元空闲。
所以初始化时full=0；empty=BUFFER_SIZE；
这个mutex被作为不稳定的临界区入口，什么是临界区以及为什么把他叫做不稳定的，后面再来谈。
四、临界区——对信号量的保护
1.信号量为什么需要保护
因为信号量是多个进程共享的，不能允许有两个进程同时修改信号量，多个并发进程会竞争CPU，可能会造成多种多样的调度结果，这些不同的调度顺序其中某些就可能造成信号量的语义错误。
2.如何保护信号量
1.什么是临界区
简单来说，临界区就是进程中的一段代码，一旦进入了这段代码，进程之间就不能随意切换了，直出临界区。
2.实现好的临界区的几个要素
（1）互斥进入——确保只能有一个进程进入临界区
（2）有空进入——确保没有进程处于临界区内时且有进程请求进入临界区时让某个进程进入临界区执行
（3）有限等待——每个进程都一定会进入临界区，不会无限等待
3.信号量保护
信号量保护要确保每个进程对信号量的修改操作是原子操作。
信号量保护的实质就是让进程中修改信号量的代码变成临界区代码。
4.临界区的实现
（1）软件实现
（a）轮换法
一次只允许一个进程进入，然后进程轮着来(设置优先级)
//进程P0 //进程P1
while(turn==1); while(turn==0);
empty--; empty--;
turn=1; turn=0;
满足互斥进入，不满足有空让进和有限等待
（b）标记法
//P0 //P1
flag[0]=true; flag[1]=true;
while(flag[1]); while(flag[0]);
empty--; empty--;
flag[0]=false; flag[1]=false;
满足互斥进入，再非特殊情况下满足有空让进 ，但当两个进程同时请求进入临界区时，由于flag[1]==flag[0] ==true导致两个进程全部自选，相互锁住。不满足有限等待
（c）Peterson算法——标记法和轮换法结合
（1）标记法判断进程是否请求进入临界区
（2）轮换发给进程明确的优先级排序——这种明显的优先顺序可以避免由于两个进程同时申请进入临界区时导致互锁的情况
//P0 //P1
flag[0]=true; flag[1]=true;
turn=1; turn=0;
while(flag[1]&&turn==1); while(flag[0]&&turn==0);
empty--; empty--;
flag[0]=false; flag[1]=false;
可以看出，先请求进入的进程，优先级更高，后请求的就会自旋等待先请求的执行完成
满足互斥进入、有空进入、有限等待
缺陷：只能处理两个进程的临界区
（d）面包店算法
每个顾客都是一个进程，一次只能接待一个顾客进入，是一种互斥，N个顾客要进入面包店采购，首先按照次序给每个顾客安排一个号码，按照其号码大小依次进行购买，未完成购买的顾客号码重置为0，这样完成购买的顾客如果要再次购买，要重新排队
do{
chooseing[i]=true;
numer[i]=max(number[0],number[1],……,number[n-1])+1;
choosing[i]=false;
for(j=0;j<n;j++){
while(choosing[j]);
while((number[j]!=0)&&(number[j],j)<(number[i],i));
}
........ //临界区代码
number[i]=0;
}while(true;)
这个算法是什么意思呢，就是给你了一个i进程，先取一个最大的号**（比当前的所有号码都要大——注意看number[i]选号最后加了一），然后在申请队列中，逐个判断哪一个进程没有进入过商店==(while(choosing[j] )==并且“号”是最小的**<mark>(number[j],j)<(number[i],i)</mark>，遍历所有进程找到那个最小的进程，让其进入“商店”执行，执行完后，将他的号变为0代表重新排队。
满足互斥进入——轮换的算法一定满足互斥进入
满足有空进入——当申请队列中没有进程时，新申请的进程就是最小的，可以直接进入
满足有限等待——显然的，每一个进程都有机会被轮换到
（2）硬件实现
由于面包店算法很复杂，并且每次选号都比所有号的最大值还要大1，容易发生号码溢出。
当软件实现变得复杂时，就要从硬件下手了。
（a）对于单核CPU系统
调用cli（）；——关闭中断
sti（）；——开启中断
因为需要内核才能调用schedule（）函数，要进入内核需要中断，所以为了阻止在某一进程在临界区时被切换，直接阻断中断就好了。
语法很简单
cli();
empty--;
sti();
（b）对于多核CPU系统
保护临界区可以使用互斥信号量来实现，由于互斥信号量只取0，1两个数值，所以这个信号量的P、V操作就会简单而规整，完全可以用硬件来实现P\V操作的原子性。
硬件原子指令法： <mark>可以实现多CPU的临界区保护</mark>
function TestAndSet(boolean &lock){
boolean initial=*lock;
*lock=true;
return initial;
}
当lock为true时，表明其他进程已经在使用临界区了，已经为临界区上了锁，此时，申请进程自旋等待。
当lock为false时，表明没有进程使用临界区，可以进入，并将lock改为true，为临界区上锁，表明有进程正在使用。
while(TestAndSet(&lock));
empty--;
lock=false;
这里有一种例外情况，当多个进程同时申请进入临界区，即同时执行TestAndSet指令。不过可以解决
当执行该指令时，CPU会锁住内存总线，阻止其他CPU在该指令执行结束以前访问内存。
五、死锁现象以及死锁处理
1.什么是死锁
多个进程由于互相 等待对方持有的资源而造成谁也无法执行的情况叫做死锁
死锁会导致计算机运转很慢甚至不运转
2.死锁的成因
（1）资源互斥使用，一旦占有，别人不能使用
（2）进程占有了一些资源，不去释放，又申请新的资源
（3）各自占有的资源和互相申请的资源形成环路等待。
3.死锁的4个必要条件
（1）互斥使用
（2）不可抢占——资源只能自愿放弃
（3）请求和保持——进程必须占有资源，再去申请
（4）循环等待——资源分配图中存在环路
4.死锁的处理方法
（1）死锁预防
破坏死锁出现的条件：——互斥和不可抢占很难被破坏，这是基本
（a）破坏请求与保持——一次性申请进程需要的所有资源，当进程因为请求资源而阻塞时，该进程当然不会获得，也就不会占有任何资源。
（b）破坏循环与等待——使资源按顺序申请
不管是以上那种方式，都会造成资源的浪费，且编程困难，不提倡。
（2）死锁避免
检测资源请求，如果造成死锁，就拒绝。
——银行家算法
int Available[1....m];
int Allocation[1...n,1...m];
int Max[1...n,1...m];
int work[1....m];
bool Finish[1...n];
work=Available;
Finish[1...n]=false;
while(true){
find=false;
for(i=1;i<=n;i++){
if(Finish[i]==false&&Work>=Max[i]-Allocation[i]){
Finish[i]=true;
work=work+Allocation[i];
find=true;
}
}
if(find==false){
goto END;}
}
END:for(i=1;i<=n;i++)
if(Finish[i]==false)
return "deadlock";
find表示是否找到可以执行的进程（可提供的资源足够进程使用），如果找到（即使一个），就不会出现死锁的情况，如果都没有找到，说明进程均不能执行，跳转至end：标记处执行。
（3）死锁检测，恢复死锁
这个检测到死锁以后需要回滚会未死锁的状态，算法复杂，对于PC机学习不推荐使用
（4）死锁忽略
就是我们经常做的，出现死锁的情况，直接重启就好了，死锁的效果就可以忽略掉。
京公网安备 11010502036488号