《計算機操作系統(tǒng)-進程調(diào)度》課件

1、計算機操作系統(tǒng)計算機操作系統(tǒng) 進程調(diào)度進程調(diào)度摘要基礎：進程調(diào)度策略：進程調(diào)度實現(xiàn)：互斥與同步- 避免：死鎖與饑餓避免：死鎖與饑餓- 解決：幾個經(jīng)典問題（如生產(chǎn)者解決：幾個經(jīng)典問題（如生產(chǎn)者-消費者）消費者）- 了解：進程通信了解：進程通信單道程序與多道程序的執(zhí)行 單道程序執(zhí)行的過程 多道程序執(zhí)行的過程課堂思考與練習 設時刻0，在內(nèi)存中有三個程序A、B、C，占用CPU的優(yōu)先權(quán)為A最高，C最低；它們的計算和I/O操作時間如表所示。試畫出單道運行和多道運行的時間關(guān)系圖。 什么叫進程？為什么要引入“進程”這一概念？ 為了提高系統(tǒng)資源的利用率，出現(xiàn)了多道程序設計技術(shù)，但多道程序的并發(fā)執(zhí)行和資源共享帶來

2、了新的問題，破壞了程序的封閉性和可再現(xiàn)性，程序和機器執(zhí)行程序的活動不再一一對應，并發(fā)程序之間有可能存在相互制約關(guān)系。并發(fā)程序的獨立性、并發(fā)性、動態(tài)性和相互制約反映了并發(fā)程序的本質(zhì)，而程序的概念已不能反映程序并發(fā)執(zhí)行的實質(zhì)，因此，人們引入了進程的概念來描述并發(fā)程序的執(zhí)行過程。進程：一個具有獨立功能的程序?qū)δ硞€數(shù)據(jù)集在處理機上的執(zhí)行過程和分配資源的基本單位。這里，程序指一組操作序列，而數(shù)據(jù)集則是接受程序規(guī)定操作的一組存儲單元的內(nèi)容。 進程 = 程序的執(zhí)行？進程和程序的區(qū)別和關(guān)系？ 進程和程序是兩個既有聯(lián)系又有區(qū)別的概念，它們的區(qū)別和關(guān)系可簡述如下：(1) 進程是一個動態(tài)概念，而程序則是一個靜態(tài)概念

3、。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進程則強調(diào)執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2) 進程具有并行特征，而程序沒有。由進程的定義可知，進程具有并行特征的兩個方面，即獨立性和異步性。也就是說，在不考慮資源共享的情況下，各進程的執(zhí)行是獨立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3) 進程是競爭計算機系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對進程獨立性和異步性的限制。(4) 不同的進程可以包含同一程序，只要該程序所對應的數(shù)據(jù)集不同。如何監(jiān)控程序的執(zhí)行？用各種數(shù)據(jù)結(jié)構(gòu)來記錄多個進程（PCB）用狀態(tài)的變遷來跟蹤多個進程用

4、進程調(diào)度來選擇控制多個進程用并發(fā)控制來同步、協(xié)調(diào)多個進程進程的靜態(tài)描述進程=程序+數(shù)據(jù)+進程控制塊PCB 程序描述進程所要完成的功能 數(shù)據(jù)是對其進行操作的數(shù)據(jù)結(jié)構(gòu)集，程序在執(zhí)行時必不可少的工作區(qū)和操作對象。 進程控制塊包含了有關(guān)進程的描述信息、控制信息以及資源信息，是進程動態(tài)特征的集中反映。進程狀態(tài)及轉(zhuǎn)換進程控制 進程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進程以及完成進程各狀態(tài)間的轉(zhuǎn)換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實現(xiàn)資源共享的目的。 1.進程創(chuàng)建 2.進程撤銷 3.進程阻塞 4.進程喚醒 5.進程切換：在某一時刻，一運行的進程被迫中斷，讓出CPU給指定進程。一般在進行

