uCoreOs lab7 实验报告

实验目的

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

实验内容

练习0：填写已有实验

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

要修改的文件有proc.c default_pmm.c pmm.c swap_fifo.c vmm.c trap.c kdebug.c

并将lab6的default_sched_stride.c复制到lab7，并对default_sched.h sched.c做修改

无需要在原代码基础上做进一步修改的代码

其中有个比较坑的地方需要做修改

此处需要和lab6一样改为MAX_TIME_SLICE

而且，比较奇怪的是，这个MAX_TIME_SLICE的值有时候能通过priority测验，有时候却不行，如果不行的话，可以将sched.h的MAX_TIME_SLICE的值进行调节（例如把20改成5）看是否能通过测验。

修改后执行make grade

测试均通过

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

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

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

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

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

本次实验的底层支撑

信号量原理

信号量结构体包括信号量计数值sem和等待队列q

查看sem.c的头文件

查看文件kern/process/proc.c

可以看到在进程中，调用check_sync这个函数来解决哲学家问题

分析check_sync函数

kern/sync/check_sync.c  
void check_sync(void){

    int i;

    //check semaphore
    sem_init(&mutex, 1);
    for(i=0;i<N;i++){   //N是哲学家的数量  
        sem_init(&s[i], 0);  //初始化信号量 
        //线程需要执行的函数名、哲学家编号、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");
    }

    //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");
    }
}

前半段是用信号量的方法，后半段是用管程的方法

pid用kernel_thread创建了一个内核线程，

其定义在kern/process/proc.c

其中fn表示内核线程执行的函数，arg表示传入的哲学家编号i，clone_flag表示共享内存的标志位

此处传入的函数为philosopher_using_semaphore，查看这个函数定义

kern/sync/check_sync.c
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;
}

传入参数*arg是哲学家的编号。

iter++<TIMES，表示循环4次，目的在于模拟多次试验情况。

其中用do_sleep这个延时函数来模拟哲学家的思考和进餐的过程，且睡眠过程是无法打断的。

另外还有phi_take_forks_sema(i)和phi_put_forks_sema(i)这两个函数，表示拿起叉子和放下叉子。

#define N 5 /* 哲学家数目 */
#define LEFT (i-1+N)%N /* i的左邻号码 */
#define RIGHT (i+1)%N /* i的右邻号码 */
#define THINKING 0 /* 哲学家正在思考 */
#define HUNGRY 1 /* 哲学家想取得叉子 */
#define EATING 2 /* 哲学家正在吃面 */
#define TIMES  4 /* 吃4次饭 */
#define SLEEP_TIME 10
void phi_test_sema(i) /* i：哲学家号码从0到N-1 */
{
    //检查左右两位是否在eating，如果均不在吃，可获得EATING状态
    if(state_sema[i]==HUNGRY&&state_sema[LEFT]!=EATING
            &&state_sema[RIGHT]!=EATING)
    {
        state_sema[i]=EATING;
        up(&s[i]);
    }
}
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]); /* 如果得不到叉子就阻塞 */
}
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); /* 离开临界区 */
}

其中mutex是二进制信号量结构体。

down代表P操作，up代表V操作

打开sem.c，sem.h，wait.h

有如下定义

// 先是定义了一个信号量的数据结构
typedef struct {
    int value; // 计数值 用于 PV操作
    wait_queue_t wait_queue; // 进程等待队列
} semaphore_t;

// 用于等待队列 存放了当前等待的线程PCB 和 唤醒原因 和 等待队列 和 用于还原结构体的等待队列标志
/*wakeup_flags取值如下
kern/process/proc.h
#define WT_INTERRUPTED               0x80000000                    // the wait state could be interrupted
#define WT_CHILD                    (0x00000001 | WT_INTERRUPTED)  // wait child process
#define WT_KSEM                      0x00000100                    // wait kernel semaphore
#define WT_TIMER                    (0x00000002 | WT_INTERRUPTED)  // wait timer
*/
typedef struct {
    struct proc_struct *proc;//当前进程
    uint32_t wakeup_flags; //唤醒标志
    wait_queue_t *wait_queue; //等待队列
    list_entry_t wait_link; //还原节点
} wait_t;

