5、临界区算法与信号量实现.md

# 信号与信号量

* 在需要同步的位置上，进程将自己阻塞起来等待信号；当该进程所依赖的进程执行到步调一致以后，会向操作系统发出信号；

* 操作系统收到信号以后，将阻塞进程唤醒执行。 



信号量的准确定义：

* （1）信号量就是一个整型变量，用来记录和进程同步有关的重要信息；
* （2）能让进程阻塞睡眠在这个信号量上；
* （3）需要同步的进程通过操作（加 1 和减 1）信号量实现进程的阻塞和唤醒，即进程间的同步。因此，**信号量就是一个数据对象以及操作这个数据对象的两个操作**
  * 其中数据对象是信号量数值以及相应的阻塞进程队列
  * 而在这个数据对象上的两个操作就是对信号量数值的加 1 和减 1，并根据加减后的信号量数值决定的睡眠和唤醒。



```c
struct semaphore
{
    int value;  //信号量数值，用来记录资源个数或进程个数
    PCB *queue; //等待在该信号量上的进程队列    
}

//进行减 1 的操作
//根据减去 1 以后的信号量数值来进程决定是否睡眠等待
P(semaphore s) 
{
    s.value--;
    if(s.value<0)
    sleep_on(s.queue);    
}

//进行加 1 的操作
//根据加上 1 以后的信号量数值决定是否要唤醒睡眠在该信号量上的进程。
V(semaphore s) 
{
    s.value++;
    if(s.value <= 0)
    wake_up(s.queue);
}
```





生产者---消费者同步问题的信号量解法

* 生产者在缓存区满了以后会睡眠等待，此处要定义一个信号量，当这个信号量的数值为 0 时，生产者要执行 P 操作以后会睡眠等待。
  * 所以此处定义的信号量是用 0 来表示缓存区满。因此这个信号量表达的含义就应该是缓存区中空闲单元的个数，所以可以命名为 empty，初值为 BUFFER_SIZE，生产者对 empty 信号量执行 P 操作，而消费者对 empty 信号量执行 V 操作。
* 类似的，可以分析出消费者进程在缓存区中没有 item 时会阻塞
  * 所以对应的信号量为 0 时要表达出缓存区中没有 item 这样的语义，所以该信号量要表达的含义就是缓存区中的 item 个数，可命名为 full，初值为 0。
* 另外，由于是共享缓存区，当某个进程进入共享缓存区进行修改时，其他进程不能使用缓存区的，只能睡眠等待。有睡眠等待就是一个同步点，因此需要再定义一个信号量来实现这个同步点。
  * 由于只能让 1 个进程修改缓存区，所以这个信号量的初值应该为 1，一旦某个进程进入以后就应该将其减为 0 （对应 P 操作）。
  * 此时当其他进程再想修改缓存区时，对该信号量的 P 操作会导致进程阻塞等待。根据语义，这个信号量的含义是互斥进入，所以将其命名为 mutex，初值为 1



信号量的命名与初值

* 关键点：阻塞即将发生（再来一个就发生）的条件，即信号量为 0 时的含义
  * 比如生产者，阻塞条件为产品满了，所以生产者阻塞的信号量为 0 时就代表产品敲好满了，所以等待减少来缓解，那就叫 empty
  * 比如消费者，阻塞条件为产品空了，所以生产者阻塞的信号量为 0 时就代表产品敲好空了，所以等待增加来缓解，那就叫 full

* 命名：阻塞即将发生时（即信号量为 0 时），等待消除阻塞的条件名
* 初值：根据信号量为 0 时的语义决定，每种信号量语义不同



根据上面的分析，生产者 消费者同步问题的信号量解法就不难给出了

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121002354326.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)

# 临界区

归根结底，信号量的作用就是根据信号量数值表达出来的语义来决定进程的停与走。

* 比如信号量的当前值为 -1，表达出来的语义就是现在有一个进程等待在这个信号量上，如果再来一个进程执行 P 操作（即要继续减 1，相当于继
  续申请资源），此时该进程应该睡眠等待在该信号量上。
* 而如果再来的进程执行的是 V 操作（即要给信号量加 1，相当于释放资源），则唤醒睡眠在该信号量上的一个进程。



因此，信号量的数值非常重要，只有信号量的数值时刻与信号量对应的语义信息保持一致，才能正确地使用信号量来决定进程的同步（停与走）。

