第二章 進程線程管理

第二章進程線程管理第二章進程線程管理第二章進程線程管理第二章進程(線程)管理本章內容2.1進程的基本概念2.2進程控制2.3進程同步2.4進程通信2.5線程2.1進程的基本概念2.1.1程序執(zhí)行過程1．前趨圖2.1進程的基本概念2．順序執(zhí)行及其特征

程序順序執(zhí)行具有如下特征。（1）順序性。處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行,每一操作必須在上一操作結束之后才能開始。（2）封閉性。程序在封閉環(huán)境下運行，獨占系統(tǒng)所有資源。即程序一旦開始運行，其執(zhí)行結果不受其它程序和外界因素影響。（3）可再現(xiàn)性。只要程序執(zhí)行時的初始條件和執(zhí)行環(huán)境相同,程序重復執(zhí)行時獲得完全相同結果。2.1進程的基本概念3．并發(fā)執(zhí)行及其特征

2.1進程的基本概念

并發(fā)執(zhí)行的多個程序的特征：（1）間斷性。程序在執(zhí)行過程中，由于等待資源或及其它程序協(xié)作完成任務，每個程序的執(zhí)行過程往往不是“一氣呵成”，而是呈現(xiàn)出“執(zhí)行－暫停－執(zhí)行”的間斷性活動規(guī)律。（2）失去封閉性。程序并發(fā)執(zhí)行時,多個程序共享系統(tǒng)資源,系統(tǒng)資源的狀態(tài)將由多個程序改變。即一個程序在運行時，其運行環(huán)境會受其它程序的影響，失去了順序執(zhí)行的封閉性。2.1進程的基本概念

（3）相互作用和制約性。并發(fā)執(zhí)行程序既有相互獨立的一面，表現(xiàn)為每個程序為用戶提供特定的功能，它們之間相互獨立；也有時也會直接或間接制約的一面。（4）不可再現(xiàn)性。程序并發(fā)執(zhí)行時,由于失去了封閉性,導致其失去可再現(xiàn)性。即使初始條件相同，程序多次執(zhí)行的結果也可能不同。2.1進程的基本概念例1：有兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N∶=N+1操作；程序B每執(zhí)行一次時，都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運行。

(1)N∶=N+1在Print(N)和N∶=0之前，此時得到的N值分別為n+1,n+1,0。

(2)N∶=N+1在Print(N)和N∶=0之后，此時得到的N值分別為n,0,1。

(3)N∶=N+1在Print(N)和N∶=0之間，此時得到的N值分別為n,n+1,0。2.1進程的基本概念例2：假設某飛機定票系統(tǒng)在t0時刻有A、B、C、D四個終端程序同時都要對機票庫中的某航班當前剩余票數X進行操作。如果每個終端程序的當前定票需求為N，并對共享變量X進行如下操作：在機票數據庫中取出當前剩余票數X；判斷X>0（有票嗎）？如果有，X≥N（票夠嗎）？如果夠，則出票（打印票據）；X＝X－N（修改剩余票數）；將X回寫到數據庫中；2.1.2進程的定義和特征

1.為何引入進程從程序并發(fā)執(zhí)行角度和系統(tǒng)資源共享角度分析一下引入進程的必要性。（1）程序并發(fā)執(zhí)行角度（2）系統(tǒng)資源共享角度2.1.2進程的定義和特征

2.進程的定義進程是一個可并發(fā)執(zhí)行的具有獨立功能的程序在某個數據集合的一次執(zhí)行過程，它也是操作系統(tǒng)進行資源分配和保護的基本單位。為了更好的描述和管理并發(fā)執(zhí)行的多個進程，操作系統(tǒng)中為每個進程配置了一個進程控制塊PCB（ProcessControlBlock）。2.1.2進程的定義和特征

3.進程的構成進程包括程序，數據和PCB2.1.2進程的定義和特征

4.進程的上下文進程的物理實體和支持進程運行的環(huán)境合稱為進程上下文（ProcessContext）。進程在進程上下文中執(zhí)行。進程上下文包括用戶級上下文、系統(tǒng)級上下文和寄存器上下文。當一個進程被系統(tǒng)調度而占用處理機時，發(fā)生進程切換，切換的內容主要是進程上下文。2.1.2進程的定義和特征

5.進程的特征進程具有如下特征：（1）動態(tài)性（2）共享性（3）并發(fā)性（4）獨立性（5）異步性 2.1.2進程的定義和特征6.進程和程序的區(qū)別①進程和程序的最大區(qū)別就是進程是程序的一次執(zhí)行過程，它是一個動態(tài)概念。程序是一個靜態(tài)概念。②進程能夠并發(fā)執(zhí)行。③進程是資源分配和獨立運行的基本單位，而程序不是。④進程由含有代碼和數據的用戶地址空間、進程控制塊和執(zhí)行棧區(qū)等部分組成，而程序只是靜態(tài)代碼。⑤進程和程序之間是多對多的關系。一個程序可被多個進程共用，一個進程在其活動中又可調用若干個程序。2.1.3進程狀態(tài)和進程轉換1.進程的3種基本狀態(tài)進程執(zhí)行時的間斷性決定了進程可能具有多種狀態(tài)。事實上，運行中的進程可能具有以下三種基本狀態(tài)。2.1.3進程狀態(tài)和進程轉換1)就緒(Ready)狀態(tài)當進程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執(zhí)行，進程這時的狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中處于就緒狀態(tài)的進程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。2)執(zhí)行狀態(tài)進程已獲得CPU，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只有一個進程處于執(zhí)行狀態(tài)；在多處理機系統(tǒng)中，則有多個進程處于執(zhí)行狀態(tài)。2.1.3進程狀態(tài)和進程轉換3)阻塞狀態(tài)正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，亦即進程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)，有時也稱為等待狀態(tài)或封鎖狀態(tài)。致使進程阻塞的典型事件有：請求I/O，申請緩沖空間等。通常將這種處于阻塞狀態(tài)的進程也排成一個隊列。有的系統(tǒng)則根據阻塞原因的不同而把處于阻塞狀態(tài)的進程排成多個隊列。2.1.3進程狀態(tài)和進程轉換執(zhí)行就緒阻塞時間片到進程調度I/O請求I/O完成2.1.3進程狀態(tài)和進程轉換2.創(chuàng)建和終止狀態(tài)

