《計算機(jī)操作系統(tǒng)進(jìn)程調(diào)度》課件解讀

計算機(jī)操作系統(tǒng)

——進(jìn)程調(diào)度

計算機(jī)操作系統(tǒng)0摘要基礎(chǔ)：進(jìn)程調(diào)度策略：進(jìn)程調(diào)度實(shí)現(xiàn)：互斥與同步

-避免：死鎖與饑餓 -解決：幾個經(jīng)典問題（如生產(chǎn)者-消費(fèi)者） -了解：進(jìn)程通信摘要單道程序與多道程序的執(zhí)行單道程序執(zhí)行的過程多道程序執(zhí)行的過程單道程序與多道程序的執(zhí)行單道程序執(zhí)行的過程課堂思考與練習(xí) 設(shè)時刻0，在內(nèi)存中有三個程序A、B、C，占用CPU的優(yōu)先權(quán)為A最高，C最低；它們的計算和I/O操作時間如表所示。試畫出單道運(yùn)行和多道運(yùn)行的時間關(guān)系圖。課堂思考與練習(xí) 設(shè)時刻0，在內(nèi)存中有三個程序什么叫進(jìn)程？為什么要引入“進(jìn)程”這一概念？為了提高系統(tǒng)資源的利用率，出現(xiàn)了多道程序設(shè)計技術(shù)，但多道程序的并發(fā)執(zhí)行和資源共享帶來了新的問題，破壞了程序的封閉性和可再現(xiàn)性，程序和機(jī)器執(zhí)行程序的活動不再一一對應(yīng)，并發(fā)程序之間有可能存在相互制約關(guān)系。并發(fā)程序的獨(dú)立性、并發(fā)性、動態(tài)性和相互制約反映了并發(fā)程序的本質(zhì)，而程序的概念已不能反映程序并發(fā)執(zhí)行的實(shí)質(zhì)，因此，人們引入了進(jìn)程的概念來描述并發(fā)程序的執(zhí)行過程。進(jìn)程：一個具有獨(dú)立功能的程序?qū)δ硞€數(shù)據(jù)集在處理機(jī)上的執(zhí)行過程和分配資源的基本單位。這里，程序指一組操作序列，而數(shù)據(jù)集則是接受程序規(guī)定操作的一組存儲單元的內(nèi)容。進(jìn)程=程序的執(zhí)行？什么叫進(jìn)程？為什么要引入“進(jìn)程”這一概念？進(jìn)程和程序的區(qū)別和關(guān)系？進(jìn)程和程序是兩個既有聯(lián)系又有區(qū)別的概念，它們的區(qū)別和關(guān)系可簡述如下：(1)進(jìn)程是一個動態(tài)概念，而程序則是一個靜態(tài)概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進(jìn)程則強(qiáng)調(diào)執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2)進(jìn)程具有并行特征，而程序沒有。由進(jìn)程的定義可知，進(jìn)程具有并行特征的兩個方面，即獨(dú)立性和異步性。也就是說，在不考慮資源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3)進(jìn)程是競爭計算機(jī)系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對進(jìn)程獨(dú)立性和異步性的限制。(4)不同的進(jìn)程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。進(jìn)程和程序的區(qū)別和關(guān)系？進(jìn)程和程序是兩個如何監(jiān)控程序的執(zhí)行？用各種數(shù)據(jù)結(jié)構(gòu)來記錄多個進(jìn)程（PCB）用狀態(tài)的變遷來跟蹤多個進(jìn)程用進(jìn)程調(diào)度來選擇控制多個進(jìn)程用并發(fā)控制來同步、協(xié)調(diào)多個進(jìn)程如何監(jiān)控程序的執(zhí)行？用各種數(shù)據(jù)結(jié)構(gòu)來記錄多個進(jìn)程（PCB）進(jìn)程的靜態(tài)描述進(jìn)程=程序+數(shù)據(jù)+進(jìn)程控制塊PCB

程序描述進(jìn)程所要完成的功能

數(shù)據(jù)是對其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集，程序在執(zhí)行時必不可少的工作區(qū)和操作對象。進(jìn)程控制塊包含了有關(guān)進(jìn)程的描述信息、控制信息以及資源信息，是進(jìn)程動態(tài)特征的集中反映。進(jìn)程的靜態(tài)描述進(jìn)程=程序+數(shù)據(jù)+進(jìn)程控制塊PCB進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程控制進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。1.進(jìn)程創(chuàng)建2.進(jìn)程撤銷3.進(jìn)程阻塞4.進(jìn)程喚醒5.進(jìn)程切換：在某一時刻，一運(yùn)行的進(jìn)程被迫中斷，讓出CPU給指定進(jìn)程。一般在進(jìn)行進(jìn)程上下文切換時，不保留被切換的進(jìn)程上下文的正文，但保留進(jìn)程執(zhí)行時所使用的寄存器。進(jìn)程控制進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序《計算機(jī)操作系統(tǒng)進(jìn)程調(diào)度》課件解讀《計算機(jī)操作系統(tǒng)進(jìn)程調(diào)度》課件解讀程序執(zhí)行過程①單進(jìn)程單一進(jìn)程②多進(jìn)程獨(dú)立進(jìn)程彼此獨(dú)立③多進(jìn)程協(xié)作進(jìn)程彼此依賴在并發(fā)環(huán)境下不存在完全獨(dú)立的進(jìn)程！程序執(zhí)行過程①單進(jìn)程單一進(jìn)程②多進(jìn)程獨(dú)立進(jìn)程③多進(jìn)程協(xié)作進(jìn)程程序執(zhí)行過程④多進(jìn)程競爭進(jìn)程共享互斥共享資源⑤多進(jìn)程通信進(jìn)程相互通信程序執(zhí)行過程④多進(jìn)程競爭進(jìn)程共享資源⑤多進(jìn)程通信進(jìn)程程序執(zhí)行過程中的問題①②不存在資源競爭，只存在CPU調(diào)度③④⑤多個進(jìn)程相互依賴、彼此競爭資源，既存在CPU調(diào)度，又存在同步協(xié)調(diào)，從而引入并發(fā)控制。并發(fā)控制的實(shí)施策略：臨界資源與臨界區(qū)機(jī)制：標(biāo)志、信號量方法：加鎖、P、V原語實(shí)現(xiàn)：互斥和同步程序執(zhí)行過程中的問題①②不存在資源競爭，只存在CPU調(diào)度進(jìn)程互斥（1）臨界資源：一次僅允許一個進(jìn)程使用的共享資源。每次只準(zhǔn)許一個進(jìn)程進(jìn)入臨界區(qū)，進(jìn)入后不允許其他進(jìn)程進(jìn)入。對于臨界資源，多個進(jìn)程必須互斥地對它進(jìn)行訪問。臨界區(qū)：每個進(jìn)程中訪問臨界資源的那段代碼。

臨界區(qū)是由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。間接制約：由共享公有資源而造成的對并發(fā)進(jìn)程執(zhí)行速度的間接制約。即把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象。進(jìn)程互斥（1）臨界資源：一次僅允許一個進(jìn)程使用的共享資源。每進(jìn)程互斥（2）互斥：一組并發(fā)進(jìn)程中的一個或多個程序段，因共享某一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個以上的共享該資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)稱為互斥。進(jìn)程互斥：一個進(jìn)程正在訪問臨界資源，另一個要訪問該資源的進(jìn)程必須等待。當(dāng)占用臨界資源的進(jìn)程退出臨界區(qū)，才允許另一進(jìn)程區(qū)訪問此臨界資源。為了禁止兩個進(jìn)程同時進(jìn)入臨界區(qū)，需采用一定的方法來協(xié)調(diào)它們。無論方法是什么都應(yīng)遵循下述準(zhǔn)則：空閑讓出忙則等待讓權(quán)等待有限等待進(jìn)程互斥（2）互斥：一組并發(fā)進(jìn)程中的一個或多個程序段，因共享進(jìn)程互斥（3）互斥的加鎖實(shí)現(xiàn)對臨界區(qū)加鎖以實(shí)現(xiàn)互斥：當(dāng)某個進(jìn)程進(jìn)入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進(jìn)程在申請進(jìn)入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。進(jìn)程互斥（3）互斥的加鎖實(shí)現(xiàn)進(jìn)程互斥（4）

