第2章進(jìn)程的描述與控制2

1第二章進(jìn)程控制與描述2.5經(jīng)典進(jìn)程同步問題2.6進(jìn)程通信2.7線程的基本概念2.8線程的實(shí)現(xiàn)22.5

經(jīng)典進(jìn)程的同步問題

1.生產(chǎn)者—消費(fèi)者問題2.哲學(xué)家進(jìn)餐問題3.讀者—寫者問題通過對經(jīng)典問題的研究和學(xué)習(xí)，可以幫助我們更好地理解進(jìn)程同步的概念及實(shí)現(xiàn)方法P6032.5.1生產(chǎn)者—消費(fèi)者問題

Producer-consumerproblem，又稱有限緩沖問題（Bounded-bufferproblem)兩個(gè)共享固定大小緩沖區(qū)的進(jìn)程—“生產(chǎn)者”和“消費(fèi)者”42.5.1生產(chǎn)者—消費(fèi)者問題

Theyare,相互合作進(jìn)程關(guān)系1.用記錄型信號量解決

2.

用AND信號量解決3.利用管程解決生產(chǎn)者-消費(fèi)者問題單緩沖區(qū)情況生產(chǎn)者P和消費(fèi)者C共用一個(gè)緩沖區(qū)，P生產(chǎn)產(chǎn)品放入緩沖區(qū)，C從緩沖區(qū)取產(chǎn)品來消費(fèi)。多個(gè)緩沖區(qū)情況生產(chǎn)者和消費(fèi)者通過一個(gè)有界緩沖池(n個(gè))相互聯(lián)系。

5單緩沖區(qū)情況單緩沖區(qū)的同步問題

生產(chǎn)者P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為empty（初值為1）消費(fèi)者C進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量full（初值為0）單緩沖區(qū)的互斥問題P、C進(jìn)程不能同時(shí)使用緩沖區(qū)6Semaphoreempty=n,full=0；(單緩沖區(qū))生產(chǎn)者─消費(fèi)者問題Proceducer

：while(true){

生產(chǎn)一個(gè)產(chǎn)品;

P(empty);

送產(chǎn)品到緩沖區(qū);

V(full);};Consumer：while(true){P(full);從緩沖區(qū)取產(chǎn)品;

V(empty);消費(fèi)產(chǎn)品;};7多個(gè)緩沖區(qū)情況生產(chǎn)者和消費(fèi)者共享n個(gè)緩沖區(qū)，利用互斥信號量Mutex(Mutualexclusion，縮寫Mutex)實(shí)現(xiàn)進(jìn)程對緩沖池的互斥使用。信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息。8....PC生產(chǎn)者消費(fèi)者n-1n個(gè)Buffer

同步當(dāng)緩沖池已放滿產(chǎn)品時(shí)，生產(chǎn)者進(jìn)程必須等待當(dāng)緩沖池已空時(shí)，消費(fèi)者進(jìn)程應(yīng)等待互斥：所有進(jìn)程應(yīng)互斥使用緩沖池這一臨界資源。91.用記錄型信號量解決

Semaphoreempty=n,full=0；empty表示空緩沖個(gè)數(shù)，初值為n；full表示滿緩沖個(gè)數(shù)，初值為0。互斥使用臨界區(qū)的信號量mutex，初值為1。101.用記錄型信號量解決

Semaphoreempty=n,full=0,mutex;item=buffer[n];intin=0,out=0;Main(){cobeginproducer();consumer();

coend}11生產(chǎn)者producer(){do{

produceaniteminnextp;┋wait(empty);/*申請空緩沖區(qū)*/wait(mutex);/*實(shí)現(xiàn)對緩沖池的互斥使用*/

buffer[in]=nextp;in=(in+1)%n;signal(mutex);signal(full);/*滿緩沖區(qū)的個(gè)數(shù)加1*/}while(TRUE)}重點(diǎn)掌握！12消費(fèi)者consumer(){

do{wait(full);/*申請滿緩沖區(qū)*/wait(mutex);

/*實(shí)現(xiàn)互斥*/nextc=buffer[out];out=(out+1)modn;signal(mutex);signal(empty);/*空緩沖區(qū)的個(gè)數(shù)加1*/consumetheiteminnextc;┋}while(TRUE);}重點(diǎn)掌握！132.

用AND信號量解決對于生產(chǎn)者—消費(fèi)者問題，也可利用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)

