操作系統(tǒng)第2章進(jìn)程的描述與控制(下)

第二章進(jìn)程的描述與控制前趨圖和程序執(zhí)行進(jìn)程的描述2進(jìn)程控制33進(jìn)程同步44經(jīng)典進(jìn)程的同步問題3535142023/2/11進(jìn)程通信44線程(Threads)的基本概念3576線程的實現(xiàn)4482023/2/122.5經(jīng)典進(jìn)程的同步問題2.5.1生產(chǎn)者—消費者問題

1．利用記錄型信號量解決生產(chǎn)者—消費者問題假定在生產(chǎn)者和消費者之間的公用緩沖池中，具有n個緩沖區(qū)，這時可利用互斥信號量mutex實現(xiàn)諸進(jìn)程對緩沖池的互斥使用。利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產(chǎn)者—消費者問題可描述如下:P60

2023/2/13intmutex=1，empty=n，full=0；

arraybuffer[0，…，n-1]；

intin=0，out=0；

begin

parbegin

proceducer:begin

repeat

…2023/2/14 produceranitemnextp；

……

wait(empty)；

wait(mutex)；

buffer[in]=nextp；

in=(in+1)%n；

signal(mutex)；

signal(full)；

untilfalse；

end

2023/2/15

consumer:{

wait(full)；

wait(mutex)；

nextc:=buffer(out)；

out=(out+1)%n；

signal(mutex)；

signal(empty)；

consumertheiteminnextc； }

2023/2/16在生產(chǎn)者—消費者問題中應(yīng)注意：首先，在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)；其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計算進(jìn)程中，而signal(empty)則在消費進(jìn)程中，計算進(jìn)程若因執(zhí)行wait(empty)而阻塞，則以后將由消費進(jìn)程將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒，應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。2023/2/17

2．利用AND信號量解決生產(chǎn)者—消費者問題對于生產(chǎn)者—消費者問題，也可利用AND信號量來解決，即用Swait(empty，mutex)來代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)來代替signal(mutex)和signal(full)；用Swait(full，mutex)來代替wait(full)和wait(mutex)，以及用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。利用AND信號量來解決生產(chǎn)者—消費者問題的算法描述如下：2023/2/18intmutex，empty，full:=1，n，0；

buffer:array[0，…，n-1]ofitem；

inout:integer:=0，0；

begin

parbegin

producer:begin

repeat

produceaniteminnextp；

Swait(empty，mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

Ssignal(mutex，full)；

untilfalse；

end……2023/2/19

consumer:begin

repeat

Swait(full，mutex)；

Nextc:=buffer(out)；

Out:=(out+1)modn；

Ssignal(mutex，empty)；

consumertheiteminnextc；

untilfalse；

end

parend

end2023/2/110

3．利用管程解決生產(chǎn)者—消費者問題在利用管程方法來解決生產(chǎn)者—消費者問題時，首先便是為它們建立一個管程，并命名為ProclucerConsumer，或簡稱為PC。其中包括兩個過程：

(1)put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)count≥n時，表示緩沖池已滿，生產(chǎn)者須等待。

(2)get(item)過程。消費者利用該過程從緩沖池中取出一個產(chǎn)品，當(dāng)count≤0時，表示緩沖池中已無可取用的產(chǎn)品，消費者應(yīng)等待。2023/2/111PC管程可描述如下：

typeproducer-consumer=monitor

Varin,out,count:integer；

buffer:array[0,…,n-1]ofitem；

notfull，notempty:condition；

procedureentryput(item)

begin

ifcount>=nthennotfull.wait；

buffer(in):=nextp；

in:=(in+1)modn；

count:=count+1；

ifnotempty.queuethennotempty.signal；

end2023/2/112

procedureentryget(item)

begin

ifcount<=0thennotempty.wait；

nextc:=buffer(out)；

out:=(out+1)modn；

count:=count-1；

ifnotfull.queuethennotfull.signal；

end

beginin:=out:=0；count:=0end2023/2/1132.4.2哲學(xué)家進(jìn)餐問題

1．利用記錄型信號量解決哲學(xué)家進(jìn)餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學(xué)家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組。其描述如下：

Varchopstick:array[0，…，4]ofsemaphore；2023/2/114所有信號量均被初始化為1，第i位哲學(xué)家的活動可描述為：

repeat

wait(chopstick[i])；//左邊

wait(chopstick[(i+1)mod5])；//右邊

eat；

signal(chopstick[i])；

signal(chopstick[(i+1)mod5])；

think；

untilfalse；………2023/2/115在以上描述中，當(dāng)哲學(xué)家饑餓時，總是先去拿他左邊的筷子，即執(zhí)行wait(chopstick[i])；成功后，再去拿他右邊的筷子，即執(zhí)行wait(chopstick[(i+1)mod5])；又成功后便可進(jìn)餐。進(jìn)餐完畢，又先放下他左邊的筷子，然后再放右邊的筷子。雖然，上述解法可保證不會有兩個相鄰的哲學(xué)家同時進(jìn)餐，但有可能引起死鎖。假如五位哲學(xué)家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為0；當(dāng)他們再試圖去拿右邊的筷子時，都將因無筷子可拿而無限期地等待。對于這樣的死鎖問題，可采取以下幾種解決方法：2023/2/116

(1)至多只允許有四位哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。

(2)僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時，才允許他拿起筷子進(jìn)餐。

(3)規(guī)定偶數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子，而奇數(shù)號哲學(xué)家則相反。按此規(guī)定，將是1、2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。2023/2/117

2．利用AND信號量機制解決哲學(xué)家進(jìn)餐問題在哲學(xué)家進(jìn)餐問題中，要求每個哲學(xué)家先獲得兩個臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機制可獲得最簡潔的解法。描述如下：Varchopsiickarrayofsemaphore:=(1,1,1,1,1)；

processi

repeat

think；

Swait(chopstick[(i+1)mod5]，chopstick[i])；

eat；

Ssignal(chopstick[(i+1)mod5]，chopstick[i])；

untilfalse；2023/2/1182.4.3讀者—寫者問題

