操作系统计算题综合

1、操作系统复习、综合计算问题、未来服务(FCFS )调度算法，例如：工作名称到达时间服务时间a0b1c2d3100、完成时间-到达时间、开始时间服务时间、先前处理的完成时间、11011001、10110 一、先到先得服务(FCFS )调度算法， 示例2 :以下三个工作几乎同时到达系统，并立即进行FCFS调度：如果工作名称必要CPU时间工作1 28工作2 9工作3提交顺序为1、2、3，平均工作周转时间T=提交顺序变更为工作2、1、3，则T=提交顺序变更为工作3、2、1 (283740 )/3=35，29，18，执行顺序：SJF/SPF_非抢占示例，a、0、3、a、b、c、d、e、2、4、6、8、6

2、、4、5、2、b、3、9、7、1.17 7.6 1.84，FCFS:abcdesjf : adbec，FCFS:abcdesjf 333: adbeeee 、 进程到达时间服务时间p107p2p3p4p4p5，进程到达时间服务时间p107p2p3p4p4p5fcfs平均旋转时间=(7-0) (11-2 ) (12-4 ) (16-5 ) )/4=8.75平均等待时间=(0(7-2) (11-4 ) (12-4 ) 教室练习，进程到达时间服务时间p107p22p4p3p4p4spf平均运行时间=(7-0) (12-2) (8-4) (16-5)/4=8平均等待时间=(0-0) (8-2) (7-

3、4) (12-5)/4=4，SPF和FCFS的比较，三， 时间片轮换调度算法-例子(1) EG :进程到达时间服务时间P107P2p3p4p4p5rr (时间表为4 )，P1，p2，0 4 5 6 7 8 9 10 11 12 13 14 15 16，P1，P4 p5平均运行时间=(16-0 ) (8-2) (9-4) (13-5 ) )/4=8.75平均等待时间=(9 2 4 4)/4=4.75，非优先优先优先算法-例1 EG1 :进程到达时间服务时间优先数p107p22p3p4p4p4p51gantt图表平均旋转(16-4)(11-5)/4=9.5平均等待时间=(0 9 11 2)/4=5

4、.5，优先级数越小优先级越高的优先权优先算法例2， EG2 :进程到达时间服务时间优先数p107p22p3p4p4p4p51gantt图平均旋转时间=(15-0 ) (10-2 ) (16-4 ) (9-5) )/4=9.75平均等待时间=(8 4 11 0)/4=5.75 )，各种算法结果值的比较、返回另外，若等待时间相同，则请求服务时间越短，优先级越高-SPF .若请求服务时间相同，则优先级被决定为等待时间-FCFS。 在长时间的工作中，等待时间足够长的话，优先级也高，CPU也能得到。 算法HRP的示例，HRP的调度性能，=2. 14，0，3，9，15，13，3，9，13，13，15，TA

5、=3，TB=7，TC=9，TD=14，TE=7，=8. 00，8，3，6，4 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，= (9-4)4/4=(9-8) 2/2=1.5， RC、RD、RE、RD、=(13-6) 5/5=2.4、RE、=(13-8) 2/2=3.5、5、快速响应比优先调度算法HRP、使用不同的调度算法的相同工作/过程的性能分析： (1) T0时刻的安全性，T0时刻存在安全系列P1 P3 P4 P2 P0，因此系统是安全的。 银行家算法

6、的例子有(2) P1要求执行资源request1(1，0，2 )银行家算法的例子，P1请求资源时的资源分配表，P1请求资源时的安全性检查表，是安全的序列P1 P3 P4 P2 P0(3)P4请求资源request4(3，3，0 )，P4发出请求向量request4(3，3，0 )，并且系统根据银行家算法检查request4(3，3，0 )need 可用(2，3 )， 0 )一旦指示资源不足，就让P4等待，银行家算法的示例包括： (4) P0请求资源request0(0，2，0 )，银行家算法的示例，P0请求资源时的资源分配表，available=(2，1，0 )表示过程的需求系统进入不安全状态

7、，不分配P0请求，返回到目录，三，地址结构示例：有一个基于页的存储管理系统，提供给用户的逻辑地址空间最多16页，每页2048B，内存共计8个块， 问一下逻辑地址应该至少有多少位？内存容量是多少？解： (1)基于页的存储管理系统的逻辑地址，其中页内地地址表的每页大小为2048B=2*1024B=211B 逻辑地址必须至少为15位。 (2)关于物理地址，其中块内地地址表的块大小与页大小相等，所以块内地地址也是11比特，其中，块号码表的存储区域中最大允许块数是8块=23块，所以块号码因此，存储器区域必须至少有14位，即，214=16KB。 返回，四，地址转换例题1、例1 :在寻呼存储管理系统中，如果

