[自制操作系统] 第16回 锁的实现

目录
一、前景回顾
二、锁的实现
三、使用锁实现console函数
四、运行测试

 

一、前景回顾

  上回我们实现了多线程,并且最后做了一个小小的实验,不过有一点小瑕疵。

   

  可以看到黄色部分的字符不连续,按道理应该是“argB Main”,这是为什么呢?其实仔细思考一下还是很好得出结论。我们的字符打印函数是put_str,实际上是调用的put_char函数。所以打印一个字符串需要多次调用put_char函数来打印一个个字符,如果我们当前线程刚好打印完了arg,正准备打印下一个字符B时,这时发生了调度,那么就造成了上面的这种情况。

  由此引申出来了公共资源、临界区和互斥的概念:

  公共资源:可以是公共内存、公共文件、公共硬件等,总之是被所有任务共享的一套资源。

  临界区:程序想要使用某些资源,必然通过一些指令去访问这些资源,若多个任务都访问同一公共资源,那么各任务中访问公共资源的指令代码组成的区域就被称为临界区。

  互斥:互斥又称为排他,是指某一时刻公共资源只能被一个任务独享,即不允许多个任务同时出现在自己的临界区中。其他任务想要访问公共资源时,必须等待当前公共资源的访问者完全执行完毕他自己的临界区代码后,才可以访问。

  现在联系实际情况,我们可以知道,显存区域是公共资源,每个线程的临界区便是put_str函数。每个线程之间的put_str函数是互斥的关系,也就是说,任何一个时刻,只能有一个线程可以访问操作显存,并且只有等这个线程访问操作完毕显存后,才可以让下一个线程访问操作显存。我们的代码中并没有具备互斥这个条件,所以便会造成上面的情况。

  基于上面的思路,如果我们对main.c文件做如下修改,在每个线程的put_str函数执行前后先执行关中断和开中断操作。

 1 #include "print.h"
 2 #include "init.h"
 3 #include "memory.h"
 4 #include "thread.h"
 5 #include "list.h"
 6 #include "interrupt.h"
 7 
 8 void k_thread_a(void *arg);  9 void k_thread_b(void *arg); 10 
11 int main(void) 12 { 13     put_str("HELLO KERNEL\n"); 14  init_all(); 15     
16     thread_start("k_thread_a", 31, k_thread_a, "argA "); 17     thread_start("k_thread_b", 8, k_thread_b, "argB "); 18  intr_enable(); 19     while(1) { 20  intr_disable(); 21         console_put_str("Main "); 22  intr_enable(); 23  } 24 } 25 
26 /*在线程中运行的函数k_thread_a*/
27 void k_thread_a(void *arg) 28 { 29     char *para = arg; 30     while (1) { 31  intr_disable(); 32  put_str(para); 33  intr_enable(); 34  } 35 } 36 
37 /*在线程中运行的函数k_thread_b*/
38 void k_thread_b(void *arg) 39 { 40     char *para = arg; 41     while (1) { 42  intr_disable(); 43  put_str(para); 44  intr_enable(); 45  } 46 }

main.c

  此时我们再运行系统,便可以看到字符输出就变得正常了。

  

  虽然关中断可以实现互斥,但是,关中断的操作应尽可能地靠近临界区,这样才更高效,毕竟只有临界区中的代码才用于访问公共资源,而访问公共资源的时候才需要互斥、排他,各任务临界区之外的代码并不会和其他任务有所冲突。关中断操作离临界区越远,多任务调度就越低效。

  总结一下:多线程访问公共资源时产生了竞争条件,也就是多个任务同时出现在了自己的临界区。为了避免产生竞争条件,必须保证任意时刻只能有一个任务处于临界区。虽然开闭中断的方式能够解决这个问题,但是效率并不是最高的,我们通过提供一种互斥的机制,互斥使临界区具有原子性,避免产生竞争条件,从而避免了多任务访问公共资源时出问题。

