西安交大操作系統(tǒng)第一次習(xí)題課

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

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

3、的互斥鎖mutex加以保護(hù)。加以保護(hù)。4.形成最終代碼形成最終代碼Tips：對信號量的使用一定要成對對信號量的使用一定要成對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è)置信號量如下設(shè)置信號量如下eastTowest：begin P(EW); P(WE); P(east); 從東岸經(jīng)東段橋，走到橋中央； V(east); 通過橋中央或者休息； P(west); 經(jīng)西段橋，從橋中央到西岸； V(west); V(WE); V(EW); end;沒有必要同時(shí)定義EW和WE。westToeast：begin P(EW); P(WE); P(west); 從西岸經(jīng)西段橋，走到橋中央； V(west); 通過橋中央或者休息； P(east); 經(jīng)東段橋，從橋中央到東岸

5、； V(east); V(WE); V(EW); end; 3.把學(xué)生和監(jiān)考老師都看作進(jìn)程把學(xué)生和監(jiān)考老師都看作進(jìn)程, 學(xué)生有學(xué)生有N人人, 教師教師1人人. 考場門口每次只能進(jìn)出一個(gè)人考場門口每次只能進(jìn)出一個(gè)人, 進(jìn)考場原則是先來先進(jìn)進(jìn)考場原則是先來先進(jìn). 當(dāng)當(dāng)N個(gè)學(xué)生都進(jìn)入考場后個(gè)學(xué)生都進(jìn)入考場后, 教師才能發(fā)卷子教師才能發(fā)卷子. 學(xué)生交卷后學(xué)生交卷后可以離開考場可以離開考場. 教師要等收上來全部卷子并封裝卷子后才教師要等收上來全部卷子并封裝卷子后才能離開考場能離開考場. 問題問題: 問共需設(shè)置幾個(gè)進(jìn)程問共需設(shè)置幾個(gè)進(jìn)程? 試用試用P、V操作解決上述問題中的同步和互斥關(guān)系操作解決上述問題中

6、的同步和互斥關(guān)系. 該題解析是錯(cuò)誤的！該題解析是錯(cuò)誤的！ 【解析】【解析】： 定義一個(gè)共享變量定義一個(gè)共享變量StudentCounter=N 定義四個(gè)信號量：定義四個(gè)信號量： Mutex=1，實(shí)現(xiàn)考場門口的互斥進(jìn)入，實(shí)現(xiàn)考場門口的互斥進(jìn)入 M1=1，實(shí)現(xiàn)對，實(shí)現(xiàn)對StudentCounter的互斥訪問；的互斥訪問； M2=1，表示學(xué)生是否到齊了，教師是否可以發(fā)，表示學(xué)生是否到齊了，教師是否可以發(fā)試卷；試卷； M3=1，表示試卷是否收齊了，教師是否可以離，表示試卷是否收齊了，教師是否可以離開開 共需設(shè)置二個(gè)進(jìn)程：學(xué)生進(jìn)程，教師進(jìn)程共需設(shè)置二個(gè)進(jìn)程：學(xué)生進(jìn)程，教師進(jìn)程學(xué)生：學(xué)生： P(mutex

7、); 進(jìn)入考場；進(jìn)入考場； V(mutex);P（M1）；）； StudentCounter：=StudentCounter -1； If StudentCounter=0 V(M2);V(M1);答題；答題；P（M1）；）； StudentCounter：=StudentCounter+1； 交試卷；交試卷； If StudentCounter=N V(M3); 離開考場；離開考場；V(M1); P(mutex); 離開考場；離開考場； V(mutex);教師：教師： P(mutex); 進(jìn)入考場；進(jìn)入考場； V(mutex); P（M2）；）； 發(fā)試卷；發(fā)試卷； 巡視考場；巡視考場； 收試

8、卷；收試卷； P（M3）；）； 離開離開考慮一個(gè)學(xué)生“一馬當(dāng)先”的情況。不應(yīng)共用一個(gè)StudentCounter 4.流水線問題流水線問題 某流水線有某流水線有4個(gè)并發(fā)工序個(gè)并發(fā)工序P1、P2、P3、P4，他們，他們執(zhí)行情況如下：執(zhí)行情況如下： P1先執(zhí)行；先執(zhí)行；P1結(jié)束后，結(jié)束后，P2，P3同時(shí)開始執(zhí)行，同時(shí)開始執(zhí)行，P2，P3都結(jié)束后，都結(jié)束后，P1才能繼續(xù)下一次執(zhí)行，同時(shí)才能繼續(xù)下一次執(zhí)行，同時(shí)P4開始執(zhí)行。試用開始執(zhí)行。試用PV操作實(shí)現(xiàn)他們之間的同步。操作實(shí)現(xiàn)他們之間的同步?！窘馕鼋馕觥浚篠A12,SB12,SA13,SB13,SB24,SB34;SemophoreSA12:=SA1

9、3:=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(SA12)P(SA13)執(zhí)行執(zhí)行P1V(SB13)V(SB12)End;(PA) 5.設(shè)在公共汽車上，司機(jī)和售票員的活動分設(shè)在公共汽車上，司機(jī)和售票員的活動分別如下：別如下： 司機(jī)的活動：啟動車輛；正常行車；到站司機(jī)的