2.1.3進程狀態(tài)和進程轉換3.掛起1)引入掛起的原因在不少系統(tǒng)中進程只有上述三種狀態(tài)，但在另一些系統(tǒng)中，又增加了一些新狀態(tài)，最重要的是掛起狀態(tài)。引入掛起狀態(tài)的原因有：(1)終端用戶的請求(2)父進程請求(3)負荷調節(jié)的需要(4)操作系統(tǒng)的需要2.1.3進程狀態(tài)和進程轉換2)進程狀態(tài)的轉換在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)(又稱為靜止狀態(tài))到非掛起狀態(tài)(又稱為活動狀態(tài))的轉換；或者相反。此時把狀態(tài)細分為：運行態(tài)活動就緒、靜止就緒活動阻塞、靜止阻塞可有以下幾種狀態(tài)轉換情況：(1)活動就緒→靜止就緒。當進程處于未被掛起的就緒狀態(tài)時，稱此為活動就緒狀態(tài)，表示為Readya。當用掛起原語Suspend將該進程掛起后，該進程便轉變?yōu)殪o止就緒狀態(tài)，表示為Readys，處于Readys狀態(tài)的進程不再被調度執(zhí)行。2.1.3進程狀態(tài)和進程轉換(2)活動阻塞→靜止阻塞。當進程處于未被掛起的阻塞狀態(tài)時，稱它是處于活動阻塞狀態(tài)，表示為Blockeda。當用Suspend原語將它掛起后，進程便轉變?yōu)殪o止阻塞狀態(tài)，表示為Blockeds。處于該狀態(tài)的進程在其所期待的事件出現(xiàn)后，將從靜止阻塞變?yōu)殪o止就緒。(3)靜止就緒→活動就緒。處于Readys狀態(tài)的進程，若用激活原語Active激活后，該進程將轉變?yōu)镽eadya狀態(tài)。(4)靜止阻塞→活動阻塞。處于Blockeds狀態(tài)的進程，若用激活原語Active激活后，該進程將轉變?yōu)锽lockeda狀態(tài)。下圖示出了具有掛起狀態(tài)的進程狀態(tài)圖。2.1.3進程狀態(tài)和進程轉換3.掛起操作

執(zhí)行活動就緒活動阻塞時間片到進程調度I/O請求I/O完成內存外存靜止就緒靜止阻塞I/O完成掛起掛起激活激活2.1.4進程控制塊及其組織方式

1.進程控制塊的作用進程控制塊的具體作用如下：（1）PCB是進程在系統(tǒng)中存在的唯一標識。（2）保存CPU現(xiàn)場信息。（3）提供進程管理所需信息。（4）提供進程調度所需信息。（5）實現(xiàn)及其它進程的同步和通信。2.1.4進程控制塊及其組織方式

2.進程控制塊的信息

進程控制塊包含下述4類信息：（1）進程標識信息。（2）進程說明信息。（3）處理機狀態(tài)信息。（4）進程的控制信息。

2.1.4進程控制塊及其組織方式

3.進程控制塊的組織方式常用的PCB組織方式有以下三種：（1）線性方式（2）鏈接方式。2.1.4進程控制塊及其組織方式

