相信很多寫程序的人都寫過 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