二、锁的实现

  我们的锁是通过信号量的方式来实现的。信号量是一个整数,用来记录所积累信号的数量。在我们的代码中,对信号量的加法操作是用up表示,减法操作是用down表示。

  增加操作up,可以理解为释放锁,包括两个微操作:

  1、将信号量的值加1。

  2、唤醒在此信号量上等待的线程。

  减少操作down,可以理解获取锁,包括三个微操作:

  1、判断信号量是否为0。

  2、若信号量大于0,则将信号量减1。

  3、若信号量等于0,当前线程将自己阻塞,以在此信号量上等待。

  所以有了这两个操作后,两个线程在进入临界区时,便是如下操作:

  1、线程A进入临界区前先通过down操作获取锁,此时信号量减去1为0。

  2、同样,线程B也要进入临界区,尝试使用down操作获取锁,但是信号量已经减为0,所以线程B便在此信号量上等待,也就是将自己阻塞。

  3、当线程A从临界区中出来后,将信号量加1,也就是释放锁,随后线程A将线程B唤醒

  4、线程B被唤醒后,获得锁,进入临界区。

  来看看代码吧,在project/kernel目录下新建sync.c和sync.h文件,关于阻塞和解除阻塞的函数我们放在了thread.c文件下。

 1 #include "sync.h"
 2 #include "interrupt.h"
 3 #include "debug.h"
 4 #include "thread.h"
 5 
 6 /*初始化信号量*/
 7 void sema_init(struct semaphore *psema, uint8_t value)  8 {  9     psema->value = value; 10     list_init(&psema->waiters); 11 } 12 
13 /*初始化锁lock*/
14 void lock_init(struct lock* plock) 15 { 16     plock->holder = NULL; 17     plock->holder_repeat_nr = 0; 18     sema_init(&plock->semaphore, 1); 19 } 20 
21 /*信号量down操作*/
22 void sema_down(struct semaphore *psema) 23 { 24     /*关中断来保证原子操作*/
25     enum intr_status state = intr_disable(); 26     while (psema->value == 0) { 27         /*当前线程不应该在信号量的waiters队列中*/
28         ASSERT(!elem_find(&psema->waiters, &running_thread()->general_tag)); 29         if (elem_find(&psema->waiters, &running_thread()->general_tag)) { 30             PANIC("sema_down: thread blocked has been in waiters_list\n"); 31  } 32 
33         /*若信号量为0,则当前线程把自己加入到该锁的等待队列中*/
34         list_append(&psema->waiters, &running_thread()->general_tag); 35  thread_block(TASK_BLOCKED); 36  } 37 
38     /*若value为1或者被唤醒后,会执行以下代码*/
39     psema->value--; 40     ASSERT(psema->value == 0); 41     /*恢复之前的中断状态*/
42  intr_set_status(state); 43 } 44 
45 /*信号量UP操作*/
46 void sema_up(struct semaphore *psema) 47 { 48     /*关中断来保证原子操作*/
49     enum intr_status state = intr_disable(); 50     ASSERT(psema->value == 0); 51     if (!list_empty(&psema->waiters)) { 52         struct task_struct *thread_blocked = elem2entry(struct task_struct, general_tag, list_pop(&psema->waiters)); 53  thread_unblock(thread_blocked); 54  } 55     psema->value++; 56     ASSERT(psema->value == 1); 57     /*恢复之前的中断状态*/
58  intr_set_status(state); 59 } 60 
61 /*获取锁plock*/
62 void lock_acquire(struct lock *plock) 63 { 64     /*排除曾经自己有锁但还未释放锁的情况*/
65     if (plock->holder != running_thread()) { 66         sema_down(&plock->semaphore); 67         plock->holder = running_thread(); 68         ASSERT(plock->holder_repeat_nr == 0); 69         plock->holder_repeat_nr = 1; 70     } else { 71         plock->holder_repeat_nr++; 72  } 73 } 74 
75 /*释放锁plock*/
76 void lock_release(struct lock *plock) 77 { 78     ASSERT(plock->holder == running_thread()); 79     if (plock->holder_repeat_nr > 1) { 80         plock->holder_repeat_nr--; 81         return; 82  } 83     ASSERT(plock->holder_repeat_nr == 1); 84     plock->holder = NULL; 85     plock->holder_repeat_nr = 0; 86     sema_up(&plock->semaphore); 87 }

sync.c

#ifndef __KERNEL_SYNC_H #define  __KERNEL_SYNC_H #include "stdint.h" #include "list.h"

/*信号量结构*/
struct semaphore { uint8_t value; struct list waiters; }; /*锁结构*/
struct lock { struct task_struct *holder;    //锁的持有者
    struct semaphore semaphore;    //用二元信号量实现锁
    uint32_t holder_repeat_nr;     //锁的持有者重复申请锁的次数 
}; void lock_release(struct lock *plock); void lock_acquire(struct lock *plock); void sema_up(struct semaphore *psema); void sema_down(struct semaphore *psema); void lock_init(struct lock* plock); void sema_init(struct semaphore *psema, uint8_t value); #endif

