wait queue
Wednesday, October 28, 2009 by JSDN
相信很多寫程序的人都寫過 socket 的程序。當我們 open 一個 socket 之後，接著去讀取這個 socket，如果此時沒有任何資料可供讀取，那 read 就會 block 住。(這是沒有加上 O_NONBLOCK 的情形)，直到有資料可讀取才會傳回來。在 Linux kernel 裡有一個數據結構可以幫助我們做到這樣的功能。這個數據結構就是這裡要跟各位介紹的 wait queue。在 kernel 裡，wait_queue 的應用很廣，舉凡 device driver semaphore 等方面都會使用到 wait_queue 來 implement。所以，它算是 kernel 裡蠻基本的一個數據結構。
接下來，我要跟各位介紹一下 wait_queue 的用法，以及用一個例子來說明如何使用 wait_queue。最後，我會帶各位去 trace 一下 wait_queue 的原始程序代碼，看看 wait_queue 是如何做到的。
我想有件事要先提及的是 Linux 在 user space 跟在 kernel space 上的差異。我們知道 Linux 是 multi-tasking 的環境，同時可以有很多人執行很多的程序。這是從 user 的觀點來看的。如果就 kernel 的觀點來看，是沒有所謂的 multi-tasking 的。在 kernel 裡，只有 single-thread。也就是說，如果你的 kernel code 正在執行，那系統裡只有那部分在執行。不會有另一部分的 kernel code 也在運作。當然，這是指 single processor 的情況下，如果是 SMP 的話，那我就不清楚了。我想很多人都在 Windows 3.1 下寫過程序，在那種環境下寫程序，每一個程序都必須適當的將 CPU 讓給別的程序使用。如果有個程序裡面有一個
while (1);
的話，那保證系統就停在那裡了。這種的多任務叫做 non-preemptive。它多任務的特性是由各個程序相互合作而造成的。在 Linux 的 user space 下，則是所謂的 preemptive，各個 process 喜歡執行什麼就執行什麼，就算你在你的程序裡加上 while(1); 這一行也不會影響系統的運作。反正時間到了，系統自動就會將你的程序停住，讓別的程序去執行。這是在 user space 的情況下，在 kernel 這方面，就跟 Windows 3.1 程序是一樣的。在 kernel 裡，你必須適當的將 CPU 的執行權釋放出來。如果你在 kernel裡加入 while(1); 這一行。那系統就會跟 Windows 3.1 一樣。卡在那裡。當然啦，我是沒試過這樣去改 kernel，有興趣的人可以去試試看，如果有不同的結果，請記得告訴我。
假設我們在 kernel 裡產生一個 buffer，user 可以經由 read，write 等 system call 來讀取或寫資料到這個 buffer 裡。如果有一個 user 寫資料到 buffer 時，此時 buffer 已經滿了。那請問你要如何去處理這種情形呢 ? 第一種，傳給 user 一個錯誤訊息，說 buffer 已經滿了，不能再寫入。第二種，將 user 的要求 block 住，等有人將 buffer 內容讀走，留出空位時，再讓 user 寫入資料。但問題來了，你要怎麼將 user 的要求 block 住。難道你要用
while ( is_full );
write_to_buffer;
這樣的程序代碼嗎? 想想看，如果你這樣做會發生什麼事? 第一，kernel會一直在這個 while 裡執行。第二個，如果 kernel 一直在這個 while 裡執行，表示它沒有辦法去 maintain系統的運作。那此時系統就相當於當掉了。在這裡 is_full 是一個變量，當然，你可以讓 is_full 是一個 function，在這個 function裡會去做別的事讓 kernel 可以運作，那系統就不會當。這是一個方式。但是，如果我們使用 wait_queue 的話，那程序看起來會比較漂亮，而且也比較讓人瞭解，如下所示:
struct wait_queue *wq = NULL; /* global variable */
while ( is_full ) {
interruptible_sleep_on( &wq );
}
write_to_buffer();
interruptible_sleep_on( &wq ) 是用來將目前的 process，也就是要求寫資料到 buffer 的 process放到 wq 這個 wait_queue 裡。在 interruptible_sleep_on 裡，則是最後會呼叫 schedule() 來做 schedule 的動作，也就是去找另一個 process 來執行以維持系統的運作。當執行完 interruptible_sleep_on 之後，要求 write 的 process 就會被 block 住。那什麼時候會恢復執行呢 ? 這個 process 之所以會被 block 住是因為 buffer 的空間滿了，無法寫入。但是如果有人將 buffer 的資料讀取掉，則 buffer 就有空間可以讓人寫入。所以，有關於叫醒 process 的動作應該是在 read buffer 這方面的程序代碼做的。
extern struct wait_queue *wq;
if ( !is_empty ) {
read_from_buffer();
wake_up_interruptible( &wq );
}
....
以上的程序代碼應該要放在 read buffer 這部分的程序代碼裡，當 buffer 有多餘的空間時,我們就呼叫 wake_up_interruptible( &wq ) 來將掛在 wq 上的所有 process 叫醒。請記得，我是說將 wq 上的所有 process 叫醒，所以，如果如果有10個 process 掛在 wq 上的話，那這 10 個都會被叫醒。之後，至於誰先執行。則是要看 schedule 是怎麼做的。就是因為這 10 個都會被叫醒。如果 A 先執行，而且萬一很不湊巧的，A 又把 buffer 寫滿了，那其它 9 個 process 要怎麼辦呢? 所以在 write buffer 的部分，需要用一個 while 來檢查 buffer 目前是否滿了.如果是的話，那就繼續掛在 wq 上面.
上面所談的就是 wait_queue 的用法。很簡單不是嗎? 接下來，我會再介紹一下 wait_queue 提供那些 function 讓我們使用。讓我再重申一次。wait_queue 應設為 global variable，比方叫 wq，只要任何的 process 想將自己掛在上面，就可以直接叫呼叫 sleep_on 等 function。要將 wq 上的 process 叫醒。只要呼叫 wake_up 等 function 就可以了.
就我所知，wait_queue 提供4個 function 可以使用，兩個是用來將 process 加到 wait_queue 的:
sleep_on( struct wait_queue **wq );
interruptible_sleep_on( struct wait_queue **wq );
另外兩個則是將process從wait_queue上叫醒的。
wake_up( struct wait_queue **wq );
wake_up_interruptible( struct wait_queue **wq );
我現在來解釋一下為什麼會有兩組。有 interruptible 的那一組是這樣子的。當我們去 read 一個沒有資料可供讀取的 socket 時，process 會 block 在那裡。如果我們此時按下 Ctrl+C，那 read() 就會傳回 EINTR。像這種的 block IO 就是使用 interruptible_sleep_on() 做到的。也就是說，如果你是用 interruptible_sleep_on() 來將 process 放到 wait_queue 時，如果有人送一個 signal 給這個 process，那它就會自動從 wait_queue 中醒來。但是如果你是用 sleep_on() 把 process 放到 wq 中的話，那不管你送任何的 signal 給它，它還是不會理你的。除非你是使用 wake_up() 將它叫醒。sleep 有兩組。wake_up 也有兩組。wake_up_interruptible() 會將 wq 中使用 interruptible_sleep_on() 的 process 叫醒。至於 wake_up() 則是會將 wq 中所有的 process 叫醒。包括使用 interruptible_sleep_on() 的 process。
在使用 wait_queue 之前有一點需要特別的小心，呼叫 interruptible_sleep_on() 以及 sleep_on() 的 function 必須要是 reentrant。簡單的說，reentrant 的意思是說此 function不會改變任何的 global variable，或者是不會 depend on 任何的 global variable，或者是在呼叫 interruptible_sleep_on() 或 sleep_on() 之後不會 depend on 任何的 global variable。因為當此 function 呼叫 sleep_on() 時，目前的 process 會被暫停執行。可能另一個 process 又會呼叫此 function。若之前的 process 將某些 information 存在 global variable，等它恢復執行時要使用，結果第二行程進來了，又把這個 global variable 改掉了。等第一個 process 恢復執行時，放在 global variable 中的 information 都變了。產生的結果恐怕就不是我們所能想像了。其實，從 process 執行指令到此 function 中所呼叫的 function 都應該是要 reentrant 的。不然，很有可能還是會有上述的情形發生.
由於 wait_queue 是 kernel 所提供的，所以，這個例子必須要放到 kernel 裡去執行。我使用的這個例子是一個簡單的 driver。它會 maintain 一個 buffer，大小是 8192 bytes。提供 read跟 write 的功能。當 buffer 中沒有資料時，read() 會馬上傳回，也就是不做 block IO。而當 write buffer 時，如果呼叫 write() 時，空間已滿或寫入的資料比 buffer 大時，就會被 block 住，直到有人將 buffer 裡的資料讀出來為止。在 write buffer 的程序代碼中，我們使用 wait_queue 來做到 block IO 的功能。在這裡，我會將此 driver 寫成 module，方便加載 kernel。
第一步，這個 driver 是一個簡單的 character device driver。所以，我們先在 /dev 下產生一個 character device。major number 我們找一個比較沒人使用的，像是 54，minor number 就用 0。接著下一個命令.
mknod /dev/buf c 54 0
mknod 是用來產生 special file 的 command。/dev/buf 表示要產生叫 buf 的檔案，位於 /dev 下。 c 表示它是一個 character device。54 為其 major number，0 則是它的 minor number。有關 character device driver 的寫法。有機會我再跟各位介紹，由於這次是講 wait_queue，所以，就不再多提 driver 方面的東西.
第二步，我們要寫一個 module，底下是這個 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 54\n" );
return result;
}
return 0;
}
static void buf_clean()
{
if ( unregister_chrdev( 54，"buf" ) ) {
printk( "<5>buf: unregister_chrdev error\n" );
}
}
int init_module( void )
{
return buf_init();
}
void cleanup_module( void )
{
buf_clean();
}
有關 module 的寫法，請各位自行參考其它的文件，最重要的是要有 init_module()和 cleanup_module() 這兩個 function。我在這兩個 function 裡分別做 initialize 和 finalize 的動作。現在分別解釋一下。在 init_module() 裡，只有呼叫 buf_init() 而己。其實，也可以將 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 54\n" );
return result;
}
return 0;
init_buf() 做的事就是去註冊一個 character device driver。在註冊一個 character device driver 之前，必須要先準備一個型別為 file_operations 結構的變量，file_operations 裡包含了一些 function pointer。driver 的作者必須自己寫這些 function。並將 function address 放到這個結構裡。如此一來，當 user 去讀取這個 device 時，kernel 才有辦法去呼叫對應這個 driver 的 function。其實，簡要來講。character device driver 就是這麼一個 file_operations 結構的變量。file_operations 定義在這個檔案裡。它的 prototype 在 kernel 2.2.1 與以前的版本有些微的差異，這點是需要注意的地方。
register_chrdev() 看名字就大概知道是要註冊 character device driver。第一個參數是此 device 的 major number。第二個是它的名字。名字你可以隨便取。第三個的參數就是一個 file_operations 變量的地址。init_module() 必須要傳回 0，module 才會被加載。
在 cleanup_module() 的部分，我們也是只呼叫 buf_clean() 而已。它做的事是 unregister 的動作。
if ( unregister_chrdev( 54，"buf" ) ) {
printk( "<5>buf: unregister_chrdev error\n" );
}
也就是將原本記錄在 device driver table 上的資料洗掉。第一個參數是 major number。第二個則是此 driver 的名稱，這個名字必須要跟 register_chrdev() 中所給的名字一樣才行。
現在我們來看看此 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 對這個 device 呼叫 open() 的時候，buf_open() 會在最後被 kernel 呼叫。相同的，當呼叫 close()，read()，和 write() 時，buf_release()，buf_read()，和 buf_write() 也都會分別被呼叫。首先，我們先來看看 buf_open()。
static int buf_open( struct inode *inode，struct file *filp )
MOD_INC_USE_COUNT;
return 0;
}
buf_open() 做的事很簡單。就是將此 module 的 use count 加一。這是為了避免當此 module 正被使用時不會被從 kernel 移除掉。相對應的，在 buf_release() 中，我們應該要將 use count 減一。就像開啟檔案一樣。有 open()，就應該要有對應的 close() 才行。如果 module 的 use count 在不為 0 的話，那此 module 就無法從 kernel 中移除了。
static int buf_release( struct inode *inode，struct file *filp )
{
MOD_DEC_USE_COUNT;
return 0;
}
接下來，我們要看一下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 要求讀取或寫入的字符數目而已。在此，我要說明一下這些參數的意義。filp 是一個 file 結構的 pointer。也就是指我們在 /dev 下所產生的 buf 檔案的 file 結構。當我們呼叫 read() 或 write() 時，必須要給一個 buffer 以及要讀寫的長度。Buf 指的就是這個 buffer，而 count 指的就是長度。至於 ppos 是表示目前這個檔案的 offset 在那裡。這個值對普通檔案是有用的。也就是跟 lseek() 有關係。由於在這裡是一個 drvice。所以 ppos 在此並不會用到。有一點要小心的是，上面參數 buf 是一個地址，而且還是一個 user space 的地址，當 kernel 呼叫 buf_read() 時，程序在位於 kernel space。所以你不能直接讀寫資料到 buf 裡。必須先切換 FS 這個 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)
加入上面這個 Makefile，打入 make 之後，就會產生一個 buf.o 的檔案。利用 insmod 將 buf.o 載到 kernel 裡。相信大家應該都用過 /dev/zero 這個 device。去讀取這個 device，只會得到空的內容。寫資料到這個 device 裡也只會石沈大海。現在你可以去比較 buf 和 zero 這兩個 device。兩者的行為應該很類似才是。
第三步，我們在第二步中 implement 一個像 zero 的 device driver。我們現在要經由修改它來使用 wait_queue。首先，我們先加入一個 global variable，write_wq，並把它設為 NULL。
struct wait_queue *write_wq = NULL;
然後，在 buf_read() 裡，我們要改寫成這個樣子。
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 這個 register 來當作 kernel space 和 user space 的切換。所以，如果你想手動的話，可以這樣做:
mm_segment_t fs;
fs = get_fs();
set_fs( USER_DS );
write_data_to_buf( buf );
set_fs( fs );
也就是先切換到 user space，再寫資料到 buf 裡。之後記得要切換回來 kernel space。這種自己動手的方法比較麻煩，所以 Linux 提供了幾個 function，可以讓我們直接在不同的 space 之間做資料的搬移。誠如各位所見，copy_to_user() 就是其中一個。
copy_to_user( to，from，n );
copy_from_user( to，from，n );
顧名思義，copy_to_user() 就是將資料 copy 到 user space 的 buffer 裡，也就是從 to 寫到 from，n 為要 copy 的 byte 數。相同的，copy_from_user() 就是將資料從 user space 的 from copy 到位於 kernel 的 to 裡，長度是 n bytes。在以前的 kernel 裡，這兩個 function 的前身是 memcpy_tofs() 和 memcpy_fromfs()，不知道為什麼到了 kernel 2.2.1之後，名字就被改掉了。至於它們的程序代碼有沒有更改就不太清楚了。至於到那一版才改的。我沒有仔細去查，只知道在 2.0.36 時還沒改，到了 2.2.1 就改了。這兩個 function 是 macro，都定義在裡。要使用前記得先 include 進來。
相信 buf_read() 的程序代碼應當不難瞭解才對。不知道各位有沒有看到，在buf_read() 的後面有一行的程序，就是
wake_up_interruptible( &write_wq );
write_wq 是我們用來放那些想要寫資料到 buffer，但 buffer 已滿的 process。這一行的程序會將掛在此 queue 上的 process 叫醒。當 queue 是空的時，也就是當 write_wq 為 NULL 時，wake_up_interruptible() 並不會造成任何的錯誤。接下來，我們來看看更改後的 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 的動作放在 buf_write() 裡。當 buffer 已滿時，就直接將 process 丟到 write_wq 裡.
while ( ( wp == rp ) && flag ) {
interruptible_sleep_on( &write_wq );
}
好了。現在程序已經做了一些修改。再重新 make 一次，利用 insmod 將 buf.o 載到 kernel 裡就行了。接著，我們就來試驗一下是不是真正做到 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
執行到這裡，應該會被 block 住。現在，我們再開一個 shell 出來.
# cd /dev
# cat buf
..。( contents of WWW-HOWTO ) ..。skip ...
此時，WWW-HOWTO 的內容就會出現了。而且之前 block 住的 shell 也已經回來了。最後，試驗結束，可以下
# rmmod buf
將 buf 這個 module 從 kernel 中移除。以上跟各位介紹的就是 wait_queue 的使用。希望能對各位有所助益。
我想對某些人來講，會使用一個東西就夠了。然而對某些人來講，可能也很希望知道這項東西是如何做出來的。至少我就是這種人。在下面，我將為各位介紹 wait_queue 的 implementation。如果對其 implementation 沒興趣，以下這一段就可以略過不用看了。
wait_queue 是定義在 裡，我們可以先看看它的數據結構是怎麼樣:
struct wait_queue {
struct task_struct * task;
struct wait_queue * next;
};
很簡單是吧。這個結構裡面只有二個字段，一個是 task_struct 的 pointer，另一個則是 wait_queue 的 pointer。很明顯的，我們可以看出 wait_queue 其實就是一個 linked list,而且它還是一個 circular linked list。 其中 task_struct 就是用來指呼叫 sleep_on 等 function的 process。在 Linux 裡，每一個 process 是由一個 task_struct 來描敘。task_struct 是一個很大的的結構，在此我們不會討論。Linux 裡有一個 global variable，叫 current，它會指到目前正在執行的 process 的 task_struct 結構。這也就是為什麼當 process 呼叫 system call，切換到 kernel 時，kernel 會知道是那個 process 呼叫的。
好，我們現在來看看 interruptible_sleep_on() 和 sleep_on() 是如何做的。這兩個 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
}
各位有沒有發現這兩個 function 很類似。是的，它們唯一的差別就在於
current->state = ...
這一行而已。之前，我們有說過，interruptible_sleep_on() 可以被 signal 中斷，所以，其 current->state 被設為 TASK_INTERRUPTIBLE。而 sleep_on() 沒辦法被中斷，所以 current->state 設為 TASK_UNINTERRUPTIBLE。接下來，我們只看 interruptible_sleep_on() 就好了。畢竟它們兩的差異只在那一行而已。
在 sched.c 裡，SLEEP_ON_VAR 是一個 macro，其實它只是定義兩個區域變量出來而已。
#defineSLEEP_ON_VAR\
unsigned long flags;\
struct wait_queue wait;
剛才我也說過，current 這個變量是指到目前正在執行的 process 的 task_struct 結構。所以 current->state = TASK_INTERRUPTIBLE 會設定在呼叫 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 這個變量是一個 spin lock。 waitqueue_lock 是用來確保同一時間只能有一個 writer。但同一時間則可以有好幾個 reader。也就是說 waitqueue_lock 是用來保證 critical section 的 mutual exclusive ACCESS。
unsigned long flags;
write_lock_irqsave(&waitqueue_lock，flags);
...critical section ...
write_unlock(&waitqueue_lock)
學過 OS 的人應該知道 critical section 的作用是什麼，如有需要，請自行參考 OS 參考書。在 critical section 裡只做一件事，就是將 wait 這個區域變量放到 p 這個 wait_queue list 中。 p 是 user 在呼叫 interruptible_sleep_on() 時傳進來的，它的型別是 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() 是一個inline function，定義在 中。WAIT_QUEUE_HEAD()是個很有趣的 macro，待會我們再討論。現在只要知道它會傳回這個 wait_queue 的開頭就可以了。所以，__add_wait_queue() 的意思就是要把 wait 放到 p 所屬的 wait_queue list 的開頭。但是，大家還記得嗎? 在上面的例子裡，一開始我們是把 write_wq 設為 NULL。也就是說 *p 是 NULL。所以，當 *p 是 NULL 時,
wait->next = WAIT_QUEUE_HEAD(p)
是什麼意思呢?
所以，現在，我們來看一下 WAIT_QUEUE_HEAD() 是怎麼樣的一個 macro，它是定義在裡。
#define WAIT_QUEUE_HEAD(x) ((struct wait_queue *)((x)-1))
x 型別是 struct wait_queue **，因為是一個 pointer，所以大小是 4 byte。因此，若 x 為 100 的話，那 ((x)-1) 就變成 96。如下圖所示。 WAIT_QUEUE_HEAD(x) 其實會傳回 96，而且將其轉型為 struct wait_queue*，各位可以看看。原本的 wait_queue* 只配製在 100-104 之間。現在 WAIT_QUEUE_HEAD(x) 卻直接傳回96，但是 96-100 這塊位置根本沒有被我們配置起來。更妙的事。由於 x 是一個 wait_queue list 的開頭，我們始終不會用到 96-100 這塊，我們只會直接使用到 100-104 這塊內存。這也算是 wait_queue 一項比較奇怪的 implementation 方式吧。下面有三張圖，第一張表示我們宣告了一個 wait_queue* 的變量，地址在 100。另外還有一個 wait_queue 的變量，名叫 wait。第二張圖是我們呼叫 interruptible_sleep_on() 之後得到的結果。第三張則是我們又宣告一個 wait_queue，名叫 ano_wait，將 ano_wait 放到 wait_queue list 後的結果就第三張圖所顯示的。http://linuxfab.cx/Columns/10/wqq.GIF
在 interruptible_sleep_on() 中，當呼叫完 SLEEP_ON_HEAD 之後，目前的 process 就已經被放到 wait_queue 中了。接下來會直接呼叫 schedule()，這個 function 是用來做 scheduling 用的。current 所指到的 process 會被放到 scheduling queue 中等待被挑出來執行。執行完 schedule() 之後，current 就沒辦法繼續執行了。而當 current 以後被 wake up 時，就會從 schedule() 之後，也就是從 SLEEP_ON_TAIL 開始執行。SLEEP_ON_TAIL 做的事剛好跟 SLEEP_ON_HEAD 相反，它會將此 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 包住一個 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() 是一個 inline function，也是同樣定義在 裡。是用來將 wait 從 p 這個 wait_queue list 中移除掉。
現在，大家應該已經清楚了 interruptible_sleep_on() 和 sleep_on() 的做法，也應該比較清楚 wait_queue 是如何的做到 block IO。接下來，我們繼續看 wake_up_interruptible() 和 wake_up() 是如何 implement 的。wake_up_interruptible() 和 wake_up() 其實是兩個 macro，都定義在 裡。
#define wake_up(x) __wake_up((x),TASK_UNINTERRUPTIBLE | \
TASK_INTERRUPTIBLE)
#define wake_up_interruptible(x) __wake_up((x),TASK_INTERRUPTIBLE)
從這裡可以看出，兩個 macro 幾乎是一樣的，差別只在於傳給 __wake_up() 中的一個 flag 有所差異而已。其實，wake_up() 傳給 __wake_up() 的是 TASK_UNINTERRUPTIBLE|TASK_INTERRUPTIBLE，意思是說它會將 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 的過程中，我們不需要設定 write lock，但是仍要設定 read lock，這是為了避免有人在我們讀取 wait_queue 時去寫 wait_queue list 的內容，造成 inconsistent。在這段程序代碼中，是去 transverse 整個 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 也是一個 spin lock，kernel 依然在此設一個 critical section 以方便更改 run queue。Run queue 是用來放可以執行的 process 用的。在放入 run queue 之前，會先將 process 的 state 設為 TASK_RUNNING。
wait_queue 其實是一個蠻好用的東西。相信只要各位有機會去修改 kernel 的話，都應該有機會用到它才對。希望對大家有點幫助.
接下來，我要跟各位介紹一下 wait_queue 的用法，以及用一個例子來說明如何使用 wait_queue。最後，我會帶各位去 trace 一下 wait_queue 的原始程序代碼，看看 wait_queue 是如何做到的。
我想有件事要先提及的是 Linux 在 user space 跟在 kernel space 上的差異。我們知道 Linux 是 multi-tasking 的環境，同時可以有很多人執行很多的程序。這是從 user 的觀點來看的。如果就 kernel 的觀點來看，是沒有所謂的 multi-tasking 的。在 kernel 裡，只有 single-thread。也就是說，如果你的 kernel code 正在執行，那系統裡只有那部分在執行。不會有另一部分的 kernel code 也在運作。當然，這是指 single processor 的情況下，如果是 SMP 的話，那我就不清楚了。我想很多人都在 Windows 3.1 下寫過程序，在那種環境下寫程序，每一個程序都必須適當的將 CPU 讓給別的程序使用。如果有個程序裡面有一個
while (1);
的話，那保證系統就停在那裡了。這種的多任務叫做 non-preemptive。它多任務的特性是由各個程序相互合作而造成的。在 Linux 的 user space 下，則是所謂的 preemptive，各個 process 喜歡執行什麼就執行什麼，就算你在你的程序裡加上 while(1); 這一行也不會影響系統的運作。反正時間到了，系統自動就會將你的程序停住，讓別的程序去執行。這是在 user space 的情況下，在 kernel 這方面，就跟 Windows 3.1 程序是一樣的。在 kernel 裡，你必須適當的將 CPU 的執行權釋放出來。如果你在 kernel裡加入 while(1); 這一行。那系統就會跟 Windows 3.1 一樣。卡在那裡。當然啦，我是沒試過這樣去改 kernel，有興趣的人可以去試試看，如果有不同的結果，請記得告訴我。
假設我們在 kernel 裡產生一個 buffer，user 可以經由 read，write 等 system call 來讀取或寫資料到這個 buffer 裡。如果有一個 user 寫資料到 buffer 時，此時 buffer 已經滿了。那請問你要如何去處理這種情形呢 ? 第一種，傳給 user 一個錯誤訊息，說 buffer 已經滿了，不能再寫入。第二種，將 user 的要求 block 住，等有人將 buffer 內容讀走，留出空位時，再讓 user 寫入資料。但問題來了，你要怎麼將 user 的要求 block 住。難道你要用
while ( is_full );
write_to_buffer;
這樣的程序代碼嗎? 想想看，如果你這樣做會發生什麼事? 第一，kernel會一直在這個 while 裡執行。第二個，如果 kernel 一直在這個 while 裡執行，表示它沒有辦法去 maintain系統的運作。那此時系統就相當於當掉了。在這裡 is_full 是一個變量，當然，你可以讓 is_full 是一個 function，在這個 function裡會去做別的事讓 kernel 可以運作，那系統就不會當。這是一個方式。但是，如果我們使用 wait_queue 的話，那程序看起來會比較漂亮，而且也比較讓人瞭解，如下所示:
struct wait_queue *wq = NULL; /* global variable */
while ( is_full ) {
interruptible_sleep_on( &wq );
}
write_to_buffer();
interruptible_sleep_on( &wq ) 是用來將目前的 process，也就是要求寫資料到 buffer 的 process放到 wq 這個 wait_queue 裡。在 interruptible_sleep_on 裡，則是最後會呼叫 schedule() 來做 schedule 的動作，也就是去找另一個 process 來執行以維持系統的運作。當執行完 interruptible_sleep_on 之後，要求 write 的 process 就會被 block 住。那什麼時候會恢復執行呢 ? 這個 process 之所以會被 block 住是因為 buffer 的空間滿了，無法寫入。但是如果有人將 buffer 的資料讀取掉，則 buffer 就有空間可以讓人寫入。所以，有關於叫醒 process 的動作應該是在 read buffer 這方面的程序代碼做的。
extern struct wait_queue *wq;
if ( !is_empty ) {
read_from_buffer();
wake_up_interruptible( &wq );
}
....
以上的程序代碼應該要放在 read buffer 這部分的程序代碼裡，當 buffer 有多餘的空間時,我們就呼叫 wake_up_interruptible( &wq ) 來將掛在 wq 上的所有 process 叫醒。請記得，我是說將 wq 上的所有 process 叫醒，所以，如果如果有10個 process 掛在 wq 上的話，那這 10 個都會被叫醒。之後，至於誰先執行。則是要看 schedule 是怎麼做的。就是因為這 10 個都會被叫醒。如果 A 先執行，而且萬一很不湊巧的，A 又把 buffer 寫滿了，那其它 9 個 process 要怎麼辦呢? 所以在 write buffer 的部分，需要用一個 while 來檢查 buffer 目前是否滿了.如果是的話，那就繼續掛在 wq 上面.
上面所談的就是 wait_queue 的用法。很簡單不是嗎? 接下來，我會再介紹一下 wait_queue 提供那些 function 讓我們使用。讓我再重申一次。wait_queue 應設為 global variable，比方叫 wq，只要任何的 process 想將自己掛在上面，就可以直接叫呼叫 sleep_on 等 function。要將 wq 上的 process 叫醒。只要呼叫 wake_up 等 function 就可以了.
就我所知，wait_queue 提供4個 function 可以使用，兩個是用來將 process 加到 wait_queue 的:
sleep_on( struct wait_queue **wq );
interruptible_sleep_on( struct wait_queue **wq );
另外兩個則是將process從wait_queue上叫醒的。
wake_up( struct wait_queue **wq );
wake_up_interruptible( struct wait_queue **wq );
我現在來解釋一下為什麼會有兩組。有 interruptible 的那一組是這樣子的。當我們去 read 一個沒有資料可供讀取的 socket 時，process 會 block 在那裡。如果我們此時按下 Ctrl+C，那 read() 就會傳回 EINTR。像這種的 block IO 就是使用 interruptible_sleep_on() 做到的。也就是說，如果你是用 interruptible_sleep_on() 來將 process 放到 wait_queue 時，如果有人送一個 signal 給這個 process，那它就會自動從 wait_queue 中醒來。但是如果你是用 sleep_on() 把 process 放到 wq 中的話，那不管你送任何的 signal 給它，它還是不會理你的。除非你是使用 wake_up() 將它叫醒。sleep 有兩組。wake_up 也有兩組。wake_up_interruptible() 會將 wq 中使用 interruptible_sleep_on() 的 process 叫醒。至於 wake_up() 則是會將 wq 中所有的 process 叫醒。包括使用 interruptible_sleep_on() 的 process。
在使用 wait_queue 之前有一點需要特別的小心，呼叫 interruptible_sleep_on() 以及 sleep_on() 的 function 必須要是 reentrant。簡單的說，reentrant 的意思是說此 function不會改變任何的 global variable，或者是不會 depend on 任何的 global variable，或者是在呼叫 interruptible_sleep_on() 或 sleep_on() 之後不會 depend on 任何的 global variable。因為當此 function 呼叫 sleep_on() 時，目前的 process 會被暫停執行。可能另一個 process 又會呼叫此 function。若之前的 process 將某些 information 存在 global variable，等它恢復執行時要使用，結果第二行程進來了，又把這個 global variable 改掉了。等第一個 process 恢復執行時，放在 global variable 中的 information 都變了。產生的結果恐怕就不是我們所能想像了。其實，從 process 執行指令到此 function 中所呼叫的 function 都應該是要 reentrant 的。不然，很有可能還是會有上述的情形發生.
由於 wait_queue 是 kernel 所提供的，所以，這個例子必須要放到 kernel 裡去執行。我使用的這個例子是一個簡單的 driver。它會 maintain 一個 buffer，大小是 8192 bytes。提供 read跟 write 的功能。當 buffer 中沒有資料時，read() 會馬上傳回，也就是不做 block IO。而當 write buffer 時，如果呼叫 write() 時，空間已滿或寫入的資料比 buffer 大時，就會被 block 住，直到有人將 buffer 裡的資料讀出來為止。在 write buffer 的程序代碼中，我們使用 wait_queue 來做到 block IO 的功能。在這裡，我會將此 driver 寫成 module，方便加載 kernel。
第一步，這個 driver 是一個簡單的 character device driver。所以，我們先在 /dev 下產生一個 character device。major number 我們找一個比較沒人使用的，像是 54，minor number 就用 0。接著下一個命令.
mknod /dev/buf c 54 0
mknod 是用來產生 special file 的 command。/dev/buf 表示要產生叫 buf 的檔案，位於 /dev 下。 c 表示它是一個 character device。54 為其 major number，0 則是它的 minor number。有關 character device driver 的寫法。有機會我再跟各位介紹，由於這次是講 wait_queue，所以，就不再多提 driver 方面的東西.
第二步，我們要寫一個 module，底下是這個 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 54\n" );
return result;
}
return 0;
}
static void buf_clean()
{
if ( unregister_chrdev( 54，"buf" ) ) {
printk( "<5>buf: unregister_chrdev error\n" );
}
}
int init_module( void )
{
return buf_init();
}
void cleanup_module( void )
{
buf_clean();
}
有關 module 的寫法，請各位自行參考其它的文件，最重要的是要有 init_module()和 cleanup_module() 這兩個 function。我在這兩個 function 裡分別做 initialize 和 finalize 的動作。現在分別解釋一下。在 init_module() 裡，只有呼叫 buf_init() 而己。其實，也可以將 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 54\n" );
return result;
}
return 0;
init_buf() 做的事就是去註冊一個 character device driver。在註冊一個 character device driver 之前，必須要先準備一個型別為 file_operations 結構的變量，file_operations 裡包含了一些 function pointer。driver 的作者必須自己寫這些 function。並將 function address 放到這個結構裡。如此一來，當 user 去讀取這個 device 時，kernel 才有辦法去呼叫對應這個 driver 的 function。其實，簡要來講。character device driver 就是這麼一個 file_operations 結構的變量。file_operations 定義在這個檔案裡。它的 prototype 在 kernel 2.2.1 與以前的版本有些微的差異，這點是需要注意的地方。
register_chrdev() 看名字就大概知道是要註冊 character device driver。第一個參數是此 device 的 major number。第二個是它的名字。名字你可以隨便取。第三個的參數就是一個 file_operations 變量的地址。init_module() 必須要傳回 0，module 才會被加載。
在 cleanup_module() 的部分，我們也是只呼叫 buf_clean() 而已。它做的事是 unregister 的動作。
if ( unregister_chrdev( 54，"buf" ) ) {
printk( "<5>buf: unregister_chrdev error\n" );
}
也就是將原本記錄在 device driver table 上的資料洗掉。第一個參數是 major number。第二個則是此 driver 的名稱，這個名字必須要跟 register_chrdev() 中所給的名字一樣才行。
現在我們來看看此 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 對這個 device 呼叫 open() 的時候，buf_open() 會在最後被 kernel 呼叫。相同的，當呼叫 close()，read()，和 write() 時，buf_release()，buf_read()，和 buf_write() 也都會分別被呼叫。首先，我們先來看看 buf_open()。
static int buf_open( struct inode *inode，struct file *filp )
MOD_INC_USE_COUNT;
return 0;
}
buf_open() 做的事很簡單。就是將此 module 的 use count 加一。這是為了避免當此 module 正被使用時不會被從 kernel 移除掉。相對應的，在 buf_release() 中，我們應該要將 use count 減一。就像開啟檔案一樣。有 open()，就應該要有對應的 close() 才行。如果 module 的 use count 在不為 0 的話，那此 module 就無法從 kernel 中移除了。
static int buf_release( struct inode *inode，struct file *filp )
{
MOD_DEC_USE_COUNT;
return 0;
}
接下來，我們要看一下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 要求讀取或寫入的字符數目而已。在此，我要說明一下這些參數的意義。filp 是一個 file 結構的 pointer。也就是指我們在 /dev 下所產生的 buf 檔案的 file 結構。當我們呼叫 read() 或 write() 時，必須要給一個 buffer 以及要讀寫的長度。Buf 指的就是這個 buffer，而 count 指的就是長度。至於 ppos 是表示目前這個檔案的 offset 在那裡。這個值對普通檔案是有用的。也就是跟 lseek() 有關係。由於在這裡是一個 drvice。所以 ppos 在此並不會用到。有一點要小心的是，上面參數 buf 是一個地址，而且還是一個 user space 的地址，當 kernel 呼叫 buf_read() 時，程序在位於 kernel space。所以你不能直接讀寫資料到 buf 裡。必須先切換 FS 這個 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)
加入上面這個 Makefile，打入 make 之後，就會產生一個 buf.o 的檔案。利用 insmod 將 buf.o 載到 kernel 裡。相信大家應該都用過 /dev/zero 這個 device。去讀取這個 device，只會得到空的內容。寫資料到這個 device 裡也只會石沈大海。現在你可以去比較 buf 和 zero 這兩個 device。兩者的行為應該很類似才是。
第三步，我們在第二步中 implement 一個像 zero 的 device driver。我們現在要經由修改它來使用 wait_queue。首先，我們先加入一個 global variable，write_wq，並把它設為 NULL。
struct wait_queue *write_wq = NULL;
然後，在 buf_read() 裡，我們要改寫成這個樣子。
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 這個 register 來當作 kernel space 和 user space 的切換。所以，如果你想手動的話，可以這樣做:
mm_segment_t fs;
fs = get_fs();
set_fs( USER_DS );
write_data_to_buf( buf );
set_fs( fs );
也就是先切換到 user space，再寫資料到 buf 裡。之後記得要切換回來 kernel space。這種自己動手的方法比較麻煩，所以 Linux 提供了幾個 function，可以讓我們直接在不同的 space 之間做資料的搬移。誠如各位所見，copy_to_user() 就是其中一個。
copy_to_user( to，from，n );
copy_from_user( to，from，n );
顧名思義，copy_to_user() 就是將資料 copy 到 user space 的 buffer 裡，也就是從 to 寫到 from，n 為要 copy 的 byte 數。相同的，copy_from_user() 就是將資料從 user space 的 from copy 到位於 kernel 的 to 裡，長度是 n bytes。在以前的 kernel 裡，這兩個 function 的前身是 memcpy_tofs() 和 memcpy_fromfs()，不知道為什麼到了 kernel 2.2.1之後，名字就被改掉了。至於它們的程序代碼有沒有更改就不太清楚了。至於到那一版才改的。我沒有仔細去查，只知道在 2.0.36 時還沒改，到了 2.2.1 就改了。這兩個 function 是 macro，都定義在裡。要使用前記得先 include 進來。
相信 buf_read() 的程序代碼應當不難瞭解才對。不知道各位有沒有看到，在buf_read() 的後面有一行的程序，就是
wake_up_interruptible( &write_wq );
write_wq 是我們用來放那些想要寫資料到 buffer，但 buffer 已滿的 process。這一行的程序會將掛在此 queue 上的 process 叫醒。當 queue 是空的時，也就是當 write_wq 為 NULL 時，wake_up_interruptible() 並不會造成任何的錯誤。接下來，我們來看看更改後的 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 的動作放在 buf_write() 裡。當 buffer 已滿時，就直接將 process 丟到 write_wq 裡.
while ( ( wp == rp ) && flag ) {
interruptible_sleep_on( &write_wq );
}
好了。現在程序已經做了一些修改。再重新 make 一次，利用 insmod 將 buf.o 載到 kernel 裡就行了。接著，我們就來試驗一下是不是真正做到 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
執行到這裡，應該會被 block 住。現在，我們再開一個 shell 出來.
# cd /dev
# cat buf
..。( contents of WWW-HOWTO ) ..。skip ...
此時，WWW-HOWTO 的內容就會出現了。而且之前 block 住的 shell 也已經回來了。最後，試驗結束，可以下
# rmmod buf
將 buf 這個 module 從 kernel 中移除。以上跟各位介紹的就是 wait_queue 的使用。希望能對各位有所助益。
我想對某些人來講，會使用一個東西就夠了。然而對某些人來講，可能也很希望知道這項東西是如何做出來的。至少我就是這種人。在下面，我將為各位介紹 wait_queue 的 implementation。如果對其 implementation 沒興趣，以下這一段就可以略過不用看了。
wait_queue 是定義在 裡，我們可以先看看它的數據結構是怎麼樣:
struct wait_queue {
struct task_struct * task;
struct wait_queue * next;
};
很簡單是吧。這個結構裡面只有二個字段，一個是 task_struct 的 pointer，另一個則是 wait_queue 的 pointer。很明顯的，我們可以看出 wait_queue 其實就是一個 linked list,而且它還是一個 circular linked list。 其中 task_struct 就是用來指呼叫 sleep_on 等 function的 process。在 Linux 裡，每一個 process 是由一個 task_struct 來描敘。task_struct 是一個很大的的結構，在此我們不會討論。Linux 裡有一個 global variable，叫 current，它會指到目前正在執行的 process 的 task_struct 結構。這也就是為什麼當 process 呼叫 system call，切換到 kernel 時，kernel 會知道是那個 process 呼叫的。
好，我們現在來看看 interruptible_sleep_on() 和 sleep_on() 是如何做的。這兩個 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
}
各位有沒有發現這兩個 function 很類似。是的，它們唯一的差別就在於
current->state = ...
這一行而已。之前，我們有說過，interruptible_sleep_on() 可以被 signal 中斷，所以，其 current->state 被設為 TASK_INTERRUPTIBLE。而 sleep_on() 沒辦法被中斷，所以 current->state 設為 TASK_UNINTERRUPTIBLE。接下來，我們只看 interruptible_sleep_on() 就好了。畢竟它們兩的差異只在那一行而已。
在 sched.c 裡，SLEEP_ON_VAR 是一個 macro，其實它只是定義兩個區域變量出來而已。
#defineSLEEP_ON_VAR\
unsigned long flags;\
struct wait_queue wait;
剛才我也說過，current 這個變量是指到目前正在執行的 process 的 task_struct 結構。所以 current->state = TASK_INTERRUPTIBLE 會設定在呼叫 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 這個變量是一個 spin lock。 waitqueue_lock 是用來確保同一時間只能有一個 writer。但同一時間則可以有好幾個 reader。也就是說 waitqueue_lock 是用來保證 critical section 的 mutual exclusive ACCESS。
unsigned long flags;
write_lock_irqsave(&waitqueue_lock，flags);
...critical section ...
write_unlock(&waitqueue_lock)
學過 OS 的人應該知道 critical section 的作用是什麼，如有需要，請自行參考 OS 參考書。在 critical section 裡只做一件事，就是將 wait 這個區域變量放到 p 這個 wait_queue list 中。 p 是 user 在呼叫 interruptible_sleep_on() 時傳進來的，它的型別是 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() 是一個inline function，定義在 中。WAIT_QUEUE_HEAD()是個很有趣的 macro，待會我們再討論。現在只要知道它會傳回這個 wait_queue 的開頭就可以了。所以，__add_wait_queue() 的意思就是要把 wait 放到 p 所屬的 wait_queue list 的開頭。但是，大家還記得嗎? 在上面的例子裡，一開始我們是把 write_wq 設為 NULL。也就是說 *p 是 NULL。所以，當 *p 是 NULL 時,
wait->next = WAIT_QUEUE_HEAD(p)
是什麼意思呢?
所以，現在，我們來看一下 WAIT_QUEUE_HEAD() 是怎麼樣的一個 macro，它是定義在裡。
#define WAIT_QUEUE_HEAD(x) ((struct wait_queue *)((x)-1))
x 型別是 struct wait_queue **，因為是一個 pointer，所以大小是 4 byte。因此，若 x 為 100 的話，那 ((x)-1) 就變成 96。如下圖所示。 WAIT_QUEUE_HEAD(x) 其實會傳回 96，而且將其轉型為 struct wait_queue*，各位可以看看。原本的 wait_queue* 只配製在 100-104 之間。現在 WAIT_QUEUE_HEAD(x) 卻直接傳回96，但是 96-100 這塊位置根本沒有被我們配置起來。更妙的事。由於 x 是一個 wait_queue list 的開頭，我們始終不會用到 96-100 這塊，我們只會直接使用到 100-104 這塊內存。這也算是 wait_queue 一項比較奇怪的 implementation 方式吧。下面有三張圖，第一張表示我們宣告了一個 wait_queue* 的變量，地址在 100。另外還有一個 wait_queue 的變量，名叫 wait。第二張圖是我們呼叫 interruptible_sleep_on() 之後得到的結果。第三張則是我們又宣告一個 wait_queue，名叫 ano_wait，將 ano_wait 放到 wait_queue list 後的結果就第三張圖所顯示的。http://linuxfab.cx/Columns/10/wqq.GIF
在 interruptible_sleep_on() 中，當呼叫完 SLEEP_ON_HEAD 之後，目前的 process 就已經被放到 wait_queue 中了。接下來會直接呼叫 schedule()，這個 function 是用來做 scheduling 用的。current 所指到的 process 會被放到 scheduling queue 中等待被挑出來執行。執行完 schedule() 之後，current 就沒辦法繼續執行了。而當 current 以後被 wake up 時，就會從 schedule() 之後，也就是從 SLEEP_ON_TAIL 開始執行。SLEEP_ON_TAIL 做的事剛好跟 SLEEP_ON_HEAD 相反，它會將此 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 包住一個 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() 是一個 inline function，也是同樣定義在 裡。是用來將 wait 從 p 這個 wait_queue list 中移除掉。
現在，大家應該已經清楚了 interruptible_sleep_on() 和 sleep_on() 的做法，也應該比較清楚 wait_queue 是如何的做到 block IO。接下來，我們繼續看 wake_up_interruptible() 和 wake_up() 是如何 implement 的。wake_up_interruptible() 和 wake_up() 其實是兩個 macro，都定義在 裡。
#define wake_up(x) __wake_up((x),TASK_UNINTERRUPTIBLE | \
TASK_INTERRUPTIBLE)
#define wake_up_interruptible(x) __wake_up((x),TASK_INTERRUPTIBLE)
從這裡可以看出，兩個 macro 幾乎是一樣的，差別只在於傳給 __wake_up() 中的一個 flag 有所差異而已。其實，wake_up() 傳給 __wake_up() 的是 TASK_UNINTERRUPTIBLE|TASK_INTERRUPTIBLE，意思是說它會將 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 的過程中，我們不需要設定 write lock，但是仍要設定 read lock，這是為了避免有人在我們讀取 wait_queue 時去寫 wait_queue list 的內容，造成 inconsistent。在這段程序代碼中，是去 transverse 整個 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 也是一個 spin lock，kernel 依然在此設一個 critical section 以方便更改 run queue。Run queue 是用來放可以執行的 process 用的。在放入 run queue 之前，會先將 process 的 state 設為 TASK_RUNNING。
wait_queue 其實是一個蠻好用的東西。相信只要各位有機會去修改 kernel 的話，都應該有機會用到它才對。希望對大家有點幫助.
