1、習(xí)題課（一）張航2013.11.4Contact me張航Email: Addr : 西一樓721Ftp : 28User : stuPwd : 2013Upload your file to /up/, download the shared file from /down/.Brief 第六章及之前作業(yè)存在的問(wèn)題 補(bǔ)充習(xí)題（重點(diǎn)在于進(jìn)程同步）Assignment: 6.4Points：1.等待自旋鎖期間進(jìn)程仍然等待自旋鎖期間進(jìn)程仍然占用處理器占用處理器2.自旋鎖需要的進(jìn)入條件必須由自旋鎖需要的進(jìn)入條件必須由其他進(jìn)程其他進(jìn)程滿(mǎn)足滿(mǎn)足Assignment: 6

2、.9Advice:將高級(jí)語(yǔ)言代碼細(xì)化為匯編代碼進(jìn)行分析將高級(jí)語(yǔ)言代碼細(xì)化為匯編代碼進(jìn)行分析start:mov eax,scmp eax,0jng startdec eaxmov s,eaxAssignment: 6.11Steps:1.從題目中找出各方進(jìn)程爭(zhēng)奪的從題目中找出各方進(jìn)程爭(zhēng)奪的共享資源共享資源2.所有的共享資源都應(yīng)當(dāng)有所有的共享資源都應(yīng)當(dāng)有相應(yīng)的信號(hào)量相應(yīng)的信號(hào)量進(jìn)行保護(hù)進(jìn)行保護(hù)3.分析各角色的行為邏輯，必要時(shí)定義分析各角色的行為邏輯，必要時(shí)定義輔助變量或信號(hào)量輔助變量或信號(hào)量，如果輔助變量也是多，如果輔助變量也是多進(jìn)程共享訪(fǎng)問(wèn)的，則應(yīng)當(dāng)定義進(jìn)程共享訪(fǎng)問(wèn)的，則應(yīng)當(dāng)定義對(duì)應(yīng)的互斥鎖對(duì)應(yīng)