1．利用記錄型信號量解決讀者—寫者問題為實現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量Wmutex。另外，再設(shè)置一個整型變量Readcount表示正在讀的進(jìn)程數(shù)目。由于只要有一個Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫。因此，僅當(dāng)Readcount=0，表示尚無Reader進(jìn)程在讀時，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作。若Wait(Wmutex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫。又因為Readcount是一個可被多個Reader進(jìn)程訪問的臨界資源，因此，也應(yīng)該為它設(shè)置一個互斥信號量rmutex。2023/2/119讀者—寫者問題可描述如下:

Varrmutex，wmutex:=1,1；

Readcount=0；

Reader:begin

repeat

wait(rmutex)；

ifreadcount==0thenwait(wmutex)；

Readcount:=Readcount+1；

signal(rmutex)；

………..performreadoperation；

wait(rmutex)；

readcount:=readcount-1；

ifreadcount==0thensignal(wmutex)；

signal(rmutex)；

2023/2/120

writer:begin

repeat

wait(wmutex)；

performwriteoperation；

signal(wmutex)；

untilfalse；

end

parend

end…2023/2/12121請給出一個寫者優(yōu)先的“讀者-寫者”問題的算法描述。應(yīng)用題舉例Reader：begin repeat

wait(S);

wait(rmutex); ifreadcount==0 thenwait(wmutex); readcount=readcount+1;

signal(rmutex);

signal(S); performreadoperation;

wait(rmutex); readcount=readcount-1; ifreadcount==0 thensignal(wmutex);

signal(rmutex); untilfalse; end;2023/2/12222writer：begin repeat

wait(mutex); ifwritecount==0 thenwait(S); writecount=writecount+1;

signal(mutex);

wait(wmutex); performwriteoperation;

signal(wmutex);

wait(mutex); writecount=writecount-1; ifwritecount==0 thensignal(S);

signal(mutex); untilfalse; end;應(yīng)用題舉例2023/2/123

2．利用信號量集機制解決讀者—寫者問題這里的讀者—寫者問題與前面的略有不同，它增加了一個限制，即最多只允許RN個讀者同時讀。為此，又引入了一個信號量L，并賦予其初值為RN，通過執(zhí)行wait(L，1，1)操作，來控制讀者的數(shù)目。每當(dāng)有一個讀者進(jìn)入時，就要先執(zhí)行wait(L，1，1)操作，使L的值減1。當(dāng)有RN個讀者進(jìn)入讀后，L便減為0，第RN+1個讀者要進(jìn)入讀時，必然會因wait(L，1，1)操作失敗而阻塞。對利用信號量集來解決讀者—寫者問題的描述如下：2023/2/124VarRNinteger；

L=RN，mx=1；

begin

parbegin

reader:begin

repeat

Swait(L,1,1)；

Swait(mx,1,0)；

performreadoperation；

Ssignal(L,1)；

untilfalse；

end……2023/2/125

writer:begin

repeat

Swait(mx,1,1；L,RN,0)；

performwriteoperation；

Ssignal(mx,1)；

untilfalse；

end

parend

end2023/2/126其中，Swait(mx，1，0)語句起著開關(guān)的作用。只要無writer進(jìn)程進(jìn)入寫，mx=1，reader進(jìn)程就都可以進(jìn)入讀。但只要一旦有writer進(jìn)程進(jìn)入寫時，其mx=0，則任何reader進(jìn)程就都無法進(jìn)入讀。Swait(mx，1，1；L，RN，0)語句表示僅當(dāng)既無writer進(jìn)程在寫(mx=1)，又無reader進(jìn)程在讀(L=RN)時，writer進(jìn)程才能進(jìn)入臨界區(qū)寫。第二章進(jìn)程的描述與控制前趨圖和程序執(zhí)行進(jìn)程的描述2進(jìn)程控制33進(jìn)程同步44經(jīng)典進(jìn)程的同步問題3535142023/2/127進(jìn)程通信44線程(Threads)的基本概念3576線程的實現(xiàn)4482023/2/1282.6進(jìn)程通信信號量機制在通信方面：效率低；通信對用戶不透明。2.6.1進(jìn)程通信的類型

1．共享存儲器系統(tǒng)（Shared-MemorySystem）

(1)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。在這種通信方式中，要求諸進(jìn)程公用某些數(shù)據(jù)結(jié)構(gòu)，借以實現(xiàn)諸進(jìn)程間的信息交換。如在生產(chǎn)者—消費者問題中，就是用有界緩沖區(qū)這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)通信的。這里，公用數(shù)據(jù)結(jié)構(gòu)的設(shè)置及對進(jìn)程間同步的處理，都是程序員的職責(zé)。這無疑增加了程序員的負(fù)擔(dān)，而操作系統(tǒng)卻只須提供共享存儲器。因此，這種通信方式是低效的，只適于傳遞相對少量的數(shù)據(jù)(低級通信)。2023/2/129

(2)基于共享存儲區(qū)的通信方式。為了傳輸大量數(shù)據(jù)，在存儲器中劃出了一塊共享存儲區(qū)，諸進(jìn)程可通過對共享存儲區(qū)中數(shù)據(jù)的讀或?qū)憗韺崿F(xiàn)通信。這種通信方式屬于高級通信。進(jìn)程在通信前，先向系統(tǒng)申請獲得共享存儲區(qū)中的一個分區(qū)，并指定該分區(qū)的關(guān)鍵字；若系統(tǒng)已經(jīng)給其他進(jìn)程分配了這樣的分區(qū)，則將該分區(qū)的描述符返回給申請者，繼之，由申請者把獲得的共享存儲分區(qū)連接到本進(jìn)程上；此后，便可像讀、寫普通存儲器一樣地讀、寫該公用存儲分區(qū)。2023/2/130

2．管道通信所謂“管道”，是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實現(xiàn)它們之間通信的一個共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)，以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它的操作系統(tǒng)中。2023/2/131為了協(xié)調(diào)雙方的通信，管道機制必須提供以下三方面的協(xié)調(diào)能力：

(1)互斥，即當(dāng)一個進(jìn)程正在對pipe執(zhí)行讀/寫操作時，其它(另一)進(jìn)程必須等待。

(2)同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量(如4KB)的數(shù)據(jù)寫入pipe，便去睡眠等待，直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把它喚醒。當(dāng)讀進(jìn)程讀一空pipe時，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。

(3)確定對方是否存在，只有確定了對方已存在時，才能進(jìn)行通信。2023/2/132

3．消息傳遞系統(tǒng)(Messagepassingsystem)消息傳遞系統(tǒng)是當(dāng)前應(yīng)用最為廣泛的一種進(jìn)程間的通信機制。在該機制中，進(jìn)程間的數(shù)據(jù)交換是以格式化的消息(message)為單位的；在計算機網(wǎng)絡(luò)中，又把message稱為報文。程序員直接利用操作系統(tǒng)提供的一組通信命令(原語)，不僅能實現(xiàn)大量數(shù)據(jù)的傳遞，而且還隱藏了通信的實現(xiàn)細(xì)節(jié)，使通信過程對用戶是透明的，從而大大減化了通信程序編制的復(fù)雜性，因而獲得了廣泛的應(yīng)用。2023/2/133特別值得一提的是，在當(dāng)今最為流行的微內(nèi)核操作系統(tǒng)中，微內(nèi)核與服務(wù)器之間的通信，無一例外地都采用了消息傳遞機制。又由于它能很好地支持多處理機系統(tǒng)、分布式系統(tǒng)和計算機網(wǎng)絡(luò)，因此它也成為這些領(lǐng)域最主要的通信工具。消息傳遞系統(tǒng)的通信方式屬于高級通信方式。又因其實現(xiàn)方式的不同而進(jìn)一步分成直接通信方式和間接通信方式兩種。2023/2/134

4．客戶機-服務(wù)器系統(tǒng)(Client-Serversystem)（1）套接字（UniversityofCaliforniaBerkeley）通信標(biāo)識類型的數(shù)據(jù)結(jié)構(gòu)：目的地址、端口號、通信網(wǎng)絡(luò)的傳輸協(xié)議、進(jìn)程所在的網(wǎng)絡(luò)地址、系統(tǒng)調(diào)用?；谖募停和慌_機器，一個套接字關(guān)聯(lián)一個特殊文件。

