《操作系统计算题综合ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统计算题综合ppt课件.ppt（47页珍藏版）》请在三一办公上搜索。
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=若提交顺序改为作业3、2、1，则T=FCFS调度算
2、法的平均作业周转时间与作业提交的顺序有关。,(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非抢占调度算法时的平均周转时间和平均等待时间。 进程 到达时间 服务时间 P107 P2
3、24 P341 P454,进程到达时间服务时间 P107 P224 P341 P454FCFS,平均周转时间= (7-0)+(11-2)+(12-4)+(16-5)/4=8.75平均等待时间 = (0+(7-2)+(11-4)+(12-5)/4 =4.75,课堂练习,课堂练习,进程 到达时间 服务时间 P107 P224 P341 P454SPF,平均周转时间= (7-0)+(12-2)+(8-4)+(16-5)/4=8平均等待时间= (0-0)+(8-2)+(7-4)+(12-5)/4 = 4,SPF与FCFS的比较,三、时间片轮转调度算法例(1),EG：进程到达时间服务时间P107 P22
4、4 P341 P454RR（时间片为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,非抢占式优先权算法例1,EG1：进程到达时间 服务时间 优先数 P1 0 7 3 P2 2 4 2 P3 4 1 4 P4 5 4 1Gantt图平均周转时间 =(7-0)+(15-2)+(16-4)+(11-5)/4=9.5平均等待时间=(0+9+11+2)/4 = 5.5,优先数越小优先级越高,抢占式优先权算法例2,EG2
5、：进程到达时间 服务时间 优先数P10 7 3 P22 4 2 P34 1 4 P45 4 1Gantt图平均周转时间 =(15-0)+(10-2)+(16-4)+(9-5)/4=9.75平均等待时间=(8+4+11+0)/4 = 5.75,各种算法结果值的比较,返回,五、高响应比优先权调度算法HRP,优先权的变化为,为响应比。,如等待时间相同,则要求服务时间愈短,其优先权愈高-SPF.如要求服务时间相同,优先权决定于等待时间-FCFS。对长作业,若等待时间足够长，优先权也高，也能获得CPU。,算法HRP示例,HRP 的调度性能,=2.14,0,3,9,15,13,3,9,13,20,15,T
6、A=3,TB=7,TC=9,TD=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,不同调度算法对同一
7、个 作业/进程的性能分析:,返回,银行家算法的例子,假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。,（1） T0时刻的安全性,T0时刻存在着一个安全序列P1 P3 P4 P2 P0，故系统是安全的。,银行家算法的例子,(2) P1请求资源 Request1(1,0,2)执行银行家算法,银行家算法的例子,P1请求资源时的资源分配表,P1请求资源时的安全性检查表,存在着一个安全序列P1 P3 P4 P2 P0，故系统是安全的，可以立即将P1所申请的资源分配给它。,银行家算法的例子,（3）P4请求资源Request4(3,3,0),P4发出请求向量Request4(3
8、,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) 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配,返回目录,三、地址结构例题,例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解
9、：（1）页式存储管理系统的逻辑地址为：其中页内地址表每页的大小即 2048B=2*1024B=211B，所以页内地址为11位；页号表最多允许的页数即 16页=24页，所以页号为4位。故逻辑地址至少应为15位。 （2）物理地址为：其中块内地址表每块的大小与页大小相等，所以块内地址也为11位；其中块号表内存空间最多允许的块数即 8块=23块，所以块号为3位。故内存空间至少应为14位，即214 =16KB。,返回,四、地址变换例题1,例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。,四、
10、地址变换例题,解：由题知逻辑地址为： 物理地址为：（1）逻辑地址1011（十进制）的二进制表示为： 00 1111110011，由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中； 其物理地址的二进制表示为：010 1111110011，所以逻辑地址1011对应的物理地址为0BF3H。其地址转换图如后所示。,四、地址变换例题1,（2）逻辑地址2148（十进制）的二进制为： 10 0001100100，由此可知逻辑地址2148的页号是2，查页表知该页放入物理块1中； 其物理地址的二进制是：001 0001100100，所以逻辑地址2148对应的物理地址是0464H。 （3）逻辑地址5
11、012（十进制）的二进制表示为： 100 1110010100，可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。,地址变换过程,+,页表长度,页表始址,3F3,0,页表寄存器,逻辑地址1011（03F3H）,物理地址0BF3H,越界中断,页合法,四、地址变换例题1,例1、在一个段式存储管理系统中，其段表为： 段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 95试求右表中逻辑地址对应的物理地址是什么？解：逻辑地址为： 逻辑地址 对应的物理地址为：210+430=640。 逻辑地址 因为段内地址120段长90
12、，所为该段为非法段。,分段地址变换例题1,由段表可知段号为3位，段内地址为10位。,分段地址变换例题2,例2、某段表的内容如下：段号 段首址 段长度 0 120K 40K 1 760K 30K 2 480K 20K 3 370K 20K对于逻辑地址2154，它对应的物理地址为多少？解：逻辑地址为： 由段表可知段号为2位，段内地址为16位，段允许的最大长度为 216=210*26=1024*64=65536。 所以逻辑地址2154（二进制为100001101010）的段号为0，查段表知其对应的物理地址为：120K+2154=125034,地址变换例题,某虚拟存储器的用户空间共有32个页面，每页1
13、KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。解：虚拟地址为：页号5位（25=32），页内位移10位（110=1024）；物理地址为：物理块号4位（24=16），块内位移（110=1024）10位。虚拟地址0A5C对应的二进制为：00010 1001011100，即虚拟地址0A5C的页号为2，页内位移为1001011100，由题意知对应的物理地址为：0100 1001011100即125C。同理求093C的物理地址为293C。略,最佳置换算法(Optimal,OPT)例,假定系统为某进程分配了3个
14、物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换页面淘汰算法时的缺页率？,返回,注：实际上这种算法无法实现，因页面访问的未来顺序很难精确预测，但可用该算法评价其它算法的优劣。,1,缺,缺,缺,缺,缺,缺,缺,1,2,3,1,2,1,2,1,2,1,2,1,2,1,2,1,2,3,3,3,4,4,4,4,4,2,5,5,5,5,5,5,(7/12),先进先出置换算法(FIFO)例题,1、假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先
15、进先出页面淘汰算法时的缺页率？,(9/12),先进先出置换算法例题,2、假定系统为某进程分配了4个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时4个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？,(10/12),先进先出置换算法例题,3、假定系统为某进程分配了5个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？,(5/12),先进先出置换算法_注1：,1、该算法的出发点是最早调入内存的页面，其不再被访问的可能性会大一些。2、FIFO算法易于理解与编程，
16、但它的效率不高。被置换的页可能存有一个初始化程序段，很早前用过后再也不会用到；但也可能存有一组经常访问的全局变量，初始化时被调入内存，在整个程序运行过程中都将会用到。,先进先出置换算法_注2：,3、先进先出算法存在一种异常现象，即在某些情况下会出现分配给进程的物理块数增多，缺页次数有时增加，有时减少的奇怪现象，这种现象称为Belady现象。如前述几例：,返回,“Belady异常”与其说是一种奇怪现象，不如说是一个重要提示。它对学习操作系统来说的实际意义是起警示作用：即操作系统是一个复杂的机构，直观的感觉是靠不住的。,最近最久未使用算法例,例：假定系统为某进程分配了3个物理块，进程运行时的页面走
17、向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最近最久未使用页面淘汰算法时的缺页率？,(10/12),2、磁盘调度算法,磁盘调度算法早期的磁盘调度算法先来先服务FCFS最短寻道时间优先SSTF扫描算法扫描(SCAN)/电梯(LOOK)算法循环扫描(CSCAN)算法,返回,例：假设一个请求序列：98、183、 37、 122、14、124、65、 67，磁头当前的位置在53。,FCFS 先来先服务,按进程请求访问磁盘的先后次序进行调度,最短寻道时间优先（SSTF）,选择从当前磁头位置所需寻道时间最短的请求。,扫描算法（SCAN）,假定：磁头向磁道号增加的方
18、向移动。,假定：磁头向磁道号增加的方向移动。,Look算法（电梯算法）,循环扫描算法（CSCAN）,特点：消除了对两端磁道请求的不公平。,返回,练习题1,例1：设某系统的磁盘有500块，块号为：0，1，2，3，499。（1） 若用位示图法管理这500块的盘空间，当字长为32位时，此位示图占了几个字？（2） 第i字的第j位对应的块号是多少？（其中：i=0，1，2，j=0，1，2，3，）,解：（1） 位示图法就是在内存用一些字建立一张位示图，用其中的每一位表示一个盘块的使用情况，通常用“1”表示占用，“0”表示空闲。因此，本问题中位示图所占的字数为：50032=16。（2） 第i字的第j位对应的块
19、号N=32*i+j。,练习题2,例2：有一计算机系统利用下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。（1） 现要为文件分配两个盘块，试具体说明分配过程。（2） 若要释放磁盘的第300块，应如何处理？,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0123456,答：（1）为某文件分配两个盘块的过程如下： 顺序检索位示图，从中找到第一个值为0的二进制位，得到其行号il=2，列号jl=2。第二个值为0的二进制位，得到其行号i2=3，列号j2=6。 计算出找到的两个空闲块的盘块号分别为： b1=i116+j1+1=216+2+1=35 b2=i216+j2+1=316+6+1=55 修改位示图，令map2,2=map3,6=1，并将对应块35、55分配出去。 （2） 释放磁盘的第300块时，应进行如下处理： 计算出磁盘第300块所对应的二进制位的行号i和列号j： i=（300-1）16=18，j =（300-1）%16=11 修改位示图，令map18,11=0，表示对应块为空闲块。,
