第四章作業(yè)參考答案

2 答：多道程序在單CPU上并發(fā)運(yùn)行和多道程序在多CPU上并行在本質(zhì)上是不同的,在單CPU上，操作系統(tǒng)利用時(shí)間片輪轉(zhuǎn)算法在一段時(shí)間內(nèi)依次調(diào)度執(zhí)行多個(gè)程序，宏觀上多道程序并發(fā)運(yùn)行、微觀上仍是串行執(zhí)行；在多CPU上，同一時(shí)刻可有多個(gè)程序分別在多個(gè)CPU上并行執(zhí)行，而某個(gè)程序也可能同時(shí)在多個(gè)CPU上并行執(zhí)行。前者實(shí)現(xiàn)時(shí)應(yīng)考慮的因素： 在多道程序環(huán)境下如何向用戶提供服務(wù)； 在并發(fā)程序之間如可正確傳遞消息（通信）； 如何對(duì)CPU進(jìn)行調(diào)度，保證每個(gè)用戶相對(duì)公平地得到CPU；（CPU是一個(gè)只可調(diào)度，不可分配的資源）后者實(shí)現(xiàn)時(shí)應(yīng)考慮的因素： 在執(zhí)行多道程序時(shí)應(yīng)如何分配程序給CPU 多CPU之間的通信問題 在多CPU上并行執(zhí)行一個(gè)程序時(shí)如何調(diào)度和分配CPU9說明下列活動(dòng)時(shí)屬于哪種至于關(guān)系？（1）若干同學(xué)去圖書館借書；（2）兩隊(duì)進(jìn)行籃球比賽；（3）流水線生產(chǎn)中的各道工序；（4）商品生產(chǎn)和社會(huì)消費(fèi)；答：（1）互斥關(guān)系（2）互斥關(guān)系（3）同步關(guān)系（4）同步關(guān)系11設(shè)有一臺(tái)計(jì)算機(jī)，有兩條I/O通道，分別接一臺(tái)卡片輸入機(jī)和一臺(tái)打印機(jī)?？ㄆ瑱C(jī)把一疊卡片逐一輸入到緩沖區(qū)B1中，加工處理后再搬到緩沖區(qū)B2中，并在打印機(jī)上印出。問：（1）系統(tǒng)要設(shè)幾個(gè)進(jìn)程來完成這個(gè)任務(wù)？各自的工作是什么？（2）這些進(jìn)程間有什么樣的相互制約關(guān)系？（3）用PV操作寫出這些進(jìn)程的同步算法。（4）設(shè)系統(tǒng)中只有上述幾個(gè)過程，用圖表示出各自狀態(tài)變遷情況及原因。答：（1）系統(tǒng)要設(shè)3個(gè)進(jìn)程來完成這個(gè)任務(wù)； 第一個(gè)進(jìn)程：從卡片機(jī)把一疊卡片逐一輸入到緩沖區(qū)B1中； 第二個(gè)進(jìn)程：加工處理后再搬到緩沖區(qū)B2中； 第三個(gè)進(jìn)程：從緩沖區(qū)B2讀出，打印機(jī)印出。（2）第一個(gè)進(jìn)程從卡片機(jī)把一疊卡片逐一輸入到緩沖區(qū)B1中，第二個(gè)進(jìn)程加工處理B1中的數(shù)據(jù)。如果B1為空，則第二個(gè)進(jìn)程無法進(jìn)行；如果B1滿了，第一個(gè)進(jìn)程不能再進(jìn)行。 第二個(gè)進(jìn)程加工處理B1中的數(shù)據(jù)并搬到B2中，第三個(gè)進(jìn)程從B2讀出。如果B2為空，則第三個(gè)進(jìn)程無法進(jìn)行；如果B2滿了，第二個(gè)進(jìn)程無法進(jìn)行。（3）P:不能往滿的B1送數(shù)據(jù)，設(shè)信號(hào)量S1，初值為k（k為緩沖區(qū)B1的大?。﹚hile(true)讀一張卡片;P(S1);數(shù)據(jù)送到緩沖區(qū)B1;V(S2);Q:不能從空的B1讀數(shù)據(jù)，設(shè)信號(hào)量S2，初值為0；不能往滿的B2送數(shù)據(jù)，設(shè)信號(hào)量S3，初值為l（l為緩沖區(qū)B2的大?。﹚hile(true)P(S2);從緩沖區(qū)B1讀數(shù)據(jù);加工數(shù)據(jù);V(S1);P(S3)加工的數(shù)據(jù)寫入緩沖區(qū)B2;V(S4);R:不能從空的B2讀數(shù)據(jù)，設(shè)信號(hào)量S4，初值為0；while(true)P(S4);從緩沖區(qū)B2讀數(shù)據(jù);V(S3)打印;（4）卡片打印機(jī)B1B2B1未滿B2未滿B1非空B2非空進(jìn)程一：運(yùn)行就緒等待jklmjB1滿kB1未滿l卡片全部讀完m新的一批卡片作業(yè)進(jìn)程二：運(yùn)行就緒等待jklmjB2滿kB2未滿lB1空mB1非空進(jìn)程三：運(yùn)行就緒等待jklj無條件k B2空l(shuí) B2非空13假定一個(gè)閱覽室最多可容納100人，讀者進(jìn)入和離開閱覽室時(shí)都必須在閱覽室門口的一個(gè)登記表上標(biāo)志（進(jìn)入時(shí)登記，離開時(shí)去掉登記項(xiàng)），而且每次只允許一人登記或去掉登記，問：（1） 應(yīng)編寫幾個(gè)程序完成此項(xiàng)工作，程序的主要?jiǎng)幼魇切┦裁?？?yīng)設(shè)置幾個(gè)進(jìn)程？進(jìn)程與程序間的對(duì)應(yīng)關(guān)系如何？（2） 用P、V操作寫出這些進(jìn)程的同步通信關(guān)系。答：（1） 應(yīng)該編寫四個(gè)程序完成工作，分別執(zhí)行：管理等待登入隊(duì)列，登入并分配資源，管理等待離開隊(duì)列，登出并回收資源。應(yīng)設(shè)置2個(gè)進(jìn)程，分別負(fù)責(zé)管理登入和負(fù)責(zé)管理登出。（2） 設(shè)置readercount=100，控制可進(jìn)入的讀者數(shù)設(shè)置mutex=1，控制操作登記表登入進(jìn)程：P(mutex)P(readercount）分配閱覽室資源V(mutex)登出進(jìn)程：P(mutex)回收閱覽室資源V(readercount)V(mutex)17假設(shè)一個(gè)系統(tǒng)的磁盤大小為2kB，一個(gè)塊的平均訪問時(shí)間是20毫秒，一個(gè)有40kB的進(jìn)程由于資源請(qǐng)求此從運(yùn)行狀態(tài)變?yōu)樽枞麘B(tài)。要確保將該進(jìn)程換出，它必須保持阻塞多長(zhǎng)時(shí)間？解：阻塞時(shí)間：T = 40/2 * 20 =400 (毫秒)18.假使A、B兩個(gè)火車站之間是單軌線，許多列車可以同時(shí)到達(dá)A站，然后經(jīng)A站到B站，又列車從A到B的行駛時(shí)間是t，列車到B站后的停留時(shí)間是t/2。試問在該問題模型中，什么是臨界資源？什么是臨界區(qū)？答：因?yàn)樵S多列車可以同時(shí)到達(dá)A站，所以A站不是互斥資源，而A、B之間的單軌線每次只能允許一輛列車發(fā)出以后另一輛才能發(fā)出。因?yàn)榱熊囆旭倳r(shí)間為t，B的停留時(shí)間為t/2，所以只要在前一輛列車走完前1/2路程后再發(fā)車，到達(dá)B站時(shí)前一輛車也已離開B站。（1）A、B間單軌線的前半段是臨界資源。 （2）臨界區(qū)：列車在單軌線前半段上行駛21題 （測(cè)驗(yàn)的最后一題，類似，更簡(jiǎn)單）由于有m個(gè)發(fā)送者，n個(gè)接收者，k大小的緩沖區(qū)；從單個(gè)的問題出發(fā)，發(fā)送者要么等待在第x緩沖區(qū)（條件是緩沖區(qū)x未被清空，而發(fā)送者采用遞增環(huán)狀方式使用緩沖區(qū)）要么發(fā)送到x，發(fā)送完后需要喚醒所有接收進(jìn)程。接收進(jìn)程不停的輪詢緩沖區(qū),也采用遞增環(huán)狀方式，如果緩沖區(qū)有內(nèi)容，則收取，并把此緩沖區(qū)的未接收數(shù)減一，如果減至0，則置緩沖區(qū)為空。綜上所述，需要對(duì)每個(gè)緩沖區(qū)單位設(shè)置空，滿，互斥量，未收取數(shù)（empty，full，mutex，count）其中full是一個(gè)數(shù)組，記錄每個(gè)接收者的情況，防止重復(fù)接收，mutex主要用來做count的互斥訪問。此外，還要設(shè)置全局的互斥變量mutex。Type BufferType = Recordmsg:MessageType;count:integer;mutex:semaphore; 初值為1empty: semaphore; 初值為1full: array 1.n of semaphore； 初值全為0EndVar mutex: semaphore; 初值為1s: integer; 初值為0buff: array 0.k-1 of BufferType; k是緩沖區(qū)大??； n是接收進(jìn)程個(gè)數(shù) m是發(fā)送進(jìn)程個(gè)數(shù)，通過 s 進(jìn)行“寫互斥” Procedure Sender_i(i:integer); i 為發(fā)送進(jìn)程的標(biāo)號(hào)Vars0, j: integer;Begin Repeat P(mutex); s0:=s; s:=(s+1) mod k; V(mutex); P(buffs0.empty)； 在buffs0.msg中寫信息； P(buffs0.mutex)； buffs0.count:=n; V(buffs0.mutex); For (j:=1 to n do) V(buffs0.fullj); Until false;EndProcedure Recvr(i:integer); i 為接收進(jìn)程的標(biāo)號(hào)Varj: integer;Begin j:=0; Repeat P(buffj.fulli); 從buffj.msg中讀信息； P(buffj.mutex)； buffj.count:= buffj.count-1; If (buffj.count=0) Then V(buffj.empty)； V(buffj.mutex); j:=(j+1) mod kUntil false;End22.信號(hào)量說明：mutex，初值為，記錄可進(jìn)入臨界區(qū)的進(jìn)程數(shù);互斥算法；P(mutex); 進(jìn)入臨界區(qū)；V(mutex); 結(jié)束； .信號(hào)量說明：mutex，初值為m，記錄可進(jìn)入臨界區(qū)的進(jìn)程數(shù); 互斥算法；P(mutex); 進(jìn)入臨界區(qū)；V(mutex);結(jié)束；25.一家快餐店招有4種雇員：（1）開票者，取顧客的訂單；（2）廚師，準(zhǔn)備飯菜；（3）包裝員，把食物撞進(jìn)袋中；（4）出納，一手收錢一手交貨。每位雇員可以看作一個(gè)在通信的順序進(jìn)程。他們采用的是什么方式的進(jìn)程間通信？ 答：開票者和廚師之間是管道通信。開票者源源不斷的把訂單給廚師，一次可能給一張也可能給多張，廚師一次可能拿走一張訂單去做也可能拿走多張去做。廚師和包裝員之間是信箱通信，他們之間有個(gè)信箱，可能就是一個(gè)小平臺(tái)，廚師做好就把菜放上去，相當(dāng)于放進(jìn)信箱 ，而包裝員可以在任何時(shí)候取走那個(gè)菜。包裝員和出納之間是消息緩沖通信，包裝員包號(hào)了就給出納發(fā)消息，出納得到消息就取走包好的飯菜然后出售。 29計(jì)算系統(tǒng)CPU利用率。答：1）Q等于無窮時(shí)，算法退化為FIFO，這時(shí)CPU利用率為T/（S+T）2）QT時(shí)，進(jìn)程在用完時(shí)間片之前已被堵塞，因此CPU利用率仍為T/（S+T）3）SQ=2)級(jí)船閘，并且只能允許單向通行。船閘依次編號(hào)為1、2、T。由大西洋來的船需經(jīng)由船閘T、T-1、1通過運(yùn)河到太平洋；由太平洋來的船需經(jīng)由船閘1、2、T通過運(yùn)河到大西洋。試用P、V操作正確解決大西洋和太平洋的船只通航問題答：來自不同方向的船只對(duì)船閘要互斥使用。但如過有同方向的船只正在通行，則不用等待。對(duì)一個(gè)船閘設(shè)以下變量：PtoAcount 整型，記錄此船閘正由太平洋往大西洋航行的船只 初值0。AtoPcount 整型，記錄此船閘正由大西洋往太平洋航行的船只 初值0。Mutex 信號(hào)量，對(duì)PtoAcount互斥 初值1Mutex1 信號(hào)量，對(duì)AtoPcount互斥 初值1Pass 信號(hào)量 初值1太平洋到大西洋的船：P(mutex);PtoAcount:=PtoAcount+1;if PtoAcount = 1then P(pass);V(mutex);過P(mutex)PtoAcount:=PtoAcount-1;if PtoAcount = 0;then V(pass);V(mutex);大西洋到太平洋的船:P(mutex1);AtoPcount:=AtoPcount+1;if AtoPcount = 1;then P(pass);V(mutex1);過P(mutex1)AtoPcount:=AtoPcount-1;if AtoPcount = 0;then V(pass);V(mutex1);32題：有5個(gè)帶運(yùn)行的作業(yè)，它們的估計(jì)運(yùn)行時(shí)間分別是9，6，3，5和x。采用那種次序的運(yùn)行各種作業(yè)將得到最短的平均響應(yīng)時(shí)間。解：采用最短作業(yè)優(yōu)先法運(yùn)行作業(yè)將得到最短平均相應(yīng)時(shí)間。具體執(zhí)行順序是（依賴x） ：1） x=3時(shí) ，x 3 5 6 92） 3x=5時(shí)，3 x 5 6 93） 5x=6時(shí)，3 5 x 6 94） 6x=9時(shí)，3 5 6 x 95） 9x 時(shí)，3 5 6 9 x 35答：設(shè)有n個(gè)柜臺(tái)需要考慮等待人數(shù)如果沒有顧客 則柜臺(tái)需要等待 設(shè)置 empty = 0如果顧客太多 則顧客需要等待 設(shè)置 Customer = 0int CUSTOMER_NUM = 1;int COUNTER_NUM = 1;Customer/取號(hào)碼P(MUTEX_CUSTOMER_NUM);int X = CUSTOMER_NUM;CUSTOMER_NUM+;V(MUTEX_CUSTOMER_NUM);/等待叫號(hào)V(COUNTER);P(CUSTOMER);ACTION_CUSTOMER(X);Counterint X;REPEAT/叫號(hào)P(COUNTER);V(CUSTOMER);P(MUTEX_COUNTER_NUM);int X = COUNTER_NUM;V(MUTEX_COUNTER_NUM);ACTION_COUNTER(X);UNTIL false;37.對(duì)PV操作定義做如下修改P(s): s:=s-1; If s0 Then 將本進(jìn)程插入相應(yīng)隊(duì)列末尾等待；V(s)： s:=s+1; If s=0 Then 從等待隊(duì)列隊(duì)尾取一個(gè)進(jìn)程喚醒，插入就緒隊(duì)列 問題：（實(shí)現(xiàn)4個(gè)進(jìn)程使用某一個(gè)需互斥使用的資源）1）這樣定義P、V操作是否有問題？不合理：先進(jìn)后出；可能“無限等待”2）先考慮用這樣的P、V操作實(shí)現(xiàn)N個(gè)進(jìn)程競(jìng)爭(zhēng)使用某一共享變量的互斥機(jī)制。思路：令等待隊(duì)列中始終只有一個(gè)進(jìn)程。將 “?！?變成 “隊(duì)列”Var S:array 1.n-1 of semaphore; n為進(jìn)程數(shù)目；Si初值為i；Sn-1到S1的作用好象是 n-1 層篩子 Procedure Pi;Var i:integer;BeginRepeat Pre_Do_it();For i:=n-1 Downto 1 Do P(Si);Do_It_In_Critical_Section;For i:=1 To n-1 Do V(Si); Post_Do_it();Until false;End3）對(duì)于2）的解法，有無效率更高的方法。如有，試問降低了多少?gòu)?fù)雜性？上述解法每次都需要做2(n-1)次P/V操作，性能低下。采用二叉樹的思想，改進(jìn)如下：設(shè)有4個(gè)進(jìn)程P1.P4，Var S1, S2, S3: semaphore; 初值為1Procedure P1; P2 is the sameBegin Repeat P(S1);P(S3);Do_It();V(S3);V(S1);Until false;End;Procedure P3; P4 is the sameBegin Repeat P(S2);P(S3);Do_It();V(S3);V(S2);Until false;End;假設(shè)共有2N個(gè)進(jìn)程爭(zhēng)用臨界區(qū)；時(shí)間復(fù)雜性： 2N -1 vsN；空間復(fù)雜性： 2N-1 vs 2N-138 用進(jìn)程通訊的辦法解決生產(chǎn)者消費(fèi)者問題問題（設(shè)有N個(gè)緩沖區(qū)）生產(chǎn)者：Void producer (void) int item; Message m; While (TRUE) produce_item (&item); Receive (consumer, &m); Build_message (&m, item); Send (consumer, &m); 消費(fèi)者：Void consumer (void); int item, I; Message m; For (i=0;iN; i+) send (producer, &m); /發(fā)N條空消息 While (TRUE) Receive ( producer ,&m)； Extract_item( &m, &item); Send (producer ,&m); Consumer_item(item); 39.用管程實(shí)現(xiàn)哲學(xué)家就餐問題解法思想如下： 一個(gè)想用餐的哲學(xué)家首先拿他（她）的左邊叉子，拿到后若他（她）的右邊的叉子時(shí)空閑的則拿起它開始用餐，否則，他（她）放下左邊的叉子并重復(fù)這個(gè)過程。 該解法是非構(gòu)造性的，即假設(shè)管程已經(jīng)實(shí)現(xiàn)。FUNCTION test_and_pick_up(i:0.4):boolean;BEGIN IF fork i=used THEN test_and_pick_up=false ELSE BEGIN fork i:=used; test_and_pick_up:=true ENDEND;PROCEDURE put_down(i:0.4); 放下 BEGIN fork i=free; signal (queue i); END; PROCEDURE initialize; 初始化 VAR i:0.4 BEGIN FOR i:=0 TO 4 DO BEGIN fork i:=