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

作业讲解（24）,1,知识点,进程互斥和同步的控制信号量机制信号量是一种数据结构信号量的值与相应资源的使用情况有关信号量的值仅由P、V操作改变,2,知识点,记录型信号量记录型结构，包括两个数据项：typesemaphore=recordvalue:integer;L:listofprocess;end,3,知识点,假设定义了一个信号量SS.value为资源信号量，其初值为某类资源的数目。S.value=0，代表系统当中可用资源的数目。S.value0,其绝对值代表等待使用资源的进程个数。S.L是一个阻塞队列，进程无法申请到资源则进入此队列。,4,知识点,定义对信号量的两个原子操作：wait(s)和signal（s）,procedurewait(S)varS:semaphore;beginS.value:=S.value-1;ifS.value0thenblock(S.L)/进程阻塞，即进入S.L链表；end,5,知识点,定义对信号量的两个原子操作：wait(s)和signal（s）,proceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value0thenwakeup(S.L);/唤醒阻塞队列首进程,将进程从/S.L阻塞队列中移出；end,6,第二章,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;parendend,7,第二章,26.参看教材P58-59,8,第二章,3、设公共汽车上有一个司机和一个售票员，其活动如图3所示。为了安全起见，显然要求:(1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。试用记录型信号量实现司机与售票员之间的同步，并说明各信号量的含义。,9,用记录型信号量解决这一问题，需要定义两个信号量：Start：表示是否允许司机启动车辆，初值为0；Open：表示是否允许售票员开车门，初值为0。,semaphorestart=0;semaphoreopen=0;,售票员的活动:beginrepeat关车门;Signal(start);售票;Wait(open);开车门;untilfalseend,司机的活动:beginrepeatWait(start);启动车辆;正常行车;到站停车;Signal(open);untilfalseend,10,第二章,知识点进程调度算法避免死锁银行家算法,11,进程调度算法,先来先服务FCFS短作业优先调度算法时间片轮转调度算法概念周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。带权周转时间：周转时间/系统为它提供服务的时间,12,第三章,1、假定有如下作业：,请用FCFS、SJF、RR(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。,13,第三章,FCF和SPF的计算结果如下,14,第三章,时间片轮转调度算法，执行图如下：,BCA,15,银行家算法,用于避免死锁。基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。安全状态：是指系统能按某种进程顺序，如,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称序列为安全序列。若系统存在安全序列，则系统当前为安全状态。,16,银行家算法描述,设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果RequestijNeedi,j，【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。如果RequestijAvailablej【请求小于库存】,便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。,17,银行家算法描述,3.系统试探着把资源分配给进程Pi【试分配】，并修改下面数据结构中的数值：【库存】Availablej:=Availablej-Requestij;【获取】Allocationi,j:=Allocationi,j+Requestij;【需求】Needi,j:=Needi,j-Requestij4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,18,第三章,2.在银行家算法中，若出现下述资源分配情况：P115第22题,19,第三章,1）该状态是否安全？,安全，因为存在安全序列,20,第三章,2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？分配后系统资源情况如下：,此状态不安全，因此不能分配。,21,第四章,知识点基本分页式存储管理地址映射过程基本分段式存储管理地址映射过程页面置换算法,22,基本分页式存储管理地址映射过程,23,第四章,1、在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下：试借助地址变换图求出有效逻辑地址4865所对应的物理地址。,24,解答,25,基本分段式存储管理地址映射过程,段地址变换由硬件地址变换机构完成。,26,第四章作业3,3、对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成物理地址。,27,4,Cb,+,0137,比较,5*1024+137,段表,04,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,b,1375K,比较,51337,28,4,Cb,+,14000,比较,段表,04,地址越界,段表始址寄存器,段表长度寄存器,逻辑地址,b,40003K,比较,29,4,Cb,4230,44,段表始址寄存器,段表长度寄存器,逻辑地址,地址越界,比较,30,页面置换算法,在请求分页式存储管理中，当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。,31,页面置换算法分类,最佳页面算法（OPT）先进先出页面置换算法（FIFO）最近最久未使用页面置换算法（LRU）轮转算法（Clock）,32,第四章作业2：P143页23题,2、某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、Clock、OPT算法分别计算缺页次数假设开始时所有页均不在内存,33,LRU432143543215块1块2块3块4xxxxxxxx共缺页中断8次,LRU,34,Clock432143543215块1块2块3块4xxxxxxxxxx共缺页中断10次,Clock,35,OPT432143543215块1块2块3块4xxxxxx共缺页中断6次,OPT,36,第四章作业4,4、某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3653，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制，而内存中尚未装