基于網(wǎng)絡(luò)型：非對稱方式，套接字+端口。（2）遠(yuǎn)程過程調(diào)用和遠(yuǎn)程方法調(diào)用

遠(yuǎn)程過程的步驟P70

2023/2/1352.6.2消息傳遞通信的實現(xiàn)方法

1．直接消息傳遞系統(tǒng)這是指發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。此時，要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式（對稱）提供對方的標(biāo)識符。（1）通信原語Send(Receiver，message)；發(fā)送一個消息給接收進(jìn)程；Receive(Sender，message)；接收Sender發(fā)來的消息；例如，原語Send(P2，m1)表示將消息m1發(fā)送給接收進(jìn)程P2；而原語Receive(P1，m1)則表示接收來自P1發(fā)來的消息m1。2023/2/136在某些情況下，接收進(jìn)程可與多個發(fā)送進(jìn)程通信（非對稱），因此，它不可能事先指定發(fā)送進(jìn)程。例如，用于提供打印服務(wù)的進(jìn)程，它可以接收來自任何一個進(jìn)程的“打印請求”消息。對于這樣的應(yīng)用，在接收進(jìn)程接收消息的原語中，表示源進(jìn)程的參數(shù)，也是完成通信后的返回值，接收原語可表示為：

Receive(id，message)；2023/2/137我們還可以利用直接通信原語來解決生產(chǎn)者—消費者問題。當(dāng)生產(chǎn)者生產(chǎn)出一個產(chǎn)品(消息)后，便用Send原語將消息發(fā)送給消費者進(jìn)程；而消費者進(jìn)程則利用Receive原語來得到一個消息。如果消息尚未生產(chǎn)出來，消費者必須等待，直至生產(chǎn)者進(jìn)程將消息發(fā)送過來。2023/2/138

2）消息的格式在消息傳遞系統(tǒng)中所傳遞的消息，必須具有一定的消息格式。在單機系統(tǒng)環(huán)境中，由于發(fā)送進(jìn)程和接收進(jìn)程處于同一臺機器中，有著相同的環(huán)境，故其消息格式比較簡單；但在計算機網(wǎng)絡(luò)環(huán)境下，不僅源和目標(biāo)進(jìn)程所處的環(huán)境不同，而且信息的傳輸距離很遠(yuǎn)，可能要跨越若干個完全不同的網(wǎng)絡(luò)，致使所用的消息格式比較復(fù)雜。通常，可把一個消息分成消息頭和消息正文兩部分。消息頭包括消息在傳輸時所需的控制信息，如源進(jìn)程名、目標(biāo)進(jìn)程名、消息長度、消息類型、消息編號及發(fā)送的日期和時間；而消息正文則是發(fā)送進(jìn)程實際上所發(fā)送的數(shù)據(jù)。2023/2/139在某些OS中，消息采用比較短的定長消息格式，這便減少了對消息的處理和存儲開銷。這種方式可用于辦公自動化系統(tǒng)中，為用戶提供快速的便箋式通信；但這對要發(fā)送較長消息的用戶是不方便的。在有的OS中，采用變長的消息格式，即進(jìn)程所發(fā)送消息的長度是可變的。系統(tǒng)無論在處理還是在存儲變長消息時，都可能會付出更多的開銷，但這方便了用戶。這兩種消息格式各有其優(yōu)缺點，故在很多系統(tǒng)(包括計算機網(wǎng)絡(luò))中，是同時都用的。2023/2/140

3）進(jìn)程同步方式在進(jìn)程之間進(jìn)行通信時，同樣需要有進(jìn)程同步機制，以使諸進(jìn)程間能協(xié)調(diào)通信。不論是發(fā)送進(jìn)程，還是接收進(jìn)程，在完成消息的發(fā)送或接收后，都存在兩種可能性，即進(jìn)程或者繼續(xù)發(fā)送(接收)，或者阻塞。由此，我們可得到以下三種情況：

(1)發(fā)送進(jìn)程阻塞，接收進(jìn)程阻塞。這種情況主要用于進(jìn)程之間緊密同步(tightsynchronization)，發(fā)送進(jìn)程和接收進(jìn)程之間無緩沖時。這兩個進(jìn)程平時都處于阻塞狀態(tài)，直到有消息傳遞時。這種同步方式稱為匯合(rendezrous)。2023/2/141

(2)發(fā)送進(jìn)程不阻塞，接收進(jìn)程阻塞。這是一種應(yīng)用最廣的進(jìn)程同步方式。平時，發(fā)送進(jìn)程不阻塞，因而它可以盡快地把一個或多個消息發(fā)送給多個目標(biāo)；而接收進(jìn)程平時則處于阻塞狀態(tài)，直到發(fā)送進(jìn)程發(fā)來消息時才被喚醒。例如，在服務(wù)器上通常都設(shè)置了多個服務(wù)進(jìn)程，它們分別用于提供不同的服務(wù)，如打印服務(wù)。平時，這些服務(wù)進(jìn)程都處于阻塞狀態(tài)，一旦有請求服務(wù)的消息到達(dá)時，系統(tǒng)便喚醒相應(yīng)的服務(wù)進(jìn)程，去完成用戶所要求的服務(wù)。處理完后，若無新的服務(wù)請求，服務(wù)進(jìn)程又阻塞。2023/2/142

(3)發(fā)送進(jìn)程和接收進(jìn)程均不阻塞。這也是一種較常見的進(jìn)程同步形式。平時，發(fā)送進(jìn)程和接收進(jìn)程都在忙于自己的事情，僅當(dāng)發(fā)生某事件使它無法繼續(xù)運行時，才把自己阻塞起來等待。例如，在發(fā)送進(jìn)程和接收進(jìn)程之間聯(lián)系著一個消息隊列時，該消息隊列最多能接納n個消息，這樣，發(fā)送進(jìn)程便可以連續(xù)地向消息隊列中發(fā)送消息而不必等待；接收進(jìn)程也可以連續(xù)地從消息隊列中取得消息，也不必等待。只有當(dāng)消息隊列中的消息數(shù)已達(dá)到n個時，即消息隊列已滿，發(fā)送進(jìn)程無法向消息隊列中發(fā)送消息時才會阻塞；類似地，只有當(dāng)消息隊列中的消息數(shù)為0，接收進(jìn)程已無法從消息隊列中取得消息時才會阻塞。2023/2/143

4）通信鏈路為使在發(fā)送進(jìn)程和接收進(jìn)程之間能進(jìn)行通信，必須在兩者之間建立一條通信鏈路(communicationlink)。有兩種方式建立通信鏈路。第一種方式是由發(fā)送進(jìn)程在通信之前用顯式的“建立連接”命令(原語)請求系統(tǒng)為之建立一條通信鏈路；在鏈路使用完后，也用顯式方式拆除鏈路。這種方式主要用于計算機網(wǎng)絡(luò)中。第二種方式是發(fā)送進(jìn)程無須明確提出建立鏈路的請求，只須利用系統(tǒng)提供的發(fā)送命令(原語)，系統(tǒng)會自動地為之建立一條鏈路。這種方式主要用于單機系統(tǒng)中。2023/2/144根據(jù)通信鏈路的連接方法，又可把通信鏈路分為兩類：