5、進程上下文切換時，不保留被切換的進程上下文的正文，但保留進程執(zhí)行時所使用的寄存器。程序執(zhí)行過程單進程單一進程多進程獨立進程彼此獨立多進程協(xié)作進程彼此依賴在并發(fā)環(huán)境下不存在完全獨立的進程 ！程序執(zhí)行過程多進程競爭進程共享互斥共享資源多進程通信進程相互通信程序執(zhí)行過程中的問題不存在資源競爭，只存在CPU調(diào)度多個進程相互依賴、彼此競爭資源，既存在CPU調(diào)度，又存在同步協(xié)調(diào)，從而引入并發(fā)控制。并發(fā)控制的實施 策略：臨界資源與臨界區(qū) 機制：標志、信號量 方法：加鎖、P、V原語 實現(xiàn)：互斥和同步進程互斥（1） 臨界資源：一次僅允許一個進程使用的共享資源。每次只準許一個進程進入臨界區(qū)，進入后不允許其他進程進

6、入。對于臨界資源，多個進程必須互斥地對它進行訪問。 臨界區(qū)：每個進程中訪問臨界資源的那段代碼。 臨界區(qū)是由屬于不同并發(fā)進程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。 間接制約：由共享公有資源而造成的對并發(fā)進程執(zhí)行速度的間接制約。即把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進程交叉執(zhí)行的現(xiàn)象。進程互斥（2） 互斥：一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為互斥。 進程互斥：一個進程正在訪問臨界資源，另一個要訪問該資源的進程必須等待。當占用臨界資源的進程退出臨界區(qū)，

7、才允許另一進程區(qū)訪問此臨界資源。 為了禁止兩個進程同時進入臨界區(qū)，需采用一定的方法來協(xié)調(diào)它們。無論方法是什么都應遵循下述準則：空閑讓出忙則等待讓權(quán)等待1. 有限等待進程互斥（3） 互斥的加鎖實現(xiàn) 對臨界區(qū)加鎖以實現(xiàn)互斥：當某個進程進入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進程在申請進入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。進程互斥（4） 設臨界區(qū)的類名為。為了保證每一次臨界區(qū)中只能有一個程序段被執(zhí)行，又設鎖定位 key 。key表示該鎖定位屬于類名為的臨界區(qū)。加鎖后的臨界區(qū)程序描述如下：lock(key

8、 )臨 界 區(qū)unlock(key ) 設key =1時表示類名為的臨界區(qū)可用，key =0時表示類名為的臨界區(qū)不可用。進程互斥（5）一種簡便的實現(xiàn)方法是：lock (x)=begin local vrepeatvxuntilv=1x0end 因為當同時有幾個進程調(diào)用lock(key )時，在x0語句執(zhí)行之前，可能已有兩個以上的多個進程由于key =1而進入臨界區(qū)。為解決這個問題有些機器在硬件中設置了“測試與設置指令，保證第一步和第二步執(zhí)行不可分離。 注意：在系統(tǒng)實現(xiàn)時鎖定位key 總是設置在公有資源所對應的數(shù)據(jù)結(jié)構(gòu)中的。進程互斥（6）試考慮以下進程PA和PB反復使用臨界區(qū)的情況：PAA：lo

9、ck(key)unlock(key)Goto APBB：lock(key )unlock(key )Goto B 設進程A已通過lock(key )過程而進入臨界區(qū)。顯然，在進程PA執(zhí)行unlock(key )過程之前，key =0且進程PB沒有進入臨界區(qū)的機會。然而，當進程PA執(zhí)行完unlock(key )過程之后，由于緊接著是一轉(zhuǎn)向語句，進程PA將又立即去執(zhí)行l(wèi)ock(key )過程。此時，由于unlock(key)過程已將key的值置為1，也就是開鎖狀態(tài)，從而進程PA又可進入臨界區(qū)。只有在進程PA執(zhí)行完unlock(key)過程之后、執(zhí)行Goto A語句之前的瞬間發(fā)生進程調(diào)度，使進程PA

