操作系统大题

1、试问：ProcessAllocatio nNeedAvailab lePo003200121622Pi10001750R13542356R03320652R0014065622.在银行家算法中，若出现下述资源分配情:该状态是否安全？若进程P2提出请求Request。，2，2，2）后，系统能否将资源分配给它？该状态是安全的，因为存在一个安全序列< PoRRPiR>。下表为该时刻的安全序列表资源情 况 进程WorkNeedAllocati onWork+AllocationFi nis hR1 6 2 20 0 1 20 0 3 21 6 5 4trueP31 6 5 40 6 5 2

2、0 3 3 31 9 8 7trueR1 9 8 70 6 5 60 0 1 41 9 9 11truePl1 9 9 111 7 5 01 0 0 02 9 9 11trueP22 9 9 112 3 5 61 3 5 4312 14 17true若进程P2提出请求Request。, 2, 2, 2)后，系统不能将 资源分配给它，若分配给进程P2,系统还剩的资源情况为(0, 4, 0, 0)，此时系统中的资源将无法满足任何一个进程的资源请求， 从而导致系统进入不安全状态，容易引起死锁的发生。第三章 有关作业和进程调度算法的习题1.有一个具有两道作业的批处理系统，作业调度采用短作业优 先的调度

3、算法，进程调度采用抢占式的优先级调度算法，在下表 的作业序列，作业优先数即为进程优先数，优先数越小优先级越作业名到达时间估计运行时间优先数4SdkO40分钟4B8:2030分钟2C8:3050分钟3D8:5020分钟5(1)列出所有作业进入内存时间及结束时间2)计算这批作业的平均周转时间及平均带权周转时间解：作业执行过程如下：8:00A到达，内存空，A进入内存,无竞争开始运行；8:20B 到达,进入内存,优先数为2，由于A的优先数为4,相比B优先级低，被剥夺处理器，B开始运行；8:30 A到达， 内存满，不可进入内存；8:50B运行结束，同时D到达，同C争夺内存，由于D运行时间短，按照短作业优

4、先的调度算法，D被调入内存；D与A的优先数相比，A的优先级别高，获得处理器 继续运行；9:10 A运行结束，C进入内存，C的优先级别高于D, C开始运 行；10:00 C运行结束，D开始运行； 10:20 D运行结 束。1 ) 所 有 作 业 进 入 内 存 时 间 及 结 束 时 间 如 下 表 所 示：作业到达时间进入内存时间结束时，可执行时间（分钟周转时间（分钟）舄权周转时间（分钟）A8:008:009:104070B8:208:20*:5030301C8:309:1010:0050909/5D8:508:5010:2020909/22）作业周转时间二作业结束时间-作业到达时间这批作业的

5、平均周转时间=（70+30+90+90）/4=70分钟 这批作业 的平均带权周转时间=（7/4+1+9/5+9/2）/4二2.有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：作业提交时间估计运行时间（分钟）J18:0060J28:2035J38:2520J48:3025J58:355J68:4010采用短作业优先调度算法，作业被调入系统后中途不会退出，但 作业运行时可被更短作业抢占。 （1）分别给出 6 个作业的开始执 行时间、作业完成时间、作业周转时间。 （ 2）计算这批作业的平 均周转时间。 解答：作业执行过程如下：8:00 J1 到 达 ，

6、内 存 空 ， 无 竞 争 , 进 入 内 存 开 始 运 行； 8:20J1 运行 20 分钟，剩余 40分钟；J2到达，运行时间为35分钟，小于J1，取代J1 开始运行。 8:25 J1 剩 40分钟， J2 剩 30分钟；J3到达，运行时间为20分钟，小于J2,取代J2开始运行。8:30 J1剩40分钟，J2剩30分钟；J3剩15分钟；J4 到达，运行时间为 25分钟， 大于 J3， J3 继续运行。8:35 J3 剩 10分钟；J5 到达，运行时间为 5 分钟，尽管时间最短， 但是内存中已有四道作业，因此，J5,不可进入内存，J3继续运行。8:40 J3 剩 5 分钟； J6 到达，同

