興大物件導向程式設計 Assignment Ch23 參考詳解

前言

Ch23 開始進入了多工處理（Multithreading, Multiprocessing）的環節，這部分其實水很深，不過還是鼓勵大家學起來，畢竟大型的程式通常都避不開多工。

如果覺得上課講義太長難以吸收也請不要勉強，上網找找中文的教學，重點是知識要先吸收，量力而為。

更新記錄

• 2024/05/25：發佈文章
• 2024/05/26：更新 Thread 的狀態定義章節、修正 A23.5 的 C 選項答案

Thread 的狀態定義（重要★★★）

Java 的 Thread 有幾種狀態：

1. 剛創建還沒啟動，這個應該很好理解
2. Runnable：在你啟動以後，thread 有可能在正常工作，也有可能在等待被 CPU 調度
3. Blocked：如果這個 Thread 正在排隊等著要取某個物件的鎖，我們會叫他 Blocked（阻塞狀態）
4. Waiting：在 Waiting 的時候，線程既沒有在工作也沒有在排隊等待某個鎖，就是單純在休息。就是一直休息，如果你調用了 wait() 而且沒有傳入參數告訴 thread 要休息多久，他就一直休息。
5. Timed Waiting：當你呼叫 wait() 並且有傳入參數告訴程式要休息多久（比如講三秒鐘），這個 thread 就會休息 3 秒鐘然後回去做他的事（有可能是 Runnable 或是跑去排隊等待鎖，變成 Blocked）

我們可以做一些操作：

1. wait()：這個操作會讓 thread 跑去休息，不傳參數的時候就是一直休息直到我們主動喚醒他
2. wait()：如果傳了參數，就是休息指定的時間後，恢復成 runnable 或是 blocked
3. interrupt()：如果一個 thread 原本是 runnable 或 blocked，那就是字面上的意思，我們中斷他，他會拋出異常，我們可以進行一些清理然後退出它
4. interrupt()：如果一個 thread 原本正在休息，進行 interrupt() 會告訴他：「起床，中斷你的休息」，他就會變成 blocked 或 runnable
5. notify()：當一個物件使用了 notify，會把正在排隊要取鎖的其中一個 thread 喚醒，那個 thread 會退出休息的狀態，然後試著取鎖
6. notifyAll()：當一個物件使用了 notifyAll，會把所有正在排隊的線程一起挖醒，然後大家會一起搶搶看鎖

Q23.5

(True or False) State whether each of the following is true or false. If false, explain why.
a) Timed waiting threads return to the runnable state only when the time interval expires.
b) With synchronized, there is no way to state the condition on which threads are waiting.
c) Using ReentrantLock with a fairness policy won’t allow starvation to occur.
d) When several threads call method lock on the same object at the same time, only one of them can obtain the lock, the other threads are placed in the waiting state for that lock.

A23.5

a) Timed waiting 的線程只有在等待的時間到達後才會恢復成 runnable 的狀態。

False：Timed waiting Threads 會在多個情況下恢復成 runnable 的狀態

• 等待的時間到達
• 接收到中斷信號
• 被通知可以繼續（Notify/NotifyAll）

b) 使用 synchronized 沒辦法明確說明 Thread 在等待的條件。

True

c) 使用帶有「公平策略」的 ReentrantLock 可以避免執行緒耗盡 (Thread Starvation)

True

d) 當多個執行緒同時調用同一個對象的 lock 方法時，只有一個執行緒能夠獲得鎖，其他執行序會進入等待狀態。

True：鎖（Lock）的存在是為了避免資源競爭的問題，舉個例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class RaceConditionExample {
    private int a = 0; // a 變數會被兩個 thread 同時存取

    public static void main(String[] args) { // main 方法，程式從這裡開始
        RaceConditionExample example = new RaceConditionExample();
        example.runTest();
    }

    public void runTest() {
        Thread thread1 = new Thread(new IncrementTask()); // 創建第一個線程
        Thread thread2 = new Thread(new IncrementTask()); // 創建第二個線程

        thread1.start(); // 兩個線程同時啟動
        thread2.start(); // 兩個線程同時啟動

        try {
            thread1.join(); // 等待 thread1 完成工作
            thread2.join(); // 等待 thread2 完成工作
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final value of a: " + a); // 輸出最終的結果 a
    }

    private class IncrementTask implements Runnable {
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++) {
                increment(); // 呼叫 10000 次 increment()
            }
        }
    }

    private void increment() {
        a++; // increment() 會讓 a = a + 1
    }
}

這個程式的輸出結果並不會如我們想像的「線程 1 呼叫 10000 次、線程 2 呼叫 10000 次，所以最後 a 應該會等於 10000 + 10000 = 20000」。

最後的輸出結果很有可能會比 20000 小，因為：

1
2
3
4

// 當我們進行 a++
a++;
// 事實上是在進行
a = a + 1;

也就是說其實 a++ 不是一個操作，是好幾個操作：

1
2
3

1. 取得 a 現在的值（拿在手上）
2. 把手上拿的值 + 1
3. 把手上加完的值放回（賦值）給 a