設(shè)臨界區(qū)的類名為Ｓ。為了保證每一次臨界區(qū)中只能有一個程序段被執(zhí)行，又設(shè)鎖定位key［Ｓ］。key［Ｓ］表示該鎖定位屬于類名為Ｓ的臨界區(qū)。加鎖后的臨界區(qū)程序描述如下：

lock(key［Ｓ］) 〈臨界區(qū)〉 unlock(key［Ｓ］)設(shè)key［Ｓ］=1時表示類名為Ｓ的臨界區(qū)可用，key［Ｓ］=0時表示類名為Ｓ的臨界區(qū)不可用。進(jìn)程互斥（4）設(shè)臨界區(qū)的類名為Ｓ。為了保證每一次臨界區(qū)進(jìn)程互斥（5）一種簡便的實(shí)現(xiàn)方法是：

lock(x)=beginlocalv repeat v←x untilv=1 x←0 end因?yàn)楫?dāng)同時有幾個進(jìn)程調(diào)用lock(key［Ｓ］)時，在x←0語句執(zhí)行之前，可能已有兩個以上的多個進(jìn)程由于key［Ｓ］=1而進(jìn)入臨界區(qū)。為解決這個問題有些機(jī)器在硬件中設(shè)置了“測試與設(shè)置指令，保證第一步和第二步執(zhí)行不可分離。注意：在系統(tǒng)實(shí)現(xiàn)時鎖定位key［Ｓ］總是設(shè)置在公有資源所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。進(jìn)程互斥（5）一種簡便的實(shí)現(xiàn)方法是：進(jìn)程互斥（6）試考慮以下進(jìn)程PA和PB反復(fù)使用臨界區(qū)的情況：PA A：lock(key［Ｓ］) 〈Ｓ〉 unlock(key［Ｓ］) GotoAPB B：lock(key［Ｓ］)

＜Ｓ＞

unlock(key［Ｓ］) GotoB設(shè)進(jìn)程ＰA已通過lock(key［Ｓ］)過程而進(jìn)入臨界區(qū)。顯然，在進(jìn)程PA執(zhí)行unlock(key［Ｓ］)過程之前，key［Ｓ］=0且進(jìn)程PB沒有進(jìn)入臨界區(qū)的機(jī)會。然而，當(dāng)進(jìn)程PA執(zhí)行完unlock(key［Ｓ］)過程之后，由于緊接著是一轉(zhuǎn)向語句，進(jìn)程PA將又立即去執(zhí)行l(wèi)ock(key［Ｓ］)過程。此時，由于unlock(key［Ｓ］)過程已將key［Ｓ］的值置為1，也就是開鎖狀態(tài)，從而進(jìn)程PA又可進(jìn)入臨界區(qū)Ｓ。只有在進(jìn)程PA執(zhí)行完unlock(key［Ｓ］)過程之后、執(zhí)行GotoA語句之前的瞬間發(fā)生進(jìn)程調(diào)度，使進(jìn)程PA把處理機(jī)轉(zhuǎn)讓給進(jìn)程PB，進(jìn)程PB才有可能得到執(zhí)行。然而遺憾的是，這種可能性是非常小的。因此，進(jìn)程PB將處于永久饑餓狀態(tài)（starvation）。使用加鎖法實(shí)現(xiàn)進(jìn)程間互斥時，還將導(dǎo)致在某些情況下出現(xiàn)不公平現(xiàn)象。進(jìn)程互斥（6）試考慮以下進(jìn)程PA和PB反復(fù)使用臨界區(qū)的情況：進(jìn)程互斥（7）這正如某個學(xué)生想使用某個人人都可借用、且不規(guī)定使用時間的教室時一樣，他必須首先申請獲得使用該教室的權(quán)利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復(fù)將持續(xù)到他進(jìn)門后為止。從這個例子中，可以得到解決加鎖法所帶來的問題的方法。一種最直觀的辦法是，設(shè)置一個教室管理員。從而，如果有學(xué)生申請使用教室而未能如愿時，教室管理員記下他的名字，并等到教室門一打開則通知該學(xué)生進(jìn)入。這樣，既減少了學(xué)生多次來去教室檢查門是否被打開的時間，又減少了因?yàn)閷W(xué)生自發(fā)地檢查造成的不公平現(xiàn)象。在操作系統(tǒng)中，這個管理員就是信號量。信號量管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源實(shí)體。進(jìn)程互斥（7）這正如某個學(xué)生想使用某個人人都可借用、且不規(guī)定進(jìn)程互斥（8）信號量信號量的概念和下面所述的Ｐ、Ｖ原語是荷蘭科學(xué)家E.W.Dijkstra提出來的。信號是鐵路交通管理中的一種常用設(shè)備，交通管理人員利用信號顏色的變化來實(shí)現(xiàn)交通管理。在操作系統(tǒng)中，信號量sem是一整數(shù)。在sem大于等于零時代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但sem小于零時則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。顯然，用于互斥的信號量sem的初值應(yīng)該大于零，而建立一個信號量必須經(jīng)過說明所建信號量所代表的意義，和賦初值以及建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以便指向那些等待使用該臨界區(qū)的進(jìn)程。進(jìn)程互斥（8）信號量進(jìn)程互斥（9）Ｐ，Ｖ原語信號量的數(shù)值僅能由Ｐ，Ｖ原語操作改變(Ｐ和Ｖ分別是荷蘭語Passeren和Verhoog的頭一個字母，相當(dāng)于英文的pass和increment的意思)。采用Ｐ，Ｖ原語，可以把類名為Ｓ的臨界區(qū)描述為WhenＳdoＰ(sem)臨界區(qū)Ｖ(sem)od。這里，sem是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號量。一次Ｐ原語操作使得信號量sem減1，而一次Ｖ原語操作將使得信號量sem加1。必須強(qiáng)調(diào)的一點(diǎn)是，當(dāng)某個進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時，其他進(jìn)程如果執(zhí)行了Ｐ原語操作，則該進(jìn)程并不像調(diào)用lock時那樣因進(jìn)不了臨界區(qū)而返回到lock的起點(diǎn)，等以后重新執(zhí)行測試，而是在等待隊(duì)列中等待有其他進(jìn)程做Ｖ原語操作釋放資源后，進(jìn)入臨界區(qū)，這時，Ｐ原語的執(zhí)行才算真正結(jié)束。另外，當(dāng)有好幾個進(jìn)程執(zhí)行Ｐ原語未通過而進(jìn)入等待狀態(tài)之后，如有某進(jìn)程作了Ｖ原語操作，則等待進(jìn)程中的一個可以進(jìn)入臨界區(qū)，但其他進(jìn)程必須等待。進(jìn)程互斥（9）Ｐ，Ｖ原語進(jìn)程互斥（10）Ｐ原語操作的主要動作是：(1)sem減1；(2)若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3)若sem減1后小于零，則該進(jìn)程被阻塞后與該信號相對應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。進(jìn)程互斥（10）Ｐ原語操作的主要動作是：進(jìn)程互斥（11）Ｖ原語的操作主要動作是：(1)sem加1；(2)若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3)若相加結(jié)果小于或等于零，則從該信號的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。進(jìn)程互斥（11）Ｖ原語的操作主要動作是：用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥利用Ｐ，Ｖ原語和信號量，可以方便地解決并發(fā)進(jìn)程的互斥問題，而且不會產(chǎn)生使用加鎖法解決互斥問題時所出現(xiàn)的問題。設(shè)信號量sem是用于互斥的信號量，且其初值為1表示沒有并發(fā)進(jìn)程使用該臨界區(qū)。顯然，由上面幾節(jié)的討論可知，只要把臨界區(qū)置于Ｐ(sem)和Ｖ(sem)之間，即可實(shí)現(xiàn)進(jìn)程間的互斥。當(dāng)一個進(jìn)程想要進(jìn)入臨界區(qū)時，它必須先執(zhí)行Ｐ原語操作以將信號量sem減1。在一個進(jìn)程完成對臨界區(qū)的操作之后，它必須執(zhí)行Ｖ原語操作以釋放它所占用的臨界區(qū)。由于信號量初始值為1，所以，任一進(jìn)程在執(zhí)行Ｐ原語操作之后將sem的值變?yōu)?，表示該進(jìn)程可以進(jìn)入臨界區(qū)。用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥用信號量實(shí)現(xiàn)互斥時值的變化wait(s)p1s10-1-2-101criticalsignal(s)wait(s)criticalsignal(s)p2wait(s)criticalsignal(s)p3semaphoreWait操作信號量非負(fù)，P1進(jìn)入臨界區(qū)Wait操作信號量為負(fù)，P2阻塞Wait操作信號量為負(fù)，P3阻塞Signal操作后信號量非正，從等待隊(duì)列中喚醒一個進(jìn)程Signal操作后信號量非正，從等待隊(duì)列中喚醒一個進(jìn)程Signal操作后信號量為正，表示已無進(jìn)程在臨界區(qū)用信號量實(shí)現(xiàn)互斥時值的變化wait(s)p1scritica用信號量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：1)設(shè)sem為互斥信號量，其取值范圍為(1,0,-1)。其中sem=1表示進(jìn)程PA和PB都未進(jìn)入類名為Ｓ的臨界區(qū)，sem=0表示進(jìn)程PA或PB已進(jìn)入類名為Ｓ的臨界區(qū)，sem=-1表示進(jìn)程PA和PB中，一個進(jìn)程已進(jìn)入臨界區(qū)，而另一個進(jìn)程等待進(jìn)入臨界區(qū)。2）描述： PA：

