资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,作业讲解（24）,知识点,进程互斥和同步的控制,信号量机制,信号量是一种数据结构,信号量的值与相应资源的使用情况有关,信号量的值仅由P、V操作改变,知识点,记录型信号量,记录型结构，包括两个数据项：,type semaphore=record,value:integer;,L:list of process;,end,知识点,假设定义了一个信号量S,S.value为资源信号量，其初值为某类资源的数目。,S.value=0，代表系统当中可用资源的数目。,S.value0,其绝对值代表等待使用资源的进程个数。,S.L是一个阻塞队列，进程无法申请到资源则进入此队列。,知识点,定义对信号量的两个原子操作：,wait(s)和signal（s）,procedure wait(S),var S:semaphore;,begin,S.value:=S.value-1;,if S.value0 then,block(S.L),/,进程阻塞，即进入S.L链表；,end,知识点,定义对信号量的两个原子操作：,wait(s)和signal（s）,procedure signal(S),var S:semaphore;,begin,S.value:=S.value+1;,if S.value0 then,wakeup(S.L);,/,唤醒阻塞队列首进程,将进程从,/S.L阻塞队列中移出；,end,第二章,22、试写出相应的程序来描述图2-17 所示的前趋图。P82 22(a),Var a,b,c,d,e,f,g,h;semaphore:=0,0,0,0,0,0,0,0;,begin,parbegin,begin S1;signal(a);signal(b);end;,begin wait(a);S2;signal(c);signal(d);end;,begin wait(b);S3;signal(e);end;,begin wait(c);S4;signal(f);end;,begin wait(d);S5;signal(g);end;,begin wait(e);S6;signal(h);end;,begin wait(f);wait(g);wait(h);S7;end;,parend,end,第二章,26.参看教材P58-59,第二章,3、设公共汽车上有一个司机和一个售票员，其活动如图3所示。为了安全起见，显然要求:(1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。试用记录型信号量实现司机与售票员之间的同步，并说明各信号量的含义。,用记录型信号量解决这一问题，需要定义两个信号量：,Start：表示是否允许司机启动车辆，初值为0；,Open：表示是否允许售票员开车门，初值为0。,semaphore start=0;,semaphore open=0;,售票员的活动:,begin,repeat,关车门;,Signal(start);,售票;,Wait(open);,开车门;,until false,end,司机的活动:,begin,repeat,Wait(start);,启动车辆;,正常行车;,到站停车;,Signal(open);,until false,end,第二章,知识点,进程调度算法,避免死锁银行家算法,进程调度算法,先来先服务FCFS,短作业优先调度算法,时间片轮转调度算法,概念,周转时间：指,作业提交给系统,开始，到,作业完成为止,的这段时间间隔。,带权周转时间：周转时间/系统为它提供服务的时间,第三章,1、假定有如下作业：,请用FCFS、SJF、RR(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。,第三章,FCF和SPF的计算结果如下,第三章,时间片轮转调度算法，执行图如下：,进程名,A,B,C,D,E,平均,到达时间,0,1,2,3,4,服务时间,6,4,3,2,5,RR,完成时间,17,14,15,10,20,周转时间,17,13,13,7,16,13.2,带权周转时间,2.83,3.25,4.3,3.5,3.2,3.42,BCA,银行家算法,用于避免死锁。,基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。,安全状态：,是指系统能按某种进程顺序，如,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称序列为安全序列。,若系统存在安全序列，则系统当前为安全状态。,银行家算法描述,设Request,i,是进程P,i,的请求向量，如果Request,i,j=,K,，表示进程P,i,需要,K,个Rj类型的资源。当P,i,发出资源请求后，系统按下述步骤进行检查：,如果Request,i,jNeedi,j，,【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。,如果Request,i,jAvailablej,【请求小于库存】,便转向步骤(3)；否则，表示尚无足够资源，P,i,须等待。,银行家算法描述,3.系统试探着把资源分配给进程P,i,【试分配】,，并修改下面数据结构中的数值：,【库存】,Available j:=Available j-Request,i,j;,【获取】,Allocationi,j:=Allocationi,j+Request,i,j;,【需求】,Needi,j:=Needi,j-Request,i,j,4.系统执行,安全性算法,，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,第三章,2.,在银行家算法中，若出现下述资源分配情况：P115第22题,Proceses,Allocation,Need,Available,P0,0032,0012,1622,P1,1000,1750,P2,1354,2356,P3,0332,0652,P4,0014,0656,第三章,1）该状态是否安全？,Proceses,Allocation,Need,Available,P0,0032,0012,1622,P1,1000,1750,P2,1354,2356,P3,0332,0652,P4,0014,0656,Proceses,Work,Need,Allocation,Work+Allocation,Finish,P0,1622,0012,0032,1654,true,P3,1654,0652,0332,1986,true,P1,1986,1750,1000,2986,true,P2,2986,2356,1354,4340,true,P4,4340,0656,0014,3354,true,安全，因为存在安全序列,第三章,2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它,？,分配后系统资源情况如下：,Proceses,Allocation,Need,Available,P0,0032,0012,0400,P1,1000,1750,P2,2576,2356,P3,0332,0652,P4,0014,0656,此状态不安全，因此不能分配。,第四章,知识点,基本分页式存储管理地址映射过程,基本分段式存储管理地址映射过程,页面置换算法,页表寄存器,页表始址,页表长度,页号,页内地址,逻辑地址L,越界中断,1,块号,b,页表,页号,0,1,2,物理地址,3,基本分页式存储管理地址映射过程,第四章,1、,在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下：,试借助地址变换图求出有效逻辑地址4865所对应的物理地址。,页号,块号,0,2,1,4,2,6,3,8,解答,4,1,8,3,6,2,2,0,块号,页号,011 0000 0001,00010,01100000001,00111,页表首址,+,0,10,物理地址为：13057,基本分段式存储管理地址映射过程,段地址变换由硬件地址变换机构完成。,第四章 作业3,3、,对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成物理地址,。,段号,内存始址,段长,0,50K,10K,1,60K,3K,2,70K,5K,3,120K,8K,4,Cb,+,0,137,比较,5*1024 +137,段,表,04,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,b,1375K,比较,段号,内存始址,段长,0,50K,10K,1,60K,3K,2,70K,5K,3,120K,8K,51337,4,Cb,+,1,4000,比较,段,表,04,地址越界,段表始址寄存器,段表长度寄存器,逻辑地址,b,40003K,比较,段号,内存始址,段长,0,50K,10K,1,60K,3K,2,70K,5K,3,120K,8K,4,Cb,4,230,44,段表始址寄存器,段表长度寄存器,逻辑地址,地址越界,比较,页面置换算法,在请求分页式存储管理中，当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。,页面置换算法分类,最佳页面算法（OPT）,先进先出页面置换算法（FIFO）,最近最久未使用页面置换算法（LRU）,轮转算法（Clock）,第四章 作业2：P143页 23题,2、某程序在内存中分配,四,个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、Clock、OPT算法分别计算缺页次数,假设开始时所有页均不在内存,LRU 4 3 2 1 4 3 5 4 3 2 1 5,块1,块2,块3,块4,x x x x,x,x x x,共缺页中断8次,LRU,4,4,3,4,3,2,4,3,2,1,4,3,2,1,4,3,2,1,4,3,5,1,4,3,5,1,4,3,5,1,4,3,5,2,4,3,1,2,5,3,1,2,Clock 4 3 2 1 4 3 5 4 3 2 1 5,块1,块2,块3,块4,x x x x,x x x,x x x,共缺页中断10次,Clock,4,4,3,4,3,2,4,3,2,1,4,3,2,1,4,3,2,1,5,3,2,1,5,4,2,1,5,4,3,1,5,4,3,2,1,4,3,2,1,5,3,2,OPT 4 3 2 1 4 3 5 4 3 2 1 5,块1,块2,块3,块4,x x x x,x,x,共缺页中断6次,OPT,4,4,3,4,3,2,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,5,4,3,2,5,4,3,2,5,4,3,2,5,1,3,2,5,1,3,2,5,第四章 作业4,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。,LRU,3 3 1 3 2 3 0 2 1 2 3 0 1 1,块1,块2,块3,LRU,3,3,3
展开阅读全文