Windows XP Windows 7 Windows 2003 Windows Vista Windows教程綜合 Linux 系統教程
Windows 10 Windows 8 Windows 2008 Windows NT Windows Server 電腦軟件教程
 Windows教程網 >> Linux系統教程 >> Linux系統常見問題解答 >> Linux內核設計與實現——內核同步

Linux內核設計與實現——內核同步

日期:2017/1/20 17:40:42      編輯:Linux系統常見問題解答

內核同步

同步介紹

同步的概念

臨界區:也稱為臨界段,就是訪問和操作共享數據的代碼段。

競爭條件: 2個或2個以上線程在臨界區裡同時執行的時候,就構成了競爭條件。

所謂同步,其實防止在臨界區中形成競爭條件。

如果臨界區裡是原子操作(即整個操作完成前不會被打斷),那麼自然就不會出競爭條件。但在實際應用中,臨界區中的代碼往往不會那麼簡單,所以為了保持同步,引入了鎖機制。但又會產生一些關於鎖的問題。

死鎖產生的條件:要有一個或多個執行線程和一個或多個資源,每個線程都在等待其中的一個資源,但所有資源都已被占用。所以線程相互等待,但它們永遠不會釋放已經占有的資源。於是任何線程都無法繼續,死鎖發生。

自死鎖:如果一個執行線程試圖去獲得一個自己已經持有的鎖,它不得不等待鎖被釋放。但因為它正在忙著等待這個鎖,所以自己永遠也不會有機會釋放鎖,死鎖產生。

饑餓(starvation) 是一個線程長時間得不到需要的資源而不能執行的現象。

造成並發的原因

中斷——中斷幾乎可以在任何時刻異步發生,也就是可能隨時打斷當前正在運行的代碼。

軟中斷和tasklet ——內核能在任何時刻喚醒或調度中斷和tasklet,打斷當前正在執行的代碼。

內核搶占——因為內核具有搶占性,所以內核中的任務可能會被另一任務搶占。

睡眠及用戶空間的同步——在內核執行的進程可能會睡眠,這就會喚醒調度程序從而導致調度一個新的用戶進程執行。

對稱多處理——兩個或多個處理器可以同時執行代碼。

避免死鎖的簡單規則

加鎖的順序是關鍵。使用嵌套的鎖時必須保證以相同的順序獲取鎖,這樣可以阻止致命擁抱類型的死鎖。最好能記錄下鎖的順序,以便其他人能照此順序使用。

防止發生饑餓。判斷這個代碼的執行是否會結束。如果A不發生,B要一直等待下去嗎?

不要重復請求同一個鎖。

越復雜的加鎖方案越可能造成死鎖。---設計應力求簡單。

鎖的粒度

加鎖的粒度用來描述加鎖保護的數據規模。一個過粗的鎖保護大塊數據,比如一個子系統的所有數據結構;一個過細的鎖保護小塊數據,比如一個大數據結構中的一個元素。

在加鎖的時候,不僅要避免死鎖,還需要考慮加鎖的粒度。

鎖的粒度對系統的可擴展性有很大影響,在加鎖的時候,要考慮一下這個鎖是否會被多個線程頻繁的爭用。

如果鎖有可能會被頻繁爭用,就需要將鎖的粒度細化。

細化後的鎖在多處理器的情況下,性能會有所提升。

同步方法

原子操作

原子操作指的是在執行過程中不會被別的代碼路徑所中斷的操作,內核代碼可以安全的調用它們而不被打斷。

原子操作分為整型原子操作和位原子操作。

spinlock自旋鎖

自旋鎖的特點就是當一個線程獲取了鎖之後,其他試圖獲取這個鎖的線程一直在循環等待獲取這個鎖,直至鎖重新可用。

由於線程實在一直循環的獲取這個鎖,所以會造成CPU處理時間的浪費,因此最好將自旋鎖用於能很快處理完的臨界區。

自旋鎖使用時有2點需要注意:

1.自旋鎖是不可遞歸的,遞歸的請求同一個自旋鎖會自己鎖死自己。

2.線程獲取自旋鎖之前,要禁止當前處理器上的中斷。(防止獲取鎖的線程和中斷形成競爭條件)比如:當前線程獲取自旋鎖後,在臨界區中被中斷處理程序打斷,中斷處理程序正好也要獲取這個鎖,於是中斷處理程序會等待當前線程釋放鎖,而當前線程也在等待中斷執行完後再執行臨界區和釋放鎖的代碼。

