[关闭]
@JudyYe 2017-04-24T14:21:03.000000Z 字数 5941 阅读 759

LAB7 EXERCISE

UCORE_REPORT

练习0：填写已有实验

本实验依赖实验1/2/3/4/5/6。请把你做的实验1/2/3/4/5/6的代码填入本实验中代码中有"LAB1”/“LAB2”/“LAB
3”/“LAB4”/“LAB5”/“LAB6”的注释相应部分。并确保编译通过。注意：为了能够正确执行lab7的测试应用程序，可能需对已完成的实验1/2/3/4/5/6的代码进行进一步改进。

done
改变了trap_dispatch

练习1: 理解内核级信号量的实现和基于内核级信号量的哲学家就餐问题（不需要编码）

完成练习0后，建议大家比较一下（可用kdiff3等文件比较软件）个人完成的lab6和练习0完成后的刚修改的lab7之间的区别，分析了解lab7采用信号量的执行过程。执行make grade，大部分测试用例应该通过。

请在实验报告中给出内核级信号量的设计描述，并说其大致执行流流程。
请在实验报告中给出给用户态进程/线程提供信号量机制的设计方案，并比较说明给内核级提供信号量机制的异同。

信号量是一种同步互斥机制的实现，普遍存在于现在的各种操作系统内核里。相对于spinlock的应用对象，信号量的应用对象是在临界区中运行的时间较长的进程。等待信号量的进程需要睡眠来减少占用 CPU 的开销。

  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. }
  • __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. }

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

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

练习2: 完成内核级条件变量和基于内核级条件变量的哲学家就餐问题（需要编码）

首先掌握管程机制，然后基于信号量实现完成条件变量实现，然后用管程机制实现哲学家就餐问题的解决方案（基于条件变量）。

执行：make grade 。如果所显示的应用程序检测都输出ok，则基本正确。如果只是某程序过不去，比如matrix.c，则可执行 make run-matrix 命令来单独调试它。大致执行结果可看附录。（使用的是qemu-1.0.1）。

请在实验报告中给出内核级条件变量的设计描述，并说其大致执行流流程。

请在实验报告中给出给用户态进程/线程提供条件变量机制的设计方案，并比较说明给内核级提供条件变量机制的异同。

引入条件变量（Condition Variables，简称CV）。一个条件变量CV可理解为一个进程的等待队列，队列中的进程正等待某个条件C变为真。每个条件变量关联着一个断言 "断言 (程序)")Pc。当一个进程等待一个条件变量，该进程不算作占用了该管程，因而其它进程可以进入该管程执行，改变管程的状态，通知条件变量CV其关联的断言Pc在当前状态下为真。因此对条件变量CV有两种主要操作：

  • wait_cv： 被一个进程调用，以等待断言Pc被满足后该进程可恢复执行. 进程挂在该条件变量上等待时，不被认为是占用了管程。
  • signal_cv：被一个进程调用，以指出断言Pc现在为真，从而可以唤醒等待断言Pc被满足的进程继续执行。

ucore中的管程的数据结构monitor_t定义如下：

  1. typedef struct monitor{
  2.     semaphore_t mutex;      // the mutex lock for going into the routines in monitor, should be initialized to 1
  3.     semaphore_t next;       // the next semaphore is used to down the signaling proc itself, and the other OR wakeuped
  4.     //waiting proc should wake up the sleeped signaling proc.
  5.     int next_count;         // the number of of sleeped signaling proc
  6.     condvar_t *cv;          // the condvars in monitor
  7. } monitor_t;

管程中的成员变量信号量next和整形变量next_count是配合进程对条件变量cv的操作而设置的，这是由于发出signal_cv的进程A会唤醒睡眠进程B，进程B执行会导致进程A睡眠，直到进程B离开管程，进程A才能继续执行，这个同步过程是通过信号量next完成的；而next_count表示了由于发出singal_cv而睡眠的进程个数。

