操作系統(tǒng)概論第6章_并發(fā)管理

1、第6章 并發(fā)管理操作系統(tǒng)概論操作系統(tǒng)概論主要內(nèi)容6.1進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性 6.2與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 6.3臨界區(qū)與臨界區(qū)與PV操作操作 6.4進(jìn)程的互斥與同步進(jìn)程的互斥與同步 6.5進(jìn)程通信進(jìn)程通信 6.6死鎖死鎖 重點(diǎn)：分析與時(shí)間有關(guān)的錯(cuò)誤；用PV操作實(shí)現(xiàn)進(jìn)程的互斥與同步；解決死鎖問(wèn)題的方法6.1 6.1 程序的順序執(zhí)行與并發(fā)執(zhí)行程序的順序執(zhí)行與并發(fā)執(zhí)行 一一. 程序的順序執(zhí)行與特征程序的順序執(zhí)行與特征 1. 什么是程序的順序執(zhí)行什么是程序的順序執(zhí)行 一個(gè)程序由若干個(gè)程序段組成，而這些程序段的執(zhí)一個(gè)程序由若干個(gè)程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式

2、就稱為程序的順行必須是順序的，這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。序執(zhí)行。 例如：例如： 2. 順序程序的特征順序程序的特征 （1）順序性：處理機(jī)的操作嚴(yán)格按照程序規(guī)定的順）順序性：處理機(jī)的操作嚴(yán)格按照程序規(guī)定的順序執(zhí)行，即只有前一操作結(jié)束后，才能啟動(dòng)后一操序執(zhí)行，即只有前一操作結(jié)束后，才能啟動(dòng)后一操作的執(zhí)行作的執(zhí)行 （2）封閉性：程序在封閉的環(huán)境下運(yùn)行，并獨(dú)占全）封閉性：程序在封閉的環(huán)境下運(yùn)行，并獨(dú)占全機(jī)，因此機(jī)內(nèi)的資源的狀態(tài)只有運(yùn)行的程序操作才機(jī)，因此機(jī)內(nèi)的資源的狀態(tài)只有運(yùn)行的程序操作才能改變它，其執(zhí)行結(jié)果不受外界因素的影響能改變它，其執(zhí)行結(jié)果不受外界因素的影響 （3）可再現(xiàn)性：只要程

3、序執(zhí)行時(shí)的環(huán)境和初始條件）可再現(xiàn)性：只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，程序經(jīng)多次運(yùn)行后所得的結(jié)果必然相同相同，程序經(jīng)多次運(yùn)行后所得的結(jié)果必然相同 二二. 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 1. 什么是程序的并發(fā)執(zhí)行什么是程序的并發(fā)執(zhí)行 若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序段若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序段的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序段的執(zhí)行尚未的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開(kāi)始，即使這種重結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開(kāi)始，即使這種重疊是很小的一部分，也稱這幾個(gè)程序段是并發(fā)執(zhí)行疊是很小的一部分，也稱這幾個(gè)程序段是并發(fā)執(zhí)行的。的。PQR例：三個(gè)

4、并發(fā)執(zhí)行的程序段。例：三個(gè)并發(fā)執(zhí)行的程序段。 用下圖說(shuō)明在多道批處理系統(tǒng)中，大量操作執(zhí)用下圖說(shuō)明在多道批處理系統(tǒng)中，大量操作執(zhí)行的先后次序。行的先后次序。 I1 I2 I3 I4C1C3C2P1P2討論：討論：(1) 哪些程序段的執(zhí)哪些程序段的執(zhí)行必須是順序的？為行必須是順序的？為什么？什么？(2) 哪些程序段的執(zhí)哪些程序段的執(zhí)行是并行的？為什么？行是并行的？為什么？2. 2. 表示方法表示方法s0;cobegins1; s2; sn;coendsn+1;s0s1s2snSn+1程序順序執(zhí)行在順序環(huán)境下在順序環(huán)境下:先先A,后后B CPU利用率利用率= 40/80 = 50%DEV1利用率利用