3.進程控制塊的組織方式（3）索引方式重點回顧進程的定義和特征進程狀態(tài)就緒(Ready)狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)掛起執(zhí)行重點回顧就緒阻塞時間片到進程調度I/O請求I/O完成重點回顧執(zhí)行活動就緒活動阻塞時間片到進程調度I/O請求I/O完成內存外存靜止就緒靜止阻塞I/O完成掛起掛起激活激活2.2進程控制2.2.1進程創(chuàng)建系統(tǒng)中導致創(chuàng)建新進程的典型事件：①操作系統(tǒng)初始化。當操作系統(tǒng)啟動時，通常會創(chuàng)建若干進程，特別是創(chuàng)建一些常駐系統(tǒng)進程。②作業(yè)調度。多道批處理系統(tǒng)中，當作業(yè)調度程序選中某個作業(yè)時，將其裝入內存，為其創(chuàng)建進程，并把創(chuàng)建好的進程插入到就緒進程隊列。③提供服務。當某一進程向操作系統(tǒng)提出某種服務請求時，系統(tǒng)將專門創(chuàng)建一個進程來提供其所要求的服務。④應用請求。當用戶向系統(tǒng)提出某種應用請求時，系統(tǒng)為其創(chuàng)建新進程。2.2.1進程創(chuàng)建進程的創(chuàng)建(CreationofProcess)過程一旦操作系統(tǒng)發(fā)現(xiàn)了要求創(chuàng)建新進程的事件后，便調用進程創(chuàng)建原語Creat()按下述步驟創(chuàng)建一個新進程。(1)申請空白PCB。為新進程申請獲得惟一的數字標識符，并從PCB集合中索取一個空白PCB。(2)為新進程分配資源。為新進程的程序和數據，以及用戶棧分配必要的內存空間。(3)初始化進程控制塊。(4)將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程，便將新進程插入就緒隊列。入口圖創(chuàng)建原語流圖2.2.2進程執(zhí)行及進程切換系統(tǒng)進行進程切換時通常進行如下工作：①保存被中斷進程的處理器現(xiàn)場信息；②修改當前運行進程的PCB，將運行狀態(tài)改為其他狀態(tài)，并把它插入到相應的PCB隊列中；③選擇另一個進程運行，并修改該進程的PCB，使其狀態(tài)變?yōu)檫\行態(tài)；④將當前進程存儲管理數據修改為新選進程的存儲管理數據；⑤恢復被選進程上次切換出處理機時的處理機現(xiàn)場，開始運行該進程。1、引起進程阻塞和喚醒的事件請求系統(tǒng)服務：正在執(zhí)行的程序請求操作系統(tǒng)服務，但是由于某種原因操作系統(tǒng)沒有立即滿足該進程的要求，該進程只能轉變?yōu)樽枞麪顟B(tài)來等待。啟動某操作：當進程啟動某種操作后，如果該進程必須在該操作完成之后才能繼續(xù)執(zhí)行，所有必須先使進程阻塞。新數據尚未到達無新工作可做：系統(tǒng)往往設置一些具有某特定功能的系統(tǒng)進程，每當這種進程完成任務以后便把自己阻塞起來等待新任務的到來。（發(fā)送進程）2.2.3進程的阻塞及喚醒2、進程阻塞過程當有阻塞事件發(fā)生時，進程便調用阻塞原語block()把自己阻塞。進入block后，應先立即停止執(zhí)行，把進程控制塊中的執(zhí)行狀態(tài)改為阻塞狀態(tài)，并把它插入阻塞隊列。3、進程喚醒過程當阻塞進程所期待的事件出現(xiàn)時，則調用喚醒原語wakeup()，將等待事件的進程喚醒。喚醒原語執(zhí)行的過程是：首先把被阻塞進程從等待該事件的阻塞隊列中移出，將其PCB中的阻塞狀態(tài)改為就緒狀態(tài)，然后把該進程插入到就緒隊列中。block()和wakeup()是一對作用剛好相反的原語。2.2.3進程的阻塞及喚醒入口圖

阻塞原語入口圖

喚醒原語2.2.4進程掛起及激活1、進程的掛起

當出現(xiàn)了引起進程掛起的事件時，比如，用戶進程請求將自己掛起，或父進程請求將自己的某個子進程掛起，系統(tǒng)將利用掛起原語suspend()將指定進程或處于阻塞狀態(tài)的進程掛起。掛起原語的執(zhí)行過程是：首先檢查被掛起進程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進程，則將之改為靜止阻塞。最后，若被掛起的進程正在執(zhí)行，則轉向調度程序重新調度。2.2.4進程掛起及激活2．進程的激活過程當發(fā)生激活進程的事件時，例如，父進程或用戶進程請求激活指定進程，若該進程駐留在外存而內存中已有足夠的空間時，則可將在外存上處于靜止就緒狀態(tài)的該進程換入內存。這時，系統(tǒng)將利用激活原語active()將指定進程激活。激活原語的執(zhí)行過程是：先將進程從外存調入內存，檢查該進程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動就緒；若為靜止阻塞，便將之改為活動阻塞。2.2.5進程撤銷1．引起進程撤銷的事件正常結束：計算機系統(tǒng)中，都有一個表示進程已經運行完成的指示。（批處理，Holt。分時系統(tǒng)中，LogsOff）異常結束：越界錯誤、保護錯、特權指令錯、非法指令錯、運行超時、等待超時、算術運算錯、I/O故障外界干預：操作員或操作系統(tǒng)干預、父進程請求、父進程終止2．進程的撤銷過程入口圖終止原語流圖2.3進程同步2.3.1進程同步的基本概念1．進程同步的兩種制約關系在多道程序環(huán)境下，當程序并發(fā)執(zhí)行時，由于資源共享和進程合作，使同處于一個系統(tǒng)中的諸進程之間可能存在著以下兩種形式的制約關系。(1)間接制約(進程互斥)：源于資源共享。(2)直接制約(進程同步)：主要源于進程間的合作。重點2.3.1進程同步的基本概念