Ｐ（sem） 〈Ｓ〉

Ｖ（sem）：

：

： PB：

Ｐ（sem） 〈Ｓ〉

Ｖ（sem）∷

：

：用信號量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：練習(xí)與思考一試用P、V操作實(shí)現(xiàn)飛機(jī)聯(lián)網(wǎng)售票系統(tǒng)中各地N個終端的終端售票進(jìn)程發(fā)售同月同日同一次航班機(jī)票的過程。練習(xí)與思考一試用P、V操作實(shí)現(xiàn)飛機(jī)聯(lián)網(wǎng)售票系統(tǒng)中各地N個終端例：設(shè)余票單元為count，有N個售票進(jìn)程正確并發(fā)執(zhí)行的算法 ProcessPi(i=1,2,…n) Beginbegin

count:integer;s:semaphore;

VarXi:integer;s:=1;

按旅客要求找到count; cobegin P(s);P1; Xi:=count;P2; IfXi>=1then …… beginPn; Xi:=Xi-1; coend Xi:=count;end. V(s);

輸出一張票; End Else

輸出“票已售完”; End; 例：設(shè)余票單元為count，有N個售票進(jìn)程正確并發(fā)執(zhí)行思考與練習(xí)二兩個火車站A、B之間是單軌連接，現(xiàn)有許多列車同時到達(dá)A站，經(jīng)A站到B站，列車駛出B站后又可分路行駛。為了保證行車安全，請用信號量機(jī)制設(shè)計一個自動調(diào)度算法。思考與練習(xí)二兩個火車站A、B之間是單軌連接，現(xiàn)有許多列車Programmutualexclusion;begin(*mainprogram*) Count=n;(*n為列車數(shù)*);cobegin Vars:semaphore(:=1);P(1); ProcedureP(i:integer);P(2); Begin…………P(n);RepeatcoendP(s);end.

列車駛?cè)階、B段;V(s);

列車分路行駛

……ForeverEnd;Programmutualexclusion;進(jìn)程同步（1）

除了對公有資源的競爭而引起的間接制約之外，并發(fā)進(jìn)程之間是否還存在著其他制約關(guān)系影響執(zhí)行速度呢？來看下面的例子。

計算進(jìn)程和打印進(jìn)程共同使用同一緩沖區(qū)Buf。計算進(jìn)程反復(fù)地把每次計算結(jié)果放入Buf中，而打印進(jìn)程則把計算進(jìn)程每次放入Buf中的數(shù)據(jù)通過打印機(jī)打印輸出。如果不采取任何制約措施，這兩個進(jìn)程的執(zhí)行起始時間和執(zhí)行速度都是彼此獨(dú)立的，其相應(yīng)的控制段可以描述為：進(jìn)程同步（1）除了對公有資源的競爭而引起的PC ： : A: localBuf Repeat Buf←Buf Until Buf=空

計算

得到計算結(jié)果 Buf←計算結(jié)果 Goto APP: ： : B: localPri Repeat Pri←Buf Until Pri≠空

打印Buf中的數(shù)據(jù)

清除Buf中的數(shù)據(jù) Goto BPC ：

直接制約：一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過程。

進(jìn)程同步：把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過程。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號稱為消息或事件。直接制約：一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互

如果對一個消息或事件賦以唯一的消息名，則可用過程

wait（消息名）

表示進(jìn)程等待合作進(jìn)程發(fā)來的消息，而用過程 signal（消息名）

表示向合作進(jìn)程發(fā)送消息。利用過程wait和signal，可以簡單地描述上面例子中的計算進(jìn)程PC和打印進(jìn)程PP的同步關(guān)系如下：如果對一個消息或事件賦以唯一的消息名，則可用過程（1）設(shè)消息名Bufempty表示Buf空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。（2）初始化Bufempty=true，Buffull=false。（3）描述： PC

： A: wait（Bufempty）

計算 Buf←計算結(jié)果 Bufempty←false signal（Buffull） Goto A（1）設(shè)消息名Bufempty表示Buf空，消息名Buffu

PP ： B: wait（Buffull）

打印Buf中的數(shù)據(jù)

清除Buf中的數(shù)據(jù) Buffull←false signal（Bufempty） Goto B

過程wait的功能是等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行，而signal的功能則是向合作進(jìn)程發(fā)送合作進(jìn)程所需要的消息名，并將其值置為true。 PP ：私用信號量：上面用wait（消息名）與signal（消息名）的方式，描述了進(jìn)程同步的一種實(shí)現(xiàn)方法。只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān)，稱該信號量為私用信號量。公用信號量：一個進(jìn)程Pi的私用信號量Semi是從制約進(jìn)程發(fā)送來的進(jìn)程Pi的執(zhí)行條件所需要的消息。與私用信號量相對應(yīng)，稱互斥時使用的信號量為公用信號量。私用信號量：上面用wait（消息名）與signal（消息名）用Ｐ，Ｖ原語操作實(shí)現(xiàn)同步

