第6章處理機調(diào)度課件

(一)處理機的多級調(diào)度

(二)作業(yè)調(diào)度

(三)進程調(diào)度

第六章處理機調(diào)度1

(一)處理機的多級調(diào)度一.處理機調(diào)度的功能

確定數(shù)據(jù)結(jié)構(gòu)

制訂調(diào)度策略(調(diào)度原則)

給出調(diào)度算法

具體的實施處理機分派不同類型的操作系統(tǒng)往往采用不同的處理機分配方法。

2

二.批處理系統(tǒng)中的處理機調(diào)度處理機調(diào)度分為兩級：作業(yè)調(diào)度和進程調(diào)度。

1.作業(yè)調(diào)度作業(yè)調(diào)度又稱為宏觀調(diào)度。任務(wù)——對存放在輔存設(shè)備上的大量作業(yè)，以一定的策略進行挑選，分配主存等必要的資源，建立作業(yè)對應(yīng)的進程，使其投入運行。

2.進程調(diào)度進程調(diào)度又稱為微觀調(diào)度。任務(wù)——對進入主存的所有進程，確定哪個進程在什么時候獲得處理機，使用多長時間。

3

三.多任務(wù)操作系統(tǒng)中的處理機調(diào)度在分時系統(tǒng)或支持多任務(wù)并發(fā)執(zhí)行個人計算機操作系統(tǒng)中，系統(tǒng)將用戶提交的任務(wù)處理為進程，一個進程又可以創(chuàng)建多個子進程，形成可以并發(fā)執(zhí)行的多進程。進程調(diào)度的任務(wù)是：當(dāng)處理機空閑時，以某種策略選擇一個就緒進程去運行，并分配處理機的時間。

4

四.多線程操作系統(tǒng)中的處理機調(diào)度在支持多線程運行的系統(tǒng)中，一個進程可以創(chuàng)建一個線程，也可以創(chuàng)建多個線程。系統(tǒng)為進程分配它所需要的資源，而處理機的分配單位則為線程。系統(tǒng)提供線程調(diào)度程序，其功能是當(dāng)處理機空閑時，以某種策略選擇一個就緒線程去運行，并分配處理機時間。

5

(二)作業(yè)調(diào)度一.作業(yè)的狀態(tài)作業(yè)在整個活動期間一共有四種狀態(tài)，提交狀態(tài)：用戶將自己的程序和數(shù)據(jù)提交給系統(tǒng)，等待輸入。后備狀態(tài)：作業(yè)已存放在磁盤上，等待調(diào)度。執(zhí)行狀態(tài)：作業(yè)進入主存開始運行。完成狀態(tài)：作業(yè)計算完成開始，退出系統(tǒng)。

6運行就緒完成等待后備提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入執(zhí)行運行就緒完成等待后備提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入執(zhí)行運行就緒完成等待后備提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入執(zhí)行7

二.作業(yè)調(diào)度的功能

1.確定數(shù)據(jù)結(jié)構(gòu)建立作業(yè)控制塊jcb(jobcontrolblock)。作業(yè)控制塊記錄了每個作業(yè)類型、狀態(tài)、資源請求及分配情況。

2.確定調(diào)度策略與調(diào)度算法

3.分配資源為選中的作業(yè)分配所需要的系統(tǒng)資源。

4.善后處理收回該作業(yè)所占用的全部資源，撤消作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進程。

8

三.作業(yè)控制塊作業(yè)控制塊jcb存在于系統(tǒng)的整個過程中，jcb是一個作業(yè)存在的標志。jcb的主要內(nèi)容如下：

作業(yè)名

資源要求（用戶提供） 資源使用情況 估計執(zhí)行時間 進入系統(tǒng)時間 最遲完成時間 開始執(zhí)行時間 要求的主存量 已執(zhí)行時間 要求外設(shè)的類型及臺數(shù) 主存地址 要求文件量和輸出量 外設(shè)臺號

類型 優(yōu)先級 控制方式（聯(lián)機/脫機） 狀態(tài)（后備/執(zhí)行/完成） 作業(yè)類型（CPU偏多，I/O偏多，均衡）

9

四.作業(yè)調(diào)度算法性能的衡量采用平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間來衡量作業(yè)調(diào)度算法性能的好壞。