5、率=18.75%DEV2利用率利用率= 31.25%程序并發(fā)執(zhí)行在并發(fā)環(huán)境下在并發(fā)環(huán)境下CPU利用率利用率=89%DEV1并發(fā)環(huán)境下利用并發(fā)環(huán)境下利用=33%DEV2并發(fā)環(huán)境下利用并發(fā)環(huán)境下利用=66%并行和并發(fā)在單在單CPU系統(tǒng)中，系統(tǒng)調(diào)度在某一時(shí)刻只能讓一系統(tǒng)中，系統(tǒng)調(diào)度在某一時(shí)刻只能讓一個(gè)線程個(gè)線程(進(jìn)程進(jìn)程)運(yùn)行，雖然這種調(diào)度機(jī)制有多種形運(yùn)行，雖然這種調(diào)度機(jī)制有多種形式式(大多數(shù)是時(shí)間片輪巡為主大多數(shù)是時(shí)間片輪巡為主)，但無(wú)論如何，要，但無(wú)論如何，要通過(guò)不斷切換需要運(yùn)行的線程讓其運(yùn)行的方式就通過(guò)不斷切換需要運(yùn)行的線程讓其運(yùn)行的方式就叫叫并發(fā)(concurrent)。而在多而在多CPU系

6、統(tǒng)中，可以讓兩個(gè)以上的線程系統(tǒng)中，可以讓兩個(gè)以上的線程(進(jìn)進(jìn)程程)同時(shí)運(yùn)行，這種可以同時(shí)讓兩個(gè)以上線程同時(shí)同時(shí)運(yùn)行，這種可以同時(shí)讓兩個(gè)以上線程同時(shí)運(yùn)行的方式叫做運(yùn)行的方式叫做并行(parallel)多道程序設(shè)計(jì)和并發(fā)的關(guān)系多道程序設(shè)計(jì)和并發(fā)的關(guān)系6.2 6.2 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤 1. 1. 什么是與時(shí)間有關(guān)的錯(cuò)誤什么是與時(shí)間有關(guān)的錯(cuò)誤 執(zhí)行結(jié)果與并發(fā)程序執(zhí)行的相對(duì)速度相關(guān)執(zhí)行結(jié)果與并發(fā)程序執(zhí)行的相對(duì)速度相關(guān) 2. 2. 為什么會(huì)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤為什么會(huì)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤 當(dāng)兩個(gè)或多個(gè)程序有共同的臨界資源時(shí)，由于程序當(dāng)兩個(gè)或多個(gè)程序有共同的臨界資源時(shí)，由于程序執(zhí)行的速度不同

7、，則會(huì)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤執(zhí)行的速度不同，則會(huì)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤例：例：P111例：例：P113并發(fā)程序的特征并發(fā)程序的特征 1. 失去程序的封閉性和可再現(xiàn)性失去程序的封閉性和可再現(xiàn)性 如果程序執(zhí)行的結(jié)果是一個(gè)與時(shí)間無(wú)關(guān)的函數(shù)，即具有封如果程序執(zhí)行的結(jié)果是一個(gè)與時(shí)間無(wú)關(guān)的函數(shù)，即具有封閉性。閉性。 若一個(gè)程序的執(zhí)行可改變另一個(gè)程序的變量，程序執(zhí)行的若一個(gè)程序的執(zhí)行可改變另一個(gè)程序的變量，程序執(zhí)行的結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時(shí)的相結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時(shí)的相對(duì)速度，在這種情況下就失去了程序的封閉性。對(duì)速度，在這種情況下就失去了程序的封閉性。 在并發(fā)環(huán)

