Ucore Lab7 操作系统实验

LAB7实验报告

实验相关知识

（主要从教学ppt、gitbook、学堂在线上了解掌握并根据CSDN查询了解更加详细的信息。同时结合自己的理论课笔记，实际上是对理论知识的复习）

（此次实验理论知识较为抽象，需具体分析）

根据系统的设计，在语句执行期间，也有可能发生中断或调度，从而导致和当前进程无关的程序先一步执行。为了保证程序执行最终结果的正确性，必须对并发执行的各进程制约，以控制它们的执行速度和对资源的竞争。

互斥：一组并发进程中的一个或多个程序段，因为共享某一个公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。

临界区(critical section)：每个进程中访问临界资源的那段程序（临界资源是一次仅允许一个进程使用的共享资源。）每次只准许一个进程进入临界区，进入后不允许其他进程进入。不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。

互斥是指某一资源同时只允许一个进程对其进行访问，具有唯一性和排它性，但互斥不用限制进程对资源的访问顺序，即访问可以是无序的。同步是指在进程间的执行必须严格按照规定的某种先后次序来运行，即访问是有序的，这种先后次序取决于要系统完成的任务需求。在进程写资源情况下，进程间要求满足互斥条件。在进程读资源情况下，可允许多个进程同时访问资源。

算法进入临界区的准则:有空让进、无空等待、择一而入、算法可行(等待有限)

如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。

信号量：它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。信号允许多个线程同时使用共享资源，这与操作系统中的P V操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。信号量的关键之处在于它们原子地执行。必须确保没有两个进程能够同时对同一信号量执行wait和signal操作

P V 操作：P(sem)：表示申请一个资源 V (sem)：表示释放一个资源。信号量的初值应该大于等于0。P、V操作必须成对出现，有一个 P 操作就一定有一个 V 操作。

实验内容

• 主要是熟悉 ucore的进程同步机制—信号量（semaphore）机制，以及基于信号量的哲学家就餐问题解决方案;
• 掌握管程的概念和原理，并参考信号量机制，实现基于管程的条件变量机制和基于条件变量来解决哲学家就餐问题;

实验过程

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

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

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

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

答：分析lab6和lab7的区别可知，lab7主要多了sync文件夹，也就是sem.c , monitor.c , wait.c 等文件，增添了信号量等操作从而使得操作系统支持进程同步。在trap.c中，当发生时钟中断时，需要调用run_time_list函数。在lab6中，互斥通过lock实现，在lab7中则使用信号量实现互斥，此外增加了等待队列、计时器、禁用中断等。之后将具体分析。

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

信号量的核心用以下的简短代码可以大致表示：

struct semaphore {
 int count;
 queueType queue;
 };
 void semWait(semaphore s)
 {
 s.count--;
 if (s.count < 0) {
 /* place this process in s.queue */;
 /* block this process */;
 }
 }
 void semSignal(semaphore s)
 {
 s.count++;
 if (s.count<= 0) {
/* remove a process P from s.queue */;
 /* place process P on ready list */;
}
}
           

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

我将以具体的代码来分析ucore是如何实现内核信号量的。

首先定义了一些数据结构，包括信号量、等待队列等

// 定义信号量的数据结构
typedef struct {
    int value;                    //信号量的当前值
    wait_queue_t wait_queue;     //信号量对应的等待队列
} semaphore_t;

// 用于等待队列，存放了当前等待的线程的PCB 和 唤醒原因 和 等待队列 和 用于还原结构体的等待队列标志
typedef  struct {
    struct proc_struct *proc;     //等待进程的指针
    uint32_t wakeup_flags;        //进程被放入等待队列的原因标记
    wait_queue_t *wait_queue;     //指向此wait结构所属于的wait_queue
    list_entry_t wait_link;       //用来组织wait_queue中wait节点的连接
} wait_t;
           

信号量的计数器value 含义如下：

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

之后有相应的有关信号量的操作函数：

初始化函数 sem_init:

// 对信号量进行初始化的函数
void sem_init(semaphore_t *sem, int value) 
{
    //将value设为特定值
    sem->value = value;
    //将等待队列初始化
    wait_queue_init(&(sem->wait_queue));
}
           

实现P操作，请求一个信号量对应的资源：

//表示请求一个该信号量对应的资源
static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    local_intr_save(intr_flag);
    //查询整型变量来了解是否存在多余的可分配的资源，
    //如果有多余可分配资源，取出资源（整型变量减1），之后当前进程便可以正常进行；
    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);
//如果没有可用的资源，整型变量不是正数，当前进程的资源需求得不到满足，
//因此将其状态改为SLEEPING态，然后将其挂到对应信号量的等待队列中，
    wait_t __wait, *wait = &__wait;
    wait_current_set(&(sem->wait_queue), wait, wait_state);
    local_intr_restore(intr_flag);
   //调用schedule函数来让出CPU
    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;
}
           