14Producer(){repeat┋produceaniteminnextp;┋

Swait(empty,mutex);buffer[in]=nextp;in=[in+1]%n;

Ssignal(mutex,full);untilfalse;}Consumer(){repeatSwait(mutex,full);nextc=buffer[out];out=(out+1)%n;Ssignal(mutex,empty);consumetheiteminnextc;┋untilfalse;}152.5.2哲學(xué)家進(jìn)餐問題5個(gè)哲學(xué)家圍坐在圓桌旁，每人面前有一只空盤子，每2人之間放一只筷子:放在桌子上的筷子是臨界資源，可用一個(gè)信號量表示一只筷子，五個(gè)信號量構(gòu)成信號量數(shù)組。Semaphorechopstick[5]={1,1,1,1,1}；為了就餐，每個(gè)哲學(xué)家必須拿到兩只筷子，并且只能直接從自己的左邊或右邊去取筷子。

[?s?m??f?r]16

1.

利用記錄型信號量解決第i位哲學(xué)家的活動(dòng)可描述為：Semaphorechopstick[5]={1,1,1,1,1}；repeatwait(chopstick[i]);//取左邊筷子wait(chopstick[(i+1)%5]);

//取右邊筷子┋eat;┋signal(chopstick[i]);signal(chopstick[(i+1)%5]);┋

think;untilfalse;

會(huì)死鎖否？17

哲學(xué)家進(jìn)餐問題哲學(xué)家饑餓時(shí)，總是先去拿左邊的筷子(wait(chopstick[i]))；成功后，再去拿他右邊的筷子(wait(chopstick[(i+1)mod5]))；又成功后便可進(jìn)餐。進(jìn)餐完畢，則先放下左邊的筷子，然后再放右邊的筷子。上述解法可保證不會(huì)有兩個(gè)相鄰的哲學(xué)家同時(shí)進(jìn)餐，但有可能引起死鎖。

18假如五位哲學(xué)家同時(shí)饑餓而各自拿起左邊的筷子時(shí)，就會(huì)使五個(gè)信號量chopstick均為0；當(dāng)他們再試圖去拿右邊的筷子時(shí)，都將因無筷子可拿而無限期地等待。幾種解決方法

:死鎖的情況19至多允許4個(gè)哲學(xué)家進(jìn)餐能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在進(jìn)餐完畢時(shí)能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。規(guī)定哲學(xué)家拿起筷子的次序給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之。1、2號哲學(xué)家競爭1號筷子，則3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。202.

用AND信號量解決varchopstick:array[0..4]ofsemaphore:=(1,1,1,1,1);

repeatthink;swait(chopstick[(i+1)%5],chopstick[i]);eat;signal(chopstick[(i+1)%5],chopstick[i]);

untilfalse;在哲學(xué)家進(jìn)餐問題中，每個(gè)哲學(xué)家先獲得2臨界資源(筷子)方能進(jìn)餐，用AND信號量機(jī)制可獲得最簡潔的解法212.5.3

“讀者—寫者”問題“讀者一寫者(Reader—WriterProblem)問題”:保證一個(gè)Writer進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象。Example:222.5.3

“讀者—寫者”解決方案讀者一寫者的同步要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作1.用記錄型信號量解決2.用信號量集機(jī)制解決Writer在不能同時(shí)231.用記錄型信號量解決

讀者--寫者問題有兩種類型：讀者優(yōu)先當(dāng)寫者提出寫的要求后，允許新的讀者繼續(xù)進(jìn)入寫者優(yōu)先當(dāng)寫者提出寫的要求后，不允許新的讀者進(jìn)入24讀者--寫者問題的信號量設(shè)置：為實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號量Wmutex。設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)目，也應(yīng)該為它設(shè)置一個(gè)互斥信號量rmutex。當(dāng)Readcount=0，表示無讀者進(jìn)程在讀，讀者進(jìn)程需要執(zhí)行Wait(Wmutex)操作。若成功，讀者進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。僅當(dāng)讀者進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時(shí)，才須執(zhí)行signal(Wmutex)操作，以便讓寫者進(jìn)程寫。25用記錄型信號量解決

讀者reader:

beginrepeatwait(rmutex);if(readcount=0)then

wait(wmutex);readcount=readcount+1;signal(rmutex);┋performreadoption;讀操作┋wait(rmutex);readcount=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);

untilfalse;end

semaphorermutex=1,wmutex=1;intReadcount=0;