中斷處理下半部的操作中使用自旋鎖尤其需要小心:

1. 下半部處理和進程上下文共享數據時,由於下半部的處理可以搶占進程上下文的代碼,所以進程上下文在對共享數據加鎖前要禁止下半部的執行,解鎖時再允許下半部的執行。

2. 中斷處理程序(上半部)和下半部處理共享數據時,由於中斷處理(上半部)可以搶占下半部的執行,所以下半部在對共享數據加鎖前要禁止中斷處理(上半部),解鎖時再允許中斷的執行。

3. 同一種tasklet不能同時運行,所以同類tasklet中的共享數據不需要保護。

4. 不同類tasklet中共享數據時,其中一個tasklet獲得鎖後,不用禁止其他tasklet的執行,因為同一個處理器上不會有tasklet相互搶占的情況

5. 同類型或者非同類型的軟中斷在共享數據時,也不用禁止下半部,因為同一個處理器上不會有軟中斷互相搶占的情況

讀-寫自旋鎖

如果臨界區保護的數據是可讀可寫的,那麼只要沒有寫操作,對於讀是可以支持並發操作的。對於這種只要求寫操作是互斥的需求,如果還是使用自旋鎖顯然是無法滿足這個要求(對於讀操作實在是太浪費了)。為此內核提供了另一種鎖-讀寫自旋鎖,讀自旋鎖也叫共享自旋鎖,寫自旋鎖也叫排他自旋鎖。

讀寫自旋鎖是一種比自旋鎖粒度更小的鎖機制,它保留了“自旋”的概念,但是在寫操作方面,只能最多有一個寫進程,在讀操作方面,同時可以有多個讀執行單元,當然,讀和寫也不能同時進行。

自旋鎖提供了一種快速簡單的所得實現方法。如果加鎖時間不長並且代碼不會睡眠,利用自旋鎖是最佳選擇。如果加鎖時間可能很長或者代碼在持有鎖時有可能睡眠,那麼最好使用信號量來完成加鎖功能。

信號量

Linux中的信號量是一種睡眠鎖,如果有一個任務試圖獲得一個已經被占用的信號量時,信號量會將其推進一個等待隊列,然後讓其睡眠,這時處理器能重獲自由,從而去執行其它代碼,當持有信號量的進程將信號量釋放後,處於等待隊列中的哪個任務被喚醒,並獲得該信號量。

1)由於爭用信號量的過程在等待鎖重新變為可用時會睡眠,所以信號量適用於鎖會被長時間持有的情況;相反,鎖被短時間持有時,使用信號量就不太適宜了。因為睡眠、維護等待隊列以及喚醒所花費的開銷可能比鎖被占用的全部時間還要長。

2)由於執行線程在鎖被爭用時會睡眠,所以只能在進程上下文中才能獲取信號量鎖,因為中斷上下文中是不能進行調度的。
3)你可以在持有信號量時去睡眠,因為當其他進程試圖獲得同一信號量時不會因此而死鎖(因為該進程也只是去睡眠而已,最終會繼續執行的)。

4)在你占用信號量的同時不能占用自旋鎖。因為在你等待信號量時可能會睡眠,而在持有自旋鎖時是不允許睡眠的。

5)信號量同時允許任意數量的鎖持有者,而自旋鎖在一個時刻最多允許一個任務持有它。原因是信號量有個計數值,比如計數值為5,表示同時可以有5個線程訪問臨界區。如果信號量的初始值始1,這信號量就是互斥信號量(MUTEX)。對於大於1的非0值信號量,也可稱為計數信號量(counting semaphore)。對於一般的驅動程序使用的信號量都是互斥信號量。

信號量支持兩個原子操作:P/V原語操作(也有叫做down操作和up操作的):

P:如果信號量值大於0,則遞減信號量的值,程序繼續執行,否則,睡眠等待信號量大於0。

V:遞增信號量的值,如果遞增的信號量的值大於0,則喚醒等待的進程。

down操作有兩個版本,分別對於睡眠可中斷和睡眠不可中斷。

讀-寫信號量

讀寫信號量和信號量之間的關系 與 讀寫自旋鎖和普通自旋鎖之間的關系 差不多。

Copyright © Windows教程網 All Rights Reserved