內(nèi)核等待隊(duì)列機(jī)制介紹

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

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

while (1);

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

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

while ( is_full );
write_to_buffer;

這樣的程序代碼嗎? 想想看，如果你這樣做會(huì)發(fā)生什么事? 第一，kernel會(huì)一直在這個(gè) while 里執(zhí)行。第二個(gè)，如果 kernel 一直在這個(gè) while 里執(zhí)行，表示它沒有辦法去 maintain系統(tǒng)的運(yùn)作。那此時(shí)系統(tǒng)就相當(dāng)于當(dāng)?shù)袅?。在這里 is_full 是一個(gè)變量，當(dāng)然，你可以讓 is_full 是一個(gè) function，在這個(gè) function里會(huì)去做別的事讓 kernel 可以運(yùn)作，那系統(tǒng)就不會(huì)當(dāng)。這是一個(gè)方式。但是，如果我們使用 wait_queue 的話，那程序看起來(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，也就是要求寫資料到 buffer 的 process放到 wq 這個(gè) wait_queue 里。在 interruptible_sleep_on 里，則是最后會(huì)呼叫 schedule() 來(lái)做 schedule 的動(dòng)作，也就是去找另一個(gè) process 來(lái)執(zhí)行以維持系統(tǒng)的運(yùn)作。當(dāng)執(zhí)行完 interruptible_sleep_on 之后，要求 write 的 process 就會(huì)被 block 住。那什么時(shí)候會(huì)恢復(fù)執(zhí)行呢 ? 這個(gè) process 之所以會(huì)被 block 住是因?yàn)?buffer 的空間滿了，無(wú)法寫入。但是如果有人將 buffer 的資料讀取掉，則 buffer 就有空間可以讓人寫入。所以，有關(guān)于叫醒 process 的動(dòng)作應(yīng)該是在 read buffer 這方面的程序代碼做的。

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

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

上面所談的就是 wait_queue 的用法。很簡(jiǎn)單不是嗎? 接下來(lái)，我會(huì)再介紹一下 wait_queue 提供那些 function 讓我們使用。讓我再重申一次。wait_queue 應(yīng)設(shè)為 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 );

我現(xiàn)在來(lái)解釋一下為什么會(huì)有兩組。有 interruptible 的那一組是這樣子的。當(dāng)我們?nèi)?read 一個(gè)沒有資料可供讀取的 socket 時(shí)，process 會(huì) block 在那里。如果我們此時(shí)按下 Ctrl C，那 read() 就會(huì)傳回 EINTR。像這種的 block IO 就是使用 interruptible_sleep_on() 做到的。也就是說，如果你是用 interruptible_sleep_on() 來(lái)將 process 放到 wait_queue 時(shí)，如果有人送一個(gè) signal 給這個(gè) process，那它就會(huì)自動(dòng)從 wait_queue 中醒來(lái)。但是如果你是用 sleep_on() 把 process 放到 wq 中的話，那不管你送任何的 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)單的說，reentrant 的意思是說此 function不會(huì)改變?nèi)魏蔚?global variable，或者是不會(huì) depend on 任何的 global variable，或者是在呼叫 interruptible_sleep_on() 或 sleep_on() 之后不會(huì) depend on 任何的 global variable。因?yàn)楫?dāng)此 function 呼叫 sleep_on() 時(shí)，目前的 process 會(huì)被暫停執(zhí)行?？赡芰硪粋€(gè) process 又會(huì)呼叫此 function。若之前的 process 將某些 information 存在 global variable，等它恢復(fù)執(zhí)行時(shí)要使用，結(jié)果第二行程進(jìn)來(lái)了，又把這個(gè) global variable 改掉了。等第一個(gè) process 恢復(fù)執(zhí)行時(shí)，放在 global variable 中的 information 都變了。產(chǎn)生的結(jié)果恐怕就不是我們所能想象了。其實(shí)，從 process 執(zhí)行指令到此 function 中所呼叫的 function 都應(yīng)該是要 reentrant 的。不然，很有可能還是會(huì)有上述的情形發(fā)生.

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

