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

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

2.由核心返回目態(tài)程序時(shí)，進(jìn)程的PSW和PC為何必須用一條機(jī)器指令同時(shí)恢復(fù)？答案：中斷向量中程序狀態(tài)字PSW和指令計(jì)數(shù)器PC的內(nèi)容必須由一條指令同時(shí)恢復(fù)，這樣才能保證系統(tǒng)狀態(tài)由管態(tài)轉(zhuǎn)到目態(tài)的同時(shí)，控制轉(zhuǎn)到上升進(jìn)程的斷點(diǎn)處繼續(xù)執(zhí)行。如果不同時(shí)恢復(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ū)域（因?yàn)镻SW仍在系統(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)先推進(jìn)，當(dāng)P(0))執(zhí)行到whileblocked[1-id]時(shí)不滿足條件跳出循環(huán)在（1）處讓出處理機(jī)P(1)推進(jìn)，P(1)執(zhí)行whileturn<>id而進(jìn)入臨界區(qū)后讓出處理機(jī)，P(0),繼續(xù)也進(jìn)入臨界區(qū)，不滿足正確性。作業(yè)#3關(guān)于讀者寫者問題改進(jìn)算法semaphorer_w_w,mutex,s=1;intcount=0;寫者活動(dòng)：P(s);P(r_w_w);{寫操作}；V(r_w_w);V(s);讀者活動(dòng)：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臺類型相同的打印機(jī)，依次編號為1-5。又設(shè)系統(tǒng)有n個(gè)使用打印機(jī)的進(jìn)程，使用前申請，使用后釋放。每個(gè)進(jìn)程都有一個(gè)進(jìn)程標(biāo)識，用于區(qū)分不同的進(jìn)程。每個(gè)進(jìn)程有一個(gè)優(yōu)先數(shù)，不同進(jìn)程的優(yōu)先數(shù)各異。當(dāng)有多個(gè)進(jìn)程同時(shí)申請打印機(jī)時(shí)，按照進(jìn)程優(yōu)先數(shù)由高到低的次序?qū)嵤┓峙?。試用信號量和PV操作實(shí)現(xiàn)對打印機(jī)資源的管理，即要求編寫如下函數(shù)和過程。（1）函數(shù)require(pid,pri)：申請一臺打印機(jī)。參數(shù)pid為進(jìn)程標(biāo)識，其值為1-n之間的一個(gè)整數(shù)；pri為進(jìn)程優(yōu)先數(shù)，其值為正整數(shù)。函數(shù)返回值為所申請到的打印機(jī)的編號，其值為1-5的一個(gè)整數(shù)。（2）過程return(prnt)：釋放一臺打印機(jī)。參數(shù)prnt為所釋放的打印機(jī)的編號，其值為1-5的一個(gè)整數(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管程實(shí)現(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操作在喚醒條件隊(duì)列的一個(gè)進(jìn)程后執(zhí)行此操作的進(jìn)程離開管程，在本例中signal操作在release中的upscan和downscan中執(zhí)行。如下：ProcedurereleaseBeginIfdirection=upThenBeginupscan;downscanEndElseBegindownscan;upscanEndEnd;當(dāng)在upscan或downscan中執(zhí)行signal操作時(shí)，進(jìn)程就離開了管城即結(jié)束了release，不會(huì)去執(zhí)行upscan或downscan后面的downscan或upscan。但是在Hoare管程中當(dāng)進(jìn)程執(zhí)行signal操作時(shí)，不僅會(huì)喚醒條件隊(duì)列中的一個(gè)進(jìn)程，同時(shí)執(zhí)行此操作的進(jìn)程并不離開管程而是在管程中的緊急隊(duì)列排隊(duì)，若還沿用Hanson管程的代碼會(huì)出現(xiàn)以下情況。若進(jìn)程在upscan中執(zhí)行signal操作后進(jìn)入緊急隊(duì)列，當(dāng)進(jìn)程在緊急隊(duì)列被喚醒后就會(huì)繼續(xù)執(zhí)行release中的后續(xù)代碼即執(zhí)行downscan，這不符合程序的語義，一個(gè)進(jìn)程一次只能釋放一個(gè)資源同時(shí)也就只能喚醒一個(gè)進(jìn)程，若進(jìn)程繼續(xù)執(zhí)行downscan會(huì)執(zhí)行下一個(gè)喚醒動(dòng)作。讀者/寫者問題（寫者優(yōu)先）1.用Ada語言中的會(huì)合解決讀者/寫者問題，要求寫者優(yōu)先。即編寫一個(gè)任務(wù)，其中有如下四個(gè)入口：

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