3、的互斥鎖mutex加以保護(hù)。加以保護(hù)。4.形成最終代碼形成最終代碼Tips：對(duì)信號(hào)量的使用一定要成對(duì)對(duì)信號(hào)量的使用一定要成對(duì)var mutex,customers, barbers : semaphore; waiting, chairs : integer; procedure barber: begin while(true) begin p(customers); p(mutex); waiting:= waiting 1 ; v(mutex); cuthair(); v(barbers); end endprocedure customer; begin p(mutex); if (w

4、aiting 東東 一人：東一人：東西西 兩個(gè)人：西兩個(gè)人：西東東 兩個(gè)人：東兩個(gè)人：東西西西東橋中央設(shè)置信號(hào)量如下設(shè)置信號(hào)量如下信號(hào)量信號(hào)量初值初值 含義含義 EW 2允許從東到西的人數(shù)允許從東到西的人數(shù) WE 2允許從西到東的人數(shù)允許從西到東的人數(shù) east 1是否允許在東段橋上是否允許在東段橋上 west 1是否允許在西段橋上是否允許在西段橋上eastTowest：begin P(EW); P(WE); P(east); 從東岸經(jīng)東段橋，走到橋中央； V(east); 通過(guò)橋中央或者休息； P(west); 經(jīng)西段橋，從橋中央到西岸； V(west); V(WE); V(EW); end

5、;沒(méi)有必要同時(shí)定義EW和WE。westToeast：begin P(EW); P(WE); P(west); 從西岸經(jīng)西段橋，走到橋中央； V(west); 通過(guò)橋中央或者休息； P(east); 經(jīng)東段橋，從橋中央到東岸； V(east); V(WE); V(EW); end; 3.把學(xué)生和監(jiān)考老師都看作進(jìn)程把學(xué)生和監(jiān)考老師都看作進(jìn)程, 學(xué)生有學(xué)生有N人人, 教師教師1人人. 考場(chǎng)門(mén)口每次只能進(jìn)出一個(gè)人考場(chǎng)門(mén)口每次只能進(jìn)出一個(gè)人, 進(jìn)考場(chǎng)原則是先來(lái)先進(jìn)進(jìn)考場(chǎng)原則是先來(lái)先進(jìn). 當(dāng)當(dāng)N個(gè)學(xué)生都進(jìn)入考場(chǎng)后個(gè)學(xué)生都進(jìn)入考場(chǎng)后, 教師才能發(fā)卷子教師才能發(fā)卷子. 學(xué)生交卷后學(xué)生交卷后可以離開(kāi)考場(chǎng)可以離開(kāi)

6、考場(chǎng). 教師要等收上來(lái)全部卷子并封裝卷子后才教師要等收上來(lái)全部卷子并封裝卷子后才能離開(kāi)考場(chǎng)能離開(kāi)考場(chǎng). 問(wèn)題問(wèn)題: 問(wèn)共需設(shè)置幾個(gè)進(jìn)程問(wèn)共需設(shè)置幾個(gè)進(jìn)程? 試用試用P、V操作解決上述問(wèn)題中的同步和互斥關(guān)系操作解決上述問(wèn)題中的同步和互斥關(guān)系. 該題解析是錯(cuò)誤的！該題解析是錯(cuò)誤的！ 【解析解析】： 定義一個(gè)共享變量定義一個(gè)共享變量StudentCounter=N 定義四個(gè)信號(hào)量：定義四個(gè)信號(hào)量： Mutex=1，實(shí)現(xiàn)考場(chǎng)門(mén)口的互斥進(jìn)入，實(shí)現(xiàn)考場(chǎng)門(mén)口的互斥進(jìn)入 M1=1，實(shí)現(xiàn)對(duì)，實(shí)現(xiàn)對(duì)StudentCounter的互斥訪(fǎng)問(wèn)；的互斥訪(fǎng)問(wèn)； M2=1，表示學(xué)生是否到齊了，教師是否可以發(fā)，表示學(xué)生是否到齊

7、了，教師是否可以發(fā)試卷；試卷； M3=1，表示試卷是否收齊了，教師是否可以離，表示試卷是否收齊了，教師是否可以離開(kāi)開(kāi) 共需設(shè)置二個(gè)進(jìn)程：學(xué)生進(jìn)程，教師進(jìn)程共需設(shè)置二個(gè)進(jìn)程：學(xué)生進(jìn)程，教師進(jìn)程學(xué)生：學(xué)生： P(mutex); 進(jìn)入考場(chǎng)；進(jìn)入考場(chǎng)； V(mutex);P（M1）；）； StudentCounter：=StudentCounter -1； If StudentCounter=0 V(M2);V(M1);答題；答題；P（M1）；）； StudentCounter：=StudentCounter+1； 交試卷；交試卷； If StudentCounter=N V(M3); 離開(kāi)考場(chǎng)；離開(kāi)

8、考場(chǎng)；V(M1); P(mutex); 離開(kāi)考場(chǎng)；離開(kāi)考場(chǎng)； V(mutex);教師：教師： P(mutex); 進(jìn)入考場(chǎng)；進(jìn)入考場(chǎng)； V(mutex); P（M2）；）； 發(fā)試卷；發(fā)試卷； 巡視考場(chǎng)；巡視考場(chǎng)； 收試卷；收試卷； P（M3）；）； 離開(kāi)離開(kāi)考慮一個(gè)學(xué)生“一馬當(dāng)先”的情況。不應(yīng)共用一個(gè)StudentCounter 4.流水線(xiàn)問(wèn)題流水線(xiàn)問(wèn)題 某流水線(xiàn)有某流水線(xiàn)有4個(gè)并發(fā)工序個(gè)并發(fā)工序P1、P2、P3、P4，他們，他們執(zhí)行情況如下：執(zhí)行情況如下： P1先執(zhí)行；先執(zhí)行；P1結(jié)束后，結(jié)束后，P2，P3同時(shí)開(kāi)始執(zhí)行，同時(shí)開(kāi)始執(zhí)行，P2，P3都結(jié)束后，都結(jié)束后，P1才能繼續(xù)下一次執(zhí)行，同時(shí)

9、才能繼續(xù)下一次執(zhí)行，同時(shí)P4開(kāi)始執(zhí)行。試用開(kāi)始執(zhí)行。試用PV操作實(shí)現(xiàn)他們之間的同步。操作實(shí)現(xiàn)他們之間的同步?！窘馕鼋馕觥浚篠A12,SB12,SA13,SB13,SB24,SB34;SemophoreSA12:=SA13:=1;SB12:=SB13:=SB24:=SB34:=0;Process PCBeginP(SB13)執(zhí)行執(zhí)行P3V(SB34)V(SA13)End;(PC)Process PBBeginP(SB12)執(zhí)行執(zhí)行P2V(SB24)V(SA12)End;(PB)Process PDBeginP(SB24)P(SB34)執(zhí)行執(zhí)行P4End;(PD)Process PABeginP(

10、SA12)P(SA13)執(zhí)行執(zhí)行P1V(SB13)V(SB12)End;(PA) 5.設(shè)在公共汽車(chē)上，司機(jī)和售票員的活動(dòng)分設(shè)在公共汽車(chē)上，司機(jī)和售票員的活動(dòng)分別如下：別如下： 司機(jī)的活動(dòng)：?jiǎn)?dòng)車(chē)輛；正常行車(chē)；到站司機(jī)的活動(dòng)：?jiǎn)?dòng)車(chē)輛；正常行車(chē)；到站停車(chē)。停車(chē)。 售票員的活動(dòng)：關(guān)車(chē)門(mén)；售票；開(kāi)車(chē)門(mén)。售票員的活動(dòng)：關(guān)車(chē)門(mén)；售票；開(kāi)車(chē)門(mén)。 問(wèn)題問(wèn)題:在汽車(chē)不停地到站、停車(chē)以及行駛的在汽車(chē)不停地到站、停車(chē)以及行駛的過(guò)程中，司機(jī)和售票員之間的活動(dòng)有什么同過(guò)程中，司機(jī)和售票員之間的活動(dòng)有什么同步關(guān)系？步關(guān)系？ 解答：解答： 首先分析兩個(gè)進(jìn)程之間的同步關(guān)系。汽車(chē)行駛過(guò)首先分析兩個(gè)進(jìn)程之間的同步關(guān)系。汽車(chē)行駛

