吉林大學(xué)操作系統(tǒng)作業(yè)解析公開課獲獎?wù)n件省賽課一等獎?wù)n件

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

2.由核心返回目態(tài)程序時，進程的PSW和PC為何必須用一條機器指令同時恢復(fù)？答案：中斷向量中程序狀態(tài)字PSW和指令計數(shù)器PC的內(nèi)容必須由一條指令同時恢復(fù)，這樣才能保證系統(tǒng)狀態(tài)由管態(tài)轉(zhuǎn)到目態(tài)的同時，控制轉(zhuǎn)到上升進程的斷點處繼續(xù)執(zhí)行。如果不同時恢復(fù)，則只能1.先恢復(fù)PSW再恢復(fù)PC，在恢復(fù)PSW后已經(jīng)轉(zhuǎn)到目態(tài)，操作系統(tǒng)恢復(fù)PC的使命無法完成2.先恢復(fù)PC再恢復(fù)PSW，PC改變后轉(zhuǎn)到操作系統(tǒng)另外區(qū)域（因為PSW仍在系統(tǒng)狀態(tài)），PSW無法恢復(fù)作業(yè)#2Considerthefollowingprogram:varblocked:array[0..1]ofboolean;turn:0..1;procedureP(id:integer);beginrepeatblocked[id]:=true;whileturn<>iddobeginwhileblocked[1-id]do{nothing}turn:=idend;<Criticalsection>blocked[id]:=false;<Remainder>untilfalseend;beginblocked[0]:=false;blocked[1]:=false;turn:=0;parbeginP(0);P(1)parend;end.ThisisasoftwaresolutiontothemutualexclusionproblemproposedbyHyman.Findacounterexampletodemonstratethatthissolutionisincorrect.ItisinterestingtonotethateventheCommunicationoftheACMwasfooledonthisone.beginrepeatblocked[id]:=true;whileturn<>iddobeginwhileblocked[1-id]do{nothing}（1）turn:=idend;<Criticalsection>若turn=1，blocked[0]:=true，blocked[1]:=false

，P(0),P(1)并發(fā)執(zhí)行，P(0)先推進，當(dāng)P(0))執(zhí)行到whileblocked[1-id]時不滿足條件跳出循環(huán)在（1）處讓出處理機P(1)推進，P(1)執(zhí)行whileturn<>id而進入臨界區(qū)后讓出處理機，P(0),繼續(xù)也進入臨界區(qū)，不滿足正確性。作業(yè)#3關(guān)于讀者寫者問題改進算法semaphorer_w_w,mutex,s=1;intcount=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)先算法intreadcount,writecount=0;semaphorersem,wsem=1;Semaphorex,y,z=1;

Reader:writer:

p(z)1

p(y)p(rsem)2writecount++p(x)

if(writecount==1)p(rsem)4readcount++v(y)

if(readcount==1)p(wsem)

p(wsem)5

v(x)

<write>v(rsem)3v(wsem)v(z)

p(y)<read>

writecount--p(x)

if(writecount==0)readcount--v(rsem)6

if(readcount==0)v(wsem)7v(y)

v(x)作業(yè)#4設(shè)系統(tǒng)有5臺類型相同的打印機，依次編號為1-5。又設(shè)系統(tǒng)有n個使用打印機的進程，使用前申請，使用后釋放。每個進程都有一個進程標識，用于區(qū)分不同的進程。每個進程有一個優(yōu)先數(shù)，不同進程的優(yōu)先數(shù)各異。當(dāng)有多個進程同時申請打印機時，按照進程優(yōu)先數(shù)由高到低的次序?qū)嵤┓峙?。試用信號量和PV操作實現(xiàn)對打印機資源的管理，即要求編寫如下函數(shù)和過程。（1）函數(shù)require(pid,pri)：申請一臺打印機。參數(shù)pid為進程標識，其值為1-n之間的一個整數(shù)；pri為進程優(yōu)先數(shù)，其值為正整數(shù)。函數(shù)返回值為所申請到的打印機的編號，其值為1-5的一個整數(shù)。（2）過程return(prnt)：釋放一臺打印機。參數(shù)prnt為所釋放的打印機的編號，其值為1-5的一個整數(shù)。intlp[5];(initialvalueis1)intcount=5;intp[N];(initialvalueis-1)semaphoreq[N];(initialvalueis0)semaphoremutex=1;intrequire(intpid,intpri);{p(mutex);L:if(count==0){pri[pid]==pri;v(mutex)P(q[pid]);gotoL;}count--;inti;for(i=0;i<5;i++)if(lp[i]!=0){lp[i]=0;return(i);}V(mutex);}}

