深入理解進程，執行緒，協程
進程，執行緒，協程，以及golang協程和python協程的區別。
1. 進程
進程是系統進行資源分配和調度的一個獨立單位，程式段、數據段、PCB三部分組成了進程實體（進程映像），PCB是進程存在的唯一標準
1.1 進程的組織方式：
- 鏈接方式
- 按照進程狀態將PCB分為多個隊列，就緒隊列，阻塞隊列等
- 作業系統持有指向各個隊列的指針
- 索引方式
- 根據進程狀態的不同，建立幾張索引表
- 作業系統持有指向各個索引表的指針
1.2 進程的狀態
-
創建態： 作業系統為進程分配資源，初始化PCB
-
就緒態：運行資源等條件都滿足，存儲在就緒隊列中，等待CPU調度
-
運行態：CPU正在執行進程
-
阻塞態：等待某些條件滿足，等待消息回復，等待同步鎖，sleep等，阻塞隊列
-
終止態 ：回收進程擁有的資源，撤銷PCB
1.3 進程的切換和調度
進程在作業系統內核程式臨界區中不能進行調度與切換
臨界資源：一個時間段內只允許一個進程使用資源，各進程需要互斥地訪問臨界資源
臨界區：訪問臨界資源的程式碼
內核程式臨界區：訪問某種內核數據結構，如進程的就緒隊列（存儲各進程的PCB）
進程調度的方式：
- 非剝奪調度方式（非搶佔方式），只允許進程主動放棄處理機，在運行過程中即便有更緊迫的任務到達，當前進程依然會繼續使用處理機，直到該進程終止或者主動要求進入阻塞態
- 剝奪調度方式（又稱搶佔方式）當一個進程正在處理機上執行時，如果有一個優先順序更高的進程需要處理機，則立即開中斷暫停正在執行的進程，將處理機飯呢陪給優先順序高的那個進程
進程的切換與過程：進程的調度、切換是有代價的
- 對原來運行進程各種數據的保存
- 對新的進程各種數據恢復（程式計數器，程式狀態字，各種數據暫存器等處理機的現場）
進程調度演算法的相關參數：
- CPU利用率：CPU忙碌時間/作業完成的總時間
- 系統吞吐量：單位時間內完成作業的數量
- 周轉時間：從作業被提交給系統開始，到作業完成為止的時間間隔 = 作業完成時間-作業提交時間
- 帶權周轉時間：（由於周轉時間相同的情況下，可能實際作業的運行時間不一樣，這樣就會給用戶帶來不一樣的感覺） 作業周轉時間/作業實際運行時間， 帶權周轉時間>=1, 越小越好
- 平均帶權周轉時間：各作業帶權周轉時間之和/作業數
- 等待時間
- 響應時間
調度演算法：
演算法思想，用於解決什麼問題？
演算法規則，用於作業（PCB作業）調度還是進程調度？
搶佔式還是非搶佔式的？
優缺點？是否會導致飢餓？
以下調度演算法是適用於當前互動式作業系統
- 時間片輪轉（Round-Robin）
- 演算法思想：公平地、輪流地為各個進程服務，讓每個進程在一定時間間隔內可以得到相應
- 演算法規則：按照各進程到達就緒隊列的順序，輪流讓各個進程執行一個時間片（如100ms）。若進程未在一個時間片內執行完，則剝奪處理機，將進程重新放到就緒隊列隊尾重新排隊。
- 用於作業/進程調度：用於進程的調度（只有作業放入記憶體建立相應的進程後，才會被分配處理機時間片）
- 是否可搶佔？若進程未能在規定時間片內完成，將被強行剝奪處理機使用權，由時鐘裝置發出時鐘中斷訊號來通知CPU時間片到達
- 優缺點：適用於分時作業系統，由於高頻率的進程切換，因此有一定開銷；不區分任務的緊急程度
- 是否會導致飢餓？ 不會
- 優先順序調度演算法
- 演算法思想：隨著電腦的發展，特別是實時作業系統的出現，越來越多的應用場景需要根據任務的進程成都決定處理順序
- 演算法規則：每個作業/進程有各自的優先順序，調度時選擇優先順序最高的作業/進程
- 用於作業/進程調度：即可用於作業調度（處於外存後備隊列中的作業調度進記憶體），也可用於進程調度（選擇就緒隊列中的進程，為其分配處理機），甚至I/O調度
- 是否可搶佔？ 具有可搶佔版本，也有非搶佔式的
- 優缺點：適用於實時作業系統，用優先順序區分緊急程度，可靈活地調整對各種作業/及進程的偏好程度。缺點：若源源不斷地提供高優先順序進程，則可能導致飢餓
- 是否會導致飢餓： 會
- 多級回饋隊列調度演算法
-
演算法思想：綜合FCFS、SJF(SPF)、時間片輪轉、優先順序調度
-
演算法規則：
- 1.設置多級就緒隊列，各級別隊列優先順序從高到底，時間片從小到大
- 2.新進程到達時先進入第1級隊列，按照FCFS原則排隊等待被分配時間片，若用完時間片進程還未結束，則進程進入下一級隊列隊尾
- 3.只有第k級別隊列為空時，才會為k+1級對頭的進程分配時間片
-
用於作業/進程調度：用於進程調度
-
是否可搶佔？ 搶佔式演算法。在k級隊列的進程運行過程中，若更上級別的隊列（1-k-1級）中進入一個新進程，則由於新進程處於優先順序高的隊列中，因此新進程會搶佔處理機，原理運行的進程放回k級隊列隊尾。
-
優缺點：對各類型進程相對公平（FCFS的有點）；每個新到達的進程都可以很快就得到相應（RR優點）；短進程只用較少的時間就可完成（SPF）的有點；不必實現估計進程的運行時間；可靈活地調整對各類進程的偏好程度，比如CPU密集型進程、I/O密集型進程（拓展：可以將因I/O而阻塞的進程重新放回原隊列，這樣I/O型進程就可以保持較高優先順序）
-
是否會導致飢餓： 會
-
-
2. 執行緒
引入執行緒之後，進程只作為除CPU之外的系統資源的分配單元（如：印表機，記憶體地址空間等都是分配給進程的）
執行緒的是實現方式：
- 用戶級執行緒（User-Level Thread），用戶級執行緒由應用程式通過執行緒庫是實現如python (import thread), 執行緒的管理工作由應用程式負責。
- 內核級執行緒（kernel-Level Thread），內核級執行緒的管理工作由作業系統內核完成，執行緒調度，切換等工作都由內核負責，因此內核級執行緒的切換必然需要在核心態下才能完成
進程和執行緒的關係：一條執行緒指的是進程中一個單一順序的控制流，一個進程中可以並發多個執行緒，每條執行緒並行執行不同的任務。CPU的最小調度單元是執行緒，所以單進程多執行緒是可以利用多核CPU的。
2.1 執行緒模型：
- 用戶級執行緒模型(一對多模型)
多個用戶態的執行緒對應著一個內核執行緒，程式執行緒的創建、終止、切換或者同步等執行緒工作必須自身來完成。python就是這種。雖然可以實現非同步，但是不能有效利用多核（GIL）
- 內核級執行緒模型 (一對一)
這種模型直接調用作業系統的內核執行緒，所有執行緒的創建、終止、切換、同步等操作，都由內核來完成。C++就是這種
- 兩級執行緒模型(M:N)
這種執行緒模型會先創建多個內核級執行緒，然後用自身的用戶級執行緒去對應創建的多個內核級執行緒，自身的用戶級執行緒需要本身程式去調度，內核級的執行緒交給作業系統內核去調度。GO語言就是這種。
python中的多執行緒因為GIL的存在，並不能利用多核CPU優勢，但是在阻塞的系統調用中，如sock.connect(), sock.recv()等耗時的I/O操作，當前的執行緒會釋放GIL，讓出處理器。但是單個執行緒內，阻塞調用上還是阻塞的。除了GIL之外，所有的多執行緒還有通病，他們都是被OS調用的，調度策略是搶佔式的，以保證同等有限級的執行緒都有機執行，帶來的問題就是:並不知道下一刻執行那個執行緒，也不知道正在執行什麼程式碼，會存在競態條件
3. 協程
協程通過在執行緒中實現調度，避免了陷入內核級別的上下文切換造成的性能損失，進而突破了執行緒在IO上的性能瓶頸。
python的協程源於yield指令
- yield item 用於產出一個值，回饋給next()的調用方法
- 讓出處理機，暫停執行生成器，讓調用方繼續工作，直到需要使用另一個值時再調用next()
協程式對執行緒的調度，yield類似惰性求職方式可以視為一種流程式控制制工具，實現協作式多任務，python3.5引入了async/await表達式，使得協程證實在語言層面得到支援和優化，大大簡化之前的yield寫法。執行緒正式在語言層面得到支援和優化。執行緒是內核進行搶佔式調度的，這樣就確保每個執行緒都有執行的機會。而coroutine運行在同一個執行緒中，有語言層面運行時中的EventLoop（事件循環）來進行調度。在python中協程的調度是非搶佔式的，也就是說一個協程必須主動讓出執行機會，其他協程才有機會運行。讓出執行的關鍵字 await， 如果一個協程阻塞了，持續不讓出CPU處理機，那麼整個執行緒就卡住了，沒有任何並發。
PS: 作為服務端，event loop最核心的就是I/O多路復用技術，所有來自客戶端的請求都由I/O多路復用函數來處理；作為客戶端，event loop的核心在於Future對象延遲執行，並使用send函數激發協程，掛起，等待服務端處理完成返回後再調用Callback函數繼續執行。[python 協程與go協程的區別]
3.1 Golang 協程
Go 天生在語言層面支援，和python類似都是用關鍵字，而GO語言使用了go關鍵字，go協程之間的通訊，採用了channel關鍵字。
go實現了兩種並發形式：
- 多執行緒共享記憶體：如Java 或者C++在多執行緒中共享數據的時候，通過鎖來訪問
- Go語言特有的，也是Go語言推薦的 CSP(communicating sequential processes)並發模型。
package main
import ("fmt")
func main() {
jobs := make(chan int)
done := make(chan bool) // end flag
go func() {
for {
j, ok := <- jobs
fmt.Println("---->:", j, ok)
if ok {
fmt.Println("received job")
} else {
fmt.Println("end received jobs")
done <- true
return
}
}
}()
go func() {
for j:= 1; j <= 3; j++ {
jobs <-j
fmt.Println("sent job", j)
}
close(jobs)
fmt.Println("close(jobs)")
}()
fmt.Println("sent all jobs")
<-done // 阻塞 讓main等待協程完成
}
Go的CSP並發模型是通過goroutine 和 channel來實現的。
- goroutine是go語言中並發的執行單位。
- channel是Go語言中各個並髮結構體之間的通訊機制。
- channel -< data 寫數據
- <- channel 讀數據
協程本質上來說是一種用戶態的執行緒，不需要系統來執行搶佔式調度，而是在語言測個面實現執行緒的調度。
4. 並發
並發：Do not communicate by sharing memory; instead, share memory by communicate.
4.1 Actor模型
Actor模型和CSP模型的區別：
- CSP並不Focus發送消息的實體/Task， 而是關注發送消息時消息所使用的載體，即channel。
- 在Actor的設計中，Actor與信箱是耦合的，而在CSP中channel是作為first-class獨立存在的
- Actor中有明確的send/receive關係，而channel中並不區分這樣的關係，執行快可以任意選擇發送或者取消息
4.4 Go 協程調度器 GPM
- G 指的是Goroutine，其本質上也是一種輕量級的執行緒
- P proessor， 代表M所需要的上下文環境，也是處理用戶級程式碼邏輯處理器。同一時間只有一個執行緒(M)可以擁有P, P中的數據都是鎖自由(lock free)的, 讀寫這些數據的效率會非常的高
- M Machine，一個M直接關聯一個內核執行緒，可以運行go程式碼 即goroutine, M運行go程式碼需要一個P, 另外就是運行原生程式碼，如 syscall。運行原生程式碼不需要P。
一個M會對應一個內核執行緒，一個M也會連接一個上下文P，一個上下文P相當於一個「處理器」，一個上下文連接一個或者多個Goroutine。P(Processor)的數量是在啟動時被設置為環境變數GOMAXPROCS的值，或者通過運行時調用函數runtime.GOMAXPROCS()進行設置
erlang和golang都是採用CSP模型，python中協程是eventloop模型。但是erlang是基於進程的消息通訊，go是基於goroutine和channel通訊。
python和golang都引入了消息調度系統模型，來避免鎖的影響和進程執行緒的開銷問題。
電腦科學領域的任何問題都可以通過增加一個間接的中間層來解決 — G-P-M模型正是此理論踐行者,此理論也用到了python的asyncio對地獄回調的處理上(使用Task+Future避免回調嵌套),是不是巧合?
其實非同步≈可中斷的函數+事件循環+回調,go和python都把嵌套結構轉換成列表結構有點像演算法中的遞歸轉迭代.
調度器在電腦中是分配工作時所需要的資源，Linux的調度是CPU找到可運行的執行緒，Go的調度是為M執行緒找到P(記憶體，執行票據)和可運行的G(協程)
Go協程是輕量級的，棧初始2KB（OS作業系統的執行緒一般都是固有的棧記憶體2M）， 調度不涉及系統調用，用戶函數調用前會檢查棧空間是否足夠，不夠的話，會進行站擴容，棧大小限制可以達到1GB。
Go的網路操作是封裝了epoll， 為NonBlocking模式，切換協程不阻塞執行緒。
Go語言相比起其他語言的優勢在於OS執行緒是由OS內核來調度的，goroutine則是由Go運行時（runtime）自己的調度器調度的，這個調度器使用一個稱為m:n調度的技術（復用/調度m個goroutine到n個OS執行緒）。 其一大特點是goroutine的調度是在用戶態下完成的， 不涉及內核態與用戶態之間的頻繁切換，包括記憶體的分配與釋放，都是在用戶態維護著一塊大的記憶體池， 不直接調用系統的malloc函數（除非記憶體池需要改變），成本比調度OS執行緒低很多。 另一方面充分利用了多核的硬體資源，近似的把若干goroutine均分在物理執行緒上， 再加上本身goroutine的超輕量，以上種種保證了go調度方面的性能。點我了解更多
4.5 Go 調度器的實現 以及搶佔式調度
相關參考文獻：
作業系統中調度演算法（FCFS、RR、SPN、SRT、HRRN）
