计算机操作系统（6） （经典进程同步问题）

系列文章目录

第二章：进程的描述与控制

前言

  上节我们简单的讲述了整型信号量和记录型信号量的定义和wait，signal操作的方式，但是这些讲述的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况，而在有些应用场合， 是一个进程往往需要获得两个或更多的共享资源后方能执行其任务，所以有了AND型信号量和以它为基础的信号量集的出现，下面我们开始详细的讲述一下子。

一、AND型信号量：

    出现原因（自身理解）

这里我还是想给大家先强调一下为啥会出现AND型呢，因为我们如果没有AND型信号量的话，就比如说我们有两个进程A,B，它们都要求访问共享资源D，E，当然共享资源都做为临界资源，所以我们肯定要设置用于互斥的信号量Dmutex和Emutex，并令它们的初值都是1.我们来分析一下这个过程看有没有什么surprise。

Process A：                   Process B:
 wait(Dmutex);                  wait(Emutex);
 wait(Emutex);                  wait(Dmutex);
 若进程A和B按下述次序交替执行wait操作：
Process A:wait(Dmutex);  于是Dmutex = 0;
Process B:wait(Emutex);  于是Emutex = 0;
Process A:wait(Emutex);  于是Emutex = -1;
Process B:wait(Dmutex);  于是Dmutex = -1；

   这样进程A和B就将处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来，我们称此时的进程A和B已进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程的死锁的可能性也就会越大。

    我们接下来再拿一个Java线程当中的死锁举个例子。

package com.yuan5;

/**
 * @author 袁敬尧
 * @version 1.0
 */
public class DeadLock_ {
    public static void main(String[] args) {
        DeadLock deadLock1 = new DeadLock(true);
        DeadLock deadLock2 = new DeadLock(false);
        deadLock1.start();
        deadLock2.start();
    }
}

class DeadLock extends Thread {
    static Object ob1 = new Object();
    static Object ob2 = new Object();//保证多线程，共享一个对象
    boolean flag;

    public DeadLock(boolean flag) {
          this.flag = flag;
    }

    @Override
    public void run() {
        if (flag) {
            synchronized (ob1) {
                System.out.println(Thread.currentThread().getName() + "A线程进入1");
                synchronized (ob2) {
                    System.out.println(Thread.currentThread().getName() + "A线程进入2");
                }
            }
        } else {
            synchronized (ob2) {
                System.out.println(Thread.currentThread().getName() + "B进程进入3");

                synchronized (ob1) {
                    System.out.println(Thread.currentThread().getName() + "B线程进入4");
                }
            }
        }
    }
}

    这个也是一种死锁，就是两个线程进来的时候可能也会阻塞，因为进程也具有异步性，我们没有办法即按照各自独自的，不可预知的速度向前推进。

定义和基本思想：

  其实AND同步机制的基本思想是：将进程在整个运行过程中所需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。所以这样就可避免上述的死锁情况的发生。

       定义：AND型信号量是一种多资源原子分配机制，要求进程在进入临界区前一次性获取所有需要的资源，若无法同时满足，则阻塞等待。这有效避免了因分步申请资源导致的死锁​（如哲学家就餐问题中的循环等待）。

        下面是伪代码的具体实现：

Swait(S1,S2,.....Sn)
{
   while(TRUE)
  {
    if(Si>=1&&...&&Sn>=1){

for(i=1;i<=n;i++)Si--;
break;

}
else{
 block();

}
    }
}  
Ssignal(S1,S2,.....Sn){

    while(TRUE){

     for(i = 1;i<=n;i++){
       Si++;
  wakeup();
     }
}
   } 

具体例子我们放到后面讲。

二、信号量集：