8、境中，機(jī)內(nèi)資源狀態(tài)將由多個(gè)程序來(lái)改變，因此在并發(fā)環(huán)境中，機(jī)內(nèi)資源狀態(tài)將由多個(gè)程序來(lái)改變，因此使程序的運(yùn)行失去了封閉性。使程序的運(yùn)行失去了封閉性。 2. 2.程序與計(jì)算不再一一對(duì)應(yīng)程序與計(jì)算不再一一對(duì)應(yīng) 一個(gè)程序的一次執(zhí)行稱為一個(gè)計(jì)算一個(gè)程序的一次執(zhí)行稱為一個(gè)計(jì)算 在并發(fā)的環(huán)境下，一個(gè)程序可對(duì)應(yīng)多個(gè)計(jì)算。在并發(fā)的環(huán)境下，一個(gè)程序可對(duì)應(yīng)多個(gè)計(jì)算。 在程序順序執(zhí)行時(shí)，一個(gè)程序總是對(duì)應(yīng)一個(gè)具體在程序順序執(zhí)行時(shí)，一個(gè)程序總是對(duì)應(yīng)一個(gè)具體的計(jì)算，但在程序的并發(fā)執(zhí)行時(shí)，可能有多用戶共享的計(jì)算，但在程序的并發(fā)執(zhí)行時(shí)，可能有多用戶共享使用同一個(gè)程序，但處理（計(jì)算）的對(duì)象卻是不同的，使用同一個(gè)程序，但處理（計(jì)算）

9、的對(duì)象卻是不同的，例如，在多用戶環(huán)境下，可能同時(shí)有多個(gè)用戶調(diào)用例如，在多用戶環(huán)境下，可能同時(shí)有多個(gè)用戶調(diào)用C C語(yǔ)語(yǔ)言的編譯程序，這就是典型的一個(gè)程序?qū)?yīng)多個(gè)用戶言的編譯程序，這就是典型的一個(gè)程序?qū)?yīng)多個(gè)用戶源程序的情況。源程序的情況。 3.3.程序并發(fā)執(zhí)行的相互制約程序并發(fā)執(zhí)行的相互制約 在多道程序設(shè)計(jì)的環(huán)境下，程序是并發(fā)執(zhí)行的。在多道程序設(shè)計(jì)的環(huán)境下，程序是并發(fā)執(zhí)行的。即系統(tǒng)中有多道程序在即系統(tǒng)中有多道程序在“同時(shí)同時(shí)”執(zhí)行，這些程序之間執(zhí)行，這些程序之間要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。合作與競(jìng)爭(zhēng)產(chǎn)生一系列的矛盾，這些矛盾實(shí)際

10、上是一合作與競(jìng)爭(zhēng)產(chǎn)生一系列的矛盾，這些矛盾實(shí)際上是一種相互制約，有直接的，也有間接。種相互制約，有直接的，也有間接。 （1 1）資源共享）資源共享 （間接制約關(guān)系）（間接制約關(guān)系） （2 2）進(jìn)程合作）進(jìn)程合作 （直接制約關(guān)系）（直接制約關(guān)系） 無(wú)關(guān)的并發(fā)進(jìn)程并發(fā)進(jìn)程分類：并發(fā)進(jìn)程分類：無(wú)關(guān)的，交互的無(wú)關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個(gè)別在不同的變量集合上操作，一個(gè)進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無(wú)關(guān)無(wú)關(guān)并發(fā)進(jìn)程的無(wú)關(guān)性是進(jìn)程的執(zhí)行與時(shí)間無(wú)關(guān)的一個(gè)充分條件進(jìn)程的相互制約關(guān)系進(jìn)程的相互制約關(guān)系交互的并發(fā)進(jìn)程交互的并發(fā)進(jìn)程

