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

内核级信号量实现位于 sem.c 中：

1
2
3
4
5
6
7
8
9
10
bool
try_down(semaphore_t *sem) {
    bool intr_flag, ret = 0;
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        sem->value --, ret = 1;
    }
    local_intr_restore(intr_flag);
    return ret;
}

内核级信号量中使用了等待队列的方法来实现：

1
2
3
4
5
6
7
8
9
10
11
typedef struct {
    int value;
    wait_queue_t wait_queue;
} semaphore_t;

typedef struct {
    struct proc_struct *proc;
    uint32_t wakeup_flags;
    wait_queue_t *wait_queue;
    list_entry_t wait_link;
} wait_t;

信号量中存了信号量的值和一个等待队列，而等待队列中的项就是 wait_t ，存储了等待的进程，唤醒的标志，等待队列和链表项。

在使用信号量之前，需要调用 sem_init 对信号量的值和等待队列进行初始化：

1
2
3
4
5
void
sem_init(semaphore_t *sem, int value) {
    sem->value = value;
    wait_queue_init(&(sem->wait_queue));
}

而 up 对应课本中的 signal 操作，也就是 V 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
}

void
up(semaphore_t *sem) {
    __up(sem, WT_KSEM);
}

在 V 操作中，首先需要关闭中断保证操作的原子性，避免多个线程同时修改信号量。然后判断等待队列中是否有正在等待的进程，如果有，就出队，并唤醒该进程；否则直接将信号量的值加一。

1
2
3
4
5
6
7
8
void
wakeup_wait(wait_queue_t *queue, wait_t *wait, uint32_t wakeup_flags, bool del) {
    if (del) {
        wait_queue_del(queue, wait);
    }
    wait->wakeup_flags = wakeup_flags;
    wakeup_proc(wait->proc);
}

而 down 函数对应课本中的 wait 操作，也就是 P 操作：

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

void
down(semaphore_t *sem) {
    uint32_t flags = __down(sem, WT_KSEM);
    assert(flags == 0);
}

同样使用 local_intr_save 关闭中断保证操作原子性，然后检查信号量的值是否大于 0，如果是则不需要等待，恢复中断并从函数中返回。

而当信号量为 0 的时候，则需要将自己加入到等待队列中：

1
2
3
4
5
6
7
8
void
wait_current_set(wait_queue_t *queue, wait_t *wait, uint32_t wait_state) {
    assert(current != NULL);
    wait_init(wait, current);
    current->state = PROC_SLEEPING;
    current->wait_state = wait_state;
    wait_queue_add(queue, wait);
}

此时进程进入睡眠状态并进入等待队列，直到一个 V 操作将其唤醒。

之后的 schedule 则执行调度器，找到可以运行的进程运行。

随后调度器不断被时钟中断唤起，不断切换进程，当从 schedule 函数返回的时候，说明其他线程释放了一个信号量，本进程已经被唤醒，获得了信号量，所以将自己从等待队列中删除，最后从 down 函数中返回，继续执行接下来的代码。

而 try_down 函数则不会在获取不到信号量的时候阻塞：

1
2
3
4
5
6
7
8
9
10
bool
try_down(semaphore_t *sem) {
    bool intr_flag, ret = 0;
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        sem->value --, ret = 1;
    }
    local_intr_restore(intr_flag);
    return ret;
}

由于不能保证函数返回的时候获取到了信号量，所以一般需要配合 while 循环使用，但是这样会占用 CPU。

给用户态进程/线程提供信号量的方法与内核态几乎相同，区别在于由于关中断需要内核权限，因此需要给用户态增加系统调用进入内核态来实现 PV 操作，其他关于等待队列的实现是一样的。

而 check_sync.c 提供了一个哲学家就餐问题的解法：

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