吉林大學操作系統(tǒng)課件 作業(yè)1

1、操作系統(tǒng)作業(yè)（一） 作業(yè)作業(yè) #1 1. 進程切換時需要保存哪些現(xiàn)場信息？請盡量考慮進程切換時需要保存哪些現(xiàn)場信息？請盡量考慮 完全。完全。 答案：進程切換過程是進程上下文的切換過程，進答案：進程切換過程是進程上下文的切換過程，進 程上下文是指進程運行的物理環(huán)境。包括地址映寄程上下文是指進程運行的物理環(huán)境。包括地址映寄 存器、通用寄存器、浮點寄存器、存器、通用寄存器、浮點寄存器、SP、PSW(程序程序 狀態(tài)字狀態(tài)字)、PC(指令計數(shù)器指令計數(shù)器)、以及打開文件表等。、以及打開文件表等。 2. 由核心返回目態(tài)程序時，進程的由核心返回目態(tài)程序時，進程的PSW和和PC為何必為何必 須用一條機器指令同

2、時恢復？須用一條機器指令同時恢復？ 答案：中斷向量中程序狀態(tài)字答案：中斷向量中程序狀態(tài)字PSW和指令計數(shù)器和指令計數(shù)器 PC的內(nèi)容必須由一條指令同時恢復，這樣才能保的內(nèi)容必須由一條指令同時恢復，這樣才能保 證系統(tǒng)狀態(tài)由管態(tài)轉(zhuǎn)到目態(tài)的同時，控制轉(zhuǎn)到上證系統(tǒng)狀態(tài)由管態(tài)轉(zhuǎn)到目態(tài)的同時，控制轉(zhuǎn)到上 升進程的斷點處繼續(xù)執(zhí)行。升進程的斷點處繼續(xù)執(zhí)行。 如果不同時恢復，則只能如果不同時恢復，則只能 1.先恢復先恢復PSW再恢復再恢復PC，在恢復，在恢復PSW后已經(jīng)轉(zhuǎn)到目態(tài)，后已經(jīng)轉(zhuǎn)到目態(tài)， 操作系統(tǒng)恢復操作系統(tǒng)恢復PC的使命無法完成的使命無法完成 2.先恢復先恢復PC再恢復再恢復PSW，PC改變后轉(zhuǎn)到操作系

3、統(tǒng)另外區(qū)改變后轉(zhuǎn)到操作系統(tǒng)另外區(qū) 域（因為域（因為PSW仍在系統(tǒng)狀態(tài)），仍在系統(tǒng)狀態(tài)），PSW無法恢復無法恢復 作業(yè)作業(yè) #2 Consider the following program: var blocked: array0.1of boolean; turn:0.1; procedure P(id:integer); begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing turn:=id end; blockedid:=false; until false end; begin

4、blocked0:=false; blocked1:=false; turn:=0; parbegin P(0); P(1) parend; end. This is a software solution to the mutual exclusion problem proposed by Hyman. Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was foole

5、d on this one. begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing （1） turn:=id end; 若若turn=1， blocked0:=true， blocked1:= false ， P(0), P(1)并發(fā)執(zhí)行，并發(fā)執(zhí)行， P(0)先推進，當先推進，當P(0)執(zhí)行到執(zhí)行到while blocked1-id 時不滿足條件跳出循環(huán)在（時不滿足條件跳出循環(huán)在（1）處讓出處理）處讓出處理 機機P(1)推進，推進， P(1)執(zhí)行執(zhí)行while turnid 而進入臨界區(qū)

6、后讓而進入臨界區(qū)后讓 出處理機，出處理機， P(0), 繼續(xù)也進入臨界區(qū)，不滿足正確性。繼續(xù)也進入臨界區(qū)，不滿足正確性。 作業(yè)作業(yè) #3 關(guān)于讀者寫者問題改進算法 semaphore r_w_w ,mutex ,s=1; int count=0; 寫者活動： P(s); P(r_w_w); 寫操作； V(r_w_w); V(s); 讀者活動： P(s); P(mutex); count+; if (count=1) p(r_w_w); V(mutex); V(s); 讀操作； P(mutex); count-; if (count=0) v(r_w_w); V(mutex); 寫者優(yōu)先寫者優(yōu)先

7、算法算法 int readcount ,writecount =0; semaphore rsem, wsem =1; Semaphore x ,y , z =1; Reader: writer: p(z) 1 p(y) p(rsem) 2 writecount+ p(x) if(writecount=1)p(rsem) 4 readcount+ v(y) if(readcount=1) p(wsem) p(wsem) 5 v(x) v(rsem) 3 v(wsem) v(z) p(y) writecount- p(x) if(writecount=0) readcount- v(rsem)

