Linux操作系統(tǒng)第七章

第七章內(nèi)核中的同步臨界區(qū)和競(jìng)爭(zhēng)狀態(tài)內(nèi)核同步措施并發(fā)控制什么是臨界區(qū)（criticalregions）?就是訪問和操作共享數(shù)據(jù)的代碼段,這段代碼必須被原子地執(zhí)行什么是競(jìng)爭(zhēng)狀態(tài)?多個(gè)內(nèi)核任務(wù)同時(shí)訪問同一臨界區(qū)什么是同步?避免并發(fā)和防止競(jìng)爭(zhēng)狀態(tài)稱為同步（synchronization）

<>7.1臨界區(qū)和競(jìng)爭(zhēng)狀態(tài)考慮一個(gè)非常簡(jiǎn)單的共享資源的例子：一個(gè)全局整型變量和一個(gè)簡(jiǎn)單的臨界區(qū)，其中的操作僅僅是將整型變量的值增加1：

i++

該操作可以轉(zhuǎn)化成下面三條機(jī)器指令序列：(1)得到當(dāng)前變量i的值并拷貝到一個(gè)寄存器中(2)將寄存器中的值加1(3)把i的新值寫回到內(nèi)存中

<>臨界區(qū)舉例內(nèi)核任務(wù)1內(nèi)核任務(wù)2獲得i(1)---增加i(1->2)---寫回i(2)---

獲得i(2)

增加i(2->3)

寫回i(3)<>臨界區(qū)舉例內(nèi)核任務(wù)1內(nèi)核任務(wù)2獲得i(1)------獲得i(1)

增加i(1->2)------增加i(1->2)

寫回i(2)------寫回i(2)

可能的實(shí)際執(zhí)行結(jié)果：期望的結(jié)果同步進(jìn)程之間的一種通信方式，有時(shí)序上的制約關(guān)系，或者說是進(jìn)程之間為了協(xié)同工作而存在的一種等待關(guān)系?；コ膺M(jìn)程之間對(duì)臨界資源的一種競(jìng)爭(zhēng)關(guān)系，排他性地對(duì)資源的訪問方式。同步與互斥

當(dāng)共享資源是一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)時(shí)，競(jìng)爭(zhēng)狀態(tài)往往會(huì)使該數(shù)據(jù)結(jié)構(gòu)遭到破壞。

對(duì)于這種情況，鎖機(jī)制可以避免競(jìng)爭(zhēng)狀態(tài)正如門鎖和門一樣，門后的房間可想象成一個(gè)臨界區(qū)。

在一個(gè)指定時(shí)間內(nèi)，房間里只能有個(gè)一個(gè)內(nèi)核任務(wù)存在，當(dāng)一個(gè)任務(wù)進(jìn)入房間后，它會(huì)鎖住身后的房門；當(dāng)它結(jié)束對(duì)共享數(shù)據(jù)的操作后，就會(huì)走出房間，打開門鎖。如果另一個(gè)任務(wù)在房門上鎖時(shí)來(lái)了,那么它就必須等待房間內(nèi)的任務(wù)出來(lái)并打開門鎖后，才能進(jìn)入房間。

<>共享隊(duì)列和加鎖任何要訪問隊(duì)列的代碼首先都需要占住相應(yīng)的鎖，這樣該鎖就能阻止來(lái)自其它內(nèi)核任務(wù)的并發(fā)訪問：

<>任務(wù)1

試圖鎖定隊(duì)列成功：獲得鎖訪問隊(duì)列…為隊(duì)列解除鎖…任務(wù)2試圖鎖定隊(duì)列失?。旱却却却晒Γ韩@得鎖

訪問隊(duì)列…

為隊(duì)列解除鎖共享隊(duì)列和加鎖

找出哪些數(shù)據(jù)需要保護(hù)是關(guān)鍵所在

內(nèi)核任務(wù)的局部數(shù)據(jù)僅僅被它本身訪問，顯然不需要保護(hù)