出现原因（自身理解）

      为啥会出现信号量集呢，就是因为也是不够使了，因为在前面说的记录型信号量机制中，wait和signal操作仅能对信号量进行加1或减1的操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时，便要进行N次wait操作，这显然也是低效的，甚至还会增加思索的概率。而为了确保系统安全性（其实我理解的就是你要运行肯定需要内存，肯定需要有个临界值，临界值以下的内存肯定是用来运行的），所以当进程申请某类资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

   基于上述两点，可以对AND型信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P,V原语操作中完成申请获释放。进程对信号量Si的测试值不再是1，而是该资源的分配下限值ti,即要求Si>=ti，否则不予分配。一旦允许分配，进程对该资源的需求值为di，即表示资源的占用量，进行Si = Si-di操作，而不是简单的减1.

    即操作分别为Swait(S1,T1,D1,.....,Sn,tn,dn);

                         Ssignal(s1,d1,......,sn,dn);

     注意：Swait(S,1,1)此时的信号量集已蜕化为一般的记录型信号量(S>1时)或互斥信号量（S=1时）。

        Swait(S,1,0)这是一种很特殊且很有用的信号量操作。当S>=1,允许多个进程进入特定某特定区，当S变为0后，将阻止任何进程进入特定区，换言之，它相当于一个可控开关。

定义：

 信号量集是一组信号量的集合，允许进程通过单次系统调用对多个信号量进行复合操作​（如同时P或V多个信号量）。其核心目标是减少同步操作的开销，并支持更复杂的资源管理策略。

 核心操作：

三、经典同步问题----哲学家就餐

    这里面如果用记录型信号量有可能会出现死锁的问题

RecordSemaphore chopsticks[5];  // 5根筷子，初始值为1

void philosopher(int i) {
    while (1) {
        think();
        P(&chopsticks[i]);               // 申请左边筷子
        P(&chopsticks[(i+1) % 5]);       // 申请右边筷子
        eat();
        V(&chopsticks[i]);               // 释放左边筷子
        V(&chopsticks[(i+1) % 5]);       // 释放右边筷子
    }
}

   因为

• 循环等待条件成立：所有哲学家同时拿起左边筷子后，右边筷子均被占用。
• ​每个哲学家阻塞在第二个P操作，系统陷入死锁。

   这里面我们就可以用AND型信号量了，一个进程必须把所有需要的资源都占用才能执行。

// 定义AND型P操作（基于记录型信号量）
void AND_P(RecordSemaphore *sems[], int n) {
    bool all_available = true;
    for (int i = 0; i < n; i++) {
        if (sems[i]->value <= 0) {
            all_available = false;
            break;
        }
    }
    if (!all_available) {
        for (int i = 0; i < n; i++) {
            P(sems[i]);  // 原子性检查失败则阻塞
        }
    } else {
        for (int i = 0; i < n; i++) {
            sems[i]->value--;  // 直接分配资源
        }
    }
}

void philosopher(int i) {
    while (1) {
        think();
        RecordSemaphore *needed[] = {&chopsticks[i], &chopsticks[(i+1)%5]};
        AND_P(needed, 2);  // 原子性申请两根筷子
        eat();
        V(&chopsticks[i]);
        V(&chopsticks[(i+1)%5]);
    }
}

其实还有其他方案 例如只有四个人同时占用筷子

RecordSemaphore table = {4, empty_queue};  // 最多允许4人并发

void philosopher(int i) {
    while (1) {
        think();
        P(&table);                     // 先抢占“席位”
        P(&chopsticks[i]);
        P(&chopsticks[(i+1)%5]);
        eat();
        V(&chopsticks[i]);
        V(&chopsticks[(i+1)%5]);
        V(&table);
    }
}

• AND型信号量通过原子性多资源分配，​直接解决死锁问题，适合固定资源组的场景。
• ​信号量集通过复合操作，​降低同步开销并支持灵活策略，适合动态资源管理。

四、总结

    这就是我今天要讲的内容，简单的总结了一下AND型信号量和信号量集的思想，和一个经典的线程同步问题，哲学家就餐，下面我会继续更新经典的线程同步问题，如生产者消费者，读者-写者问题等等。谢谢大家，我会持续更新的。