同步及互斥的比較同步互斥進程及進程之間有序合作進程及進程之間共享臨界資源相互清楚對方的存在及其作用，直接合作不清楚對方的情況，只是共享同一臨界資源多個進程合作完成一個任務各個進程之間沒有任何合作工作例如：發(fā)送消息進程和接受消息進程之間；輸入進程、計算進程和輸出進程之間等。例如：共享打印機的若干進程之間；共享同一全局變量的若干進程之間等。2.3.1進程同步的基本概念2．臨界資源及臨界區(qū)臨界資源也稱獨占資源，是指某段時間內只允許一個進程使用的資源。比如打印機等硬件資源，以及只能互斥使用的變量、表格、隊列等軟件資源。臨界資源的使用只能采用互斥方式。當一個進程正在使用某個臨界資源且尚未使用完畢時，其它進程必須阻塞等待。只有當使用該資源的進程釋放該資源時，其它進程才可使用。任何進程不能在其他進程沒有使用完臨界資源時使用該資源，否則將會導致錯誤。各個進程中訪問臨界資源的、必須互斥執(zhí)行的程序代碼段稱為臨界區(qū)。2.3.1進程同步的基本概念2．臨界資源及臨界區(qū)2.3.1進程同步的基本概念3．同步機制應遵循的準則①空閑讓進。當無進程處于某臨界資源對應的臨界區(qū)時，表明該臨界資源處于空閑狀態(tài)，應充許一個請求進入臨界區(qū)的進程立即進入臨界區(qū)。②忙則等待。當有進程已進入某臨界資源對應的臨界區(qū)時，表明該臨界資源正在被使用，因而其它試圖進入該臨界資源對應臨界區(qū)的進程必須在進入區(qū)代碼處等待。③有限等待。對要求訪問臨界資源的進程應保證其在有限時間內能進入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。④讓權等待。當進程不能進入自己的臨界區(qū)時，應立即阻塞自己并釋放處理機，以免進程陷入“忙等”狀態(tài)。2.3.1進程同步的基本概念4．實現(xiàn)臨界區(qū)互斥的基本方法（1）軟件實現(xiàn)方法軟件方法是指編程人員編寫程序時在臨界區(qū)前面設置檢查語句，檢查如果有其他并發(fā)執(zhí)行的進程在臨界區(qū)中，則不允許進程進入臨界區(qū)，只能在臨界區(qū)外“忙等”或阻塞。當其他進程退出臨界區(qū)后，進程能夠進入臨界區(qū)運行。常見的軟件實現(xiàn)方法有：Dekker算法和Peterson算法等。（2）硬件實現(xiàn)方法2.3.1進程同步的基本概念4．實現(xiàn)臨界區(qū)互斥的基本方法①中斷禁用為保證多個并發(fā)進程互斥使用臨界資源，只需保證一個進程在執(zhí)行臨界區(qū)代碼時不被中斷即可，這可通過系統(tǒng)內核為啟用和禁用中斷而定義的原語來實現(xiàn)。②專用機器指令編程人員利用專用機器指令來實現(xiàn)臨界區(qū)的互斥使用。在臨界區(qū)代碼前通過硬件指令來檢查某一全局變量是否有其他并發(fā)執(zhí)行的進程在臨界區(qū)中使用。若沒有，則可進入臨界區(qū)；若有，則重復檢查，處于“忙等”狀態(tài)。當進程執(zhí)行完臨界區(qū)代碼退出時，修改該全局變量，允許其他并發(fā)執(zhí)行的進程進入臨界區(qū)執(zhí)行。2.3.2信號量機制1．常見信號量分類(1)整型信號量最初由Dijkstra把整型信號量定義為一個用于表示資源數目的整型量S，它及一般整型量不同，除初始化外，僅能通過兩個標準的原子操作(AtomicOperation)P(S)和V(S)來訪問。P(S)和V(S)操作可描述為：

P(S)：whileS<=0donoop；

S:=S-1；

V(S)：S:=S+1；wait(S)和signal(S)是兩個原語，因此，它們在執(zhí)行時是不可中斷的。重點2.3.2信號量機制(2)記錄型信號量在整型信號量機制中的P操作，只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵循“讓權等待”的準則，而是使進程處于“忙等”的狀態(tài)。記錄型信號量機制則是一種不存在“忙等”現(xiàn)象的進程同步機制。但在采取了“讓權等待”的策略后，又會出現(xiàn)多個進程等待訪問同一臨界資源的情況。為此，在記錄型信號量機制中，除了需要一個用于代表資源數目的整型變量value外，還應增加一個進程鏈表指針L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數據結構而得名的。它所包含的上述兩個數據項可描述為：2.3.2信號量機制記錄型信號量的value值：用于表示資源數目或請求使用某一資源的進程個數的整形量。S.value是及臨界區(qū)內所使用的公用資源有關的信號量。S.value≥0：可供并發(fā)進程使用的資源數S.value<0：正在等待使用臨界區(qū)的進程數信號量的值除初始化外，只能通過P、V原語來修改2.3.2信號量機制P(S)原語操作的主要動作是：S.value-1；如果S.value-1以后仍大于等于零，則進程繼續(xù)進行；如果S.value-1以后小于零，則將該進程阻塞以后插入阻塞隊列，然后轉進程調度。如下圖所示V(S)原語操作的主要動作是：S.value+1；如果相加后結果大于零，則繼續(xù)進行；相加后結果小于等于零，則從該信號的等待隊列中喚醒一個等待進程，然后返回原進程繼續(xù)執(zhí)行或者轉進程調度。如下圖所示入口圖P原語操作功能入口圖V原語操作功能2.3.2信號量機制typesemaphore=record

value:integer；

L:listofprocess；end相應地，P(S)和V(S)操作可描述為：procedureP(S)

varS：semaphore；

begin

S.value:=S.value-1；

ifS.value<0then block(S.L)；

endprocedureV(S)

varS:semaphore；

begin

S.value:=S.value+1；

ifS.value<=0thenwakeup(S.L)；