intreturn(intprnt){P(mutex);lp[prnt]=1;count++;intmax,i,j;max=-1;for(j=0;j<N;j++)if(p[j]>max){max=p[j];i=j;}if(max==-1)V(mutex);else{p[i]=-1;v(q[i];}}2.Hoare管程實現(xiàn)SCAN算法Procedureupscan;VarI:0..200;BeginI:=headpos;

flag:=true;While(I<=199)and(count[I]=0)DoI:=I+1;IfI<=199ThenBegincount[I]:=count[I]-1;signal(cylinder[I])

flag=false;EndEnd;Proceduredownscan;VarI:-1..199;BeginI:=headpos;

flag:=true;While(I>=0)and(count[I]=0)DoI:=I-1;IfI>=0ThenBegincount[I]:=count[I]-1;signal(cylinder[I])

flag=false;EndEnd;Procedurerelease;Beginbusy:=false;Ifdirection=upThenBeginupscan;

ifflag=truethendownscanEndElseBegindownscan;

ifflag=truethen

upscanEndEnd;Hansen管程中signal操作在喚醒條件隊列的一個進程后執(zhí)行此操作的進程離開管程，在本例中signal操作在release中的upscan和downscan中執(zhí)行。如下：ProcedurereleaseBeginIfdirection=upThenBeginupscan;downscanEndElseBegindownscan;upscanEndEnd;當(dāng)在upscan或downscan中執(zhí)行signal操作時，進程就離開了管城即結(jié)束了release，不會去執(zhí)行upscan或downscan后面的downscan或upscan。但是在Hoare管程中當(dāng)進程執(zhí)行signal操作時，不僅會喚醒條件隊列中的一個進程，同時執(zhí)行此操作的進程并不離開管程而是在管程中的緊急隊列排隊，若還沿用Hanson管程的代碼會出現(xiàn)以下情況。若進程在upscan中執(zhí)行signal操作后進入緊急隊列，當(dāng)進程在緊急隊列被喚醒后就會繼續(xù)執(zhí)行release中的后續(xù)代碼即執(zhí)行downscan，這不符合程序的語義，一個進程一次只能釋放一個資源同時也就只能喚醒一個進程，若進程繼續(xù)執(zhí)行downscan會執(zhí)行下一個喚醒動作。讀者/寫者問題（寫者優(yōu)先）1.用Ada語言中的會合解決讀者/寫者問題，要求寫者優(yōu)先。即編寫一個任務(wù)，其中有如下四個入口：

start_read;finish_read,start_write,finish_write.

提示：可以使用嵌套的accept語句。讀者-寫者問題Taskreaders_writersis

entrystart_read;

entryfinish_read;

entrystart_write;

entryfinish_write;Endreaders_writes;

Task

bodyreaders_writersis;

Varread_count,write_count:integer;beginread_count:=0;write_count:=0;讀者-寫者問題

Loop

select

whenwrite_count=0=>

acceptstart_readdoread_count:=read_count+1;

endstart_read

or

whenread_count>0=>

acceptfinish_readdoread_count:=read_count-1;

endfinish_read;

or

讀者-寫者問題

whenwrite_count=0