清华大学操作系统Lab7实验报告
课程主页：http://os.cs.tsinghua.edu.cn/oscourse/OS2018spring
实验指导书：https://chyyuu.gitbooks.io/ucore_os_docs/content/
github：https://github.com/chyyuu/ucore_os_lab

实验目的

• 理解操作系统的同步互斥的设计实现；
• 理解底层支撑技术：禁用中断、定时器、等待队列；
• 在ucore中理解信号量（ semaphore） 机制的具体实现；
• 理解管程机制，在ucore内核中增加基于管程（ monitor） 的条件变量（ condition variable） 的支持；
• 了解经典进程同步问题，并能使用同步机制解决进程同步问题。

练习1：理解内核级信号量的实现和基于内核级信号量的哲学家就餐问题

为了完成Lab7的练习1，首先需要对之前的代码做一些修改。在trap.c的trap_dispatch中：

    case IRQ_OFFSET + IRQ_TIMER:
        run_timer_list();
        break;

完成之后，运行make grade，所有测试均能通过。结果如下。

练习1测试结果

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

内核级信号量的实现主要包含信号量数据结构semaphore_t和实现P操作的函数down以及实现V操作的函数up

• semaphore_t：信号量数据结构。value是一个计数器，wait_queue是等待队列。

typedef struct {
    int value;
    wait_queue_t wait_queue;
} semaphore_t;

• down：完成了信号量中的P操作。该函数主要调用了__down函数。__down函数中，首先关掉中断，然后判断信号量的value值是否大于0，如果大于0说明资源未被占用，则将value值减一并退出。若value值小于或等于0，则说明资源已经被占用，因此该进程需要等待。将该进程加入到等待队列中，开中断，然后进行调度。如果之后被V操作唤醒，则先关中断，将该进程从等待队列中删除，再开中断。

static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        sem->value --;
        local_intr_restore(intr_flag);
        return 0;
    }
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state);
    local_intr_restore(intr_flag);

    schedule();

    local_intr_save(intr_flag);
    wait_current_del(&(sem->wait_queue), wait);
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        return wait->wakeup_flags;
    }
    return 0;
}

• up：完成了信号量中的V操作。该函数主要调用了__up函数。在__up中，首先关中断，如果当前等待队列为空则直接将value值加一，否则如果有进程在等待且进程等待的原因是semophore设置的，则调用wakeup_wait函数将waitqueue中等待的第一个wait删除，且把此wait关联的进程唤醒，最后开中断返回。

static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
            sem->value ++;
        }
        else {
            assert(wait->proc->wait_state == wait_state);
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
        }
    }
    local_intr_restore(intr_flag);
}

在实验中，实现了应用信号量机制的哲学家问题。

程序的入口是check_sync函数。首先初始化了mutex信号量和五个哲学家对应的信号量s[i]，然后针对五个哲学家创建了五个进程来运行philosopher_using_semaphore函数。

void check_sync(void){

    int i;

    //check semaphore
    sem_init(&mutex, 1);
    for(i=0;i<N;i++){
        sem_init(&s[i], 0);
        int pid = kernel_thread(philosopher_using_semaphore, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_semaphore failed.\n");
        }
        philosopher_proc_sema[i] = find_proc(pid);
        set_proc_name(philosopher_proc_sema[i], "philosopher_sema_proc");
    }
    ......
}

philosopher_using_semaphore函数的内容如下。观察循环体里的内容可以发现，哲学家循环进行思考（第一次do_sleep(SLEEP_TIME)）、拿起两只叉子（或者被阻塞，phi_take_forks_sema(i)）、进餐（第二次do_sleep(SLEEP_TIME)）、放回两只叉子（phi_put_forks_sema(i)）这四个操作。

int philosopher_using_semaphore(void * arg) /* i：哲学家号码，从0到N-1 */
{
    int i, iter=0;
    i=(int)arg;
    cprintf("I am No.%d philosopher_sema\n",i);
    while(iter++<TIMES)
    { /* 无限循环 */
        cprintf("Iter %d, No.%d philosopher_sema is thinking\n",iter,i); /* 哲学家正在思考 */
        do_sleep(SLEEP_TIME);
        phi_take_forks_sema(i); 
        /* 需要两只叉子，或者阻塞 */
        cprintf("Iter %d, No.%d philosopher_sema is eating\n",iter,i); /* 进餐 */
        do_sleep(SLEEP_TIME);
        phi_put_forks_sema(i); 
        /* 把两把叉子同时放回桌子 */
    }
    cprintf("No.%d philosopher_sema quit\n",i);
    return 0;    
}

涉及到信号量的使用的主要是phi_take_forks_sema和phi_put_forks_sema两个函数。

在phi_take_forks_sema函数中，哲学家尝试拿起两个叉子。如果得到两只叉子则流程继续，否则阻塞（等待对应的信号量被释放）。

void phi_take_forks_sema(int i) /* i：哲学家号码从0到N-1 */
{ 
        down(&mutex); /* 进入临界区 */
        state_sema[i]=HUNGRY; /* 记录下哲学家i饥饿的事实 */
        phi_test_sema(i); /* 试图得到两只叉子 */
        up(&mutex); /* 离开临界区 */
        down(&s[i]); /* 如果得不到叉子就阻塞 */
}

在phi_put_forks_sema函数中，哲学家放下两只叉子。

void phi_put_forks_sema(int i) /* i：哲学家号码从0到N-1 */
{ 
        down(&mutex); /* 进入临界区 */
        state_sema[i]=THINKING; /* 哲学家进餐结束 */
        phi_test_sema(LEFT); /* 看一下左邻居现在是否能进餐 */
        phi_test_sema(RIGHT); /* 看一下右邻居现在是否能进餐 */
        up(&mutex); /* 离开临界区 */
}

在以上两个函数中，还调用了phi_test_sema(i)函数，用来测试第i个哲学家的左右两边的叉子是否都是可以获得的，如果可以则对这个哲学家的V操作。

void phi_test_sema(i) /* i：哲学家号码从0到N-1 */
{ 
    if(state_sema[i]==HUNGRY&&state_sema[LEFT]!=EATING
            &&state_sema[RIGHT]!=EATING)
    {
        state_sema[i]=EATING;
        up(&s[i]);
    }
}

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

（参考POSIX信号量实现机制）
用户态进程、线程的信号量机制依旧需要内核态的信号量机制支持，因此在内核部分沿用上面给出的内核态信号量实现。为了使用户态进程/线程可以调用内核态的信号量实现，需要添加相应的系统调用接口，主要包括以下几个：

• sem_open：打开或创建一个信号量并返回一个句柄以供后续调用使用，如果这个调用会创建信号量的话还会对所创建的信号量进行初始化。创建信号量时，将该信号量放置在内核态的一段共享内存中，可以供所有进程调用。
• sem_post和sem_wait：P操作和V操作接口。
• sem_getvalue：获取信号量当前的值。
• sem_close：删除调用进程与它之前打开的一个信号量之间的关联关系。
• sem_unlink：删除一个信号量名字并将其标记为在所有进程关闭该信号量时删除该信号量。

内核态信号量实现和用户态信号量实现的区别：

• 内核态信号量可以直接调用内核的服务，而用户态信号量需要通过系统调用接口调用内核态的服务，涉及到栈切换等等。
• 内核态信号量存储在内核态的内核栈上，而用户态信号量存储在内核中一段共享内存中。

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

内核级条件变量的哲学家就餐问题在check_sync处实现。同信号量的测试相似，这里也是创建了5个内核进程表示5个哲学家的行为。

void check_sync(void){
    int i;
    //check condition variable
    monitor_init(&mt, N);
    for(i=0;i<N;i++){
        state_condvar[i]=THINKING;
        int pid = kernel_thread(philosopher_using_condvar, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_condvar failed.\n");
        }
        philosopher_proc_condvar[i] = find_proc(pid);
        set_proc_name(philosopher_proc_condvar[i], "philosopher_condvar_proc");
    }
}

实现了哲学家行为的函数philosopher_using_condvar也和信号量实现的philosopher_using_semaphore相似。哲学家尝试4次思考->拿叉子->吃饭->放下叉子。

int philosopher_using_condvar(void * arg) { /* arg is the No. of philosopher 0~N-1*/
  
    int i, iter=0;
    i=(int)arg;
    cprintf("I am No.%d philosopher_condvar\n",i);
    while(iter++<TIMES)
    { /* iterate*/
        cprintf("Iter %d, No.%d philosopher_condvar is thinking\n",iter,i); /* thinking*/
        do_sleep(SLEEP_TIME);
        phi_take_forks_condvar(i); 
        /* need two forks, maybe blocked */
        cprintf("Iter %d, No.%d philosopher_condvar is eating\n",iter,i); /* eating*/
        do_sleep(SLEEP_TIME);
        phi_put_forks_condvar(i); 
        /* return two forks back*/
    }
    cprintf("No.%d philosopher_condvar quit\n",i);
    return 0;    
}

拿叉子和放下叉子的函数phi_take_forks_condvar和phi_put_forks_condvar内容需要自己填写。

phi_take_forks_condvar：首先进入管程，将哲学家状态改为HUNGRY，然后通过phi_test_condvar查看该哲学家对应的条件变量是否可以获得，如果不能则等待。最后退出管程。

