內核等待隊列機制介紹

接下來(lái)，我要跟各位介紹一下 wait_queue 的用法，以及用一個(gè)例子來(lái)說(shuō)明如何使用 wait_queue。最后，我會(huì )帶各位去 trace 一下 wait_queue 的原始程序代碼，看看 wait_queue 是如何做到的。

我想有件事要先提及的是 Linux 在 user space 跟在 kernel space 上的差異。我們知道 Linux 是 multi-tasking 的環(huán)境，同時(shí)可以有很多人執行很多的程序。這是從 user 的觀(guān)點(diǎn)來(lái)看的。如果就 kernel 的觀(guān)點(diǎn)來(lái)看，是沒(méi)有所謂的 multi-tasking 的。在 kernel 里，只有 single-thread。也就是說(shuō)，如果你的 kernel code 正在執行，那系統里只有那部分在執行。不會(huì )有另一部分的 kernel code 也在運作。當然，這是指 single processor 的情況下，如果是 SMP 的話(huà)，那我就不清楚了。我想很多人都在 Windows 3.1 下寫(xiě)過(guò)程序，在那種環(huán)境下寫(xiě)程序，每一個(gè)程序都必須適當的將 CPU 讓給別的程序使用。如果有個(gè)程序里面有一個(gè)

while (1);

的話(huà)，那保證系統就停在那里了。這種的多任務(wù)叫做 non-preemptive。它多任務(wù)的特性是由各個(gè)程序相互合作而造成的。在 Linux 的 user space 下，則是所謂的 preemptive，各個(gè) process 喜歡執行什么就執行什么，就算你在你的程序里加上 while(1); 這一行也不會(huì )影響系統的運作。反正時(shí)間到了，系統自動(dòng)就會(huì )將你的程序停住，讓別的程序去執行。這是在 user space 的情況下，在 kernel 這方面，就跟 Windows 3.1 程序是一樣的。在 kernel 里，你必須適當的將 CPU 的執行權釋放出來(lái)。如果你在 kernel里加入 while(1); 這一行。那系統就會(huì )跟 Windows 3.1 一樣?？ㄔ谀抢?。當然啦，我是沒(méi)試過(guò)這樣去改 kernel，有興趣的人可以去試試看，如果有不同的結果，請記得告訴我。

假設我們在 kernel 里產(chǎn)生一個(gè) buffer，user 可以經(jīng)由 read，write 等 system call 來(lái)讀取或寫(xiě)資料到這個(gè) buffer 里。如果有一個(gè) user 寫(xiě)資料到 buffer 時(shí)，此時(shí) buffer 已經(jīng)滿(mǎn)了。那請問(wèn)你要如何去處理這種情形呢 ? 第一種，傳給 user 一個(gè)錯誤訊息，說(shuō) buffer 已經(jīng)滿(mǎn)了，不能再寫(xiě)入。第二種，將 user 的要求 block 住，等有人將 buffer 內容讀走，留出空位時(shí)，再讓 user 寫(xiě)入資料。但問(wèn)題來(lái)了，你要怎么將 user 的要求 block 住。難道你要用

while ( is_full );
write_to_buffer;

這樣的程序代碼嗎? 想想看，如果你這樣做會(huì )發(fā)生什么事? 第一，kernel會(huì )一直在這個(gè) while 里執行。第二個(gè)，如果 kernel 一直在這個(gè) while 里執行，表示它沒(méi)有辦法去 maintain系統的運作。那此時(shí)系統就相當于當掉了。在這里 is_full 是一個(gè)變量，當然，你可以讓 is_full 是一個(gè) function，在這個(gè) function里會(huì )去做別的事讓 kernel 可以運作，那系統就不會(huì )當。這是一個(gè)方式。但是，如果我們使用 wait_queue 的話(huà)，那程序看起來(lái)會(huì )比較漂亮，而且也比較讓人了解，如下所示:

struct wait_queue *wq = NULL; /* global variable */
while ( is_full ) {
interruptible_sleep_on( wq );
}
write_to_buffer();

interruptible_sleep_on( wq ) 是用來(lái)將目前的 process，也就是要求寫(xiě)資料到 buffer 的 process放到 wq 這個(gè) wait_queue 里。在 interruptible_sleep_on 里，則是最后會(huì )呼叫 schedule() 來(lái)做 schedule 的動(dòng)作，也就是去找另一個(gè) process 來(lái)執行以維持系統的運作。當執行完 interruptible_sleep_on 之后，要求 write 的 process 就會(huì )被 block 住。那什么時(shí)候會(huì )恢復執行呢 ? 這個(gè) process 之所以會(huì )被 block 住是因為 buffer 的空間滿(mǎn)了，無(wú)法寫(xiě)入。但是如果有人將 buffer 的資料讀取掉，則 buffer 就有空間可以讓人寫(xiě)入。所以，有關(guān)于叫醒 process 的動(dòng)作應該是在 read buffer 這方面的程序代碼做的。

