UNIX核心（1）：加鎖解鎖——等待事件及喚醒

原文轉自：http://blog.chinaunix.net/uid-7471615-id-83756.html

概述

加鎖和解鎖的基本思想是，當某個程序進入臨界區，它将持有一個某種類型的鎖（UNIX裡一般來說是semaphore，Linux裡一般是信号量和原子量或者spinlock）。當其他程序在該程序沒有釋放該鎖時試圖進入臨界區（加鎖），它将會被設定成睡眠狀态，然後被置入等待該鎖的程序隊列（某個優先級的）。當該鎖被釋放時，也就是解鎖事件發生時，核心将從等待該鎖的程序優先級隊列中尋找一個程序并将其置為就緒态，等待排程（schedule）。

原理

在system v中，等待某一事件被稱為sleep（sleep on an event），是以下文将統一使用睡眠（sleep）。等待某事件也可以成為等待某個鎖。（注：本文中的sleep與sleep()系統調用不同）

系統的實作将一組事件映射到一組核心虛拟位址（鎖）；而且事件不差別對待到底有多少程序在等待。這就意味着兩個不規則的事情：

一、當某個事件發生時，等待該事件的一組程序均被喚醒（而不是僅僅喚醒一個程序），并且狀态均被設定成就緒（ready-to-run）。這時候由核心選擇（schedule）一個程序來執行，由于system v核心不是可搶占的（Linux核心可搶占），是以其他的程序将一直在就緒狀态等待排程，或者再次進入睡眠（因為該鎖有可能被執行程序持有，而執行程序因為等待其他事件的發生而睡眠），或者等其他程序在使用者态被搶占。

二、多個事件映射到同一個位址（鎖）。假設事件e1和e2都映射到同一個位址（鎖）addr，有一組程序在等待e1，一組程序在等待e2，它們等待的事件不同，但是對應的鎖相同。假如e2發生了，所有等待e2的程序都被喚醒進入就緒狀态，而由于e1沒有發生，鎖addr沒有被釋放，所有被喚醒的程序又回到睡眠狀态。貌似一個事件對應一個位址會提高效率，但實際上由于system v是非搶占式核心，而且這種多對一映射非常少，再加上運作态程序很快就會釋放資源（在其他程序被排程之前），是以這種映射不會導緻性能的顯著降低。

下面簡單闡述一下sleep和wakeup的算法。

//僞代碼

sleep(位址（事件），優先級)

傳回值：程序能捕獲的信号發生導緻的傳回則傳回1，當程序不能捕獲的信号發生時傳回longjmp算法，否則傳回0。

{

提高處理器執行等級以禁用所有中斷；//避免競态條件

将程序的狀态設定為睡眠；

根據事件将程序放入睡眠哈希隊列；//一般來說每個事件都有一個等待隊列

将睡眠位址（事件）及輸入的優先級儲存到程序表中；

if (該等待是不可中斷的等待)

//一般有兩種睡眠狀态：可中斷的和不可中斷的。不可中斷的睡眠是指程序除了等待的事件外，

//不會被其他任何事件（如信号）中斷睡眠狀态，該情況不太常用。

上下文切換；//此處該程序執行上下文被儲存起來，核心轉而執行其他程序

//在别處進行了上下文切換，核心選擇該上下文進行執行，此時該程序被喚醒

恢複處理器等級來允許中斷；

傳回0；

}

// 被信号中斷的睡眠

if (沒有未遞送的信号)

上下文切換；

//有未遞送的信号

若程序還在等待哈希隊列中，将其從該隊列移出；

if(程序捕獲該信号)

傳回1；

執行longjmp算法；//這一段我也不明白

void wakeup(位址（事件）)

禁用所有的中斷；

根據位址（事件）查找睡眠程序隊列；

for(每個在該事件上睡眠的程序)

将該程序從哈希隊列中移出；

設定狀态為就緒；

将該程序放入排程連結清單中；

清除程序表中的睡眠位址（事件）；

if(程序不在記憶體中)

喚醒swapper程序；

else if(喚醒的程序更适合運作)

設定排程标志；

恢複中斷；

在wakeup調用之後，被喚醒的程序并不是馬上投入運作，而是讓其适合運作，等到下次排程該程序才有機會運作（也可能不會運作）。

代碼示例

由于沒能找到UNIX的源碼，是以用Linux的源代碼替代。上述僞代碼已經是比較簡單的處理。Linux 0.01則更簡單。

//Linux 0.01的實作：

//不可中斷睡眠

void sleep_on(struct task_struct **p)

struct task_struct *tmp;

if (!p)

return;

if (current == &(init_task.task)) //current宏用來擷取目前運作程序的task_struct

panic("task[0] trying to sleep");

tmp = *p; //将已經在睡眠的程序p2儲存到tmp

*p = current; //将目前程序p1儲存到睡眠程序隊列中（實際上隻有一個）