10、把處理機轉(zhuǎn)讓給進程PB，進程PB才有可能得到執(zhí)行。然而遺憾的是，這種可能性是非常小的。因此，進程PB將處于永久饑餓狀態(tài)（starvation）。 使用加鎖法實現(xiàn)進程間互斥時，還將導致在某些情況下出現(xiàn)不公平現(xiàn)象。進程互斥（7） 這正如某個學生想使用某個人人都可借用、且不規(guī)定使用時間的教室時一樣，他必須首先申請獲得使用該教室的權(quán)利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復將持續(xù)到他進門后為止。從這個例子中，可以得到解決加鎖法所帶來的問題的方法。一種最直觀的辦法是，設置一個教室管理員。從而，如果有學生申請使用教室而未能如愿時，教

11、室管理員記下他的名字，并等到教室門一打開則通知該學生進入。這樣，既減少了學生多次來去教室檢查門是否被打開的時間，又減少了因為學生自發(fā)地檢查造成的不公平現(xiàn)象。在操作系統(tǒng)中，這個管理員就是信號量。信號量管理相應臨界區(qū)的公有資源，它代表可用資源實體。進程互斥（8） 信號量 信號量的概念和下面所述的、原語是荷蘭科學家E.W.Dijkstra提出來的。信號是鐵路交通管理中的一種常用設備，交通管理人員利用信號顏色的變化來實現(xiàn)交通管理。在操作系統(tǒng)中，信號量sem是一整數(shù)。在sem大于等于零時代表可供并發(fā)進程使用的資源實體數(shù)，但sem小于零時則表示正在等待使用臨界區(qū)的進程數(shù)。顯然，用于互斥的信號量sem的初值

12、應該大于零，而建立一個信號量必須經(jīng)過說明所建信號量所代表的意義，和賦初值以及建立相應的數(shù)據(jù)結(jié)構(gòu)以便指向那些等待使用該臨界區(qū)的進程。進程互斥（9） ，原語 信號量的數(shù)值僅能由，原語操作改變(和分別是荷蘭語 Passeren 和Verhoog 的頭一個字母，相當于英文的pass和increment的意思)。采用，原語，可以把類名為的臨界區(qū)描述為When do (sem)臨界區(qū)(sem)od。 這里，sem是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號量。一次原語操作使得信號量sem減1，而一次原語操作將使得信號量sem加1。必須強調(diào)的一點是，當某個進程正在臨界區(qū)內(nèi)執(zhí)行時，其他進程如果執(zhí)行了原語操作，則該進

13、程并不像調(diào)用lock時那樣因進不了臨界區(qū)而返回到lock的起點，等以后重新執(zhí)行測試，而是在等待隊列中等待有其他進程做原語操作釋放資源后，進入臨界區(qū)，這時，原語的執(zhí)行才算真正結(jié)束。另外，當有好幾個進程執(zhí)行原語未通過而進入等待狀態(tài)之后，如有某進程作了原語操作，則等待進程中的一個可以進入臨界區(qū)，但其他進程必須等待。進程互斥（10） 原語操作的主要動作是： (1) sem減 1； (2) 若sem減1后仍大于或等于零，則進程繼續(xù)執(zhí)行； (3) 若sem減1后小于零，則該進程被阻塞后與該信號相對應的隊列中，然后轉(zhuǎn)進程調(diào)度。進程互斥（11） 原語的操作主要動作是： (1) sem加1； (2) 若相加結(jié)果

14、大于零，進程繼續(xù)執(zhí)行； (3) 若相加結(jié)果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉(zhuǎn)進程調(diào)度。用，原語實現(xiàn)進程互斥利用，原語和信號量，可以方便地解決并發(fā)進程的互斥問題，而且不會產(chǎn)生使用加鎖法解決互斥問題時所出現(xiàn)的問題。設信號量sem是用于互斥的信號量，且其初值為1表示沒有并發(fā)進程使用該臨界區(qū)。顯然，由上面幾節(jié)的討論可知，只要把臨界區(qū)置于(sem)和(sem)之間，即可實現(xiàn)進程間的互斥。當一個進程想要進入臨界區(qū)時，它必須先執(zhí)行原語操作以將信號量sem減1。在一個進程完成對臨界區(qū)的操作之后，它必須執(zhí)行原語操作以釋放它所占用的臨界區(qū)。由于信號量初始值為 1，所以

