ucore lab7

发表于 分类于

lab6完成了用户进程的调度框架和具体的调度算法，可调度运行多个进程。进程间需要协同操作或访问共享资源，这时候引入了同步互斥问题。本次实验主要是熟悉进程同步机制中的信号量机制，基于信号量机制解决哲学家就餐问题。然后参考信号量机制，实现基于管程的条件变量机制，并给出基于条件变量机制的哲学家就餐问题的解决方案。

填写已有实验

本实验依赖实验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的代码进行进一步改进。

trap.c中对应部分更改如下：

1
2
3
4
5
6
static void trap_dispatch(struct trapframe *tf) {
    case IRQ_OFFSET + IRQ_TIMER:
        ticks ++;
        assert(current != NULL);
        run_timer_list();
        break;

定时器提供了基于时间事件的调度机制，lab7将时间片作为基本的调度和记时单位，实现基于时间长度的睡眠等待和唤醒机制。与lab6相比中断时，lab7调用run_timer_list来更新当前系统时间，遍历当前所有处在系统管理内的定时器，并找出所有到期的进程进行唤醒。

内核级信号量

内核级信号量描述

首先分析lab7执行内核哲学家就餐问题的执行流过程。

  1. 在proc_init中调用kernel_thread创建init内核线程，分配用户程序空间
  2. 执行check_sync函数开始对哲学家就餐问题的测试
  3. 调用kernel_execve生成了n个内核线程代表n个哲学家

接下来具体分析信号量的相关代码。

以下为信号量对应的数据结构

1
2
3
4
5
6
7
8
struct semaphore {//理论
int count;
queueType queue;
};
typedef struct {//具体实现
    int value;//信号量的当前值
    wait_queue_t wait_queue;//对应的等待队列
} semaphore_t;

其中wait相关的数据结构如下

1
2
3
4
5
6
7
8
9
typedef struct {
    struct proc_struct *proc;//等待进程的进程控制块指针
    uint32_t wakeup_flags;//原因标记
    wait_queue_t *wait_queue;//对应等待队列
    list_entry_t wait_link;//对应wait_queue_t
} wait_t;
typedef struct {
    list_entry_t wait_head;
} wait_queue_t;

信号量初始化完成后只能通过P()和V()修改，ucore中对应的函数为down()和up()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
Semaphore::P() {
   sem--;
   if (sem < 0) {
     Add this thread t to q;
     block(t);
     //wakeup
   }
   //else return
}
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;
}
Semaphore::V() {
    sem++; 
    if (sem<=0) {
        Remove a thread t from q;
        wakeup(t);        
    }
}
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);
}

此处需要提及的是，在原理课中的sem若为负数，则其值等于当前正在等待队列的进程的个数，通过sem的值来判断当前是否有进程正在等待该资源，而具体实现中sem最小为0，sem为0表示当前共享资源不空闲，而正在等待该资源的进程则用wait队列来表示，若为空，则当前无正在等待该资源的进程，若不为空，则唤醒对应的进程。

lab7中采用以下方式来解决同步互斥问题：

  • 所有哲学家共用mutex来确保对state_sema数组的互斥访问，在拿刀叉和放回刀叉时均需互斥访问。
  • S信号量数组表示对应哲学家是否正在使用他左右的叉子就餐。
  • 尝试开始就餐时，哲学家先试图取得两个叉子，若得不到叉子则进入阻塞状态等待对应的信号量。
  • 在放回叉子时检查左右哲学家是否可以就餐，可以就餐则解除对应信号量引起的阻塞。

信号量机制

在进程控制块中添加信号量对应的数据结构，用户态进程/线程通过系统调用接口来实现对信号量的P(),V()操作。

对应接口可以设计如下：

  • P: 传入参数为信号量，相当于信号量的P操作，其原子性同样由操作系统来保证。
  • V：传入参数为信号量，相当于信号量的V操作。
  • Set_sem: 传入参数为信号量和设置的value，返回信号量。创建信号量结构体并与当前进程关联，添加到对应的PCB/TCB中。

由系统调用实现是因为用户态特权级无法保证操作的原子性，仍然会被各种中断打断，且进程切换会涉及到内核态的操作，由系统调用来实现更为连贯。

内核级条件变量

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

内核级条件变量描述

管程

