【作業系統】Busy Waiting忙碌等待|使電腦空轉的忙碌迴圈

Busy Waiting 定義：

使CPU在工作，但是沒有產能，因為CPU在等待某一個特定事情發生。

以小明燒熱水的例子說明 Busy Waiting

1. 他去打開瓦斯爐，
2. 等待水滾了以後熄火
3.倒入杯子裡才算完成工作

笨方法，小明站在火爐旁邊一直盯著水有沒有滾

燒熱水(){
    開火;
    while(水還沒沸騰){
        什麼都不做。
    }
    關火;
    把熱水倒入杯子裡;
}

小明在看水的這段時間，就是 Busy Waiting。小明一直有在做事情，但是實際上一點產能都沒有。很浪費小明的時間，因此我們可以想辦法改善。

我們將水壺加上笛音，水燒開了就「嗶嗶叫」

燒熱水(){
    開火;
    wait(水壺嗶嗶叫叫); // 這個時間，小明就可以去做其他事情了，不用一直監控水壺。
    關火;
    把熱水倒入杯子裡;
}

經過改進以後，小明就可以在等待水滾的期間，去做其他事情（看書，聽音樂）。直到水壺叫了，再去關火就可以了。效率高很多！

Note:
以上是 Busy Waiting 的基本觀念。也帶出作業系統（恐龍本）的CH6. 的同步問題。基本上就是有一個工作要等待另一個工作完成以後，要怎麼確保這一件事情可以執行。

Busy Waiting 是多工處理系統會發生的 (Round robin 和 Priority queue的排班方式)。我們希望保持CPU不斷的運轉，不要花時間在等待。等待是很浪費生命的！

避免的方法

笨方法： Sleep

while( waitinigForThread1() && waitingForThread2() ) {
    Thread.sleep(1000); // Sleep for 1 second
}

笨方法： Exponential Backoff

private static final int MAX_BACKOFF=1000*60*60; // 1 hour
private static final int INITIAL_BACKOFF=100; // 100ms
int backOff=INITIAL_BACKOFF;
while( waitinigForThread1() && waitingForThread2() ) {
    Thread.sleep(backOff); // Sleep for 1 second
    backOff=backOff<<2; //bit shift to the left to multiply by 2
    if(backOff > MAX_BACKOFF) {
        backOff = MAX_BACKOFF;
    }
}

不錯的解法: Locking or Monitors (監視器)

Object lock = new Object(); // shared object to synchronize on
int doneCount = 0;
Thread thread1 = new Thread(new Runnable() {
    public void run() {
        // ...
        // do sub task 1
        // ...
        synchronized(lock) {
            doneCount++;
            notify();
        }
    }
});
Thread thread2 = new Thread(new Runnable() {
    public void run() {
        // ...
        // do sub task 2
        // ...
        synchronized(lock) {
            doneCount++;
            notify();
        }
    }
});
 
// this is the main thread again
synchronized(lock) {
    thread1.start();
    thread2.start();
 
    while(doneCount < 2) {
        wait();
    }
}

效率最高: Concurrency Libraries (並行)

ExecutorService executor = ...
Future<String> future1 = executor.submit( new Callable<String>() {
    public String call() {
        /* do work for first result here */
    }
});
Future<String> future2 = executor.submit( new Callable<String>() {
    public String call() {
        /* do work for second result here */
    }
} );
String result1 = future1.get();
String result2 = future2.get();

結論

如果要解決 Busy Waiting 的問題，最好的方法是先去看看有沒有人家寫好的程式庫，直接拿來用。如果沒有的話再利用 Monitor 解決問題，最差最差才是用Wait處理。