实现V操作，释放一个信号量资源：

//表示释放一个该信号量对应的资源，
static __noinline void __up(semaphore_t *sem, uint32_t wait_state) 
{
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        查询等待队列是否为空，如果是空的话，给整型变量加1；
        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);
}
           

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

用户态的进程/线程的信号量的数据结构与内核态相同**。用户态进程/线程的信号量的相关操作通过系统调用来完成**。每当用户进程调用信号量相关函数时，都会进入系统调用，由内核进行处理，之后再返回到用户态继续执行。相比于为内核提供的信号量机制，用户态进程/线程由于要执行中断操作等特权指令，需要通过系统调用进入内核态使用内核信号量机制。

因此想要在用户态完成信号量机制设计，其实只需要在完成内核态信号量机制设计的基础上，增添一些系统调用，包括：

• 申请创建一个信号量的系统调用
• 对某一信号量进行P操作
• 对某一信号量进行V操作
• 将指定信号量释放

相同：提供信号量机制的代码实现逻辑是相同的

不同：提供给用户态进程的信号量机制是通过系统调用来实现的，而内核级线程只需要直接调用相应的函数就可以

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

能。模仿信号量的实现，可以通过开关中断来完成 cond_wait和cond_signal 的原子性。

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

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

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

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

答：

Hansan为管程所下的定义：“一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据”。

因此管程由四部分组成：

• 管程内部的共享变量；
• 管程内部的条件变量；
• 管程内部并发执行的进程；
• 对局部于管程内部的共享数据设置初始值的语句。

局限在管程中的数据结构，只能被局限在管程的操作过程所访问，任何管程之外的操作过程都不能访问它；另一方面，局限在管程中的操作过程也主要访问管程内的数据结构。由此可见，管程相当于一个隔离区，它把共享变量和对它进行操作的若干个过程围了起来，所有进程要访问临界资源时，都必须经过管程才能进入，而管程每次只允许一个进程进入管程，从而需要确保进程之间互斥。

从ucore具体的代码来看实现：

实现管程所构建的数据结构

monitor

以及

condvar

// 管程的数据结构
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;
           

条件变量机制的实现主要是

cond_signal

,

cond_wait

两个函数中，分别表示提醒等待在这个条件变量上的进程恢复执行，以及等待在这个条件变量上，直到有其他进行将其唤醒为止

cond_signal

: 将指定条件变量上等待队列中的一个线程进行唤醒，并且将控制权转交给这个进程。该操作实现了对共享变量访问的互斥性；

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);  
//判断当前的条件变量的等待队列上是否有正在等待的进程，如果没有则不需要进行任何操作；
//如果有正在等待的进程
     if(cvp->count>0)
     {
        //将其中的一个唤醒
        up(&(cvp->sem));
        //所属管程的next计数加1，表示当前进程会被等待者堵塞
        cvp->owner->next_count ++;
        //阻塞，等待条件同步
        down(&(cvp->owner->next));
        //当前进程被唤醒，恢复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);
}
           

总的来说：执行cond_signal函数时，首先当前进程测试cv.count，如果不大于0，则表示当前没有执行cond_wait而进入休眠状态的进程，函数直接返回。如果cv.count大于0，这表示当前有执行cond_wait而进入休眠状态的进程，因此需要唤醒在cv.sem上等待出入休眠状态的进程。由于只允许一个进程在管程中执行，所以一旦当前进程唤醒了其他进程，自身就要进入休眠状态，即增加monitor.next_count，让当前进程在信号量monitor.next上进入休眠状态，直到被唤醒时，减少monitor.next_count。

cond_wait

：该函数的功能为将当前进程等待在指定信号量上，其操作过程为将等待队列的计数加1，然后释放管程的锁或者唤醒一个next上的进程来释放锁，然后把自己等在条件变量的等待队列上，直到有signal信号将其唤醒，正常退出函数；

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);
   cvp->count ++; // 修改等待在条件变量的等待队列上的进程计数
  //当管程的 next_count 大于0，说明有进程睡在了 signal 操作上我们将其唤醒
   if (cvp->owner->next_count > 0)
   { // 释放锁
    up(&cvp->owner->next);
   }
   else  //当前没有进程睡在 signal操作数 只需要释放互斥体
   {
    up(&cvp->owner->mutex);
   }
   //将自身阻塞，等待条件变量的条件为真，被唤醒后将条件不成立而睡眠的进程计数减1
   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);
}

           

