操作系统大题

在银专家算法中，若出现下述资源分派情：ProcessAllocationNeedAvailableP0003200121622P110001750P213542356P033206523P400140656试问：⑴该状态能否安全？⑵若进度P2提出恳求Request(1，2，2，2)后，系统可否将资源分派给它？⑴该状态是安全的，因为存在一个安全序列<P0P3P4P1P2>。下表为该时刻的安全序列表。资源情WorkNeedAllocatiWork+AllocatioFinis况onnh进度P01622001200321654trueP31654065203331987trueP419870656001419911trueP1199111750100029911trueP229911235613543121417true⑵若进度P2提出恳求Request(1，2，2，2)后，系统不可以将资源分派给它，若分派给进度P2，系统还剩的资源状况为（0，4，0，0），此时系统中的资源将没法知足任何一个进度的资源恳求，进而致使系统进入不安全状态，简单惹起死锁的发生。第三章相关作业和进度调动算法的习题有一个拥有两道作业的批办理系统，作业调动采纳短作业优先的调动算法，进度调动采纳抢占式的优先级调动算法，在下表的作业序列，作业优先数即为进度优先数，优先数越小优先级越高。1）列出所有作业进入内存时间及结束时间。2）计算这批作业的均匀周转时间及均匀带权周转时间。解：作业履行过程以下：8:00A抵达，内存空，A进入内存，无竞争开始运转；8:20B抵达，进入内存，优先数为2，因为A的优先数为4，对比B优先级低，被剥夺办理器，B开始运转；8:30A抵达，内存满，不行进入内存；8:50B运转结束，同时D抵达，同C抢夺内存，因为D运转时间短，依据短作业优先的调动算法，D被调入内存；D与A的优先数对比，A的优先级别高，获取办理器持续运转；9:10

A运转结束，C进入内存，C的优先级别高于

D，C开始运行；

10:00

C运转结束，

D开始运转；

10:20

D运转结束。1）所有作业进入内存时间及结束时间以下表所示：2）作业周转时间=作业结束时间-作业抵达时间这批作业的均匀周转时间=(70+30+90+90)/4=70分钟这批作业的均匀带权周转时间=(7/4+1+9/5+9/2)/4=2.有一个四道作业的操作系统，若在一段时间内先后抵达6个作业，它们的提交和预计运转时间由下表给出：采纳短作业优先调动算法，作业被调入系统后半途不会退出，但作业运转时可被更短作业抢占。（1）分别给出6个作业的开始履行时间、作业达成时间、作业周转时间。（2）计算这批作业的平均周转时间。解答：作业履行过程以下：8:00行；

J18:20

抵达，内存空，无竞争,进入内存开始运J1运转20分钟，节余40分钟；J2

抵达，运转时间为

35分钟，小于

J1，代替

J1开始运转。

8:25

J1剩

40分钟，J2

剩

30分钟；J3抵达，运转时间为20分钟，小于J2，代替J2开始运转。8:30J1剩40分钟，J2剩30分钟；J3剩15分钟；J4抵达，运转时间为25分钟，大于J3，J3持续运转。8:35J3剩10分钟；J5抵达，运转时间为5分钟，只管时间最短，可是内存中已有四道作业，所以，J5，不行进入内存，J3持续运转。8:40行。

J38:45

剩

5分钟；J6抵达，同理不行进入内存，J3持续运J3运转结束；J5最短，进入内存并开始履行。8:50J5开始履行。

