操作系統(tǒng)習(xí)題.doc

六、兩個(gè)進(jìn)程合作完成一個(gè)任務(wù)。在并發(fā)執(zhí)行中，一個(gè)進(jìn)程要等待其合作伙伴發(fā)來消 息，或者建立某個(gè)條件后再向前執(zhí)行，這種制約性合作關(guān)系被稱為進(jìn)程的。 A.同步 B互斥 C. 調(diào)度 D執(zhí)行 答：A 七、為了進(jìn)行進(jìn)程協(xié)調(diào)，進(jìn)程之間應(yīng)當(dāng)具有一定的聯(lián)系，這種聯(lián)系通常采用進(jìn)程間交換數(shù)據(jù)的方式進(jìn)行，這種方式稱為。 A.進(jìn)程互斥 B進(jìn)程同步 C進(jìn)程制約 D進(jìn)程通信 答：D 八、在測量控制系統(tǒng)中，數(shù)據(jù)采集任務(wù)把所采集的數(shù)據(jù)送入一單緩沖區(qū);計(jì)算任務(wù)從該單緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計(jì)算。試寫出利用信號(hào)量機(jī)制實(shí)現(xiàn)兩者共享單緩沖區(qū)的同步算法。P33 分析及相關(guān)知識(shí) 在本題中采集任務(wù)與計(jì)算任務(wù)共用一個(gè)單緩沖區(qū)當(dāng)采集 任務(wù)采集到一個(gè)數(shù)據(jù)后，只有當(dāng)緩沖區(qū)為空時(shí)才能將數(shù)據(jù)送入緩沖區(qū)中存放，否則應(yīng)等待緩沖區(qū)騰空;當(dāng)緩沖區(qū)中有數(shù)據(jù)時(shí)，計(jì)算任務(wù)才能從緩沖區(qū)中取出數(shù)據(jù)進(jìn)行計(jì)算，否則也應(yīng)等待。 本題實(shí)際上是一個(gè)生產(chǎn)者消費(fèi)者問題。將生產(chǎn)者消費(fèi)者問題抽象出來，以另外 一種形式描述是一種常見的試題形式只要對(duì)生產(chǎn)者消費(fèi)者問題有了深入的理 解，就不難解決此類試題。 解;在本題中，應(yīng)設(shè)置兩個(gè)信號(hào)量Sf,Se，信號(hào)量Sf表示緩沖區(qū)中是否有可供打印的計(jì)算結(jié)果，其初值為0;信號(hào)量Se用于表示緩沖區(qū)有無空位置存放新的信息，其初值為1。 本題的同步描述如下： int Se=l; int Sf=0; main() cobegin get(); compute(); coend get() while (采集工作未完成) 采集一個(gè)數(shù)據(jù)： p(Se); 將數(shù)據(jù)送入緩沖區(qū)中; v(Sf); compute() while(計(jì)算工作未完成) p(Sf); 從緩沖區(qū)中取出數(shù)據(jù); v(Se); 進(jìn)行數(shù)據(jù)計(jì)算; 九、圖27給出了四個(gè)進(jìn)程合作完成某一任務(wù)的前趨圖，試說明這四個(gè)進(jìn)程間的同步關(guān)系，并用P、V操作描述它。P35 圖27 四個(gè)合作進(jìn)程的前趨圖 解：圖27說明任務(wù)啟動(dòng)后S1先執(zhí)行。當(dāng)S1結(jié)束后，S2、S3可以開始執(zhí)行。S2、S3 完成后，S4才能開始執(zhí)行。為了確保這一執(zhí)行順序，設(shè)三個(gè)同步信號(hào)量b2、b3、b4分別 表示進(jìn)程S2、S3、S4是否可以開始執(zhí)行，其初值均為0。這四個(gè)進(jìn)程的同步描述如下： int b2=0; /*表示進(jìn)程S2是否可以開始執(zhí)行* int b3=0; /*表示進(jìn)程S3是否可以開始執(zhí)行* int b4=0; /*表示進(jìn)程S4是否可以開始執(zhí)行* main() cobegin S1 ( ); S2 ( ); S3 ( ); S4 ( ); coend S1 ( ) v(b2); v(b3); S2 ( ) p(b2); v(b4); S3 ( ) p(b3)： v(b4); S4 ( ) p(b4); p(b4); /*因在S2及S3完成時(shí)均對(duì)b4做了v操作，因此這里要用兩個(gè)p操作* 十、桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用P、V原語實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。P37 分析及相關(guān)知識(shí) 在本題中，爸爸、兒子、女兒共用一個(gè)盤子，且盤中一次只能放一個(gè)水果當(dāng)盤子為空時(shí)，爸爸可將一個(gè)水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待;若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實(shí)際上是生產(chǎn)者消費(fèi)者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費(fèi)者也有兩類，每類消費(fèi)者只消費(fèi)其中固定的一類產(chǎn)品。 解：在本題中，應(yīng)設(shè)置三個(gè)信號(hào)量S、So、Sa，信號(hào)量S表示盤子是否為空，其初值 為1;信號(hào)量So表示盤中是否有桔子，其初值為0;信號(hào)量Sa表示盤中是否有蘋果，其初 值為0。同步描述如下： int S=1; int Sa=O： int So=O： main( ) cobegin father(); son(); daughter()： coend father() while (1) p(S); 將水果放入盤中; if(放入的是桔子) v(So)： else v(Sa); ) son( ) while(1) p(So); 從盤中取出桔子; v(S); 吃桔子; daushter() while(1) p(Sa); 從盤中取出蘋果; v(S)： 吃蘋果; PV原語操作詳解 PV原語通過操作信號(hào)量來處理進(jìn)程間的同步與互斥的問題。其核心就是一段不可分割不可中斷的程序。 信號(hào)量的概念1965年由著名的荷蘭計(jì)算機(jī)科學(xué)家Dijkstra提出，其基本思路是用一種新的變量類型(semaphore)來記錄當(dāng)前可用資源的數(shù)量。 semaphore有兩種實(shí)現(xiàn)方式： 1) semaphore的取值必須大于或等于0。0表示當(dāng)前已沒有空閑資源，而正數(shù)表示當(dāng)前空閑資源的數(shù)量； 2) semaphore的取值可正可負(fù)，負(fù)數(shù)的絕對(duì)值表示正在等待進(jìn)入臨界區(qū)的進(jìn)程個(gè)數(shù)。 信號(hào)量是由操作系統(tǒng)來維護(hù)的，用戶進(jìn)程只能通過初始化和兩個(gè)標(biāo)準(zhǔn)原語(P、V原語)來訪問。初始化可指定一個(gè)非負(fù)整數(shù)，即空閑資源總數(shù)。 P原語：P是荷蘭語Proberen(測試)的首字母。為阻塞原語，負(fù)責(zé)把當(dāng)前進(jìn)程由運(yùn)行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)，直到另外一個(gè)進(jìn)程喚醒它。操作為：申請(qǐng)一個(gè)空閑資源(把信號(hào)量減1)，若成功，則退出；若失敗，則該進(jìn)程被阻塞； V原語：V是荷蘭語Verhogen(增加)的首字母。為喚醒原語，負(fù)責(zé)把一個(gè)被阻塞的進(jìn)程喚醒，它有一個(gè)參數(shù)表，存放著等待被喚醒的進(jìn)程信息。操作為：釋放一個(gè)被占用的資源(把信號(hào)量加1)，如果發(fā)現(xiàn)有被阻塞的進(jìn)程，則選擇一個(gè)喚醒之。 P原語操作的動(dòng)作是： (1)sem減1； (2)若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行； (3)若sem減1后小于零，則該進(jìn)程被阻塞后進(jìn)入與該信號(hào)相對(duì)應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。 V原語操作的動(dòng)作是： (1)sem加1； (2)若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行； (3)若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。 PV操作對(duì)于每一個(gè)進(jìn)程來說，都只能進(jìn)行一次，而且必須成對(duì)使用。在PV原語執(zhí)行期間不允許有中斷的發(fā)生。 - 具體PV原語對(duì)信號(hào)量的操作可以分為三種情況： 1) 把信號(hào)量視為一個(gè)加鎖標(biāo)志位，實(shí)現(xiàn)對(duì)一個(gè)共享變量的互斥訪問。 實(shí)現(xiàn)過程： P(mutex); / mutex的初始值為1 訪問該共享數(shù)據(jù); V(mutex); 非臨界區(qū); 2) 把信號(hào)量視為是某種類型的共享資源的剩余個(gè)數(shù)，實(shí)現(xiàn)對(duì)一類共享資源的訪問。 實(shí)現(xiàn)過程： P(resource); / resource的初始值為該資源的個(gè)數(shù)N 使用該資源； V(resource); 非臨界區(qū); 3) 把信號(hào)量作為進(jìn)程間的同步工具 實(shí)現(xiàn)過程： 臨界區(qū)C1; P(S); V(S); 臨界區(qū)C2; - 舉例說明： 例1：某超市門口為顧客準(zhǔn)備了100輛手推車，每位顧客在進(jìn)去買東西時(shí)取一輛推車，在買完東西結(jié)完帳以后再把推車還回去。試用P、V操作正確實(shí)現(xiàn)顧客進(jìn)程的同步互斥關(guān)系。 分析：把手推車視為某種資源，每個(gè)顧客為一個(gè)要互斥訪問該資源的進(jìn)程。因此這個(gè)例子為PV原語的第二種應(yīng)用類型。 解： semaphoreS_CartNum;/ 空閑的手推車數(shù)量，初值為100 void consumer(void)/ 顧客進(jìn)程 P(S_CartNum); 買東西; 結(jié)帳; V(S_CartNum); 例2：桌子上有一個(gè)水果盤，每一次可以往里面放入一個(gè)水果。爸爸專向盤子中放蘋果，兒子專等吃盤子中的蘋果。把爸爸、兒子看作二個(gè)進(jìn)程，試用P、V操作使這兩個(gè)進(jìn)程能正確地并發(fā)執(zhí)行。 分析：爸爸和兒子兩個(gè)進(jìn)程相互制約，爸爸進(jìn)程執(zhí)行完即往盤中放入蘋果后，兒子進(jìn)程才能執(zhí)行即吃蘋果。因此該問題為進(jìn)程間的同步問題。 解： semaphore S_PlateNum; / 盤子容量，初值為1 semaphore S_AppleNum;/ 蘋果數(shù)量，初值為0 void father( )/ 父親進(jìn)程 while(1) P(S_PlateNum); 往盤子中放入一個(gè)蘋果; V(S_AppleNum); void son( )/ 兒子進(jìn)程 while(1) P(S_AppleNum); 從盤中取出蘋果; V(S_PlateNum); 吃蘋果； - 另附用PV原語解決進(jìn)程同步與互斥問題的例子: 例3：兩個(gè)進(jìn)程PA、PB通過兩個(gè)FIFO(先進(jìn)先出)緩沖區(qū)隊(duì)列連接(如圖) PA從Q2取消息，處理后往Q1發(fā)消息；PB從Q1取消息，處理后往Q2發(fā)消息，每個(gè)緩沖區(qū)長度等于傳送消息長度。 Q1隊(duì)列長度為n，Q2隊(duì)列長度為m. 假設(shè)開始時(shí)Q1中裝滿了消息，試用P、V操作解決上述進(jìn)程間通訊問題。 解： / Q1隊(duì)列當(dāng)中的空閑緩沖區(qū)個(gè)數(shù)，初值為0semaphore S_BuffNum_Q1; / Q2隊(duì)列當(dāng)中的空閑緩沖區(qū)個(gè)數(shù)，初值為msemaphore S_BuffNum_Q2; / Q1隊(duì)列當(dāng)中的消息數(shù)量，初值為nsemaphore S_MessageNum_Q1; / Q2隊(duì)列當(dāng)中的消息數(shù)量，初值為0semaphore S_MessageNum_Q2; voidPA( ) while(1) P(S_MessageNum_Q2); 從Q2當(dāng)中取出一條消息; V(S_BuffNum_Q2); 處理消息; 生成新的消息; P(S_BuffNum_Q1); 把該消息發(fā)送到Q1當(dāng)中; V(S_MessageNum_Q1); voidPB( ) while(1) P(S_MessageNum_Q1); 從Q1當(dāng)中取出一條消息; V(S_BuffNum_Q1); 處理消息; 生成新的消息; P(S_BuffNum_Q2); 把該消息發(fā)送到Q2當(dāng)中; V(S_MessageNum_Q2); 例4：操作系統(tǒng)課程的期末考試即將舉行，假設(shè)把學(xué)生和監(jiān)考老師都看作進(jìn)程，學(xué)生有N人，教師1人?？紙鲩T口每次只能進(jìn)出一個(gè)人，進(jìn)考場的原則是先來先進(jìn)。當(dāng)N個(gè)學(xué)生都進(jìn)入了考場后，教師才能發(fā)卷子。學(xué)生交卷后即可離開考場，而教師要等收上來全部卷子并封裝卷子后才能離開考場。 (1)問共需設(shè)置幾個(gè)進(jìn)程? (2)請(qǐng)用P、V操作解決上述問題中的同步和互斥關(guān)系。 解： semaphore S_Door;/ 能否進(jìn)出門，初值1 semaphore S_StudentReady;/ 學(xué)生是否到齊，初值為0 semaphore S_ExamBegin;/ 開始考試，初值為0 semaphore S_ExamOver;/ 考試結(jié)束，初值為0 intnStudentNum = 0;/ 學(xué)生數(shù)目 semaphore S_Mutex1;/互斥信號(hào)量，初值為1 int nPaperNum = 0;/ 已交的卷子數(shù)目 semaphore S_Mutex2;/互斥信號(hào)量，初值為1 void student( ) P(S_Door); 進(jìn)門; V(S_Door); P(S_Mutex1)； nStudentNum +;/ 增加學(xué)生的個(gè)數(shù) if(nStudentNum = N) V(S_StudentReady); V(S_Mutex1); P(S_ExamBegin);/ 等老師宣布考試開始 考試中 交卷; P(S_Mutex2); nPaperNum +;/ 增加試卷的份數(shù) if(nPaperNum = N) V(S_ExamOver); V(S_Mutex2); P(S_Door); 出門; V(S_Door); void teacher( ) P(S_Door); 進(jìn)門; V(S_Door); P(S_StudentReady);/等待最后一個(gè)學(xué)生來喚醒 發(fā)卷子; for(i = 1; i = N; i+) V(S_ExamBegin); P(S_ExamOver);/等待考試結(jié)束 封裝試卷; P(S_Door); 出門; V(S_Door); 例 5：某商店有兩種食品A和B，最大數(shù)量均為m個(gè)。 該商店將A、B兩種食品搭配出售，每次各取一個(gè)。為避免食品變質(zhì)，遵循先到食品先出售的原則。有兩個(gè)食品公司分別不斷地供應(yīng)A、B兩種食品(每次一個(gè))。為保證正常銷售，當(dāng)某種食品的數(shù)量比另一種的數(shù)量超過k(k 0) / 優(yōu)先喚醒女生 girls_waiting -; V(S_girls); else if(boys_waiting 0) boys_waiting -; V(S_ boys); else using = 0;/ 無人在等待 V(S_mutex); void girl_wants_to_use_bathroom ( ) P(S_mutex); if(using = 0) using = 1; V(S_mutex); else girls_waiting +; V(S_mutex); P(S_girls); void girl_leaves_bathroom ( ) P(S_mutex); if(girls_waiting 0) / 優(yōu)先喚醒女生 girls_waiting -; V(S_girls); else if(boys_waiting 0) boys_waiting -; V(S_ boys); else using = 0;/ 無人在等待 V(S_mutex); 再附上幾個(gè)例子： * 用PV原語實(shí)現(xiàn)進(jìn)程的互斥 由于用于互斥的信號(hào)量sem與所有的并發(fā)進(jìn)程有關(guān)，所以稱之為公有信號(hào)量。公有信號(hào)量的值反映了公有資源的數(shù)量。只要把臨界區(qū)置于P(sem)和V(sem)之間，即可實(shí)現(xiàn)進(jìn)程間的互斥。就象火車中的每節(jié)車廂只有一個(gè)衛(wèi)生間，該車廂的所有旅客共享這個(gè)公有資源：衛(wèi)生間，所以旅客間必須互斥進(jìn)入衛(wèi)生間，只要把衛(wèi)生間放在P(sem)和V(sem)之間，就可以到達(dá)互斥的效果。以下例子說明進(jìn)程的互斥實(shí)現(xiàn)。 例1： 生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個(gè)箱子里，現(xiàn)要用自動(dòng)分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成，功能如下：(1)進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；(2)每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子； 分析： 第一步：確定進(jìn)程間的關(guān)系。由功能(2)可知進(jìn)程之間是互斥的關(guān)系。 第二步：確定信號(hào)量及其值。由于進(jìn)程A和進(jìn)程B要互斥進(jìn)入箱子去揀棋子，箱子是兩個(gè)進(jìn)程的公有資源，所以設(shè)置一個(gè)信號(hào)量s，其值取決于公有資源的數(shù)目，由于箱子只有一個(gè)，s的初值就設(shè)為1。 實(shí)現(xiàn)：begin s:semaphore; s:=1; cobegin process A begin L1: P(s); 揀黑子; V(s); goto L1; end; process B begin L2:P(s); 揀白子； V(s); goto L2; end; coend;end;判斷進(jìn)程間是否互斥，關(guān)鍵是看進(jìn)程間是否共享某一公有資源，一個(gè)公有資源與一個(gè)信號(hào)量相對(duì)應(yīng)。確定信號(hào)量的值是一個(gè)關(guān)鍵點(diǎn)，它代表了可用資源實(shí)體數(shù)。如下實(shí)例： 例2： 某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí)，廳外的購票者可立即進(jìn)入，否則需要在外面等待。每個(gè)購票者可看成一個(gè)進(jìn)程。 分析：第一步：確定進(jìn)程間的關(guān)系。售票廳是各進(jìn)程共享的公有資源，當(dāng)售票廳中多于20名購票者時(shí)，廳外的購票者需要在外面等待。所以進(jìn)程間是互斥的關(guān)系。第二步：確定信號(hào)量及其值。只有一個(gè)公有資源：售票廳，所以設(shè)置一個(gè)信號(hào)量s。售票廳最多容納20個(gè)進(jìn)程，即可用資源實(shí)體數(shù)為20，s的初值就設(shè)為20。 實(shí)現(xiàn)：begin s:semaphore; s:=20; cobegin process PI(I=1,2,) begin P(s); 進(jìn)入售票廳; 購票; 退出; V(s); end; coend; end; 當(dāng)購票者進(jìn)入售票廳前要執(zhí)行P(s)操作，執(zhí)行后若s大于或等于零，說明售票廳的人數(shù)還未滿可進(jìn)入。執(zhí)行后若s小于零，則說明售票廳的人數(shù)已滿不能進(jìn)入。這個(gè)實(shí)現(xiàn)中同時(shí)最多允許20個(gè)進(jìn)程進(jìn)入售票廳購票，其余進(jìn)程只能等待。用PV原語實(shí)現(xiàn)進(jìn)程的同步 與進(jìn)程互斥不同，進(jìn)程同步時(shí)的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān)，所以稱該信號(hào)量為私有信號(hào)量。利用PV原語實(shí)現(xiàn)進(jìn)程同步的方法是：首先判斷進(jìn)程間的關(guān)系為同步的，且為各并發(fā)進(jìn)程設(shè)置私有信號(hào)量，然后為私有信號(hào)量賦初值，最后利用PV原語和私有信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序。下面我們將例1增添一個(gè)條件，使其成為進(jìn)程間是同步的。 例3： 在例1的基礎(chǔ)之上再添加一個(gè)功能：(3)當(dāng)一個(gè)進(jìn)程揀了一個(gè)棋子（黑子或白子）以后，必讓另一個(gè)進(jìn)程揀一個(gè)棋子（黑子或白子）。 分析： 第一步：確定進(jìn)程間的關(guān)系。由功能（1）（2）（3）可知，進(jìn)程間的關(guān)系為同步關(guān)系。第二步：確定信號(hào)量及其值。進(jìn)程A和B共享箱子這個(gè)公有資源，但規(guī)定兩個(gè)進(jìn)程必須輪流去取不同色的棋子，因而相互間要互通消息。對(duì)于進(jìn)程A可設(shè)置一個(gè)私有信號(hào)量s1，該私有信號(hào)量用于判斷進(jìn)程A是否能去揀黑子，初值為1。對(duì)于進(jìn)程B同樣設(shè)置一個(gè)私有信號(hào)量s2，