如果數(shù)據(jù)只會(huì)被特定的進(jìn)程訪問，也不需加鎖

大多數(shù)內(nèi)核數(shù)據(jù)結(jié)構(gòu)都需要加鎖：若有其它內(nèi)核任務(wù)可以訪問這些數(shù)據(jù)，那么就給這些數(shù)據(jù)加上某種形式的鎖；若任何其它東西能看到它，那么就要鎖住它

<>確定保護(hù)對(duì)象

死鎖產(chǎn)生的條件：有一個(gè)或多個(gè)并發(fā)執(zhí)行的內(nèi)核任務(wù)和一個(gè)或多個(gè)資源，每個(gè)任務(wù)都在等待其中的一個(gè)資源，但所有的資源都已經(jīng)被占用。所有任務(wù)都在相互等待，但它們永遠(yuǎn)不會(huì)釋放已經(jīng)占有的資源，于是任何任務(wù)都無(wú)法繼續(xù)。

典型的死鎖：

四路交通堵塞

自死鎖：一個(gè)執(zhí)行任務(wù)試圖去獲得一個(gè)自己已經(jīng)持有的鎖

<>死鎖

加鎖的順序是關(guān)鍵。使用嵌套的鎖時(shí)必須保證以相同的順序獲取鎖，這樣可以阻止致命擁抱類型的死鎖

防止發(fā)生饑餓

不要重復(fù)請(qǐng)求同一個(gè)鎖。

越復(fù)雜的加鎖方案越有可能造成死鎖，因此設(shè)計(jì)應(yīng)力求簡(jiǎn)單

<>死鎖的避免

中斷——中斷幾乎可以在任何時(shí)刻異步發(fā)生，也可能隨時(shí)打斷正在執(zhí)行的代碼。

內(nèi)核搶占——若內(nèi)核具有搶占性，內(nèi)核中的任務(wù)就可能會(huì)被另一任務(wù)搶占。

睡眠及與用戶空間的同步——在內(nèi)核執(zhí)行的進(jìn)程可能會(huì)睡眠，這將喚醒調(diào)度程序，導(dǎo)致調(diào)度一個(gè)新的用戶進(jìn)程執(zhí)行。

對(duì)稱多處理——兩個(gè)或多個(gè)處理器可以同時(shí)執(zhí)行代碼。<>并發(fā)執(zhí)行的原因

為了避免并發(fā)，防止競(jìng)爭(zhēng)。內(nèi)核提供了一組同步方法來(lái)提供對(duì)共享數(shù)據(jù)的保護(hù)

原子操作自旋鎖信號(hào)量

<>7.2內(nèi)核同步措施

原子操作可以保證指令以原子的方式被執(zhí)行。

兩個(gè)原子操作絕對(duì)不可能并發(fā)地訪問同一個(gè)變量。

Linux內(nèi)核提供了一個(gè)專門的atomic_t類型（一個(gè)24位原子訪問計(jì)數(shù)器）和一些專門的函數(shù)，這些函數(shù)作用于atomic_t類型的變量。

<>原子操作Linux中的原子操作，見表7.1。例子：atomic_tv=ATOMIC_INIT(0)；atomic_set(&v,4);atomic_add(2,&v);atomic_inc(&v);printk(“%d\n”,atomic_read(&v));打印結(jié)果為7。原子操作Why？大部分同步方案均采用某個(gè)物理實(shí)體（如鎖、信號(hào)燈等）實(shí)現(xiàn)通信，進(jìn)程通信原語(yǔ)中關(guān)鎖（lock）和開鎖（unlock）是最簡(jiǎn)單的原語(yǔ)。在這兩個(gè)原語(yǔ)中設(shè)置一個(gè)公共變量x代表某個(gè)臨界資源的狀態(tài)。如：x=0，表示資源可用，x=1，表示資源正在使用。關(guān)鎖原語(yǔ)1ock（x）：

L：ifx＝1thengotoLelsex：=1；開鎖原語(yǔ)unlock（x）：