extern struct wait_queue *wq;
if ( !is_empty ) {
read_from_buffer();
wake_up_interruptible( wq );
}
....

以上的程序代碼應該要放在 read buffer 這部分的程序代碼里，當 buffer 有多余的空間時(shí),我們就呼叫 wake_up_interruptible( wq ) 來(lái)將掛在 wq 上的所有 process 叫醒。請記得，我是說(shuō)將 wq 上的所有 process 叫醒，所以，如果如果有10個(gè) process 掛在 wq 上的話(huà)，那這 10 個(gè)都會(huì )被叫醒。之后，至于誰(shuí)先執行。則是要看 schedule 是怎么做的。就是因為這 10 個(gè)都會(huì )被叫醒。如果 A 先執行，而且萬(wàn)一很不湊巧的，A 又把 buffer 寫(xiě)滿(mǎn)了，那其它 9 個(gè) process 要怎么辦呢? 所以在 write buffer 的部分，需要用一個(gè) while 來(lái)檢查 buffer 目前是否滿(mǎn)了.如果是的話(huà)，那就繼續掛在 wq 上面.

上面所談的就是 wait_queue 的用法。很簡(jiǎn)單不是嗎? 接下來(lái)，我會(huì )再介紹一下 wait_queue 提供那些 function 讓我們使用。讓我再重申一次。wait_queue 應設為 global variable，比方叫 wq，只要任何的 process 想將自己掛在上面，就可以直接叫呼叫 sleep_on 等 function。要將 wq 上的 process 叫醒。只要呼叫 wake_up 等 function 就可以了.

就我所知，wait_queue 提供4個(gè) function 可以使用，兩個(gè)是用來(lái)將 process 加到 wait_queue 的:

sleep_on( struct wait_queue **wq );
interruptible_sleep_on( struct wait_queue **wq );

另外兩個(gè)則是將process從wait_queue上叫醒的。

wake_up( struct wait_queue **wq );
wake_up_interruptible( struct wait_queue **wq );

我現在來(lái)解釋一下為什么會(huì )有兩組。有 interruptible 的那一組是這樣子的。當我們去 read 一個(gè)沒(méi)有資料可供讀取的 socket 時(shí)，process 會(huì ) block 在那里。如果我們此時(shí)按下 Ctrl C，那 read() 就會(huì )傳回 EINTR。像這種的 block IO 就是使用 interruptible_sleep_on() 做到的。也就是說(shuō)，如果你是用 interruptible_sleep_on() 來(lái)將 process 放到 wait_queue 時(shí)，如果有人送一個(gè) signal 給這個(gè) process，那它就會(huì )自動(dòng)從 wait_queue 中醒來(lái)。但是如果你是用 sleep_on() 把 process 放到 wq 中的話(huà)，那不管你送任何的 signal 給它，它還是不會(huì )理你的。除非你是使用 wake_up() 將它叫醒。sleep 有兩組。wake_up 也有兩組。wake_up_interruptible() 會(huì )將 wq 中使用 interruptible_sleep_on() 的 process 叫醒。至于 wake_up() 則是會(huì )將 wq 中所有的 process 叫醒。包括使用 interruptible_sleep_on() 的 process。

在使用 wait_queue 之前有一點(diǎn)需要特別的小心，呼叫 interruptible_sleep_on() 以及 sleep_on() 的 function 必須要是 reentrant。簡(jiǎn)單的說(shuō)，reentrant 的意思是說(shuō)此 function不會(huì )改變任何的 global variable，或者是不會(huì ) depend on 任何的 global variable，或者是在呼叫 interruptible_sleep_on() 或 sleep_on() 之后不會(huì ) depend on 任何的 global variable。因為當此 function 呼叫 sleep_on() 時(shí)，目前的 process 會(huì )被暫停執行?？赡芰硪粋€(gè) process 又會(huì )呼叫此 function。若之前的 process 將某些 information 存在 global variable，等它恢復執行時(shí)要使用，結果第二行程進(jìn)來(lái)了，又把這個(gè) global variable 改掉了。等第一個(gè) process 恢復執行時(shí)，放在 global variable 中的 information 都變了。產(chǎn)生的結果恐怕就不是我們所能想象了。其實(shí)，從 process 執行指令到此 function 中所呼叫的 function 都應該是要 reentrant 的。不然，很有可能還是會(huì )有上述的情形發(fā)生.