利用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程同步的方法與利用wait和signal過程時相同，也是分為三步。首先為各并發(fā)進(jìn)程設(shè)置私用信號量，然后為私用信號量賦初值，最后利用Ｐ，Ｖ原語和私用信號量規(guī)定各進(jìn)程的執(zhí)行順序。緩沖區(qū)隊(duì)列用Ｐ，Ｖ原語操作實(shí)現(xiàn)同步利用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程例：設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)（如上圖）。PA為發(fā)送進(jìn)程，PB為接收進(jìn)程。PA發(fā)送數(shù)據(jù)時調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：（1）在PA至少送一塊數(shù)據(jù)入一個緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長等于緩沖區(qū)長度），即緩沖區(qū)空時PB不能取數(shù)；（2）PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時，至少有一個緩沖區(qū)是空的，即緩沖區(qū)滿時PA不能送數(shù)；（3）由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出（FIFO）方式排列。描述發(fā)送過程deposit(data)和接收過程remove(data)。例：設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)（如上圖）。PA為解：由題意可知，進(jìn)程PA調(diào)用的過程deposit(data)和進(jìn)程PB調(diào)用的過程remove(data)必須同步執(zhí)行，因?yàn)檫^程deposit(data)的執(zhí)行結(jié)果是過程remove(data)的執(zhí)行條件，而當(dāng)緩沖隊(duì)列全部裝滿數(shù)據(jù)時，remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件，滿足同步定義。從而，按以下三步描述過程deposit(data)和remove(data)：（1）設(shè)Bufempty為進(jìn)程PA的私用信號量，Buffull為進(jìn)程PB的私用信號量；（2）令Bufempty的初始值為n（n為緩沖隊(duì)列的緩沖區(qū)個數(shù)），Buffull的初始值為0；（3）描述：解：由題意可知，進(jìn)程PA調(diào)用的過程deposit(dataPA:deposit(data): beginlocalx P(Bufempty)；

按FIFO方式選擇一個空緩沖區(qū)Buf(x)； Buf(x)←data Buf(x)置滿標(biāo)記

Ｖ（Buffull） endPB:remove(data): Beginlocalx

Ｐ（Buffull）；

按FIFO方式選擇一個裝滿數(shù)據(jù)的緩沖區(qū)Buf(x) data←Buf(x) Buf(x)置空標(biāo)記

Ｖ（Bufempty） endPA:deposit(data):思考與練習(xí)

設(shè)課程的前驅(qū)、后繼關(guān)系如下，若每修一門課程看作進(jìn)程Px（x∈1..6）試用P、V操作算法描述這種前驅(qū)與后繼關(guān)系。

計算機(jī)導(dǎo)論

高級語言程序設(shè)計計算機(jī)組成原理

數(shù)據(jù)結(jié)構(gòu)86匯編語言

計算機(jī)操作系統(tǒng)思考與練習(xí)設(shè)課程的前驅(qū)、后繼關(guān)系如下，若生產(chǎn)者-消費(fèi)者問題把并發(fā)進(jìn)程的同步和互斥問題一般化，可以得到一個抽象的一般模型，即生產(chǎn)者-消費(fèi)者問題。計算機(jī)系統(tǒng)中，每個進(jìn)程都申請使用和釋放各種不同類型的資源，這些資源既可以是像外設(shè)、內(nèi)存及緩沖區(qū)等硬件資源，也包括臨界區(qū)、數(shù)據(jù)、例程等軟件資源。把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者，而把釋放同類資源的進(jìn)程稱為該資源的生產(chǎn)者。例如在上面的計算進(jìn)程PC與打印進(jìn)程PP公用一個緩沖區(qū)的例子中，計算進(jìn)程PC把數(shù)據(jù)送入緩沖區(qū)，打印進(jìn)程PP從緩沖區(qū)中取數(shù)據(jù)打印輸出，因此，PC進(jìn)程相當(dāng)于數(shù)據(jù)資源的生產(chǎn)者，而PP進(jìn)程相當(dāng)于消費(fèi)者。生產(chǎn)者-消費(fèi)者問題把并發(fā)進(jìn)程的同步和互斥問題一般化，可以得到用信號量解決生產(chǎn)者/消費(fèi)者問題說明假如是一個生產(chǎn)者、一個消費(fèi)者，且緩沖區(qū)只有一個單元。 BeginProcessproducer

Processconsumer Buffer:integer; Begin

Begin Se,Sf:semaphore; Repeat

Repeat Se:=1;Sf:=0; Produceaproduct;

P(Sf);cobegin P(Se);

Takeaproduct;producer; Buffer:=product;

V(Se);consumer;V(Sf);

Consumer;coend Forever

ForeverEnd.End;

End;驗(yàn)證：1、緩沖區(qū)滿生產(chǎn)者不能送數(shù)；緩沖區(qū)空消費(fèi)者不能取數(shù) 2、在這個問題中同步隱含著互斥。用信號量解決生產(chǎn)者/消費(fèi)者問題說明假如是一個生產(chǎn)者、一個消費(fèi)用信號量解決生產(chǎn)者/消費(fèi)者問題說明假如是一個生產(chǎn)者、一個消費(fèi)者，且緩沖區(qū)有N個單元。當(dāng)緩沖區(qū)沒有放滿N個數(shù)據(jù)時，生產(chǎn)者進(jìn)程調(diào)用P（Se）都不會成為等待狀態(tài)，可以把數(shù)據(jù)送入緩沖區(qū)。但當(dāng)緩沖區(qū)中已有N個數(shù)據(jù)時，生產(chǎn)者進(jìn)程想要再送數(shù)將被拒絕。由于每送入一個數(shù)后要調(diào)用V（Sf），所以此時Sf的值表示緩沖區(qū)中可取的數(shù)據(jù)數(shù)，只要Sf≠0，消費(fèi)者進(jìn)程在調(diào)用P（Sf）后總可以從緩沖區(qū)取數(shù)。每取走一個數(shù)據(jù)就調(diào)用V（Se），因此增加了一個存放數(shù)據(jù)的位置。可以用指針in和out分別指示生產(chǎn)者進(jìn)程向緩沖區(qū)送數(shù)和消費(fèi)者進(jìn)程從緩沖區(qū)取數(shù)的相對位置；指針的初始值為“0”。這種情況下生產(chǎn)者與消費(fèi)者進(jìn)程的同步算法為：用信號量解決生產(chǎn)者/消費(fèi)者問題說明假如是一個生產(chǎn)者、一個消費(fèi)用信號量解決生產(chǎn)者/消費(fèi)者問題說明BeginProcessproducer

ProcessconsumerB:array[0..n-1]ofinteger;BeginBeginin,out:integer; Repeat

RepeatSe,Sf:semaphore; Produceaproduct;

P(Sf);in:=out:=0;P(Se);

TakeaproductfromB[out];Se:=n;Sf:=0;B[in]:=product;

out:=(out+1)modn;

cobegin in:=(in+1)modn;

V(Se);

producer; V(Sf);

Consumer;

consumer; ForeverForevercoend End;

End;End.說明：這時緩沖區(qū)可以看成是頭尾相連一個環(huán)形，in、out指針指出存取數(shù)的位置。驗(yàn)證：1、緩沖區(qū)滿生產(chǎn)者不能送數(shù)；緩沖區(qū)空消費(fèi)者不能取數(shù) 2、在這個問題中生產(chǎn)者與消費(fèi)者進(jìn)程有可能同時進(jìn)入緩沖區(qū)，但不會出錯。用信號量解決生產(chǎn)者/消費(fèi)者問題說明Begin把一個長度為ｎ的有界緩沖區(qū)（n>0)與一群生產(chǎn)者進(jìn)程Ｐ1，Ｐ2，…，Ｐm和一群消費(fèi)者進(jìn)程Ｃ1，Ｃ2，…，Ｃk聯(lián)系起來（如圖3.14所示）。設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用的過程deposit(data)和各消費(fèi)者使用的過程remove(data)可描述如下：首先，可以看到，上述生產(chǎn)者-消費(fèi)者問題是一個同步問題。即生產(chǎn)者和消費(fèi)者之間滿足如下條件：(1)消費(fèi)者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的；(2)生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間必須互斥執(zhí)行。把一個長度為ｎ的有界緩沖區(qū)（n>0)與一群生產(chǎn)者進(jìn)程Ｐ1，Ｐ圖3.14生產(chǎn)者-消費(fèi)者問題《計算機(jī)操作系統(tǒng)進(jìn)程調(diào)度》課件解讀

由以上分析，設(shè)公用信號量mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，設(shè)信號量avail為生產(chǎn)者進(jìn)程的私用信號量，信號量full為消費(fèi)者進(jìn)程的私用信號量。信號量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號量mutex表示可用有界緩沖區(qū)的個數(shù)，初值為1。從而有： deposit(data): begin

Ｐ（avail）

Ｐ（mutex）

送數(shù)據(jù)入緩沖區(qū)某單元

Ｖ（full）

Ｖ（mutex） end 由以上分析，設(shè)公用信號量mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)

remove(data): begin

Ｐ（full）

Ｐ（mutex）

取緩沖區(qū)中某單元數(shù)據(jù)

Ｖ（avail）

Ｖ（mutex） end