current->state = TASK_UNINTERRUPTIBLE; //p1狀态設定為不可中斷的睡眠

schedule(); //上下文切換，執行其他程序

//p1被喚醒後回到此處

if (tmp)

tmp->state=0; //将p2的狀态設定為運作，等待排程

//可中斷睡眠

void interruptible_sleep_on(struct task_struct **p)

if (current == &(init_task.task))

tmp=*p; //正在等待的程序p2儲存到tmp

*p=current; //将目前程序p1儲存到睡眠程序隊列中

repeat: current->state = TASK_INTERRUPTIBLE; //将p1狀态設定為可中斷睡眠

schedule(); //上下文切換

if (*p && *p != current) { //p2睡眠被中斷

(**p).state=0;//p1設定為運作态

goto repeat; //回到repeat，繼續讓p2睡眠

*p=NULL;

tmp->state=0; //将p2的狀态設定為運作态，等待排程

這兩個函數比較難以了解，主要是在最後兩條語句。在schedule()之前，切換的是目前程序的上下文，但是，切換回來之後，卻是将原先正在睡眠的程序置為就緒态。在執行schedule()之前，各指針如下圖所示（不好意思，不會粘貼圖檔）：

---

| p |

||

\/

---- Step 3 ---------

| *p |--------->| current |

---- ---------

|

X Step 1

---------------- Step 2 -----

| Wait Process |<--------| tmp |

---------------- -----

而在schedule()傳回到這段代碼之後，事情就不一樣了。因為在step 3之後，current程序已經進入睡眠，tmp指向的睡眠程序的描述符也被儲存下來。從schedule()傳回之後，執行的代碼仍然是current，而tmp指向的仍然是wait process，此時将其狀态置為就緒，等待下一次排程。

與前兩個函數相比，wake_up相當簡單：

//被喚醒的程序并不是馬上投入運作，而是讓其适合運作

void wake_up(struct task_struct **p)

if (p && *p) {

(**p).state=0; //将要喚醒的程序狀态置為就緒

*p=NULL; //将程序移出等待的程序

使用加鎖機制

有了sleep_on()和wake_up()之後，就可以對資源加鎖了，如（硬碟緩沖加鎖、等待緩沖可用、喚醒等待程序）：

//鎖住bh

static inline void lock_buffer(struct buffer_head * bh)

if (bh->b_lock)

printk("hd.c: buffer multiply locked\n");

bh->b_lock=1;

static inline void unlock_buffer(struct buffer_head * bh)

if (!bh->b_lock)

printk("hd.c: free buffer being unlocked\n");

bh->b_lock=0;

wake_up(&bh->b_wait);

static inline void wait_on_buffer(struct buffer_head * bh)

cli(); //禁止中斷

while (bh->b_lock)

sleep_on(&bh->b_wait);

sti(); //恢複中斷

//Linux 0.99.15的sleep和wake_up的實作（支援等待隊列）：

static inline void __sleep_on(struct wait_queue **p, int state)

unsigned long flags;

struct wait_queue wait = { current, NULL };

if (current == task[0])

current->state = state;

add_wait_queue(p, &wait); //将目前程序加入等待隊列

save_flags(flags); //儲存中斷掩碼

sti(); //屏蔽中斷

remove_wait_queue(p, &wait); //從等待隊列中移除目前程序

restore_flags(flags); //恢複中斷掩碼

void wake_up(struct wait_queue **q)

struct wait_queue *tmp;

struct task_struct * p;

if (!q || !(tmp = *q))

do {//将等待隊列中喚醒隊首程序

if ((p = tmp->task) != NULL) {

if ((p->state == TASK_UNINTERRUPTIBLE) ||

(p->state == TASK_INTERRUPTIBLE)) {

p->state = TASK_RUNNING;

if (p->counter > current->counter)

need_resched = 1;

if (!tmp->next) {

printk("wait_queue is bad (eip = %08lx)\n",((unsigned long *) q)[-1]);

printk(" q = %p\n",q);

printk(" *q = %p\n",*q);

printk(" tmp = %p\n",tmp);

break;

tmp = tmp->next;

} while (tmp != *q);

PS：對于核心的了解很膚淺，文章中應該有不少錯誤，而且Linux核心0.01版本身就有很多bug，是以，穩中引用的代碼不一定完全正确。盼高手指正！！！

參考：

The Deisgn of The UNIX Operating System, by Maurice J. Bach

Linux核心源代碼0.01，0.99.15及2.6.22

Copyleft (C) raof01.

本文可以用于除商業外的所有用途。此處“用途”包括（但不限于）拷貝/翻譯（部分或全部），不包括根據本文描述來産生代碼及思想。若用于非商業，請保留此權利聲明，并标明文章原始位址和作者資訊；若要用于商業，請與作者聯系（[email protected]），否則作者将使用法律來保證權利。