所以在兩個線程同時操作的情況下，就可能發生這種事：

1
2
3
4
5
6
7
8
9

// a 目前是 0
Thread1 取得 a 目前的值 (0)
Thread2 取得 a 目前的值 (目前 a 還是 == 0)

Thread1 把手上的值 + 1 (手上的值 == 1)
Thread2 把手上的值 + 1 (手上的值 == 1)

Thread1 把手上的值放回 a (a 目前 == 1)
Thread2 把手上的值放回 a (a 目前還是 == 1)

雖然 Thread1 跟 Thread2 都做了一次 a++，但 a 的變數卻沒有如我們所願變成 2，這就是資源競爭的問題。

那麼互斥鎖要怎麼解決這種問題呢？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// a 目前是 0
Thread1 取得鎖
Thread1 取得 a 目前的值 (0)
// Thread2 此時可能也想取值，但鎖已經被 Thread1 取走，所以只能等待
Thread1 把手上的值 + 1 (手上的值 == 1)
Thread1 把手上的值放回 a (a == 1)
Thread1 釋放互斥鎖

Thread2 取得鎖
…（以下省略）

透過上鎖的操作，我們就可以避免資源競爭的問題。

所以這題的答案是 True：當多個執行緒同時調用同一個對象的 lock 方法時，只有一個執行緒能夠獲得鎖，其他執行序會進入等待狀態。

Q23.6

(Multithreading Terms) Define each of the following terms.
a) blocked state
b) thread scheduling
c) quantum
d) thread confinement
e) atomic operation
f) indefinite postponement
g) monitor lock
h) thread priority

A23.6

a) blocked state

Blocked state (阻塞狀態) 是指執行緒正在等待某個資源 (例如互斥鎖) 或等待某個條件達成 (例如等待 I/O 操作，像是讀取網頁)，無法繼續執行。

b) thread sceduling

Thread scheduling (線程調度/執行緒調度) 是指作業系統決定哪些 Thread 應該獲得 CPU 時間來運行的過程。

c) quantum

Quantum 是指分配給每個 Thread 的時間片段，當 Quantum 用完時，調度器可能會把 CPU 分配給別的 Thread 執行 (目前的被暫停執行)

d) Thread confinement

Thread confinement 是指變數只能被一個 Thread 讀寫，(比如講每個 thread 自己獨享的 local variable，絕對不會被別人讀寫的那種)。可以避免資源競爭問題。

e) Atomic operation

Atomic operation (原子操作) 是指不可以分割的操作。原子操作要嘛被完成、要嘛不完成，不會有「做一半」的狀態。

比如講 a = 5 就是一個原子操作，a 要嘛變成 5，要嘛沒被我們賦值。

或是前幾題的 a++ 就不是原子操作，因為它其實是由 取得 a 的值、把取得的值 + 1、把值賦值給 a 三個操作構成的。

f) Indefinite posponement

Indefinite posponement (無限期推遲) 是指一個 Thread 無限期地等待某個條件達成 (永遠等不到)，導致它沒辦法繼續工作。

g) Monitor lock

Monitor lock 是 Java 中每個物件都會有的內建的互斥鎖。當我們用 synchronized 關鍵字要求方法需要同步執行 (不會有兩個線程同時執行) 時，Thread 就會自動去獲取 monitor lock。

h) Thread priority

Thread priority (線程優先級/執行緒優先級) 是指調度器用來決定 Thread 執行順序的一個數值。優先級越高的 Thread 通常會比優先級低的 Thread 更早被執行。

Q23.23

Write java codes that generates two threads, one thread can be used to calculate the number of prime numbers between 2-10000 and the other thread can be used to calculate the number of prime numbers between 10000-20000, and answer the following questions:
(a) Which thread finishes first?
(b) Are there more primes between 2-10000 or more primes between 10000-20000?

A23.23

寫一個 java 程式，程式需有兩個 threads，第一個 thread 計算 2-10000 的質數；另一個 thread 計算 10000-20000 的質數，並回答以下問題：
(a) 哪一個 thread 會比較快完成工作？
(b) 2-10000 和 10000-20000 這兩個區間，哪個質數比較多？

程式碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public class EX_23_23 {
    public static void main(String[] args) {
        Thread thread1 = new Thread(new PrimeCounter(2, 10000));
        Thread thread2 = new Thread(new PrimeCounter(10000, 20000));

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class PrimeCounter implements Runnable {
    private int start;
    private int end;

    public PrimeCounter(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        System.out.println("Number of prime numbers between " + start + " and " + end + " is " + count);
    }

    public boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

執行結果：

(a) 哪一個 thread 會比較快完成工作？

從結果可以看到，答案是：不一定。雖然 1-10000 這個區間的數字比較小，在進行檢查的速度應該比較快，但是執行速度還會受到系統資源分配、CPU 效能、其他正在運行的程式等因素的影響，所以無法確定哪個執行緒會比較快完成。

(b) 2-10000 和 10000-20000 這兩個區間，哪個質數比較多？

• 2-10000：1229 個質數
• 10000-20000：1033 個質數

所以在 2-10000 這個區間的質數比較多。