wmutex:讀寫互斥rmutex:互斥訪問readcountReadcount:讀進(jìn)程數(shù)重點(diǎn)掌握！26寫者writer:

beginrepeat

wait(wmutex);performwriteoption;寫操作

signal(wmutex);┋untilfalse;end272.

用信號量集機(jī)制解決引入一個(gè)信號量L，并賦予其初值為RN，通過執(zhí)行wait(L，1，1)操作來控制讀者的數(shù)目wait(S，d，t)操作來:S為信號量，總資源數(shù)量d為需求值，運(yùn)轉(zhuǎn)所需量t為下線,s>t時(shí)方能啟動(dòng)P66282.

用信號量集機(jī)制解決與前面的略有不同，增加一個(gè)限制，即最多只允許RN個(gè)讀者同時(shí)讀。引入一個(gè)信號量L，并賦予其初值為RN，通過執(zhí)行wait(L，1，1)操作來控制讀者的數(shù)目當(dāng)有一個(gè)讀者進(jìn)入，執(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)操作失敗而阻塞。L=0時(shí)表示不允許讀者進(jìn)入L=RN時(shí)表示寫者可以進(jìn)入29varRN:integer;L,mx:semaphore:=RN,1;reader:

beginrepeat

swait(L,1,1);

swait(mx,1,0);┋performreadoption;┋

ssignal(L,1);untilfalse;end

writer:beginrepeat

swait(mx,1,1;L,RN,0);┋performwriteoption;┋

ssignal(mx,1);┋untilfalse;end30Now,theproblemsare:信號量機(jī)制

進(jìn)程必須自備同步操作wait(s)和signal(s)

wait(s)和signal(s)分布在進(jìn)程中

同步操作使用不當(dāng)，造成死鎖同步操作使用問題

wait(s)和signal(s)顛倒

多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)

signal(s)誤寫成wait(s)

其它不能進(jìn)入臨界區(qū)

遺漏

wait(s)

幾個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)

signal(s)

其它進(jìn)程無法進(jìn)入臨界區(qū)煩，暈,誰來幫幫我?31I’m

themonitor，coming!