在上例中，由于一個過程中包含有幾個公用、私用信號量，因此，Ｐ、Ｖ原語的操作次序要非常小心。一般說來，由于Ｖ原語是釋放資源的，所以可以以任意次序出現(xiàn)。但Ｐ原語則不然，如果次序混亂，將會造成進(jìn)程之間的死鎖。關(guān)于死鎖，將在3.8中介紹。 remove(data):用信號量解決生產(chǎn)者/消費(fèi)者問題說明假設(shè)是M個生產(chǎn)者、R個消費(fèi)者，且緩沖區(qū)有N個單元?，F(xiàn)在不僅生產(chǎn)者與消費(fèi)者之間要同步，而且M個生產(chǎn)者之間、R個消費(fèi)者之間還必須互斥地訪問緩沖區(qū)。要同步的原因和前面的問題一樣；之所以要互斥是因?yàn)槿绻鸐個生產(chǎn)者進(jìn)程各自個向緩沖區(qū)送數(shù)，當(dāng)?shù)谝粋€生產(chǎn)者按指針in指示的位置送一個數(shù)，但在改變指針前可能被打斷執(zhí)行，于是當(dāng)?shù)诙€生產(chǎn)者送數(shù)時仍按原指針?biāo)赋龅奈恢么娣?，這樣兩個數(shù)被放在同一個單元，造成數(shù)據(jù)丟失。同樣，R個消費(fèi)者都要取數(shù)時可能都從指針out指出的位置取數(shù)，造成一個數(shù)據(jù)被重復(fù)取出。用信號量解決生產(chǎn)者/消費(fèi)者問題說明假設(shè)是M個生產(chǎn)者、R個消費(fèi)用信號量解決生產(chǎn)者/消費(fèi)者問題說明如果該問題描述在任一時刻只能有一方(生產(chǎn)者或消費(fèi)者)訪問緩沖區(qū)。即一次只能有一個進(jìn)程可以進(jìn)入緩沖區(qū)。這是第一種方法（書上前例）?？墒?、當(dāng)有一個生產(chǎn)者（或消費(fèi)者）在送數(shù)（或取數(shù)）時，可以允許一個消費(fèi)者（或生產(chǎn)者）同時訪問緩沖區(qū)去取數(shù)（或送數(shù)）。因此這是第二種方法。顯然、第二種方法的并行性要比第一種方法的并行性高。用信號量解決生產(chǎn)者/消費(fèi)者問題說明如果該問題描述在任一時刻只用信號量解決生產(chǎn)者/消費(fèi)者問題說明第一種方法BeginProcessproduceri

ProcessconsumerjB:array[0..n-1]ofinteger;BeginBeginin,out:integer; Repeat

RepeatS,Se,Sf:semaphore; Produceaproduct;

P(Sf);

in:=out:=0;

P(Se)P(S);S:=1;Se:=n;Sf:=0P(S);

TakeaproductfromB[out];cobeginB[in]:=product;out:=(out+1)modn;

producer;in:=(in+1)modn;

V(Se);

consumer; V(Sf)

;

V(S);coendV(S);

Consumer;End. ForeverForever

End;

End;

思考：1、如果生產(chǎn)者或消費(fèi)者進(jìn)程中的兩個P操作次序?qū)φ{(diào)

可以嗎？ 2、第二種方法應(yīng)該如何改寫？用信號量解決生產(chǎn)者/消費(fèi)者問題說明第一種方法思考與練習(xí)

有三個進(jìn)程R、P、D，進(jìn)程R從輸入設(shè)備上讀數(shù)據(jù)到緩沖區(qū)B，進(jìn)程P將緩沖區(qū)B中的數(shù)據(jù)寫到磁帶、進(jìn)程D將緩沖區(qū)B中的數(shù)據(jù)寫到磁盤（即把一個數(shù)據(jù)做兩個副本分別存放在磁盤和磁帶上），P、D互斥共享緩沖區(qū)B；設(shè)B只能放一個數(shù)據(jù)，試用信號量機(jī)制寫出R、P、D三個進(jìn)程的同步工作算法。思考與練習(xí) 有三個進(jìn)程R、P、D，進(jìn)程R從輸入設(shè)解答分析：R與P、R與D之間為同步關(guān)系；P與D之間為互斥關(guān)系信號量：S表示P、D之間的互斥，初值為1 Se1、Sf1表示R、P之間的同步關(guān)系，Se1初值為1、Sf1初值為0 Se2、Sf2表示R、D之間的同步關(guān)系，Se2初值為1、Sf2初值為0算法：R（）、P（）、D（）并發(fā)執(zhí)行。 R（）P（）D（） while(1)while(1)while(1) {讀數(shù)；{P（Sf1）；{P（Sf2）；P（Se1）；P（S）；P（S）；P（Se2）；從B中取數(shù)到磁帶；從B中取數(shù)到磁盤；

送數(shù)到B中；V（S）；V（S）；V（Sf1）；V（Se1）；V（Se2）；V（Sf2）；}} }解答分析：R與P、R與D之間為同步關(guān)系；P與D之間為互斥關(guān)系并發(fā)控制是否完全解決問題？死鎖并發(fā)控制是否完全解決問題？死鎖

死鎖：指各并發(fā)進(jìn)程彼此互相等待對方所擁有的資源，且這些并發(fā)進(jìn)程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。死鎖死鎖：指各并發(fā)進(jìn)程彼此互相等待對方所擁有的資源，且死鎖的起因死鎖的起因是并發(fā)進(jìn)程的資源競爭。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個數(shù)少于并發(fā)進(jìn)程所要求的該類資源數(shù)。顯然，由于資源的有限性，不可能為所有要求資源的進(jìn)程無限制地提供資源。但是，可以采用適當(dāng)?shù)馁Y源分配算法，以達(dá)到消除死鎖的目的。為此，先看看產(chǎn)生死鎖的必要條件。死鎖的起因死鎖的起因是并發(fā)進(jìn)程的資源競爭。產(chǎn)生死鎖的根本原因產(chǎn)生死鎖的必要條件(1)互斥條件。并發(fā)進(jìn)程所要求和占有的資源是不能同時被兩個以上進(jìn)程使用或操作的，進(jìn)程對它所需要的資源進(jìn)行排他性控制。(2)不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行剝奪，而只能由獲得該資源的進(jìn)程自己釋放。(3)部分分配。進(jìn)程每次申請它所需要的一部分資源，在等待新資源的同時繼續(xù)占用已分配到的資源。(4)環(huán)路條件。存在一種進(jìn)程循環(huán)鏈，鏈中每一個進(jìn)程已獲得的資源同時被下一個進(jìn)程所請求。

顯然，只要使上述4個必要條件中的某一個不滿足，則死鎖就可以排除。產(chǎn)生死鎖的必要條件(1)互斥條件。并發(fā)進(jìn)程所要求和占有的資死鎖的排除方法

預(yù)防是采用某種策略，限制并發(fā)進(jìn)程對資源的請求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時間都不滿足。

避免是指系統(tǒng)在分配資源時，根據(jù)資源的使用情況提前做出預(yù)測，從而避免死鎖的發(fā)生。

死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來。在實(shí)際操作系統(tǒng)中大都使用檢測與恢復(fù)法排除死鎖。死鎖的排除方法死鎖預(yù)防1.打破資源的互斥條件。例如允許進(jìn)程同時訪問某些資源等2.打破不可剝奪條件，即允許剝奪。3.打破資源的部分分配。即預(yù)先分配各并發(fā)進(jìn)程所需要的全部資源。如某個進(jìn)程的資源得不到滿足時，則安排一定的等待次序讓其他進(jìn)程釋放資源。4.打破死鎖的環(huán)路條件。即把資源分類按順序排列，使進(jìn)程在申請、保持資源時不形成環(huán)路。死鎖預(yù)防1.打破資源的互斥條件。例如允許進(jìn)程同時訪問某些資源死鎖避免

死鎖避免可被稱為動態(tài)預(yù)防，因?yàn)橄到y(tǒng)采用動態(tài)分配資源，在分配過程中預(yù)測出死鎖發(fā)生的可能性并采取措施加以避免。

