ucore lab7 同步互斥机制学习笔记

管程的设计实在是精妙,初看的时候觉得非常奇怪,这混乱的进程切换怎么能保证同一时刻只有一个进程访问管程?理清之后大为赞叹,函数中途把前一个进程唤醒后立刻把自己挂起,完美切换.后一个进程又在巧妙的时机将自己唤醒,同时让后一个挂起.看似松散的跳转背后竟然是无比严丝合缝的逻辑,真的就滴水不漏.

等待状态

在proc.h中又增加了等待定时器和等待内核信号量的宏供本节使用

#define WT_INTERRUPTED // the wait state could be interrupted

#define WT_CHILD       // wait child process

#define WT_KSEM        // wait kernel semaphore

#define WT_TIMER       // wait timer

定时器timer

static list_entry_t timer_list; //定时器链表

typedef struct {

    unsigned int expires;       //与前一个timer的时间差

    struct proc_struct *proc;   //关联的进程

    list_entry_t timer_link;    //定时器链表,管理所有定时器

} timer_t;

timer_init: 设置指定timer的proc和expires,并timer_link的next和prev指向自身

add_timer: 把timer插入到timer_list的适应位置,并调整自身和后一项的expires

del_timer: 调整后一项的expires,把自身从timer_list里删除

run_timer_list: timer_list头的时差-1,减到0时唤醒它和它之后的时差为0进程,并从timer_list中删除.返回前调用进程调度框架的proc_tick()

值得注意在其他项目中我们令一个链表项为空时都是让它的next指向NULL,而在UCORE中则是让next指向自身.

等待队列

typedef struct {

    list_entry_t wait_head;

} wait_queue_t;

typedef struct {

    struct proc_struct *proc;	//关联的进程

    uint32_t wakeup_flags;	//标志

    wait_queue_t *wait_queue;	//所属的等待队列

    list_entry_t wait_link;	//等待队列的链表,决定了自己的位置

} wait_t;

与之对应的定义了各种增删查找初始化的函数

信号量semaphore

typedef struct {

    int value;

    wait_queue_t wait_queue;

} semaphore_t;

信号量的本质可以想象成红绿灯,大于0时可以通行,否则就按顺序排队等待.

value>0: 信号量可用

value=0: 信号量被占用

value<0: 等待信号量的进程数

主要操作为一下四个:

sem_init(sem,value): 初始化

down(sem): 申请占用信号量

up(sem): 释放信号量

try_down(sem): 检查信号量value>0?,为真的时候令value--并返回1

down间接调用了__down

void

down(semaphore_t *sem) {

    uint32_t flags = __down(sem, WT_KSEM);

    assert(flags == 0); //返回非零,状态异常

}

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;

    //把当前进程变为SLEEPING态并插入等待队列

    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间接调用了__up

void

up(semaphore_t *sem) {

    __up(sem, WT_KSEM);

}

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

}

这时候我们来分析一下基于信号量的哲学家就餐问题

int state_sema[N]; /* 记录每个人状态的数组 */

/* 信号量是一个特殊的整型变量 */

semaphore_t mutex; /* 临界区互斥 */

semaphore_t s[N]; /* 每个哲学家一个信号量 */

struct proc_struct *philosopher_proc_sema[N];

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

    }

}

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); /* 离开临界区 */

}

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;

}

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

    }

	//.......

}

注意mutex初始值为1,可以被占用.而s数组值为0.

假设0号哲学家第一个行动,执行它的take_fork函数.先占用mutex,保证这一时刻只有他能行动.他HUNGRY了,一看左右都没有在EATING,于是把自己设为EATING态,并把信号量s0释放,证明自己现在可以吃了.再把mutex释放,允许别人行动.此时再把s0占用掉,证明自己已经开始吃了.最后返回到using_semaphore里,让自己睡眠一会儿.

在此期间1号哲学家被调度,不过要等到0号哲学家释放mutex后才能执行take_fork.1号占用到mutex后感觉HUNGRY了,一看左边0号还拿着叉子不放手.没办法就先释放了mutex,等在了自己的s1上.

风水轮流转,等着0号执行到put_fork,把叉子放下,才能唤醒1号

管程monitor

//条件变量结构体

typedef struct condvar{

    semaphore_t sem;        // 关联的信号量

    int count;              // 等待进程个数

    monitor_t * owner;      // 所属的管程

} condvar_t;

//管程结构体

typedef struct monitor{

    semaphore_t mutex;      // 初始值为1,保证每次只有一个进程进入管程

    semaphore_t next;       // the next semaphore is used to down the signaling proc itself, and the other OR wakeuped waiting proc should wake up the sleeped signaling proc.

    int next_count;         // the number of of sleeped signaling proc

    condvar_t *cv;          // 条件变量数组

} monitor_t;

// Initialize monitor.

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); //unlocked

    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.

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

   }

}

// 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

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

}

基于管程的哲学家就餐问题

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

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

}

void phi_put_forks_condvar(int i) {

    down(&(mtp->mutex));

    state_condvar[i]=THINKING;

    phi_test_condvar((i+1)%5);

    phi_test_condvar((i+4)%5);

    if(mtp->next_count>0)

        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;

}

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

    }

}

monitor_init中会将除mutex以外的所有成员置零

0号先行动,调用take_forks,占用mutex,检查合法后将自己设为EATING.调用cond_signal,因为cv[0]->count初始值为0,所以直接跳过.然后mtp->next_count为初始值0,释放mutex,返回.

1号再行动,占用mutex,检查后发现自己不满足EATING条件,调用cond_wait.mtp->next_count为0,释放mutex.cv[1]->count变成1.申请信号量,因为cv[1]->sem->value为0,进入等待状态.

等到轮完一遍再到0号时,执行put_fork,占用mutex,放下叉子后检查左右的状态,执行1号的cond_signal.此时cv[1]->count为1,满足条件,将monitor的next_count增加1,解除cv[1]->sem的占用,1号进入RUNNABLE态.因为管程中同一时刻只能有一个进程访问,故马上申请占用monitor的next信号量,让自己进入等待状态.

此时1号得以继续在cont_wait的down中执行.因为是从一个占用管程的进程切换到了另一个占用管程的进程,保证了管程中同一时刻只能有一个进程访问,所以mutex也无须变更.将cv[1]->count变回0,返回.

再往后,随便哪个n号进程运行到cond_wait时,都会因为next_count>0而唤醒等待next信号量的0号进程.又因为n号进程一定是因为没有进入EATING才执行的cond_wait,所以n号进程一定会在down(cv[n]->sem)处卡住,切换到0号进程,有一次保证了保证了管程中同一时刻只能有一个进程访问.

0号进程切回后next_count--,直接返回.

巴特西

ucore lab7 同步互斥机制学习笔记

最新文章

热门文章

巴特西

ucore lab7 同步互斥机制 学习笔记

最新文章

热门文章

ucore lab7 同步互斥机制学习笔记