(1)點—點連接通信鏈路，這時的一條鏈路只連接兩個結(jié)點(進(jìn)程)；

(2)多點連接鏈路，指用一條鏈路連接多個(n>2)結(jié)點(進(jìn)程)。2023/2/145而根據(jù)通信方式的不同，則又可把鏈路分成兩種：

(1)單向通信鏈路，只允許發(fā)送進(jìn)程向接收進(jìn)程發(fā)送消息，或者相反；

(2)雙向通信鏈路，允許兩個進(jìn)程之間相互發(fā)送信息；還可根據(jù)通信鏈路容量的不同而把鏈路分成兩類：一是無容量通信鏈路，在這種通信鏈路上沒有緩沖區(qū)，因而不能暫存任何消息；再者就是有容量通信鏈路，指在通信鏈路中設(shè)置了緩沖區(qū)，因而能暫存消息。緩沖區(qū)數(shù)目愈多，通信鏈路的容量愈大。2023/2/146

2．間接通信方式間接通信方式指進(jìn)程之間的通信需要通過作為共享數(shù)據(jù)結(jié)構(gòu)的實體。該實體用來暫存發(fā)送進(jìn)程發(fā)送給目標(biāo)進(jìn)程的消息；接收進(jìn)程則從該實體中取出對方發(fā)送給自己的消息。通常把這種中間實體稱為信箱。消息在信箱中可以安全地保存，只允許核準(zhǔn)的目標(biāo)用戶隨時讀取。因此，利用信箱通信方式，既可實現(xiàn)實時通信，又可實現(xiàn)非實時通信。系統(tǒng)為信箱通信提供了若干條原語，分別用于信箱的創(chuàng)建、撤消和消息的發(fā)送、接收等。2023/2/1471)信箱結(jié)構(gòu)P722）信箱通信原語

（1）信箱的創(chuàng)建和撤消。進(jìn)程可利用信箱創(chuàng)建原語來建立一個新信箱。創(chuàng)建者進(jìn)程應(yīng)給出信箱名字、信箱屬性(公用、私用或共享)；對于共享信箱，還應(yīng)給出共享者的名字。當(dāng)進(jìn)程不再需要讀信箱時，可用信箱撤消原語將之撤消。2023/2/148

(2)

消息的發(fā)送和接收。當(dāng)進(jìn)程之間要利用信箱進(jìn)行通信時，必須使用共享信箱，并利用系統(tǒng)提供的下述通信原語進(jìn)行通信：

Send(mailbox，message)；將一個消息發(fā)送到指定信箱；

Receive(mailbox，message)；從指定信箱中接收一個消息；信箱可由操作系統(tǒng)創(chuàng)建，也可由用戶進(jìn)程創(chuàng)建，創(chuàng)建者是信箱的擁有者。據(jù)此，可把信箱分為以下三類。2023/2/1493)信箱類型

(1)私用信箱:用戶進(jìn)程可為自己建立一個新信箱，并作為該進(jìn)程的一部分。信箱的擁有者有權(quán)從信箱中讀取消息，其他用戶則只能將自己構(gòu)成的消息發(fā)送到該信箱中。這種私用信箱可采用單向通信鏈路的信箱來實現(xiàn)。當(dāng)擁有該信箱的進(jìn)程結(jié)束時，信箱也隨之消失。(2)公用信箱:它由操作系統(tǒng)創(chuàng)建，并提供給系統(tǒng)中的所有核準(zhǔn)進(jìn)程使用。核準(zhǔn)進(jìn)程既可把消息發(fā)送到該信箱中，也可從信箱中讀取發(fā)送給自己的消息。顯然，公用信箱應(yīng)采用雙向通信鏈路的信箱來實現(xiàn)。通常，公用信箱在系統(tǒng)運行期間始終存在。2023/2/150

(3)共享信箱它由某進(jìn)程創(chuàng)建，在創(chuàng)建時或創(chuàng)建后指明它是可共享的，同時指出共享進(jìn)程的名字。信箱擁有者和共享者都有權(quán)取走發(fā)送給自己的消息。一對一關(guān)系；多對一關(guān)系；一對多關(guān)系；多對多關(guān)系2023/2/1512.6.3消息緩沖隊列通信機制

1)消息緩沖區(qū)在消息緩沖隊列通信方式中，主要利用的數(shù)據(jù)結(jié)構(gòu)是消息緩沖區(qū)。它可描述如下：

typemessagebuffer=struct

sender ；發(fā)送者進(jìn)程標(biāo)識符

size ；消息長度

text ；消息正文

next ；指向下一個消息緩沖區(qū)的指針

end2023/2/152

2)PCB中有關(guān)通信的數(shù)據(jù)項在操作系統(tǒng)中采用了消息緩沖隊列通信機制時，除了需要為進(jìn)程設(shè)置消息緩沖隊列外，還應(yīng)在進(jìn)程的PCB中增加消息隊列隊首指針，用于對消息隊列進(jìn)行操作，以及用于實現(xiàn)同步的互斥信號量mutex和資源信號量sm。在PCB中應(yīng)增加的數(shù)據(jù)項可描述如下：2023/2/153typeprocesscontrolblock=struct

mq ；消息隊列隊首指針

mutex ；消息隊列互斥信號量

sm ；消息隊列資源信號量

end……2023/2/154

2．發(fā)送原語發(fā)送進(jìn)程在利用發(fā)送原語發(fā)送消息之前，應(yīng)先在自己的內(nèi)存空間設(shè)置一發(fā)送區(qū)a，見圖2-17所示。把待發(fā)送的消息正文、發(fā)送進(jìn)程標(biāo)識符、消息長度等信息填入其中，然后調(diào)用發(fā)送原語，把消息發(fā)送給目標(biāo)(接收)進(jìn)程。發(fā)送原語首先根據(jù)發(fā)送區(qū)a中所設(shè)置的消息長度a.size來申請一緩沖區(qū)i，接著把發(fā)送區(qū)a中的信息復(fù)制到緩沖區(qū)i中。為了能將i掛在接收進(jìn)程的消息隊列mq上，應(yīng)先獲得接收進(jìn)程的內(nèi)部標(biāo)識符j，然后將i掛在j.mq上。由于該隊列屬于臨界資源，故在執(zhí)行insert操作的前后，都要執(zhí)行wait和signal操作。2023/2/155圖2-17消息緩沖通信2023/2/156發(fā)送原語可描述如下：

proceduresend(receiver，a)

begin

getbuf(a.size,i)；根據(jù)a.size申請緩沖區(qū)；

i.sender:=a.sender；將發(fā)送區(qū)a中的信息復(fù)制到消息緩沖區(qū)i中；

i.size:=a.size；

i.text:=a.text；

i.next:=0；

getid(PCBset，receiver.j)；獲得接收進(jìn)程內(nèi)部標(biāo)識符；

wait(j.mutex)；

insert(j.mq，i)； 將消息緩沖區(qū)插入消息隊列；

signal(j.mutex)；

signal(j.sm)；

end2023/2/157procedurereceive(b)

begin

j:=internalname；j為接收進(jìn)程內(nèi)部的標(biāo)識符；

wait(j.sm)；

wait(j.mutex)；

remove(j.mq，i)；將消息隊列中第一個消息移出；