由于 wait_queue 是 kernel 所提供的，所以，這個(gè)例子必須要放到 kernel 里去執行。我使用的這個(gè)例子是一個(gè)簡(jiǎn)單的 driver。它會(huì ) maintain 一個(gè) buffer，大小是 8192 bytes。提供 read跟 write 的功能。當 buffer 中沒(méi)有資料時(shí)，read() 會(huì )馬上傳回，也就是不做 block IO。而當 write buffer 時(shí)，如果呼叫 write() 時(shí)，空間已滿(mǎn)或寫(xiě)入的資料比 buffer 大時(shí)，就會(huì )被 block 住，直到有人將 buffer 里的資料讀出來(lái)為止。在 write buffer 的程序代碼中，我們使用 wait_queue 來(lái)做到 block IO 的功能。在這里，我會(huì )將此 driver 寫(xiě)成 module，方便加載 kernel。

第一步，這個(gè) driver 是一個(gè)簡(jiǎn)單的 character device driver。所以，我們先在 /dev 下產(chǎn)生一個(gè) character device。major number 我們找一個(gè)比較沒(méi)人使用的，像是 54，minor number 就用 0。接著(zhù)下一個(gè)命令.

mknod /dev/buf c 54 0

mknod 是用來(lái)產(chǎn)生 special file 的 command。/dev/buf 表示要產(chǎn)生叫 buf 的檔案，位于 /dev 下。 c 表示它是一個(gè) character device。54 為其 major number，0 則是它的 minor number。有關(guān) character device driver 的寫(xiě)法。有機會(huì )我再跟各位介紹，由于這次是講 wait_queue，所以，就不再多提 driver 方面的東西.

第二步，我們要寫(xiě)一個(gè) module，底下是這個(gè) module 的程序代碼:

buf.c
#define MODULE
#include
#include
#include
#include
#include
#define BUF_LEN 8192

int flag; /* when rp = wp,flag = 0 for empty,flag = 1 for
non-empty */
char *wp，*rp;
char buffer[BUF_LEN];
EXPORT_NO_SYMBOLS; /* don't export anything */

static ssize_t buf_read( struct file *filp，char *buf，size_t count，
loff_t *ppos )
{
return count;
}

static ssize_t buf_write( struct file *filp，const char *buf，size_t count，
loff_t *ppos )
{
return count;
}

static int buf_open( struct inode *inode，struct file *filp )
{
MOD_INC_USE_COUNT;
return 0;
}

static int buf_release( struct inode *inode，struct file *filp )
{
MOD_DEC_USE_COUNT;
return 0;
}

static struct file_operations buf_fops = {
NULL， /* lseek */
buf_read,
buf_write,
NULL， /* readdir */
NULL， /* poll */
NULL， /* ioctl */
NULL， /* mmap */
buf_open， /* open */
NULL， /* flush */
buf_release， /* release */
NULL， /* fsync */
NULL， /* fasync */
NULL， /* check_media_change */
NULL， /* revalidate */
NULL /* lock */
};

static int buf_init()
{
int result;

flag = 0;
wp = rp = buf;

result = register_chrdev( 54，"buf"，buf_fops );
if ( result 0 ) {
printk( "5>buf: cannot get major 54n" );
return result;
}

return 0;
}

static void buf_clean()
{
if ( unregister_chrdev( 54，"buf" ) ) {
printk( "5>buf: unregister_chrdev errorn" );
}
}

int init_module( void )
{
return buf_init();
}

void cleanup_module( void )
{
buf_clean();
}

有關(guān) module 的寫(xiě)法，請各位自行參考其它的文件，最重要的是要有 init_module()和 cleanup_module() 這兩個(gè) function。我在這兩個(gè) function 里分別做 initialize 和 finalize 的動(dòng)作?，F在分別解釋一下。在 init_module() 里，只有呼叫 buf_init() 而己。其實(shí)，也可以將 buf_init() 的 code 寫(xiě)到 init_module() 里。只是我覺(jué)得這樣比較好而已。

flag = 0;
wp = rp = buf;
result = register_chrdev( 54，"buf"，buf_fops );
if ( result 0 ) {
printk( "5>buf: cannot get major 54n" );
return result;
}
return 0;

