文章目錄

• • 4.1 什么是并發
  • 4.2 互斥的實現
  • 4.3 硬件互斥
  • • 4.3.1 中斷禁用
    • 4.3.2 專用機器指令
    • • 4.3.2.1 比較交換指令
      • 4.3.2.2 exchange指令
      • 4.3.3 使用機器指令完成互斥
  • 4.4 操作系統層面的軟件互斥
  • • 4.4.1 信號量
    • 4.4.2 二元信號量
    • 4.4.3 信號量的強弱
    • 4.4.4 信號量的實現
    • 4.4.4 管程
    • • 4.4.4.1 管程的定義
      • 4.4.4.2 管程的組成
  • 4.5 linux 內核并發機制
  • • 4.5.1 原子操作
    • 4.5.2 自旋鎖
    • 4.5.3 信號量
    • 4.5.4 屏障
    • 4.5.5 信號處理
    • • 4.5.5.1 信號的定義
      • 4.5.5.2 信號的傳遞和響應機制
      • 4.5.5.3 信號的產生

4.1 什么是并發

多個進程、線程對共享資源的操作構成了并發問題。并發問題使程序不能得到和單進程執行一樣的預期的結果。
與并發相關的術語：

原子操作：一個函數或者動作由一個或者多個指令序列實現，對外是不可見的。也就是說沒有其他進程可以看到中間狀態，或者能夠中斷此操作。要么都執行要不都不執行。原子性保證了進程的隔離。

臨界區：一段代碼，在這段代碼中將訪問共享資源，每次只能有一個進程進入臨界區

死鎖：兩個或以上的進程因為等待彼此完成一些任務陷入停滯

活鎖：兩個或以上的進程為影響其他進程而持續改變自己的狀態但是不做有用功的工作情形

互斥：當一個進程在臨界區工作，其他進程不能進入臨界區的情形

競爭條件：多個線程或進程在讀寫一個共享數據時，結果依賴于他們執行的相對時間的情形

饑餓：一個進程盡管可以運行，但是調度被無限延遲的情況

4.2 互斥的實現

互斥的實現有三種，

用戶程序層面，

硬件層面，

操作系統層面

??如果都放在用戶程序層面來實現的話用戶程序就會變得特別復雜。所以一般都是在操作系統層面實現，有些時候也可以在用戶程序中使用機器指令(硬件層面)來實現。比如java的AQS鎖。

4.3 硬件互斥

4.3.1 中斷禁用

??在單核處理器中，并發進程不能重疊，所以可以使用中斷禁用的方式在進程進入臨界區之前禁用中斷，這樣該進程就不會被調度出去，臨界區的訪問就變成了原子性的。但是缺點也很明顯，不支持多處理器，現在基本沒法單獨使用。

4.3.2 專用機器指令

??在硬件級別上，一個對存儲器單元的訪問排斥其他對該單元的訪問，因此設計了一些處理器指令，用于保證兩個動作的原子性。如，在一個取指令周期中對一個存儲器讀和寫或者讀和測試。這里介紹兩個。

比較交換指令

exchange指令

4.3.2.1 比較交換指令

bool compareAndSwap(int *word, int testval, int newval) {int oldval;oldval=*word;if (oldval==testval){*word=newval;return oldval} }

在進入臨界區之前執行這個，假如成功進入臨界區后再進行置位

4.3.2.2 exchange指令

這個用的更少一些

void exchange (int *register, int *memory) { int temp; temp =*memory; *memory = *register; *register =temp; }

4.3.3 使用機器指令完成互斥

1.使用比較和交換指令

/* program mutualexclusion */ const int n-*進程個數*1 int bolt; bolt= 0; void P(int i){while (true) {while (compare and swap (bolt, 0, 1) == 1)/*不做任何事*//*臨界區/bolt=0;/*其余部分*/} }void main() {bolt=0;parbegin (P(1), P(2), ... P(n)); }

2.交換指令

/* program mutualexclusion */ int const n=*進程個數**; int bolt; void P(int i) {while (true) {int keyi = 1;do exchange (keyi, bolt)while (keyi !=0);/*臨界區*/bolt=0;/*其余部分*/} } void main() {bolt=0;parbegin (P(1), P(2), ... P(n)); }