1.周轉(zhuǎn)時間一個作業(yè)提交給計算機系統(tǒng)到該作業(yè)的結(jié)果返回給用戶所需要的時間。

(1)定義ti=tci-tsi

ti—作業(yè)i的周轉(zhuǎn)時間

tsi—作業(yè)i的提交時間

tci—作業(yè)i的完成時間

(2)意義說明作業(yè)i在系統(tǒng)中停留時間的長短。

(3)平均周轉(zhuǎn)時間t=

n為進入系統(tǒng)的作業(yè)個數(shù)10

2.帶權(quán)周轉(zhuǎn)時間

(1)定義一個作業(yè)的周轉(zhuǎn)時間與其運行時間的比值。

wi=

(2)意義說明作業(yè)i在系統(tǒng)中相對等待時間。

(3)平均帶權(quán)周轉(zhuǎn)時間

t=

tri為作業(yè)的實際執(zhí)行時間11

五.作業(yè)調(diào)度算法

1.先來先服務(wù)調(diào)度算法(FCFS)(1)策略：按作業(yè)來到的先后次序進行調(diào)度。

(2)特點：簡單，易實現(xiàn)。

(3)討論在先來先服調(diào)度算法下的周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間

作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

8.0010.002.001

10.0010.502.004

10.5010.601.6016

10.6010.801.306.5

平均周轉(zhuǎn)時間t=

平均帶權(quán)周轉(zhuǎn)時間w=1.7256.87512

五.作業(yè)調(diào)度算法

2.短作業(yè)優(yōu)先調(diào)度算法

(1)策略：按作業(yè)按作業(yè)請求運行的時間長短進行調(diào)度。

(2)特點：易實現(xiàn)，系統(tǒng)吞吐量高；只照顧短作業(yè)，而沒有考慮長作業(yè)的利益易實現(xiàn)。

(3)討論短作業(yè)優(yōu)先調(diào)度算法下的周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

平均周轉(zhuǎn)時間t=

平均帶權(quán)周轉(zhuǎn)時間w=1.555.15

8.0010.002.001

10.3010.802.304.6

10.0010.101.1011

10.1010.300.80413先來先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法（比較）143.響應(yīng)比高者優(yōu)先調(diào)度算法：先來先服務(wù)和短作業(yè)優(yōu)先算法都有其片面性，先來先服務(wù)調(diào)度算法只考慮作業(yè)的等待時間，而忽視了作業(yè)的運行時間，短作業(yè)優(yōu)先算法則相反，只考慮了作業(yè)的運行時間，而忽視了作業(yè)的等待時間。響應(yīng)比高者優(yōu)先調(diào)度算法是介于這兩種算法之間的一種折中的算法。15作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

8.0010.002.001

10.0010.101.1011

作業(yè)1執(zhí)行之后，計算其余作業(yè)的響應(yīng)比響應(yīng)比2=1+（10.00–8.50）/0.5=1+3=4響應(yīng)比3=1+（10.00–9.00）/0.1=1+10 =11響應(yīng)比4=1+（10.00–9.50）/0.2=1+2.5=3.5因為作業(yè)3的響應(yīng)比最高，所以選擇作業(yè)3執(zhí)行作業(yè)3執(zhí)行之后，計算其余作業(yè)的響應(yīng)比響應(yīng)比2=1+（10.10–8.50）/0.5=1+3.2=4.2響應(yīng)比4=1+（10.10–9.50）/0.2=1+3=4因為作業(yè)2的響應(yīng)比較高，所以選擇作業(yè)2執(zhí)行

10.1010.602.10 4.2

10.6010.801.306.5

平均周轉(zhuǎn)時間t=1.625平均帶權(quán)周轉(zhuǎn)時間w=5.67516