init_buf() 做的事就是去注冊一個(gè) character device driver。在注冊一個(gè) character device driver 之前，必須要先準備一個(gè)型別為 file_operations 結構的變量，file_operations 里包含了一些 function pointer。driver 的作者必須自己寫(xiě)這些 function。并將 function address 放到這個(gè)結構里。如此一來(lái)，當 user 去讀取這個(gè) device 時(shí)，kernel 才有辦法去呼叫對應這個(gè) driver 的 function。其實(shí)，簡(jiǎn)要來(lái)講。character device driver 就是這么一個(gè) file_operations 結構的變量。file_operations 定義在 這個(gè)檔案里。它的 prototype 在 kernel 2.2.1 與以前的版本有些微的差異，這點(diǎn)是需要注意的地方。

register_chrdev() 看名字就大概知道是要注冊 character device driver。第一個(gè)參數是此 device 的 major number。第二個(gè)是它的名字。名字你可以隨便取。第三個(gè)的參數就是一個(gè) file_operations 變量的地址。init_module() 必須要傳回 0，module 才會(huì )被加載。

在 cleanup_module() 的部分，我們也是只呼叫 buf_clean() 而已。它做的事是 unregister 的動(dòng)作。

if ( unregister_chrdev( 54，"buf" ) ) {
printk( "5>buf: unregister_chrdev errorn" );
}

也就是將原本記錄在 device driver table 上的資料洗掉。第一個(gè)參數是 major number。第二個(gè)則是此 driver 的名稱(chēng)，這個(gè)名字必須要跟 register_chrdev() 中所給的名字一樣才行。

現在我們來(lái)看看此 driver 所提供的 file_operations 是那些。

static struct file_operations buf_fops = {
NULL， /* lseek */
buf_read,
buf_write,
NULL， /* readdir */
NULL， /* poll */
NULL， /* ioctl */
NULL， /* mmap */
buf_open， /* open */
NULL， /* flush */
buf_release， /* release */
NULL， /* fsync */
NULL， /* fasync */
NULL， /* check_media_change */
NULL， /* revalidate */
NULL /* lock */
};

在此，我們只打算 implement buf_read()，buf_write()，buf_open，和 buf_release()等 function 而已。當 user 對這個(gè) device 呼叫 open() 的時(shí)候，buf_open() 會(huì )在最后被 kernel 呼叫。相同的，當呼叫 close()，read()，和 write() 時(shí)，buf_release()，buf_read()，和 buf_write() 也都會(huì )分別被呼叫。首先，我們先來(lái)看看 buf_open()。

static int buf_open( struct inode *inode，struct file *filp )
MOD_INC_USE_COUNT;
return 0;
}

buf_open() 做的事很簡(jiǎn)單。就是將此 module 的 use count 加一。這是為了避免當此 module 正被使用時(shí)不會(huì )被從 kernel 移除掉。相對應的，在 buf_release() 中，我們應該要將 use count 減一。就像開(kāi)啟檔案一樣。有 open()，就應該要有對應的 close() 才行。如果 module 的 use count 在不為 0 的話(huà)，那此 module 就無(wú)法從 kernel 中移除了。

static int buf_release( struct inode *inode，struct file *filp )
{
MOD_DEC_USE_COUNT;
return 0;
}

接下來(lái)，我們要看一下buf_read()和buf_write()。

static ssize_t buf_read( struct file *filp，char *buf，size_t count,
loff_t *ppos )
{
return count;
}

static ssize_t buf_write( struct file *filp，const char *buf，
size_t count，loff_t *ppos )
{
return count;
}

在此，我們都只是回傳 user 要求讀取或寫(xiě)入的字符數目而已。在此，我要說(shuō)明一下這些參數的意義。filp 是一個(gè) file 結構的 pointer。也就是指我們在 /dev 下所產(chǎn)生的 buf 檔案的 file 結構。當我們呼叫 read() 或 write() 時(shí)，必須要給一個(gè) buffer 以及要讀寫(xiě)的長(cháng)度。Buf 指的就是這個(gè) buffer，而 count 指的就是長(cháng)度。至于 ppos 是表示目前這個(gè)檔案的 offset 在那里。這個(gè)值對普通檔案是有用的。也就是跟 lseek() 有關(guān)系。由于在這里是一個(gè) drvice。所以 ppos 在此并不會(huì )用到。有一點(diǎn)要小心的是，上面參數 buf 是一個(gè)地址，而且還是一個(gè) user space 的地址，當 kernel 呼叫 buf_read() 時(shí)，程序在位于 kernel space。所以你不能直接讀寫(xiě)資料到 buf 里。必須先切換 FS 這個(gè) register 才行。

