本文前置内容：浅谈锁机制
本节对应分支：lock

在上节内容中我们提到，当线程申请锁时，如果该锁已经被其他线程拥有，则此线程必须在该锁上陷入睡眠，直到锁的拥有者将其叫醒。所以我们先实现进程的睡眠与觉醒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//thread.c
void thread_block(enum task_status stat)
{
    assert(((stat == TASK_BLOCKED) || (stat == TASK_WAITING) || (stat == TASK_HANGING)));
    enum intr_status old_status = intr_disable();
    struct task_struct* cur_thread = running_thread();
    cur_thread->status = stat;
    schedule();                  //将当前线程换下处理器
    intr_set_status(old_status); //待当前线程被解除阻塞后才继续运行
}

void thread_unblock(struct task_struct* pthread)
{
    enum intr_status old_status = intr_disable();
    assert(((pthread->status == TASK_BLOCKED) || (pthread->status == TASK_WAITING) || (pthread->status == TASK_HANGING)));
    if (pthread->status != TASK_READY)
    {
        if (elem_find(&thread_ready_list, &pthread->general_tag))
            panic("thread_unblock: blocked thread in ready_list\n",__FILE__,__LINE__,__func__);
        list_push(&thread_ready_list, &pthread->general_tag);    // 放到队列的最前面,使其尽快得到调度
        pthread->status = TASK_READY;
    }
    intr_set_status(old_status);
}
  • 第 4 行，只有为 TASK_BLOCKED、TASK_WAITING、TASK_HANGING 三种状态才会进行睡眠。
  • 第 20 行，为了使觉醒的线程尽快得到调度，使用 list_push 而非 list_append 。
  • 注意，thread_block() 是由当前线程主动执行来进入睡眠的，如果要觉醒，则只能等待其他线程来唤醒，此时是被动的。

再来看锁的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//sync.h
struct semaphore  //信号量
{
    uint8_t  value;       //锁的状态
    struct list waiters;  //在此信号量上等待的线程
};

struct lock       //锁结构
{
    struct   task_struct* holder;	    // 锁的持有者
    struct   semaphore semaphore;	    // 用二元信号量实现锁
    uint32_t holder_repeat_nr;		    // 锁的持有者重复申请锁的次数
};

void sema_init(struct semaphore* psema, uint8_t value);
void sema_down(struct semaphore* psema);
void sema_up(struct semaphore* psema);
void lock_init(struct lock* plock);
void lock_acquire(struct lock* plock);
void lock_release(struct lock* plock);
  • holder_repeat_nr 是同一线程对锁的申请次数。这是为了 1）防止重复申请锁导致陷入死锁；2）防止多次释放锁而出错。
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//sync.c

void sema_init(struct semaphore* psema, uint8_t value) {
    psema->value = value;       // 为信号量赋初值
    list_init(&psema->waiters); //初始化信号量的等待队列
}

/* 初始化锁plock */
void lock_init(struct lock* plock) {
    plock->holder = NULL;
    plock->holder_repeat_nr = 0;
    sema_init(&plock->semaphore, 1);  // 信号量初值为1
}

/* 信号量down操作 */
void sema_down(struct semaphore* psema) {
/* 关中断来保证原子操作 */
    enum intr_status old_status = intr_disable();
    while(psema->value == 0)// 若value为0,表示已经被别人持有
    {
        /* 当前线程不应该已在信号量的waiters队列中 */
        if (elem_find(&psema->waiters, &running_thread()->general_tag))
        {
            panic("sema_down: thread blocked has been in waiters_list\n",__FILE__,__LINE__,__func__);
        }
/* 若信号量的值等于0,则当前线程把自己加入该锁的等待队列,然后阻塞自己 */
        list_append(&psema->waiters, &running_thread()->general_tag);
        thread_block(TASK_BLOCKED);    // 阻塞线程,直到被唤醒
    }
/* 若value为1或被唤醒后,会执行下面的代码,也就是获得了锁。*/
    psema->value--;
    assert(psema->value == 0);
/* 恢复之前的中断状态 */
    intr_set_status(old_status);
}

/* 信号量的up操作 */
void sema_up(struct semaphore* psema) {
/* 关中断,保证原子操作 */
    enum intr_status old_status = intr_disable();
    assert(psema->value == 0);
    if (!list_empty(&psema->waiters)) {
        struct task_struct* thread_blocked = elem2entry(struct task_struct, general_tag, list_pop(&psema->waiters));
        thread_unblock(thread_blocked);
    }
    psema->value++;
    assert(psema->value == 1);
/* 恢复之前的中断状态 */
    intr_set_status(old_status);
}

