ShuWa

進程、線程和協程#

進程，線程，協程是什麼#

進程，線程，協程的切換問題#

1. 進程切換： 進程切換是由操作系統負責管理和調度的。當操作系統決定切換到另一個進程時，它會保存當前進程的上下文（包括寄存器值、程序計數器等），並加載下一個進程的上下文。這個過程涉及切換內存映射、寄存器和其他資源，因此切換進程的成本較高。進程切換需要操作系統的介入，因此開銷相對較大。
2. 線程切換： 線程切換是在同一進程內進行的，由操作系統負責調度。線程切換也需要保存和恢復寄存器值、程序計數器等上下文信息，但由於線程共享進程的地址空間和資源，因此切換成本相對較低。線程切換仍然需要操作系統的介入，但比進程切換的開銷小很多。
   性能開銷：切換內核堆棧，切換硬件上下文，保存寄存器中的內容，將之前執行流程的狀態保存，CPU 高速緩存失效
   頁表查找是一個很慢的過程，因此通常使用 Cache 來緩存常用的地址映射，這樣可以加速頁表查找，這個 cache 就是 TLB. 當進程切換後頁表也要進行切換，頁表切換後 TLB 就失效了，cache 失效導致命中率降低，那麼虛擬地址轉換為物理地址就會變慢，表現出來的就是程序運行會變慢。
3. 協程切換： 協程切換是在應用程序級別上進行的，由協程庫或程序員顯式管理。協程切換不需要操作系統的介入，因此切換成本非常低。協程的切換通常只涉及保存和恢復少量的上下文信息，例如堆棧指針和局部變量等。由於協程的切換是協作式的，需要顯式地將控制權交給其他協程，因此協程切換的開銷可以更好地控制。
   性能開銷：
   把當前協程的 CPU 寄存器狀態保存起來，然後將需要切換進來的協程的 CPU 寄存器狀態加載的 CPU 寄存器上就 ok 了。而且完全在用戶態進行，一般來說一次協程上下文切換最多就是幾十 ns 這個量級。

協程切換比線程切換快主要有兩點：

1. 協程切換完全在用戶空間進行；線程切換涉及特權模式切換，需要在內核空間完成；
2. 協程切換相比線程切換做的事情更少，線程需要有內核和用戶態的切換，系統調用過程。

總體來說，進程切換的開銷最高，線程切換次之，而協程切換的開銷最低。協程由於在應用程序級別上管理，可以更靈活地控制切換時機，以提高效率和並發性能。然而，需要注意的是，在協程中合理管理切換點，避免過於頻繁的切換，以免帶來額外的開銷。

一個進程最多可以創建多少個線程？

32 位系統，用戶態的虛擬空間只有 3G，如果創建線程時分配的堆棧空間是 10M，那麼一個進程最多只能創建 300 個左右的線程。
64 位系統，用戶態的虛擬空間大到有 128T，理論上不會受虛擬內存大小的限制，而會受系統的參數或性能限制。

線程崩潰，進程崩潰

一般來說如果線程是因為非法訪問內存引起的崩潰，那麼進程肯定會崩潰，為什麼系統要讓進程崩潰呢，這主要是因為在進程中，各個線程的地址空間是共享的，既然是共享，那麼某個線程對地址的非法訪問就會導致內存的不確定性，進而可能會影響到其他線程，這種操作是危險的，操作系統會認為這很可能導致一系列嚴重的後果，於是乾脆讓整個進程崩潰。

進程是如何崩潰的呢，這背後的機制到底是怎樣的，答案是信號 - kill (SIGSEGV)。

為什麼線程崩潰不會導致 JVM 進程崩潰

因為 JVM 自定義了自己的信號處理函數，攔截了 SIGSEGV 信號，針對這兩者不讓它們崩潰。

通信方式有哪些？#

進程間通信方式有哪些？#