Makefile
P = buf
OBJ = buf.o
INCLUDE = -I/usr/src/linux/include/linux
CFLAGS = -D__KERNEL__ -DMODVERSIONS -DEXPORT_SYMTAB -O $(INCLUDE)
-include /usr/src/linux/include/linux/modversions.h
CC = gcc

$(P): $(OBJ)
ld -r $(OBJ) -o $(P).o

.c.o:
$(CC) -c $(CFLAGS) $

clean:
rm -f *.o *~ $(P)

加入上面這個(gè) Makefile，打入 make 之后，就會(huì )產(chǎn)生一個(gè) buf.o 的檔案。利用 insmod 將 buf.o 載到 kernel 里。相信大家應該都用過(guò) /dev/zero 這個(gè) device。去讀取這個(gè) device，只會(huì )得到空的內容。寫(xiě)資料到這個(gè) device 里也只會(huì )石沈大?！，F在你可以去比較 buf 和 zero 這兩個(gè) device。兩者的行為應該很類(lèi)似才是。

第三步，我們在第二步中 implement 一個(gè)像 zero 的 device driver。我們現在要經(jīng)由修改它來(lái)使用 wait_queue。首先，我們先加入一個(gè) global variable，write_wq，并把它設為 NULL。

struct wait_queue *write_wq = NULL;

然后，在 buf_read() 里，我們要改寫(xiě)成這個(gè)樣子。

static ssize_t buf_read( struct file *filp，char *buf，size_t count，
loff_t *ppos )
{
int num，nRead;
nRead = 0;
while ( ( wp == rp ) !flag ) { /* buffer is empty */
return 0;
}

repeate_reading:
if ( rp wp ) {
num = min( count，( int ) ( wp-rp ) );
}
else {
num = min( count，( int ) ( buffer BUF_LEN-rp ) );
}
copy_to_user( buf，rp，num );
rp = num;
count -= num;
nRead = num;
if ( rp == ( buffer BUF_LEN ) )
rp = buffer;
if ( ( rp != wp ) ( count > 0 ) )
goto repeate_reading;
flag = 0;
wake_up_interruptible( write_wq );
return nRead;
}

在前頭我有提到，buf 的地址是屬于 user space 的。在 kernel space 中，你不能像普通寫(xiě)到 buffer 里一樣直接將資料寫(xiě)到 buf 里，或直接從 buf 里讀資料。Linux 里使用 FS 這個(gè) register 來(lái)當作 kernel space 和 user space 的切換。所以，如果你想手動(dòng)的話(huà)，可以這樣做:

mm_segment_t fs;
fs = get_fs();
set_fs( USER_DS );
write_data_to_buf( buf );
set_fs( fs );

也就是先切換到 user space，再寫(xiě)資料到 buf 里。之后記得要切換回來(lái) kernel space。這種自己動(dòng)手的方法比較麻煩，所以 Linux 提供了幾個(gè) function，可以讓我們直接在不同的 space 之間做資料的搬移。誠如各位所見(jiàn)，copy_to_user() 就是其中一個(gè)。

copy_to_user( to，from，n );
copy_from_user( to，from，n );

顧名思義，copy_to_user() 就是將資料 copy 到 user space 的 buffer 里，也就是從 to 寫(xiě)到 from，n 為要 copy 的 byte 數。相同的，copy_from_user() 就是將資料從 user space 的 from copy 到位于 kernel 的 to 里，長(cháng)度是 n bytes。在以前的 kernel 里，這兩個(gè) function 的前身是 memcpy_tofs() 和 memcpy_fromfs()，不知道為什么到了 kernel 2.2.1之后，名字就被改掉了。至于它們的程序代碼有沒(méi)有更改就不太清楚了。至于到那一版才改的。我沒(méi)有仔細去查，只知道在 2.0.36 時(shí)還沒(méi)改，到了 2.2.1 就改了。這兩個(gè) function 是 macro，都定義在 里。要使用前記得先 include 進(jìn)來(lái)。

相信 buf_read() 的程序代碼應當不難了解才對。不知道各位有沒(méi)有看到，在buf_read() 的后面有一行的程序，就是

wake_up_interruptible( write_wq );

write_wq 是我們用來(lái)放那些想要寫(xiě)資料到 buffer，但 buffer 已滿(mǎn)的 process。這一行的程序會(huì )將掛在此 queue 上的 process 叫醒。當 queue 是空的時(shí)，也就是當 write_wq 為 NULL 時(shí)，wake_up_interruptible() 并不會(huì )造成任何的錯誤。接下來(lái)，我們來(lái)看看更改后的 buf_write()。

