lagrange's blog

what's dead may never die

0%

Lab7 实验报告

发表于 更新于 分类于

Lab7

定时器 Timer

timer_t 结构用于存储一个定时器所需要的相关数据，包括倒计时时间以及所绑定的进程。

1
2
3
4
5
6
7
static list_entry_t timer_list;

typedef struct {
    unsigned int expires;       //the expire time
    struct proc_struct *proc;   //the proc wait in this timer. If the expire time is end, then this proc will be scheduled
    list_entry_t timer_link;    //the timer list
} timer_t;

add_timer 用于将某个 timer 添加进 timer 列表中。

处于性能考虑，每个新添加的 timer 都会按照其 expires 属性的大小排列，同时减去上一个 timer 的 expires 属性。一个例子：

两个尚未添加进列表中的 timer:

timer1->expires = 20;
timer2->expires = 38;

将这两个 timer 添加进列表后:（注意 timer2 的 expires）

1
2
3
+------------+       +----------------------+       +--------------------------+
| timer_list | <---> | timer1->expires = 20 | <---> | timer2->expires = 18 !!! |
+------------+       +----------------------+       +--------------------------+

这样，在更新 timer_list 中的所有 timer 的 expires 时，只需递减链首的第一个 timer 的 expire，即可间接达到所有 timer 的 expires 减一的目的。

该函数源代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// add timer to timer_list
void add_timer(timer_t *timer) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        list_entry_t *le = list_next(&timer_list);
        // 减去每个遍历到的timer的expires
        while (le != &timer_list) {
            timer_t *next = le2timer(le, timer_link);
            if (timer->expires < next->expires) {
                next->expires -= timer->expires;
                break;
            }
            timer->expires -= next->expires;
            le = list_next(le);
        }
        // 将当前timer添加至列表中
        list_add_before(le, &(timer->timer_link));
    }
    local_intr_restore(intr_flag);
}

run_timer_list 函数用于更新定时器的时间，并更新当前进程的运行时间片。如果当前定时器的剩余时间结束，则唤醒某个处于 WT_INTERRUPTED 等待状态的进程。有一点在上个函数中提到过：递减 timer_list 中每个 timer 的 expires 时，只递减链头第一个 timer 的 expires。该函数的源代码如下

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
// call scheduler to update tick related info, and check the timer is  expired? If expired, then wakup proc
void run_timer_list(void) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        list_entry_t *le = list_next(&timer_list);
        if (le != &timer_list) {
            timer_t *timer = le2timer(le, timer_link);
            // 只递减链头timer的expires
            timer->expires --;
            while (timer->expires == 0) {
                le = list_next(le);
                struct proc_struct *proc = timer->proc;
                wakeup_proc(proc);
                del_timer(timer);
                if (le == &timer_list)
                    break;
                timer = le2timer(le, timer_link);
            }
        }
        // 当前进程执行时间减 1
        sched_class_proc_tick(current);
    }
    local_intr_restore(intr_flag);
}

将 timer 从 timer_list 中删除的操作比较简单：设置好当前待移除 timer 的下一个 timer->expires，并将当前 timer 从链表中移除即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// del timer from timer_list
void del_timer(timer_t *timer) {
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        if (!list_empty(&(timer->timer_link))) {
            if (timer->expires != 0) {
                list_entry_t *le = list_next(&(timer->timer_link));
                if (le != &timer_list) {
                    timer_t *next = le2timer(le, timer_link);
                    next->expires += timer->expires;
                }
            }
            list_del_init(&(timer->timer_link));
        }
    }
    local_intr_restore(intr_flag);
}

一个简单的例子，do_sleep 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int do_sleep(unsigned int time) {
    if (time == 0)
        return 0;
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        // 设置定时器
        timer_t __timer, *timer = timer_init(&__timer, current, time);
        current->state = PROC_SLEEPING;
        current->wait_state = WT_TIMER;
        // 启用定时器
        add_timer(timer);
    }
    local_intr_restore(intr_flag);
    // 当前进程放弃CPU资源
    schedule();
    // 时间到点了，删除当前timer
    del_timer(timer);
    return 0;
}

定时器的用处：定时器可以帮助操作系统在经过一段特定时间后执行一些特殊操作，例如唤醒执行线程。可以说，正是有了定时器，操作系统才有了时间这个概念。

内核信号量实现

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
int pid = kernel_thread(init_main, NULL, 0);

static int
init_main(void *arg) {
    ...
extern void check_sync(void);
    check_sync();                // check philosopher sync problem

    while (do_wait(0, NULL) == 0)
        schedule();
    ...
    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);
        philosopher_proc_sema[i] = find_proc(pid);
        set_proc_name(philosopher_proc_sema[i], "philosopher_sema_proc");
    }
}

在第一个内核进程 idleproc 调用 kernel_thread 派生出第二个进程 init 执行 init_main 函数，init_main 函数调用 check_sync 创建了五个哲学家进程，此时进程控制权还在 init 手中，之后 init 执行 do_wait，主动放弃时间片，执行 schedule()，五个哲学家开始活动。

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

上面是哲学家就餐问题的解，但本文主要聚焦于内核信号量的实现，即 sem_init，up，down 这三个函数的实现。

sem_init

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

void
sem_init(semaphore_t *sem, int value) {
    sem->value = value;
    wait_queue_init(&(sem->wait_queue));
}

sem_init 函数初始化了一个等待队列以及信号量的初值。

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
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
            // 否则唤醒在该信号量等待队列中的第一个进程
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
    }
    local_intr_restore(intr_flag);
}

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

void
wakeup_proc(struct proc_struct *proc) {
    assert(proc->state != PROC_ZOMBIE);
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        // 设置进程状态为就绪
        if (proc->state != PROC_RUNNABLE) {
            proc->state = PROC_RUNNABLE;
            proc->wait_state = 0;
            if (proc != current) {
                // 将进程放入调度队列
                sched_class_enqueue(proc);
            }
        }
        else {
            warn("wakeup runnable process.\n");
        }
    }
    local_intr_restore(intr_flag);
}

down

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
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);
    // 如果信号量大于 0
    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队列删除
    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
wait_current_set(wait_queue_t *queue, wait_t *wait, uint32_t wait_state) {
    // 用当前的进程建一个 wait 结构体放入信号量等待队列
    wait_init(wait, current);
    // 设置当前的进程状态为睡眠状态，后面调用 schedule 放弃时间片
    current->state = PROC_SLEEPING;
    current->wait_state = wait_state;
    wait_queue_add(queue, wait);
}

管程

管程