程式者的胡言亂語
星期四 九月 21, 2006
Busy Loop
最近我們開發的一個軟體突然會在撥放音樂時佔去大多數的CPU time，幾乎都超過百分之九十以上。這是最近一個星期中，我在不同的兩個開發專案中看到這個現象。接著我問了一下身邊的人，有一些人不知道會有這種現象，有些人知道怎麼避免，但不是很確切的知道原因。這其實滿讓我驚訝的。這意謂著很多人也許在開發應用程式的時候，不小心引發了這個問題，但卻不知道問題從何而起。
我跟這個現象相處大概有十多年的歷史了，所以很直覺的就知道答案多半出自於程式中含有所謂的「busy loop」。有些busy loop是由於busy waiting而產生的，也就是利用一個loop不斷的等候某個事件發生，例如：
while( eventFlag == false )
;
在程式的另一個地方會將eventFlag由false設為true，所以當它的狀態改變時，就會離開while loop。邏輯上正確，但在多工的系統中卻會發生效能的問題。
以round robin和priority queue為基礎的作業系統排程器，會為每個執行緒指定一個執行的時間單位（例如在Win NT裡就叫quantum），代表著該執行緒被分配到執行權後，可以執行的最長時間片段。但在這個過程中，如果執行緒結束或執行緒必須被事件的等待動作（例如做disk I/O必須等I/O動作完成）所block時，也會提前讓排程器介入，因而選出下一個要執行的執行緒。
所謂的「busy loop」就是一種在loop裡只有CPU活動，不僅不會呼叫任何會block執行的system call也不會等候任何的事件，包括做I/O動作。這麼一來，這樣子的loop就會變成CPU intensive。當我們在程式裡放了一個所謂的「busy loop」時，這busy loop如果執行時間夠長，幾乎就會讓執行緒耗完整個被分配到的執行時間。但如果是I/O-bound的程式，卻往往不會耗完整個被分配到的執行時間。這麼一來，CPU-bound的執行緒，如果沒有其他的競爭者的話，它的執行時間就會佔去大多數的CPU時間。
由於大多數的interactive的執行緒，例如處理使用者在視窗上的滑鼠及鍵盤輸入的執行緒都是I/O-bound，但這類的執行緒由於是直接面對使用者，所以反而需要比較快的反應速度。如果系統中存在一個CPU-bound的執行緒時，就會大幅的影響到此類執行緒的執行反應。為此，排程器也有可能會動態的區分出執行緒是CPU-bound的特性（看執行緒消耗執行時間的情況就可以知道）或I/O-bound的特性，動態的調低CPU-bound的執行緒的優先序。甚至像WinNT的排程器也設計了boosting的機制，在等完I/O後，會給它短暫的優先序調昇，藉以提高此類執行緒的反應速度。
即使有些作業系統的排程器設計了上述類似的機制來避免CPU-bound的執行緒「欺凌」I/O-bound的執行緒，但不論如何，CPU-bound的執行緒仍然能構成影響。尤其是busy loop更是能造成嚴重且明顯的影響。
「busy waiting」會造成busy loop（雖然busy loop不一定是由busy waiting造成），但如果適時的加上一些等候事件的動作，例如在Win32上加上Sleep(1)，便能夠將CPU釋放出來，原先的目的也不致於被影響到。例如：
while( eventFlag == false )
Sleep(1);
Posted at 05:00下午 九月 21, 2006 by Chien-Hsing Wang in programming | 迴響[2]
寫得真好，第一次讀到對 busy loop 如此詳盡的解說呢。
由...發表 Leon on 九月 22, 2006 at 10:04 上午 CST #
記得第一次接觸到 busy loop，就是 qing 介紹 mud engines 給我認識時，翻了一些 code 看到的，受益良多。
由...發表 Drake on 九月 24, 2006 at 03:14 下午 CST #