void phi_take_forks_condvar(int i) {
     down(&(mtp->mutex));
     state_condvar[i] = HUNGRY;
     phi_test_condvar(i);
     if (state_condvar[i] != EATING) {
         cond_wait(&mtp->cv[i]);
     }
      if(mtp->next_count>0)
         up(&(mtp->next));
      else
         up(&(mtp->mutex));
}

phi_puta_forks_condvar：首先进入管程，将哲学家状态改为THINKING，然后通过phi_test_condvar查看该哲学家左右两位是否可以同时获得两把叉子，如果能则唤醒左右两个条件变量。最后退出管程。

void phi_put_forks_condvar(int i) {
     down(&(mtp->mutex));
     state_condvar[i] = THINKING;
     phi_test_condvar(LEFT);
     phi_test_condvar(RIGHT);
     if(mtp->next_count>0)
        up(&(mtp->next));
     else
        up(&(mtp->mutex));
}

条件变量用信号量来实现，在实验中，条件变量的wait和signal需要自己完成。

void 
cond_signal (condvar_t *cvp) {
   if (cvp->count > 0) {
       cvp->owner->next_count++;
       up(&(cvp->sem));
       down(&(cvp->owner->next));
       cvp->owner->next_count--;
   }
   cprintf("cond_signal end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

void
cond_wait (condvar_t *cvp) {
    cvp->count++;
    if (cvp->owner->next_count > 0) {
        up(&(cvp->owner->next));
    } else {
        up(&(cvp->owner->mutex));
    }
    down(&cvp->sem);
    cvp->count--;
    cprintf("cond_wait end:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

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

（参考自POSIX的条件变量接口）

我猜测用户态的条件变量实现机制可能和用户态的信号量实现机制类似。用户态进程、线程的条件变量机制依旧需要内核态的条件变量机制支持，因此在内核部分沿用上面给出的内核态条件变量实现。为了使用内核态条件变量的服务，增加以下几个系统调用接口：

• cond_init：创建条件变量，需要先初始化，并将该条件变量放置在内核态的一段共享内存中，可以供所有进程调用。
• cond_wait和cond_signal：wait和signal操作的接口。
• cond_broadcast：唤醒所有的的等待进程。
• cond_destroy：删除一个条件变量。

内核态条件变量实现和用户态条件变量实现的区别：

• 内核态条件变量可以直接调用内核的服务，而用户态条件变量需要通过系统调用接口调用内核态的服务，涉及到栈切换等等。
• 内核态条件变量存储在内核态的内核栈上，而用户态条件变量存储在内核中一段共享内存中。

请在实验报告中回答：能否不用基于信号量机制来完成条件变量？如果不能，请给出理由，如果能，请给出设计说明和具体实现。

能。模仿信号量的实现，可以通过开关中断来完成cond_wait和cond_signal的原子性。下面给出伪代码：

首先定义条件变量的结构体。其中需要一个计数器count来记录等待的进程数和一个等待队列wait_queue

typedef struct {
    int count;
    wait_queue_t wait_queue;
} cond_t;

接下来完成条件变量的wait操作。wait操作之前首先要关中断以保证其原子性。随后判断count是否为0，若为0则表明没有进程在占用该资源，直接使用即可；否则将自身挂起等待别的进程唤醒。

static __noinline uint32_t __wait(cond_t *cond, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    if (cond->count == 0) {
        cond->count ++;
        local_intr_restore(intr_flag);
        return 0;
    }
    wait_t __wait, *wait = &__wait;
    cond->count++;
    wait_current_set(&(cond->wait_queue), wait, wait_state);
    local_intr_restore(intr_flag);

    schedule();

    local_intr_save(intr_flag);
    wait_current_del(&(wait->wait_queue), wait);
    cond->count--;
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        return wait->wakeup_flags;
    }
    return 0;
}

void
cond_wait(cond_t *cond) {
    uint32_t flags = __wait(cond, WT_KCOND);
    assert(flags == 0);
}

条件变量的signal操作同样需要先关中断，然后唤醒等待列表上的第一个进程。

static __noinline void __signal(cond_t *cond, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(cond->wait_queue))) != NULL) {
            assert(wait->proc->wait_state == wait_state);
            wakeup_wait(&(cond->wait_queue), wait, wait_state, 1);
        }
    }
    local_intr_restore(intr_flag);
}

void
cond_signal(semaphore_t *cond) {
    __signal(cond, WT_KCOND);
}

覆盖的知识点

• 进程间同步互斥
• 信号量、条件变量、管程的具体实现
• 哲学家问题的实现

与参考答案的区别

• 练习1：自己完成。
• 练习2：自己完成。

总结

根据注释里的伪代码可以写对，但是理解不够透彻，还需要接下来练习来加深理解。