信号量

信号量是一种同步互斥机制的实现，普遍存在于现在的各种操作系统内核里。相对于spinlock
的应用对象，信号量的应用对象是在临界区中运行的时间较长的进程。等待信号量的进程需要睡眠来减少占用
CPU 的开销。参考教科书“Operating Systems Internals and Design
Principles”第五章“同步互斥”中对信号量实现的原理性描述：

  1. struct semaphore {
  2. int count;
  3. queueType queue;
  4. };
  5. void semWait(semaphore s)
  6. {
  7. s.count--;
  8. if (s.count < 0) {
  9. /* place this process in s.queue */;
  10. /* block this process */;
  11. }
  12. }
  13. void semSignal(semaphore s)
  14. {
  15. s.count++;
  16. if (s.count<= 0) {
  17. /* remove a process P from s.queue */;
  18. /* place process P on ready list */;
  19. }
  20. }

基于上诉信号量实现可以认为，当多个（>1）进程可以进行互斥或同步合作时，一个进程会由于无法满足信号量设置的某条件而在某一位置停止，直到它接收到一个特定的信号（表明条件满足了）。为了发信号，需要使用一个称作信号量的特殊变量。为通过信号量s传送信号，信号量的V操作采用进程可执行原语semSignal(s)；为通过信号量s接收信号，信号量的P操作采用进程可执行原语semWait(s)；如果相应的信号仍然没有发送，则进程被阻塞或睡眠，直到发送完为止。

ucore中信号量参照上述原理描述，建立在开关中断机制和wait_queue的基础上进行了具体实现。信号量的数据结构定义如下：

  1. typedef struct {
  2.     int value;                   //信号量的当前值
  3.     wait_queue_t wait_queue;     //信号量对应的等待队列
  4. } semaphore_t;

semaphore_t是最基本的记录型信号量（record
semaphore)结构，包含了用于计数的整数值value，和一个进程等待队列wait_queue，一个等待的进程会挂在此等待队列上。

在ucore中最重要的信号量操作是P操作函数down(semaphore_t *sem)和V操作函数 up(semaphore_t *sem)。但这两个函数的具体实现是__down(semaphore_t *sem, uint32_t wait_state) 函数和__up(semaphore_t *sem, uint32_t wait_state)函数，二者的具体实现描述如下：

● __down(semaphore_t *sem, uint32_t wait_state, timer_t *timer)：具体实现信号量的P操作，首先关掉中断，然后判断当前信号量的value是否大于0。如果是>0，则表明可以获得信号量，故让value减一，并打开中断返回即可；如果不是>0，则表明无法获得信号量，故需要将当前的进程加入到等待队列中，并打开中断，然后运行调度器选择另外一个进程执行。如果被V操作唤醒，则把自身关联的wait从等待队列中删除（此过程需要先关中断，完成后开中断）。具体实现如下所示：

  1. static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
  2.     bool intr_flag;
  3.     local_intr_save(intr_flag);
  4.     if (sem->value > 0) {
  5.         sem->value --;
  6.         local_intr_restore(intr_flag);
  7.         return 0;
  8.     }
  9.     wait_t __wait, *wait = &__wait;
  10.     wait_current_set(&(sem->wait_queue), wait, wait_state);
  11.     local_intr_restore(intr_flag);
  13.     schedule();
  15.     local_intr_save(intr_flag);
  16.     wait_current_del(&(sem->wait_queue), wait);
  17.     local_intr_restore(intr_flag);
  19.     if (wait->wakeup_flags != wait_state) {
  20.         return wait->wakeup_flags;
  21.     }
  22.     return 0;
  23. }