11、過(guò)程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為： 售票員關(guān)車(chē)門(mén)后，向司機(jī)發(fā)開(kāi)車(chē)信號(hào)售票員關(guān)車(chē)門(mén)后，向司機(jī)發(fā)開(kāi)車(chē)信號(hào) 司機(jī)接到開(kāi)車(chē)信號(hào)后起動(dòng)車(chē)輛司機(jī)接到開(kāi)車(chē)信號(hào)后起動(dòng)車(chē)輛 在汽車(chē)正常行駛過(guò)程中售票員售票在汽車(chē)正常行駛過(guò)程中售票員售票 到站時(shí)司機(jī)停車(chē)到站時(shí)司機(jī)停車(chē) 售票員在車(chē)停后開(kāi)車(chē)門(mén)讓乘客下車(chē)售票員在車(chē)停后開(kāi)車(chē)門(mén)讓乘客下車(chē) 定義兩個(gè)信號(hào)量定義兩個(gè)信號(hào)量s1：表示是否允許司機(jī)起動(dòng)車(chē)輛，：表示是否允許司機(jī)起動(dòng)車(chē)輛，s2：表示是否允許售票員開(kāi)門(mén)。初值為：表示是否允許售票員開(kāi)門(mén)。初值為0。請(qǐng)將以下描述這兩個(gè)活動(dòng)的PV操作補(bǔ)充完整：Semaphore s1=0;S

12、emaphore s2=0;main()cobegindriver();conductor();Coend; driver()while(1)p(s1); 啟動(dòng)車(chē)輛；啟動(dòng)車(chē)輛； 正常行車(chē)；正常行車(chē)； 到站停車(chē)；到站停車(chē)； ； conductor()while(1)關(guān)車(chē)門(mén)；關(guān)車(chē)門(mén)； ； 售票；售票； p(s2); 開(kāi)車(chē)門(mén)；開(kāi)車(chē)門(mén)； 上下乘客；上下乘客；Semaphore s1=0;Semaphore s2=0;main()cobegindriver();conductor();Coend; driver()while(1)p(s1); 啟動(dòng)車(chē)輛；啟動(dòng)車(chē)輛； 正常行車(chē)；正常行車(chē)； 到站停車(chē)；到站停