響應(yīng)比高者優(yōu)先調(diào)度算法的特點響應(yīng)比高者優(yōu)先調(diào)度算法其調(diào)度性能不如短作業(yè)優(yōu)先算法好，但它及照顧到用戶到來先后，又考慮到系統(tǒng)服務(wù)時間長短，從理論上講是比較完備的調(diào)度算法。但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶的估計的運行時間，并要作浮點運算（這是系統(tǒng)程序最忌諱的）浪費大量的計算時間，這是系統(tǒng)程序所不允許的。174.優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法是綜合考慮各方面的因素（作業(yè)等待時間、運行時間、緩急程度，系統(tǒng)資源使用等），給每個作業(yè)設(shè)置一個優(yōu)先數(shù)，調(diào)度程序總是選擇一個優(yōu)先數(shù)最大（或者最?。┑淖鳂I(yè)調(diào)入（系統(tǒng)）內(nèi)存。這種算法實現(xiàn)的困難在于如何綜合考慮，這些因素之間的關(guān)系怎樣處理。算法思想： 計算優(yōu)先數(shù)，確定優(yōu)先級，根據(jù)優(yōu)先級大小挑選作業(yè)。 例如，優(yōu)先數(shù)=等待時間2–要求執(zhí)行時間–16*輸出量特點： 迅速地執(zhí)行一個短作業(yè)，但偶爾也要執(zhí)行一個在磁盤中等待了很久的作業(yè)。此時“等待時間”的值遠遠超過其他2項目的和185.均衡調(diào)度算法均衡調(diào)度算法就是一種更為理想化的調(diào)度算法，如何實現(xiàn)就更困難，并且算法本身的開銷有時會遠大于先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法。 先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法是2種開銷較小的算法，這也是這兩種算法被眾多系統(tǒng)采用的最根本的原因。19

(三)進程調(diào)度一.調(diào)度/分派結(jié)構(gòu)

1.調(diào)度 在眾多處于就緒狀態(tài)的進程中，按一定的原則選擇一個進程。 組織和維護就緒進程隊列。包括確定調(diào)度算法、按調(diào)度算法組織和維護就緒進程隊列。

2.分派 當(dāng)處理機空閑時，是移出就緒隊列中第一個進程，并賦予它使用處理機的權(quán)利。

調(diào)度與進程控制和進程通信的功能有密切的聯(lián)系，當(dāng)一個進程阻塞時，這種進程將進入相應(yīng)的等待隊列中，并讓出CPU，調(diào)用進程分派程序選擇一個就緒進程占用CPU；當(dāng)一進程被喚醒時，這種進程將插入到就緒進程隊列中。在一般的操作系統(tǒng)教材中把上述功能稱為進程調(diào)度。

20

3.調(diào)度∕分派結(jié)構(gòu)圖

ready_q

scheduler

suspwakeupreceive……pcb6……pcb4pcb3pcb2pcb1

dispatcher

CPU21

二.進程調(diào)度的功能1.記錄和保持系統(tǒng)中所有進程的有關(guān)情況和狀態(tài)特征 有關(guān)進程調(diào)度的信息是記錄在PCB中的，在進程調(diào)度中用到的主要是進程的狀態(tài)、調(diào)度優(yōu)先級（優(yōu)先數(shù)）、就緒進程隊列等。2.決定分配（處理機）策略 確定進程調(diào)度的策略，例如，先來先服務(wù)、優(yōu)先數(shù)調(diào)度策略，調(diào)度策略的不同，組織就緒進程隊列的方式也不同。

優(yōu)先調(diào)度原則——

進程就緒隊列按進程優(yōu)先級高低排序

先來先服務(wù)原則——

進程就緒隊列按進程來到的先后次序排序22

3.實施處理機的分配 調(diào)度時機（UNIX系統(tǒng)中）： （1）進程完成； （2）進程阻塞； （3）進程出錯掛起； （4）分時系統(tǒng)中時間片到； （5）高優(yōu)先級進程就緒（搶占式系統(tǒng)）；4.進程調(diào)度的準則 （1）CPU使用率；40%~90%

（2）吞吐率；單位時間內(nèi)所完成的進程數(shù) （3）周轉(zhuǎn)時間； （4）響應(yīng)時間；交互式系統(tǒng) （5）等待時間；23

三.進程調(diào)度方式

1.什么是調(diào)度方式當(dāng)一進程正在處理機上執(zhí)行時，若有某個更為“重要而緊迫”的進程需要進行運行，系統(tǒng)如何分配處理機。

2.非剝奪方式一種是讓正在執(zhí)行的進程繼續(xù)執(zhí)行，直到該進程完成或發(fā)生某事件而進入“完成”或“阻塞”狀態(tài)時，才把處理機分配給“重要而緊迫”的進程。

3.剝奪方式當(dāng)“重要而緊迫”的進程一到，便暫停正在執(zhí)行的進程，立即把處理機分配給優(yōu)先級更高的進程。