// 初始化信号量中的计数值和等待队列
void sem_init(semaphore_t *sem, int value) {
    sem->value = value;
    wait_queue_init(&(sem->wait_queue));
}

/*
    P操作 要关闭中断并保存 intr_flag 寄存器的值 避免共享变量被多个线程同时修改
    判断 计数值是否大于 0 
    	若大于 0 说明此时没有其他线程访问临界区 则直接将计数值 减 1 并 返回
    	若 计数值小于 0 则 已经有其他线程访问临界区了 就将当前线程放入等待队列中 并调用调度函数
    等到进程被唤醒 再将当前进程从等待队列中 取出并删去 最后判断等待的线程是因为什么原因被唤醒
*/
static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    //********************原子操作 start**********************************
    //如果信号量大于0，那么说明信号量可用，因此可以分配给当前进程运行，分配完之后关闭中断 
    if (sem->value > 0) {
        sem->value --;
        local_intr_restore(intr_flag);
        return 0;
    }
    
    //如果信号量数值小于零，那么需要将当前进程加入等待队列并调用schedule函数查找下一个可以被运行调度的进程，
    //此时，如果能够查到，那么唤醒，并将其中队列中删除并返回 
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state);//放入等待队列
    //********************原子操作end*************************************
    local_intr_restore(intr_flag);

    schedule(); //调度函数

    local_intr_save(intr_flag);
    //********************原子操作 start**********************************
    wait_current_del(&(sem->wait_queue), wait);//将当前进程从等待队列删除
    //********************原子操作end*************************************
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {//线程被唤醒，等待状态改变，返回新的等待状态
        return wait->wakeup_flags;
    }
    return 0;
}

/*
    V操作 也要关闭中断 并保存 intr_flag 寄存器的值 防止共享变量同时被多个线程访问或修改
    先判断等待队列是否为空 若为空 则将计数值 加 1 并返回
    若不为空 则说明还有线程在等待 此时取出等待队列的第一个线程 并将其 唤醒 唤醒的过程中 
    将其从等待队列中删除
*/
static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    //********************原子操作 start**********************************
    {
        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); //唤醒等待队列的第一个线程
        }
    }
    //********************原子操作end*************************************
    local_intr_restore(intr_flag);
}

整个执行过程如下

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

由于是用户态进程，不可以直接使用内核态的信号量，因此应该将内核级的信号量操作封装成系统调用供用户态调用。

异同点：

• 相同点：
  • 提供信号量机制的代码实现逻辑是相同的；
• 不同点：
  • 由于实现原子操作的中断禁用、Test and Set指令等均需要在内核态下运行，因此提供给用户态进程的信号量机制是通过系统调用来实现的，而内核级线程只需要直接调用相应的函数就可以了

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

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

执行：make grade 。如果所显示的应用程序检测都输出ok，则基本正确。如果只是某程序过不去，比如matrix.c，则可执行

make run-matrix

命令来单独调试它。大致执行结果可看附录。

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

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

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

该练习需要编程，查看需要编程的地方

这边写错了练习序号

管程实现机制

管程机制在monitor.c实现

// 管程数据结构
typedef struct monitor{
    semaphore_t mutex; // 二值信号量 用来互斥访问管程
    semaphore_t next; // 用于 条件同步 用于发出signal操作的进程等条件为真之前进入睡眠
    int next_count; // 记录睡在 signal 操作的进程数
    condvar_t *cv; // 条件变量
} monitor_t;

// 条件变量数据结构
typedef struct condvar{
    semaphore_t sem; // 用于条件同步 用于发出wait操作的进程等待条件为真之前进入睡眠
    int count; // 记录睡在 wait 操作的进程数(等待条件变量成真)
    monitor_t * owner; // 所属管程
} condvar_t;

