操作系统计算题综合（课堂PPT）

操作系统复习,综合计算题,1,2,一、先来先服务（FCFS）调度算法,例1：作业名到达时间服务时间A01B1100C21D3100,2,2020/5/19,完成时间-到达时间,开始时间+服务时间,上一个进程的完成时间,11011001,101102100100,1022021991.99,3,2020/5/19,一、先来先服务（FCFS）调度算法,例2：下面三个作业几乎同时到达系统并立即进行FCFS调度：作业名所需CPU时间作业128作业29作业33假设提交顺序为1、2、3，则平均作业周转时间T=若提交顺序改为作业2、1、3，则T=若提交顺序改为作业3、2、1，则T=FCFS调度算法的平均作业周转时间与作业提交的顺序有关。,(28+37+40)/3=35,29,18,4,2020/5/19,执行顺序：,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,5,2020/5/19,FCFS：ABCDESJF:ADBEC,FCFS和的SJF比较,6,2020/5/19,课堂练习,练习：有如下四个进程，它们的到达时间和服务时间如下所示，请分别计算在采用FCFS、SPF非抢占调度算法时的平均周转时间和平均等待时间。进程到达时间服务时间P107P224P341P454,7,2020/5/19,进程到达时间服务时间P107P224P341P454FCFS,平均周转时间=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75平均等待时间=(0+(7-2)+(11-4)+(12-5)/4=4.75,课堂练习,8,2020/5/19,课堂练习,进程到达时间服务时间P107P224P341P454SPF,平均周转时间=(7-0)+(12-2)+(8-4)+(16-5)/4=8平均等待时间=(0-0)+(8-2)+(7-4)+(12-5)/4=4,9,2020/5/19,SPF与FCFS的比较,10,2020/5/19,三、时间片轮转调度算法例(1),EG：进程到达时间服务时间P107P224P341P454RR（时间片为4）,P1,P2,045678910111213141516,P1,P3,P4,平均周转时间=(16-0)+(8-2)+(9-4)+(13-5)/4=8.75平均等待时间=(9+2+4+4)/4=4.75,11,2020/5/19,非抢占式优先权算法例1,EG1：进程到达时间服务时间优先数P1073P2242P3414P4541Gantt图平均周转时间=(7-0)+(15-2)+(16-4)+(11-5)/4=9.5平均等待时间=(0+9+11+2)/4=5.5,优先数越小优先级越高,12,2020/5/19,抢占式优先权算法例2,EG2：进程到达时间服务时间优先数P1073P2242P3414P4541Gantt图平均周转时间=(15-0)+(10-2)+(16-4)+(9-5)/4=9.75平均等待时间=(8+4+11+0)/4=5.75,13,2020/5/19,各种算法结果值的比较,返回,14,五、高响应比优先权调度算法HRP,优先权的变化为,为响应比。,如等待时间相同,则要求服务时间愈短,其优先权愈高-SPF.如要求服务时间相同,优先权决定于等待时间-FCFS。对长作业,若等待时间足够长，优先权也高，也能获得CPU。,15,2020/5/19,算法HRP示例,HRP的调度性能,=2.14,0,3,9,15,13,3,9,13,20,15,TA=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,16,2020/5/19,五、高响应比优先权调度算法HRP,不同调度算法对同一个作业/进程的性能分析:,返回,17,2020/5/19,银行家算法的例子,假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。,18,2020/5/19,（1）T0时刻的安全性,T0时刻存在着一个安全序列P1P3P4P2P0，故系统是安全的。,银行家算法的例子,19,2020/5/19,(2)P1请求资源Request1(1,0,2)执行银行家算法,银行家算法的例子,P1请求资源时的资源分配表,20,P1请求资源时的安全性检查表,存在着一个安全序列P1P3P4P2P0，故系统是安全的，可以立即将P1所申请的资源分配给它。,银行家算法的例子,21,2020/5/19,（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等待,银行家算法的例子,22,2020/5/19,(4)P0请求资源Request0(0,2,0),银行家算法的例子,P0请求资源时的资源分配表,Available(2,1,0)不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配,返回目录,23,三、地址结构例题,例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：（1）页式存储管理系统的逻辑地址为：其中页内地址表每页的大小即2048B=2*1024B=211B，所以页内地址为11位；页号表最多允许的页数即16页=24页，所以页号为4位。故逻辑地址至少应为15位。（2）物理地址为：其中块内地址表每块的大小与页大小相等，所以块内地址也为11位；其中块号表内存空间最多允许的块数即8块=23块，所以块号为3位。故内存空间至少应为14位，即214=16KB。,返回,24,2020/5/19,四、地址变换例题1,例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。,25,2020/5/19,四、地址变换例题,解：由题知逻辑地址为：物理地址为：（1）逻辑地址1011（十进制）的二进制表示为：001111110011，由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中；其物理地址的二进制表示为：0101111110011，所以逻辑地址1011对应的物理地址为0BF3H。其地址转换图如后所示。,26,2020/5/19,四、地址变换例题1,（2）逻辑地址2148（十进制）的二进制为：100001100100，由此可知逻辑地址2148的页号是2，查页表知该页放入物理块1中；其物理地址的二进制是：0010001100100，所以逻辑地址2148对应的物理地址是0464H。（3）逻辑地址5012（十进制）的二进制表示为：1001110010100，可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。,27,2020/5/19,地址变换过程,+,段长90，所为该段为非法段。,分段地址变换例题1,由段表可知段号为3位，段内地址为10位。,29,2020/5/19,分段地址变换例题2,例2、某段表的内容如下：段号段首址段长度0120K40K1760K30K2480K20K3370K20K对于逻辑地址2154，它对应的物理地址为多少？解：逻辑地址为：由段表可知段号为2位，段内地址为16位，段允许的最大长度为216=210*26=1024*64=65536。所以逻辑地址2154（二进制为100001101010）的段号为0，查段表知其对应的物理地址为：120K+2154=125034,30,2020/5/19,地址变换例题,某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。解：虚拟地址为：页号5位（25=32），页内位移10位（110=1024）；物理地址为：物理块号4位（24=16），块内位移（110=1024）10位。虚拟地址0A5C对应的二进制为：000101001011100，即虚拟地址0A5C的页号为2，页内位移为1001011100，由题意知对应的物理地址为：01001001011100即125C。同理求093C的物理地址为293C。略,31,2020/5/19,最佳置换算法(Optimal,OPT)例,假定系统为某进程分配了3个物理块，进程运行时的页面走向为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),32,2020/5/19,先进先出置换算法(FIFO)例题,1、假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？,(9/12),33,2020/5/19,先进先出置换算法例题,2、假定系统为某进程分配了4个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时4个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？,(10/12),34,2020/5/19,先进先出置换算法例题,3、假定系统为某进程分配了5个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？,(5/12),35,2020/5/19,先进先出置换算法_注1：,1、该算法的出发点是最早调入内存的页面，其不再被访问的可能性会大一些。2、FIFO算法易于理解与编程，但它的效率不高。被置换的页可能存有一个初始化程序段，很早前用过后再也不会用到；但也可能存有一组经常访问的全局变量，初始化时被调入内存，在整个程序运行过程中都将会用到。,36,2020/5/19,先进先出置换算法_注2：,3、先进先出算法存在一种异常现象，即在某些情况下会出现分配给进程的物理块数增多，缺页次数有时增加，有时减少的奇怪现象，这种现象称为Belady现象。如前述几例：,返回,“Belady异常”与其说是一种奇怪现象，不如说是一个重要提示。它对学习操作系统来说的实际意义是起警示作用：即操作系统是一个复杂的机构，直观的感觉是靠不住的。,37,最近最久未使用算法例,例：假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最近最久未使用页面淘汰算法时的缺页率？,(10/12),38,2020/5/19,2、磁盘调度算法,磁盘调度算法早期的磁盘调度算法先来先服务FCFS最短寻道时间优先SSTF扫描算法扫描(SCAN)/电梯(LOOK)算法循环扫描(CSCAN)算法,返回,例：假设一个请求序列：98、183、37、122、14、124、65、67，磁头当前的位置在53。,39,2020/5/19,FCFS先来先服务,按进程请求访问磁盘的先后次序进行调度,40,2020/5/19,最短寻道时间优先（SSTF）,选择从当前磁头位置所需寻道时间最短的请求。,41,2020/5/19,扫描算法（SCAN）,假定：磁头向磁道号增加的方向移动。,42,2020/5/19,假定：磁头向磁道号增加的方向移动。,Look算法（电梯算法）,43,循环扫描算法（CSCAN）,特点：消除了对两端磁道请求的不公平。,返回,44,2020/5/19,练习题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位对应的块号N=32*i+j。,45,2020/5/19,练习题2,例2：有一计算机系统利用下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。（1）现要为文件分配两个盘块，试具体说明分配过程。（2）若要释放磁盘的第300块，应如何处理？,0123456789101112131415,0123456,46,答：（1）为某文件分配两个盘块的过程