7、理不可进入内存， J3 继续运 行。 8:45 J3 运行结束； J5 最短，进入内存并开始执行。8:50 J5运行结束；J6进入内存，运行时间10分钟，为最短, 开始执行。9:00 J6运行结束，J1剩40分钟，J2剩30分钟; J4剩25分钟；J4最短，开始运行。9:25J4运行结束，J2最短，开始运行。9:55J2运行结束，J1开始运行。 10:35 J1运行结束1）所有作业的开始执行时间、作业完成时间、作业周转时间,如下表所示作业提交时运厅时间开始执完成时周转时间平均周转时间（分钟）行时间间（分钟间（分钟）J18:00608:0010:35155155/60J28:2035S:209:

8、559595/35J38:25203:258:45201.T48:30259:009:255511/5J58:358:458:50153JG«：41>108:509:002Q22）作业周转时间二作业结束时间-作业到达时间这批作业的平均周转时 间=（155+95+20+55+15+20）/6=60 分钟 这批作业的平均带权周转时间=(155/60+195/35+1 + 11/5+3+2)/4=1. 为什么要进行页面置换在请求分页存储管理系统中， 由于使用了虚拟存储管理技术， 使 得所有的进程页面不是一次性地全部调入内存，而是部分页面装入。这就有可能出现下面的情况： 要访问的页面不

9、在内存， 这时系统 产生缺页中断。 操作系统在处理缺页中断时， 要把所需页面从外存调 入到内存中。如果这时内存中有空闲块，就可以直接调入该页面；如 果这时内存中没有空闲块，就必须先淘汰一个已经在内存中的页面， 腾出空间，再把所需的页面装入，即进行页面置换。有助于理解的关键词有：请求分页、虚拟存储、缺页中断、页面 置换。2. 常用的页面置换算法教材中介绍的常用页面置换算法有：先进先出法（FIFO）、最佳置换法（OPT和最近最少使用置换法（LRU。（1）先进先出法（ FIFO）算法描述： 由于认为最早调入内存的页不再被使用的可能性要大 于刚调入内存的页， 因此，先进先出法总是淘汰在内存中停留时间最

10、 长的一页，即先进入内存的页，先被换出。先进先出法把一个进程所 有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。 如果一个页面刚被放入内存，就把它插在队尾。【例1】教材第4章课后习题考虑下述页面走向：1, 2,3,4,2, 1,5,6,2, 1,2,3, 7,6, 3, 2, 1, 2, 3, 6。当内存块数量分别为3, 5时，试问先进先出 置换算法（FIFO）的缺页次数是多少？（注意，所有内存块最初都是 空的，凡第一次用到的页面都产生一次缺页。）解：当内存块数量分别为3时，FIFO算法的执行过程如下图所示。页面12342156212376321236块11114446663332

11、226块2222111222777111块333355511166633缺页打叉的表示发生了缺页，共缺页16次提示：当FIFO算法执行到蓝色的4号页面时，这时内存中有三 个页面，分别是1, 2, 3。按照FIFO算法，在内存中停留时间最长 的页面被淘汰。三个页面在内存中的停留时间用绿色区域标记出来 了，可见，1号页面是停留时间最长的，因此要淘汰 1号页面。当内存块数量分别为5时，共缺页10次。FIFO算法的执行过程如下页面12342156212376321236块11111166666块2222221111块333333222块44444433块5555557缺页优缺点：先进先出法（FIFO）

12、简单易于实现，但是性能不好，存 在Belady现象。例如对于以下页面：1，2, 3, 4，1，2, 5，1，2, 3，4，5，当内存块为3时，出现9次缺页中断；当内存块为4时， 出现10次缺页中断。缺页率随着内存块增加而增加的现象，称为 Belady现象。有兴趣的同学可以试一试，看看是不是这样的。（2）最佳置换法（OPT算法描述：最佳置换算法（OPT在为调入新页面而必须预先淘 汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远 的将来才被访问。采用这种算法，能保证有最小缺页率。【例2】教材第4章课后习题。考虑下述页面走向：1,2，3,4,2，1，5，6,2，1，2，3,7,6，3,