运转结束；J6进入内存，运转时间10分钟，为最短，9:00J6运转结束，J1剩40分钟，J2剩30分钟；J4剩25分钟；J4最短，开始运转。9:25J4运转结束，J2最短，开始运转。9:55J2运行结束，J1开始运转。10:35J1运转结束。1）所有作业的开始履行时间、作业达成时间、作业周转时间，以下表所示：2）作业周转时间=作业结束时间-作业抵达时间这批作业的均匀周转时间=(155+95+20+55+15+20)/6=60分钟这批作业的均匀带权周转时间=(155/60+195/35+1+11/5+3+2)/4=为何要进行页面置换在恳求分页储存管理系统中，因为使用了虚构储存管理技术，使得所有的进度页面不是一次性地所有调入内存，而是部分页面装入。这就有可能出现下边的状况：要接见的页面不在内存，这时系统产生缺页中止。操作系统在办理缺页中止时，要把所需页面从外存调入到内存中。假如这时内存中有安闲块，就能够直接调入该页面；如果这时内存中没有安闲块，就一定先裁减一个已经在内存中的页面，腾出空间，再把所需的页面装入，即进行页面置换。有助于理解的重点词有：恳求分页、虚构储存、缺页中止、页面置换。常用的页面置换算法教材中介绍的常用页面置换算法有：先进先出法（FIFO）、最正确置换法（OPT）和近来最少使用置换法（LRU）。（1）先进先出法（FIFO）算法描绘：因为以为最早调入内存的页不再被使用的可能性要大于刚调入内存的页，所以，先进先出法老是裁减在内存中逗留时间最长的一页，即先进入内存的页，先被换出。先进先出法把一个进度所有在内存中的页按进入内存的序次排队，裁减页面老是在队首进行。假如一个页面刚被放入内存，就把它插在队尾。【例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算法的履行过程以以下图所示。页面块1块2221112227771112块333555111666333缺页打叉的表示发生了缺页，共缺页16次。提示：当FIFO算法履行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。依据FIFO算法，在内存中逗留时间最长的页面被裁减。三个页面在内存中的逗留时间用绿色地区标志出来了，可见，1号页面是逗留时间最长的，所以要裁减1号页面。当内存块数目分别为5时，共缺页10次。FIFO算法的履行过程以下。页面块11111666661块2222211112块333332223块44444334块5555575缺页优弊端：先进先出法（FIFO）简单易于实现，可是性能不好，存在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，2，1，2，3，6。当内存块数目分别为3，5时，试问最正确置换法（OPT）的缺页次数是多少？（注意，所有内存块最先都是空的，凡第一次用到的页面都产生一次缺页。）解：当内存块数目分别为3时，OPT算法的履行过程以以下图所示。页面块1块22222272222块3456666113缺页打叉的表示发生了缺页，共缺页11次。提示：当OPT算法履行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。依据OPT算法，在最远的未来才被接见的页面先裁减。这三个页面在未来页面走向序列的地点用绿色地区标志出来了，可见，3号页面是最晚被接见到的，所以要裁减3号页面。到了最后一个6号页面时，因为没有后续的页面序列了，能够随机选择一个页面裁减。当内存块数目分别为5时，共缺页7次。OPT算法的履行过程如下。页面块11111111块2222222块333333块44664块5575缺页优弊端：OPT算法因为要需要早先知道一个进度在整个运转过程中页面走向的所有状况，所以不过一种理想状态，实质是行不通的。一般用算法来权衡（如经过模拟实验剖析或理论剖析）其余算法的好坏。（3）近来最少使用置换法（LRU）算法描绘：近来最少使用置换法（LRU）是选择在近来一段时间里最久没有使用过的页面予以裁减。借鉴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算法的履行过程以以下图所示。页面块1块222226663333332块33111222266113缺页打叉的表示发生了缺页，共缺页15次。提示：当LRU算法履行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。依据LRU算法，在近来一段时间里最久没有使用过的页面予以裁减。这三个页面在4号页面以前的页面走向序列中的地点用绿色地区标志出来了，可见，1号页面是最久没有被使用过的，所以要裁减1号页面。当内存块数目分别为5时，共缺页8次。LRU算法的履行过程如下。页面块111111111块22222222块3336663块444334块55575缺页优弊端：LRU算法是常常采纳的页面置换算法。弊端是实现上需要大批的硬件支持。需要注意的问题1）不要把储存管理的页面置换算法与办理机调动算法混杂。有的同学可能会将FIFO和FCFS弄混，FIFO是先进先出页面置换算法，FCFS是先来先服务的作业调换算法，固然道理相像，却用在不一样的地方。2）缺页率。教材中提到了缺页率，没有给出它的观点。缺页率=缺页次数/页面总数。以上边3个例题为例，缺页率以下：算法FIFOOPTLRU内存块为316/20=80%11/20=55%15/20=75%内存块为510/20=50%7/20=35%8/20=40%影响缺页率的要素有分派给进度的内存块数和页面尺寸等。一般来说，内存块数多，页面增大，使得发生缺页的可能性降落。可是这不是绝对的，还存在着Belady现象。3）权衡页面置换算法利害的标准是：好的算法能适合减少缺页率，防止系统“颤动”。说明：以上内容仅作为教课指导资料，不作为查核内容。设正在办理器上履行的一个进度的页表以下表所示，表中的虚页号和物理块号是十进制数，开端页号（块号）均为0。所有的地点均是储存器字节地点。页的大小为1024字节。（7分）①详述在设有快表的恳求分页储存管理系统中，一个虚地点变换成物理内存地点的过程。②以下虚地点对应于什么物理地点：5499，2221。进度的页表虚页号状态