end2.3.2信號量機制2．信號量的應用（1）利用信號量實現(xiàn)進程互斥關系為使多個進程能互斥地訪問某臨界資源，只須為該資源設置一互斥信號量mutex，并設其初始值為1，然后將各進程訪問該資源的臨界區(qū)CS置于P(mutex)和V(mutex)操作之間即可。利用信號量實現(xiàn)進程互斥的進程可描述如下：(1)利用信號量實現(xiàn)進程互斥必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、重復或遺漏04/01/1159P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)(1)利用信號量實現(xiàn)進程互斥首先需要找到共享的臨界資源；如右圖所示程序中，每個進程中含有多個變量，但只有共享的公共變量a才是共享的臨界資源，而c和y都不是；找到了共享的臨界資源a，則每個程序中涉及該資源a的程序段都是臨界區(qū)；為臨界資源a設置信號量mutex及其初值；再針對每個臨界區(qū)使用mutex的P、V操作將臨界區(qū)括起來。(1)利用信號量實現(xiàn)進程互斥—舉例重點回顧進程控制進程同步的兩種制約關系間接制約(進程互斥)：源于資源共享。直接制約(進程同步)：主要源于進程間的合作。臨界資源及臨界區(qū)臨界資源也稱獨占資源，是指某段時間內只允許一個進程使用的資源。比如打印機等硬件資源，以及只能互斥使用的變量、表格、隊列等軟件資源。各個進程中訪問臨界資源的、必須互斥執(zhí)行的程序代碼段稱為臨界區(qū)。重點回顧記錄型信號量需要一個用于代表資源數目的整型變量value外，還應增加一個進程鏈表指針L，用于鏈接上述的所有等待進程。記錄型信號量的value值：用于表示資源數目或請求使用某一資源的進程個數的整形量。信號量的值除初始化外，只能通過P、V原語來修改重點回顧P(S)原語操作的主要動作是：S.value-1；如果減1以后仍大于等于零，則進程繼續(xù)進行；如果減1以后小于零，則將該進程阻塞以后插入阻塞隊列，然后轉進程調度。V(S)原語操作的主要動作是：S.value+1；如果相加后結果大于零，則繼續(xù)進行；相加后結果小于等于零，則從該信號的等待隊列中喚醒一個等待進程，然后返回原進程繼續(xù)執(zhí)行或者轉進程調度。例：某車站售票廳有20個窗口，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在廳外等待。若把一個購票者看作一個進程，請用P、V操作管理這些并發(fā)進程，要求如下：⑴在主函數中給出信號量的定義和初值。⑵給出一個購票者進程的算法。⑶給出當購票者最多不超過n(設n>20)個時，信號量可能的變化范圍。(1)利用信號量實現(xiàn)進程互斥—舉例判斷該問題是互斥問題還是同步問題：可以將該售票廳的每個窗口看作是一個臨界資源為每個購票者進程共享，每個購票者進程只能使用其中一個窗口。售票廳有20個窗口，所以有20個同類的臨界資源，一次可以允許20個進程進入，并且先來者先進入。由此可知：該問題滿足互斥的2個必要條件（共享臨界資源，共享方式是先來者先進入），所以該問題是互斥問題。根據互斥問題的解決方法設置信號量并賦初值：設置一個信號量mutex，初值為20。用信號量的P、V操作將臨界區(qū)括起來。問題分析⑴．主函數算法：main(){

semaphoremutex=20; cobegin P1();…Pi();…Pn(); coend}⑵．購票者i的算法：Pi(){ P(mutex);

進入售票廳占有一個窗口購票；

V(mutex);}算法描述⑶．信號量mutex的取值范圍：－(n－20)≤mutex≤20其物理含義是：當mutex=20時，表示售票廳內沒有購票者進入，20個窗口都是空閑的，表示可用資源個數；當mutex=0時，表示售票廳內已經進入了20個購票者，每個窗口都被分配，沒有等待的購票者，可用資源為0；當mutex=－(n－20)時，表示一共有n個購票者，其中20個購票者已經進入廳內，分別占有一個窗口，還有n－20個購票者在廳外等待，絕對值表示等待進程個數。結論：當mutex≥0時其值表示可用資源個數；當mutex＜0時其絕對值表示等待進程的個數。信號量討論(2)利用信號量實現(xiàn)前趨關系還可利用信號量來描述程序或語句之間的前趨關系。設有兩個并發(fā)執(zhí)行的進程P1和P2。P1中有語句S1；P2中有語句S2。我們希望在S1執(zhí)行后再執(zhí)行S2。為實現(xiàn)這種前趨關系，我們只須使進程P1和P2共享一個公用信號量S，并賦予其初值為0，將V(S)操作放在語句S1后面；而在S2語句前面插入P(S)操作，即在進程P1中，用S1；V(S)；在進程P2中，用P(S)；S2；(2)利用信號量實現(xiàn)前趨關系下圖示出了一個前趨圖，其中S1，S2，S3，…，S6是最簡單的程序段(只有一條語句)。為使各程序段能正確執(zhí)行，應設置若干個初始值為“0”的信號量。如為保證S1→S2，S1→S3的前趨關系，應分別設置信號量a和b，同樣，為了保證S2→S4，S2→S5，S3→S6，S4→S6和S5→S6，應設置信號量c，d，e，f，g。圖

前趨圖舉例

2.3.2信號量機制semaphorevara,b,c,d,e,f,g=0,0,0,0,0,0,0;beginparbegin//并發(fā)程序開始