11、：一組并發(fā)進(jìn)程共享交互的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程共享某些變量，或者一組進(jìn)程相互合作某些變量，或者一組進(jìn)程相互合作; ;一一個(gè)進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程個(gè)進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的結(jié)果的結(jié)果與時(shí)間有關(guān)的錯(cuò)誤執(zhí)行的相對(duì)速度無(wú)法相互控制執(zhí)行的相對(duì)速度無(wú)法相互控制表現(xiàn)形式：表現(xiàn)形式：結(jié)果不唯一結(jié)果不唯一 例：例：P P111,111,P P113113永遠(yuǎn)等待永遠(yuǎn)等待 例：死鎖例：死鎖進(jìn)程的交互：競(jìng)爭(zhēng)與協(xié)作 并發(fā)進(jìn)程之間的競(jìng)爭(zhēng)關(guān)系并發(fā)進(jìn)程之間的競(jìng)爭(zhēng)關(guān)系共享資源共享資源 進(jìn)程的互斥進(jìn)程的互斥 并發(fā)進(jìn)程之間的協(xié)作關(guān)系并發(fā)進(jìn)程之間的協(xié)作關(guān)系進(jìn)程的相互合作進(jìn)程的相互合作進(jìn)程的同步進(jìn)程的同步進(jìn)程的交互：

12、競(jìng)爭(zhēng)與協(xié)作第一種是競(jìng)爭(zhēng)關(guān)系 資源競(jìng)爭(zhēng)的兩個(gè)控制問(wèn)題：一個(gè)是死鎖一個(gè)是死鎖(Deadlock)(Deadlock)問(wèn)題問(wèn)題 一個(gè)是饑餓一個(gè)是饑餓(Starvation) (Starvation) 問(wèn)題問(wèn)題既要解決饑餓問(wèn)題，又要解決死鎖問(wèn)題既要解決饑餓問(wèn)題，又要解決死鎖問(wèn)題進(jìn)程的交互：競(jìng)爭(zhēng)與協(xié)作進(jìn)程互斥是解決進(jìn)程間競(jìng)爭(zhēng)關(guān)系是解決進(jìn)程間競(jìng)爭(zhēng)關(guān)系( (間接制約關(guān)系間接制約關(guān)系) )的手段的手段進(jìn)程互斥指若干進(jìn)程要使用同一共指若干進(jìn)程要使用同一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程使用，其他進(jìn)程必須等待，直進(jìn)程使用，其他進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源到占有資源的進(jìn)

13、程釋放該資源進(jìn)程的交互：競(jìng)爭(zhēng)與協(xié)作第二種是協(xié)作關(guān)系(1) 某些進(jìn)程為完成同一任務(wù)需要某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作分工協(xié)作 進(jìn)程的同步是解決進(jìn)程間協(xié)作是解決進(jìn)程間協(xié)作關(guān)系關(guān)系( (直接制約關(guān)系直接制約關(guān)系) )的手段的手段進(jìn)程的交互：競(jìng)爭(zhēng)與協(xié)作第二種是協(xié)作關(guān)系(2) 進(jìn)程同步指兩個(gè)以上進(jìn)程基于某個(gè)指兩個(gè)以上進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)它們的活動(dòng)。一個(gè)進(jìn)程條件來(lái)協(xié)調(diào)它們的活動(dòng)。一個(gè)進(jìn)程的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信號(hào)，當(dāng)一個(gè)進(jìn)程沒(méi)有得到來(lái)自于協(xié)號(hào)，當(dāng)一個(gè)進(jìn)程沒(méi)有得到來(lái)自于協(xié)作進(jìn)程的消息或信號(hào)時(shí)需等待，直作進(jìn)程的消息或信號(hào)時(shí)需等待，直到消息或信號(hào)到達(dá)才被喚醒到消息或信號(hào)

14、到達(dá)才被喚醒 進(jìn)程的交互：競(jìng)爭(zhēng)與協(xié)作第二種是協(xié)作關(guān)系(3)進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即同步關(guān)系，即逐次使用逐次使用互斥共享互斥共享資源，是對(duì)進(jìn)程使用資源次序上資源，是對(duì)進(jìn)程使用資源次序上的一種協(xié)調(diào)的一種協(xié)調(diào)6.3臨界區(qū)與PV操作6.3.1臨界區(qū)臨界區(qū) 6.3.2 PV操作操作 6.3 6.3 臨界區(qū)和臨界區(qū)和PVPV操作操作 引例：引例： 宿舍電話的使用宿舍電話的使用 打印機(jī)的使用打印機(jī)的使用 1. 臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源稱為臨臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源界資源 引例中的電話和打印機(jī)都屬于臨界資源。除此之外引例中的電

15、話和打印機(jī)都屬于臨界資源。除此之外，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源2 2、臨界區(qū)：、臨界區(qū)：每個(gè)進(jìn)程中訪問(wèn)臨界資每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段程序段稱為臨源的那段程序段稱為臨界區(qū)（臨界段）界區(qū)（臨界段）臨界區(qū)臨界區(qū)例：例：P111例：例：P113臨界區(qū)臨界區(qū)互斥互斥定義定義: : 在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問(wèn)某臨界區(qū)時(shí)，在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問(wèn)某臨界區(qū)時(shí)，就不允許其它進(jìn)程進(jìn)入，否則就會(huì)發(fā)生就不允許其它進(jìn)程進(jìn)入，否則就會(huì)發(fā)生( (后果后果) )無(wú)法無(wú)法估計(jì)的錯(cuò)誤。我們把進(jìn)程之間的這種相互制約的關(guān)估計(jì)的錯(cuò)誤。我們把進(jìn)程之間的這種相互制約

16、的關(guān)系稱為互斥系稱為互斥 進(jìn)入臨界區(qū)的準(zhǔn)則：進(jìn)入臨界區(qū)的準(zhǔn)則： (1)(1)每次至多有一個(gè)進(jìn)程處于臨界區(qū)；每次至多有一個(gè)進(jìn)程處于臨界區(qū)； (2)(2)當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間內(nèi)使其進(jìn)入；限的時(shí)間內(nèi)使其進(jìn)入； (3)(3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間信號(hào)量信號(hào)量 信號(hào)量信號(hào)量是一個(gè)確定的二元組是一個(gè)確定的二元組(s，q)，s是一個(gè)具有非負(fù)初是一個(gè)具有非負(fù)初值的整型變量，值的整型變量，q是一個(gè)初始狀態(tài)為空的隊(duì)列。操作系是一個(gè)初始狀態(tài)為空的隊(duì)列。操作系統(tǒng)利用信號(hào)燈的狀態(tài)對(duì)并發(fā)進(jìn)程和共享資源進(jìn)行控制和統(tǒng)利用信號(hào)燈的

17、狀態(tài)對(duì)并發(fā)進(jìn)程和共享資源進(jìn)行控制和管理管理 s代表資源的實(shí)體代表資源的實(shí)體，是，是整型變量整型變量 s 0 0 時(shí)，表示綠燈，進(jìn)程執(zhí)行時(shí)，表示綠燈，進(jìn)程執(zhí)行( (表示系統(tǒng)擁有的表示系統(tǒng)擁有的資源個(gè)數(shù)資源個(gè)數(shù)) s 0 0 時(shí)，表示紅燈，進(jìn)程停止執(zhí)行時(shí)，表示紅燈，進(jìn)程停止執(zhí)行( ( |s|表示等待表示等待某資源的進(jìn)程個(gè)數(shù)某資源的進(jìn)程個(gè)數(shù)) ) 注意：創(chuàng)建信號(hào)燈時(shí)，應(yīng)準(zhǔn)確說(shuō)明信號(hào)燈注意：創(chuàng)建信號(hào)燈時(shí)，應(yīng)準(zhǔn)確說(shuō)明信號(hào)燈 s 的意義的意義和初值和初值 (這個(gè)初值絕不能為負(fù)值這個(gè)初值絕不能為負(fù)值)用原語(yǔ)實(shí)現(xiàn)互斥用原語(yǔ)實(shí)現(xiàn)互斥記錄型信號(hào)量設(shè)s為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu),一個(gè)分量為整型量value,另一個(gè)為信號(hào)量

18、隊(duì)列queue, P和V操作原語(yǔ)定義： P(s)：將信號(hào)量s減去l，若結(jié)果小于0，則調(diào)用P(s)的進(jìn)程被置成等待信號(hào)量s的狀態(tài) V(s)：將信號(hào)量s加1，若結(jié)果不大于0，則釋放一個(gè)等待信號(hào)量s的進(jìn)程記錄型信號(hào)量type semaphore = record value:integer; queue: list of process;Endprocedure P(var s:semaphore);begin s := s 1; / /* * 把信號(hào)量減去把信號(hào)量減去1 1 * */ / if s 0 then W(s);/ /* * 若信號(hào)量小于若信號(hào)量小于0 0，則調(diào)用，則調(diào)用P(s)P(s)

19、的進(jìn)的進(jìn) 程被置成等待信號(hào)量程被置成等待信號(hào)量s s的狀態(tài)的狀態(tài) * */ /end;procedure V(var s:semaphore);begins := s + 1; / /* * 把信號(hào)量加把信號(hào)量加1 1 * */ /if s 0表示有S個(gè)資源可用；S=0表示無(wú)資源可用；S0則| S |表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)。P(S):表示申請(qǐng)一個(gè)資源; V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0P.V操作討論P(yáng).V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操

