相信很多寫程序的人都寫過 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 的話，那程序看起來會比較漂亮，而且也比較讓人瞭解，如下所示:
接下來，我要跟各位介紹一下 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 的話，那程序看起來會比較漂亮，而且也比較讓人瞭解，如下所示:
