西安电子科技大学 操作系统 考试重点作业讲解(2～4)

作业讲解（2～4）知识点进程互斥和同步的控制–信号量机制•信号量是一种数据结构•信号量的值与相应资源的使用情况有关•信号量的值仅由P、V操作改变知识点记录型信号量记录型结构，包括两个数据项：typesemaphore=recordvalue:integer;L:listofprocess;end知识点假设定义了一个信号量SS.value为资源信号量，其初值为某类资源的数目。–S.value=0，代表系统当中可用资源的数目。–S.value0,其绝对值代表等待使用资源的进程个数。S.L是一个阻塞队列，进程无法申请到资源则进入此队列。知识点定义对信号量的两个原子操作：wait(s)和signal（s）procedurewait(S)varS:semaphore;beginS.value:=S.value-1;ifS.value＜0thenblock(S.L)//进程阻塞，即进入S.L链表；end知识点定义对信号量的两个原子操作：wait(s)和signal（s）proceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S.L);//唤醒阻塞队列首进程,将进程从//S.L阻塞队列中移出；end第二章22、试写出相应的程序来描述图2-17所示的前趋图。P8222(a)Vara,b,c,d,e,f,g,h;semaphore:=0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);S6;signal(h);end;beginwait(f);wait(g);wait(h);S7;end;parendendS1S2S3S4S5S6S7abcdefgh第二章26.参看教材P58-59第二章3、设公共汽车上有一个司机和一个售票员，其活动如图3所示。为了安全起见，显然要求:(1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。试用记录型信号量实现司机与售票员之间的同步，并说明各信号量的含义。用记录型信号量解决这一问题，需要定义两个信号量：Start：表示是否允许司机启动车辆，初值为0；Open：表示是否允许售票员开车门，初值为0。semaphorestart=0;semaphoreopen=0;售票员的活动:beginrepeat关车门;Signal(start);售票;Wait(open);开车门;untilfalseend司机的活动:beginrepeatWait(start);启动车辆;正常行车;到站停车;Signal(open);untilfalseend第二章知识点–进程调度算法–避免死锁——银行家算法进程调度算法先来先服务FCFS短作业优先调度算法时间片轮转调度算法概念–周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。–带权周转时间：周转时间/系统为它提供服务的时间第三章1、假定有如下作业：进程名ABCDE到达时间01234服务时间64325请用FCFS、SJF、RR(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。第三章进程名ABCDE平均到达时间01234作业情况调度算法服务时间64325完成时间610131520周转时间6911121610.8FCFS带权周转时间12.253.6763.23.2完成时间61511820周转时间614951610SPF带权周转时间13.532.53.22.64FCF和SPF的计算结果如下第三章时间片轮转调度算法，执行图如下：q=21234567891011121314151617t181920ABCDEABCAE进程名ABCDE平均到达时间01234服务时间64325RR完成时间1714151020周转时间17131371613.2带权周转时间2.833.254.33.53.23.42BCA银行家算法用于避免死锁。基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。安全状态：–是指系统能按某种进程顺序，如P1,P2,…,Pn,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称P1,P2,…,Pn序列为安全序列。–若系统存在安全序列，则系统当前为安全状态。银行家算法描述设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：1.如果Requesti［j］≤Need［i,j］，【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。2.如果Requesti［j］≤Available［j］【请求小于库存】,便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。银行家算法描述3.系统试探着把资源分配给进程Pi【试分配】，并修改下面数据结构中的数值：【库存】Available[j]:=Available[j]-Requesti[j];【获取】Allocation[i,j]:=Allocation[i,j]+Requesti[j];【需求】Need[i,j]:=Need[i,j]-Requesti[j]4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。第三章2.在银行家算法中，若出现下述资源分配情况：P115第22题ProcesesAllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656第三章1）该状态是否安全？ProcesesAllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656ProcesesWorkNeedAllocationWork+AllocationFinishP01622001200321654trueP31654065203321986trueP11986175010002986trueP22986235613544340trueP44340065600143354true安全，因为存在安全序列p0,p3,p1,p2,p4第三章2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？分配后系统资源情况如下：ProcesesAllocationNeedAvailableP0003200120400P110001750P225762356P303320652P400140656此状态不安全，因此不能分配。第四章知识点–基本分页式存储管理地址映射过程–基本分段式存储管理地址映射过程–页面置换算法页表寄存器页表始址页表长度＞页号页内地址＋逻辑地址L越界中断1块号b页表页号012物理地址3基本分页式存储管理地址映射过程第四章1、在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下：试借助地址变换图求出有效逻辑地址4865所对应的物理地址。页号块号02142638解答41836220块号页号01100000001000100110000000100111页表首址+010物理地址为：13057基本分段式存储管理地址映射过程段地址变换由硬件地址变换机构完成。控制寄存器段表始址段表长度＞2100＋段号S越界1K段长600段号01236K4K5002008K9200基址位移量W＋82928K82928692主存物理地址有效地址第四章作业33、对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成物理地址。段号内存始址段长050K10K160K3K270K5K3120K8K4Cb+0137比较5*1024+137段表04物理地址段表始址寄存器段表长度寄存器逻辑地址b1375K比较段号内存始址段长050K10K160K3K270K5K3120K8K513374Cb+14000比较段表04地址越界段表始址寄存器段表长度寄存器逻辑地址b40003K比较段号内存始址段长050K10K160K3K270K5K3120K8K4Cb423044段表始址寄存器段表长度寄存器逻辑地址地址越界比较页面置换算法在请求分页式存储管理中，当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。页面置换算法分类最佳页面算法（OPT）先进先出页面置换算法（FIFO）最近最久未使用页面置换算法（LRU）轮转算法（Clock）第四章作业2：P143页23题2、某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、Clock、OPT算法分别计算缺页次数假设开始时所有页均不在内存LRU432143543215块1块2块3块4xxxxxxxx共缺页中断8次LRU443432432143214321435143514351435243125312Clock432143543215块1块2块3块4xxxxxxxxxx共缺页中断10次Clock443432432143214321532154215431543214321532OPT432143543215块1块2块3块4xxxxxx共缺页中断6次OPT443432432143214321432543254325432513251325第四章作业44、某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3653，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制，而内存中尚未装入任何页。请给出使用LRU算法时的缺页次数。解答：页块数为3，页号分别为0（0～1023），1（1024～2047），2（2048～3071），3（3071～4095），则引用内存单元对应的页号为：3、3、1、3、2、3、0、2、1、2、3、0、1、1。LRU33132302123011块1块2块3LRU333131312312302302102102132032031031xxxxxxxx共缺页中断8次