与__down相关的调用和被调用函数关系图如下所示：

  2. digraph "__down" {
  3.   graph [bgcolor="#F7F5F3", fontname="Arial", fontsize="10", label="", rankdir="LR"];
  4.   node [shape="box", style="filled", color="blue", fontname="Arial", fontsize="10", fillcolor="white", label=""];
  5.   edge [color="#CC0044", fontname="Arial", fontsize="10", label=""];
  6.   graph [bgcolor="#F7F5F3"];
  7.   __N1 [color="red", label="__down"];
  8.   __N2 [label="__intr_save"];
  9.   __N3 [label="__intr_restore"];
  10.   __N4 [label="wait_current_set"];
  11.   __N5 [label="schedule"];
  12.   __N6 [label="wait_in_queue"];
  13.   __N7 [label="wait_queue_del"];
  14.   __N8 [label="down"];
  15.   __N9 [label="phi_take_forks_sema"];
  16.   __N10 [label="cond_signal"];
  17.   __N11 [label="phi_put_forks_sema"];
  18.   __N12 [label="cond_wait"];
  19.   __N13 [label="lock_mm"];
  20.   __N14 [label="phi_take_forks_condvar"];
  21.   __N15 [label="phi_put_forks_condvar"];
  22.   __N1 -> __N2;
  23.   __N1 -> __N3;
  24.   __N1 -> __N4;
  25.   __N1 -> __N5;
  26.   __N1 -> __N6;
  27.   __N1 -> __N7;
  28.   __N9 -> __N8;
  29.   __N10 -> __N8;
  30.   __N11 -> __N8;
  31.   __N12 -> __N8;
  32.   __N13 -> __N8;
  33.   __N14 -> __N8;
  34.   __N15 -> __N8;
  35.   __N8 -> __N1;
  36. }

● __up(semaphore_t *sem, uint32_t
wait_state)：具体实现信号量的V操作，首先关中断，如果信号量对应的wait
queue中没有进程在等待，直接把信号量的value加一，然后开中断返回；如果有进程在等待且进程等待的原因是semophore设置的，则调用wakeup_wait函数将waitqueue中等待的第一个wait删除，且把此wait关联的进程唤醒，最后开中断返回。具体实现如下所示：

  1. static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
  2.     bool intr_flag;
  3.     local_intr_save(intr_flag);
  4.     {
  5.         wait_t *wait;
  6.         if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
  7.             sem->value ++;
  8.         }
  9.         else {
  10.             wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
  11.         }
  12.     }
  13.     local_intr_restore(intr_flag);
  14. }

与__up相关的调用和被调用函数关系图如下所示：

  1. digraph "__up" {
  2.   graph [bgcolor="#F7F5F3", fontname="Arial", fontsize="10", label="", rankdir="LR"];
  3.   node [shape="box", style="filled", color="blue", fontname="Arial", fontsize="10", fillcolor="white", label=""];
  4.   edge [color="#CC0044", fontname="Arial", fontsize="10", label=""];
  5.   graph [bgcolor="#F7F5F3"];
  6.   __N1 [color="red", label="__up"];
  7.   __N2 [label="__intr_save"];
  8.   __N3 [label="wait_queue_first"];
  9.   __N5 [label="wakeup_wait"];
  10.   __N6 [label="__intr_restore"];
  11.   __N7 [label="up"];
  12.   __N8 [label="phi_test_sema"];
  13.   __N9 [label="phi_take_forks_sema"];
  14.   __N10 [label="cond_signal"];
  15.   __N11 [label="phi_put_forks_sema"];
  16.   __N12 [label="cond_wait"];
  17.   __N13 [label="unlock_mm"];
  18.   __N14 [label="phi_take_forks_condvar"];
  19.   __N15 [label="phi_put_forks_condvar"];
  20.   __N1 -> __N2;
  21.   __N1 -> __N3;
  22.   __N1 -> __N5;
  23.   __N1 -> __N6;
  24.   __N8 -> __N7;
  25.   __N9 -> __N7;
  26.   __N10 -> __N7;
  27.   __N11 -> __N7;
  28.   __N12 -> __N7;
  29.   __N13 -> __N7;
  30.   __N14 -> __N7;
  31.   __N15 -> __N7;
  32.   __N7 -> __N1;
  33. }

对照信号量的原理性描述和具体实现，可以发现二者在流程上基本一致，只是具体实现采用了关中断的方式保证了对共享资源的互斥访问，通过等待队列让无法获得信号量的进程睡眠等待。另外，我们可以看出信号量的计数器value具有有如下性质：

  • value>0，表示共享资源的空闲数
  • vlaue<0，表示该信号量的等待队列里的进程数
  • value=0，表示等待队列为空