Scala Parallel Programming筆記 1 - Parallelism on JVM

定義

在parallel hardware的存在下，某個problem能夠被分解成許多sub problems，然後同時(in parallel)被解決。

Parallel硬體

這張圖說明了一切：

Parallel Programming vs Concurrent Programming

concurrent programming不是parallel programming，concurrent programming不一定有同時執行的指令或程式。

parallel programming主要是關心速度提升
concurrent programming主要是關心asynchronous資源存取共享
兩者可能有些許交集。

CPU時脈無法再增加

power-wall效應，因為增加時脈需要的能量已經不是線性成長了！

Parallelism on JVM

process是某個program的instance，被OS執行，當然此program也可以被instantiation好幾次，就會有好幾個process執行同一個program，例如我們可以開好幾個terminal，每一個都有不同的process id (PID)。

OS把某個數量的processes分配給少數的cpu (multiplexing)，每個process分到一些time slice，稱為multitasking。processes之間因為安全性問題，不容許access彼此的memory，所以inter-process communication通常不是輕易的事。

比process更細微的primitives是threads，threads屬於同一個process是可以share "heap" memory的，每個thread仍然有自己private memory稱為thread stack，包含了function invocation以及program counter：

每個JVM啓動會spawn main thread，parallel programming的話就需要spawn更多的threads，讓OS來分配threads給有限數量的CPU執行：

join的意義是 caller (main thread)會block 自己的執行，要等到t thread執行完畢後才繼續執行：

2 threads

如果main thread instantiates 2 helloworld threads:

如果重複跑幾次，會發現不同結果：

兩個sequence跑起來結果不一樣，這是正常的，原因在於thread implementation不是atomic operation:

Synchronized Block

防止兩個threads以上的race condition，Scala有一個synchronization機制，稱為monitor。JVM把monitor存在每一個object中，一次只有一個thread能acquire這個monitor，直到monitor被釋放，其他的thread才能acquire此monitor。改寫以上的code:

我們先new一個object x，因為要用他的monitor來synchronize getUniqueId()的code block。
注意這時候code block 被 synchronized key word包住，並且invoked on object x。現在synchronized block可以被視為atomic operation。

Nested synchronized block

假設有一個Account class如下：

同時可能有很多帳戶在做transfer這個動作，這邊的難題在於假設A1 A2同時想要transfer給A3的話怎麼辦？一種可能是用global monitor(宣告某個global object，使用其內的monitor)來synchronize transfer method，但是這會造成bottleneck，因為變成相當於sequential queue了，僅管A3想transfers to A4跟A1 transfers to A2事件無關，但是還是得等到後者release monitor才能執行transfer()。

這邊可以解決的方法是"nested synchronization"，假設A1.transfer(A2, $1000)被某個thread執行時，此thread先acquire A1的monitor，再acquire A2的monitor，所以整個atomic operation只關乎A1和A2，其他parallel執行的transfer只要跟A1 A2皆不相干的話，不用等待monitor release：

Deadlocks

如果我們執行上面的implementation，用以下的code new出兩個threads:

事實上產生了deadlock!

Deadlock發生在某個資源被某thread A acquire住的情況下，其他thread B等待此資源，但A又在等待B acquired住的資源，無解！

上面的code發生deadlock原因在於thread t先acquire a1的monitor，但是還沒acquire a2的monitor的時候，thread s已經start並且acquire a2的monitor，但又等待a1的monitor，變成deadlock。

不過課程中給的solution有點瞎，在此不列，應該是之後才會正式介紹其他的方法。

Java Memory Model

java memory model是一些JVM runtime如何讓threads access shared memory的規定。本課程至少用到以下兩個：

1. 寫入不同記憶體的threads不需要synchronization
2. thread x如果呼叫thread y的join method，則當join method returns，thread x保證會看到thread y所有的寫入結果：

注意：thread x若是沒有呼叫thread y的join，則不能保證thread x read能在thread y 之後發生。