13、車(chē)； v(s2)； conductor()while(1)關(guān)車(chē)門(mén)；關(guān)車(chē)門(mén)；v（s1） ； 售票；售票； p(s2); 開(kāi)車(chē)門(mén)；開(kāi)車(chē)門(mén)； 上下乘客；上下乘客；CPU調(diào)度習(xí)題（1）一個(gè)具有一個(gè)具有兩道兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)短作業(yè)優(yōu)先的調(diào)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以?xún)?yōu)先數(shù)為基礎(chǔ)的度算法，進(jìn)程調(diào)度采用以?xún)?yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度搶占式調(diào)度算法，如下算法，如下表的作業(yè)序列（表中所有作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，數(shù)值越小表的作業(yè)序列（表中所有作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，數(shù)值越小優(yōu)先級(jí)越高）。要求：優(yōu)先級(jí)越高）。要求：（1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間）列出所

14、有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間（2）計(jì)算平均周轉(zhuǎn)時(shí)間）計(jì)算平均周轉(zhuǎn)時(shí)間 作業(yè)名作業(yè)名 到達(dá)時(shí)間到達(dá)時(shí)間 估計(jì)運(yùn)算時(shí)間估計(jì)運(yùn)算時(shí)間 優(yōu)先數(shù)優(yōu)先數(shù) A 10：00 40分分 5 B 10：20 30分分 3 C 10：30 50分分 4 D 10：50 20分分 610:00 A作業(yè)到達(dá)作業(yè)到達(dá), 作業(yè)作業(yè)A調(diào)入內(nèi)存，進(jìn)程調(diào)度程序調(diào)度調(diào)入內(nèi)存，進(jìn)程調(diào)度程序調(diào)度A運(yùn)行運(yùn)行10:20 B作業(yè)到達(dá)作業(yè)到達(dá),作業(yè)作業(yè)B調(diào)入內(nèi)存調(diào)入內(nèi)存,搶占進(jìn)程搶占進(jìn)程A的處理機(jī)的處理機(jī),A回到就緒隊(duì)回到就緒隊(duì)列列,A還需運(yùn)行還需運(yùn)行20分鐘分鐘10:30 C作業(yè)到達(dá)作業(yè)到達(dá),在后備隊(duì)列中等待在后備隊(duì)列中等待10:50 B運(yùn)

15、行運(yùn)行30分鐘后結(jié)束運(yùn)行分鐘后結(jié)束運(yùn)行,D作業(yè)到達(dá)作業(yè)到達(dá),后備隊(duì)列中有后備隊(duì)列中有C,D兩個(gè)作業(yè)兩個(gè)作業(yè)等待調(diào)度等待調(diào)度,根據(jù)短作業(yè)優(yōu)先原則根據(jù)短作業(yè)優(yōu)先原則,D調(diào)入內(nèi)存調(diào)入內(nèi)存.內(nèi)存中內(nèi)存中,A在就緒隊(duì)列上已等待在就緒隊(duì)列上已等待了了30分鐘分鐘,A的優(yōu)先級(jí)高于的優(yōu)先級(jí)高于D,A運(yùn)行運(yùn)行,D就緒就緒.此時(shí)此時(shí)C在后備隊(duì)列中已等待了在后備隊(duì)列中已等待了20分鐘并繼續(xù)等待分鐘并繼續(xù)等待.11:10 A運(yùn)行結(jié)束運(yùn)行結(jié)束,C裝入內(nèi)存裝入內(nèi)存,C的優(yōu)先權(quán)高于的優(yōu)先權(quán)高于D,C運(yùn)行運(yùn)行,D繼續(xù)等繼續(xù)等待待,此時(shí)此時(shí)D已等待了已等待了20分鐘分鐘.12:00 C運(yùn)行結(jié)束運(yùn)行結(jié)束,D運(yùn)行運(yùn)行12:20 D