20、作的順序至關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前,而兩個(gè)V操作無(wú)關(guān)緊要總結(jié)：如何描述進(jìn)程同步問(wèn)題？先寫(xiě)出對(duì)問(wèn)題的初步描述（用漢語(yǔ)，流程）；例如司機(jī)售票員問(wèn)題中：司機(jī)（進(jìn)程）：?jiǎn)?dòng)車輛；正常行駛；停車問(wèn)題中存在的關(guān)系（互斥、同步，各有幾種）；互斥：涉及到對(duì)共享資源的訪問(wèn)同步：涉及到進(jìn)程之間的執(zhí)行次序設(shè)置信號(hào)量（信號(hào)量的個(gè)數(shù)和初值（考慮問(wèn)題的初始狀態(tài)），信號(hào)量的物理含義）； 信號(hào)量的初值：0，1，n三種情況 1：表示臨界資源； 0：表示進(jìn)程間的同步（前驅(qū)）關(guān)系 n：表示若干個(gè)資源總結(jié)：如何描述進(jìn)程同步問(wèn)題？（續(xù)）把P、V操作放到合適的位置。P操作：要控制誰(shuí)就放在誰(shuí)的

21、前面；6.5 進(jìn)程通信P.V操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊，所操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊，所以以P.V為低級(jí)通訊原語(yǔ)。它只能傳遞簡(jiǎn)單的為低級(jí)通訊原語(yǔ)。它只能傳遞簡(jiǎn)單的信號(hào)，不能傳遞交換大量信息信號(hào)，不能傳遞交換大量信息如果要在進(jìn)程間傳遞大量信息則要用如果要在進(jìn)程間傳遞大量信息則要用Send / Receive原語(yǔ)（高級(jí)通信原語(yǔ)）原語(yǔ)（高級(jí)通信原語(yǔ)）目前常用的高級(jí)通信方式有信箱通信、消息緩沖通信、管道通信。6.5.1 信件發(fā)送者名發(fā)送者名-進(jìn)程名進(jìn)程名信息信息(地址和長(zhǎng)度地址和長(zhǎng)度)等等/不等回信不等回信回信存放地址回信存放地址6.5.2 信箱若干個(gè)進(jìn)程可向同一進(jìn)程發(fā)送信件若干個(gè)進(jìn)程可向同一

