[自制作業系統] 第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 }
此時我們再執行系統，便可以看到字元輸出就變得正常了。
雖然關中斷可以實現互斥，但是，關中斷的操作應儘可能地靠近臨界區，這樣才更高效，畢竟只有臨界區中的程式碼才用於存取公共資源，而存取公共資源的時候才需要互斥、排他，各任務臨界區之外的程式碼並不會和其他任務有所衝突。關中斷操作離臨界區越遠，多工排程就越低效。
總結一下：多執行緒存取公共資源時產生了競爭條件，也就是多個任務同時出現在了自己的臨界區。為了避免產生競爭條件，必須保證任意時刻只能有一個任務處於臨界區。雖然開閉中斷的方式能夠解決這個問題，但是效率並不是最高的，我們通過提供一種互斥的機制，互斥使臨界區具有原子性，避免產生競爭條件，從而避免了多工存取公共資源時出問題。
我們的鎖是通過號誌的方式來實現的。號誌是一個整數，用來記錄所積累訊號的數量。在我們的程式碼中，對號誌的加法操作是用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 }
#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
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 }
在本回開始，我們通過在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();
}
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
修改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");
本回到此結束，預知後事如何，請看下回分解。