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處理。

最後修改日期: 7 11 月 2019

留言

撰寫回覆或留言

發佈留言必須填寫的電子郵件地址不會公開。