作业讲解（24）知识点n进程互斥和同步的控制信号量机制信号量是一种数据结构信号量的值与相应资源的使用情况有关信号量的值仅由P、V操作改变知识点记录型信号量n记录型结构，包括两个数据项：type semaphore=record value:integer; L:list of process; end 知识点n假设定义了一个信号量SnS.value为资源信号量，其初值为某类资源的数目。S.value=0，代表系统当中可用资源的数目。S.value0,其绝对值代表等待使用资源的进程个数。nS.L是一个阻塞队列，进程无法申请到资源则进入此队列。知识点n定义对信号量的两个原子操作：定义对信号量的两个原子操作：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 知识点n定义对信号量的两个原子操作：定义对信号量的两个原子操作：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;beginparbeginbegin 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;parendend第二章n26. 参看教材参看教材P58-59第二章n3、设公共汽车上有一个司机和一个售票员，其活动如图、设公共汽车上有一个司机和一个售票员，其活动如图3所示。所示。为了安全起见，显然要求为了安全起见，显然要求: (1)关车门后方能启动车辆；关车门后方能启动车辆；(2)到站停到站停车后方能开车门。亦即车后方能开车门。亦即“启动车辆启动车辆”这一活动应当在这一活动应当在“关车门关车门”这一这一活动之后，活动之后，“开车门开车门”这一活动应当在这一活动应当在“到站停车到站停车”这一活动之后。这一活动之后。试用记录型信号量实现司机与售票员之间的同步，并说明各信号试用记录型信号量实现司机与售票员之间的同步，并说明各信号量的含义。量的含义。n用记录型信号量解决这一问题，需要定义两个信号量：nStart：表示是否允许司机启动车辆，初值为0；nOpen：表示是否允许售票员开车门，初值为0。semaphore start=0;semaphore open=0;售票员的活动:beginrepeat 关车门; Signal(start); 售票; Wait(open); 开车门;until falseend司机的活动:beginrepeat Wait(start); 启动车辆; 正常行车; 到站停车; Signal(open);until falseend第二章n知识点进程调度算法避免死锁银行家算法进程调度算法n先来先服务FCFSn短作业优先调度算法n时间片轮转调度算法n概念周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。带权周转时间：周转时间/系统为它提供服务的时间第三章1、假定有如下作业：请用FCFS、SJF、RR(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。第三章FCF和SPF的计算结果如下第三章n时间片轮转调度算法，执行图如下：进程名ABCDE平均到达时间01234服务时间64325RR完成时间1714151020周转时间17131371613.2带权周转时间2.833.254.33.53.23.42BCA银行家算法n用于避免死锁。n基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。n安全状态：是指系统能按某种进程顺序，如,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称序列为安全序列。若系统存在安全序列，则系统当前为安全状态。银行家算法描述n设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 1.如果RequestijNeedi,j， 【请求小于需求请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。2.如果RequestijAvailablej【请求小于库存请求小于库存】,便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 银行家算法描述3. 系统试探着把资源分配给进程Pi【试分配】【试分配】，并修改下面数据结构中的数值： 【库存】【库存】 Available j :=Available j -Requestij; 【获取】【获取】 Allocationi,j:=Allocationi,j+Requestij; 【需求】【需求】 Needi,j:=Needi,j-Requestij4. 系统执行安全性算法安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。第三章2 .在银行家算法中，若出现下述资源分配情况：P115第22题Proceses AllocationNeed AvailableP0003200121622P110001750P213542356P303320652P400140656第三章n1）该状态是否安全？Proceses AllocationNeed AvailableP0003200121622P110001750P213542356P303320652P400140656Proceses WorkNeed AllocationWork+AllocationFinishP01622001200321654trueP31654065203321986trueP11986175010002986trueP22986235613544340trueP44340065600143354true安全，因为存在安安全，因为存在安全序列全序列第三章n2)2)若进程若进程P2P2提出请求提出请求Request(1,2,2,2)Request(1,2,2,2)后，系统能否后，系统能否将资源分配给它将资源分配给它？n分配后系统资源情况如下：分配后系统资源情况如下：Proceses AllocationNeed AvailableP0003200120400P110001750P225762356P303320652P400140656此状态不安此状态不安全，因此不全，因此不能分配。能分配。第四章n知识点基本分页式存储管理地址映射过程基本分段式存储管理地址映射过程页面置换算法页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断1块号b页表页号012物理地址3基本分页式存储管理地址映射过程第四章1、在采用页式存储管理的系统中，拥有的逻辑在采用页式存储管理的系统中，拥有的逻辑地址空间为地址空间为32页，某作业页，某作业J的逻辑地址空间为的逻辑地址空间为4页（每页页（每页2048字节），且已知该作业的页面映字节），且已知该作业的页面映像（即页表）如下：像（即页表）如下：n试借助地址变换图求出有效逻辑地址试借助地址变换图求出有效逻辑地址4865所对所对应的物理地址。应的物理地址。页号页号块号块号02142638解答41836220块号页号011 0000 0001000100110000000100111页表首址页表首址+010物理地址为：物理地址为：13057基本分段式存储管理地址映射过程段地址变换由硬件地址变换机构完成。段地址变换由硬件地址变换机构完成。第四章 作业33、对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成物理地址。段号内存始址段长050K10K160K3K270K5K3120K8K 4 Cb+0 137比较比较5*1024 + 137段段表表04物理地址物理地址段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址b1375K比较比较段号内存始址段长050K10K160K3K270K5K3120K8K51337 4 Cb+1 4000比较比较段段表表04地址越界地址越界段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址b40003K比较比较段号内存始址段长050K10K160K3K270K5K3120K8K 4 Cb4 23044段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址地址越界地址越界比较比较页面置换算法n在请求分页式存储管理中，当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。页面置换算法分类n最佳页面算法（OPT）n先进先出页面置换算法（FIFO）n最近最久未使用页面置换算法（LRU）n轮转算法（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次LRU443432432143214321435143514351435243125312Clock 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次Clock443432432143214321532154215431543214321532OPT 4 3 2 1 4 3 5 4 3 2 1 5块1块2块3块4 x x x x x x 共缺页中断6次OPT443432432143214321432543254325432513251325第四章 作业44、某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3653，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制，而内存中尚未装入任何页。请给出使用LRU算法时的缺页次数。n解答：页块数为解答：页块数为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块3LRU3 3 3131312312302302102102132032031031x x x x x x x x 共缺页中断8次