// 初始化管程
void monitor_init (monitor_t * mtp, size_t num_cv) {
    int i;
    assert(num_cv>0);
    mtp->next_count = 0; // 睡在signal进程数 初始化为0
    mtp->cv = NULL;
    sem_init(&(mtp->mutex), 1); // 二值信号量 保护管程 使进程访问管程操作为互斥的
    sem_init(&(mtp->next), 0); // 条件同步信号量
    mtp->cv =(condvar_t *) kmalloc(sizeof(condvar_t)*num_cv); // 获取一块内核空间 放置条件变量
    assert(mtp->cv!=NULL);
    for(i=0; i<num_cv; i++){
        mtp->cv[i].count=0;
        sem_init(&(mtp->cv[i].sem),0);
        mtp->cv[i].owner=mtp;
    }
}

// Unlock one of threads waiting on the condition variable. 
// 管程signal操作
/*
分支1. 因为条件不成立而睡眠的进程计数小于等于0 时 说明 没有进程需要唤醒 则直接返回
分支2. 因为条件不成立而睡眠的进程计数大于0 说明有进程需要唤醒 就将其唤醒
同时设置 条件变量所属管程的 next_count 加1 以用来告诉 wait操作 有进程睡在了 signal操作上
然后自己将自己阻塞 等待条件同步 被唤醒 被唤醒后 睡在 signal 操作上的进程应该减少 故 next_count 应减 1
*/
void 
cond_signal (condvar_t *cvp) {
   //LAB7 EXERCISE1: YOUR CODE
   cprintf("cond_signal begin: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);  
  /*
   *      cond_signal(cv) {
   *          if(cv.count>0) {
   *             mt.next_count ++;
   *             signal(cv.sem);
   *             wait(mt.next);
   *             mt.next_count--;
   *          }
   *       }
   */
+   if (cvp->count > 0) { // 若存在因为当前条件变量而等待的进程的话
+       up(&(cvp->sem));
+       cvp->owner->next_count++; // 所属管程的 next 计数 加 1 表示当前进程会被等待者堵塞
+       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);
}

// Suspend calling thread on a condition variable waiting for condition Atomically unlocks 
// mutex and suspends calling thread on conditional variable after waking up locks mutex. Notice: mp is mutex semaphore for monitor's procedures
// 管程wait操作
/*
先将 因为条件不成立而睡眠的进程计数加1
分支1. 当 管程的 next_count 大于 0 说明 有进程睡在了 signal 操作上 我们将其唤醒
分支2. 当 管程的 next_count 小于 0 说明 当前没有进程睡在 signal操作数 只需要释放互斥体
然后 再将 自身阻塞 等待 条件变量的条件为真 被唤醒后 将条件不成立而睡眠的进程计数减1 因为现在成立了
*/
void
cond_wait (condvar_t *cvp) {
    //LAB7 EXERCISE1: YOUR CODE
    cprintf("cond_wait begin:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
   /*
    *         cv.count ++;
    *         if(mt.next_count>0)
    *            signal(mt.next)
    *         else
    *            signal(mt.mutex);
    *         wait(cv.sem);
    *         cv.count --;
    */
+   cvp->count++;//条件变量中睡眠的进程数量加加  
+   if (cvp->owner->next_count > 0) {
+       up(&(cvp->owner->next));//如果当前有进程正在等待，且睡在宿主管程的信号量上，此时需要唤醒，让该调用了wait的睡，此时就唤醒了，这是一个同步问题。 
+   } else {
+       up(&(cvp->owner->mutex));//如果没有进程睡眠，那么当前进程无法进入管程的原因就是互斥条件的限制。因此唤醒mutex互斥锁，代表现在互斥锁被占用，此时，再让进程睡在宿主管程的信号量上，如果睡醒了，count--
+   }

+   down(&(cvp->sem)); //因为条件不满足，所以主动调用wait的进程，会睡在条件变量cvp的信号量上，是条件不满足的问题；而因为调用signal唤醒其他进程而导致自身互斥睡眠，会睡在宿主管程cvp->owner的信号量上，是同步的问题 
+   cvp->count--;
    cprintf("cond_wait end:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

补充check_sync.c的代码

check_sync.c:
//-----------------philosopher problem using monitor ------------
/*PSEUDO CODE :philosopher problem using monitor
 * monitor dp
 * {
 *  enum {thinking, hungry, eating} state[5];
 *  condition self[5];
 *
 *  void pickup(int i) {
 *      state[i] = hungry;
 *      if ((state[(i+4)%5] != eating) && (state[(i+1)%5] != eating)) {
 *        state[i] = eating;
 *      else
 *         self[i].wait();
 *   }
 *
 *   void putdown(int i) {
 *      state[i] = thinking;
 *      if ((state[(i+4)%5] == hungry) && (state[(i+3)%5] != eating)) {
 *          state[(i+4)%5] = eating;
 *          self[(i+4)%5].signal();
 *      }
 *      if ((state[(i+1)%5] == hungry) && (state[(i+2)%5] != eating)) {
 *          state[(i+1)%5] = eating;
 *          self[(i+1)%5].signal();
 *      }
 *   }
 *
 *   void init() {
 *      for (int i = 0; i < 5; i++)
 *         state[i] = thinking;
 *   }
 * }
 */

struct proc_struct *philosopher_proc_condvar[N]; // N philosopher
int state_condvar[N];                            // the philosopher's state: EATING, HUNGARY, THINKING  
monitor_t mt, *mtp=&mt;                          // monitor

void phi_test_condvar (i) { 
    if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
            &&state_condvar[RIGHT]!=EATING) {
        cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
        state_condvar[i] = EATING ;
        cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
        cond_signal(&mtp->cv[i]) ;
    }
}


void phi_take_forks_condvar(int i) {
     down(&(mtp->mutex));// P操作进入临界区
//--------into routine in monitor--------------
     // LAB7 EXERCISE1: YOUR CODE
     // I am hungry
     // try to get fork
//--------leave routine in monitor--------------
+   state_condvar[i] = HUNGRY; // 饥饿状态 准备进食
+   phi_test_condvar(i); // 测试当前是否能获得刀叉 
+   while (state_condvar[i] != EATING) {
+       cond_wait(&mtp->cv[i]); // 若不能拿 则阻塞自己 等其它进程唤醒
+   }
      if(mtp->next_count>0)
         up(&(mtp->next));
      else
         up(&(mtp->mutex));
}

void phi_put_forks_condvar(int i) {
     down(&(mtp->mutex));// P操作进入临界区

//--------into routine in monitor--------------
     // LAB7 EXERCISE1: YOUR CODE
     // I ate over
     // test left and right neighbors
//--------leave routine in monitor--------------
+    state_condvar[i] = THINKING; // 思考状态
+    phi_test_condvar(LEFT); // 试试左右两边能否获得刀叉
+    phi_test_condvar(RIGHT);
     if(mtp->next_count>0)// 有哲学家睡在 signal操作 则将其唤醒
        up(&(mtp->next));
     else
        up(&(mtp->mutex));// 离开临界区
}

//---------- philosophers using monitor (condition variable) ----------------------
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;    
}


// 测试编号为i的哲学家是否能获得刀叉 如果能获得 则将状态改为正在吃 并且 尝试唤醒 因为wait操作睡眠的进程
// cond_signal 还会阻塞自己 等被唤醒的进程唤醒自己
void phi_test_condvar (i) { 
    if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
            &&state_condvar[RIGHT]!=EATING) {
        cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
        state_condvar[i] = EATING ;
        cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
        cond_signal(&mtp->cv[i]) ;
    }
}

具体原理如下

哲学家->试试拿刀叉->能拿->signal 唤醒被wait阻塞的进程->阻塞本身
                  |             |                  A
                  |             V                  |
                  ->不能拿->wait阻塞本身             |
                                                   |
哲学家->放刀叉->让左右两边试试拿刀叉->有哲学家睡在signal 唤醒他

make grade

通过

make run-matrix

有关输出显示

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

同练习1，通过系统调用实现

异同点类似

• 相同点：基本的实现逻辑相同；
• 不一样点：最终在用户态下实现管程和条件变量机制，须要使用到操做系统使用系统调用提供必定的支持; 而在内核态下实现条件变量是不需要的；

实验总结

本次实验是基于哲学家就餐问题所展开的，并分别用信号量机制和管程机制实现同步和互斥，本次实验代码较为复杂，但是所要编码的部分较为简单，其中管程部分较难理解，还是要多加学习。