static ssize_t buf_write( struct file *filp，const char *buf，size_t count，loff_t *ppos )
{
int num，nWrite;
nWrite = 0;
while ( ( wp == rp ) flag ) {
interruptible_sleep_on( write_wq );
}

repeate_writing:
if ( rp > wp ) {
num = min( count，( int ) ( rp - wp ) );
}
else {
num = min( count，( int ) ( buffer BUF_LEN - wp ) );
}
copy_from_user( wp，buf，num );
wp = num;
count -= num;
nWrite = num;
if ( wp == ( buffer BUF_LEN ) ) {
wp = buffer;
}
if ( ( wp != rp ) ( count > 0 ) ) {
goto repeate_writing;
}
flag = 1;
return nWrite;
}

我們把 process 丟到 write_wq 的動(dòng)作放在 buf_write() 里。當 buffer 已滿(mǎn)時(shí)，就直接將 process 丟到 write_wq 里.

while ( ( wp == rp ) flag ) {
interruptible_sleep_on( write_wq );
}

好了?，F在程序已經(jīng)做了一些修改。再重新 make 一次，利用 insmod 將 buf.o 載到 kernel 里就行了。接著(zhù)，我們就來(lái)試驗一下是不是真正做到 block IO.

# cd /dev
# ls -l ~/WWW-HOWTO
-rw-r--r-- 1 root root 23910 Apr 14 16:50 /root/WWW-HOWTO
# cat ~/WWW-HOWTO > buf

執行到這里，應該會(huì )被 block 住?，F在，我們再開(kāi)一個(gè) shell 出來(lái).

# cd /dev
# cat buf
..。( contents of WWW-HOWTO ) ..。skip ...

此時(shí)，WWW-HOWTO 的內容就會(huì )出現了。而且之前 block 住的 shell 也已經(jīng)回來(lái)了。最后，試驗結束，可以下

# rmmod buf

將 buf 這個(gè) module 從 kernel 中移除。以上跟各位介紹的就是 wait_queue 的使用。希望能對各位有所助益。

我想對某些人來(lái)講，會(huì )使用一個(gè)東西就夠了。然而對某些人來(lái)講，可能也很希望知道這項東西是如何做出來(lái)的。至少我就是這種人。在下面，我將為各位介紹 wait_queue 的 implementation。如果對其 implementation 沒(méi)興趣，以下這一段就可以略過(guò)不用看了。

wait_queue 是定義在 里，我們可以先看看它的數據結構是怎么樣:

struct wait_queue {
struct task_struct * task;
struct wait_queue * next;
};

很簡(jiǎn)單是吧。這個(gè)結構里面只有二個(gè)字段，一個(gè)是 task_struct 的 pointer，另一個(gè)則是 wait_queue 的 pointer。很明顯的，我們可以看出 wait_queue 其實(shí)就是一個(gè) linked list,而且它還是一個(gè) circular linked list。 其中 task_struct 就是用來(lái)指呼叫 sleep_on 等 function的 process。在 Linux 里，每一個(gè) process 是由一個(gè) task_struct 來(lái)描敘。task_struct 是一個(gè)很大的的結構，在此我們不會(huì )討論。Linux 里有一個(gè) global variable，叫 current，它會(huì )指到目前正在執行的 process 的 task_struct 結構。這也就是為什么當 process 呼叫 system call，切換到 kernel 時(shí)，kernel 會(huì )知道是那個(gè) process 呼叫的。

好，我們現在來(lái)看看 interruptible_sleep_on() 和 sleep_on() 是如何做的。這兩個(gè) function 都是位于 /usr/src/linux/kernel/sched.c 里。

void interruptible_sleep_on(struct wait_queue **p)
{
SLEEP_ON_VAR
current->state = TASK_INTERRUPTIBLE;
SLEEP_ON_HEAD
schedule();
SLEEP_ON_TAIL
}

void sleep_on(struct wait_queue **p)
{
SLEEP_ON_VAR
current->state = TASK_UNINTERRUPTIBLE;
SLEEP_ON_HEAD
schedule();
SLEEP_ON_TAIL
}

各位有沒(méi)有發(fā)現這兩個(gè) function 很類(lèi)似。是的，它們唯一的差別就在于

current->state = ...

這一行而已。之前，我們有說(shuō)過(guò)，interruptible_sleep_on() 可以被 signal 中斷，所以，其 current->state 被設為 TASK_INTERRUPTIBLE。而 sleep_on() 沒(méi)辦法被中斷，所以 current->state 設為 TASK_UNINTERRUPTIBLE。接下來(lái)，我們只看 interruptible_sleep_on() 就好了。畢竟它們兩的差異只在那一行而已。

