进程同步 summarize
重点是同步算法设计！
但是前面的知识点也顺便整理了一下
制约关系
1. 同步：需要在某些位置上协调进程之间的工作次序而等待、传递信息产生的制约关系
2. 互斥：当一个进程进入临界区使用临界资源时，其他要求”进入临界区“或”进区“必须等待
临界资源：一次仅允许一个进程是用的资源
临界区互斥-原则：空闲让进，忙则等待，有限等待，让权等待
软件实现 | 硬件实现
Peterson’s Algorithm
IMG_8788.JPG
信号量
P(wait(S)) V(signal(S)) 操作
是原语操作
简单来说，PV操作紧紧夹着使用互斥资源的行为，如果需要某种资源你就P一下，V一下标志着已经完成,提供了某种资源
经典同步问题
生产者-消费者问题
只能放一种水果所以dad 和mom是互斥关系，mom和son，dad和daughter是同步关系，所以这两对进程必须连起来
semaphore plate=1, apple=0, orange=0;
dad(){
while(1){
prepare an apple;
P(plate);//互斥放水果
put the apple;//互斥行为
V(apple);//允许取苹果
}
}
mom(){
//...
}
son(){
while(1){
P(orange);//互斥取橘子
take an orange;
V(plate);//释放盘子
}
}
daught(){
//...
}
哲学家就餐问题
哲学家是和贪心算法相反的思路，如果按照贪心的思路，有筷子就拿起筷子，就会出现死锁。
semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;
Pi(){
do{
P(mutex);//如果没有这条会死锁
P(chopstick[i]);
P(chopstick[(i+1)%5]);//取右边筷子
V(mutex);//释放取筷子的 信号量
eat;
V(chopstick[i]);
V(chopstick[(i+1)%5]);
think;
}while(1);
}
2013联考题
某博物馆最多可容纳500人同事餐馆，有一个出入口，该出入口一次只允许一人通过
请添加信号量并写出完整过程
分析：只允许一个人出入则需要设置出入口的互斥量，并且设置容纳量为500
对应出入操作的时候修改容纳量和互斥量
参观者进程
{
P(empty);//先check容纳量并-1
P(mutex);
进门;
V(mutex);//此时门可以使用
参观;
P(mutex);//参观结束，使用门
出门;
V(mutex);
V(empty);//可接纳容量+1
}
