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

1．利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用。利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息。對(duì)生產(chǎn)者—消費(fèi)者問(wè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)者—消費(fèi)者問(wèn)題中應(yīng)注意：首先，在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)；其次，對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計(jì)算進(jìn)程中，而signal(empty)則在消費(fèi)進(jìn)程中，計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞，則以后將由消費(fèi)進(jìn)程將它喚醒；最后，在每個(gè)程序中的多個(gè)wait操作順序不能顛倒，應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。2023/2/17

2．利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題對(duì)于生產(chǎn)者—消費(fèi)者問(wèn)題，也可利用AND信號(hào)量來(lái)解決，即用Swait(empty，mutex)來(lái)代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)來(lái)代替signal(mutex)和signal(full)；用Swait(full，mutex)來(lái)代替wait(full)和wait(mutex)，以及用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。利用AND信號(hào)量來(lái)解決生產(chǎn)者—消費(fèi)者問(wè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)者—消費(fèi)者問(wèn)題在利用管程方法來(lái)解決生產(chǎn)者—消費(fèi)者問(wèn)題時(shí)，首先便是為它們建立一個(gè)管程，并命名為ProclucerConsumer，或簡(jiǎn)稱為PC。其中包括兩個(gè)過(guò)程：

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

(2)get(item)過(guò)程。消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count≤0時(shí)，表示緩沖池中已無(wú)可取用的產(chǎn)品，消費(fèi)者應(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)餐問(wèn)題

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

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

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é)家饑餓時(shí)，總是先去拿他左邊的筷子，即執(zhí)行wait(chopstick[i])；成功后，再去拿他右邊的筷子，即執(zhí)行wait(chopstick[(i+1)mod5])；又成功后便可進(jìn)餐。進(jìn)餐完畢，又先放下他左邊的筷子，然后再放右邊的筷子。雖然，上述解法可保證不會(huì)有兩個(gè)相鄰的哲學(xué)家同時(shí)進(jìn)餐，但有可能引起死鎖。假如五位哲學(xué)家同時(shí)饑餓而各自拿起左邊的筷子時(shí)，就會(huì)使五個(gè)信號(hào)量chopstick均為0；當(dāng)他們?cè)僭噲D去拿右邊的筷子時(shí)，都將因無(wú)筷子可拿而無(wú)限期地等待。對(duì)于這樣的死鎖問(wèn)題，可采取以下幾種解決方法：2023/2/116

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

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

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

2．利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題在哲學(xué)家進(jìn)餐問(wèn)題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問(wèn)題，故用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。描述如下：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讀者—寫(xiě)者問(wèn)題

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

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請(qǐng)給出一個(gè)寫(xiě)者優(yōu)先的“讀者-寫(xiě)者”問(wèn)題的算法描述。應(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．利用信號(hào)量集機(jī)制解決讀者—寫(xiě)者問(wèn)題這里的讀者—寫(xiě)者問(wèn)題與前面的略有不同，它增加了一個(gè)限制，即最多只允許RN個(gè)讀者同時(shí)讀。為此，又引入了一個(gè)信號(hào)量L，并賦予其初值為RN，通過(guò)執(zhí)行wait(L，1，1)操作，來(lái)控制讀者的數(shù)目。每當(dāng)有一個(gè)讀者進(jìn)入時(shí)，就要先執(zhí)行wait(L，1，1)操作，使L的值減1。當(dāng)有RN個(gè)讀者進(jìn)入讀后，L便減為0，第RN+1個(gè)讀者要進(jìn)入讀時(shí)，必然會(huì)因wait(L，1，1)操作失敗而阻塞。對(duì)利用信號(hào)量集來(lái)解決讀者—寫(xiě)者問(wèn)題的描述如下：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)語(yǔ)句起著開(kāi)關(guān)的作用。只要無(wú)writer進(jìn)程進(jìn)入寫(xiě)，mx=1，reader進(jìn)程就都可以進(jìn)入讀。但只要一旦有writer進(jìn)程進(jìn)入寫(xiě)時(shí)，其mx=0，則任何reader進(jìn)程就都無(wú)法進(jìn)入讀。Swait(mx，1，1；L，RN，0)語(yǔ)句表示僅當(dāng)既無(wú)writer進(jìn)程在寫(xiě)(mx=1)，又無(wú)reader進(jìn)程在讀(L=RN)時(shí)，writer進(jìn)程才能進(jìn)入臨界區(qū)寫(xiě)。第二章進(jìn)程的描述與控制前趨圖和程序執(zhí)行進(jìn)程的描述2進(jìn)程控制33進(jìn)程同步44經(jīng)典進(jìn)程的同步問(wèn)題3535142023/2/127進(jìn)程通信44線程(Threads)的基本概念3576線程的實(shí)現(xiàn)4482023/2/1282.6進(jìn)程通信信號(hào)量機(jī)制在通信方面：效率低；通信對(duì)用戶不透明。2.6.1進(jìn)程通信的類(lèi)型

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

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

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

