加 鎖和解鎖的基本思想是，當某個(gè)進(jìn)程進(jìn)入臨界區，它將持有一個(gè)某種類(lèi)型的鎖（UNIX里一般來(lái)說(shuō)是semaphore，Linux里一般是信號量和原子量或 者spinlock）。當其他進(jìn)程在該進(jìn)程沒(méi)有釋放該鎖時(shí)試圖進(jìn)入臨界區（加鎖），它將會(huì )被設置成睡眠狀態(tài)，然后被置入等待該鎖的進(jìn)程隊列（某個(gè)優(yōu)先級 的）。當該鎖被釋放時(shí)，也就是解鎖事件發(fā)生時(shí)，內核將從等待該鎖的進(jìn)程優(yōu)先級隊列中尋找一個(gè)進(jìn)程并將其置為就緒態(tài)，等待調度（schedule）。
在system v中，等待某一事件被稱(chēng)為sleep（sleep on an event），因此下文將統一使用睡眠（sleep）。等待某事件也可以成為等待某個(gè)鎖。（注：本文中的sleep與sleep()系統調用不同）
系統的實(shí)現將一組事件映射到一組內核虛擬地址（鎖）；而且事件不區別對待到底有多少進(jìn)程在等待。這就意味著(zhù)兩個(gè)不規則的事情：
一、當某個(gè)事件發(fā)生時(shí)，等待該事件的一組進(jìn)程均被喚醒（而不是僅僅喚醒一個(gè)進(jìn)程），并且狀態(tài)均被設置成就緒（ready-to-run）。這時(shí) 候由內核選擇（schedule）一個(gè)進(jìn)程來(lái)執行，由于system v內核不是可搶占的（Linux內核可搶占），因此其他的進(jìn)程將一直在就緒狀態(tài)等待調度，或者再次進(jìn)入睡眠（因為該鎖有可能被執行進(jìn)程持有，而執行進(jìn)程因 為等待其他事件的發(fā)生而睡眠），或者等其他進(jìn)程在用戶(hù)態(tài)被搶占。
二、多個(gè)事件映射到同一個(gè)地址（鎖）。假設事件e1和e2都映射到同一個(gè)地址（鎖）addr，有一組進(jìn)程在等待e1，一組進(jìn)程在等待e2，它們 等待的事件不同，但是對應的鎖相同。假如e2發(fā)生了，所有等待e2的進(jìn)程都被喚醒進(jìn)入就緒狀態(tài)，而由于e1沒(méi)有發(fā)生，鎖addr沒(méi)有被釋放，所有被喚醒的 進(jìn)程又回到睡眠狀態(tài)。貌似一個(gè)事件對應一個(gè)地址會(huì )提高效率，但實(shí)際上由于system v是非搶占式內核，而且這種多對一映射非常少，再加上運行態(tài)進(jìn)程很快就會(huì )釋放資源（在其他進(jìn)程被調度之前），因此這種映射不會(huì )導致性能的顯著(zhù)降低。
下面簡(jiǎn)單闡述一下sleep和wakeup的算法。
//偽代碼
sleep(地址（事件），優(yōu)先級)
返回值：進(jìn)程能捕獲的信號發(fā)生導致的返回則返回1，當進(jìn)程不能捕獲的信號發(fā)生時(shí)返回longjmp算法，否則返回0。
{
提高處理器執行等級以禁用所有中斷；//避免競態(tài)條件
將進(jìn)程的狀態(tài)設置為睡眠；
根據事件將進(jìn)程放入睡眠哈希隊列；//一般來(lái)說(shuō)每個(gè)事件都有一個(gè)等待隊列
將睡眠地址（事件）及輸入的優(yōu)先級保存到進(jìn)程表中；
if (該等待是不可中斷的等待)
//一般有兩種睡眠狀態(tài)：可中斷的和不可中斷的。不可中斷的睡眠是指進(jìn)程除了等待的事件外，
//不會(huì )被其他任何事件（如信號）中斷睡眠狀態(tài)，該情況不太常用。
{
上下文切換；//此處該進(jìn)程執行上下文被保存起來(lái)，內核轉而執行其他進(jìn)程
//在別處進(jìn)行了上下文切換，內核選擇該上下文進(jìn)行執行，此時(shí)該進(jìn)程被喚醒
恢復處理器等級來(lái)允許中斷；
返回0；
}
// 被信號中斷的睡眠
if (沒(méi)有未遞送的信號)
{
上下文切換；
if (沒(méi)有未遞送的信號)
{
恢復處理器等級來(lái)允許中斷；
返回0；
}
}
//有未遞送的信號
若進(jìn)程還在等待哈希隊列中，將其從該隊列移出；
恢復處理器等級來(lái)允許中斷；
if(進(jìn)程捕獲該信號)
返回1；
執行longjmp算法；//這一段我也不明白
}
void wakeup(地址（事件）)
{
禁用所有的中斷；
根據地址（事件）查找睡眠進(jìn)程隊列；
for(每個(gè)在該事件上睡眠的進(jìn)程)
{
將該進(jìn)程從哈希隊列中移出；
設置狀態(tài)為就緒；
將該進(jìn)程放入調度鏈表中；
清除進(jìn)程表中的睡眠地址（事件）；
if(進(jìn)程不在內存中)
{
喚醒swapper進(jìn)程；
}
else if(喚醒的進(jìn)程更適合運行)
{
設置調度標志；
}
}
恢復中斷；
}
在wakeup調用之后，被喚醒的進(jìn)程并不是馬上投入運行，而是讓其適合運行，等到下次調度該進(jìn)程才有機會(huì )運行（也可能不會(huì )運行）。
代碼示例：
由于沒(méi)能找到UNIX的源碼，因此用Linux的源代碼替代。上述偽代碼已經(jīng)是比較簡(jiǎn)單的處理。Linux 0.01則更簡(jiǎn)單。
//Linux 0.01的實(shí)現：
//不可中斷睡眠
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task)) //current宏用來(lái)獲取當前運行進(jìn)程的task_struct
panic("task[0] trying to sleep");
tmp = *p; //將已經(jīng)在睡眠的進(jìn)程p2保存到tmp
*p = current; //將當前進(jìn)程p1保存到睡眠進(jìn)程隊列中（實(shí)際上只有一個(gè)）
current->state = TASK_UNINTERRUPTIBLE; //p1狀態(tài)設置為不可中斷的睡眠
schedule(); //上下文切換，執行其他進(jìn)程
//p1被喚醒后回到此處
if (tmp)
tmp->state=0; //將p2的狀態(tài)設置為運行，等待調度
}
//可中斷睡眠
void interruptible_sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp=*p; //正在等待的進(jìn)程p2保存到tmp
*p=current; //將當前進(jìn)程p1保存到睡眠進(jìn)程隊列中
repeat: current->state = TASK_INTERRUPTIBLE; //將p1狀態(tài)設置為可中斷睡眠
schedule(); //上下文切換
if (*p && *p != current) { //p2睡眠被中斷
(**p).state=0;//p1設置為運行態(tài)
goto repeat; //回到repeat，繼續讓p2睡眠
}
*p=NULL;
if (tmp)
tmp->state=0; //將p2的狀態(tài)設置為運行態(tài)，等待調度
}
這兩個(gè)函數比較難以理解，主要是在最后兩條語(yǔ)句。在schedule()之前，切換的是當前進(jìn)程的上下文，但是，切換回來(lái)之后，卻是將原先正在睡眠的進(jìn)程置為就緒態(tài)。在執行schedule()之前，各指針如下圖所示（不好意思，不會(huì )粘貼圖片）：
---
| p |
---
||
\/
---- Step 3 ---------
| *p |--------->| current |
---- ---------
|
X Step 1
|
\/
---------------- Step 2 -----
| Wait Process |<--------| tmp |
---------------- -----
而在schedule()返回到這段代碼之后，事情就不一樣了。因為在step 3之后，current進(jìn)程已經(jīng)進(jìn)入睡眠，tmp指向的睡眠進(jìn)程的描述符也被保存下來(lái)。從schedule()返回之后，執行的代碼仍然是 current，而tmp指向的仍然是wait process，此時(shí)將其狀態(tài)置為就緒，等待下一次調度。
與前兩個(gè)函數相比，wake_up相當簡(jiǎn)單：
//被喚醒的進(jìn)程并不是馬上投入運行，而是讓其適合運行
void wake_up(struct task_struct **p)
{
if (p && *p) {
(**p).state=0; //將要喚醒的進(jìn)程狀態(tài)置為就緒
*p=NULL; //將進(jìn)程移出等待的進(jìn)程
}
}
有了sleep_on()和wake_up()之后，就可以對資源加鎖了，如（硬盤(pán)緩沖加鎖、等待緩沖可用、喚醒等待進(jìn)程）：
//鎖住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的實(shí)現（支持等待隊列）：
static inline void __sleep_on(struct wait_queue **p, int state)
{
unsigned long flags;
struct wait_queue wait = { current, NULL };
if (!p)
return;
if (current == task[0])
panic("task[0] trying to sleep");
current->state = state;
add_wait_queue(p, &wait); //將當前進(jìn)程加入等待隊列
save_flags(flags); //保存中斷掩碼
sti(); //屏蔽中斷
schedule(); //上下文切換
remove_wait_queue(p, &wait); //從等待隊列中移除當前進(jìn)程
restore_flags(flags); //恢復中斷掩碼
}
void wake_up(struct wait_queue **q)
{
struct wait_queue *tmp;
struct task_struct * p;
if (!q || !(tmp = *q))
return;
do {//將等待隊列中喚醒隊首進(jìn)程
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
Copyright (C) by raof01. 本文可以用于除商業(yè)用途外的所有用途。若要用于商業(yè)用途，請與作者聯(lián)系。