10、活動：啟動車輛；正常行車；到站停車。停車。 售票員的活動：關(guān)車門；售票；開車門。售票員的活動：關(guān)車門；售票；開車門。 問題問題:在汽車不停地到站、停車以及行駛的在汽車不停地到站、停車以及行駛的過程中，司機(jī)和售票員之間的活動有什么同過程中，司機(jī)和售票員之間的活動有什么同步關(guān)系？步關(guān)系？ 解答：解答： 首先分析兩個(gè)進(jìn)程之間的同步關(guān)系。汽車行駛過首先分析兩個(gè)進(jìn)程之間的同步關(guān)系。汽車行駛過程中，司機(jī)活動與售票員活動之間的同步關(guān)系為：程中，司機(jī)活動與售票員活動之間的同步關(guān)系為： 售票員關(guān)車門后，向司機(jī)發(fā)開車信號售票員關(guān)車門后，向司機(jī)發(fā)開車信號 司機(jī)接到開車信號后起動車輛司機(jī)接到開車信號后起動車輛 在汽車

11、正常行駛過程中售票員售票在汽車正常行駛過程中售票員售票 到站時(shí)司機(jī)停車到站時(shí)司機(jī)停車 售票員在車停后開車門讓乘客下車售票員在車停后開車門讓乘客下車 定義兩個(gè)信號量定義兩個(gè)信號量s1：表示是否允許司機(jī)起動車輛，：表示是否允許司機(jī)起動車輛，s2：表示是否允許售票員開門。初值為：表示是否允許售票員開門。初值為0。請將以下描述這兩個(gè)活動的PV操作補(bǔ)充完整：Semaphore s1=0;Semaphore s2=0;main()cobegindriver();conductor();Coend; driver()while(1)p(s1); 啟動車輛；啟動車輛； 正常行車；正常行車； 到站停車；到站停車

12、； ； conductor()while(1)關(guān)車門；關(guān)車門； ； 售票；售票； p(s2); 開車門；開車門； 上下乘客；上下乘客；Semaphore s1=0;Semaphore s2=0;main()cobegindriver();conductor();Coend; driver()while(1)p(s1); 啟動車輛；啟動車輛； 正常行車；正常行車； 到站停車；到站停車； v(s2)； conductor()while(1)關(guān)車門；關(guān)車門；v（s1） ； 售票；售票； p(s2); 開車門；開車門； 上下乘客；上下乘客；CPU調(diào)度習(xí)題（1）一個(gè)具有一個(gè)具有兩道兩道作業(yè)的批處理系統(tǒng)，

13、作業(yè)調(diào)度采用作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)短作業(yè)優(yōu)先的調(diào)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的度算法，進(jìn)程調(diào)度采用以優(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)先級越高）。要求：優(yōu)先級越高）。要求：（1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間）列出所有作業(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

14、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)行運(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ì)列上已等待在

15、就緒隊(duì)列上已等待了了30分鐘分鐘,A的優(yōu)先級高于的優(yōu)先級高于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運(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í)間

16、為: 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í)間見下表們的提交時(shí)間和運(yùn)行時(shí)間見下表作業(yè)號作業(yè)號 提交時(shí)間提交時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 JOB1JOB2JOB3JOB4JOB5JOB68: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)先次

17、序。入運(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)度采用可搶占的短作業(yè)優(yōu)先調(diào)度原則8：00 J1到達(dá)，無競爭者，進(jìn)入內(nèi)存。到達(dá)，無競爭者，進(jìn)入內(nèi)存。8：20 J1運(yùn)行運(yùn)行20分鐘，剩余分鐘，剩余40分鐘；分鐘；J2到達(dá)，運(yùn)行時(shí)間為到達(dá)，運(yùn)行時(shí)間為35分鐘，分鐘，小于小于J1

18、， 取代取代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è)，因此，存已經(jīng)有四道作業(yè)，因此，J5不可進(jìn)入內(nèi)存，不可進(jìn)入內(nèi)存，J3繼續(xù)運(yùn)行。繼續(xù)運(yùn)行。08：40 J3剩余剩余5分鐘；分鐘；J6到達(dá)，同理不可以進(jìn)入內(nèi)存，到達(dá)，同理不可以進(jìn)入內(nèi)存，J3繼繼續(xù)運(yùn)行。續(xù)運(yùn)行。08：45 J3運(yùn)行結(jié)束，離開主存。運(yùn)行結(jié)束，離開主存。J5最短，進(jìn)入內(nèi)存。最短，進(jìn)入內(nèi)存。08：50 J5結(jié)束，離開。結(jié)束，離開。J6進(jìn)入，運(yùn)行時(shí)間為進(jìn)入，運(yùn)行時(shí)間為10分鐘，為最短，分鐘，為最短，開始運(yùn)行。開始運(yùn)行。09：00 J6結(jié)束，離開。結(jié)束，離開。J1剩余剩余40分鐘，分鐘，J2剩余剩余30分鐘，分鐘，J4剩余剩余25分鐘，分鐘，J4最短，開始運(yùn)行。最短，開始運(yùn)行。09：25 J4結(jié)束，離開。結(jié)束，離開