单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,操作系统作业（一）,作业,#1,进程切换时需要保存哪些现场信息？请尽量考虑完全。,答案：进程切换过程是进程上下文的切换过程，进程上下文是指进程运行的物理环境。包括地址映寄存器、通用寄存器、浮点寄存器、SP、PSW(程序状态字)、PC(指令计数器)、以及打开文件表,等,。,2.由核心返回目态程序时，进程的PSW和PC为何必须用一条机器指令同时恢复？,答案：中断向量中程序状态字PSW和指令计数器PC的内容必须由一条指令同时恢复，这样才能保证系统状态由管态转到目态的同时，控制转到上升进程的断点处继续执行。,如果不同时恢复，则只能,1.,先恢复PSW再恢复PC，在恢复PSW后已经转到目态，操作系统恢复PC的使命无法完成,2.,先恢复PC再恢复PSW，PC改变后转到操作系统另外区域（因为PSW仍在系统状态），PSW无法恢复,作业#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,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 fooled 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)并发执行，P(0)先推进，当P(0)执行到while blocked1-id 时不满足条件跳出循环在（1）处让出处理机P(1)推进，P(1),执行,while turnid 而进入临界区后让出处理机，P(0),继续也进入临界区，不满足正确性。,作业#,3,关于读者写者问题改进算法,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);,写者优先算法,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(w,ritecount,=,1,)p(,rsem,)4,readcount+,v(,y,),if(r,eadcount,=,1,)p(,wsem,),p(,wsem,),5,v(x),v(,rsem,)3 v(,wsem,),v(,z,),p(,y,),w,ritecount-,p(x),if(w,ritecount,=0),r,eadcount-,v(,rsem,),6,if(r,eadcount,=0)v(,wsem,)7,v(y),v(x),作业#,4,设系统有,5,台类型相同的打印机，依次编号为,1-5,。又设系统有,n,个使用打印机的进程，使用前申请，使用后释放。每个进程都有一个进程标识，用于区分不同的进程。每个进程有一个优先数，不同进程的优先数各异。当有多个进程同时申请打印机时，按照进程优先数由高到低的次序实施分配。试用信号量和,PV,操作实现对打印机资源的管理，即要求编写如下函数和过程。,（,1,）函数,require(pid,pri),：申请一台打印机。参数,pid,为进程标识，其值为,1-n,之间的一个整数；,pri,为进程优先数，其值为正整数。函数返回值为所申请到的打印机的编号，其值为,1-5,的一个整数。,（,2,）过程,return(prnt),：释放一台打印机。参数,prnt,为所释放的打印机的编号，其值为,1-5,的一个整数。,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);,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,管程实现SCAN算法,Procedure upscan;,Var I:0.200;,Begin,I:=headpos;,flag:=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,upscan,End,End;,Hansen,管程中,signal,操作在唤醒条件,队列的一个进程后执行此操作的进程离开管程，在本例中,signal,操作在,release,中的,upscan,和,downscan,中,执行。如下：,Procedure release,Begin,If direction=up Then,Begin,upscan;downscan,End,Else,Begin,downscan;upscan,End,End;,当在,upscan,或,downscan,中执行,signal,操作时，进程就离开了管城即结束了,release,，不会去执行,upscan,或,downscan,后面的,downscan,或,upscan,。,但是在,Hoare,管程中当进程执行,signal,操作时，不仅会唤醒条件队列中的一个进程，同时执行此操作的进程并不离开管程而是在管程中的紧急队列排队，若还沿用,Hanson,管程的代码会出现以下情况。,若进程在,upscan,中执行,signal,操作后进入紧急队列，当进程在紧急队列被唤醒后就会继续执行,release,中的后续代码即执行,downscan,，这不符合程序的语义，一个进程一次只能释放一个资源同时也就只能唤醒一个进程，若进程继续执行,downscan,会执行下一个唤醒动作。,读者/写者问题（写者优先）,1.用Ada,语言中的会合解决读者,/,写者问题，要求写者优先。即编写一个任务，其中有如下四个入口：,start_read;finish_read,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;,读者,-,写者问题,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=,accept,finish_write,do,write_count:=write_count-1;,end,finish_write;,end,select,End,loop,;,End,readers_writers,读者,-,写者问题,读者活动,:,Readers_writes.start_read;,读操作,Readers_writers.finish_read;,写者活动,:,Readers_writers.start_write;,写操作,Readers_writers.finish_write;,