1
2
3
4
5
6
7
8
9
10
11
typedef struct condvar{
    semaphore_t sem;//二值信号量，用来互斥访问管程       
    int count;//等待信号量的进程个数
    monitor_t * owner;//该条件变量所属的管程
} condvar_t;
typedef struct monitor{
    semaphore_t mutex;//二值信号量，用来互斥访问管程
    semaphore_t next;//用于条件同步
    int next_count; // 记录signal后休眠的进程数
    condvar_t *cv;//条件变量
} monitor_t;

操作管程的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void //初始化管程数据结构    
monitor_init (monitor_t * mtp, size_t num_cv) {
    int i;
    assert(num_cv>0);
    mtp->next_count = 0;
    mtp->cv = NULL;
    sem_init(&(mtp->mutex), 1); //信号量设置为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;
    }
}

原理课上关于管程的伪代码描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Class Condition {
    int numWaiting = 0;
    WaitQueue q;
}
Condition::Wait(lock){
  numWaiting++;
  Add this thread t to q;
  release(lock);
  schedule(); //need mutex
  require(lock);
}
Condition::Signal(){
 if (numWaiting > 0) {
   Remove a thread t from q;
   wakeup(t); //need mutex
   numWaiting--;
 }
}

ucore中具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void
cond_wait (condvar_t *cvp) {
    cprintf("cond_wait begin:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
    //等待该条件变量的进程数目加一
	cvp->count++;
	//存在因signal而休眠的进程则唤醒
	if(cvp->owner->next_count>0){
		up(&(cvp->owner->next_count);
	}
	else{
		up(&(cvp->owner->mutex);
	}
	//自身进入休眠状态
	down(cv->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);
}
void 
cond_signal (condvar_t *cvp) {
   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){
       //因signal而进入休眠的进程个数加一
	   cvp->owner->next_count++;
	   //唤醒等待信号量的进程
	   up(&(cv->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);
}

wait和signal休眠原因不同，wait因为条件不满足而进入休眠，signal主动让出管程的互斥访问权而休眠。同时可以确定内核态的管程机制采用hoare管程实现，在条件变量释放的同时放弃对管程的互斥访问权。

每次进入管程时执行

1
down(&(mtp->mutex));

每次退出管程时执行

1
2
3
4
if(mtp->next_count>0)
   up(&(mtp->next));
else
   up(&(mtp->mutex));

通过以上语句来互斥访问管程，对应于原理课上的相当于原理课上所讲的lock->Acquire()和lock->Release()操作。

基于管程的哲学家就餐算法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct proc_struct *philosopher_proc_condvar[N]; // N个哲学家
int state_condvar[N]; // 哲学家的状态  
monitor_t mt, *mtp=&mt;
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));
      state_condvar[i]=HUNGRY; 
      phi_test_condvar(i); 
      if (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));
}

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

在之前版本的ucore中，对哲学家所处状态检查以while的形式进行

1
2
3
while (state_condvar[i] != EATING) {
  cond_wait(&(mtp->cv[i]));
}

while和if均可以实现对应功能，if逻辑更为简洁明了。可能考虑到逻辑问题，ucore放弃之前的while而改用if实现对状态的检查。

用户态条件变量机制

在条件变量的实现中，cond_signal和cond_wait导致的进程阻塞与唤醒均由信号量机制来实现，可以考虑由用户来手动控制系统调用来实现用户态进程/线程的条件变量机制。

在ucore中基于信号量实现了条件变量的相关机制，只用到了其中的value成员变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct semaphore {
  int count;
  queueType queue;
};
Class Condition {
    int numWaiting = 0;
    WaitQueue q;
}
typedef struct {
    int value;
    wait_queue_t wait_queue;
} semaphore_t;
typedef struct condvar{
    semaphore_t sem;       
    int count;             
    monitor_t * owner;      
} condvar_t;

信号量和条件变量均为一个整形变量和一个等待队列，但是概念有所不同，对于整形变量解释有所不同。条件变量中，numWaiting表示正在等待该条件变量的进程个数，而信号量中value表示资源的剩余数目，value初始化为1的时候与管程类似，用于互斥操作。

能否不用基于信号量机制来完成条件变量？

可以，条件变量维护者进程的等待队列和进程的等待数目，实际上用等待队列和锁机制同样可以实现。