第一步，這個(gè) driver 是一個(gè)簡(jiǎn)單的 character device driver。所以，我們先在 /dev 下產(chǎn)生一個(gè) character device。major number 我們找一個(gè)比較沒人使用的，像是 54，minor number 就用 0。接著下一個(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 的寫法。有機(jī)會(huì)我再跟各位介紹，由于這次是講 wait_queue，所以，就不再多提 driver 方面的東西.

第二步，我們要寫一個(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 的寫法，請(qǐng)各位自行參考其它的文件，最重要的是要有 init_module()和 cleanup_module() 這兩個(gè) function。我在這兩個(gè) function 里分別做 initialize 和 finalize 的動(dòng)作?，F(xiàn)在分別解釋一下。在 init_module() 里，只有呼叫 buf_init() 而己。其實(shí)，也可以將 buf_init() 的 code 寫到 init_module() 里。只是我覺得這樣比較好而已。

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

register_chrdev() 看名字就大概知道是要注冊(cè) character device driver。第一個(gè)參數(shù)是此 device 的 major number。第二個(gè)是它的名字。名字你可以隨便取。第三個(gè)的參數(shù)就是一個(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è)參數(shù)是 major number。第二個(gè)則是此 driver 的名稱，這個(gè)名字必須要跟 register_chrdev() 中所給的名字一樣才行。

現(xiàn)在我們來(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 而已。當(dāng) user 對(duì)這個(gè) device 呼叫 open() 的時(shí)候，buf_open() 會(huì)在最后被 kernel 呼叫。相同的，當(dāng)呼叫 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 加一。這是為了避免當(dāng)此 module 正被使用時(shí)不會(huì)被從 kernel 移除掉。相對(duì)應(yīng)的，在 buf_release() 中，我們應(yīng)該要將 use count 減一。就像開啟檔案一樣。有 open()，就應(yīng)該要有對(duì)應(yīng)的 close() 才行。如果 module 的 use count 在不為 0 的話，那此 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 要求讀取或?qū)懭氲淖址麛?shù)目而已。在此，我要說明一下這些參數(shù)的意義。filp 是一個(gè) file 結(jié)構(gòu)的 pointer。也就是指我們?cè)?/dev 下所產(chǎn)生的 buf 檔案的 file 結(jié)構(gòu)。當(dāng)我們呼叫 read() 或 write() 時(shí)，必須要給一個(gè) buffer 以及要讀寫的長(zhǎng)度。Buf 指的就是這個(gè) buffer，而 count 指的就是長(zhǎng)度。至于 ppos 是表示目前這個(gè)檔案的 offset 在那里。這個(gè)值對(duì)普通檔案是有用的。也就是跟 lseek() 有關(guān)系。由于在這里是一個(gè) drvice。所以 ppos 在此并不會(huì)用到。有一點(diǎn)要小心的是，上面參數(shù) buf 是一個(gè)地址，而且還是一個(gè) user space 的地址，當(dāng) kernel 呼叫 buf_read() 時(shí)，程序在位于 kernel space。所以你不能直接讀寫資料到 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 里。相信大家應(yīng)該都用過 /dev/zero 這個(gè) device。去讀取這個(gè) device，只會(huì)得到空的內(nèi)容。寫資料到這個(gè) device 里也只會(huì)石沈大海?，F(xiàn)在你可以去比較 buf 和 zero 這兩個(gè) device。兩者的行為應(yīng)該很類似才是。

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

struct wait_queue *write_wq = NULL;