13、2, 1, 2, 3, 6。当内存块数量分别为3, 5时，试问最佳置换 法（OPT的缺页次数是多少？（注意，所有内存块最初都是空的， 凡第一次用到的页面都产生一次缺页。）解：当内存块数量分别为3时，OPT算法的执行过程如下图所示页面12342 156212376321236块111111133336块22222227222块3345666611缺页打叉的表示发生了缺页，共缺页11次提示：当OPT算法执行到蓝色的4号页面时，这时内存中有三个 页面，分别是1, 2, 3。按照OPT算法，在最远的将来才被访问的页 面先淘汰。这三个页面在未来页面走向序列的位置用绿色区域标记出 来了，可见，3号页面是最

14、晚被访问到的，因此要淘汰 3号页面。到 了最后一个6号页面时，由于没有后续的页面序列了，可以随机选择 一个页面淘汰。当内存块数量分别为5时，共缺页7次。OPT算法的执行过程如下。页面12342156212376321236块11111111块2222222块333333块44466块5557缺页优缺点：OPT算法因为要需要预先知道一个进程在整个运行过程中页面走向的全部情况，因此只是一种理想状态，实际是行不通的。 一般用算法来衡量（如通过模拟实验分析或理论分析） 其他算法的优 劣。（3）最近最少使用置换法（LRU算法描述：最近最少使用置换法（LRU是选择在最近一段时间 里最久没有使用过的页面予以

15、淘汰。借鉴 FIFO算法和OPT算法，以 “最近的过去”作为“不久将来”的近似。【例3】教材第4章课后习题。考虑下述页面走向：1,2，3,4,2，1，5，6,2，1，2，3,7,6，3, 2, 1, 2, 3, 6。当内存块数量分别为3, 5时，试问最近最少 使用置换法（LRU的缺页次数是多少？（注意，所有内存块最初都 是空的，凡第一次用到的页面都产生一次缺页。）解：当内存块数量分别为3时，LRU算法的执行过程如下图所示页面12342156212376321236块1111445551177222块222222666333333块33311122226611提示：当LRU算法执行到蓝色的4号页

16、面时，这时内存中有三个 页面，分别是1, 2, 3。按照LRU算法，在最近一段时间里最久没有 使用过的页面予以淘汰。这三个页面在4号页面之前的页面走向序列 中的位置用绿色区域标记出来了，可见，1号页面是最久没有被使用 过的，因此要淘汰1号页面。当内存块数量分别为5时，共缺页8次。LRU算法的执行过程如下。页面12342156212376321236块111111111块22222222块3333666块444433块55557要大量的硬件支持3. 需要注意的问题（1）不要把存储管理的页面置换算法与处理机调度算法混淆。 有的同学可能会将FIFO和FCFS弄混，FIFO是先进先出页面置换算 法，F

17、CFS是先来先服务的作业调动算法，虽然道理相似，却用在不 同的地方。（2）缺页率。教材中提到了缺页率，没有给出它的概念。缺页 率二缺页次数/页面总数。以上面3个例题为例，缺页率如下：算法FIFOOPTLRU内存块为316/20=80%11/20=55%15/20=75%内存块为510/20=50%7/20=35%8/20=40%影响缺页率的因素有分配给进程的内存块数和页面尺寸等。一般来说，内存块数多，页面增大，使得发生缺页的可能性下降。但是这 不是绝对的，还存在着 Belady现象。（3）衡量页面置换算法好坏的标准是：好的算法能适当减少缺 页率，避免系统“抖动”。说明：以上内容仅作为教学辅导材料，不作为考核内容27.设正在处理器上执行的一个进程的页表如下表所示，表中的虚页 号和物理块号是十进制数，起始页号（块号）均为0。所有的地址均是存储器字节地址。页的大小为1024字节。（7分） 详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。 下列虚地址对应于什么物理地址：5499, 2221。进程的页表虚页号状态位访问位修改位