• 管道 / 匿名管道 (Pipes)：用於具有親緣關係的父子進程間或者兄弟進程之間的通信。
• 有名管道 (Named Pipes) : 匿名管道由於沒有名字，只能用於親緣關係的進程間通信。為了克服這個缺點，提出了有名管道。有名管道嚴格遵循 先進先出 (First In First Out) 。有名管道以磁碟文件的方式存在，可以實現本機任意兩個進程通信。
• 信號 (Signal)：信號是一種比較複雜的通信方式，用於通知接收進程某個事件已經發生；
• 消息隊列 (Message Queuing)：消息隊列是消息的鏈表，具有特定的格式，存放在內存中並由消息隊列標識符標識。管道和消息隊列的通信數據都是先進先出的原則。與管道（無名管道：只存在於內存中的文件；命名管道：存在於實際的磁碟介質或者文件系統）不同的是消息隊列存放在內核中，只有在內核重啟 (即，操作系統重啟) 或者顯式地刪除一個消息隊列時，該消息隊列才會被真正的刪除。消息隊列可以實現消息的隨機查詢，消息不一定要以先進先出的次序讀取，也可以按消息的類型讀取。比 FIFO 更有優勢。消息隊列克服了信號承載信息量少，管道只能承載無格式字節流以及緩衝區大小受限等缺點。
• 信號量 (Semaphores)：信號量是一個計數器，用於多進程對共享數據的訪問，信號量的意圖在於進程間同步。這種通信方式主要用於解決與同步相關的問題並避免競爭條件。
• 共享內存 (Shared memory)：使得多個進程可以訪問同一塊內存空間，不同進程可以及時看到對方進程中對共享內存中數據的更新。這種方式需要依靠某種同步操作，如互斥鎖和信號量等。可以說這是最有用的進程間通信方式。
• 套接字 (Sockets) : 此方法主要用於在客戶端和服務器之間通過網絡進行通信。套接字是支持 TCP/IP 的網絡通信的基本操作單元，可以看做是不同主機之間的進程進行雙向通信的端點，簡單的說就是通信的兩方的一種約定，用套接字中的相關函數來完成通信過程。

多線程間的通信？#

多線程之間由於共享進程的資源，所以在多線程間通信更多關注如何處理資源使用中的衝突問題。

互斥與同步#

在單核 CPU 系統裡，為了實現多個程序同時運行的假象，操作系統通常以時間片調度的方式，讓每個進程執行每次執行一個時間片，時間片用完了，就切換下一個進程運行，由於這個時間片的時間很短，於是就造成了「並發」的現象。多個線程如果競爭共享資源，如果不採取有效的措施，則會造成共享數據的混亂。

互斥

上面展示的情況稱為競爭條件（race condition），當多線程相互競爭操作共享變量時，由於運氣不好，即在執行過程中發生了上下文切換，我們得到了錯誤的結果，事實上，每次運行都可能得到不同的結果，因此輸出的結果存在不確定性（indeterminate）。
由於多線程執行操作共享變量的這段代碼可能會導致競爭狀態，因此我們將此段代碼稱為臨界區（critical section），它是訪問共享資源的代碼片段，一定不能給多線程同時執行。
我們希望這段代碼是 ** 互斥（mutual exclusion）** 的，也就是說保證一個線程在臨界區執行時，其他線程應該被阻止進入臨界區，說白了，就是這段代碼執行過程中，最多只能出現一個線程。

同步

互斥解決了並發進程 / 線程對臨界區的使用問題。這種基於臨界區控制的交互作用是比較簡單的，只要一個進程 / 線程進入了臨界區，其他試圖想進入臨界區的進程 / 線程都會被阻塞著，直到第一個進程 / 線程離開了臨界區。
我們都知道在多線程裡，每個線程並不一定是順序執行的，它們基本是以各自獨立的、不可預知的速度向前推進，但有時候我們又希望多個線程能密切合作，以實現一個共同的任務。
所謂同步，就是並發進程 / 線程在一些關鍵點上可能需要互相等待與互通消息，這種相互制約的等待與互通信息稱為進程 / 線程同步。

互斥與同步的實現和使用#

鎖

使用加鎖操作和解鎖操作可以解決並發線程 / 進程的互斥問題。
任何想進入臨界區的線程，必須先執行加鎖操作。若加鎖操作順利通過，則線程可進入臨界區；在完成對臨界資源的訪問後再執行解鎖操作，以釋放該臨界資源。
根據鎖的實現不同，可以分為「忙等待鎖」和「無忙等待鎖」。

忙等待鎖

「忙等待鎖」基於原子操作指令 —— 測試和置位（Test-and-Set）指令
當獲取不到鎖時，線程就會一直 while 循環，不做任何事情，所以就被稱為「忙等待鎖」，也被稱為自旋鎖（spin lock）。

無等待鎖

當沒獲取到鎖的時候，就把當前線程放入到鎖的等待隊列，然後執行調度程序，把 CPU 讓給其他線程執行。

信號量

信號量是操作系統提供的一種協調共享資源訪問的方法。

通常信號量表示資源的數量，對應的變量是一個整型（sem）變量。