24

四.進程調(diào)度算法（與作業(yè)調(diào)度算法有何關(guān)系？）

1.進程優(yōu)先數(shù)調(diào)度算法

(1)什么是進程優(yōu)先數(shù)調(diào)度算法 預(yù)先確定各進程的優(yōu)先數(shù)，系統(tǒng)把處理機的使用權(quán)賦予就緒隊列中具備最高優(yōu)先權(quán)(優(yōu)先數(shù)和一定的優(yōu)先級相對應(yīng))的就緒進程。

優(yōu)先數(shù)調(diào)度算法是目前操作系統(tǒng)廣泛采用的一種進程調(diào)度算法，這種算法按照某種原則由系統(tǒng)（或用戶、或系統(tǒng)與用戶結(jié)合）賦予每個進程一個優(yōu)先數(shù)，在處理機空閑時，進程調(diào)度程序就從就緒進程中選擇一個優(yōu)先數(shù)最大（或者最小）的進程占用CPU（該進程就從就緒狀態(tài)轉(zhuǎn)換成運行狀態(tài)）。25

(2)優(yōu)先數(shù)的分類及確定靜態(tài)優(yōu)先數(shù)——*在進程被創(chuàng)建時確定，且一經(jīng)確定后在整個進程運行期間不再改變。*靜態(tài)優(yōu)先數(shù)的確定 系統(tǒng)確定：運行時間、使用資源，進程的類型 用戶確定：緊迫程度，計費標準 系統(tǒng)與用戶結(jié)合：用戶可以為本用戶的進程設(shè)置優(yōu)先數(shù)，但不是作調(diào)度用，系統(tǒng)還要根據(jù)系統(tǒng)情況把用戶設(shè)置的進程優(yōu)先數(shù)作為確定進程優(yōu)先數(shù)的一個參數(shù)26

動態(tài)優(yōu)先數(shù)——*進程優(yōu)先數(shù)在進程運行期間可以改變。*動態(tài)優(yōu)先數(shù)的確定——

進程使用CPU超過一定數(shù)值時，降低優(yōu)先數(shù)； 進程進行I/O操作后，增加優(yōu)先數(shù) 進程等待時間超過一定數(shù)值時，提高優(yōu)先數(shù)27

2.循環(huán)輪轉(zhuǎn)調(diào)度算法

(1)什么是循環(huán)輪轉(zhuǎn)調(diào)度算法當(dāng)CPU空閑時，選取就緒隊列首元素，賦予一個時間片，當(dāng)時間片用完時，該進程轉(zhuǎn)為就緒態(tài)并進入就緒隊列末端。

該隊列排序的原則是什么？pcb1pcb2pcbnCPU完成28

(2)簡單循環(huán)輪轉(zhuǎn)調(diào)度就緒隊列中的所有進程以等速度向前進展

q=t/nt為響應(yīng)時間，n為進入系統(tǒng)的進程數(shù)目。

q值如何確定?(3)循環(huán)輪轉(zhuǎn)調(diào)度算法的發(fā)展可變時間片輪轉(zhuǎn)調(diào)度、多重時間片循環(huán)調(diào)度29

系統(tǒng)按進程轉(zhuǎn)換成就緒狀態(tài)的時間的降序排隊，調(diào)度程序每次調(diào)度，總是從隊首移出一程的PCB，然后，將此進程投入運行（由就緒狀態(tài)轉(zhuǎn)換成運行狀態(tài)）。一個運行時間片到的進程從運行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)后，排在就緒隊列的隊尾。評價：優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小缺點是不靈活，當(dāng)系統(tǒng)中進程較少時，系統(tǒng)開銷變大

為什么？由于該算法簡單易于實現(xiàn)，且系統(tǒng)開銷較小，早期的分時操作系統(tǒng)和目前一些應(yīng)用系統(tǒng)中廣泛采用了這種調(diào)度算法。

30

(3)循環(huán)輪轉(zhuǎn)調(diào)度算法的發(fā)展可變時間片輪轉(zhuǎn)調(diào)度——將固定時間片改為可變時間片