在 sched.c 里，SLEEP_ON_VAR 是一個(gè) macro，其實(shí)它只是定義兩個(gè)區域變量出來(lái)而已。

#defineSLEEP_ON_VAR
unsigned long flags;
struct wait_queue wait;

剛才我也說(shuō)過(guò)，current 這個(gè)變量是指到目前正在執行的 process 的 task_struct 結構。所以 current->state = TASK_INTERRUPTIBLE 會(huì )設定在呼叫 interruptible_sleep_on() 的 process 身上。至于 SLEEP_ON_HEAD 做的事，則是將 current 的值放到 SLEEP_ON_VAR 宣告的 wait 變量里，并把 wait 放到 interruptible_sleep_on() 的參數所屬的 wait_queue list 中。

#defineSLEEP_ON_HEAD
wait.task = current;
write_lock_irqsave(waitqueue_lock，flags);
__add_wait_queue(p，wait);
write_unlock(waitqueue_lock);

wait 是在 SLEEP_ON_VAR 中宣告的區域變量。其 task 字段被設成呼叫 interruptible_sleep_on() 的 process。至于 waitqueue_lock 這個(gè)變量是一個(gè) spin lock。 waitqueue_lock 是用來(lái)確保同一時(shí)間只能有一個(gè) writer。但同一時(shí)間則可以有好幾個(gè) reader。也就是說(shuō) waitqueue_lock 是用來(lái)保證 critical section 的 mutual exclusive access。

unsigned long flags;
write_lock_irqsave(waitqueue_lock，flags);
...critical section ...
write_unlock(waitqueue_lock)

學(xué)過(guò) OS 的人應該知道 critical section 的作用是什么，如有需要，請自行參考 OS 參考書(shū)。在 critical section 里只做一件事，就是將 wait 這個(gè)區域變量放到 p 這個(gè) wait_queue list 中。 p 是 user 在呼叫 interruptible_sleep_on() 時(shí)傳進(jìn)來(lái)的，它的型別是 struct wait_queue **。在此， critical section 只呼叫 __add_wait_queue()。

extern inline void __add_wait_queue(struct wait_queue ** p，
struct wait_queue * wait)
{
wait->next = *p ? : WAIT_QUEUE_HEAD(p);
*p = wait;
}

__add_wait_queue() 是一個(gè)inline function，定義在 中。WAIT_QUEUE_HEAD()是個(gè)很有趣的 macro，待會(huì )我們再討論?，F在只要知道它會(huì )傳回這個(gè) wait_queue 的開(kāi)頭就可以了。所以，__add_wait_queue() 的意思就是要把 wait 放到 p 所屬的 wait_queue list 的開(kāi)頭。但是，大家還記得嗎? 在上面的例子里，一開(kāi)始我們是把 write_wq 設為 NULL。也就是說(shuō) *p 是 NULL。所以，當 *p 是 NULL 時(shí),

wait->next = WAIT_QUEUE_HEAD(p)

是什么意思呢?

所以，現在，我們來(lái)看一下 WAIT_QUEUE_HEAD() 是怎么樣的一個(gè) macro，它是定義在 里。

#define WAIT_QUEUE_HEAD(x) ((struct wait_queue *)((x)-1))

x 型別是 struct wait_queue **，因為是一個(gè) pointer，所以大小是 4 byte。因此，若 x 為 100 的話(huà)，那 ((x)-1) 就變成 96。如下圖所示。 WAIT_QUEUE_HEAD(x) 其實(shí)會(huì )傳回 96，而且將其轉型為 struct wait_queue*，各位可以看看。原本的 wait_queue* 只配制在 100-104 之間?，F在 WAIT_QUEUE_HEAD(x) 卻直接傳回96，但是 96-100 這塊位置根本沒(méi)有被我們配置起來(lái)。更妙的事。由于 x 是一個(gè) wait_queue list 的開(kāi)頭，我們始終不會(huì )用到 96-100 這塊，我們只會(huì )直接使用到 100-104 這塊內存。這也算是 wait_queue 一項比較奇怪的 implementation 方式吧。下面有三張圖，第一張表示我們宣告了一個(gè) wait_queue* 的變量，地址在 100。另外還有一個(gè) wait_queue 的變量，名叫 wait。第二張圖是我們呼叫 interruptible_sleep_on() 之后得到的結果。第三張則是我們又宣告一個(gè) wait_queue，名叫 ano_wait，將 ano_wait 放到 wait_queue list 后的結果就第三張圖所顯示的。http:/linuxfab.cx/Columns/10/wqq.GIF

