# [Python] Process(程序)/Thread(執行緒)/GIL(全局解釋器鎖/Deadlock(死鎖))

###### tags: `後端`

### 程序(Process) vs 執行緒(Thread) vs協程(Coroutine)


https://longzonwu.com/software-development/operation-system/what-is-process-thread-coroutine/

1. `Program`(程式):

>開發者開發出來的**程式碼**，**尚未載入到memory**

2. `Process`(程序, **進程**):

>**啟動應用程式(program)時產生的執行實體，將program載入到memory，需要一定的CPU與記憶體等資源**，才有辦法完成工作。彼此互相獨立，**不會共用記憶體資源**。比如說，像是開啟word和excel。
>
>**Process 是 Thread 的容器，一個 Process 中可以持有多個 Thread**

3. `Thread`(執行緒, **線程**):

>就是**執行工作的基本單位**。**同一個程序(Process)中的執行緒(Thread)之間，可以共用記憶體資源**。比如說，word裏頭繪圖跟編輯文字兩個功能就是在同一個程序(Process)裡但不同的執行緒(Thread)。

底下是python的threading模組的基本應用:

import threading
import time
 
def sleep(s):
    print("Let's sleep\t ", time.ctime())
    time.sleep(s)
    print("Wake up\t ", time.ctime())
 
t = threading.Thread(target=sleep, args=(3,))  #建立執行緒，後面引述要用tuple傳入

print('Start')
t.start()      #執行
print('End')

輸出結果

Start
Let's sleep	  Mon Feb  1 15:40:30 2021
End
Wake up	  Mon Feb  1 15:40:33 2021

可以看到當sleep函式在睡覺的時候，CPU不會等待主執行緒睡覺，會自動切換到另一個執行緒去印出End，印完後再回到主執行緒，接著印出Wake up。

4. `Multithreading`(多執行緒):

>**在同一個Process中，建立多個Thread同時執行任務**，藉此來提升效率。
>
>**當主執行緒(Main Thread)閒置或等待時，CPU就會切換到另一個執行緒(Thread)執行其它的工作，完成後再回到主執行緒(Main Thread)繼續往下執行。**

5. `Coroutine`(**協程**)：
>是一種**用戶態的輕量級線程**，可以想成一個線程裡面可以有多個協程，而**協程的調度完全由使用者控制**
>
>Coroutine 一次只會執行一個 Job ，會透過**頻繁切換 Job**達到類似**異步**的效果，需要的資源比開新的 Thread 少。
>
>Coroutine 任務**類似平常大家寫的 function，但又不像一般的 function，Coroutine 是可以隨時暫停執行，再從暫停的地方恢復執行的 function。**
>
>在 Python 中的 **async, await, yield, generator**…等，就是 Coroutine 很好的應用。

**!! 總結流程<重要> !!**

>程式碼(Program)寫好之後執行，會被轉成機器看得懂的machine code，接著，**作業系統會分配記憶體，讓machine code載入到記憶體內，產生process。** **不同的Process之間不會共享資源(ex:記憶體、變數)**，此時，程式碼尚未開始被執行，**Process要被分派給CPU，才可以讓CPU執行Process內的任務，** 而一個CPU只能執行一個Process的任務，所以才會演變成多核心(CPU核心數愈多)的電腦，可以更多工，一次處理更多任務。**CPU執行Process內的任務靠的就是Process內的Thread。同一個Process底下的Thread可以共用該Process的資源(ex:記憶體、變數)，此外Thread彼此之間也會共享資源。** 當Process分派給CPU之後，Process上的**Thread會跟CPU索取CPU時間，此時CPU才會開始執行Thread內的任務**。
>
>所以，**Process**是作業系統分配**記憶體資源**的對象，而 **Thread** 是作業系統分配 **CPU 時間**的對象，有 CPU 時間，才可以執行 Thread 上的任務。

以蓋房子當作例子：

**建設公司 <–> 作業系統
磚塊、水泥、鋼筋、怪手 <–> 記憶體資源
建案 <–> Process
建築工人 <–> Thread**

### GIL(Global Interpreter Lock)