15、，任一進程在執(zhí)行原語操作之后將sem的值變?yōu)?，表示該進程可以進入臨界區(qū)。s10-1-2-101Wait 操作信號量非負，P1進入臨界區(qū)Wait 操作信號量為負，P2阻塞Wait 操作信號量為負，P3 阻塞Signal 操作后信號量非正，從等待隊列中喚醒一個進程Signal 操作后信號量非正，從等待隊列中喚醒一個進程Signal 操作后信號量為正，表示已無進程在臨界區(qū)用信號量實現(xiàn)兩并發(fā)進程PA，PB互斥的描述如下：1) 設 sem為互斥信號量，其取值范圍為(1,0,-1)。其中sem=1表示進程PA和PB都未進入類名為的臨界區(qū)，sem=0表示進程PA或PB已進入類名為的臨界區(qū)，sem=-1表示

16、進程PA和PB中，一個進程已進入臨界區(qū)，而另一個進程等待進入臨界區(qū)。2）描述：PA：（sem）（sem）：PB：（sem）（sem）：練習與思考一試用P、V操作實現(xiàn)飛機聯(lián)網(wǎng)售票系統(tǒng)中各地N個終端的終端售票進程發(fā)售同月同日同一次航班機票的過程。 例：設余票單元為 count，有 N 個售票進程正確并發(fā)執(zhí)行的算法Process Pi(i=1,2,n)Begin begin count:integer; s:semaphore; Var Xi:integer; s:=1;按旅客要求找到 count; cobeginP(s); P1;Xi:=count; P2;If Xi=1 then begin P

17、n;Xi:=Xi-1; coendXi:=count; end.V(s);輸出一張票;EndElse輸出“票已售完”;End; 思考與練習二兩個火車站 A、B 之間是單軌連接，現(xiàn)有許多列車同時到達 A 站，經(jīng) A 站到 B 站，列車駛出 B 站后又可分路行駛。為了保證行車安全，請用信號量機制設計一個自動調(diào)度算法。Program mutualexclusion; begin ( * main program * ) Count=n; (* n為列車數(shù)*); cobegin Var s:semaphore(:=1); P(1); Procedure P(i:integer); P(2); Begi

18、n P(n); Repeat coend P(s); end. 列車駛?cè)階、B段; V(s); 列車分路行駛 ForeverEnd;進程同步（1） 除了對公有資源的競爭而引起的間接制約之外，并發(fā)進程之間是否還存在著其他制約關(guān)系影響執(zhí)行速度呢？來看下面的例子。 計算進程和打印進程共同使用同一緩沖區(qū)Buf。計算進程反復地把每次計算結(jié)果放入 Buf中，而打印進程則把計算進程每次放入 Buf中的數(shù)據(jù)通過打印機打印輸出。如果不采取任何制約措施，這兩個進程的執(zhí)行起始時間和執(zhí)行速度都是彼此獨立的，其相應的控制段可以描述為：PC：:A:local BufRepeatBuf BufUntil Buf=空計算得到

19、計算結(jié)果Buf 計算結(jié)果Goto APP:：:B:local PriRepeatPri BufUntil Pri 空打印 Buf中的數(shù)據(jù)清除 Buf中的數(shù)據(jù)Goto B 直接制約：一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程。 進程同步：把異步環(huán)境下的一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程。具有同步關(guān)系的一組并發(fā)進程稱為合作進程，合作進程間互相發(fā)送的信號稱為消息或事件。 如果對一個消息或事件賦以唯一的消息名，則可用過程wait（消息名）表示進程等待合作進程發(fā)來的消息，而用過程signal（

20、消息名）表示向合作進程發(fā)送消息。利用過程wait和signal，可以簡單地描述上面例子中的計算進程PC和打印進程PP的同步關(guān)系如下：（1）設消息名Bufempty表示Buf空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。（2）初始化Bufempty=true，Buffull=false 。（3）描述：PC：A:wait（Bufempty）計算Buf 計算結(jié)果Bufempty falsesignal（Buffull）GotoAPP：B:wait（Buffull）打印Buf中的數(shù)據(jù)清除Buf中的數(shù)據(jù)Buffull falsesignal（Bufempty）GotoB過程wait的功能是等待到消息名