另外，還有兩個原子操作的系統調用函數來控制信號量的，分別是：

• P 操作：將 sem 減 1，相減後，如果 sem < 0，則進程 / 線程進入阻塞等待，否則繼續，表明 P 操作可能會阻塞；
• V 操作：將 sem 加 1，相加後，如果 sem <= 0，喚醒一個等待中的進程 / 線程，表明 V 操作不會阻塞；

P 操作是用在進入臨界區之前，V 操作是用在離開臨界區之後，這兩個操作是必須成對出現的。

如何使用信號量實現臨界區的互斥訪問

為每類共享資源設置一個信號量 s，其初值為 1，表示該臨界資源未被佔用。
只要把進入臨界區的操作置於 P (s) 和 V (s) 之間，即可實現進程 / 線程互斥:

此時，任何想進入臨界區的線程，必先在互斥信號量上執行 P 操作，在完成對臨界資源的訪問後再執行 V 操作。由於互斥信號量的初始值為 1，故在第一個線程執行 P 操作後 s 值變為 0，表示臨界資源為空閒，可分配給該線程，使之進入臨界區。

若此時又有第二個線程想進入臨界區，也應先執行 P 操作，結果使 s 變為負值，這就意味著臨界資源已被佔用，因此，第二個線程被阻塞。

並且，直到第一個線程執行 V 操作，釋放臨界資源而恢復 s 值為 0 後，才喚醒第二個線程，使之進入臨界區，待它完成臨界資源的訪問後，又執行 V 操作，使 s 恢復到初始值 1。

對於兩個並發線程，互斥信號量的值僅取 1、0 和 -1 三個值，分別表示：

• 如果互斥信號量為 1，表示沒有線程進入臨界區；
• 如果互斥信號量為 0，表示有一個線程進入臨界區；
• 如果互斥信號量為 -1，表示一個線程進入臨界區，另一個線程等待進入。

通過互斥信號量的方式，就能保證臨界區任何時刻只有一個線程在執行，就達到了互斥的效果。

如何使用信號量實現事件同步

同步的方式是設置一個信號量，其初值為 0, 以「吃飯 - 做飯」同步的例子：
媽媽一開始詢問兒子要不要做飯時，執行的是 P (s1) ，相當於詢問兒子需不需要吃飯，由於 s1 初始值為 0，此時 s1 變成 -1，表明兒子不需要吃飯，所以媽媽線程就進入等待狀態。

當兒子肚子餓時，執行了 V (s1)，使得 s1 信號量從 -1 變成 0，表明此時兒子需要吃飯了，於是就喚醒了阻塞中的媽媽線程，媽媽線程就開始做飯。

接著，兒子線程執行了 P (s2)，相當於詢問媽媽飯做完了嗎，由於 s2 初始值是 0，則此時 s2 變成 -1，說明媽媽還沒做完飯，兒子線程就等待狀態。

最後，媽媽終於做完飯了，於是執行 V (s2)，s2 信號量從 -1 變回了 0，於是就喚醒等待中的兒子線程，喚醒後，兒子線程就可以進行吃飯了。

經典同步問題#

生產者 - 消費者問題#

生產者 - 消費者問題描述：

• 生產者在生成數據後，放在一個緩衝區中；
• 消費者從緩衝區取出數據處理；
• 任何時刻，只能有一個生產者或消費者可以訪問緩衝區；

我們對問題分析可以得出：

• 任何時刻只能有一個線程操作緩衝區，說明操作緩衝區是臨界代碼，需要互斥；
• 緩衝區空時，消費者必須等待生產者生成數據；緩衝區滿時，生產者必須等待消費者取出數據。說明生產者和消費者需要同步。

那麼我們需要三個信號量，分別是：

• 互斥信號量 mutex：用於互斥訪問緩衝區，初始化值為 1；
• 資源信號量 fullBuffers：用於消費者詢問緩衝區是否有數據，有數據則讀取數據，初始化值為 0（表明緩衝區一開始為空）；
• 資源信號量 emptyBuffers：用於生產者詢問緩衝區是否有空位，有空位則生成數據，初始化值為 n （緩衝區大小）；

哲學家就餐問題#

先來看看哲學家就餐的問題描述：

• 5 個老大哥哲學家，閒著沒事做，圍繞著一張圓桌吃麵；
• 巧就巧在，這個桌子只有 5 支叉子，每兩個哲學家之間放一支叉子；
• 哲學家圍在一起先思考，思考中途餓了就會想進餐；
• 奇葩的是，這些哲學家要兩支叉子才願意吃麵，也就是需要拿到左右兩邊的叉子才進餐；
• 吃完後，會把兩支叉子放回原處，繼續思考；