signal(j.mutex)；

b.sender:=i.sender；將消息緩沖區(qū)i中的信息復(fù)制到接收區(qū)b；

b.size:=i.size；

b.text:=i.text；

end第二章進(jìn)程的描述與控制前趨圖和程序執(zhí)行進(jìn)程的描述2進(jìn)程控制33進(jìn)程同步44經(jīng)典進(jìn)程的同步問題3535142023/2/158進(jìn)程通信44線程(Threads)的基本概念3576線程的實現(xiàn)4482023/2/1592.7線程2.7.1線程的基本概念

1．線程的兩個基本屬性如果說，在操作系統(tǒng)中引入進(jìn)程的目的，是為了使多個程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量，那么，在操作系統(tǒng)中再引入線程，則是為了減少程序在并發(fā)執(zhí)行時所付出的時空開銷，使OS具有更好的并發(fā)性（進(jìn)一步提高系統(tǒng)的并發(fā)程度）。為了說明這一點，我們首先來回顧進(jìn)程的兩個基本屬性:①進(jìn)程是一個可擁有資源的獨立單位；②進(jìn)程同時又是一個可獨立調(diào)度和分派的基本單位。正是由于進(jìn)程有這兩個基本屬性，才使之成為一個能獨立運行的基本單位，從而也就構(gòu)成了進(jìn)程并發(fā)執(zhí)行的基礎(chǔ)。然而，為使程序能并發(fā)執(zhí)行，系統(tǒng)還必須進(jìn)行以下的一系列操作。2023/2/1602．進(jìn)程的時空開銷

1)創(chuàng)建進(jìn)程系統(tǒng)在創(chuàng)建一個進(jìn)程時，必須為它分配其所必需的、除處理機以外的所有資源，如內(nèi)存空間、I/O設(shè)備，以及建立相應(yīng)的PCB。2)撤消進(jìn)程系統(tǒng)在撤消進(jìn)程時，又必須先對其所占有的資源執(zhí)行回收操作，然后再撤消PCB。2023/2/161

3)進(jìn)程切換對進(jìn)程進(jìn)行切換時，由于要保留當(dāng)前進(jìn)程的CPU環(huán)境和設(shè)置新選中進(jìn)程的CPU環(huán)境，因而須花費不少的處理機時間。換言之，由于進(jìn)程是一個資源的擁有者，因而在創(chuàng)建、撤消和切換中，系統(tǒng)必須為之付出較大的時空開銷。正因如此，在系統(tǒng)中所設(shè)置的進(jìn)程，其數(shù)目不宜過多，進(jìn)程切換的頻率也不宜過高，這也就限制了并發(fā)程度的進(jìn)一步提高。2023/2/162如何能使多個程序更好地并發(fā)執(zhí)行同時又盡量減少系統(tǒng)的開銷，已成為近年來設(shè)計操作系統(tǒng)時所追求的重要目標(biāo)。有不少研究操作系統(tǒng)的學(xué)者們想到，若能將進(jìn)程的上述兩個屬性分開，由操作系統(tǒng)分開處理，亦即對于作為調(diào)度和分派的基本單位，不同時作為擁有資源的單位，以做到“輕裝上陣”；而對于擁有資源的基本單位，又不對之進(jìn)行頻繁的切換。正是在這種思想的指導(dǎo)下，形成了線程的概念。2023/2/163

2.7.2線程與進(jìn)程的比較

1.調(diào)度在傳統(tǒng)的操作系統(tǒng)中，作為擁有資源的基本單位和獨立調(diào)度、分派的基本單位都是進(jìn)程。而在引入線程的操作系統(tǒng)中，則把線程作為調(diào)度和分派的基本單位，而進(jìn)程作為資源擁有的基本單位，把傳統(tǒng)進(jìn)程的兩個屬性分開，使線程基本上不擁有資源，這樣線程便能輕裝前進(jìn)，從而可顯著地提高系統(tǒng)的并發(fā)程度。在同一進(jìn)程中，線程的切換不會引起進(jìn)程的切換，但從一個進(jìn)程中的線程切換到另一個進(jìn)程中的線程時，將會引起進(jìn)程的切換。2023/2/164

2.并發(fā)性在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個進(jìn)程中的多個線程之間亦可并發(fā)執(zhí)行，使得操作系統(tǒng)具有更好的并發(fā)性，從而能更加有效地提高系統(tǒng)資源的利用率和系統(tǒng)的吞吐量。例如，在一個未引入線程的單CPU操作系統(tǒng)中，若僅設(shè)置一個文件服務(wù)進(jìn)程，當(dāng)該進(jìn)程由于某種原因而被阻塞時，便沒有其它的文件服務(wù)進(jìn)程來提供服務(wù)。在引入線程的操作系統(tǒng)中，則可以在一個文件服務(wù)進(jìn)程中設(shè)置多個服務(wù)線程。當(dāng)?shù)谝粋€線程等待時，文件服務(wù)進(jìn)程中的第二個線程可以繼續(xù)運行，以提供文件服務(wù)；當(dāng)?shù)诙€線程阻塞時，則可由第三個繼續(xù)執(zhí)行，提供服務(wù)。顯然，這樣的方法可以顯著地提高文件服務(wù)的質(zhì)量和系統(tǒng)的吞吐量。2023/2/165

3.擁有資源不論是傳統(tǒng)的操作系統(tǒng)，還是引入了線程的操作系統(tǒng)，進(jìn)程都可以擁有資源，是系統(tǒng)中擁有資源的一個基本單位。一般而言，線程自己不擁有系統(tǒng)資源(也有一點必不可少的資源)，但它可以訪問其隸屬進(jìn)程的資源，即一個進(jìn)程的代碼段、數(shù)據(jù)段及所擁有的系統(tǒng)資源，如已打開的文件、I/O設(shè)備等，可以供該進(jìn)程中的所有線程所共享。2023/2/166

4.獨立性

線程的獨立性要比進(jìn)程獨立性低的多。2023/2/167

5.系統(tǒng)開銷在創(chuàng)建或撤消進(jìn)程時，系統(tǒng)都要為之創(chuàng)建和回收進(jìn)程控制塊，分配或回收資源，如內(nèi)存空間和I/O設(shè)備等，操作系統(tǒng)所付出的開銷明顯大于線程創(chuàng)建或撤消時的開銷。類似地，在進(jìn)程切換時，涉及到當(dāng)前進(jìn)程CPU環(huán)境的保存及新被調(diào)度運行進(jìn)程的CPU環(huán)境的設(shè)置，而線程的切換則僅需保存和設(shè)置少量寄存器內(nèi)容，不涉及存儲器管理方面的操作，所以就切換代價而言，進(jìn)程也是遠(yuǎn)高于線程的。此外，由于一個進(jìn)程中的多個線程具有相同的地址空間，在同步和通信的實現(xiàn)方面線程也比進(jìn)程容易。在一些操作系統(tǒng)中，線程的切換、同步和通信都無須操作系統(tǒng)內(nèi)核的干預(yù)。2023/2/168

6.支持多處理機

線程比進(jìn)程更加靈活。2023/2/169