然后，在 buf_read() 里，我們要改寫成這個(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 中，你不能像普通寫到 buffer 里一樣直接將資料寫到 buf 里，或直接從 buf 里讀資料。Linux 里使用 FS 這個(gè) register 來(lái)當(dāng)作 kernel space 和 user space 的切換。所以，如果你想手動(dòng)的話，可以這樣做:

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

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

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

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

相信 buf_read() 的程序代碼應(yīng)當(dāng)不難了解才對(duì)。不知道各位有沒有看到，在buf_read() 的后面有一行的程序，就是

wake_up_interruptible( write_wq );

write_wq 是我們用來(lái)放那些想要寫資料到 buffer，但 buffer 已滿的 process。這一行的程序會(huì)將掛在此 queue 上的 process 叫醒。當(dāng) queue 是空的時(shí)，也就是當(dāng) write_wq 為 NULL 時(shí)，wake_up_interruptible() 并不會(huì)造成任何的錯(cuò)誤。接下來(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() 里。當(dāng) buffer 已滿時(shí)，就直接將 process 丟到 write_wq 里.

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

好了?，F(xiàn)在程序已經(jīng)做了一些修改。再重新 make 一次，利用 insmod 將 buf.o 載到 kernel 里就行了。接著，我們就來(lái)試驗(yàn)一下是不是真正做到 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

執(zhí)行到這里，應(yīng)該會(huì)被 block 住?，F(xiàn)在，我們?cè)匍_一個(gè) shell 出來(lái).

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

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

# rmmod buf

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

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

wait_queue 是定義在 里，我們可以先看看它的數(shù)據(jù)結(jié)構(gòu)是怎么樣:

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

很簡(jiǎn)單是吧。這個(gè)結(jié)構(gòu)里面只有二個(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è)很大的的結(jié)構(gòu)，在此我們不會(huì)討論。Linux 里有一個(gè) global variable，叫 current，它會(huì)指到目前正在執(zhí)行的 process 的 task_struct 結(jié)構(gòu)。這也就是為什么當(dāng) process 呼叫 system call，切換到 kernel 時(shí)，kernel 會(huì)知道是那個(gè) process 呼叫的。

好，我們現(xiàn)在來(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
}

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

current->state = ...

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

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

#defineSLEEP_ON_VAR
unsigned long flags;
struct wait_queue wait;

剛才我也說過，current 這個(gè)變量是指到目前正在執(zhí)行的 process 的 task_struct 結(jié)構(gòu)。所以 current->state = TASK_INTERRUPTIBLE 會(huì)設(shè)定在呼叫 interruptible_sleep_on() 的 process 身上。至于 SLEEP_ON_HEAD 做的事，則是將 current 的值放到 SLEEP_ON_VAR 宣告的 wait 變量里，并把 wait 放到 interruptible_sleep_on() 的參數(shù)所屬的 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 中宣告的區(qū)域變量。其 task 字段被設(shè)成呼叫 interruptible_sleep_on() 的 process。至于 waitqueue_lock 這個(gè)變量是一個(gè) spin lock。 waitqueue_lock 是用來(lái)確保同一時(shí)間只能有一個(gè) writer。但同一時(shí)間則可以有好幾個(gè) reader。也就是說 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é)過 OS 的人應(yīng)該知道 critical section 的作用是什么，如有需要，請(qǐng)自行參考 OS 參考書。在 critical section 里只做一件事，就是將 wait 這個(gè)區(qū)域變量放到 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ì)我們?cè)儆懻摗，F(xiàn)在只要知道它會(huì)傳回這個(gè) wait_queue 的開頭就可以了。所以，__add_wait_queue() 的意思就是要把 wait 放到 p 所屬的 wait_queue list 的開頭。但是，大家還記得嗎? 在上面的例子里，一開始我們是把 write_wq 設(shè)為 NULL。也就是說 *p 是 NULL。所以，當(dāng) *p 是 NULL 時(shí),

wait->next = WAIT_QUEUE_HEAD(p)

是什么意思呢?

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

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

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

在 interruptible_sleep_on() 中，當(dāng)呼叫完 SLEEP_ON_HEAD 之后，目前的 process 就已經(jīng)被放到 wait_queue 中了。接下來(lái)會(huì)直接呼叫 schedule()，這個(gè) function 是用來(lái)做 scheduling 用的。current 所指到的 process 會(huì)被放到 scheduling queue 中等待被挑出來(lái)執(zhí)行。執(zhí)行完 schedule() 之后，current 就沒辦法繼續(xù)執(zhí)行了。而當(dāng) current 以后被 wake up 時(shí)，就會(huì)從 schedule() 之后，也就是從 SLEEP_ON_TAIL 開始執(zhí)行。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 中移除掉。

現(xiàn)在，大家應(yīng)該已經(jīng)清楚了 interruptible_sleep_on() 和 sleep_on() 的做法，也應(yīng)該比較清楚 wait_queue 是如何的做到 block IO。接下來(lái)，我們繼續(xù)看 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，意思是說它會(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 的過程中，我們不需要設(shè)定 write lock，但是仍要設(shè)定 read lock，這是為了避免有人在我們讀取 wait_queue 時(shí)去寫 wait_queue list 的內(nèi)容，造成 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 依然在此設(shè)一個(gè) critical section 以方便更改 run queue。Run queue 是用來(lái)放可以執(zhí)行的 process 用的。在放入 run queue 之前，會(huì)先將 process 的 state 設(shè)為 TASK_RUNNING。

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