sync.h

 1 ...  2 
 3 /*当前线程将自己阻塞,标志其状态为stat*/
 4 void thread_block(enum task_status stat)  5 {  6     /*stat取值为TASK_BLOCKED、TASK_WAITING、TASK_HANGING  7  这三种状态才不会被调度*/
 8 
 9     ASSERT(((stat == TASK_BLOCKED) || (stat == TASK_WAITING) || (stat == TASK_HANGING))); 10     enum intr_status old_status = intr_disable(); 11     struct task_struct *cur_thread = running_thread(); 12     cur_thread->status = stat; 13  schedule(); 14  intr_set_status(old_status); 15 } 16 
17 /*将线程thread解除阻塞*/
18 void thread_unblock(struct task_struct *thread) 19 { 20     enum intr_status old_status = intr_disable(); 21     ASSERT(((thread->status == TASK_BLOCKED) || (thread->status == TASK_WAITING) || (thread->status == TASK_HANGING))); 22     if (thread->status != TASK_READY) { 23         ASSERT(!elem_find(&thread_ready_list, &thread->general_tag)); 24         if (elem_find(&thread_ready_list, &thread->general_tag)) { 25             PANIC("thread_unblock: blocked thread in ready_list!\n"); 26  } 27         list_push(&thread_ready_list, &thread->general_tag); 28         thread->status = TASK_READY; 29  } 30  intr_set_status(old_status); 31 }

thread.c

三、使用锁实现console函数

  在本回开始,我们通过在put_str函数前后关、开中断来保证任何时刻只有一个任务处于临界区代码,不过这种方式效率低下。现在我们已经实现了锁机制,所以可以利用锁来升级put_str函数。在project/kernel目录下新建console.c和console.h文件。

#include "stdint.h" #include "sync.h" #include "thread.h" #include "print.h" #include "console.h"

static struct lock console_lock; /*初始化终端*/
void console_init(void) { lock_init(&console_lock); } /*获取终端*/
void console_acquire(void) { lock_acquire(&console_lock); } /*释放终端*/
void console_release(void) { lock_release(&console_lock); } /*终端中输出字符串*/
void console_put_str(char *str) { console_acquire(); put_str(str); console_release(); } /*终端中输出字符*/
void console_put_char(uint8_t char_asci) { console_acquire(); put_char(char_asci); console_release(); } /*终端中输出十六进制整数*/
void console_put_int(uint32_t num) { console_acquire(); put_int(num); console_release(); }

console.c

 1 #ifndef __KERNEL_CONSOLE_H  2 #define  __KERNEL_CONSOLE_H
 3 
 4 void console_init(void);  5 void console_acquire(void);  6 void console_release(void);  7 void console_put_str(char *str);  8 void console_put_char(uint8_t char_asci);  9 void console_put_int(uint32_t num); 10 
11 #endif

console.h

四、运行测试

  修改main.c函数并编译运行。可以看到,字符整齐无误地出现在屏幕上,不会出现字符短缺的现象。不要忘记在makefile中增加sync.o、console.o文件。

 1 #include "print.h"
 2 #include "init.h"
 3 #include "memory.h"
 4 #include "thread.h"
 5 #include "list.h"
 6 #include "interrupt.h"
 7 #include "console.h"
 8 
 9 void k_thread_a(void *arg); 10 void k_thread_b(void *arg); 11 
12 int main(void) 13 { 14     put_str("HELLO KERNEL\n"); 15  init_all(); 16     
17     thread_start("k_thread_a", 31, k_thread_a, "argA "); 18     thread_start("k_thread_b", 8, k_thread_b, "argB "); 19  intr_enable(); 20     while(1) { 21         console_put_str("Main "); 22  } 23 } 24 
25 /*在线程中运行的函数k_thread_a*/
26 void k_thread_a(void *arg) 27 { 28     char *para = arg; 29     while (1) { 30  console_put_str(para); 31  } 32 } 33 
34 /*在线程中运行的函数k_thread_b*/
35 void k_thread_b(void *arg) 36 { 37     char *para = arg; 38     while (1) { 39  console_put_str(para); 40  } 41 } 42 
43 
44 
45 
46 
47 
48 
49 
50 //asm volatile("sti");

main.c

   

  本回到此结束,预知后事如何,请看下回分解。

张贴在2