* 多个进程可以对某个共同的信号量任意修改，但必须是一个进程修改完成以后才能让别的进程修改。
* 也可以换一种说法，就是每个进程对信号量的修改要么一点不做，要么全部做完，中途不能被打断，即对信号量的修改必须是一个原子操作



临界区就是进程中的一段代码，这段代码和其它相关进程中的相关代码对应，一次至多只允许一个进程进入，即互斥进入。

* 之所以被称为临界区，是因为一旦进入了这段代码，操作系统的状态就发生了改变，现在就不能在进程之间随意切换了，而执行进程中的其它代码时是可以随意切换的。
* 信号量保护的实质就是让进程中修改信号量的代码变成为临界区代码。



## 软件实现

一个实现临界区的方法不仅要做到互斥进入，还应该考虑其他要求：

* 一、互斥进入，如果有多个进程要求进入空闲的临界区，一次仅允许一个进程进入；在任何时候，一旦已经有进程进入其自身的临界区，则其它所有试图进入相应临界区的进程都必须等待。
* 二、有空让进，如果没有进程处于临界区内且有进程请求进入临界区，则应该能让某个请求进程进入临界区执行，即不发生资源的死锁情况。
* 三、有限等待，有限等待意味着一个进程在提出进入临界区请求后，最多需要等待临界区被使用有限次以后，该进程就可以进入临界区。这样任何进程在临界区门口等待的时间是有限的，即不出现因等待临界区而造成的饿死情况。



轮换法

* 既然是要求互斥进入 一次只允许一个进程进入，最容易想到的方法就是“轮换法”

  * 即轮到进程 P0 进入时只能让 P0 进入，P0 进入以后再轮换到让进程 P1 进入，依次类推
  * 由于 turn 变量在任何时刻都只能取值为 0 或 1，所以图中的两个进程 P0 和 P1 在任何时候最多只能有一个进程在临界区中执行

  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121002414866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)


* 虽然轮换法能够实现多个进程互斥进入临界区，但也存在缺陷

  * 进程 P0 进入一次临界区以后，如果 P0 想再次进入其临界区时就只能等待 P1 进入一次才可以。
  * 即：没有实现临界区的有空让进





标记法

* 标记法的处理思想也很简单

  * 进程 P0 想进入临界区就打一个标记，即设置 flag[0]=ture
  * 打完标志以后扫描其他进程是否要进入临界区，如果其他进程都不进入这个进程就进入临界区，否则调用代码 while(flag[1]); 自旋等待。

  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121002432873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)

* 分析标记法的工作效果

  * 首先，是否可以保持互斥进入？可以保证，因为如果两个进程都在临界区中，则 flag[0] = falg[1] = ture，而又都没有停在 while(flag[0/1]); 的自旋循环上，说明 flag[0] = flag[1] = false，发生矛盾
  * 接下来需要分析是否能够做到用空让进，针对如下调度顺序，进程 P0 执行 flag[0]= true 后切换到进程 P1 执行，现在 P1 也请求进入临界区，从而flag[1] = true，现在 P1 会在 while(flag[0]); 上一直循环，直到发生调度为止（比如时间片到时）。现在进程 P0 会在 while(flag[1]); 上一直循环，P0 和 P1 两个进程都在临界区门口一直自旋，谁也进不去，尽管并没有进程在临界区内。

  

  

  

因此可以总结出这样的做法（Peterson 算法）

  * （1）用标记法判断进程是否请求进入临界区；

  * （2）如果进程想要进入临界区，就用轮换法给进程进行一个明确的优先排序；

  * （3）将标记法和轮换法两个方法融合在一起来实现临界区，这就是由 Gary L. Peterson 于 1981年提出著名的 Peterson 算法

      * 即另外一个进程不让当前线程进（标记），当前线程也不让自己进（轮转，如果两个线程都要进，肯定 turn 会被后来要进的线程改为不让它自己进，所以先到的线程就进去了）

    ​	![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121002637824.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)






 



Lamport 面包店算法

* 采用了“轮换 + 标记”以后，Peterson 算法的确做到通过软件实现了对临界区的保护，但 Peterson 算法只能处理两个进程的临界区，现实系统中的临界区往往要涉及到很多进程。这就诞生了 Lamport 面包店算法，该算法是解决多进程临界区问题的算法，由 Leslie Lamport发明。

  ```c
  do
  {
      choosing[i] = true;
      number[i] = maxnumber[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));
          //(a,b)<(c,d) 意味着 a<c 或 a==c 且 b<d
      }
      
      ······//临界区代码
          
      number[i] = 0;
  }while(true); //Lamport 面包店算法中进程 i 的进入区和退出区代码
  ```