死鎖避免方法并不是嚴(yán)格限制產(chǎn)生死鎖必要條件的存在，只是防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。死鎖避免算法就是避免系統(tǒng)進(jìn)入不安全狀態(tài)的算法。銀行家（Banker）算法是最著名的死鎖避免算法死鎖避免死鎖避免可被稱為動態(tài)預(yù)防，因?yàn)橄到y(tǒng)采首先，從每個進(jìn)程預(yù)先得到有關(guān)該進(jìn)程所需要資源的信息。然后，通過仔細(xì)的分配資源來避免死鎖。（1）分配要使計算機(jī)系統(tǒng)總是停留在“安全”狀態(tài)。（2）確保僅僅將以避免死鎖的方式分配資源。如果存在一個安全序列，那么系統(tǒng)處于安全狀態(tài)。存在進(jìn)程順序P1、P2、P3、…、Pn如果對于每個Pi，Pi

申請的資源小于當(dāng)前可用資源加上所有進(jìn)程Pj

（其中j<i）所占有的資源，那么這一順序?yàn)榘踩蛄?。如果沒有這樣的順序存在，那么系統(tǒng)就處于不安全狀態(tài)。首先，從每個進(jìn)程預(yù)先得到有關(guān)該進(jìn)程所需要資源是否存在安全序列？系統(tǒng):12個磁帶機(jī)，3個進(jìn)程

當(dāng)前可用的有：3個磁帶機(jī)

最大需求

當(dāng)前占有P0 10 5P1 4 2P2 9 2存在安全序列：P1,P0,P2所以系統(tǒng)處于安全狀態(tài)是否存在安全序列？系統(tǒng):12個磁帶機(jī)，3個進(jìn)程 設(shè)系統(tǒng)有三種類型的資源，數(shù)量為(4，2，2)，系統(tǒng)中有進(jìn)程A，B，C按如下順序請求資源：

進(jìn)程A申請(3，2，1)

進(jìn)程B申請(1，0，1)

進(jìn)程A申請(0，1，0)

進(jìn)程C申請(2，0，0)

請你給出一種防止死鎖的資源剝奪分配策略，完成上述請求序列，并列出資源分配過程，指明哪些進(jìn)程需要等待，哪些資源被剝奪。設(shè)系統(tǒng)有三種類型的資源，數(shù)量為(4，2，2)，系統(tǒng)中有進(jìn)程A銀行家算法的主要思想（1）若進(jìn)程Pi的申請超過了其申報的最大需求數(shù)，則報錯；（2）若進(jìn)程Pi的申請超過了可用資源數(shù)，則Pi必須等待；（3）否則，系統(tǒng)暫時為進(jìn)程Pi分配其所需要的資源，修改資源分配狀態(tài)；（4）調(diào)用安全算法檢查系統(tǒng)當(dāng)前狀態(tài)，若導(dǎo)致不安全狀態(tài)，則推遲這種分配。銀行家算法的主要思想（1）若進(jìn)程Pi的申請超過了其申報的最大死鎖檢測與恢復(fù)

當(dāng)進(jìn)程進(jìn)行資源請求時死鎖檢測算法檢查并發(fā)進(jìn)程組是否構(gòu)成資源的請求和保持環(huán)路。有限狀態(tài)轉(zhuǎn)移圖和petriNet等技術(shù)都可用來有效地判斷死鎖發(fā)生。死鎖的恢復(fù)辦法較多。最簡單的辦法是終止各鎖住進(jìn)程，或按一定的順序中止進(jìn)程序列，直至已釋放到有足夠的資源來完成剩下的進(jìn)程時為止。另外，也可以從被鎖住進(jìn)程強(qiáng)迫剝奪資源以解除死鎖。死鎖檢測與恢復(fù)當(dāng)進(jìn)程進(jìn)行資源請求時死鎖檢測線程

引入線程主要是為了提高系統(tǒng)的執(zhí)行效率，減少處理機(jī)的空轉(zhuǎn)時間和調(diào)度切換（保護(hù)現(xiàn)場信息）的時間，以及便于系統(tǒng)管理。

線程：一個進(jìn)程內(nèi)的基本調(diào)度單位，或稱為輕權(quán)進(jìn)程（Lightweightprocess），這個調(diào)度單位既可以由操作系統(tǒng)內(nèi)核控制，也可以由用戶程序控制。線程引入線程主要是為了提高系統(tǒng)的執(zhí)行效率，進(jìn)程與線程的關(guān)系ResourcesProgramcodeDataDataProcessstatusThreadstatusHeavyweightprocessThreads(e.g.,openfiles)進(jìn)程與線程的關(guān)系ResourcesProgramDataDa計算機(jī)操作系統(tǒng)

——進(jìn)程調(diào)度

計算機(jī)操作系統(tǒng)72摘要基礎(chǔ)：進(jìn)程調(diào)度策略：進(jìn)程調(diào)度實(shí)現(xiàn)：互斥與同步

-避免：死鎖與饑餓 -解決：幾個經(jīng)典問題（如生產(chǎn)者-消費(fèi)者） -了解：進(jìn)程通信摘要單道程序與多道程序的執(zhí)行單道程序執(zhí)行的過程多道程序執(zhí)行的過程單道程序與多道程序的執(zhí)行單道程序執(zhí)行的過程課堂思考與練習(xí) 設(shè)時刻0，在內(nèi)存中有三個程序A、B、C，占用CPU的優(yōu)先權(quán)為A最高，C最低；它們的計算和I/O操作時間如表所示。試畫出單道運(yùn)行和多道運(yùn)行的時間關(guān)系圖。課堂思考與練習(xí) 設(shè)時刻0，在內(nèi)存中有三個程序什么叫進(jìn)程？為什么要引入“進(jìn)程”這一概念？為了提高系統(tǒng)資源的利用率，出現(xiàn)了多道程序設(shè)計技術(shù)，但多道程序的并發(fā)執(zhí)行和資源共享帶來了新的問題，破壞了程序的封閉性和可再現(xiàn)性，程序和機(jī)器執(zhí)行程序的活動不再一一對應(yīng)，并發(fā)程序之間有可能存在相互制約關(guān)系。并發(fā)程序的獨(dú)立性、并發(fā)性、動態(tài)性和相互制約反映了并發(fā)程序的本質(zhì)，而程序的概念已不能反映程序并發(fā)執(zhí)行的實(shí)質(zhì)，因此，人們引入了進(jìn)程的概念來描述并發(fā)程序的執(zhí)行過程。進(jìn)程：一個具有獨(dú)立功能的程序?qū)δ硞€數(shù)據(jù)集在處理機(jī)上的執(zhí)行過程和分配資源的基本單位。這里，程序指一組操作序列，而數(shù)據(jù)集則是接受程序規(guī)定操作的一組存儲單元的內(nèi)容。進(jìn)程=程序的執(zhí)行？什么叫進(jìn)程？為什么要引入“進(jìn)程”這一概念？進(jìn)程和程序的區(qū)別和關(guān)系？進(jìn)程和程序是兩個既有聯(lián)系又有區(qū)別的概念，它們的區(qū)別和關(guān)系可簡述如下：(1)進(jìn)程是一個動態(tài)概念，而程序則是一個靜態(tài)概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進(jìn)程則強(qiáng)調(diào)執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2)進(jìn)程具有并行特征，而程序沒有。由進(jìn)程的定義可知，進(jìn)程具有并行特征的兩個方面，即獨(dú)立性和異步性。也就是說，在不考慮資源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3)進(jìn)程是競爭計算機(jī)系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對進(jìn)程獨(dú)立性和異步性的限制。(4)不同的進(jìn)程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。進(jìn)程和程序的區(qū)別和關(guān)系？進(jìn)程和程序是兩個如何監(jiān)控程序的執(zhí)行？用各種數(shù)據(jù)結(jié)構(gòu)來記錄多個進(jìn)程（PCB）用狀態(tài)的變遷來跟蹤多個進(jìn)程用進(jìn)程調(diào)度來選擇控制多個進(jìn)程用并發(fā)控制來同步、協(xié)調(diào)多個進(jìn)程如何監(jiān)控程序的執(zhí)行？用各種數(shù)據(jù)結(jié)構(gòu)來記錄多個進(jìn)程（PCB）進(jìn)程的靜態(tài)描述進(jìn)程=程序+數(shù)據(jù)+進(jìn)程控制塊PCB