x：=0；此兩步之間，X值不能被其他進(jìn)程所改變lock和unlock開鎖和關(guān)鎖程序流程圖

自旋鎖是專為防止多處理器并發(fā)而引入的一種鎖，它在內(nèi)核中大量應(yīng)用于中斷處理等部分，而對(duì)于單處理器來(lái)說，可簡(jiǎn)單采用關(guān)閉中斷的方式防止中斷處理程序的并發(fā)執(zhí)行。

自旋鎖最多只能被一個(gè)內(nèi)核任務(wù)持有，若一個(gè)內(nèi)核任務(wù)試圖請(qǐng)求一個(gè)已被持有的自旋鎖，那么這個(gè)任務(wù)就會(huì)一直進(jìn)行忙循環(huán)，也就是旋轉(zhuǎn)，等待鎖重新可用。<>自旋鎖

設(shè)計(jì)自旋鎖的初衷是在短期間內(nèi)進(jìn)行輕量級(jí)的鎖定。一個(gè)被持有的自旋鎖使得請(qǐng)求它的任務(wù)在等待鎖重新可用期間進(jìn)行自旋，所以自旋鎖不應(yīng)該被持有時(shí)間過長(zhǎng)。

自旋鎖在內(nèi)核中主要用來(lái)防止多處理器中并發(fā)訪問臨界區(qū)，防止內(nèi)核搶占造成的競(jìng)爭(zhēng)。

自旋鎖不允許任務(wù)睡眠，持有自旋鎖的任務(wù)睡眠會(huì)造成自死鎖，因此自旋鎖能夠在中斷上下文中使用。<>自旋鎖定義：typedef

struct{volatileunsignedintlock;}spinlock_t;自旋鎖的使用：spinlock_t

mr_lock=SPIN_LOCK_UNLOCKED;spin_lock(&mr_lock);/*臨界區(qū)*/spin_unlock(&mr_lock);自旋鎖在內(nèi)核中有許多變種。自旋鎖信號(hào)量：僅能由P、V操作修改的整型變量。整型值S隊(duì)列指針Next信號(hào)量P操作：申請(qǐng)資源操作(1)

S:=S-1；(2)

如果S≥0，則表示有資源，該進(jìn)程繼續(xù)執(zhí)行；如果S<0，則表示已無(wú)資源，執(zhí)行原語(yǔ)的進(jìn)程被置成阻塞狀態(tài)，并使其在S信號(hào)量的隊(duì)列中等待，直至其他進(jìn)程在S上執(zhí)行V操作釋放它為止。

P操作V操作V操作：釋放資源操作(1)

S:=S+1；(2)

如果S>0，則該進(jìn)程繼續(xù)執(zhí)行；如果S≤0，則釋放S信號(hào)量隊(duì)列的排頭等待者并清除其阻塞狀態(tài)，即從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行V(S)者繼續(xù)執(zhí)行。

信號(hào)量機(jī)制的應(yīng)用1。解決互斥問題2。解決同步問題解決互斥問題用信號(hào)量解決幾個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)的問題，幾個(gè)進(jìn)程共享一個(gè)公用信號(hào)量S（互斥信號(hào)量）。每個(gè)進(jìn)程進(jìn)入臨界區(qū)必須先執(zhí)行P（S），退出臨界區(qū)后執(zhí)行V（S）。P（S）V（S）臨界區(qū)

舉例：有1臺(tái)打印機(jī)，兩個(gè)并發(fā)執(zhí)行進(jìn)程p1、p2.求采用記錄型信號(hào)量機(jī)制，如何解決p1、p2互斥訪問打印機(jī)的問題。解決同步問題ICbuf設(shè)立與資源相關(guān)的私有信號(hào)量（資源信號(hào)量）。設(shè)緩沖區(qū)只有一個(gè)緩沖單元Empty=1表示空單元個(gè)數(shù)。Full=0表示裝滿信息的單元個(gè)數(shù)。IP(empty)V(full)P(full)V(empty)C放數(shù)據(jù)取數(shù)據(jù)經(jīng)典的同步/互斥問題生產(chǎn)者與消費(fèi)者生產(chǎn)者與消費(fèi)者問題