* 面包店算法是 Peterson 算法的扩展，也满足“轮换 + 标记”的基本思想

  * 其中选号过程相当于打“标记”的过程，
  * 而号码最小的进程进入相当于“轮换”。

* 所以推广 Peterson 算法在“互斥进入、有空让进和有限等待”上的分析过程，不难看出面包店算法也满足临界区保护的三个条件





## 硬件实现

* 虽然 Lamport 给出的面包店算法的确解决了多个进程对临界区的互斥访问问题，但是面包店算法的缺点也是明显的，那就是效率问题。
  * 选取号码、号码维护、号码判断等操作的代价都不小。
  * 另外在产生号码时总是要比当前所有的号码都要大，这就有可能导致号码溢出的情况，这也必须要完成而且又比较费时的处理。
* 在计算机系统中，当软件实现变得很复杂时，通
  常会想到的方法就是让硬件帮忙来简化操作，提高效率。



对于只有一个 CPU 的计算机

* 如果在进程进入临界区以后时能阻断调度，即不让系统发生调度，就不会出现“进程在临界区中
  执行而 CPU 又切换到其他进程，又进入另一个临界区的情况。”

* 如何不让调度/切换发生，根据内核级线程切换的实现原理，切换需要调用 schedule() 函数，而需要进入内核才能调用 schedule() 函数，要进入内核又需要中断。所以如果能禁止中断，上述 CPU 切换就不发生了。

* 因此，禁止中断是一种实现临界区保护的方法

  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121002703947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)




开/关中断的确是保护临界区的简单而有效的方法，但该方法也存在一个很大的缺陷，即只能工作在单 CPU 计算机系统下。

* 对于一个多 CPU 计算机（多核或多处理器），这个关中断操作对其他 CPU 没有影响，别的 CPU 照样可以执行任何任务，当然完全可以执行另一个要进入临界区的进程并让其进入临界区。
* 要用硬件实现 lock 操作的原子性。这种方法被称为硬件原子指令法。




# 信号量实现与使用

* 临界区保护了信号量 P、V 操作的原子性，从而能够保证信号量数值的语义正确性，接下来根据信号量数值所表达出来的正确语义我们就可以正确地控制进程的阻塞和唤醒了。
* 现在用户就可以定义信号量并调用信号量的 P、V 操作来实现多个进程的同步了。



## 信号量接口

根据信号量的含义：

* （1）信号量是一个需要被多个进程共享的整数；
* （2）要根据信号量对应的整数进程会 sleep_on 和 wake_up，这两个动作操作的对象是进程 PCB；
* （3）在操作这个整数时要进行临界区保护，可以调用面包店算法、开关中断操作等等。



不管从这三个方面中的哪一个方面来说，应该将信号量的实现放在操作系统内核，并将信号量的 P、V 操作实现成系统调用

* 因为将一个变量放在操作系统内核以后所有进程就可以共享了
* 另一方面在操作系统内核中操作 PCB、进行开关中断等动作既简单可行、安全可靠，又能向用户屏蔽细节。
* 通常，信号量实现为操作系统内核中的一个数据对象，而 P、V 操作实现为操作系统给上层用户程序提供的两个系统调用。



POSIX 标准针对信号量定义了如下四个基本系统调用：

* `sem_t *sem_open(const char *name, int oflag, mode_t mode,unsigned int value);`

* 这个系统调用用来打开或创建一个信号量变量，其中 name 信号量的名字，oflag可以选择创建一个新的信号量或打开一个现有的信号量。当然也可以用名字来区别是创建一个新的信号量还是打开现有的信号量，mode 是权限位，value 是信号量的初始值。

* `int sem_unlink(count char *name);`

  * 用来根据名字从操作系统中删除信号量。

* `int sem_wait(sem_t *sem); `

  `int sem_post(sem_t *sem);`

  * 这两个系统调用对应信号量的 P 操作和 V 操作。



如果要编写一个应用程序“pc.c”来模拟经典的生产者 消费者问题：

（1）建立 1 个生产者进程，5 个消费者进程；

（2）通过操作同一个文件来建立一个共享缓冲区；

（3）生产者进程依次向缓冲区文件写入整数 0,1,2,...,499；