程序描述進(jìn)程所要完成的功能

數(shù)據(jù)是對其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集，程序在執(zhí)行時必不可少的工作區(qū)和操作對象。進(jìn)程控制塊包含了有關(guān)進(jìn)程的描述信息、控制信息以及資源信息，是進(jìn)程動態(tài)特征的集中反映。進(jìn)程的靜態(tài)描述進(jìn)程=程序+數(shù)據(jù)+進(jìn)程控制塊PCB進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程控制進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。1.進(jìn)程創(chuàng)建2.進(jìn)程撤銷3.進(jìn)程阻塞4.進(jìn)程喚醒5.進(jìn)程切換：在某一時刻，一運(yùn)行的進(jìn)程被迫中斷，讓出CPU給指定進(jìn)程。一般在進(jìn)行進(jìn)程上下文切換時，不保留被切換的進(jìn)程上下文的正文，但保留進(jìn)程執(zhí)行時所使用的寄存器。進(jìn)程控制進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序《計算機(jī)操作系統(tǒng)進(jìn)程調(diào)度》課件解讀《計算機(jī)操作系統(tǒng)進(jìn)程調(diào)度》課件解讀程序執(zhí)行過程①單進(jìn)程單一進(jìn)程②多進(jìn)程獨(dú)立進(jìn)程彼此獨(dú)立③多進(jìn)程協(xié)作進(jìn)程彼此依賴在并發(fā)環(huán)境下不存在完全獨(dú)立的進(jìn)程！程序執(zhí)行過程①單進(jìn)程單一進(jìn)程②多進(jìn)程獨(dú)立進(jìn)程③多進(jìn)程協(xié)作進(jìn)程程序執(zhí)行過程④多進(jìn)程競爭進(jìn)程共享互斥共享資源⑤多進(jìn)程通信進(jìn)程相互通信程序執(zhí)行過程④多進(jìn)程競爭進(jìn)程共享資源⑤多進(jìn)程通信進(jìn)程程序執(zhí)行過程中的問題①②不存在資源競爭，只存在CPU調(diào)度③④⑤多個進(jìn)程相互依賴、彼此競爭資源，既存在CPU調(diào)度，又存在同步協(xié)調(diào)，從而引入并發(fā)控制。并發(fā)控制的實(shí)施策略：臨界資源與臨界區(qū)機(jī)制：標(biāo)志、信號量方法：加鎖、P、V原語實(shí)現(xiàn)：互斥和同步程序執(zhí)行過程中的問題①②不存在資源競爭，只存在CPU調(diào)度進(jìn)程互斥（1）臨界資源：一次僅允許一個進(jìn)程使用的共享資源。每次只準(zhǔn)許一個進(jìn)程進(jìn)入臨界區(qū)，進(jìn)入后不允許其他進(jìn)程進(jìn)入。對于臨界資源，多個進(jìn)程必須互斥地對它進(jìn)行訪問。臨界區(qū)：每個進(jìn)程中訪問臨界資源的那段代碼。

臨界區(qū)是由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。間接制約：由共享公有資源而造成的對并發(fā)進(jìn)程執(zhí)行速度的間接制約。即把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象。進(jìn)程互斥（1）臨界資源：一次僅允許一個進(jìn)程使用的共享資源。每進(jìn)程互斥（2）互斥：一組并發(fā)進(jìn)程中的一個或多個程序段，因共享某一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個以上的共享該資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)稱為互斥。進(jìn)程互斥：一個進(jìn)程正在訪問臨界資源，另一個要訪問該資源的進(jìn)程必須等待。當(dāng)占用臨界資源的進(jìn)程退出臨界區(qū)，才允許另一進(jìn)程區(qū)訪問此臨界資源。為了禁止兩個進(jìn)程同時進(jìn)入臨界區(qū)，需采用一定的方法來協(xié)調(diào)它們。無論方法是什么都應(yīng)遵循下述準(zhǔn)則：空閑讓出忙則等待讓權(quán)等待有限等待進(jìn)程互斥（2）互斥：一組并發(fā)進(jìn)程中的一個或多個程序段，因共享進(jìn)程互斥（3）互斥的加鎖實(shí)現(xiàn)對臨界區(qū)加鎖以實(shí)現(xiàn)互斥：當(dāng)某個進(jìn)程進(jìn)入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進(jìn)程在申請進(jìn)入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。進(jìn)程互斥（3）互斥的加鎖實(shí)現(xiàn)進(jìn)程互斥（4）

設(shè)臨界區(qū)的類名為Ｓ。為了保證每一次臨界區(qū)中只能有一個程序段被執(zhí)行，又設(shè)鎖定位key［Ｓ］。key［Ｓ］表示該鎖定位屬于類名為Ｓ的臨界區(qū)。加鎖后的臨界區(qū)程序描述如下：

lock(key［Ｓ］) 〈臨界區(qū)〉 unlock(key［Ｓ］)設(shè)key［Ｓ］=1時表示類名為Ｓ的臨界區(qū)可用，key［Ｓ］=0時表示類名為Ｓ的臨界區(qū)不可用。進(jìn)程互斥（4）設(shè)臨界區(qū)的類名為Ｓ。為了保證每一次臨界區(qū)進(jìn)程互斥（5）一種簡便的實(shí)現(xiàn)方法是：

lock(x)=beginlocalv repeat v←x untilv=1 x←0 end因?yàn)楫?dāng)同時有幾個進(jìn)程調(diào)用lock(key［Ｓ］)時，在x←0語句執(zhí)行之前，可能已有兩個以上的多個進(jìn)程由于key［Ｓ］=1而進(jìn)入臨界區(qū)。為解決這個問題有些機(jī)器在硬件中設(shè)置了“測試與設(shè)置指令，保證第一步和第二步執(zhí)行不可分離。注意：在系統(tǒng)實(shí)現(xiàn)時鎖定位key［Ｓ］總是設(shè)置在公有資源所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。進(jìn)程互斥（5）一種簡便的實(shí)現(xiàn)方法是：進(jìn)程互斥（6）試考慮以下進(jìn)程PA和PB反復(fù)使用臨界區(qū)的情況：PA A：lock(key［Ｓ］) 〈Ｓ〉 unlock(key［Ｓ］) GotoAPB B：lock(key［Ｓ］)

＜Ｓ＞

