1第二章進程控制與描述2.5經典進程同步問題2.6進程通信2.7線程的基本概念2.8線程的實現22.5

經典進程的同步問題

1.生產者—消費者問題2.哲學家進餐問題3.讀者—寫者問題通過對經典問題的研究和學習，可以幫助我們更好地理解進程同步的概念及實現方法P6032.5.1生產者—消費者問題

Producer-consumerproblem，又稱有限緩沖問題（Bounded-bufferproblem)兩個共享固定大小緩沖區的進程—“生產者”和“消費者”42.5.1生產者—消費者問題

Theyare,相互合作進程關系1.用記錄型信號量解決

2.

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

5單緩沖區情況單緩沖區的同步問題

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

：while(true){

生產一個產品;

P(empty);

送產品到緩沖區;

V(full);};Consumer：while(true){P(full);從緩沖區取產品;

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

同步當緩沖池已放滿產品時，生產者進程必須等待當緩沖池已空時，消費者進程應等待互斥：所有進程應互斥使用緩沖池這一臨界資源。91.用記錄型信號量解決

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

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

coend}11生產者producer(){do{

produceaniteminnextp;┋wait(empty);/*申請空緩沖區*/wait(mutex);/*實現對緩沖池的互斥使用*/

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

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

/*實現互斥*/nextc=buffer[out];out=(out+1)modn;signal(mutex);signal(empty);/*空緩沖區的個數加1*/consumetheiteminnextc;┋}while(TRUE);}重點掌握！132.

用AND信號量解決對于生產者—消費者問題，也可利用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哲學家進餐問題5個哲學家圍坐在圓桌旁，每人面前有一只空盤子，每2人之間放一只筷子:放在桌子上的筷子是臨界資源，可用一個信號量表示一只筷子，五個信號量構成信號量數組。Semaphorechopstick[5]={1,1,1,1,1}；為了就餐，每個哲學家必須拿到兩只筷子，并且只能直接從自己的左邊或右邊去取筷子。

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

1.

利用記錄型信號量解決第i位哲學家的活動可描述為：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;

會死鎖否？17

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

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

:死鎖的情況19至多允許4個哲學家進餐能保證至少有一位哲學家能夠進餐，并在進餐完畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。規定哲學家拿起筷子的次序給所有哲學家編號，奇數號的哲學家必須首先拿左邊的筷子，偶數號的哲學家則反之。1、2號哲學家競爭1號筷子，則3、4號哲學家競爭3號筷子。即五位哲學家都先競爭奇數號筷子，獲得后，再去競爭偶數號筷子，最后總會有一位哲學家能獲得兩只筷子而進餐。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;在哲學家進餐問題中，每個哲學家先獲得2臨界資源(筷子)方能進餐，用AND信號量機制可獲得最簡潔的解法212.5.3

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

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

讀者--寫者問題有兩種類型：讀者優先當寫者提出寫的要求后，允許新的讀者繼續進入寫者優先當寫者提出寫的要求后，不允許新的讀者進入24讀者--寫者問題的信號量設置：為實現Reader與Writer進程間在讀或寫時的互斥而設置了一個互斥信號量Wmutex。設置一個整型變量Readcount表示正在讀的進程數目，也應該為它設置一個互斥信號量rmutex。當Readcount=0，表示無讀者進程在讀，讀者進程需要執行Wait(Wmutex)操作。若成功，讀者進程便可去讀，相應地，做Readcount+1操作。僅當讀者進程在執行了Readcount減1操作后其值為0時，才須執行signal(Wmutex)操作，以便讓寫者進程寫。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:讀進程數重點掌握！26寫者writer:

beginrepeat

wait(wmutex);performwriteoption;寫操作

signal(wmutex);┋untilfalse;end272.

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

用信號量集機制解決與前面的略有不同，增加一個限制，即最多只允許RN個讀者同時讀。引入一個信號量L，并賦予其初值為RN，通過執行wait(L，1，1)操作來控制讀者的數目當有一個讀者進入，執行wait(L，1，1)操作，使L的值減1。當有RN個讀者進入讀后，L便減為0，第RN+1個讀者要進入讀時，必然會因wait(L，1，1)操作失敗而阻塞。L=0時表示不允許讀者進入L=RN時表示寫者可以進入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:信號量機制

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

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

同步操作使用不當，造成死鎖同步操作使用問題

wait(s)和signal(s)顛倒

多個進程同時進入臨界區

signal(s)誤寫成wait(s)

其它不能進入臨界區

遺漏

wait(s)

幾個進程同時進入臨界區

signal(s)

其它進程無法進入臨界區煩，暈,誰來幫幫我?31I’m

themonitor，coming!