2.7.3線程的狀態(tài)在多線程OS中，通常是在一個進(jìn)程中包括多個線程，每個線程都是作為利用CPU的基本單位，是花費最小開銷的實體。1.線程具有下述屬性。

(1)輕型實體。線程中的實體基本上不擁有系統(tǒng)資源，只是有一點必不可少的、能保證其獨立運行的資源，比如，在每個線程中都應(yīng)具有一個用于控制線程運行的線程控制塊TCB，用于指示被執(zhí)行指令序列的程序計數(shù)器，保留局部變量、少數(shù)狀態(tài)參數(shù)和返回地址等的一組寄存器和堆棧。2023/2/170

(2)獨立調(diào)度和分派的基本單位。在多線程OS中，線程是能獨立運行的基本單位，因而也是獨立調(diào)度和分派的基本單位。由于線程很“輕”，故線程的切換非常迅速且開銷小。

(3)可并發(fā)執(zhí)行。在一個進(jìn)程中的多個線程之間可以并發(fā)執(zhí)行，甚至允許在一個進(jìn)程中的所有線程都能并發(fā)執(zhí)行；同樣，不同進(jìn)程中的線程也能并發(fā)執(zhí)行。

(4)共享進(jìn)程資源。在同一進(jìn)程中的各個線程都可以共享該進(jìn)程所擁有的資源，這首先表現(xiàn)在所有線程都具有相同的地址空間(進(jìn)程的地址空間)。這意味著線程可以訪問該地址空間中的每一個虛地址；此外，還可以訪問進(jìn)程所擁有的已打開文件、定時器、信號量機構(gòu)等。2023/2/171

2．線程的狀態(tài)

(1)狀態(tài)參數(shù)。在OS中的每一個線程都可以利用線程標(biāo)識符和一組狀態(tài)參數(shù)進(jìn)行描述。狀態(tài)參數(shù)通常有這樣幾項：①寄存器狀態(tài)，它包括程序計數(shù)器PC和堆棧指針中的內(nèi)容；②堆棧，在堆棧中通常保存有局部變量和返回地址；③線程運行狀態(tài)，用于描述線程正處于何種運行狀態(tài)；④優(yōu)先級，描述線程執(zhí)行的優(yōu)先程度；⑤線程專有存儲器，用于保存線程自己的局部變量拷貝；⑥信號屏蔽，即對某些信號加以屏蔽。2023/2/172

(2)線程運行狀態(tài)。如同傳統(tǒng)的進(jìn)程一樣，在各線程之間也存在著共享資源和相互合作的制約關(guān)系，致使線程在運行時也具有間斷性。相應(yīng)地，線程在運行時也具有下述三種基本狀態(tài):①執(zhí)行狀態(tài)，表示線程正獲得處理機而運行；②就緒狀態(tài)，指線程已具備了各種執(zhí)行條件，一旦獲得CPU便可執(zhí)行的狀態(tài)；③阻塞狀態(tài)，指線程在執(zhí)行中因某事件而受阻，處于暫停執(zhí)行時的狀態(tài)。2023/2/173

3．多線程OS中的進(jìn)程在多線程OS中，進(jìn)程是作為擁有系統(tǒng)資源的基本單位，通常的進(jìn)程都包含多個線程并為它們提供資源，但此時的進(jìn)程就不再作為一個執(zhí)行的實體。多線程OS中的進(jìn)程有以下屬性：

(1)作為系統(tǒng)資源分配的單位。在多線程OS中，仍是將進(jìn)程作為系統(tǒng)資源分配的基本單位，在任一進(jìn)程中所擁有的資源包括受到分別保護(hù)的用戶地址空間、用于實現(xiàn)進(jìn)程間和線程間同步和通信的機制、已打開的文件和已申請到的I/O設(shè)備，以及一張由核心進(jìn)程維護(hù)的地址映射表，該表用于實現(xiàn)用戶程序的邏輯地址到其內(nèi)存物理地址的映射。2023/2/174

(2)可包括多個線程。通常，一個進(jìn)程都含有多個相對獨立的線程，其數(shù)目可多可少，但至少也要有一個線程，由進(jìn)程為這些(個)線程提供資源及運行環(huán)境，使這些線程可并發(fā)執(zhí)行。在OS中的所有線程都只能屬于某一個特定進(jìn)程。

(3)進(jìn)程不是一個可執(zhí)行的實體。在多線程OS中，是把線程作為獨立運行的基本單位，所以此時的進(jìn)程已不再是一個可執(zhí)行的實體。雖然如此，進(jìn)程仍具有與執(zhí)行相關(guān)的狀態(tài)。例如，所謂進(jìn)程處于“執(zhí)行”狀態(tài)，實際上是指該進(jìn)程中的某線程正在執(zhí)行。此外，對進(jìn)程所施加的與進(jìn)程狀態(tài)有關(guān)的操作，也對其線程起作用。例如，在把某個進(jìn)程掛起時，該進(jìn)程中的所有線程也都將被掛起；又如，在把某進(jìn)程激活時，屬于該進(jìn)程的所有線程也都將被激活。2023/2/17575P84：

7,11,12,13,14,15,16,17,18,21課程作業(yè)2023/2/1762.7.2線程間的同步和通信

1．互斥鎖(mutex)互斥鎖是一種比較簡單的、用于實現(xiàn)線程間對資源互斥訪問的機制。由于操作互斥鎖的時間和空間開銷都較低，因而較適合于高頻度使用的關(guān)鍵共享數(shù)據(jù)和程序段?；コ怄i可以有兩種狀態(tài)，即開鎖(unlock)和關(guān)鎖(lock)狀態(tài)。相應(yīng)地，可用兩條命令(函數(shù))對互斥鎖進(jìn)行操作。其中的關(guān)鎖lock操作用于將mutex關(guān)上，開鎖操作unlock則用于打開mutex。2023/2/177當(dāng)一個線程需要讀/寫一個共享數(shù)據(jù)段時，線程首先應(yīng)為該數(shù)據(jù)段所設(shè)置的mutex執(zhí)行關(guān)鎖命令。命令首先判別mutex的狀態(tài)，如果它已處于關(guān)鎖狀態(tài)，則試圖訪問該數(shù)據(jù)段的線程將被阻塞；而如果mutex是處于開鎖狀態(tài)，則將mutex關(guān)上后便去讀/寫該數(shù)據(jù)段。在線程完成對數(shù)據(jù)的讀/寫后，必須再發(fā)出開鎖命令將mutex打開，同時還須將阻塞在該互斥鎖上的一個線程喚醒，其它的線程仍被阻塞在等待mutex打開的隊列上。另外，為了減少線程被阻塞的機會，在有的系統(tǒng)中還提供了一種用于mutex上的操作命令Trylock。當(dāng)一個線程在利用Trylock命令去訪問mutex時，若mutex處于開鎖狀態(tài)，Trylock將返回一個指示成功的狀態(tài)碼；反之，若mutex處于關(guān)鎖狀態(tài)，則Trylock并不會阻塞該線程，而只是返回一個指示操作失敗的狀態(tài)碼。2023/2/178