unlock(key［Ｓ］) GotoB設(shè)進(jìn)程ＰA已通過lock(key［Ｓ］)過程而進(jìn)入臨界區(qū)。顯然，在進(jìn)程PA執(zhí)行unlock(key［Ｓ］)過程之前，key［Ｓ］=0且進(jìn)程PB沒有進(jìn)入臨界區(qū)的機(jī)會。然而，當(dāng)進(jìn)程PA執(zhí)行完unlock(key［Ｓ］)過程之后，由于緊接著是一轉(zhuǎn)向語句，進(jìn)程PA將又立即去執(zhí)行l(wèi)ock(key［Ｓ］)過程。此時，由于unlock(key［Ｓ］)過程已將key［Ｓ］的值置為1，也就是開鎖狀態(tài)，從而進(jìn)程PA又可進(jìn)入臨界區(qū)Ｓ。只有在進(jìn)程PA執(zhí)行完unlock(key［Ｓ］)過程之后、執(zhí)行GotoA語句之前的瞬間發(fā)生進(jìn)程調(diào)度，使進(jìn)程PA把處理機(jī)轉(zhuǎn)讓給進(jìn)程PB，進(jìn)程PB才有可能得到執(zhí)行。然而遺憾的是，這種可能性是非常小的。因此，進(jìn)程PB將處于永久饑餓狀態(tài)（starvation）。使用加鎖法實(shí)現(xiàn)進(jìn)程間互斥時，還將導(dǎo)致在某些情況下出現(xiàn)不公平現(xiàn)象。進(jìn)程互斥（6）試考慮以下進(jìn)程PA和PB反復(fù)使用臨界區(qū)的情況：進(jìn)程互斥（7）這正如某個學(xué)生想使用某個人人都可借用、且不規(guī)定使用時間的教室時一樣，他必須首先申請獲得使用該教室的權(quán)利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復(fù)將持續(xù)到他進(jìn)門后為止。從這個例子中，可以得到解決加鎖法所帶來的問題的方法。一種最直觀的辦法是，設(shè)置一個教室管理員。從而，如果有學(xué)生申請使用教室而未能如愿時，教室管理員記下他的名字，并等到教室門一打開則通知該學(xué)生進(jìn)入。這樣，既減少了學(xué)生多次來去教室檢查門是否被打開的時間，又減少了因?yàn)閷W(xué)生自發(fā)地檢查造成的不公平現(xiàn)象。在操作系統(tǒng)中，這個管理員就是信號量。信號量管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源實(shí)體。進(jìn)程互斥（7）這正如某個學(xué)生想使用某個人人都可借用、且不規(guī)定進(jìn)程互斥（8）信號量信號量的概念和下面所述的Ｐ、Ｖ原語是荷蘭科學(xué)家E.W.Dijkstra提出來的。信號是鐵路交通管理中的一種常用設(shè)備，交通管理人員利用信號顏色的變化來實(shí)現(xiàn)交通管理。在操作系統(tǒng)中，信號量sem是一整數(shù)。在sem大于等于零時代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但sem小于零時則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。顯然，用于互斥的信號量sem的初值應(yīng)該大于零，而建立一個信號量必須經(jīng)過說明所建信號量所代表的意義，和賦初值以及建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以便指向那些等待使用該臨界區(qū)的進(jìn)程。進(jìn)程互斥（8）信號量進(jìn)程互斥（9）Ｐ，Ｖ原語信號量的數(shù)值僅能由Ｐ，Ｖ原語操作改變(Ｐ和Ｖ分別是荷蘭語Passeren和Verhoog的頭一個字母，相當(dāng)于英文的pass和increment的意思)。采用Ｐ，Ｖ原語，可以把類名為Ｓ的臨界區(qū)描述為WhenＳdoＰ(sem)臨界區(qū)Ｖ(sem)od。這里，sem是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號量。一次Ｐ原語操作使得信號量sem減1，而一次Ｖ原語操作將使得信號量sem加1。必須強(qiáng)調(diào)的一點(diǎn)是，當(dāng)某個進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時，其他進(jìn)程如果執(zhí)行了Ｐ原語操作，則該進(jìn)程并不像調(diào)用lock時那樣因進(jìn)不了臨界區(qū)而返回到lock的起點(diǎn)，等以后重新執(zhí)行測試，而是在等待隊(duì)列中等待有其他進(jìn)程做Ｖ原語操作釋放資源后，進(jìn)入臨界區(qū)，這時，Ｐ原語的執(zhí)行才算真正結(jié)束。另外，當(dāng)有好幾個進(jìn)程執(zhí)行Ｐ原語未通過而進(jìn)入等待狀態(tài)之后，如有某進(jìn)程作了Ｖ原語操作，則等待進(jìn)程中的一個可以進(jìn)入臨界區(qū)，但其他進(jìn)程必須等待。進(jìn)程互斥（9）Ｐ，Ｖ原語進(jìn)程互斥（10）Ｐ原語操作的主要動作是：(1)sem減1；(2)若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3)若sem減1后小于零，則該進(jìn)程被阻塞后與該信號相對應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。進(jìn)程互斥（10）Ｐ原語操作的主要動作是：進(jìn)程互斥（11）Ｖ原語的操作主要動作是：(1)sem加1；(2)若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3)若相加結(jié)果小于或等于零，則從該信號的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。進(jìn)程互斥（11）Ｖ原語的操作主要動作是：用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥利用Ｐ，Ｖ原語和信號量，可以方便地解決并發(fā)進(jìn)程的互斥問題，而且不會產(chǎn)生使用加鎖法解決互斥問題時所出現(xiàn)的問題。設(shè)信號量sem是用于互斥的信號量，且其初值為1表示沒有并發(fā)進(jìn)程使用該臨界區(qū)。顯然，由上面幾節(jié)的討論可知，只要把臨界區(qū)置于Ｐ(sem)和Ｖ(sem)之間，即可實(shí)現(xiàn)進(jìn)程間的互斥。當(dāng)一個進(jìn)程想要進(jìn)入臨界區(qū)時，它必須先執(zhí)行Ｐ原語操作以將信號量sem減1。在一個進(jìn)程完成對臨界區(qū)的操作之后，它必須執(zhí)行Ｖ原語操作以釋放它所占用的臨界區(qū)。由于信號量初始值為1，所以，任一進(jìn)程在執(zhí)行Ｐ原語操作之后將sem的值變?yōu)?，表示該進(jìn)程可以進(jìn)入臨界區(qū)。用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥用信號量實(shí)現(xiàn)互斥時值的變化wait(s)p1s10-1-2-101criticalsignal(s)wait(s)criticalsignal(s)p2wait(s)criticalsignal(s)p3semaphoreWait操作信號量非負(fù)，P1進(jìn)入臨界區(qū)Wait操作信號量為負(fù)，P2阻塞Wait操作信號量為負(fù)，P3阻塞Signal操作后信號量非正，從等待隊(duì)列中喚醒一個進(jìn)程Signal操作后信號量非正，從等待隊(duì)列中喚醒一個進(jìn)程Signal操作后信號量為正，表示已無進(jìn)程在臨界區(qū)用信號量實(shí)現(xiàn)互斥時值的變化wait(s)p1scritica用信號量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：1)設(shè)sem為互斥信號量，其取值范圍為(1,0,-1)。其中sem=1表示進(jìn)程PA和PB都未進(jìn)入類名為Ｓ的臨界區(qū)，sem=0表示進(jìn)程PA或PB已進(jìn)入類名為Ｓ的臨界區(qū)，sem=-1表示進(jìn)程PA和PB中，一個進(jìn)程已進(jìn)入臨界區(qū)，而另一個進(jìn)程等待進(jìn)入臨界區(qū)。2）描述： PA：

Ｐ（sem） 〈Ｓ〉

Ｖ（sem）：

：

： PB：

Ｐ（sem） 〈Ｓ〉

Ｖ（sem）∷

：

：用信號量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：練習(xí)與思考一試用P、V操作實(shí)現(xiàn)飛機(jī)聯(lián)網(wǎng)售票系統(tǒng)中各地N個終端的終端售票進(jìn)程發(fā)售同月同日同一次航班機(jī)票的過程。練習(xí)與思考一試用P、V操作實(shí)現(xiàn)飛機(jī)聯(lián)網(wǎng)售票系統(tǒng)中各地N個終端例：設(shè)余票單元為count，有N個售票進(jìn)程正確并發(fā)執(zhí)行的算法 ProcessPi(i=1,2,…n) Beginbegin

count:integer;s:semaphore;

VarXi:integer;s:=1;

按旅客要求找到count; cobegin P(s);P1; Xi:=count;P2; IfXi>=1then …… beginPn; Xi:=Xi-1; coend Xi:=count;end. V(s);

輸出一張票; End Else

輸出“票已售完”; End; 例：設(shè)余票單元為count，有N個售票進(jìn)程正確并發(fā)執(zhí)行思考與練習(xí)二兩個火車站A、B之間是單軌連接，現(xiàn)有許多列車同時到達(dá)A站，經(jīng)A站到B站，列車駛出B站后又可分路行駛。為了保證行車安全，請用信號量機(jī)制設(shè)計一個自動調(diào)度算法。思考與練習(xí)二兩個火車站A、B之間是單軌連接，現(xiàn)有許多列車Programmutualexclusion;begin(*mainprogram*) Count=n;(*n為列車數(shù)*);cobegin Vars:semaphore(:=1);P(1); ProcedureP(i:integer);P(2); Begin……