4.4 操作系統層面的軟件互斥

操作系統層面的互斥一般常見的有三種

信號量

二元信號量

管程

4.4.1 信號量

信號量可以被初始化為一個非負數,若為正數，則等于發出semWait后可以繼續執行的進程數

semWait 操作使信號量減1，若值編程負數，則阻塞執行semWait的進程，否則調用進程繼續執行

semSignal 操作使信號加1，若值小于等于零，則被semWait操作的阻塞的其中一個進程將被解除阻塞
除了這三個操作，沒有其他任何方法可以檢查或者操作信號量

struct semaphore {int count; queueType queue; }; void semWait(semaphore s) { s.count--; if (s.count < 0) {/*把當前進程插入隊列*/;/*阻塞當前進程*/; } void semSignal(semaphore s) s.count++; if (s.count <= 0) { /*把進程p從隊列中移除*/;/*把進程p插入就緒隊列*/ }

4.4.2 二元信號量

二元信號量相對于普通信號量來說值只能是0/1

一元信號量可以初始化為0或者1

semWaitB將檢查信號量的值，若為0，則進程執行semWaitB就會受阻。若值為1，則將值改為0，當前進程繼續執行

semSignalB操作檢查是否有任何進程在該信號上面受阻。若有進程受阻，則喚醒所有的受阻進程，若沒有進程受阻，則置為1

4.4.3 信號量的強弱

阻塞在信號量上的進程會被放在特定的隊列中，進程應該按照什么順序從隊列中移出，如果是FIFO就是強信號量，否則是弱信號量。

4.4.4 信號量的實現

??我原來以為像這種上層的互斥實現都必須依賴硬件層面的原子操作來實現，實際上不是的，互斥僅僅通過用戶軟件也是可以實現的。比如Dekker算法或者Peterson算法，當然這些也會已有些處理開銷。
當然很多時候還是會選擇操作系統提供的互斥，因為開銷更小，比如基于compareAndSwap的實現信號量。
cas返回的是舊的內存值。

seaWait(s) {while (compare and swap(s.flag, 0 , 1)==1)/*不iT任何事*/;s.count--;if (s.count < 0) {/*該進程進入s.queue隊列*/;/*阻塞該進裎（還將s.flag設置為0)*/;s.flag = 0;}semSignal (s) {while (compare and swap(s.flag,0,1)==1)/*不做任何亊*/;s.count++;if(s.count<=0){/*從s.queue 隊列中移出進程p*//*進程P進入就緒隊列*/}i.flag=0; }

4.4.4 管程

??管程是一種程序設計語言結構，他提供的功能與信號量相同，但是更容易控制，因為他代表了一個操作的順序集合。在管程的發展史上，先后出現過三種不同的管程模型，分別是：Hasen 模型、Hoare 模型和 MESA模型。其中，現在廣泛應用的是 MESA 模型，并且 Java 管程的實現參考的也是 MESA 模型。
這里也主要介紹MESA模型。

4.4.4.1 管程的定義

管程是這樣定義的：
管程是由一個或者多個過程，一個初始化序列和局部數據組成的軟件模塊，其主要特點有：

局部數據變量只能被管程的過程訪問，任何外部過程都不能訪問

一個進程通過調用管程的一個過程進入管程

在任何時候，只能有一個進程在管程中執行，調用管程的任何其他進程都被阻塞，以等待管程可用。

正在管程中的線程可臨時放棄管程的互斥訪問，等待事件出現時恢復（這是最大的特點）

4.4.4.2 管程的組成

一個鎖：控制管程代碼的互斥訪問

入口隊列：每次只能有一個線程進入

0或多個條件變量：管理共享數據的并發訪問

條件變量
條件變量是管程內的等待和并發機制
這些條件變量包含在管程中，只有通過管程才能訪問。

• 進入管程的線程因資源被占用而進入等待狀態
• 每個條件變量表示一種等待原因，對應一個等待隊列

對條件變量可以有三種操作

1.wait(x)操作：
將自己阻塞在條件x等待隊列中,隨后醒來的時候需要重新進入管程,接著執行wait()后面的代碼
即允許另外一個線程進入管程

2.notify()操作：
將等待隊列中的一個線程喚醒
如果等待隊列為空，這就相當于是一個空操作,這個是和計數信號量的一個最大的區別

3.notifyAll()操作：
將阻塞在這個條件上的線程全部喚醒

4.5 linux 內核并發機制

4.5.1 原子操作

linux提供了很多保證對變量的原子操作的方式。這些操作可以用來避免簡單的競爭條件，比如原子加一減一等，cas等

4.5.2 自旋鎖

在同一時刻，只能有一個線程能夠獲得自旋鎖，其他線程都要自旋等待。因為線程使用的是忙等待的方式，適合等待時間比較短的情況，如果在自旋的時候就拿到了鎖，那么就不用進行上下文切換了，比較高效。

4.5.3 信號量

linux在用戶級提供了和UNIX SVR4(就是前面介紹的,又增加了一些拓展)
linux內核內部還提供了一些信號量，不能直接被用戶調用，下面就是這些信號量
linux提供了二元信號量和計數信號量，以及讀寫信號量。
二元信號量在linux中也被稱為MUTEX(互斥信號量)，

4.5.4 屏障

為了禁止指令重排序，linux提供了內存屏障的設置
內存屏障主要有：讀屏障、寫屏障、通用屏障、優化屏障幾種。

操作含義

rmb()	阻止跨過屏障對裝載操作重排序,保證rmb()之前的代碼沒有任何讀操作會穿越屏障，rmb()之后的任何讀操作也不會穿越屏障
wmb()	阻止跨過屏障對存儲操作重排序，保證wmb()之前的任何寫操作不會穿越屏障，wmb()之后的任何寫操作也不會穿越屏障
mb()	阻止跨過屏障對裝載存儲操作重排序，mb()=rmb()+wmb()
barrier()	阻止編譯器跨過屏障對裝載存儲操作重排序，在知道處理器不會對程序重排序的時候有用
smp_rmb()	在SMIP上提供rmb(1)操作，在UP上提供barrier ()操作
smp_wmb()	在SMP上提供wmb(1)操作，在UP上提供barrier()操作
smp_mb	在SMP上提供mb()操作，在UP上提供barrier()操作

其實就是通過這里來對指令重排序來做干預的，也就是說內存屏障和指令重排序是一回事兒。
而且隱含的屏障其實又很多，幾乎所有加鎖的地方都隱含了屏障。
這里對內存屏障有比較詳細的介紹

4.5.5 信號處理

這里的信號不是指上面的信號量的意思，是指操作系統中常見的一個進程給另一個進程發信號的情況。
比如linux中可能最常用的還是kill -9 pid這種。

4.5.5.1 信號的定義

??信號是用于向一個進程通知發生異步事件的機制。信號類似于硬件中斷,但沒有優先級,即內
核公平地對待所有信號。對于同時發生的信號,一次只給進程一個信號,而沒有特定的次序。
進程間可以互相發送信號,內核也可在內部發送信號。

4.5.5.2 信號的傳遞和響應機制

傳遞機制：信號的傳遞是通過修改信號要發送到的進程所對應的進程表中的一個域來完成的。由于每個信號只保存為一位,因此不能對給定類型的信號進行排隊。

響應機制：因為要干預原來的進程執行的流程，所以只有在進程被喚醒繼續運行時,或進程準備從系統調用中返回時,才處理信號。進程可通過執行某些默認行為(如終止進程)、執行一個信號處理函數或忽略該信號來對信號做出響應。參考這里有更詳細的介紹。

4.5.5.3 信號的產生

1 硬件方式
用戶輸入：比如在終端上按下組合鍵ctrl+C，產生SIGINT信號；
硬件異常：CPU檢測到內存非法訪問等異常，通知內核生成相應信號，并發送給發生事件的進程；
2 軟件方式
通過系統調用，發送signal信號：kill()，raise()，sigqueue()，alarm()，setitimer()，abort()
kernel,使用 kill_proc_info(）等
java,使用 Procees.sendSignal()等

關于信號分類等可以參考這里

可以看看這本書的信號量，互斥的介紹
https://book.douban.com/subject/24530911/

總結

以上是生活随笔為你收集整理的04.并发和互斥.md的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。