2．條件變量在許多情況下，只利用mutex來實現(xiàn)互斥訪問可能會引起死鎖，我們通過一個例子來說明這一點。有一個線程在對mutex1執(zhí)行關(guān)鎖操作成功后，便進(jìn)入一臨界區(qū)C，若在臨界區(qū)內(nèi)該線程又須訪問某個臨界資源R，同樣也為R設(shè)置另一互斥鎖mutex2。假如資源R此時正處于忙碌狀態(tài)，線程在對mutex2執(zhí)行關(guān)鎖操作后必將被阻塞，這樣將使mutex1一直保持關(guān)鎖狀態(tài)；如果保持了資源R的線程也要求進(jìn)入臨界區(qū)C，但由于mutex1一直保持關(guān)鎖狀態(tài)而無法進(jìn)入臨界區(qū)，這樣便形成了死鎖。為了解決這個問題便引入了條件變量。2023/2/179

每一個條件變量通常都與一個互斥鎖一起使用，亦即，在創(chuàng)建一個互斥鎖時便聯(lián)系著一個條件變量。單純的互斥鎖用于短期鎖定，主要是用來保證對臨界區(qū)的互斥進(jìn)入。而條件變量則用于線程的長期等待，直至所等待的資源成為可用的資源?，F(xiàn)在，我們看看如何利用互斥鎖和條件變量來實現(xiàn)對資源R的訪問。線程首先對mutex執(zhí)行關(guān)鎖操作，若成功便進(jìn)入臨界區(qū)，然后查找用于描述該資源狀態(tài)的數(shù)據(jù)結(jié)構(gòu)，以了解資源的情況。只要發(fā)現(xiàn)所需資源R正處于忙碌狀態(tài)，線程便轉(zhuǎn)為等待狀態(tài)，并對mutex執(zhí)行開鎖操作后，等待該資源被釋放；若資源處于空閑狀態(tài)，表明線程可以使用該資源，于是將該資源設(shè)置為忙碌狀態(tài)，再對mutex執(zhí)行開鎖操作。下面給出了對上述資源的申請(左半部分)和釋放(右半部分)操作的描述。2023/2/180Lockmutex

Lockmutex

checkdatastructures； markresourceasfree；

while(resourcebusy)； unlockmutex；

wait(conditionvariable)；wakeup(conditionvariable)；

markresourceasbusy；

unlockmutex；2023/2/181原來占有資源R的線程在使用完該資源后，便按照右半部分的描述釋放該資源，其中的wakeup(conditionvariable)表示去喚醒在指定條件變量上等待的一個或多個線程。在大多數(shù)情況下，由于所釋放的是臨界資源，此時所喚醒的只能是在條件變量上等待的某一個線程，其它線程仍繼續(xù)在該隊列上等待。但如果線程所釋放的是一個數(shù)據(jù)文件，該文件允許多個線程同時對它執(zhí)行讀操作。在這種情況下，當(dāng)一個寫線程完成寫操作并釋放該文件后，如果此時在該條件變量上還有多個讀線程在等待，則該線程可以喚醒所有的等待線程。2023/2/182

3．信號量機制

1)私用信號量(privatesamephore)當(dāng)某線程需利用信號量來實現(xiàn)同一進(jìn)程中各線程之間的同步時，可調(diào)用創(chuàng)建信號量的命令來創(chuàng)建一私用信號量，其數(shù)據(jù)結(jié)構(gòu)存放在應(yīng)用程序的地址空間中。私用信號量屬于特定的進(jìn)程所有，OS并不知道私用信號量的存在，因此，一旦發(fā)生私用信號量的占用者異常結(jié)束或正常結(jié)束，但并未釋放該信號量所占有空間的情況時，系統(tǒng)將無法使它恢復(fù)為0(空)，也不能將它傳送給下一個請求它的線程。2023/2/183

2)公用信號量(publicsemaphore)

公用信號量是為實現(xiàn)不同進(jìn)程間或不同進(jìn)程中各線程之間的同步而設(shè)置的。由于它有著一個公開的名字供所有的進(jìn)程使用，故而把它稱為公用信號量。其數(shù)據(jù)結(jié)構(gòu)是存放在受保護(hù)的系統(tǒng)存儲區(qū)中，由OS為它分配空間并進(jìn)行管理，故也稱為系統(tǒng)信號量。如果信號量的占有者在結(jié)束時未釋放該公用信號量，則OS會自動將該信號量空間回收，并通知下一進(jìn)程?？梢姡眯盘柫渴且环N比較安全的同步機制。第二章進(jìn)程的描述與控制前趨圖和程序執(zhí)行進(jìn)程的描述2進(jìn)程控制33進(jìn)程同步44經(jīng)典進(jìn)程的同步問題3535142023/2/184進(jìn)程通信44線程(Threads)的基本概念3576線程的實現(xiàn)4482023/2/1852.8線程的實現(xiàn)

1．內(nèi)核支持線程對于通常的進(jìn)程，無論是系統(tǒng)進(jìn)程還是用戶進(jìn)程，進(jìn)程的創(chuàng)建、撤消，以及要求由系統(tǒng)設(shè)備完成的I/O操作，都是利用系統(tǒng)調(diào)用而進(jìn)入內(nèi)核，再由內(nèi)核中的相應(yīng)處理程序予以完成的。進(jìn)程的切換同樣是在內(nèi)核的支持下實現(xiàn)的。因此我們說，不論什么進(jìn)程，它們都是在操作系統(tǒng)內(nèi)核的支持下運行的，是與內(nèi)核緊密相關(guān)的。2023/2/186這里所謂的內(nèi)核支持線程KST(KernelSupportedThreads)，也都同樣是在內(nèi)核的支持下運行的，即無論是用戶進(jìn)程中的線程，還是系統(tǒng)進(jìn)程中的線程，他們的創(chuàng)建、撤消和切換等也是依靠內(nèi)核，在內(nèi)核空間實現(xiàn)的。此外，在內(nèi)核空間還為每一個內(nèi)核支持線程設(shè)置了一個線程控制塊，內(nèi)核是根據(jù)該控制塊而感知某線程的存在，并對其加以控制。這種線程實現(xiàn)方式主要有如下四個優(yōu)點：

(1)在多處理器系統(tǒng)中，內(nèi)核能夠同時調(diào)度同一進(jìn)程中多個線程并行執(zhí)行；2023/2/187

(2)如果進(jìn)程中的一個線程被阻塞了，內(nèi)核可以調(diào)度該進(jìn)程中的其它線程占有處理器運行，也可以運行其它進(jìn)程中的線程；

(3)內(nèi)核支持線程具有很小的數(shù)據(jù)結(jié)構(gòu)和堆棧，線程的切換比較快，切換開銷??；

(4)內(nèi)核本身也可以采用多線程技術(shù)，可以提高系統(tǒng)的執(zhí)行速度和效率。內(nèi)核支持線程的主要缺點是：對于用戶的線程切換而言，其模式切換的開銷較大，在同一個進(jìn)程中，從一個線程切換到另一個線程時，需要從用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)進(jìn)行，這是因為用戶進(jìn)程的線程在用戶態(tài)運行，而線程調(diào)度和管理是在內(nèi)核實現(xiàn)的，系統(tǒng)開銷較大。2023/2/188