21、為true的進程繼續(xù)執(zhí)行，而signal的功能則是向合作進程發(fā)送合作進程所需要的消息名，并將其值置為true。 私用信號量：上面用wait（消息名）與signal（消息名）的方式，描述了進程同步的一種實現(xiàn)方法。只與制約進程及被制約進程有關(guān)而不是與整組并發(fā)進程有關(guān)，稱該信號量為私用信號量。 公用信號量：一個進程Pi的私用信號量Semi是從制約進程發(fā)送來的進程Pi的執(zhí)行條件所需要的消息。與私用信號量相對應，稱互斥時使用的信號量為公用信號量。用，原語操作實現(xiàn)同步 利用，原語實現(xiàn)進程同步的方法與利用wait和signal過程時相同，也是分為三步。首先為各并發(fā)進程設置私用信號量，然后為私用信號量賦初值，

22、最后利用，原語和私用信號量規(guī)定各進程的執(zhí)行順序。緩沖區(qū)隊列緩沖區(qū)隊列例：設進程PA和PB通過緩沖區(qū)隊列傳遞數(shù)據(jù)（如上圖）。PA為發(fā)送進程，PB為接收進程。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往緩沖隊列發(fā)送數(shù)據(jù)時，至少有一個緩沖區(qū)是空的，即緩沖區(qū)滿時PA不能送數(shù)；（3）由PA發(fā)送的數(shù)據(jù)塊在緩沖隊列中按先進先出（FIFO）方式排列。描述發(fā)送過程deposit(

23、data)和接收過程remove(data)。解：由題意可知，進程PA調(diào)用的過程deposit(data)和進程PB調(diào)用的過程remove(data)必須同步執(zhí)行，因為過程 deposit(data)的執(zhí)行結(jié)果是過程remove(data)的執(zhí)行條件，而當緩沖隊列全部裝滿數(shù)據(jù)時，remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件，滿足同步定義。從而，按以下三步描述過程deposit(data)和remove(data)：（1）設Bufempty為進程PA的私用信號量，Buffull 為進程PB的私用信號量；（2）令Bufempty的初始值為n（n 為緩沖隊列的緩沖區(qū)個數(shù)

24、），Buffull 的初始值為0；（3）描述：PA: deposit(data):begin local xP(Bufempty)；按FIFO方式選擇一個空緩沖區(qū)Buf(x)；Buf(x) dataBuf(x)置滿標記（Buffull）endPB: remove(data):Begin local x （Buffull）；按FIFO方式選擇一個裝滿數(shù)據(jù)的緩沖區(qū)Buf(x)data Buf(x)Buf(x)置空標記 （Bufempty）end思考與練習 設課程的前驅(qū)、后繼關(guān)系如下，若每修一門課程看作進程Px（x1.6）試用P、V操作算法描述這種前驅(qū)與后繼關(guān)系。 計算機導論高級語言程序設計 計算機

25、組成原理 數(shù)據(jù)結(jié)構(gòu) 86匯編語言 計算機操作系統(tǒng)生產(chǎn)者-消費者問題 把并發(fā)進程的同步和互斥問題一般化，可以得到一個抽象的一般模型，即生產(chǎn)者-消費者問題。計算機系統(tǒng)中，每個進程都申請使用和釋放各種不同類型的資源，這些資源既可以是像外設、內(nèi)存及緩沖區(qū)等硬件資源，也包括臨界區(qū)、數(shù)據(jù)、例程等軟件資源。把系統(tǒng)中使用某一類資源的進程稱為該資源的消費者，而把釋放同類資源的進程稱為該資源的生產(chǎn)者。例如在上面的計算進程PC與打印進程PP公用一個緩沖區(qū)的例子中，計算進程PC把數(shù)據(jù)送入緩沖區(qū)，打印進程PP從緩沖區(qū)中取數(shù)據(jù)打印輸出，因此，PC進程相當于數(shù)據(jù)資源的生產(chǎn)者，而PP進程相當于消費者。用信號量解決生產(chǎn)者/消費

