概述#

在 Microsoft、Google 或 Amazon 的面試中，直接要求實作多執行緒演算法並不常見（除非這是該職位的核心技能）。然而，對 threads 的基本理解，尤其是 deadlock 的概念，在任何公司的面試中都可能被考察。

Java 中的執行緒（Threads in Java）#

Java 中每個執行緒由一個 java.lang.Thread 物件建立和控制。當獨立應用程式啟動時，會自動建立一個 user thread 來執行 main() 方法，稱為 main thread。

在 Java 中實作執行緒有兩種方式：

  • 實作 java.lang.Runnable 介面
  • 繼承 java.lang.Thread 類別

實作 Runnable 介面#

Runnable 介面結構極為簡單：

public interface Runnable {
    void run();
}

使用步驟：

  1. 建立一個實作 Runnable 介面的類別（定義 run() 方法）
  2. 將此類別的實例傳入 Thread 建構子，建立 Thread 物件
  3. 呼叫 Thread 物件的 start() 方法
public class RunnableThreadExample implements Runnable {
    public int count = 0;

    public void run() {
        System.out.println("RunnableThread starting.");
        try {
            while (count < 5) {
                Thread.sleep(500);
                count++;
            }
        } catch (InterruptedException exc) {
            System.out.println("RunnableThread interrupted.");
        }
        System.out.println("RunnableThread terminating.");
    }

    public static void main(String[] args) {
        RunnableThreadExample instance = new RunnableThreadExample();
        Thread thread = new Thread(instance);
        thread.start();

        /* waits until above thread counts to 5 (slowly) */
        while (instance.count != 5) {
            try {
                Thread.sleep(250);
            } catch (InterruptedException exc) {
                exc.printStackTrace();
            }
        }
    }
}

繼承 Thread 類別#

繼承 Thread 類別並覆寫 run() 方法：

public class ThreadExample extends Thread {
    int count = 0;

    public void run() {
        System.out.println("Thread starting.");
        try {
            while (count < 5) {
                Thread.sleep(500);
                System.out.println("In Thread, count is " + count);
                count++;
            }
        } catch (InterruptedException exc) {
            System.out.println("Thread interrupted.");
        }
        System.out.println("Thread terminating.");
    }
}

使用時，直接在實例上呼叫 start()（因為繼承了 Thread 類別）：

ThreadExample instance = new ThreadExample();
instance.start();

Runnable vs. Thread：如何選擇？#

建議優先使用 Runnable 介面，原因：

  • Java 不支援多重繼承。繼承 Thread 後，子類別無法再繼承其他類別；而實作 Runnable 介面的類別仍可繼承其他類別。
  • 一個類別可能只需要「可執行」的能力，沒有必要繼承整個 Thread 類別的所有負擔。

同步與鎖（Synchronization and Locks）#

同一 process 中的執行緒共享記憶體空間。這讓資料共享變得容易，但也引入了競態條件（race condition）——兩個執行緒同時修改同一資源時，可能造成不一致的結果。

Java 使用 synchronized 關鍵字和 lock 來控制對共享資源的存取。

synchronized 方法#

synchronized 可以應用於方法，限制同一時間只有一個執行緒能在同一個物件上執行此方法：

public class MyObject {
    public synchronized void foo(String name) {
        try {
            System.out.println("Thread " + name + ".foo(): starting");
            Thread.sleep(3000);
            System.out.println("Thread " + name + ".foo(): ending");
        } catch (InterruptedException exc) {
            System.out.println("Thread " + name + ": interrupted.");
        }
    }
}

關鍵在於「同一個物件」。若兩個執行緒持有不同的 MyObject 實例，它們可以同時呼叫 foo()。若持有相同實例，則一個執行緒必須等另一個完成後才能執行。

靜態方法的 synchronized 鎖定的是類別鎖（class lock），即使呼叫的是不同靜態方法，同一時間也只能有一個執行緒執行：

public class MyObject {
    public static synchronized void foo(String name) { /* ... */ }
    public static synchronized void bar(String name) { /* ... */ }
}

若 thread1 呼叫 foo，thread2 呼叫 bar，thread2 仍必須等待 thread1 完成。

synchronized 區塊#

也可以對程式碼區塊進行同步，效果與同步方法類似：

public class MyObject {
    public void foo(String name) {
        synchronized(this) {
            ...
        }
    }
}

Locks（鎖）#

對於更精細的控制，可以使用 Lock 物件。Lock 讓我們可以將資源與鎖關聯，執行緒在存取共享資源前必須先取得鎖。

public class LockedATM {
    private Lock lock;
    private int balance = 100;

    public LockedATM() {
        lock = new ReentrantLock();
    }

    public int withdraw(int value) {
        lock.lock();
        int temp = balance;
        try {
            Thread.sleep(100);
            temp = temp - value;
            Thread.sleep(100);
            balance = temp;
        } catch (InterruptedException e) { }
        lock.unlock();
        return temp;
    }

    public int deposit(int value) {
        lock.lock();
        int temp = balance;
        try {
            Thread.sleep(100);
            temp = temp + value;
            Thread.sleep(300);
            balance = temp;
        } catch (InterruptedException e) { }
        lock.unlock();
        return temp;
    }
}

使用 Lock 物件可以保護共享資源免受非預期的並發修改。上例中刻意加入 sleep 來模擬真實的時序問題，說明 lock 的必要性。

死結與死結預防（Deadlocks and Deadlock Prevention）#

死結（Deadlock） 是指：

  • 執行緒 A 正在等待執行緒 B 持有的鎖
  • 執行緒 B 正在等待執行緒 A 持有的鎖
  • 雙方都在等待對方釋放，永遠不會繼續執行

死結的四個必要條件#

死結發生需要同時滿足以下四個條件：

  1. Mutual Exclusion（互斥）：同一時間只有一個 process 可以存取某資源（或資源有限量存取）
  2. Hold and Wait（持有並等待）：已持有資源的 process 可以請求更多資源，而不釋放現有的資源
  3. No Preemption（不可搶奪）：一個 process 無法強制取走另一個 process 的資源
  4. Circular Wait（循環等待）：兩個或多個 process 形成循環鏈，每個都在等待下一個所持有的資源

死結預防#

死結預防的方法是移除上述四個條件之一：

  • 移除條件 1 很難，因為許多資源本質上就是互斥的（如印表機）
  • 移除條件 4（循環等待）是最常見的方法——為所有鎖編號，強制要求所有執行緒以相同的順序取得鎖

死結預防的條件往往很難在現實中完全滿足。大多數死結預防演算法都專注於避免循環等待這個條件。

面試題目列表#

題號題目
15.1Thread vs. Process：執行緒和 process 的差異是什麼？
15.2Context Switch：如何測量 context switch 所花費的時間？
15.3Dining Philosophers：使用執行緒和鎖模擬哲學家就餐問題，並防止死結
15.4Deadlock-Free Class：設計一個只在沒有死結可能時才提供鎖的類別
15.5Call In Order：設計機制確保三個方法按照特定順序被三個執行緒呼叫
15.6Synchronized Methods：若一個類別有一個 synchronized 方法 A 和一個普通方法 B，兩個執行緒能同時執行 A 和 B 嗎？
15.7FizzBuzz：用四個執行緒實作多執行緒版本的 FizzBuzz
Backward Databases Additional Review Problems Forward