操作系统——经典同步问题

1、概念

1.1 进程同步与互斥

在多道程序环境下，进程是并发执行的（并发执行是指两个或多个事件在某段时间间隔内并发），不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

进程同步是直接制约关系，指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的的制约关系。（源于他们之间的互相合作关系）

进程互斥是间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区时，另一个进程才允许去访问此临界资源。

临界资源是一次仅允许一个进程使用的资源，临界资源的访问过程：进入区（在进入区要检查可否进入临界区，并设置正在访问临界区的标识，以阻止其他进程同时进入），临界区，退出区，剩余区

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

同步机制准则：

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

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

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

让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

1.2 信号量

信号量是一种功能较强的机制，可以用来解决互斥与同步的问题，它只能被两个标准的原语操作，即为“P”和“V”操作，P操作是信号量减1，V操作是信号量加1

原语是指完成某种功能且不被分割、不被中断执行的操作序列

（1）整型信号量

整型信号量是来表示资源数目的整形量S，只要S≤0，就会不断测试，并未遵循“让权等待”的准则，而是使进程处于“忙等”状态。

P(S){
    while(S<=0){
    S = S-1
   }
}
 
V(S){
   S=S+1
}

（2）记录型信号量

记录型信号量机制是一种不存在“忙等”现象的进程同步机制，除了表示资源数目的整型变量S外，再增加一个进程链表L，用于链接所有等待该资源的进程。

//定义结构体
typedef struct{
    int S;
    struct process *L;
}semaphore;
 
void P(semaphore se){
     se.S--;
     if(se.S<0){
        
        add this process to se;
        block(se); //调用block原语，进行自我阻塞
   }
}
 
void V(semaphore se){
 
    se.S++
    if (se.S<=0){
        remove a process P from se;
        wakeup(P); //调用wakeup原语，唤醒链表中的第一个等待进程
   }
}

（3）分析进程同步和互斥问题的方法步骤

• 关系分析：找出问题中的进程数，并分析他们之间的同步和互斥关系
• 整理思路：找出解决问题的关键点，并且根据做过的题目找出解决思路，根据进程的操作流程确定P操作，V操作的大致顺序
• 设置信号量：设置需要的信号量，确定处置，完善整理

（4）利用信号量实现进程同步

问题描述：S为P1、P2两个进程的公共信号量，初始值为0，进程P2执行需要依赖进程P1中语句x的运行结果，即只有当语句x执行完成之后，语句y才可以执行。

semaphore S=0;
 
P1(){
 
    x; //先执行x
    V(S);  //s++
}
 
P2(){
    P(x);
    y ;
    V(y);
 
}

（5）利用信号量实现互斥

问题描述：设S为实现进程P1、P2互斥的信号量，由于每次只允许一个进程进入临界区，设置S=1（即可用资源数为1），当进程对信号量S进行P操作后进入临界区，并在退出后，该进程对该信号量执行V操作，表示没有进程进入临界区，可以让其他进程进入。设计如下：

semaphore S=1;
 
P1(){
    
    P(S); //访问临界资源，S--
    //进入临界区
    V(S);//访问结束，S++
}
P2(){
    
    P(S); //访问临界资源，S--
    //进入临界区
    V(S);//访问结束，S++
}

2、经典问题

2.1 生产者-消费者

• 问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。
• 问题分析：

（1）关系分析：生产者和消费者对缓冲区访问是互斥，生产者和消费者又是相互协作关系，生产者生产之后才能消费，属于同步关系

（2）整理思路：只有生产者和消费者两个进程，两个进程间存在着同步和互斥关系，要解决互斥和同步PV操作的位置

（3）信号量设置:信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初值为1；信号量full用于记录当前缓冲池中“满”缓冲区数，初值为0。信号量empty 用于记录当前缓冲池中“空”缓冲区数，初值为n。

#define semaphore int
 
semaphore empty=n; //表示空缓冲区的个数
semaphore full=0; //表示满缓冲区的个数
 
semaphore mutex =1; //互斥信号量（生产者和消费者共用缓冲区）
 
void Producer(){
 
    while(1) {
       produce a item; //生产数据
       P(empty); //空缓冲区的个数减1
       P(mutex); //互斥变量减1，进入临界区
       add  item to buffer; // 将item放入缓冲区
       V(mutex);  //互斥量加1，退出临界区
       V(full);   //满缓冲区加1
   }
}
void Consumer(){
    
    P(full); // 同步，判断缓冲区是否有生产者
    P(mutex); //互斥变量减1，进入临界区
    remove item from buffer; //将item移除缓冲区
    V(mutex); //互斥量加1，退出临界区
    V(empty); //空缓冲区加1
    consumer a item; //消费数据
}

2.2 分水果问题

• 问题描述：桌子上有一个盘子，每次只能想其中放入一个水果，爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈就可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。
• 问题分析：

（1）关系分析。这里的关系稍复杂一些，首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发

（2）整理思路。这里有4个进程，实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上