beginS1;V(a);V(b);end; beginP(a);S2;V(c);V(d);end; beginP(b);S3;V(e);end; beginP(c);S4;V(f);end; beginP(d);S5;V(g);end; beginP(e);P(f);P(g);S6;end;parend//并發(fā)程序結束end2.3.2信號量機制舉例：V(S1)P(S1)V(S2)P(S2)2.3.2信號量機制vars1,s2:semaphore:=0,0；司機進程：beginwhile(true){P(S1);//等待售票員發(fā)送關門信息啟動車輛；正常行車；到站停車；

V(S2)；//給售票員發(fā)送到站信息}end;售票員進程：beginwhile(true){

關車門;V(S1);//給司機發(fā)送關門信息售票；

P(S2)；//等待司機發(fā)送到站信息開車門；上下乘客；}end；2.3.3典型進程同步問題一、生產者進程和消費者問題描述：有一群生產者進程在生產產品，并將這些產品提供給消費者進程去消費。為使生產者進程及消費者進程能并發(fā)執(zhí)行，在兩者之間設置了一個具有n個緩沖區(qū)的緩沖池，生產者進程將它所生產的產品放入一個緩沖區(qū)中；消費者進程可從一個緩沖區(qū)中取走產品去消費。盡管所有的生產者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即:1)消費者想接收數據時，有界緩沖區(qū)中至少有一個單元是滿的2)生產者想接收數據時，有界緩沖區(qū)中至少有一個單元是空的重點和難點一、生產者和消費者問題可利用一個數組來表示上述的具有n個(0，1，…，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個可投放產品的緩沖區(qū)，每當生產者進程生產并投放一個產品后，輸入指針加1；用一個輸出指針out來指示下一個可從中獲取產品的緩沖區(qū)，每當消費者進程取走一個產品后，輸出指針加1?！璶…….…321P1P2P3.Pn.C1C2C3.Cn有界緩沖區(qū)n圖生產者-消費者問題一、生產者和消費者問題由以上分析得:公用信號量mutex保證生產者進程和消費者進程之間對緩沖池的互斥使用，初值為1;信號量empty表示有界緩沖區(qū)中的空單元數，初值為n；信號量full表示有界緩沖區(qū)中的非空單元數，初值為0。信號量mutex表示有界緩沖區(qū)中的個數。

對生產者—消費者問題可描述如下:一、生產者和消費者問題varmutex,empty,full:semaphore:=1,n,0；buffer:array［0,…,n-1］ofitem；in,out:integer∶=0,0；beginparbegin一、生產者和消費者問題Producer:beginrepeatproduceraniteminnextp；

P(empty)；

//獲得一個空緩沖區(qū)

P(mutex)；

//互斥使用緩沖區(qū)

buffer(in):=nextp；

in:=(in+1)modn；//把產品——nextp放入緩沖區(qū)中

V(mutex)；

//釋放緩沖區(qū)

V(full)；

//緩沖池得到一個滿緩沖區(qū)

untilfalse；end一、生產者和消費者問題Consumer:beginrepeat

P(full);//獲得一個滿緩沖區(qū)

P(mutex);//互斥使用緩沖區(qū)

nextc:=buffer(out);out:=(out+1)modn;//把產品拷入nextc

V(mutex); //釋放緩沖區(qū)

V(empty);//緩沖池得到一個空緩沖區(qū)

consumertheiteminnextc;untilfalse;endparendend重點回顧經典進程的同步問題生產者—消費者問題一、生產者和消費者問題Consumer:beginrepeat

P(full);

P(mutex);

nextc:=buffer(out);out:=(out+1)modn;

V(mutex);

V(empty);

consumertheiteminnextc;untilfalse;endProducer:beginrepeatproduceraniteminnextp；

P(empty)；

P(mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

V(mutex)；

V(full)；

untilfalse；endP,V操作討論1)信號量的物理含義：S.value>0表示有S.value個資源可用S.value=0表示無資源可用S.value<0則|S.value|表示S等待隊列中的進程個數P(S):表示申請一個資源V(S)表示釋放一個資源。信號量的初值應該大于等于0P,V操作討論2)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關重要,一個同步P操作及一個互斥P操作在一起時同步P操作在互斥P操作前而兩個V操作無關緊要P,V操作討論3)P.V操作的優(yōu)缺點優(yōu)點：簡單，而且表達能力強（用P.V操作可解決任何同步互斥問題）缺點：不夠安全；P,V操作使用不當會出現(xiàn)死鎖；遇到復雜同步互斥問題時實現(xiàn)復雜二、哲學家進餐問題

問題描述：5個哲學家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學家之間放一支；哲學家的動作包括思考和進餐，進餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。如何保證哲學家們的動作有序進行？如：不出現(xiàn)相鄰者同時要求進餐；不出現(xiàn)有人永遠拿不到筷子；二、哲學家進餐問題