8、6 if(readcount=0) v(wsem) 7 v(y) v(x) 作業(yè)作業(yè) #4 設(shè)系統(tǒng)有5臺類型相同的打印機，依次編號為 1-5。又設(shè)系統(tǒng)有n個使用打印機的進程，使用 前申請，使用后釋放。每個進程都有一個進程 標識，用于區(qū)分不同的進程。每個進程有一個 優(yōu)先數(shù)，不同進程的優(yōu)先數(shù)各異。當有多個進 程同時申請打印機時，按照進程優(yōu)先數(shù)由高到 低的次序?qū)嵤┓峙?。試用信號量和PV操作實現(xiàn) 對打印機資源的管理，即要求編寫如下函數(shù)和 過程。 （1）函數(shù)require(pid,pri)：申請一臺打印 機。參數(shù)pid為進程標識，其值為1-n之間 的一個整數(shù)；pri為進程優(yōu)先數(shù)，其值為 正整數(shù)。函數(shù)返回

9、值為所申請到的打印 機的編號，其值為1-5的一個整數(shù)。 （2）過程return(prnt)：釋放一臺打印機。 參數(shù)prnt為所釋放的打印機的編號，其值 為1-5的一個整數(shù)。 int lp5; (initial value is 1) int count=5; int pN ;(initial value is -1) semaphore qN; (initial value is 0) semaphore mutex=1; int require(int pid,int pri); p(mutex); L: if (count=0) pripid=pri; v(mutex) P(qpid);

10、goto L; count-; int i; for( i=0; i5;i+) if (lpi!=0) lpi=0; return(i); V(mutex); int return(int prnt) P(mutex); lpprnt=1; count+; int max , i , j; max=-1; for ( j=0;jmax) max=pj; i=j; if (max=-1) V(mutex); else pi=-1; v(qi; 2.Hoare管程實現(xiàn)管程實現(xiàn)SCAN算法算法 Procedure upscan; Var I:0.200; Begin I:=headpos; flag

11、:=true; While (I=199)and(countI=0) Do I:=I+1; If I=0)and(countI=0) Do I:=I-1; If I=0 Then Begin countI:=countI-1; signal(cylinderI) flag=false ; End End; Procedure release; Begin busy:=false; If direction=up Then Begin upscan; if flag=true then downscan End Else Begin downscan; if flag=true then ups

12、can End End; Hansen管程中signal操作在喚醒條件隊列的一個進程后執(zhí) 行此操作的進程離開管程，在本例中signal操作在 release中的upscan和和downscan中中執(zhí)行。如下： Procedure release Begin If direction=up Then Begin upscan; downscan End Else Begin downscan; upscan End End; 當在當在upscan或或downscan中執(zhí)行中執(zhí)行signal操作操作 時，進程就離開了管城即結(jié)束了時，進程就離開了管城即結(jié)束了release， 不會去執(zhí)行不會去執(zhí)行up

13、scan或或downscan后面的后面的 downscan 或或upscan。 但是在但是在Hoare管程中當進程執(zhí)行管程中當進程執(zhí)行signal操作操作 時，不僅會喚醒條件隊列中的一個進程，同時，不僅會喚醒條件隊列中的一個進程，同 時執(zhí)行此操作的進程并不離開管程而是在管時執(zhí)行此操作的進程并不離開管程而是在管 程中的緊急隊列排隊，若還沿用程中的緊急隊列排隊，若還沿用Hanson管管 程的代碼會出現(xiàn)以下情況。程的代碼會出現(xiàn)以下情況。 若進程在若進程在upscan中執(zhí)行中執(zhí)行signal操作后進入緊急隊列，操作后進入緊急隊列， 當進程在緊急隊列被喚醒后就會繼續(xù)執(zhí)行當進程在緊急隊列被喚醒后就會繼續(xù)執(zhí)

14、行release中中 的后續(xù)代碼即執(zhí)行的后續(xù)代碼即執(zhí)行downscan，這不符合程序的語，這不符合程序的語 義，一個進程一次只能釋放一個資源同時也就只能義，一個進程一次只能釋放一個資源同時也就只能 喚醒一個進程，若進程繼續(xù)執(zhí)行喚醒一個進程，若進程繼續(xù)執(zhí)行downscan會執(zhí)行會執(zhí)行 下一個喚醒動作。下一個喚醒動作。 讀者讀者/寫者問題（寫者優(yōu)先）寫者問題（寫者優(yōu)先） 1. 用用Ada語言中的會合解決讀者語言中的會合解決讀者/寫者問題，要求寫者問題，要求 寫者優(yōu)先。即編寫一個任務，其中有如下四個入寫者優(yōu)先。即編寫一個任務，其中有如下四個入 口：口： start_read; finish_read

15、, start_write, finish_write. 提示：可以使用嵌套的提示：可以使用嵌套的accept語句。語句。 讀者讀者-寫者問題寫者問題 Task readers_writers is entry start_read; entry finish_read; entry start_write; entry finish_write; End readers_writes; Task body readers_writers is; Var read_count, write_count: integer; begin read_count:=0; write_count:=0;

16、 讀者讀者-寫者問題寫者問題 Loop select when write_count=0 = accept start_read do read_count := read_count+1; end start_read or when read_count0 = accept finish_read do read_count := read_count-1; end finish_read; or 讀者讀者-寫者問題寫者問題 when write_count=0 = accept start_write do while read_count 0 do accept finish_read do read_count:= read_count -1; end finish_read end while end start_write; write_count:=write_count+1; or when write_count0 =