管程中的条件变量的数据结构condvar_t定义如下：

  1. typedef struct condvar{
  2.     semaphore_t sem; // the sem semaphore is used to down the waiting proc, and the signaling proc should up the waiting proc
  3.     int count;       // the number of waiters on condvar
  4.     monitor_t * owner; // the owner(monitor) of this condvar
  5. } condvar_t;

条件变量的定义中也包含了一系列的成员变量，信号量sem用于让发出wait_cv操作的等待某个条件C为真的进程睡眠，而让发出signal_cv操作的进程通过这个sem来唤醒睡眠的进程。count表示等在这个条件变量上的睡眠进程的个数。owner表示此条件变量的宿主是哪个管程。

cond_wait的原理描述

  1. cv.count++;
  2. if(monitor.next_count > 0)
  3.    sem_signal(monitor.next);
  4. else
  5.    sem_signal(monitor.mutex);
  6. sem_wait(cv.sem);
  7. cv.count -- ;

cond_signal的原理描述

  1. if( cv.count > 0) {
  2.    monitor.next_count ++;
  3.    sem_signal(cv.sem);
  4.    sem_wait(monitor.next);
  5.    monitor.next_count -- ;
  6. }

简单分析一下cond_wait函数的实现。可以看出如果进程A执行了cond_wait函数，表示此进程等待某个条件C不为真，需要睡眠。因此表示等待此条件的睡眠进程个数cv.count要加一。接下来会出现两种情况。

情况一：如果monitor.next_count如果大于0，表示有大于等于1个进程执行cond_signal函数且睡着了，就睡在了monitor.next信号量上。假定这些进程形成S进程链表。因此需要唤醒S进程链表中的一个进程B。然后进程A睡在cv.sem上，如果睡醒了，则让cv.count减一，表示等待此条件的睡眠进程个数少了一个，可继续执行了！这里隐含这一个现象，即某进程A在时间顺序上先执行了signal_cv，而另一个进程B后执行了wait_cv，这会导致进程A没有起到唤醒进程B的作用。这里还隐藏这一个问题，在cond_wait有sem_signal(mutex)，但没有看到哪里有sem_wait(mutex)，这好像没有成对出现，是否是错误的？其实在管程中的每一个函数的入口处会有wait(mutex)，这样二者就配好对了。

情况二：如果monitor.next_count如果小于等于0，表示目前没有进程执行cond_signal函数且睡着了，那需要唤醒的是由于互斥条件限制而无法进入管程的进程，所以要唤醒睡在monitor.mutex上的进程。然后进程A睡在cv.sem上，如果睡醒了，则让cv.count减一，表示等待此条件的睡眠进程个数少了一个，可继续执行了！

对照着再来看cond_signal的实现。首先进程B判断cv.count，如果不大于0，则表示当前没有执行cond_wait而睡眠的进程，因此就没有被唤醒的对象了，直接函数返回即可；如果大于0，这表示当前有执行cond_wait而睡眠的进程A，因此需要唤醒等待在cv.sem上睡眠的进程A。由于只允许一个进程在管程中执行，所以一旦进程B唤醒了别人（进程A），那么自己就需要睡眠。故让monitor.next_count加一，且让自己（进程B）睡在信号量monitor.next上。如果睡醒了，这让monitor.next_count减一。

为了让整个管程正常运行，还需在管程中的每个函数的入口和出口增加相关操作，即：

  1. function （…）
  2. {
  3. sem.wait(monitor.mutex);
  4.   the real body of function;
  5.   if(monitor.next_count > 0)
  6.      sem_signal(monitor.next);
  7.   else
  8.      sem_signal(monitor.mutex);
  9. }

这样带来的作用有两个，（1）只有一个进程在执行管程中的函数。（2）避免由于执行了cond_signal函数而睡眠的进程无法被唤醒。对于第二点，如果进程A由于执行了cond_signal函数而睡眠（这会让monitor.next_count大于0，且执行sem_wait(monitor.next)），则其他进程在执行管程中的函数的出口，会判断monitor.next_count是否大于0，如果大于0，则执行sem_signal(monitor.next)，从而执行了cond_signal函数而睡眠的进程被唤醒。上诉措施将使得管程正常执行。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注