為了克服前種調(diào)度算法的缺點，人們設(shè)計出一種可變時間片的調(diào)度算法，其思想是：時間片的大小是可變的，系統(tǒng)可根據(jù)系統(tǒng)中當(dāng)前的進程數(shù)來確定時間片的大小。 這種算法從理論上克服了系統(tǒng)中進程數(shù)很少時系統(tǒng)開銷大的缺點，但修改時間片的大小，統(tǒng)計系統(tǒng)進程的數(shù)量也需要消耗系統(tǒng)時間，還有一個調(diào)整時間片大小的周期，太大，等于是固定時間片，太小，系統(tǒng)開銷很大，得不嘗失。例如，響應(yīng)時間t=3s，當(dāng)n=30，q=0.1s；當(dāng)n=6，q=0.5s多重時間片循環(huán)調(diào)度 將單一就緒隊列改為多就緒隊列（見下頁）31

五.調(diào)度用的進程調(diào)度變遷圖（多重時間片循環(huán)調(diào)度）運行500ms100ms因I∕O而等待高優(yōu)先就緒低優(yōu)先就緒進程調(diào)度進程調(diào)度時間片到請求I/OI/O完成32

1.隊列結(jié)構(gòu)

I/O等待隊列——

一個進程如果請求I/O，進入I/O等待隊列

低優(yōu)先就緒隊列——

一個進程如果在運行中超過了它的時間量，進入低優(yōu)先就緒隊列

高優(yōu)先就緒隊列——

當(dāng)進程從等待狀態(tài)變?yōu)榫途w狀態(tài)時，進入高優(yōu)先就緒隊列

2.進程調(diào)度算法優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略33

(1)當(dāng)CPU空閑時，若高優(yōu)先就緒隊列非空，則從高優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為100ms。

(2)當(dāng)CPU空閑時，若高優(yōu)先就緒隊列為空，則從低優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為500ms。

3.調(diào)度效果優(yōu)先照顧了I∕O量大的進程；適當(dāng)照顧了計算量大的進程。34

【問】某計算機系統(tǒng)中，進程調(diào)度采用時間片輪轉(zhuǎn)調(diào)度算法。每個進程得到的時間片可隨進程的執(zhí)行情況而變化，在過去的時間里，若進程經(jīng)常啟動外設(shè)則給它分配較短的時間片；若啟動外設(shè)次數(shù)很少則分配一個較長的時間片。為什么？【答】這種分配方法能夠提高處理器（CPU）的利用率。

因為啟動外設(shè)的速度是很慢的，在某個進程使用外設(shè)的過程中是處于一種阻塞的狀態(tài)，CPU只能閑置，極大地降低了CPU利用率，CPU完全可以利用該進程讀寫外設(shè)的時間運行其他的進程。比如一個進程A每使用CPU時間為1ms就要進行外設(shè)操作，假設(shè)外設(shè)操作時間為30ms，那么如果給他分配的時間片為1ms，好，那么CPU沒有被耽誤；如果分配5ms，那么CPU閑置4ms；如果分配30ms，那29ms中CPU都沒事干。

35

【問】在系統(tǒng)中設(shè)置兩個就緒隊列，一個是時間片較短的進程就緒隊列，另一個是時間片較長的進程就緒隊列。那么，在進程調(diào)度時應(yīng)優(yōu)先從哪個隊列中選取一個就緒進程占有CPU？為什么？【答】這是進程調(diào)度中的短任務(wù)優(yōu)先原則。如果兩個進程A和B，A要1ms就能做完，B要30ms才能做完，那么如果A不幸排在B后面，那么A要等30ms才能運行，那么程序響應(yīng)時間和交互體驗很差。如果先A后B，那么A的響應(yīng)時間為1ms，B為31ms；如果先B后A，那么A的響應(yīng)時間為31ms，B為30ms。

36

第六章小結(jié)一.處理機的兩級調(diào)度二.作業(yè)調(diào)度

1.作業(yè)的四種狀態(tài)

2.作業(yè)控制塊

3.周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間：定義物理意義

4.常用的作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先對一批作業(yè)，若采用兩中不同的調(diào)度算法，能分析、計算調(diào)度性能的好壞。37

三.進程調(diào)度

1.調(diào)度方式非剝奪方式剝奪方式

2.常用的進程調(diào)度算法優(yōu)先數(shù)調(diào)度循環(huán)輪轉(zhuǎn)調(diào)度