26、者問題說明 假如是一個生產(chǎn)者、一個消費者，且緩沖區(qū)只有一個單元。Begin Process producer Process consumer Buffer:integer; Begin Begin Se,Sf:semaphore; Repeat Repeat Se:=1;Sf:=0; Produce a product; P(Sf); cobegin P(Se); Take a product; producer; Buffer:=product; V(Se); consumer; V(Sf); Consumer; coend Forever Forever End. End; End;驗證

27、：1、緩沖區(qū)滿生產(chǎn)者不能送數(shù)；緩沖區(qū)空消費者不能取數(shù) 2、在這個問題中同步隱含著互斥。用信號量解決生產(chǎn)者/消費者問題說明 假如是一個生產(chǎn)者、一個消費者，且緩沖區(qū)有 N 個單元。 當緩沖區(qū)沒有放滿 N 個數(shù)據(jù)時，生產(chǎn)者進程調(diào)用 P（Se）都不會成為等待狀態(tài)，可以把數(shù)據(jù)送入緩沖區(qū)。但當緩沖區(qū)中已有 N 個數(shù)據(jù)時，生產(chǎn)者進程想要再送數(shù)將被拒絕。由于每送入一個數(shù)后要調(diào)用 V（Sf），所以此時 Sf 的值表示緩沖區(qū)中可取的數(shù)據(jù)數(shù)，只要 Sf 0，消費者進程在調(diào)用 P（Sf）后總可以從緩沖區(qū)取數(shù)。每取走一個數(shù)據(jù)就調(diào)用 V（Se），因此增加了一個存放數(shù)據(jù)的位置?？梢杂弥羔?in 和 out 分別指示生產(chǎn)者進

28、程向緩沖區(qū)送數(shù)和消費者進程從緩沖區(qū)取數(shù)的相對位置；指針的初始值為“0”。 這種情況下生產(chǎn)者與消費者進程的同步算法為： 用信號量解決生產(chǎn)者/消費者問題說明Begin Process producer Process consumer B:array0.n-1 of integer; Begin Begin in,out:integer; Repeat Repeat Se,Sf:semaphore; Produce a product; P(Sf); in:=out:=0; P(Se); Take a product from Bout; Se:=n;Sf:=0; Bin:=product; ou

29、t:=(out+1) mod n; cobegin in:=(in+1) mod n; V(Se); producer; V(Sf); Consumer; consumer; Forever Forever coend End; End;End. 說明：這時緩沖區(qū)可以看成是頭尾相連一個環(huán)形，in、out 指針指出存取數(shù)的位置。驗證：1、緩沖區(qū)滿生產(chǎn)者不能送數(shù)；緩沖區(qū)空消費者不能取數(shù) 2、在這個問題中生產(chǎn)者與消費者進程有可能同時進入緩沖區(qū)，但不會出錯。把一個長度為的有界緩沖區(qū)（n0)與一群生產(chǎn)者進程1，2，m和一群消費者進程1，2，k聯(lián)系起來（如圖3.14所示）。設生產(chǎn)者進程和消費者進程是互相等

30、效的，其中，各生產(chǎn)者進程使用的過程deposit(data)和各消費者使用的過程remove(data)可描述如下：首先，可以看到，上述生產(chǎn)者-消費者問題是一個同步問題。即生產(chǎn)者和消費者之間滿足如下條件：(1) 消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的；(2) 生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進程和各消費者進程之間必須互斥執(zhí)行。圖3.14 生產(chǎn)者-消費者問題由以上分析，設公用信號量mutex保證生產(chǎn)者進程和消費者進程之間的互斥，設信號量avail為生產(chǎn)者進程的私用信號量，信號量full為消費者進程的私用信號量。信號

31、量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號量mutex表示可用有界緩沖區(qū)的個數(shù)，初值為 1。從而有：deposit(data):begin（avail）（mutex）送數(shù)據(jù)入緩沖區(qū)某單元（full）（mutex）endremove(data):begin（full）（mutex）取緩沖區(qū)中某單元數(shù)據(jù)（avail）（mutex）end在上例中，由于一個過程中包含有幾個公用、私用信號量，因此，、原語的操作次序要非常小心。一般說來，由于原語是釋放資源的，所以可以以任意次序出現(xiàn)。但原語則不然，如果次序混亂，將會造成進程之間的死鎖。關(guān)于死鎖