>In **CPython**, **the global interpreter lock, or GIL, is a mutex that protects access to Python objects, preventing multiple threads from executing Python bytecodes at once**. This lock is necessary mainly because CPython’s memory management is not thread-safe. (However, since the GIL exists, other features have grown to depend on the guarantees that it enforces.)

>**Mutex(互斥鎖): 是一種用於多執行緒編程中，防止兩條執行緒同時對同一公共資源（比如全域變數）進行讀寫的機制。**

白話來說，在執行 multiple threads 時，CPython memory 會有 thread-safe 的問題，所以**在 Python Source Code 直譯成 bytecodes 時增加 GIL (Global Interpreter Lock) 的全域鎖。用於確保在 Python 運行時僅運行一個 Thread 來保證 Thread-safe。**

>Therefore, with only one thread running at a time, GIL ensures there will never be race conditions.
>
>In fact, a Python process cannot run threads in parallel but it can run them concurrently through context switching during I/O bound operations.

:fire:
- **GIL鎖是一個互斥鎖（或鎖），它只允許一個線程(thread)持有 Python 解釋器的控制權。**
- **GIL鎖會確保不會有race condition的問題!!**
- **CPU-bound的任務，GIL鎖會阻礙multiple-thread的效率，但IO-bound不受影響**
- **因為有GIL鎖，所以只能達到Concurrency(切換thread，同一時間不會執行多個thread)，不能達到parallelism(真正的非同步，同一時間可以執行多個thread)**
- **若不想用GIL鎖，解決方法是採用multiple-process(但開銷會較大)**
- **GIL鎖只存在於CPython中，其他直譯器實作(Jython, PyPy...)則沒有此問題**

https://towardsdatascience.com/multithreading-multiprocessing-python-180d0975ab29

https://towardsdatascience.com/python-gil-e63f18a08c65

何謂Thread Safe?
>當多執行緒同時運行，並對同一資源進行讀寫操作的修改時，必須保證其執行緒與執行緒間不會發生衝突，和數據修改不會發生錯誤，稱為 thread-safe。

**每一個 Python 線程，在 CPython 解釋器中執行時，都會先鎖住自己的線程，阻止別的線程執行。等待該線程執行完畢後再釋放GIL，供下一個線程使用。**

