# Linux 核心專題: Java 並行程式設計案例
> 執行人: zack-404
> [專題解說影片](https://youtu.be/vgM3FvWceCA)
### Reviewed by `jeremy90307`
這題目看起來蠻有趣的，因為我沒學過 Java ，蠻好奇其他程式的並行程式設計會長怎樣，也許最後可以將 Java 與 C 的並行程式來做比較，應該會蠻有趣的!最後整理以下問題:
1. 想請問你的 ThreadPool 這段是並行還是平行?因為這篇文章並行和平行混雜，也沒有特別說到為何突然變成平行。
2. 你的影片連結有問題
3. 內容可以補充更多應用的範例
> [name=zack-404]
> 感謝你的建議，以下是回答
> 1. 引自 [並行程式設計: 概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts#Concurrency-%E4%B8%A6%E8%A1%8C-vs-Parallelism-%E5%B9%B3%E8%A1%8C) 中對於並行與平行的定義， Java 的 `ThreadPool` 是一個會用到平行（parallelism, multi-processing）的並行（concurrency, multi-threading）。他的運作原理是因為會有固定數量的 `Thread` 在執行 `ThreadPool` 中的任務。 `ThreadPool` 中的任務一定是並行的，而在經過多個 `Thread` 執行後，就可以是平行的。 [`ThreadPool`](###ThreadPool) 已新增相關圖片及論述。
> 2. 影片之後會補上
> 3. 感謝你的建議
## 任務簡介
學習 [Java Concurrency](https://docs.oracle.com/javase/tutorial/essential/concurrency/)，並以經典的生產者消費者問題作為探討案例。
## TODO: 學習 [Java Concurrency](https://docs.oracle.com/javase/tutorial/essential/concurrency/)
> 列出 Java 並行的各式基礎建設，解釋 thread, thread pool, memory consistency, synchronized, `java.util.concurrent` 套件 (至少要提及 Executor 和 fork/join 模式), deadlock vs. livelock, immutable, lock 等議題，適度提供範例程式碼 (要改寫，不同於 Oracle 提供的範例)。
### `Thread`
`Thread` 是一個在 `java.lang` 內的一種物件，他可以在 Java 中建立額外的執行緒執行程式碼。使 Java 具並行程式設計的特質。
在實作中，有以下兩種常見的實作方法：
1. 繼承 `Thread` 這個物件
```java
class SendDataToSevrver extends Thread {
String JSON;
public SendDataToServer(String JSON) {
this.JSON = JSON;
}
public void run() {
sendData(JSON);
}
}
class MAIN() {
public static void main(String[] args) {
String JSON = "{\"name\":\"zack\"}";
SendDataToServer s = new SendDataToServer(JSON);
s.start();
}
}
```
2. 實作 `Runnable` 介面，在藉由 `Thread` 執行
```java
class SendDataToServer implements Runnable {
String JSON;
public SendDataToServer(String JSON) {
this.JSON = JSON;
}
public void run() {
sendData(JSON);
}
}
class MAIN() {
public static void main(String[] args) {
String JSON = "{\"name\":\"zack\"}";
Thread t0 = new Thread(new SendDataToServer(JSON));
t0.start();
}
}
```
在實作中，兩者最大的差異就是前者不能再繼承其他物件了，而後者除了可以繼承其他物件，還可以實作其他介面。因此，通常是以 `Runnable` 介面實作居多。
值得注意的是，同一個實作 `Runnable` 介面的物件，是可以同時被多個 `Thread` 執行的，且 `有些` 變數是可以互通的，但也可能帶來一些問題，如搶佔。範例程式碼如下：
### [memory consistency](https://docs.oracle.com/javase/tutorial/essential/concurrency/memconsist.html)
Java 的 Memory model 如下圖，每個執行緒會有自己一個快取空間放置自己的 local object ；但若要與其他執行續共享物件，則要把物件存於堆積（heap）中。
以下圖為例，若執行緒 A 想要存取並運算物件 O ，但在執行緒 A 存取運算的過程中，若執行緒 B 也想要存取物件 O ，那執行緒 B 存取到的物件 O 可能還會是執行緒 A 運算前的結果。執行緒 A 與執行緒 B 所存取到的物件 O 並不一致，這就是 memory inconsistency 。
:::danger
memory consistency 和 preemption 其實是不同議題，不要混淆。
澄清這部份的描述，不要參照 Wikipedia 這樣過於簡化的材料。
> [name=zack-404]
> 已參閱 Oracle Java Documents 改變敘述。
:::
為解決這個問題，我們就要使用 `synchronized` 或 lock 來解決 memory inconsistant 的問題。
```mermaid
graph
A1(Thread A) --> B1(Thread Stack A)
B1 --> C1(Cache A)
A2(Thread B) --> B2(Thread Stack B)
B2 --> C2(Cache B)
subgraph Heap
E[obj O]
end
C1 --> E
C2 --> E
```
### `volatile`
### `synchronized`
`synchronized` 這個關鍵字會限制只能有一個執行緒在存取物件或使用物件中的 `synchronized` 方法，這可以避免並行程式設計中搶佔的情況發生。
:::danger
在 Java 的術語，是 method (方法)，而非 function (函式)
> [name=zack-404]
> 以更正
:::
1. synchronized block
下列為 `synchronized block` 的程式範例。若以下列方式撰寫， `synchronized` 就會限制在同一時間只能有一個執行緒存取 `count` 這個變數，最後 `count` 應為 2 。若沒有加上 `synchronized` ，因可能兩個執行緒同十加 1 而造成搶佔的問題， `count` 則有可能是 1 。
```java
class Counter implements Runnable {
int count;
Counter(int count) {
this.count = count;
}
public Run() {
synchronized(count) { count++; }
}
public int getCount() { return count; }
}
class MAIN () {
public static void (String[] args) {
Counter counter = new Counter(0);
Thread t0 = new Thread(counter);
Thread t1 = new Thread(counter);
System.out.println(counter.getCount());
}
}
```
3. synchronized method
在一個物件中，若有多個加上 `synchronized` 關鍵字的方法，那在同一時間裡，只有一個執行緒可以執行帶有 `synchronized` 關鍵字的方法。
:::danger
參閱作業系統的教材 (如 OSTEP)，以理解為何有上述限制。有些教材稱這樣的手法為 [monitor](https://en.wikipedia.org/wiki/Monitor_(synchronization))。
> [name=zack-404]
> 限制是指「同一時間只能有一個執行緒執行」嗎？避免發生搶佔或其他非預期結果嗎？
> 不，閱讀 OSTEP
> [name=zack-404]
> 現有執行緒 A 與執行緒 B 要存取物件 O ，假設執行緒 A 先存取到了物件 O ，為確保 memory consistancy ，必須確認執行緒 B 存取到的物件 O 發生在執行緒 A 存取之後，也就是說執行緒 B 必須等待執行緒 A 完成存取才能進行存取。為達到這個目的，我們可以使用 `synchronized` 這個關鍵字去實作。
>
> 若是以 `synchronized` block 實作，那可以避免 `synchronized` block 中的物件發生 memory inconsistent。
>
> 若使以 `synchronized` method 實作，那可以避免與這個方法有關的物件發生 memory inconsistent。
:::
以下列程式為例， `count` 理應為 4 ，若 `countIncrement` 沒有加上 `synchronized` 關鍵字， `count` 則可能為 2, 3, 或 4 。
```java
class Counter implements Runnable {
int count;
Counter(int count) {
this.count = count;
}
public Run() {
countIncrement();
countIncrement();
}
public synchronized void countIncrement() {
count++;
}
public int getCount() { return count; }
}
class MAIN () {
public static void (String[] args) {
Counter counter = new Counter(0);
Thread t0 = new Thread(counter);
Thread t1 = new Thread(counter);
System.out.println(counter.getCount());
}
}
```
### `Lock`
在 `synchronized` 的實作中，等待其他執行緒完成 synchronized method 或 synchronized block 中的程式，其實就包含了 lock(monitor lock) 的實作。但若要設計更複雜的 lock 邏輯，就可以使用 `Lock` 介面，而 `java.util.concurrent.locks` 中有提供各類的 Lock 實作，包含課程提到的 `ReentrantLock` 或 `ReentrantReadWriteLock`。
以類似於 [`synchronized`](###synchronized) 的範例程式為例：
```java
class Counter implements Runnable {
int count;
private final Lock lock = new ReentrantLock();
Counter(int count) {
this.count = count;
}
public Run() {
lock.lock();
try {
count++;
} finally {
lock.unlock();
}
}
public int getCount() { return count; }
}
class MAIN () {
public static void (String[] args) {
Counter counter = new Counter(0);
Thread t0 = new Thread(counter);
Thread t1 = new Thread(counter);
System.out.println(counter.getCount());
}
}
```
值得注意的是 `Run()` 中的 `try-finally` 是為了處理臨界區間（critical section）的發生。
### Dead Lock vs Live Lock 與 starvation
Dead lock 就是多個執行緒因為某個 lock 導致無法繼續執行程式。 Live lock 就是一個執行緒在等待其他執行緒釋放 lock ，在這過程該執行緒是無法執行任何程式的，這個狀態就是 starvation 。
:::danger
用更嚴謹的定義來解說，參閱 OSTEP。
:::
> context switch occurs in a critical section. ---- OSTEP
以雞生蛋，蛋生雞為例，如果沒有蛋也沒有雞，互相都在等待彼此的出現，那這就會是一個 Dead lock。
:::danger
不是這樣，避免濫用過度簡化的概念，否則你無法區分 deadlock 和 livelock。
:::
若有一隻雞了，那等牠下蛋的過程就是一個 lock ，這段時間那隻雞是不會有任何產出的這過程也就是 starvation。等到牠下蛋後，等待蛋孵化的過程也是一個 lock ，同樣地過程也不會有任何產出，這過程也就是 starvation。
### immutable
在牛津字典中，immutable 的定義是：
> unchanging over time or unable to be changed.
在程式設計中，immutable 的意思是指一個物件一旦被初始化後，其狀態（state）就不能再被改變。
在 Java 中，字串 (`String`) 是一個典型的 immutable object。然而，以下操作仍然是合法的：
```java
String a = "Hello";
System.out.println(a);
a = "world";
System.out.println(a);
```
在這段程式碼中，我們可以發現同樣是列印 a，但其值卻不一樣。這是因為我們並沒有修改原來字串的內容，而是將變數 a 指向的記憶體位置從 `"Hello"` 改為 `"world"`。因此，`"Hello"` 和 `"world"` 這兩個字串本身都是不可變的 (immutable)，但我們可以改變 a 指向的記憶體位置。
這也是為什麼在串接字串時，使用 `"String1" + "String2"` 會比使用 `StringBuilder` 更消耗記憶體空間和執行時間。每次使用 `"String1" + "String2"`，記憶體內都會產生新的字串對象。如果這個操作是在一個大迴圈中進行，那麼將會佔據大量的記憶體空間。而 `StringBuilder` 是一個可變的 (mutable) 物件，因此使用 `StringBuilder` 來串接字串會更快且佔用更少的記憶體空間。
:::danger
不是這樣，你如何區分 constant 和 immutable？
需要更多關於 immutable 的論述，且對照英英字典去解釋其原本的意思。
:::
在 Java 中，我們可以使用 `private` 及 `final` 兩個關鍵字確保物件的狀態不會被改變
物件中的值在經過初始化後，就都不會改變了。以人的身分證字號（`id`）及出生日期（`birth`）為例，在出生過後這些資料就不會改變了，所以就可以以 `private` 及 `final` 確保資料的不可竄改，範例程式如下：
:::danger
上方說法有誤，參閱作業系統教材修正。
> [name=zack-404]
> 若把「物件內的東西」修改為「物件的狀態」是否正確？
> 不精確
:::
```java
class ImmutablePeople {
private final id;
private final birth;
ImmutablePeople(String id, String birth) {
this.id = id;
this.birth = birth;
}
}
```
### `ThreadPools`
在現實世界的問題中，許多運算並不是能完全平行的，常需要等待其他執行緒完成到一個段落才能繼續進行，也就是說並不是建立愈多執行緒速度就可以更快。再加上建立一個新的 `Thread` 需要相當的記憶體，所以一般實作中不會開到太多的執行緒。
:::danger
在你的中學課本，除了「創建民國」外，你在哪本教科書讀到「創建」ㄧ詞？務必使用流暢且符合台灣經典出版物風格的用語。
> [name=zack-404]
> 了解，已修改。
:::
延續前一部分，我們知道實作 `Runnable` 介面的物件可以被執行緒執行，那這樣是不是就可以把諸多個想要平行處理的任務分到多個實作 `Runnable` 介面的物件，而讓一定數量的執行緒執行這些物件。這麼做不僅可以減少開立 `Thread` 的記憶體開銷，還可以提升執行續的運算效率，避免執行緒發生 starvation 情形。
:::danger
避免用「塞滿」這種不精準的話語。
> [name=zack-404]
> 已改變敘述。
:::
而放這些待執行物件的地方就是 `ThreadPool` 。另外，這裡除了可以放 `Runnable` 的物件，也可以放 `Callable` 的物件。
以下圖為例，我們會將多個 `task` 放入 `ThreadPool` 中，讓 4 個 `Worker Thread` 執行，
```mermaid
graph
subgraph Worker Thread
w0[worker0]
w1[worker1]
w2[worker2]
w3[worker3]
end
subgraph Thread Pool
t0[task0]
t1[task1]
t2[task2]
t3[task3]
t4[task4]
t5[task5]
t6[task6]
t7[task7]
t8[task8]
t9[task9]
end
t3 --- t4 --- t5 --- t6
t9 --- t8 --- t7 --- t6
t3 --- t2 --- t1 --- t0
```
### `Executer`
在介紹 [`Thread`](###`Thread`) 的章節中，可以發現到若我們一直用
```java
Thread thread = new Thread(new runnableObj());
thread.start();
```
就會顯得很冗長，且建立一個新的 `Thread` 物件也會增加記憶體開銷。但若如果使用 `Executer` ，他會使用使要執行的 `Runnable` 物件，那則會由現有的 `Worker Thread` 執行，而非另一個 `Thread`。範例程式如下：
```java
class Run implements Runnable {}
class Exe implements Executer {}
Run r = new Run();
Exe e = new Exe();
e.execute(r);
```
:::danger
關鍵不在於冗長與否，行為就是不同。
> [name=zack-404]
> However, the definition of execute is less specific. The low-level idiom creates a new thread and launches it immediately. Depending on the Executor implementation, execute may do the same thing, but is more likely to use an existing worker thread to run r, or to place r in a queue to wait for a worker thread to become available. (We'll describe worker threads in the section on Thread Pools.) ---- Oracle Java Document
> 根據文件，底層邏輯確實可能是在額外建立一個 `Thread` 物件去執行 `Runable` 物件，但會更著重於運用現有的`Worker Thread` 去執行 `Runable` 物件。不確定這樣更改是否有符合要求。
> 後面還有很多陳述，對照 API 文件。什麼叫做「確實可能」？
>
:::
### `ExecuterService`
`ExecuterService` 與 `Executer` 兩個介面唯一的差異就是 `ExecuterService` 也可以執行 `Callable` 物件，並允許 `e.execute()` 回傳一個 `Future` 物件。
### Fork/Join
## TODO: 實作生產者-消費者程式碼
> 針對 (Open)JDK 8+，實作生產者-消費者程式碼，支援 SPSC, SPMC, MPSC, MPMC 等情境，使用 atomic variable 和利用 `java.util.concurrent` 套件，要有對應的測試程式碼，且分析對應的效能表現，應涵蓋 lock-based 和 lock-free 的實作。
> 提供對應的文件和介面說明。
~~以下範例將以伺服器驗證使用者登入帳號密碼的正確為例。~~
:::danger
你不用特別跟應用場景建立關聯，程式碼儘量要通用。
:::
<s>
### 自動產生亂數帳號密碼
為了要能夠有足夠數量的帳號密碼進行驗證，我們使用 `java.security.SecureRandom` 自動產生亂數的帳號密碼。實作可見於 [RandomAccount.java](https://github.com/zack-404/javaConcurrency/blob/main/MultiProducer-MultiConsumer/RandomAccount.java) 。
</s>
:::danger
提供通用的程式碼，支援 SPSC, SPMC, MPSC, MPMC 等情境。
:::
## 問題簡記
### function 與 method
function （函式）的定義為物件外的一段可執行程式，而 method （方法）的定義則為一段程式與特定的物件有關\
### object 與 interface
### Thread Pool 與 ForkJoinPool 之間的關係
Sign in with Wallet
Connect another wallet