8、某作业的页表如下表所示，则知道页大小为1024B，从而将逻辑地址1011、2148、5012转换为对应的物理地址画那个地址转换图。 四、地址转换例题、解：从问题来看，逻辑地址为： (1)将逻辑地址1011 (十进制)的二进制数表示为： 00 1111110011，所以知道逻辑地址1011的页码0，查页后，该页被放置在第2物理块上其地址转换图如下所示。 另外，四、地址转换例题1、(2)逻辑地址2148 (十进制)的二进制数是： 10000110000 (3)指示了逻辑地址5012 (十进制)的二进制文件，从而知道了逻辑地址的页编号为4，从而知道该页是非法页，这时，发生越境中断。 地址转换过程，长

9、度为90，此段为非法段。 从分段地址转换例题1、分段表可知分段编号为3位，分段内地地址为10位。 段地址转换例题2、例2，某段表的内容如下：对于段编号段长度0120k40k1760k30k2480k20k20k逻辑地址2154，与其对应的物理地址是多少？ 解：逻辑地址是段表中段编号为2比特，段内地地址为16比特，段允许的最大长度为216=210*26=1024*64=65536。 因此，逻辑地址2154 (二进制文件是100001101010 )的段编号是0，在段表格中，与其对应的物理地址为120K 2154=125034，在地址转换例题中，某虚拟存储器的用户空间为32页，分页假定分别分配给某

10、一时刻的系统的用户的第0、1、2、3页的物理块号为5、10、4、7，将虚拟地址0A5C和093C转换成物理地址。 注意，虚拟地址具有页编号5比特(25=32 )，页内位移10比特(110=1024 )，物理地址具有物理块编号4比特(24=16 )，以及块内位移(110=1024)10比特。 与虚拟地址0A5C对应的二进制文件为00010100100110000，即虚拟地址0A5C的页码为2，页内位移为1001011100，根据说明意识对应的物理地址为： 0100 1001011100、125C 同样，求093C的物理地址为293C。 省略，最佳替换算法(OPT )示例，假设系统给处理分配了三个

11、物理块，并且在处理执行的页面上有三个物理块： 1、2、3、4、1、2、5、1、2、3、4、5 再回到，注意：虽然页面访问的未来顺序很难精确地预测，因为此算法实际上是不能实现的，但是可以通过此算法评估其他算法的优劣。、1、缺口、缺口、缺口、缺口、缺口、缺口、1、2、1、2、2、1、2、2、2、2、2、2、3、3、4、4、4、4、4、4、2、5、5、5、5、5 流程执行时的页面流程为1、2、3、4、1、1，(9/12 )，假设对具有先进的先入先出算法例题、2、系统的流程分配了4个物理块，流程执行时的页面流程为1、2、3、4、1、1 、(10/12 )、先进的先入先出算法例题、3、假设系统将5个物理

12、块分配给某个进程，进程运行时的页面流程为1、2、3、4、1、2、5、1、2、3、4、5，开始时的3个物理块为(5/12 )，先进的先入先出算法_注1 :1，该算法的起点是最初调用内存的页面，无法访问的可能性很高。 2、FIFO算法虽然容易理解和编程，但效率低。 被替换的页面可能有初始化段，以前使用后不再使用，但是，存在经常访问的一组全局变量，在初始化时被存入内存中，在程序运行时使用。 先进的先入先出算法_注2 :3，先进的先入先出算法在某些情况下分配给进程的物理块数量增加，分页缺失的次数可以增加，出现了减少的奇怪现象，这种现象被称为Belady现象。 回到前面的例子，“Belady异常”与其说

13、是奇怪现象不如说是重要的提示。 操作系统学习的实际意义是操作系统是一个复杂的机构，不依赖直观的感觉。 最近最旧的未使用算法的示例：假定系统给某个处理分配了三个物理块，在执行处理时页面流动为1、2、3、4、1、2、5、1、2、3、4、5，开始时的三个物理块都是空的，最近最旧的未使用算法的示例、(10/12 )、2、盘调度算法、盘调度算法的初始盘调度算法是FCFS的最短查找时间优先SSTF扫描算法扫描(SCAN)/电梯(LOOK )阿先服务该算法，例如，假定一个请求序列： 98、183、37、122、14、124、65、67，头部的当前位置为53。 另外，FCFS先服务并按照该进程请求访问盘的顺序

14、来调度，以最短查找时间优先(SSTF )从当前头部位置选择所需的查找时间为最短的请求。 另外，假设扫描算法(SCAN )，磁头向轨道编号增加的方向移动。，假设：磁头向轨道编号增加的方向移动。，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”表示空闲。 因此，在本问题中位图所占的字符数为“500/32=16。 (2)对应于第I字的第j位的块号N=32*i j。 练习题2、例2 :某计算机系统利用下图所示的位图(行号、列号都从0开始编号)来管理空闲盘块。 如果磁盘块从1开始，则每个磁盘块的大小为1KB。 (1)现在，试着对文件分配两个磁盘块，具体说明分配过程。 (2)如何释放光盘的第300个区块？0123456789121315、01235