* [[Python爬蟲教學]善用多執行緒(Multithreading)提升Python網頁爬蟲的執行效率](https://www.learncodewithmike.com/2020/11/multithreading-with-python-web-scraping.html)
* [Python 多執行緒 threading 模組平行化程式設計教學](https://blog.gtwang.org/programming/python-threading-multithreaded-programming-tutorial/)
* [【Python教學】淺談 GIL & Thread-safe & Atomic operation](https://www.maxlist.xyz/2020/03/15/gil-thread-safe-atomic/)

### !! 死鎖（Deadlock）條件，以及如何解死鎖

**何謂Deadlock(死鎖):**
>意思是系統中存在**一組 process 陷入互相等待對方所擁有的資源的情況，造成所有的 process 無法往下執行，使得 CPU 利用度大幅降低。**


須符合以下四項充要條件才會發生deadlock:

1. `Mutual exclusion(互斥)`：資源在**同一時間內，最多只允許一個process使用(不允許≥2個processes同時使用)**，其它欲使用此resource的process必須wait，直到該process釋放resource為止
2. `Hold and wait(持有並等待)`：**process持有部分資源且又在等待其它processes所持有的資源**
3. `No preemption(不可強取豪奪)`：**process 不可以任意強奪其他 process 所持有的資源，除非其自願釋放**
4. `Circular waiting(循環等待)`：系統中存在**一組 processes P=P0,P1,…,Pn，其中 P0 等待 P1 所持有的資源 ... Pn 等待 P0 所持有的資源，形成循環式等待。**(因此，**deadlock不會存在於single process環境中**)

Deadlock 三種處理方法：

1. `Deadlock prevention`: **打破四項條件之一**，即可保證 Deadlock 永不發生
* 打破 Mutual exclusion：為某些資源與生俱來之性質，無法打破。
* 打破 Hold and wait，有兩種協定:
* 協定一: **除非 proces 可以一次取得所有工作所需的資源，才允許持有資源。**
* 協定二: process 執行之初可持有部分資源，但**要再申請資源前，要先釋放手中所有資源。**
* 打破 Preemption : **process可以搶奪waiting process所持有的Resource，雖然不會發生deadlock但有可能造成starvation**
* 打破 Circular waiting，有兩個步驟：
* 步驟一: 給予每個Resource唯一的(unique)資源編號(ID)
* 步驟二: 規定process需依資源編號遞增的方式提出申請

        eg.  持有          申請
         1    R1      →     R3  ok
         2    R3      →     R1  需先釋放R3，才可申請R1
         3    R1,R5   →     R3  釋放R5, 留R1, 即可申請R3

2. `Deadlock avoidance`: 當process提資源申請(Request)時，則OS需依據下列資訊：
1. 系統目前**可用的資源數量(Available)**
2. 各process對資源的**需求量(Need or Max)**
3. 各process**目前持有的資源量(Allocation)**

執行**Banker's Algorithm**(內含Safety Algorithm)判斷系統 **若** 核准後，是否處於Safe state，若是，則核准申請，否則(處於unsafe state)，則否決此次申請，Process則等待依段時間後再重新申請

3. `Deadlock detection & recovery`
1. 偵測死結是否存在
2. 若死結存在，則必須打破死結，恢復正常的機制

* 前兩點的 `prevention` 和 `avoidance` 保證系統不會進入 Deadlock，但資源利用度低
* 第三點的 `detection` 資源利用度較高，但若 Deadlock 需要做 recovery，則 cost 極高

### Deadlock vs Starvation:

>Deadlock是沒有希望(除非不要hold & wait，適當捨得)，Starvation則是還有希望(利用Aging老化技術，提升資歷就有機會扭轉乾坤，反轉人生)


Starvation解決的方法: 採取類似 `Aging` 技術 **(將被搶奪的次數，列為提高優先權之依據)**

[OS - Ch7 死結 Deadlock](https://mropengate.blogspot.com/2015/01/operating-system-ch7-deadlock.html)
[Chapter 5 Deadlock(死結)](http://www.csie.ntnu.edu.tw/~swanky/os/chap5.htm)

### Race Condition(競爭情況)
在多 Thread (或多 CPU) 的情況之下，兩個 thread 可以共用某些變數，但是共用變數可能造成一個嚴重的問題，那就是**當兩個 thread 同時修改一個變數時，這種修改會造成變數的值可能錯誤的情況**

因為多線程的程式會有競爭情況，為了避免該情況而引入了鎖定機制，
但是鎖定機制用得不好就會造成死結。


原先預期會輸出12，但因為race condition的原因，最終結果卻是11


增加 **鎖(Lock)** 的機制，來控制Thread的read、write

[Multithreading in Python | Set 2 (Synchronization)](https://www.geeksforgeeks.org/multithreading-in-python-set-2-synchronization/)

### 調度策略（Scheduler）

1. 長程排班程式Long-Term Scheduler (或稱 Job Scheduler)

>不適用於Time-Sharing System，可調合CPU-Bound與I/O Bound processes之混合比例，且這個的執行頻率最低。
2. 短程排班程式Short-Term Scheduler (或稱 CPU Scheduler)

>從Ready Queue挑選高優先度的Process，使之獲得 CPU控制權執行，Batch System和Time-Sharing都需要，Batch System和Time-Sharing均需要，這個的執行頻率最高。
3. 中程排班程式Medium-Term Scheduler

>通常用在Time Sharing System，也可以調合I/O Bound與CPU Bound的比例。

### Inter-Process Communication(IPC)

* **process 與 process 間是利用 IPC（inter-process communication）的方式來溝通**
* processes分為兩種，一種是不會互相影響的independent process，另一種是可以互相影響的cooperating process。
* 而實際上使用multiple process的時機大多是在處理事件或在背景做其他事。例如:在等使用者輸入時可繼續計算，或是在背景執行磁碟重組作業。
* 而常見的Inter-Process Communication有shared memory跟message Passing這兩種。
* cooperating process有資訊共享、加速運算和模組化這些好處。