32、，將在3.8 中介紹。用信號量解決生產(chǎn)者/消費者問題說明 假設是M個生產(chǎn)者、R個消費者，且緩沖區(qū)有 N 個單元。 現(xiàn)在不僅生產(chǎn)者與消費者之間要同步，而且 M 個生產(chǎn)者之間、R 個消費者之間還必須互斥地訪問緩沖區(qū)。 要同步的原因和前面的問題一樣；之所以要互斥是因為如果 M 個生產(chǎn)者進程各自個向緩沖區(qū)送數(shù)，當?shù)谝粋€生產(chǎn)者按指針 in 指示的位置送一個數(shù)，但在改變指針前可能被打斷執(zhí)行，于是當?shù)诙€生產(chǎn)者送數(shù)時仍按原指針所指出的位置存放，這樣兩個數(shù)被放在同一個單元，造成數(shù)據(jù)丟失。同樣，R 個消費者都要取數(shù)時可能都從指針 out 指出的位置取數(shù)，造成一個數(shù)據(jù)被重復取出。用信號量解決生產(chǎn)者/消費者問題說明

33、如果該問題描述在任一時刻只能有一方(生產(chǎn)者或消費者)訪問緩沖區(qū)。 即一次只能有一個進程可以進入緩沖區(qū)。這是第一種方法（書上前例）。可是、當有一個生產(chǎn)者（或消費者）在送數(shù)（或取數(shù)）時，可以允許一個消費者（或生產(chǎn)者）同時訪問緩沖區(qū)去取數(shù)（或送數(shù)）。因此這是第二種方法。顯然、第二種方法的并行性要比第一種方法的并行性高。用信號量解決生產(chǎn)者/消費者問題說明第一種方法Begin Process producer i Process consumer j B:array0.n-1 of integer; Begin Begin in,out:integer; Repeat Repeat S,Se,Sf:se

34、maphore; Produce a product; P(Sf); in:=out:=0; P(Se) P(S); S:=1;Se:=n;Sf:=0 P(S); Take a product from Bout; cobegin Bin:=product; out:=(out+1) mod n; producer; in:=(in+1) mod n; V(Se); consumer; V(Sf) ; V(S); coend V(S); Consumer;End. Forever Forever End; End; 思考：1、如果生產(chǎn)者或消費者進程中的兩個 P 操作次序?qū)φ{(diào) 可以嗎？ 2、第二

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

36、（） 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）； 并發(fā)控制是否完全解決問題？死鎖死鎖 死鎖：指各并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。死鎖的起因死鎖的起因是并發(fā)進程的資源競爭。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的

37、資源個數(shù)少于并發(fā)進程所要求的該類資源數(shù)。顯然，由于資源的有限性，不可能為所有要求資源的進程無限制地提供資源。但是，可以采用適當?shù)馁Y源分配算法，以達到消除死鎖的目的。為此，先看看產(chǎn)生死鎖的必要條件。產(chǎn)生死鎖的必要條件(1) 互斥條件。并發(fā)進程所要求和占有的資源是不能同時被兩個以上進程使用或操作的，進程對它所需要的資源進行排他性控制。(2) 不剝奪條件。進程所獲得的資源在未使用完畢之前，不能被其他進程強行剝奪，而只能由獲得該資源的進程自己釋放。(3) 部分分配。進程每次申請它所需要的一部分資源，在等待新資源的同時繼續(xù)占用已分配到的資源。(4) 環(huán)路條件。存在一種進程循環(huán)鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。顯然，只要使上述4個必要條件中的某一個不滿足，則死鎖就可以排除。死鎖的排除方法 預防是采用某種策略，限制并發(fā)進程對資源的請求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時間都不滿足。 避免是指系統(tǒng)在分配資源時，根據(jù)資源的使用情況提前做出預測，從而避免死鎖的發(fā)生。