varchopstick:array［0,…,4］ofsemaphore;第i位哲學家的活動可描述為：repeat P(chopstick［i］); P(chopstick［(i+1)mod5］); … Eating;… V(chopstick［i］); V(chopstick［(i+1)mod5］); … Thinking;untilfalse;二、哲學家進餐問題上述解法可保證不會有兩個相鄰的哲學家同時進餐，但有可能引起死鎖?？刹扇∫韵聨追N方法解決死鎖問題：(1)至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。(2)僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。(3)規(guī)定奇數號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子，而偶數號哲學家則相反。按此規(guī)定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即五位哲學家都先競爭奇數號筷子，獲得后，再去競爭偶數號筷子，最后總會有一位哲學家能獲得兩只筷子而進餐。三、讀者寫者問題問題描述：多個進程間共享一個數據文件，把只要求讀文件的進程稱為“Reader”進程，其他進程則稱為“Writer”進程。允許多個“Reader”進程同時讀取共享文件，但不允許一個Writer進程和其他Reader進程或Writer進程同時訪問共享對象。即："讀－寫"互斥"寫－寫"互斥"讀－讀"允許三、讀者寫者問題為實現(xiàn)Reader及Writer進程間在讀或寫時的互斥而設置了一個互斥信號量mutex。另外，再設置一個整型變量Readcount表示正在讀的進程數目。由于只要有一個Reader進程在讀，便不允許Writer進程去寫。因此，僅當Readcount=0,表示尚無Reader進程在讀時，Reader進程才需要執(zhí)行P(Wmutex)操作。若P(mutex)操作成功，Reader進程便可去讀，相應地，做Readcount+1操作。同理，僅當Reader進程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行V(mutex)操作，以便讓Writer進程寫。又因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應該為它設置一個互斥信號量rmutex。讀者-寫者問題可描述如下：Varrmutex,mutex:semaphore:=1,1;Readcount:integer:=0;Reader:beginrepeat三、讀者寫者問題

P(rmutex);ifreadcount=0thenP(mutex);

//readcount=0，表示該進程是第一個讀者進//程。因讀進程優(yōu)先，阻塞寫進程。

readcount:=readcount+1;

V(rmutex);…performreadoperation;…

P(rmutex);readcount:=readcount-1;ifreadcount=0thenV(mutex);

//readcount=0，表示該進程是最后一//個讀進程，這時允許寫進程執(zhí)行。

V(rmutex);untilfalse;endwriter:beginrepeat

P(mutex);performwriteoperation;

V(mutex);untilfalse;end2.3.3典型進程同步問題某寺廟，有小和尚，老和尚若干。有一水缸，由小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次中能容下一個桶取水。水桶總數為3個。每人一次取缸水僅為1桶，且不可同時進行。試用記錄型信號量給出有關取水、入水的算法描述。根據題意，定義信號量及其初值如下：（1）水桶為臨界資源需互斥使用，定義信號量bucket，因有3個桶，故初值為3；（2）水井一次只能允許下一個桶取水，定義互斥信號量well，初值為1;（3）水缸一次只能允許一個人取水，定義互斥信號量jar，初始值為1；（4）empty和full用于小和尚和老和尚之間的同步制約關系。因為缸能存10桶水，所以empty初始值為10；開始時缸中沒有水，full的初始值為0。semaphorebucket=3,jar=1,full=0,empty=10,well=1;little_monk(){//小和尚入水算法while(1){P(empty);P(bucket);P(well);

從水井中打水；

V(well);P(jar);

倒入水缸；

V(jar);V(bucket);V(full);}}

old_monk(){//老和尚取水算法while(1){P(full);P(bucket);P(jar);

從缸中取水；

V(jar);V(empty);

從桶中倒出飲用;V(bucket);}}作業(yè)習題2P89第6,9,11題

重點回顧經典進程的同步問題生產者—消費者問題哲學家進餐問題讀者－寫者問題2.3.4管程機制

1．為何引入管程雖然信號量機制是一種有效的進程同步機制，但其存在以下缺點：①信號量的P、V操作由用戶在各個進程中分散使用，使用不當容易造成死鎖，增加了用戶編程負擔。②信號量機制涉及多個程序的關聯(lián)內容，程序代碼可讀性差。③使用信號量機制不利于代碼的修改和維護，程序模塊獨立性差，任一變量或一段代碼的修改都可能影響全局。④信號量機制的正確性很難保證。操作系統(tǒng)或并發(fā)進程通常會采用多個信號量，它們關系錯綜復雜，很難保證沒有邏輯錯誤。為了解決上述問題，Hoare和Hanson于1973年提出了管程機制。2.3.4管程機制

2．管程的定義一個管程定義了一個數據和能為并發(fā)進程執(zhí)行的一組操作，這組操作能同步進程和改變管理中的數據。因此，管程是一種并發(fā)性的結構，它包括用于分配一個或一組共享資源的數據和過程，使用者使用時可忽略管程內部的實現(xiàn)細節(jié)，減輕了編程者負擔。管程由四部分組成：管程的名稱局部于管程內部的共享數據結構說明對該數據結構進行操作的一組過程對管程內部共享數據設置初始值的語句

2.3.4管程機制

3．條件變量在任何時刻，最多只有一個進程在管程中執(zhí)行，因此用管程很容易實現(xiàn)互斥，只要將需要互斥訪問的資源用數據結構來描述，并將該數據結構放入管程中便可。但當一進程進入管程執(zhí)行管程的某個過程時，如因某種原因而被阻塞，應立即退出該管程，否則會出現(xiàn)因阻擋其它進程進入管程，而它本身又無法退出管程，形成死鎖。為此，系統(tǒng)中引入了條件變量。條件變量的定義格式為：VarX:condition。對條件變量只能執(zhí)行以下兩種操作:①X.wait操作。②X.signal操作。2.3.4管程機制