2．管道通信所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程以實(shí)現(xiàn)它們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫(xiě)進(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)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力：

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

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

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

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

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

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

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

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

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

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

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

3）進(jìn)程同步方式在進(jìn)程之間進(jìn)行通信時(shí)，同樣需要有進(jìn)程同步機(jī)制，以使諸進(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)程之間無(wú)緩沖時(shí)。這兩個(gè)進(jìn)程平時(shí)都處于阻塞狀態(tài)，直到有消息傳遞時(shí)。這種同步方式稱為匯合(rendezrous)。2023/2/141

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

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

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

typemessagebuffer=struct

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

size ；消息長(zhǎng)度

text ；消息正文

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

end2023/2/152

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

mq ；消息隊(duì)列隊(duì)首指針

mutex ；消息隊(duì)列互斥信號(hào)量

sm ；消息隊(duì)列資源信號(hào)量

end……2023/2/154

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

proceduresend(receiver，a)

begin

getbuf(a.size,i)；根據(jù)a.size申請(qǐng)緩沖區(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)識(shí)符；

wait(j.mutex)；

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

signal(j.mutex)；

signal(j.sm)；

end2023/2/157procedurereceive(b)

begin

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

wait(j.sm)；

wait(j.mutex)；

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

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)程的同步問(wèn)題3535142023/2/158進(jìn)程通信44線程(Threads)的基本概念3576線程的實(shí)現(xiàn)4482023/2/1592.7線程2.7.1線程的基本概念

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

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

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

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

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

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

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

4.獨(dú)立性

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

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

6.支持多處理機(jī)

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

2.7.3線程的狀態(tài)在多線程O(píng)S中，通常是在一個(gè)進(jìn)程中包括多個(gè)線程，每個(gè)線程都是作為利用CPU的基本單位，是花費(fèi)最小開(kāi)銷(xiāo)的實(shí)體。1.線程具有下述屬性。

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

(2)獨(dú)立調(diào)度和分派的基本單位。在多線程O(píng)S中，線程是能獨(dú)立運(yùn)行的基本單位，因而也是獨(dú)立調(diào)度和分派的基本單位。由于線程很“輕”，故線程的切換非常迅速且開(kāi)銷(xiāo)小。

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

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

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

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

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

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

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

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

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

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

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

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

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

Lockmutex

checkdatastructures； markresourceasfree；

while(resourcebusy)； unlockmutex；

wait(conditionvariable)；wakeup(conditionvariable)；

markresourceasbusy；

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

3．信號(hào)量機(jī)制

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

2)公用信號(hào)量(publicsemaphore)

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

1．內(nèi)核支持線程對(duì)于通常的進(jìn)程，無(wú)論是系統(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)核的支持下實(shí)現(xiàn)的。因此我們說(shuō)，不論什么進(jìn)程，它們都是在操作系統(tǒng)內(nèi)核的支持下運(yùn)行的，是與內(nèi)核緊密相關(guān)的。2023/2/186這里所謂的內(nèi)核支持線程KST(KernelSupportedThreads)，也都同樣是在內(nèi)核的支持下運(yùn)行的，即無(wú)論是用戶進(jìn)程中的線程，還是系統(tǒng)進(jìn)程中的線程，他們的創(chuàng)建、撤消和切換等也是依靠?jī)?nèi)核，在內(nèi)核空間實(shí)現(xiàn)的。此外，在內(nèi)核空間還為每一個(gè)內(nèi)核支持線程設(shè)置了一個(gè)線程控制塊，內(nèi)核是根據(jù)該控制塊而感知某線程的存在，并對(duì)其加以控制。這種線程實(shí)現(xiàn)方式主要有如下四個(gè)優(yōu)點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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