（4）每个消费者进程从缓冲区文件中读取 100 个数，每读取一个数字就打印到标准输出上；

（5）缓冲区最多只能保存 10 个数，即缓冲区文件中最多存放 10 个数。

* 利用上面定义的和信号量有关的系统调用，可是实现这个 pc.c 程序：

  ```c
  main()
  {
      if(!fork()) { //生产者进程
          empty = sem_open(”empty”, 10); //只用了名字和初值两个参数
          full = sem_open(”full”, 0);
          mutex = sem_open(”mutex”, 1);
          for (i = 0; i< 500; i++) {
              sem_wait(empty);
              sem_wait(mutex);
              读写文件的操作;
              sem_post(mutex);
              sem_post(full);
      	}
  	}
      if(!fork()) { //第 1 个消费者进程
          empty = sem_open(”empty”, 10);
          ······ //其他内容类似
  ```



## 信号量实现

如何实现 sys_sem_wait 和 sys_sem_post 这两个系统调用

* 这两个系统调用的核心是对系统内核中的一个整型变量进行操作，并根据整型变量的数值决定是否要做进程的睡眠或唤醒，这里涉及了一个阻塞队列的维护操作。

* sys_sem_wait 

  ```c
  sys_sem_wait(sem_t *sem)
  {
      cli(); // 进入区代码，也可以是 Lamport 面包店算法、硬件原子指令法等等
      sem->value -- ; //sem 的结构定义可以很直观的想到，此处略去
      if((sem->value) < 0)
      {
          current->state = SLEEP; 
          // ... 将当前进程阻塞将当前进程（如 current 指针）追加到 sem->queue 队列的尾部;
          schedule(); //调用 schedule 切换到别的进程，由于当前进程已阻塞
      }
      sti(); //退出区代码，和进入区代码对应
  }
  ```

* sys_sem_post

  ```c
  sys_sem_post(sem_t *sem)
  {
      cli();
      sem->value ++ ;
      if((sem->value) <= 0)
      {
          //....从 sem->queue 队列的首部取出一个进程 p;
          p->state = READY; //设为就绪态将 p 加入到就绪队列中;
      }
      sti();
  }
  ```





重构：信号量只取正数、sem_wait 用 while 检测、sem_post 唤醒队列中的所有进程、

* 正值信号量表示现在有的资源个数，而负值信号量表示有多少进程等待在该信号量上。有正有负的信号量容易理解，根据信号量的正负性可以直观地判断出进程是要阻塞还要唤醒。

* 但有正有负的信号量实现存在一个问题：新来一个资源时，信号量增加 1，会在阻塞队列上唤醒 1 个进程，现在就出现问题了：“应该唤醒哪个进程？”

  * 可以在进程放入信号量阻塞队列时就进行优先排序，那么此处又需要写一个复杂的调度算法。
  * 实际上完全可以、也应该使用 schedule() 函数给出的进程调度策略来做这个选择，因为 schedule() 函数本来就是决定让哪个进程先执行的

* 所以在 sem_post 决定要唤醒队列上的哪个进程时，更好地解决办法唤醒阻塞在信号量上的所有进程，然后由 CPU 调度算法 schedule() 来决定让哪个进程获得这个信号量。

  * 在所有等待进程被唤醒时，都要重新检测看自己是否得到了信号量，如果发现自己获得了信号量就继续执行，如果发现自己没有获得信号量，就继续阻塞。
  * 由于进程被唤醒以后要再次检测自己是否获得了信号量，所以在 sem_wait 中，当从 if((sem->value) < 0) { 中的 schedule(); 处醒来以后，不能直接向前推进，而是应该再次判断信号量条件
  * 另一方面，由于每次都是将信号量阻塞队列中的所有进程都唤醒，所以就没有必要记录信号量上的等待进程个数信息（即信号量负值时的语义），因此信号量就不能出现负数了。

  ```c
  sys_sem_wait(sem_t *sem)
  {
      cli();
      while((sem->value) == 0)
      {
          //...将当前进程加入到 sem->queue 队列尾部;
          schedule();
      }
      sem->value -–;
      sti();
  }
  ```

  ```c
  sys_sem_post(sem_t *sem)
  {
      cli();
      sem->value ++ ;
      //...让 sem->queue 中的所有进程就绪并加入就绪队列;
      //当然，如果 sem->queue 为空就什么也不做了
      sti();
  }
  ```