在 interruptible_sleep_on() 中，當呼叫完 SLEEP_ON_HEAD 之后，目前的 process 就已經(jīng)被放到 wait_queue 中了。接下來(lái)會(huì )直接呼叫 schedule()，這個(gè) function 是用來(lái)做 scheduling 用的。current 所指到的 process 會(huì )被放到 scheduling queue 中等待被挑出來(lái)執行。執行完 schedule() 之后，current 就沒(méi)辦法繼續執行了。而當 current 以后被 wake up 時(shí)，就會(huì )從 schedule() 之后，也就是從 SLEEP_ON_TAIL 開(kāi)始執行。SLEEP_ON_TAIL 做的事剛好跟 SLEEP_ON_HEAD 相反，它會(huì )將此 process 從 wait_queue 中移除。

#defineSLEEP_ON_TAIL
write_lock_irq(waitqueue_lock);
__remove_wait_queue(p，wait);
write_unlock_irqrestore(waitqueue_lock，flags);

跟 SLEEP_ON_HEAD 一樣。SLEEP_ON_TAIL 也是利用 spin lock 包住一個(gè) critical section。

extern inline void __remove_wait_queue(struct wait_queue ** p，struct
wait_queue * wait)
{
struct wait_queue * next = wait->next;
struct wait_queue * head = next;
struct wait_queue * tmp;
while ((tmp = head->next) != wait) {
head = tmp;
}
head->next = next;
}

__remove_wait_queue() 是一個(gè) inline function，也是同樣定義在 里。是用來(lái)將 wait 從 p 這個(gè) wait_queue list 中移除掉。

現在，大家應該已經(jīng)清楚了 interruptible_sleep_on() 和 sleep_on() 的做法，也應該比較清楚 wait_queue 是如何的做到 block IO。接下來(lái)，我們繼續看 wake_up_interruptible() 和 wake_up() 是如何 implement 的。wake_up_interruptible() 和 wake_up() 其實(shí)是兩個(gè) macro，都定義在 里。

#define wake_up(x) __wake_up((x),TASK_UNINTERRUPTIBLE |
TASK_INTERRUPTIBLE)
#define wake_up_interruptible(x) __wake_up((x),TASK_INTERRUPTIBLE)

從這里可以看出，兩個(gè) macro 幾乎是一樣的，差別只在于傳給 __wake_up() 中的一個(gè) flag 有所差異而已。其實(shí)，wake_up() 傳給 __wake_up() 的是 TASK_UNINTERRUPTIBLE|TASK_INTERRUPTIBLE，意思是說(shuō)它會(huì )將 wait_queue list 中 process->state 是 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 的所有 process 叫醒。而 wake_up_interruptible() 則只將 state是 TASK_INTERRUPTIBLE 的叫醒.

void __wake_up(struct wait_queue **q，unsigned int mode)
{
struct wait_queue *next;
read_lock(waitqueue_lock);
if (q (next = *q)) {
struct wait_queue *head;
head = WAIT_QUEUE_HEAD(q);
while (next != head) {
struct task_struct *p = next->task;
next = next->next;
if (p->state mode)
wake_up_process(p);
}
}
read_unlock(waitqueue_lock);
}

在 wake up 的過(guò)程中，我們不需要設定 write lock，但是仍要設定 read lock，這是為了避免有人在我們讀取 wait_queue 時(shí)去寫(xiě) wait_queue list 的內容，造成 inconsistent。在這段程序代碼中，是去 transverse 整個(gè) list，如果 process 的 state 跟 mode 有吻合，則呼叫 wake_up_process() 將它叫醒。

void wake_up_process(struct task_struct * p)
{
unsigned long flags;
spin_lock_irqsave(runqueue_lock，flags);
p->state = TASK_RUNNING;
if (!p->next_run) {
add_to_runqueue(p);
reschedule_idle(p);
}
spin_unlock_irqrestore(runqueue_lock，flags);
}

在此，runqueue_lock 也是一個(gè) spin lock，kernel 依然在此設一個(gè) critical section 以方便更改 run queue。Run queue 是用來(lái)放可以執行的 process 用的。在放入 run queue 之前，會(huì )先將 process 的 state 設為 TASK_RUNNING。

wait_queue 其實(shí)是一個(gè)蠻好用的東西。相信只要各位有機會(huì )去修改 kernel 的話(huà)，都應該有機會(huì )用到它才對。希望對大家有點(diǎn)幫助。