16、運(yùn)行結(jié)束運(yùn)行結(jié)束作業(yè)名作業(yè)名 進(jìn)入內(nèi)存時(shí)間進(jìn)入內(nèi)存時(shí)間 結(jié)束時(shí)間結(jié)束時(shí)間 A 10:00 11:10 B 10:20 10:50 C 11:10 12:00 D 10:50 12:20各作業(yè)的周轉(zhuǎn)時(shí)間為各作業(yè)的周轉(zhuǎn)時(shí)間為: A:70 B:30 C:90 D:90平均周轉(zhuǎn)時(shí)間為平均周轉(zhuǎn)時(shí)間為(70+30+90+90)/4=70一個(gè)一個(gè)四道四道作業(yè)的操作系統(tǒng)中，設(shè)在一段時(shí)間內(nèi)先后到達(dá)作業(yè)的操作系統(tǒng)中，設(shè)在一段時(shí)間內(nèi)先后到達(dá)6個(gè)作業(yè)，它個(gè)作業(yè)，它們的提交時(shí)間和運(yùn)行時(shí)間見(jiàn)下表們的提交時(shí)間和運(yùn)行時(shí)間見(jiàn)下表作業(yè)號(hào)作業(yè)號(hào) 提交時(shí)間提交時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 JOB1JOB2JOB3JOB4JOB5JOB68

17、:008:208:258:308:358:4060352025 510系統(tǒng)采用系統(tǒng)采用SJF算法，算法，作業(yè)被調(diào)度進(jìn)入運(yùn)行后不再退出作業(yè)被調(diào)度進(jìn)入運(yùn)行后不再退出，但當(dāng)一作業(yè)進(jìn)，但當(dāng)一作業(yè)進(jìn)入運(yùn)行時(shí)，可以調(diào)整運(yùn)行的優(yōu)先次序。入運(yùn)行時(shí)，可以調(diào)整運(yùn)行的優(yōu)先次序。1 分別給出上述分別給出上述6個(gè)作業(yè)的執(zhí)行時(shí)間次序個(gè)作業(yè)的執(zhí)行時(shí)間次序2 計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間CPU調(diào)度習(xí)題（調(diào)度習(xí)題（2 2）【解析解析】四道的系統(tǒng)四道的系統(tǒng),作業(yè)調(diào)度最多可選擇四道作業(yè)進(jìn)入內(nèi)存作業(yè)調(diào)度最多可選擇四道作業(yè)進(jìn)入內(nèi)存,以進(jìn)程的形式運(yùn)行以進(jìn)程的形式運(yùn)行;進(jìn)程調(diào)度采用可搶占的短作業(yè)優(yōu)先調(diào)度原則進(jìn)程調(diào)度采用可搶

18、占的短作業(yè)優(yōu)先調(diào)度原則8：00 J1到達(dá)，無(wú)競(jìng)爭(zhēng)者，進(jìn)入內(nèi)存。到達(dá)，無(wú)競(jìng)爭(zhēng)者，進(jìn)入內(nèi)存。8：20 J1運(yùn)行運(yùn)行20分鐘，剩余分鐘，剩余40分鐘；分鐘；J2到達(dá)，運(yùn)行時(shí)間為到達(dá)，運(yùn)行時(shí)間為35分鐘，分鐘，小于小于J1， 取代取代J1運(yùn)行。運(yùn)行。8：25 J1剩余剩余40分鐘，分鐘，J2剩余剩余30分鐘；分鐘；J3到達(dá)，運(yùn)行時(shí)間為到達(dá)，運(yùn)行時(shí)間為20分鐘，分鐘，取代取代J2運(yùn)行。運(yùn)行。8：30 J1剩余剩余40分鐘，分鐘，J2剩余剩余30分鐘，分鐘，J3剩余剩余15分鐘，分鐘，J4到達(dá)，運(yùn)到達(dá)，運(yùn)行時(shí)間為行時(shí)間為25分鐘，分鐘，J3繼續(xù)運(yùn)行。繼續(xù)運(yùn)行。8：35 J3剩余剩余10分鐘，分鐘，J5到達(dá)，運(yùn)行時(shí)間為到達(dá)，運(yùn)行時(shí)間為5分鐘，盡管最短，但內(nèi)分鐘，盡管最短，但內(nèi)存已經(jīng)有四道作業(yè)，因此，