22、進(jìn)程發(fā)送信件.接受信件的進(jìn)程接受信件的進(jìn)程可以設(shè)立一個(gè)信箱可以設(shè)立一個(gè)信箱信箱的大小決定了可容納的信件數(shù)信箱的大小決定了可容納的信件數(shù)由信箱說(shuō)明和信箱體兩部分組成由信箱說(shuō)明和信箱體兩部分組成6.5.3 通信原語(yǔ)通信遵循規(guī)則通信遵循規(guī)則:發(fā)送信件時(shí)信箱已滿發(fā)送信件時(shí)信箱已滿,則將發(fā)送信件的進(jìn)程置為則將發(fā)送信件的進(jìn)程置為”等信箱等信箱”狀態(tài)狀態(tài),直到信箱有空才被釋放直到信箱有空才被釋放取信件信箱為空取信件信箱為空,則將收信件的進(jìn)程置為則將收信件的進(jìn)程置為”等信等信件件”狀態(tài)狀態(tài),直到有信件才被釋放直到有信件才被釋放通信原語(yǔ)send(N,M) 功能：把信件功能：把信件M送到指定的送到指定的信箱信箱N

23、中中 receive(N,X) 功能：從指定信箱功能：從指定信箱N中取中取出一封信，存放到指定的地址出一封信，存放到指定的地址X中中 6.6死鎖6.6.1死鎖的形成死鎖的形成 6.6.2死鎖的必要條件死鎖的必要條件 6.6.3死鎖的防止死鎖的防止 6.6.4死鎖的避免死鎖的避免 6.6.5死鎖的檢測(cè)死鎖的檢測(cè) 例例1： 進(jìn)程進(jìn)程P 進(jìn)程進(jìn)程Q : : 請(qǐng)求讀卡機(jī)請(qǐng)求讀卡機(jī) 請(qǐng)求打印機(jī)請(qǐng)求打印機(jī) : : 請(qǐng)求打印機(jī)請(qǐng)求打印機(jī) 請(qǐng)求讀卡機(jī)請(qǐng)求讀卡機(jī) : : 釋放讀卡機(jī)釋放讀卡機(jī) 釋放讀卡機(jī)釋放讀卡機(jī) : : 釋放打印機(jī)釋放打印機(jī) 釋放打印機(jī)釋放打印機(jī) : :資源分配不當(dāng)產(chǎn)生死鎖資源分配不當(dāng)產(chǎn)生死鎖

24、6.6.1 死鎖的形成死鎖的形成例例2：m個(gè)資源被個(gè)資源被n個(gè)進(jìn)程共享，每個(gè)進(jìn)程要求個(gè)進(jìn)程共享，每個(gè)進(jìn)程要求k個(gè)資個(gè)資源，則當(dāng)源，則當(dāng) m=n*(k-1) 時(shí)，如果分配不當(dāng)就可能發(fā)時(shí)，如果分配不當(dāng)就可能發(fā)生死鎖。生死鎖。 死鎖的定義：死鎖的定義：在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程持有某種資源而又都等待著別的進(jìn)程釋放每個(gè)進(jìn)程持有某種資源而又都等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時(shí)每個(gè)進(jìn)程都占用了一定的資源但又都不能向前此時(shí)每個(gè)進(jìn)程都占用了一定的資源但又都不能向前推進(jìn)，稱這一組進(jìn)程產(chǎn)生可死鎖。