x.wait：正在調用管程的進程因x條件需要被阻塞或掛起，則調用x.wait將自己插入到x條件的等待隊列上，并釋放管程，直到x條件變化。此時其它進程可以使用該管程。x.signal：正在調用管程的進程發(fā)現(xiàn)x條件發(fā)生了變化，則調用x.signal，重新啟動一個因x條件而阻塞或掛起的進程。如果存在多個這樣的進程，則選擇其中的一個，如果沒有，則繼續(xù)執(zhí)行原進程，而不產生任何結果。這及信號量機制中的signal操作不同，因為后者總是要執(zhí)行s:=s+1操作，因而總會改變信號量的狀態(tài)。2.3.4管程機制

4．管程解決生產者—消費者問題利用管程來解決生產者—消費者問題,首先為它們建立一個管程，命名為p_c。管程p_c中整型變量count表示緩沖池中己存放的產品數目，條件變量notfull、notempty分別對應于緩沖池不全滿、緩沖池不全空兩個條件。此外，管程p_c中有兩個局部過程：①過程put：負責將產品投放到緩沖池中，當count≥n時，表示緩沖池已滿，生產者進程需等待；②過程get：負責從緩沖池中取出產品，當count≤0時，表示緩沖池已空，消費者進程需等待。2.3.4管程機制

管程p_c描述如下：typep_c=monitorVarin,out,count:integer;Buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(Varproduct:item)beginifcount≥nthennotfull.wait;/*不全滿條件不成立*/buffer[in]:=product;in:=(in+1)modn;count:=count+1;notempty.signal;/*緩沖池不全空條件成立*/end2.3.4管程機制

procedureentryget(Varproduct:item)beginifcount≤0thennotempty.wait;

/*緩沖池不全空條件不成立*/product:=buffer[out];out:=(out+1)modn;count:=count-1;notfull.signal;/*緩沖池不全滿條件成立*/endbeginin:=out:=0;count:=0;end2.3.4管程機制

producer:beginrepeatproduceaniteminnextp;p_c.put(nextp);untilfalseendconsumer:beginrepeatp_c.get(nextc);consumetheiteminnextc;untilfalseend2.4進程通信

2.4.1進程通信分類高級通信機制可分為三大類：1．共享存儲器系統(tǒng)

2．消息傳遞系統(tǒng)

3．管道通信

1．共享存儲器系統(tǒng)基于共享數據結構的通信方式。在這種通信方式中，要求諸進程公用某些數據結構，借以實現(xiàn)諸進程間的信息交換。如在生產者—消費者問題中，就是用有界緩沖區(qū)這種數據結構來實現(xiàn)通信的。低級通信(2)基于共享存儲區(qū)的通信方式。在存儲器中劃出了一塊共享存儲區(qū)，諸進程可通過對其中數據實現(xiàn)通信。高級通信。進程在通信前，先向系統(tǒng)申請獲得共享存儲區(qū)中的一個分區(qū)，并指定該分區(qū)的關鍵字；若系統(tǒng)已經給其他進程分配了這樣的分區(qū)，則將該分區(qū)的描述符返回給申請者，繼之，由申請者把獲得的共享存儲分區(qū)連接到本進程上；此后，便可像讀、寫普通存儲器一樣地讀、寫該公用存儲分區(qū)。2．消息傳遞系統(tǒng)消息傳遞系統(tǒng)(Messagepassingsystem)是當前應用最為廣泛的一種進程間的通信機制。在該機制中，進程間的數據交換是以格式化的消息(message)為單位的；在計算機網絡中，又把message稱為報文。程序員直接利用操作系統(tǒng)提供的一組通信命令(原語)，不僅能實現(xiàn)大量數據的傳遞，而且還隱藏了通信的實現(xiàn)細節(jié)，使通信過程對用戶是透明的，從而大大減化了通信程序編制的復雜性，因而獲得了廣泛的應用。在微內核操作系統(tǒng)中，微內核及服務器之間的通信，都采用了消息傳遞機制。高級通信方式。又因其實現(xiàn)方式的不同而進一步分成直接通信方式和間接通信方式兩種。3．管道通信所謂“管道”，是指用于連接一個讀進程和一個寫進程以實現(xiàn)它們之間通信的一個共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進程(即寫進程)，以字符流形式將大量的數據送入管道；而接受管道輸出的接收進程(即讀進程)，則從管道中接收(讀)數據。由于發(fā)送進程和接收進程是利用管道進行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數據，因而又被引入到許多其它的操作系統(tǒng)中。3．管道通信為了協(xié)調雙方的通信，管道機制必須提供以下三方面的協(xié)調能力：

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

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

(3)確定對方是否存在，只有確定了對方已存在時，才能進行通信。2.4.2消息傳遞系統(tǒng)1、消息緩沖機制（1）消息緩沖區(qū)消息緩沖區(qū)由操作系統(tǒng)負責管理，每個消息緩沖區(qū)存放一個消息，消息緩沖區(qū)的數據結構：TypemessageBuffer=recordsender:integer;//發(fā)送消息的進程標識符size:integer;//消息長度text:string;//消息正文next:pointer;//指向下一個消息緩沖區(qū)的指針End2.4.2消息傳遞機制（2）進程PCB中有關數據項TypePCB=record…mutex:semaphore;//消息隊列互斥信號量，初值為1sm:semaphore;//消息隊列中消息個數信號量，初值為0mq:pointer;