用一個數組 state 來記錄每一位哲學家的三個狀態，分別是在進餐狀態、思考狀態、飢餓狀態（正在試圖拿叉子）。

那麼，一個哲學家只有在兩個鄰居都沒有進餐時，才可以進入進餐狀態。

第 i 個哲學家的左鄰右舍，則由宏 LEFT 和 RIGHT 定義：

• LEFT : ( i + 5 - 1 ) % 5
• RIGHT : ( i + 1 ) % 5

比如 i 為 2，則 LEFT 為 1，RIGHT 為 3。

讀者 - 寫者問題#

讀者 - 寫者的問題描述：

• 「讀 - 讀」允許：同一時刻，允許多個讀者同時讀
• 「讀 - 寫」互斥：沒有寫者時讀者才能讀，沒有讀者時寫者才能寫
• 「寫 - 寫」互斥：沒有其他寫者時，寫者才能寫

公平策略：

• 優先級相同；
• 寫者、讀者互斥訪問；
• 只能一個寫者訪問臨界區；
• 可以有多個讀者同時訪問臨界資源；

死鎖#

產生死鎖的條件#

死鎖只有同時滿足以下四個條件才會發生：

• 互斥條件；
• 持有並等待條件；
• 不可剝奪條件；
• 環路等待條件；

如何排查死鎖#

Java - jstack
C++ - Valgrind
Python - 第三方庫 deadlock-detector 和 deadlocks
Go - go tool trace

如何避免死鎖#

使用資源有序分配法，來破壞環路等待條件。

那什麼是資源有序分配法呢？

線程 A 和 線程 B 獲取資源的順序要一樣，當線程 A 是先嘗試獲取資源 A，然後嘗試獲取資源 B 的時候，線程 B 同樣也是先嘗試獲取資源 A，然後嘗試獲取資源 B。也就是說，線程 A 和 線程 B 總是以相同的順序申請自己想要的資源。

我們使用資源有序分配法的方式來修改前面發生死鎖的代碼，我們可以不改動線程 A 的代碼。

我們先要清楚線程 A 獲取資源的順序，它是先獲取互斥鎖 A，然後獲取互斥鎖 B。

所以我們只需將線程 B 改成以相同順序的獲取資源，就可以打破死鎖了。

樂觀鎖，悲觀鎖#

悲觀鎖認為多線程同時修改共享資源的概率比較高，因此很容易出現衝突，所以訪問共享資源前，先要上鎖。

樂觀鎖假定衝突的概率很低，它的工作方式是：先修改完共享資源，再驗證這段時間內有沒有發生衝突，如果沒有其他線程在修改資源，那麼操作完成，如果發現有其他線程已經修改過這個資源，就放棄本次操作。
場景例子：在線文檔：
實現多人同時編輯，實際上是用了樂觀鎖，它允許多個用戶打開同一文檔進行編輯，編輯完提交之後才驗證修改的內容是否有衝突。

怎麼樣才算發生衝突？這裡舉個例子，比如用戶 A 先在瀏覽器編輯文檔，之後用戶 B 在瀏覽器也打開了相同的文檔進行編輯，但是用戶 B 比用戶 A 提交早，這一過程用戶 A 是不知道的，當 A 提交修改完的內容時，那麼 A 和 B 之間並行修改的地方就會發生衝突。

服務端要怎麼驗證是否衝突了呢？通常方案如下：

由於發生衝突的概率比較低，所以先讓用戶編輯文檔，但是瀏覽器在下載文檔時會記錄下服務端返回的文檔版本號；
當用戶提交修改時，發給服務端的請求會帶上原始文檔版本號，伺服器收到後將它與當前版本號進行比較，如果版本號不一致則提交失敗，如果版本號一致則修改成功，然後服務端版本號更新到最新的版本號。
實際上，我們常見的 SVN 和 Git 也是用了樂觀鎖的思想，先讓用戶編輯代碼，然後提交的時候，通過版本號來判斷是否產生了衝突，發生了衝突的地方，需要我們自己修改後，再重新提交。

樂觀鎖雖然去除了加鎖解鎖的操作，但是一旦發生衝突，重試的成本非常高，所以只有在衝突概率非常低，且加鎖成本非常高的場景時，才考慮使用樂觀鎖。