2．用戶級線程用戶級線程ULT(UserLevelThreads)僅存在于用戶空間中。對于這種線程的創(chuàng)建、撤消、線程之間的同步與通信等功能，都無須利用系統(tǒng)調(diào)用來實現(xiàn)。對于用戶級線程的切換，通常發(fā)生在一個應(yīng)用進(jìn)程的諸多線程之間，這時，也同樣無須內(nèi)核的支持。由于切換的規(guī)則遠(yuǎn)比進(jìn)程調(diào)度和切換的規(guī)則簡單，因而使線程的切換速度特別快?？梢?，這種線程是與內(nèi)核無關(guān)的。我們可以為一個應(yīng)用程序建立多個用戶級線程。在一個系統(tǒng)中的用戶級線程的數(shù)目可以達(dá)到數(shù)百個至數(shù)千個。由于這些線程的任務(wù)控制塊都是設(shè)置在用戶空間，而線程所執(zhí)行的操作也無須內(nèi)核的幫助，因而內(nèi)核完全不知道用戶級線程的存在。2023/2/189值得說明的是，對于設(shè)置了用戶級線程的系統(tǒng)，其調(diào)度仍是以進(jìn)程為單位進(jìn)行的。在采用輪轉(zhuǎn)調(diào)度算法時，各個進(jìn)程輪流執(zhí)行一個時間片，這對諸進(jìn)程而言似乎是公平的。但假如在進(jìn)程A中包含了一個用戶級線程，而在另一個進(jìn)程B中含有100個用戶級線程，這樣，進(jìn)程A中線程的運行時間將是進(jìn)程B中各線程運行時間的100倍；相應(yīng)地，其速度要快上100倍。假如系統(tǒng)中設(shè)置的是內(nèi)核支持線程，則調(diào)度便是以線程為單位進(jìn)行的。在采用輪轉(zhuǎn)法調(diào)度時，是各個線程輪流執(zhí)行一個時間片。同樣假定進(jìn)程A中只有一個內(nèi)核支持線程，而在進(jìn)程B中有100個內(nèi)核支持線程。此時進(jìn)程B可以獲得的CPU時間是進(jìn)程A的100倍，且進(jìn)程B可使100個系統(tǒng)調(diào)用并發(fā)工作。2023/2/190使用用戶級線程方式有許多優(yōu)點，主要表現(xiàn)在如下三個方面：

(1)線程切換不需要轉(zhuǎn)換到內(nèi)核空間，對一個進(jìn)程而言，其所有線程的管理數(shù)據(jù)結(jié)構(gòu)均在該進(jìn)程的用戶空間中，管理線程切換的線程庫也在用戶地址空間運行。因此，進(jìn)程不必切換到內(nèi)核方式來做線程管理，從而節(jié)省了模式切換的開銷，也節(jié)省了內(nèi)核的寶貴資源。

(2)調(diào)度算法可以是進(jìn)程專用的。在不干擾操作系統(tǒng)調(diào)度的情況下，不同的進(jìn)程可以根據(jù)自身需要，選擇不同的調(diào)度算法對自己的線程進(jìn)行管理和調(diào)度，而與操作系統(tǒng)的低級調(diào)度算法是無關(guān)的。2023/2/191

(3)用戶級線程的實現(xiàn)與操作系統(tǒng)平臺無關(guān)，因為對于線程管理的代碼是在用戶程序內(nèi)的，屬于用戶程序的一部分，所有的應(yīng)用程序都可以對之進(jìn)行共享。因此，用戶級線程甚至可以在不支持線程機制的操作系統(tǒng)平臺上實現(xiàn)。2023/2/192用戶級線程實現(xiàn)方式的主要缺點在于如下兩個方面：

(1)系統(tǒng)調(diào)用的阻塞問題。在基于進(jìn)程機制的操作系統(tǒng)中，大多數(shù)系統(tǒng)調(diào)用將阻塞進(jìn)程，因此，當(dāng)線程執(zhí)行一個系統(tǒng)調(diào)用時，不僅該線程被阻塞，而且進(jìn)程內(nèi)的所有線程都會被阻塞。而在內(nèi)核支持線程方式中，則進(jìn)程中的其它線程仍然可以運行。

(2)在單純的用戶級線程實現(xiàn)方式中，多線程應(yīng)用不能利用多處理機進(jìn)行多重處理的優(yōu)點。內(nèi)核每次分配給一個進(jìn)程的僅有一個CPU，因此進(jìn)程中僅有一個線程能執(zhí)行，在該線程放棄CPU之前，其它線程只能等待。2023/2/193

3．組合方式有些操作系統(tǒng)把用戶級線程和內(nèi)核支持線程兩種方式進(jìn)行組合，提供了組合方式ULT/KST線程。在組合方式線程系統(tǒng)中，內(nèi)核支持多KST線程的建立、調(diào)度和管理，同時，也允許用戶應(yīng)用程序建立、調(diào)度和管理用戶級線程。一些內(nèi)核支持線程對應(yīng)多個用戶級線程，程序員可按應(yīng)用需要和機器配置對內(nèi)核支持線程數(shù)目進(jìn)行調(diào)整，以達(dá)到較好的效果。組合方式線程中，同一個進(jìn)程內(nèi)的多個線程可以同時在多處理器上并行執(zhí)行，而且在阻塞一個線程時，并不需要將整個進(jìn)程阻塞。所以，組合方式多線程機制能夠結(jié)合KST和ULT兩者的優(yōu)點，并克服了其各自的不足。2023/2/1942.7.4線程的實現(xiàn)

1．內(nèi)核支持線程的實現(xiàn)在僅設(shè)置了內(nèi)核支持線程的OS中，一種可能的線程控制方法是，系統(tǒng)在創(chuàng)建一個新進(jìn)程時，便為它分配一個任務(wù)數(shù)據(jù)區(qū)PTDA(PerTaskDataArea)，其中包括若干個線程控制塊TCB空間，如圖2-15所示。在每一個TCB中可保存線程標(biāo)識符、優(yōu)先級、線程運行的CPU狀態(tài)等信息。雖然這些信息與用戶級線程TCB中的信息相同，但現(xiàn)在卻是被保存在內(nèi)核空間中。2023/2/195圖2-15任務(wù)數(shù)據(jù)區(qū)空間2023/2/196每當(dāng)進(jìn)程要創(chuàng)建一個線程時，便為新線程分配一個TCB，將有關(guān)信息填入該TCB中，并為之分配必要的資源，如為線程分配數(shù)百至數(shù)千個字節(jié)的?？臻g和局部存儲區(qū)，于是新創(chuàng)建的線程便有條件立即執(zhí)行。當(dāng)PTDA中的所有TCB空間已用完，而進(jìn)程又要創(chuàng)建新的線程時，只要其所創(chuàng)建的線程數(shù)目未超過系統(tǒng)的允許值(通常為數(shù)十至數(shù)百個)，系統(tǒng)可再為之分配新的TCB空間；在撤消一個線程時，也應(yīng)回收該線程的所有資源和TCB。可見，內(nèi)核支持線程的創(chuàng)建、撤消均與進(jìn)程的相類似。在有的系統(tǒng)中為了減少創(chuàng)建和撤消一個線程時的開銷，在撤消一個線程時，并不立即回收該線程的資源和TCB，當(dāng)以后再要創(chuàng)建一個新線程時，便