作业讲解总ppt课件.ppt

作业讲解（总）,1,第二章,知识点信号量：记录型信号量P51记录型结构，包括两个数据项：typesemaphore=recordvalue:integer;L:listofprocess;end,2,第二章,假设定义了一个信号量SS.value为资源信号量，其初值为某类资源的数目。S.value=0，代表系统当中可用资源的数目。S.value0表示还可以执行wait（s）而不会阻塞的进程数（可用资源数）。每执行一次wait（s）操作，就意味着请求分配一个单位的资源。当s.value=0时，表示已无资源可用，因此请求该资源的进程被阻塞。此时，s.value的绝对值等于该信号量阻塞队列中的等待进程数。执行一次signal操作，就意味着释放一个单位的资源。若s.value=0，表示s.L队列中还有被阻塞的进程，需要唤醒该队列中的第一个进程，将它转移到就绪队列中。s.value的值被初始化为1时：表示只允许一个进程访问临界资源，是互斥信号量。,6,第二章,S作为互斥信号量时，s.value的取值范围当仅有两个并发进程共享临界资源时，互斥信号量仅能取值0、1、1。其中，s.value=1,表示无进程进入临界区s.value=0,表示已有一个进程进入临界区s.value=1,表示已有一个进程正在等待进入临界区当用s来实现n个进程的互斥时，s.value的取值范围为1（n1）。,7,第二章,24.在生产者消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换位置；或者是将signal(mutex)与signal(full)互换位置结果会如何?解答：生产者消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换，会引起死锁。signal(mutex)与signal(full)互换位置不会引起死锁，只是会使临界资源的释放略为推迟一些。,8,第二章,27.试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法.算法一：至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。,9,第二章,解法一：设置一个信号量Sm来限制同时进餐的哲学家数目，使它不超过4，故Sm初始值设为4。这样，第i个哲学家的活动描述为：varchopstickarray0,4ofsemaphore:=(1,1,1,1,1)varSm:semaphore:=4;processirepeatwait(Sm);wait(chopsticki);wait(chopstick(i+1)mod5);eat;signal(chopsticki);signal(chopstick(i+1)mod5);signal(Sm);thinkuntilfalse;,10,第二章,算法二：规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。,11,第二章,varchopstickarray0,4ofsemaphore:=(1,1,1,1,1)Processirepeatifimod2=1thenwait(chopsticki);wait(chopstick(i+1)mod5);eat;signal(chopsticki);signal(chopstick(i+1)mod5);,elsewait(chopstick(i+1)mod5);wait(chopsticki);eat;signal(chopstick(i+1)mod5);signal(chopsticki);untilfalse,12,第二章,总结利用信号量实现互斥时，初始值为1。用于表示某种资源时，则为资源数目。利用信号量实现前后的前趋关系时，初始值为0。如P55,13,第三章,知识点调度算法银行家算法资源分配图,14,第三章,调度算法P9195FCFS：先来先服务调度算法。SJF：短作业优先调度算法。RR：时间片轮转调度算法。概念周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。带权周转时间：W=T/TsT：作业的周转时间Ts：系统为它提供服务的时间,15,补充作业,假定有如下作业：,请用FCFS、SJF、RR(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。,16,补充作业1,FCF和SPF的计算结果如下,17,补充作业1,时间片轮转调度算法，执行图如下：,BCA,18,第三章,银行家算法P109如果RequestijNeedi,j，【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。如果RequestijAvailablej【请求小于库存】,便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。3.系统试探着把资源分配给进程Pi【试分配】，并修改下面数据结构中的数值：【库存】Availablej:=Availablej-Requestij;【获取】Allocationi,j:=Allocationi,j+Requestij;【需求】Needi,j:=Needi,j-Requestij4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,19,第三章,安全性检测算法(1)Workj:=Availablej;Finishi:=false;(2)寻找满足下列条件的i：a).Finishi=false;b).Needi,jWorkj如果不存在，则转(4)(3)进程i获取资源，然后执行完毕，并释放资源：Workj:=Workj+Allocationi,j;Finishi:=true;转(2)(4)若对所有进程的Finishi=true,则系统处于安全状态，否则处于不安全状态。,20,第三章,20.在银行家算法中，若出现下述资源分配情况：,21,第三章,1）该状态是否安全？,安全，因为存在安全序列,22,第三章,2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？Request(1,2,2,2)=Need(2,3,5,6)Request(1,2,2,2)=Available(1,6,2,2)试分配后系统资源情况如下：,此状态不安全，因此不能分配。,23,第三章,资源分配图概念二元组G=（V，E）V：结点集，分为P，R两部分P=p1,p2,pnR=r1,r2,rmE：边的集合，其元素为有序二元组(pi,rj)或(rj,pi),24,第三章,资源分配图的化简P112（1）在图中，找出一个既不阻塞又非独立的进程结点Pi，消去Pi所有的请求边和分配边，使之成为孤立结点。意义：进程Pi可获得所需资源并运行完毕，然后释放占有的所有资源。（2）循环执行（1）意义：下一个进程在前面的进程释放资源后，可获得资源并执行完毕，然后又释放占有的全部资源。（3）重复执行，直到所有进程节点都成为孤立结点，则该图是可化简的；否则，存在环，该图是不可化简的。,25,补充作业2,判断如下资源分配图中，是否存在死锁？,独立点,阻塞点,26,补充作业2,判断如下资源分配图中，是否存在死锁？,27,第四章,知识点基本分页式存储管理：地址映射P132基本分段式存储管理：地址映射P138请求分页式存储管理：页面置换算法P150,28,第四章,基本分页式存储管理：地址映射P132,29,第四章作业1：,在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下：试借助地址变换图求出有效逻辑地址4865所对应的物理地址。,30,解答,31,第四章作业3,对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成物理地址。,32,第四章,基本分段式存储管理：地址映射P138,33,4,Cb,+,0137,比较,5*1024+137,段表,04,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,b,1375K,比较,51337,34,4,Cb,+,14000,比较,段表,04,地址越界,段表始址寄存器,段表长度寄存器,逻辑地址,b,40003K,比较,35,4,Cb,4230,44,段表始址寄存器,段表长度寄存器,逻辑地址,地址越界,比较,36,第四章,请求分页式存储管理：页面置换算法P150153LRU：最近最久未使用置换算法CLOCKOPT：最佳页面置换算法,37,第四章作业2：P159页26题,某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU（最近最久未使用）、Clock、OPT算法分别计算缺页次数假设开始时所有页均不在内存,38,LRU432143543215块1块2块3块4xxxxxxxx共缺页中断8次,LRU,39,Clock432143543215块1块2块3块4xxxxxxxxxx共缺页中断10次,Clock,40,OPT432143543215块1块2块3块4xxxxxx共缺页中断6次,OPT,41,第四章作业4,某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3653，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制，而内存中尚未装入任何页。请给出使用LRU算法时的缺页次数。解答：页块数为3，页号分别为0（01023），1（10242047），2（20483071），3（30714095），则引用内存单元对应的页号为：3、3、1、3、2、3、0、2、1、2、3、0、1、1。,42,第五章,知识点磁盘调度算法P194FCFS：先来先服务SSTF：最短寻道时间优先SCAN：扫描算法,43,第五章作业,假定：当有9个磁盘读写请求；这9个磁盘读写请求访问的磁道号按照各个磁盘读写请求到达的次序依次为：55、58、39、18、19、160、150、38、184。磁头当前位于100号磁道上。如果系统采用SCAN算法，还假定磁头当前的移动方向为磁道号增长方向。请问：如果系统分别采用FIFO、SSTF、SCAN算法调度磁盘，那么系统处理这9个磁盘读写请求时磁头的平均寻道长度为多少？,44,FIFS,45,SSTF算法,46,SCAN算法,47,第六章,有一个计算机系统利用图1所示的位示图来管理空闲盘块现在要为某文件分配两个盘块，试说明盘块分配过程？,48,第六章,知识点文件存储空间管理：位示图P232盘块的分配(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3)修改位示图，令mapi,j=1。位示图大小计算：磁盘容量/(8数据块大小)（字节数）,49,盘块的分配顺序扫描位示图，从中找到第一个值为0的二进制位，得到其行号i=3，列号j=3。将所找到的二进制位转换成与之对应的盘