《应用题综合复习剖析》由会员分享，可在线阅读，更多相关《应用题综合复习剖析（115页珍藏版）》请在金锄头文库上搜索。
1、计算机操作系统 汤小丹等 西电出版社,进程（作业）调度算法,一、先来先服务（FCFS）调度算法,例1： 作业名 到达时间 服务时间 A 0 1 B 1 100 C 2 1 D 3 100,完成时间-到达时间,开始时间+服务时间,上一个进程的完成时间,1 101 100 1,101 102 100 100,102 202 199 1.99,一、先来先服务（FCFS）调度算法,例2：下面三个作业几乎同时到达系统并立即进行FCFS调度： 作业名 所需CPU时间 作业1 28 作业2 9 作业3 3 假设提交顺序为1、2、3，则平均作业周转时间T = 若提交顺序改为作业2、1、3，则T= 若提交顺序改
2、为作业3、2、1，则T= FCFS调度算法的平均作业周转时间与作业提交的顺序有关。,(28+37+40)/3 = 35,29,18,执行顺序：,SJF/SPF_非抢占式举例,A,0,3,3,1,0,3,A,B,C,D,E,2,4,6,8,6,4,5,2,B,3,9,7,1.17,9,11,3,1.5,11,15,11,2.75,15,20,14,2.8,E,C,D,7.6,1.84,FCFS：ABCDE SJF: ADBEC,FCFS和的SJF比较,练习,练习：有如下四个进程，它们的到达时间和服务时间如下所示，请分别计算在采用FCFS、SPF非抢占调度算法时的平均周转时间和平均等待时间。 进程
3、 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4,进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 FCFS,平均周转时间= (7-0)+(11-2)+(12-4)+(16-5)/4=8.75 平均等待时间 = (0+(7-2)+(11-4)+(12-5)/4 =4.75,课堂练习,课堂练习,进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 SPF,平均周转时间= (7-0)+(12-2)+(8-4)+(16-5)/4=8 平均等待时间= (0-0)+(8-2)+(7-4)+(12-5)/4 = 4,S
4、PF与FCFS的比较,三、时间片轮转调度算法例(1),EG： 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 RR（时间片为4）,P1,P2,0 4 5 6 7 8 9 10 11 12 13 14 15 16,P1,P3,P4,平均周转时间 =(16-0)+(8-2)+(9-4)+(13-5)/4 =8.75 平均等待时间=(9+2+4+4)/4 = 4.75,注意该题P1结束时P3尚未到达！,非抢占式优先级算法例1,EG1： 进程 到达时间 服务时间 优先数 P1 0 7 3 P2 2 4 2 P3 4 1 4 P4 5 4 1 Gantt图 平均周转时间
5、 =(7-0)+(15-2)+(16-4)+(11-5)/4=9.5 平均等待时间=(0+9+11+2)/4 = 5.5,优先数越小优先级越高,抢占式优先级算法（最短剩余时间优先）-例2,EG2： 进程 到达时间 服务时间 优先数 P1 0 7 3 P2 2 4 2 P3 4 1 4 P4 5 4 1 Gantt图 平均周转时间 =(15-0)+(10-2)+(16-4)+(9-5)/4=9.75 平均等待时间=(8+4+11+0)/4 = 5.75,各种算法结果值的比较,返回,HRP 的调度性能,=2.14,0,3,9,15,13,3,9,13,20,15,TA=3,TB=7,TC=9,TD
6、=14,TE=7,=8.00,8,3,6,4,5,2,2,0,4,6,A,B,C,D,E,WE=3.50,WA=1,WB=1.17,WC=2.25,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,=(9-4)+4/4=2.25,=(9-6)+5/5=1.6,=(9-8)+2/2=1.5,RC,RD,RE,RD,=(13-6)+5/5=2.4,RE,=(13-8)+2/2=3.5,高响应比调度算法HRP,五、高响应比优先权调度算法HRP,不同调度算法对同一个 作业
7、/进程的性能分析:,返回,银行家算法,安全状态实例,假定系统中有三个进程P1，P2和P3，共有12台磁带机，三个进程对磁带机的需求和占有如下：,T0时刻，存在一个安全序列（P2，P1，P3）所以系统是安全的。,二、系统的安全状态,二、系统的安全状态,由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。,因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。,避免死锁的算法-银行家算法,为实现银行家算法，系统中必须设置若干数据结构。假定系统中有n个进程（P1，P2，Pn），m类资源（R1，
8、R2，Rm），银行家算法中使用的数据结构: 可利用资源向量:availablej=k, 资源Rj类有k个可用 最大需求矩阵:Maxi,j=k,进程Pi最大请求k个Rj类资源 分配矩阵：Allocationi,j=k,进程Pi分配到k个Rj类资源 需求矩阵：Needi,j=k,进程Pi还需要k个Rj类资源 三个矩阵的关系： Need i,j = Maxi,j Allocation i,j.,银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1)如果RequestijNeedi,j，
9、便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2)如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。,银行家算法 (3)系统试探着把资源分配给进程Pi，并修改 下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资 源分配给进程Pi，以完成本次分配；否则， 将本 次
10、的试探分配作废，恢复原来的资源分配状态，让 进程Pi等待。,安全性算法 (1)设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 (2)从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj；若找到， 执行步骤(3)， 否则，执行步骤(4)。,安全性算法 (3)当进程Pi获得资源后，
11、可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; (4)如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。,银行家算法的例子,假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。,（1） T0时刻的安全性,T0时刻存在着一个安全序列 P1 P3 P4 P2 P0，故系统是安全的。,银行家算法的例子,(2) P1请求资源 Request1(1,0,2)执行银行家算法,银行家算法的例子,P1请求资源时的资源分
12、配表,P1请求资源时的安全性检查表,存在着一个安全序列P1 P3 P4 P2 P0，故系统是安全的，可以立即将P1所申请的资源分配给它。,银行家算法的例子,（3）P4请求资源Request4(3,3,0),P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查: 1) Request4(3,3,0)Need4 (4,3,1) 2) Request4 (3,3,0) Available (2,3,0),表示资源不够,则让P4等待,银行家算法的例子,(4) P0请求资源 Request0(0,2,0),银行家算法的例子,P0请求资源时的资源分配表,Available(2,1,0)
13、 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配,返回目录,地址变换,三、地址结构例题,例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？ 解：（1）页式存储管理系统的逻辑地址为：其中页内地址表每页的大小即 2048B=2*1024B=211B，所以页内地址为11位；页号表最多允许的页数即 16页=24页，所以页号为4位。故逻辑地址至少应为15位。 （2）物理地址为：其中块内地址表每块的大小与页大小相等，所以块内地址也为11位；其中块号表内存空间最多允许的块数即 8块=23块，所
14、以块号为3位。故内存空间至少应为14位，即214 =16KB。,返回,四、地址变换例题1,例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。,四、地址变换例题,解：由题知逻辑地址为： 物理地址为： （1）逻辑地址1011（十进制）的二进制表示为： 00 1111110011，由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中； 其物理地址的二进制表示为：010 1111110011，所以逻辑地址1011对应的物理地址为0BF3H。其地址转换图如后所示。,四、地址变换例题1
15、,（2）逻辑地址2148（十进制）的二进制为： 10 0001100100，由此可知逻辑地址2148的页号是2，查页表知该页放入物理块1中； 其物理地址的二进制是：001 0001100100，所以逻辑地址2148对应的物理地址是0464H。 （3）逻辑地址5012（十进制）的二进制表示为： 100 1110010100，可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。,地址变换过程,+,页表长度,页表始址,3F3,0,页表寄存器,逻辑地址1011（03F3H）,物理地址0BF3H,越界中断,页合法,四、地址变换例题1,例1、在一个段式存储管理系统中，其段表为： 段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590