(管程,

similarto“城管”：誰在掐架？）Comeon!Itcan‘tgowrongeverytime...33

管程機(jī)制

1.管程的定義2.

管程的語法描述3.

條件變量解決方法：把對臨界資源的同步操作集中起來，由一個(gè)進(jìn)程統(tǒng)一管理

341.“管程”長啥樣的？

系統(tǒng)資源抽象數(shù)據(jù)結(jié)構(gòu)

（軟件硬件）（表示信息操作）

電傳機(jī)：狀態(tài)(忙、閑)、請求/釋放操作、等待隊(duì)列

FIFO隊(duì)列：隊(duì)首、隊(duì)尾、隊(duì)長、隊(duì)列操作

緩沖池：大小、指針(空滿)、放入/獲取操作351.“管程”長啥樣的？一組表征資源的共享數(shù)據(jù)結(jié)構(gòu)

對共享數(shù)據(jù)結(jié)構(gòu)操作的一組過程管程

管程被請求和釋放資源的進(jìn)程所調(diào)用共同數(shù)據(jù)一組操作過程初始化代碼……進(jìn)入隊(duì)列362.7

線程線程的基本概念線程間的同步和通信內(nèi)核支持線程和用戶級線程線程控制20世紀(jì)60年代提出進(jìn)程后，OS中都是以進(jìn)程作為擁有資源和獨(dú)立運(yùn)行的基本單位。80年代中期，提出比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位----線程(Threads);好處：減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使OS具有更好的并發(fā)性。37Compariedwith進(jìn)程協(xié)同完成一個(gè)任務(wù)具體工作人員，多人共享相同空間（資源）進(jìn)程線程381.

線程的引入現(xiàn)代操作系統(tǒng)中，進(jìn)程只作為資源擁有者，而調(diào)度和運(yùn)行的屬性賦予新的實(shí)體——線程。引入線程，為減少程序并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使OS具有更好的并發(fā)性。進(jìn)程的兩個(gè)基本屬性:①進(jìn)程是一個(gè)可擁有資源的獨(dú)立單位；②進(jìn)程同時(shí)又是一個(gè)可獨(dú)立調(diào)度和分派的基本單位P7539如何能使多個(gè)程序更好地并發(fā)執(zhí)行同時(shí)又盡量減少系統(tǒng)的開銷?是追求的重要目標(biāo)。解決方法：搬房子累，搬人！好處:(1)對于作為調(diào)度和分派的基本單位，不擁有資源，可“輕裝上陣”；(2)對擁有資源的基本單位，又不對其進(jìn)行頻繁的切換。40在這個(gè)想法下，誕生了“線程”

先把“房子+人”區(qū)分開：將進(jìn)程的兩個(gè)屬性分開，由操作系統(tǒng)分開處理。41進(jìn)程線程調(diào)度獨(dú)立調(diào)度、分派的基本單位線程為調(diào)度分派的基本單位進(jìn)程為擁有資源的基本單位并發(fā)性僅進(jìn)程間可以并發(fā)執(zhí)行進(jìn)程和線程都可以并發(fā)執(zhí)行擁有資源擁有資源的獨(dú)立單位不擁有系統(tǒng)資源，但可以訪問其隸屬進(jìn)程的資源系統(tǒng)開銷創(chuàng)建或撤消進(jìn)程時(shí)開銷較大切換代價(jià)高線程創(chuàng)建或撤消時(shí)開銷很小切換代價(jià)低支持多處理機(jī)若進(jìn)程只有一個(gè)線程，則只能運(yùn)行在一個(gè)處理機(jī)上若進(jìn)程擁有多個(gè)線程，則可分散到多個(gè)處理機(jī)上運(yùn)行2.7.2.

線程和進(jìn)程的比較P76重點(diǎn)掌握！421.輕型實(shí)體基本上不擁有系統(tǒng)資源，只有一點(diǎn)必不可少的、能保證獨(dú)立運(yùn)行的資源2.獨(dú)立調(diào)度和分派的基本單位線程是能獨(dú)立運(yùn)行的基本單位，因而也是獨(dú)立調(diào)度和分派的基本單位。線程很“輕”，線程的切換非常迅速/開銷小。3.可并發(fā)執(zhí)行

一個(gè)進(jìn)程中的多個(gè)線程間可并發(fā)執(zhí)行；不同進(jìn)程中的線程也能并發(fā)執(zhí)行。4.共享進(jìn)程資源

同一進(jìn)程中的各個(gè)線程，可以共享該進(jìn)程所擁有的資源（有相同的地址空間；訪問進(jìn)程所擁有文件、定時(shí)器、信號量機(jī)構(gòu)等）。

線程的特點(diǎn)43用戶棧系統(tǒng)棧PCB數(shù)據(jù)程序單線程進(jìn)程寄存器PCB數(shù)據(jù)程序多線程進(jìn)程用戶棧系統(tǒng)棧

TCB寄存器用戶棧系統(tǒng)棧

TCB寄存器用戶棧系統(tǒng)棧

TCB寄存器線程1線程2線程3進(jìn)程進(jìn)程44多線程和進(jìn)程模型

多線程是指操作系統(tǒng)支持在一個(gè)進(jìn)程中執(zhí)行多個(gè)線程的能力。每個(gè)進(jìn)程中只有一個(gè)線程在執(zhí)行，稱作單線程方法（MS-DOS）;WINDOWS2000/XP、SOLARIS、LINUX等支持多線程的多進(jìn)程。在多線程的環(huán)境中，進(jìn)程被定義成資源分配的實(shí)體和保護(hù)的實(shí)體。45狀態(tài)參數(shù)每個(gè)線程都可以用線程標(biāo)識(shí)符和一組狀態(tài)參數(shù)進(jìn)行描述。①寄存器狀態(tài)②堆棧③運(yùn)行狀態(tài)

④優(yōu)先級⑤專有存儲(chǔ)器⑥信號屏蔽線程運(yùn)行狀態(tài)線程間也存在著共享資源和相互合作的制約關(guān)系，在運(yùn)行時(shí)也具有間斷性。三種基本狀態(tài)：執(zhí)行狀態(tài)、就緒狀態(tài)、阻塞狀態(tài)線程的創(chuàng)建和終止應(yīng)用程序啟動(dòng)時(shí)，通常僅有一個(gè)線程在執(zhí)行，該線程被稱為“初始化線程”。它可根據(jù)需要再去創(chuàng)建若干個(gè)線程。2.7.3.

線程的狀態(tài)和TCB461.線程標(biāo)識(shí)符每個(gè)線程有唯一標(biāo)示符2.一組寄存器保存程序計(jì)數(shù)器PC。3.線程運(yùn)行狀態(tài)三種基本狀態(tài)4.優(yōu)先級、線程專用存儲(chǔ)區(qū)、信號屏蔽、堆棧指針。。。

2.線程控制塊TCBP7847在多線程OS中，進(jìn)程是作為擁有系統(tǒng)資源的基本單位，通常的進(jìn)程都包含多個(gè)線程并為它們提供資源，但進(jìn)程不再作為一個(gè)執(zhí)行的實(shí)體。多線程OS中的進(jìn)程有以下屬性：擁有系統(tǒng)分配的資源單位用戶地址空間、進(jìn)程間和線程間同步和通信的機(jī)制、打開的文件和已申請到的I/O設(shè)備、地址映射表等?？砂ǘ鄠€(gè)線程

可含有多個(gè)相對獨(dú)立的線程，但至少要有一個(gè)線程；進(jìn)程為線程提供資源及運(yùn)行環(huán)境，使線程可并發(fā)執(zhí)行。

進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體

進(jìn)程仍有與執(zhí)行相關(guān)的狀態(tài)。進(jìn)程“執(zhí)行”狀態(tài)實(shí)際上是指該進(jìn)程中的某線程正在執(zhí)行。進(jìn)程掛起時(shí)，該進(jìn)程中的所有線程也都將被掛起；進(jìn)程激活時(shí)，屬于該進(jìn)程的所有線程也都將被激活。3．多線程OS中的進(jìn)程48線程的實(shí)現(xiàn)多線程若想有條不紊地運(yùn)行，系統(tǒng)必提供用于實(shí)現(xiàn)線程同步和通信的機(jī)制。為支持不同頻率的交互操作、不同程度的并行性，常需提供多種同步機(jī)制，如互斥鎖、條件變量、信號量以及多讀、單寫鎖等1．互斥鎖(mutex)2．條件變量3．信號量機(jī)制（私用信號量、公用信號量）491．互斥鎖(mutex)

互斥鎖是一種用于實(shí)現(xiàn)線程間對資源互斥訪問的機(jī)制。操作互斥鎖時(shí)空開銷低，因而較適合于高頻度使用的關(guān)鍵共享數(shù)據(jù)和程序段。互斥鎖可以有兩種狀態(tài)，即開鎖(unlock)和關(guān)鎖(lock)狀態(tài)。相應(yīng)地，可用兩條命令(函數(shù))對互斥鎖進(jìn)行操作。其中的關(guān)鎖lock操作用于將mutex關(guān)上，開鎖操作unlock則用于打開mutex。50

內(nèi)核支持線程和用戶級線程線程在各系統(tǒng)的實(shí)現(xiàn)方式不完全相同。一些數(shù)據(jù)庫管理系統(tǒng)（如infomix），實(shí)現(xiàn)的是用戶級線程如Macintosh、Windows和0S/2操作系統(tǒng)實(shí)現(xiàn)的是內(nèi)核支持線程；Solaris操作系統(tǒng)（UNIX操作系統(tǒng)的衍生版本之一）同時(shí)實(shí)現(xiàn)了這兩種類型的線程。KernelSupportedThreadsUserLeverThreadsP79重點(diǎn)掌握！51內(nèi)核支持線程和用戶級線程Simlarto:國家統(tǒng)一分配?！罢o錢；快，多生孩子！孩子越多，咱家錢的總數(shù)越多。”Similarto:已分發(fā)到單位（進(jìn)程），再由單位分配給個(gè)人（線程）?！霸奂揖湍敲袋c(diǎn)有限的錢，多生娃，難養(yǎng)活”線程越多，速度越快線程越多，速度不變52依賴于OS核心，由內(nèi)核的內(nèi)部需求進(jìn)行創(chuàng)建和撤銷，用來執(zhí)行一個(gè)指定的函數(shù):內(nèi)核維護(hù)進(jìn)程和線程的上下文信息；線程切換由內(nèi)核完成；一個(gè)線程阻塞，不會(huì)影響其他線程的運(yùn)行。時(shí)間片分配給線程，所以多線程的進(jìn)程獲得更多CPU時(shí)間。1.

內(nèi)核支持線程(KernelSupportedThreads)53KST線程實(shí)現(xiàn)的4優(yōu)點(diǎn):在多處理器系統(tǒng)中，內(nèi)核能夠同時(shí)調(diào)度