因此，若某个进程执行了cond_wait函数，表明该进程需因要的某个条件变量不满足需求而进入休眠状态。等待这个条件变量的休眠进程数cv.count增加。此时如果monitor.next_count大于0，表示至少有1个进程执行cond_signal函数后进入休眠状态，等待monitor.next信号量时，则需要唤醒等待该条件量的另一个进程，然后该进程在cv.sem上休眠。当进程A被唤醒时，减少cv.count，表示等待此条件变量的睡眠进程个数减少了一个，可继续执行。如果monitor.next_count小于等于0，表明目前没有进程执行cond_signal函数进入休眠，则需要唤醒的是由于互斥条件限制而无法进入管程的进程，即唤醒在monitor.mutex上休眠的进程。然后当前进程在cv.sem上休眠，直到被唤醒时，减少cv.count，表示等待此条件的睡眠进程个数减少，可继续执行。

实现上述函数后，管程基本已经实现，接下来分析本实验中基于条件变量和管程的哲学家就餐问题的实现:

实现哲学家问题主要在

check_sync.c

中

这里创建了5个线程表示5个哲学家，哲学家尝试4次思考->拿叉子->吃饭->放下叉子。

具体分析实现:主要是

phi_take_forks_condvar

函数以及

phi_put_forks_condvar

函数

phi_take_forks_condvar

函数表示指定的哲学家尝试获得自己所需要进餐的两把叉子，如果不能获得则阻塞，具体实现流程为：

• 给管程上锁，将哲学家的状态修改为HUNGER；
• 判断相邻的哲学家是否正在进餐；
• 如果能够进餐，将自己的状态修改成EATING，然后释放锁，离开管程即可；
• 如果不能进餐，等待在自己对应的条件变量上，等待相邻的哲学家释放资源的时候将自己唤醒；

void phi_take_forks_condvar(int i) {
    //通过P操作进入临界区
     down(&(mtp->mutex));  
      //记录下哲学家i是否饥饿，即处于等待状态拿叉子
      state_condvar[i]=HUNGRY; 
      phi_test_condvar(i);
      while (state_condvar[i] != EATING) 
      {
          cprintf("phi_take_forks_condvar: %d didn't get fork and will wait\n",i);
          cond_wait(&mtp->cv[i]);//如果得不到叉子就睡眠
      }
      //如果存在睡眠的进程则那么将之唤醒
      if(mtp->next_count>0)
         up(&(mtp->next));
      else
         up(&(mtp->mutex));
}
           

phi_put_forks_condvar

函数表示释放当前哲学家占用的叉子，并且唤醒相邻的因为得不到资源而进入等待的哲学家：

• 首先获取管程的锁，将自己的状态修改成THINKING；
• 检查相邻的哲学家是否在自己释放了叉子的占用之后满足了进餐的条件，如果满足，将其从等待中唤醒
• 释放锁，离开管程

void phi_put_forks_condvar(int i) {
   	 //通过P操作进入临界区
     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));
}
           

由于每个哲学家只可能占有所有需要的资源或者完全不占用资源，因此不会出现部分占有资源的现象，从而避免了死锁的产生；最终必定所有哲学将都能成功就餐

完毕后，进行make qemu以及make grade检测：

make qemu结果：需要分析make qemu 的具体结果来判断哲学家问题以及信号量是否已经具体实现:

make grade:

补充：哲学家问题自己的一些想法

哲学家问题是非常经典的同步问题，解决方法也是非常多。需要对信号量以及管程等理解非常透彻。最初我看到这个哲学家问题时，是在刚学到信号量时候，当时我的想法是对每个筷子都用一个信号量表示，不就很容易地解决筷子不能一起用的情况了嘛，但是很快便发现这样是有问题的，因为如果每个哲学家同时都把一个筷子拿了起来，便会进入死锁。然后我便修改策略，对拿筷子限制一下，让奇数哲学家优先拿左边再拿右边，偶数哲学家先拿右边再拿左边，这次将这个问题解决了。

之后我查阅了相关资料，了解了挺多关于哲学家问题的解决办法。包括限制哲学家数目为4；只有一个哲学家的左右两边筷子都可用时，利用信号量的解决办法将这两个筷子放入临界区让其拿走；利用管程使得哲学家只有两个筷子都可用将两双筷子拿走，否则将自己延迟。总体思路为：保证筷子互斥，避免进入死锁，避免出现饥饿。当然避免饥饿需要再次增加一些判断以消除。

哲学家问题说实话是非常难的一个问题，必须花费一定时间才能理解的问题，如果只是停留在皮毛，很难对其本质进行理解并解答。庆幸自己在理论课对这个知识点的掌握还不错，辅之以实验的参考资料以及清华大学的教学视频，顺利的通过了这次实验。

参考资料

gitbook上相关内容，其中对很多知识点的解释非常详细，认真看收获非常大，对完成实验内容帮助很大

清华大学学堂在线操作系统教学视频，该视频对理论进行了很好、很详细的讲解，并对实验部分进行了大致介绍

CSDN上与进程同步互斥、信号量、PV操作、管程机制等相关的内容

操作系统理论课书籍

如果给你带来了帮助，可点击关注，博主将继续努力推出好文。