Dijkstra把廣義同步問題抽象成一種“生產(chǎn)者與消費(fèi)者問題”（Producer-consumer-relationship）的抽象模型。事實(shí)上，計(jì)算機(jī)系統(tǒng)中的許多問題都可歸結(jié)為生產(chǎn)者與消費(fèi)者問題，生產(chǎn)者與消費(fèi)者可以通過一個(gè)環(huán)形緩沖池（見圖）聯(lián)系起來(lái)，環(huán)形緩沖池由幾個(gè)大小相等的緩沖塊組成，每個(gè)緩沖塊容納一個(gè)產(chǎn)品。每個(gè)生產(chǎn)者可不斷地每次往緩沖池中送一個(gè)生產(chǎn)產(chǎn)品，而每個(gè)消費(fèi)者則可不斷地每次從緩沖池中取出一個(gè)產(chǎn)品。

圖環(huán)形緩沖池生產(chǎn)者進(jìn)程臨界資源消費(fèi)者進(jìn)程下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費(fèi)者關(guān)系的形式描述，設(shè)：（1）公用信號(hào)量mutex：初值為1，用于實(shí)現(xiàn)臨界區(qū)互斥。（2）生產(chǎn)者私用信號(hào)量empty：初值為n，指示空緩沖塊數(shù)目。（3）消費(fèi)者私用信號(hào)量full：初值為0，指示滿緩沖塊數(shù)目。（4）整型量i和j初值均為0，i指示首空緩沖塊序號(hào)，j指示首滿緩沖塊序號(hào)。模塊設(shè)計(jì)如下：

生產(chǎn)者/消費(fèi)者算法描述varmutex，empty，full：psemaphore；i,j，goods：integer；buffer：array[0…n-1]ofitem；procedureproducer；生產(chǎn)者進(jìn)程beginwhiletruedobeginproducenextproduct；

P(empty)；

P(mutex)；buffer(i):=product；i:=(i+1)mod(n)；

V(mutex)；

V(full)；endend；滿空ij圖3-8環(huán)形緩沖區(qū)procedureconsumer；消費(fèi)者進(jìn)程

beginwhiletruedobegin

P(full)；

P(mutex)；

goods：=buffer(j)；

j:=(j+1)mod(n)；

V(mutex)；

V(empty)；

consumeproduct；

endend；生產(chǎn)者/消費(fèi)者算法描述beginseminitial(mutex.v，1；empty.v，n；full.v，0)；i：=j：=0；cobeginproducer；consumer；coendend注意1．每個(gè)程序中實(shí)現(xiàn)互斥的P(mutex),V(mutex)必須成對(duì)出現(xiàn)。2．Empty和full的P，V操作也必須成對(duì)出現(xiàn)，但它們處于不同的程序中。3.每個(gè)程序中的多個(gè)P操作不能顛倒順序，否則可能引起死鎖。

Linux中的信號(hào)量是一種睡眠鎖。若有一個(gè)任務(wù)試圖獲得一個(gè)已被持有的信號(hào)量時(shí)，信號(hào)量會(huì)將其推入等待隊(duì)列，然后讓其睡眠。這時(shí)處理器獲得自由而去執(zhí)行其它代碼。當(dāng)持有信號(hào)量的進(jìn)程將信號(hào)量釋放后，在等待隊(duì)列中的一個(gè)任務(wù)將被喚醒，從而便可以獲得這個(gè)信號(hào)量。

信號(hào)量具有睡眠特性，適用于鎖會(huì)被長(zhǎng)時(shí)間持有的情況，只能在進(jìn)程上下文中使用。<>信號(hào)量信號(hào)量的使用<>信號(hào)量的定義structsemaphore{

atomic_tcount;

intsleepers;

wait_queue_head_twait;

}

staticDECL