（3） 信号量设置。首先设置信号量plate为互斥信号量，表示是否允许向盘子放入水果，初值为1，表示允许放入，且只允许放入一个。信号量 apple表示盘子中是否有苹果，初值为0，表示盘子为空，不许取，若apple=1可以取。信号量orange表示盘子中是否有橘子，初值为0，表示盘子为空，不许取，若orange=1可以取。

notes:生产者和消费者是生产者生产完把缓冲区释放，消费者再去访问缓冲区；分水果是放完水果，标记盘子有水果，才会去拿水果，再释放盘子。

#define semaphore int
semaphore plate=1;  //互斥
semaphore apple=0;
semaphore orange=0;
 
void dad(){
    while(1){
    //prepare an apple
    P(plate);
    put the apple on the plate;
    V(apple);  //apple标记为1，证明盘子有apple
   }
}
 
void mom(){
    while(1){
       //prepare an orange
       P(plate);
       put the orange on the plate;
       V(orange);  //orange标记为1，证明盘子有orange
   }
}
 
void daughter(){
    while(1){
       P(apple) 
       take an apple from the plate;
       V(plate);  //plate标记为1，证明可以放水果了
       eat the apple;
   }
}
 
void son(){
    while(1){
       P(orange) 
       take an orange from the plate;
       V(plate);  //plate标记为1，证明可以放水果了
       eat the orange;
   }
}

2.3 读者和写者问题

• 问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
• 问题分析

（1）关系分析：有两个进程：读者进程和写者进程，写者和读者、写者和写者都是互斥的，读者和读者是同步关系（依次访问，依次退出），可以同时有多个读者在读

（2）整理思路：写者是跟任何进程互斥，用PV可以解决，读者比较复杂，除了实现与写者的互斥，还要实现与其他读者的同步，设计了一个计数器来判断当前是否有读者读文件，同时，不同读者对计数器的访问也应该是互斥的

（3）信号量设置：首先设置信号量count为计数器，用来记录当前读者数量，初值为0; 设置rmutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。

#define semaphore int
semaphore rmutex=1; //读者之间（依次访问和退出）的互斥量
semaphore wmutex=1; //写者和读者的互斥量
int count=0; //统计读者的数量
 
void reader(){
     
    while(1){
        
    P(rmutex)
    if(count==0) P(wmutex); //count==0 意味着没有读者在读文件，可以写文件，先进行加锁
    count++;
    V(rmutex)
    
    reading; //读者进入之后，进行写文件
    
    P(mutex);
    count--;
    if(count==0)
        
        V(wmutex); //count==0证明读者已经读完退出文件，可以写，并将互斥量解锁
    V(rmutex); //释放互斥变量
 
 }
}
 
void writer(){
 
    while(1){
     
    P(wmutex);
    writing;
    V(wmutex);
 }
}

2.4 哲学家进餐（死锁）

• 问题描述：一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭，如图2-10所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、 右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
• 补充：饥饿和死锁的定义

“饥饿”并不表示系统一定死锁，但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别有：

（1）进入“饥饿”状态的进程可以只有一个，而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。

（2）处于“饥饿”状态的进程可以是一个就绪进程，如静态优先权调度算法时的低优先权进程，而处于死锁状态的进程则必定是阻塞进程。

• 问题分析：

（1）关系分析：5个哲学家和左右邻居对其中间的筷子访问是互斥关系

（2）整理思路：本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个，一个是让他们同时拿两个筷子；二是对每个哲学家的动作制定规则，避免饥饿或者死锁现象的发生。

（3）信号量设置：定义互斥信号量数组chopstick[5] = {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。对哲学家按顺序从0～4编号，哲学家i左边的筷子编号为i，哲学家右边的筷子编号(i+1)%5。（同时拿两边的筷子）

#define semaphore int
semaphore chopstick[5]={1,1,1,1,1}
 
Pi(){
    
    while(1){
    P(chopstick[i]);  //拿左筷子
    P(chopstick[(i+1)%5]);   //拿右筷子
    eat; //进餐
    V(chopstick[i]);  //放下左筷子
    V(chopstick[(i+1)%5]);   //放下右筷子
    think; //思考
  }
 
}

该算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷子的时候（都恰好执行完P(chopstick[i]);)筷子已经被拿光了，等到他们再想拿右边的筷子的时候（执行 P(chopstick[(i+l)%5]);)就全被阻塞了，这就出现了死锁。

为了防止死锁的发生，可以对哲学家进程施加一些限制条件，比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号，要求奇数号哲学家先抓左边的筷子，然后再转他右边的筷子，而偶数号哲学家刚好相反。正解制定规则如下：假设釆用第二种方法，当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子。

semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l;  //设置取筷子的信号量
Pi(){ //i号哲学家的进程
    while(1){
        P (mutex) ; //在取筷子前获得互斥量
        P (chopstick [i]) ; //取左边筷子
        P (chopstick[ (i+1) %5]) ;  //取右边筷子
        V (mutex) ; //释放取筷子的信号量
        eat;  //进餐
        V(chopstick[i] ) ;  //放回左边筷子
        V(chopstick[ (i+l)%5]) ;  //放回右边筷子
        think;  // 思考
    }
}

参考内容：

信号量：整型、记录型信号量以及利用信号量实现进程互斥和前驱关系_C语言中文网