/* 获取锁plock */
void lock_acquire(struct lock* plock) {
/* 排除曾经自己已经持有锁但还未将其释放的情况。*/
    if (plock->holder != running_thread()) {
        sema_down(&plock->semaphore);    // 对信号量P操作,原子操作
        plock->holder = running_thread();
        plock->holder_repeat_nr = 1;
    } else {
        plock->holder_repeat_nr++;
    }
}

/* 释放锁plock */
void lock_release(struct lock* plock) {
    if (plock->holder_repeat_nr > 1) {
        plock->holder_repeat_nr--;
        return;
    }
    plock->holder = NULL;	   // 把锁的持有者置空放在V操作之前
    plock->holder_repeat_nr = 0;
    sema_up(&plock->semaphore);	   // 信号量的V操作,也是原子操作
}

  • 第 60 行，如果自己已经持有该锁，则仅将 holder_repeat_nr 加 1，不做其他操作，否则重复进行 sema_down 会导致死锁！

    为什么重复申请同一把锁会产生死锁？
    在已经持有锁的情况下继续申请该锁，若仍 sema_down ，则线程会陷入睡眠，等待锁的持有者将自己叫醒。而锁的持有者又是其本身，自己可不能叫醒自己，因此系统陷入死锁。

    所以这里为了应对重复申请锁的情况，当第二次申请时（内层），仅 holder_repeat_nr++ ；当释放锁时，肯定是先从内层释放，所以仅 holder_repeat_nr-- ；外层释放时，再 sema_up 。

  • 第 70 行，必须将置空操作放在 sema_up 之前 。如果顺序放反，则可能出现这样的情况：线程 A 刚执行完 sema_up 还没来得及置空 holder 就被换下了处理器，轮到线程 B 执行。线程 B 申请该锁，因为线程 A 已经释放，所以 B 申请成功，成为该锁的持有人。当线程 B 还没来得及释放锁时，线程 A 重新被换上 CPU，执行的第一条语句就是置空 holder，然而此锁现在依然属于线程 B ，这就引发了错误。

  • 第 19 行为什么使用 while 而非 if，这是因为锁也是通过抢占来获得的，一次抢占可能无法获得锁，举个例子：线程 A 执行 down 操作时发现锁已经被 B 占用，于是陷入睡眠；线程 B 解锁，叫醒 A ；而线程 C 却排在 A 之前，优先被调度，所以锁又被 C 占用，A 继续陷入睡眠。
    但这里也可以用 if 呢？见上面 thread.c 第 20 行，我们把叫醒的线程放在了首位，不存在线程 C 排在 A 之前的情况，所以可以用 if 。

    再次强调，叫醒并不是立刻调度，而是将其放入 thread_ready_list 中。

本文件代码在源代码基础上删除了许多 assert 断言，因为笔者发现即使没有触发这些断言，程序最终总会停留在某个任务中，不再调度其他任务，这令笔者非常疑惑，怎么 assert 还会影响程序结果？即使其没有被触发？这里折磨了我很久，最终也是胡乱改，把这些 assert 删除之后才得到了满意的结果。有明白其原理的朋友麻烦在评论区指点一二，感谢！

实现终端输出

emm，终端输出，这玩意儿听起来高端，实际就是给打印函数添了个锁，来看实现：

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
static struct lock console_lock;    // 控制台锁

/* 初始化终端 */
void console_init()
{
    lock_init(&console_lock);
}

void console_acquire()
{
    lock_acquire(&console_lock);
}

void console_release()
{
    lock_release(&console_lock);
}

void console_put_str(char* str, uint8_t clr)
{
    console_acquire();
    put_str(str,clr);
    console_release();
}

void console_put_char(uint8_t char_asci,uint8_t clr)
{
    console_acquire();
    put_char(char_asci,clr);
    console_release();
}


void console_put_int(uint32_t num,uint8_t clr,uint8_t radix)
{
    console_acquire();
    put_int(num,clr,radix);
    console_release();
}

void console_put_uint(uint32_t num,uint8_t clr,uint8_t radix)
{
    console_acquire();
    put_uint(num,clr,radix);
    console_release();
}

就是这么简单。直接看结果吧：

本文结束。