3.調(diào)度用的進程狀態(tài)變遷圖通過調(diào)度用的進程狀態(tài)變遷圖，能分析系統(tǒng)采用的調(diào)度策略，調(diào)度性能的好壞。能分析因果變遷及條件。38（2013真題）45.(7分)某博物館最多可容納500人同時參觀，有一個出入口，該出入口一次僅允許一個人通過。參觀者的活動描述如下：cobegin參觀者進程i：{ …

進門；

…

參觀；

…

出門；

…}coend請?zhí)砑颖匾男盘柫亢蚉、V(或wait()、signal())操作，以實現(xiàn)上述操作過程中的互斥與同步。

要求寫出完整的過程，說明信號量含義并賦初值。

39解答：main(){

intempty=500；

//semaphoreempty=500;//可容納人數(shù)的上限

int

mutex=1；

//用于出入口資源的控制

cobegin

visitori();

coend}visitori(){ ……

P(empty);

P(mutex);

進門

V(mutex);

參觀

P(mutex);

出門；

V(mutex);

V(empty); ……}40（2014真題）【47】系統(tǒng)中有多個生產(chǎn)者進程和消費者進程，共享用一個可以存1000個產(chǎn)品的緩沖區(qū)（初始為空），當(dāng)緩沖區(qū)為未滿時，生產(chǎn)者進程可以放入一件其生產(chǎn)的產(chǎn)品，否則等待；當(dāng)緩沖區(qū)為未空時，消費者進程可以取走一件產(chǎn)品，否則等待。要求一個消費者進程從緩沖區(qū)連續(xù)取出10件產(chǎn)品后，其他消費者進程才可以取產(chǎn)品，請用信號量P，V（wait，signed）操作實現(xiàn)進程間的互斥和同步，要求寫出完整的過程；并指出所用信號量的含義和初值。41解答：main(){

intempty=1000，full;

int

mutex=1,s0j=0;

cobegin Pi();C0();Cj();

coend

}Pi(){ while(1){

生產(chǎn)一產(chǎn)品；

P(empty);

P(mutex);

產(chǎn)品放入緩沖區(qū)；

V(mutex);

V(full);}}42C0(){

for(intt=1;t<=10;t++){

P(full);

P(mutex);

取出一個產(chǎn)品；

V(mutex);

V(full);

消費一個產(chǎn)品;}V(s0j);}Cj(){ while(1){ P(s0j); V(s0j);

P(full);

P(mutex);

取出一個產(chǎn)品

V(mutex);

V(empty);

消費一個產(chǎn)品

}}43(2011真題)【45】(8分)某銀行提供1個服務(wù)窗口和10個供顧客等待的座位。顧客到達銀行時，若有空座位，則到取號機上領(lǐng)取一個號，等待叫號。取號機每次僅允許一位顧客使用。當(dāng)營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動過程描述如下：cobegin{

process顧客i

{ 從取號機取號； 等待叫號; 獲得服務(wù);

}

process營業(yè)員

{

while(TRUE)

{ 叫號; 為顧客服務(wù);

}

}}coend

請?zhí)砑颖匾男盘柫亢蚉、V(或wait()、signal())操作，實現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。44解答：main(){

int

seets=10;//表示空余座位

int

mutex=1;//管理取號機的互斥信號量

intcustom=0;//顧客數(shù)量信號量

cobegin process顧客i(); process營業(yè)員();

coend

}45process營業(yè)員(){ while(1){

P(custom); //看是否有顧客 叫號； 為顧客服務(wù)；

}}process顧客i();{

P(seets);//找個空位

P(mutex);//取號機空否

從取號機上取號；

V(mutex);//放開取號機

V(custom);//通知營業(yè)員等待叫號；

V(seets);//離開座位接受服務(wù)；}46(2009真題)45.（7分）三個進程P1、P2、P3互斥使用一個包含N（N>0）個單元的緩沖區(qū)。P1每次用produce（）生成一個正整數(shù)并用put（）送入緩沖區(qū)某一空單元中；P2每次用getodd（）從該緩沖區(qū)中取出一個奇數(shù)并用countodd（）統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個偶數(shù)并用counteven（）統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。

47解答：定義信號量S12控制P1與P2之間的同步； 信號量S13控制P1與P3之間的同步； 信號量empty控制生產(chǎn)者與消費者之間的同步； 信號量mutex控制進程間互斥使用緩沖區(qū)。

main(){ int

s12=0,s13=0,emp