25、推進(jìn)，稱這一組進(jìn)程產(chǎn)生可死鎖。資源分配不當(dāng)產(chǎn)生死鎖資源分配不當(dāng)產(chǎn)生死鎖1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 資源不足資源不足 進(jìn)程推進(jìn)次序不合適進(jìn)程推進(jìn)次序不合適2. 2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 互斥條件互斥條件 一個(gè)資源一次只能被一個(gè)進(jìn)程使用。一個(gè)資源一次只能被一個(gè)進(jìn)程使用。 不可剝奪條件不可剝奪條件 一個(gè)資源僅能被占有它的進(jìn)程釋放。一個(gè)資源僅能被占有它的進(jìn)程釋放。 部分分配部分分配 一個(gè)進(jìn)程已占有了一些資源，但仍然要求其它資源。一個(gè)進(jìn)程已占有了一些資源，但仍然要求其它資源。 環(huán)路條件環(huán)路條件 系統(tǒng)中存在著一個(gè)由若干個(gè)進(jìn)程形成的環(huán)形請(qǐng)求鏈。系統(tǒng)中存在著一個(gè)由若干個(gè)進(jìn)程形成的環(huán)形

26、請(qǐng)求鏈。6.6.2. 死鎖的必要條件死鎖的必要條件解決死鎖問(wèn)題的策略解決死鎖問(wèn)題的策略破壞產(chǎn)生死鎖的四個(gè)必要條件之一破壞產(chǎn)生死鎖的四個(gè)必要條件之一 解決死鎖的策略：解決死鎖的策略： 死鎖的防止死鎖的防止 死鎖的避免死鎖的避免 死鎖的檢測(cè)死鎖的檢測(cè)6.6.3 6.6.3 死鎖的防止死鎖的防止 1.1.靜態(tài)分配資源：靜態(tài)分配資源：僅當(dāng)系統(tǒng)能滿足作業(yè)運(yùn)行時(shí)所僅當(dāng)系統(tǒng)能滿足作業(yè)運(yùn)行時(shí)所需的全部資源時(shí)，才把該作業(yè)調(diào)入內(nèi)存運(yùn)行，需的全部資源時(shí)，才把該作業(yè)調(diào)入內(nèi)存運(yùn)行，同時(shí)在作業(yè)運(yùn)行前，將其所需的全部資源一次同時(shí)在作業(yè)運(yùn)行前，將其所需的全部資源一次性地分配給該作業(yè)。作業(yè)在運(yùn)行過(guò)程中不再提性地分配給該作業(yè)。作

27、業(yè)在運(yùn)行過(guò)程中不再提出新的資源要求出新的資源要求破壞破壞“占有且等待資源占有且等待資源”和和“循環(huán)等待資源循環(huán)等待資源” 缺點(diǎn)：資源利用率低缺點(diǎn)：資源利用率低 作業(yè)等待時(shí)間長(zhǎng)作業(yè)等待時(shí)間長(zhǎng)2. 2. 按序分配資源：按序分配資源：系統(tǒng)中的所有資源類都分給系統(tǒng)中的所有資源類都分給一個(gè)唯一的序號(hào)，并要求每個(gè)進(jìn)程均應(yīng)一個(gè)唯一的序號(hào)，并要求每個(gè)進(jìn)程均應(yīng)嚴(yán)格按照遞增的次序請(qǐng)求資源嚴(yán)格按照遞增的次序請(qǐng)求資源破壞破壞 “循環(huán)等待資源循環(huán)等待資源” 缺點(diǎn)：缺點(diǎn)：對(duì)于實(shí)際資源使用順序與資源序號(hào)不一對(duì)于實(shí)際資源使用順序與資源序號(hào)不一致的作業(yè)仍存在著資源浪費(fèi)現(xiàn)象致的作業(yè)仍存在著資源浪費(fèi)現(xiàn)象3. 剝奪式分配資源剝奪式分配資源：可搶奪其它進(jìn)程的資源：可搶奪其它進(jìn)程的資源破壞破壞 “非搶奪式分配非搶奪式分配” 例：分配主存例：分配主存6.6.4 死鎖的避免死鎖的避免 銀行家算法銀行家算法 檢查申請(qǐng)者對(duì)各類資源的最大需求量，如果檢查申請(qǐng)者對(duì)各類資源的最大需求量，如果系