(管程,

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

管程機制

1.管程的定義2.

管程的語法描述3.

條件變量解決方法：把對臨界資源的同步操作集中起來，由一個進程統一管理

341.“管程”長啥樣的？

系統資源抽象數據結構

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

電傳機：狀態(忙、閑)、請求/釋放操作、等待隊列

FIFO隊列：隊首、隊尾、隊長、隊列操作

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

對共享數據結構操作的一組過程管程

管程被請求和釋放資源的進程所調用共同數據一組操作過程初始化代碼……進入隊列362.7

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

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

先把“房子+人”區分開：將進程的兩個屬性分開，由操作系統分開處理。41進程線程調度獨立調度、分派的基本單位線程為調度分派的基本單位進程為擁有資源的基本單位并發性僅進程間可以并發執行進程和線程都可以并發執行擁有資源擁有資源的獨立單位不擁有系統資源，但可以訪問其隸屬進程的資源系統開銷創建或撤消進程時開銷較大切換代價高線程創建或撤消時開銷很小切換代價低支持多處理機若進程只有一個線程，則只能運行在一個處理機上若進程擁有多個線程，則可分散到多個處理機上運行2.7.2.

線程和進程的比較P76重點掌握！421.輕型實體基本上不擁有系統資源，只有一點必不可少的、能保證獨立運行的資源2.獨立調度和分派的基本單位線程是能獨立運行的基本單位，因而也是獨立調度和分派的基本單位。線程很“輕”，線程的切換非常迅速/開銷小。3.可并發執行

一個進程中的多個線程間可并發執行；不同進程中的線程也能并發執行。4.共享進程資源

同一進程中的各個線程，可以共享該進程所擁有的資源（有相同的地址空間；訪問進程所擁有文件、定時器、信號量機構等）。

線程的特點43用戶棧系統棧PCB數據程序單線程進程寄存器PCB數據程序多線程進程用戶棧系統棧

TCB寄存器用戶棧系統棧

TCB寄存器用戶棧系統棧

TCB寄存器線程1線程2線程3進程進程44多線程和進程模型

多線程是指操作系統支持在一個進程中執行多個線程的能力。每個進程中只有一個線程在執行，稱作單線程方法（MS-DOS）;WINDOWS2000/XP、SOLARIS、LINUX等支持多線程的多進程。在多線程的環境中，進程被定義成資源分配的實體和保護的實體。45狀態參數每個線程都可以用線程標識符和一組狀態參數進行描述。①寄存器狀態②堆棧③運行狀態

④優先級⑤專有存儲器⑥信號屏蔽線程運行狀態線程間也存在著共享資源和相互合作的制約關系，在運行時也具有間斷性。三種基本狀態：執行狀態、就緒狀態、阻塞狀態線程的創建和終止應用程序啟動時，通常僅有一個線程在執行，該線程被稱為“初始化線程”。它可根據需要再去創建若干個線程。2.7.3.

線程的狀態和TCB461.線程標識符每個線程有唯一標示符2.一組寄存器保存程序計數器PC。3.線程運行狀態三種基本狀態4.優先級、線程專用存儲區、信號屏蔽、堆棧指針。。。

2.線程控制塊TCBP7847在多線程OS中，進程是作為擁有系統資源的基本單位，通常的進程都包含多個線程并為它們提供資源，但進程不再作為一個執行的實體。多線程OS中的進程有以下屬性：擁有系統分配的資源單位用戶地址空間、進程間和線程間同步和通信的機制、打開的文件和已申請到的I/O設備、地址映射表等。可包括多個線程

可含有多個相對獨立的線程，但至少要有一個線程；進程為線程提供資源及運行環境，使線程可并發執行。

進程不是一個可執行的實體

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

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

內核支持線程和用戶級線程線程在各系統的實現方式不完全相同。一些數據庫管理系統（如infomix），實現的是用戶級線程如Macintosh、Windows和0S/2操作系統實現的是內核支持線程；Solaris操作系統（UNIX操作系統的衍生版本之一）同時實現了這兩種類型的線程。KernelSupportedThreadsUserLeverThreadsP79重點掌握！51內核支持線程和用戶級線程Simlarto:國家統一分配。“政府給錢；快，多生孩子！孩子越多，咱家錢的總數越多。”Similarto:已分發到單位（進程），再由單位分配給個人（線程）。“咱家就那么點有限的錢，多生娃，難養活”線程越多，速度越快線程越多，速度不變52依賴于OS核心，由內核的內部需求進行創建和撤銷，用來執行一個指定的函數:內核維護進程和線程的上下文信息；線程切換由內核完成；一個線程阻塞，不會影響其他線程的運行。時間片分配給線程，所以多線程的進程獲得更多CPU時間。1.

內核支持線程(KernelSupportedThreads)53KST線程實現的4優點:在多處理器系統中，內核能夠同時調度