操作系统大题

1、.22. 在银行家算法中，若出现下述资源分配情：ProcessAllocationNeedAvailableP22P110001750P213542356P303320652P400140656试问： 该状态是否安全？ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？该状态是安全的，因为存在一个安全序列。下表为该时刻的安全序列表。资源情况进程WorkNeedAllocationWork+AllocationFinishP0P3P4P1P21 6 2 21 6 5 41 9 8 71 9 9 112 9 9 110 0 1 20 6 5 20 6 5 61 7 5

2、02 3 5 60 0 3 20 3 3 30 0 1 41 0 0 01 3 5 41 6 5 41 9 8 71 9 9 112 9 9 113 12 14 17truetruetruetruetrue 若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。第三章有关作业和进程调度算法的习题1.有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用抢占式的优先级调度算法，在下表的作业序列，

3、作业优先数即为进程优先数，优先数越小优先级越高。（1）列出所有作业进入内存时间及结束时间。（2）计算这批作业的平均周转时间及平均带权周转时间。解：作业执行过程如下：8:00A到达，内存空，A进入内存，无竞争开始运行；8:20B到达，进入内存，优先数为2，由于A的优先数为4，相比B优先级低，被剥夺处理器，B开始运行；8:30A到达，内存满，不可进入内存；8:50B运行结束，同时D到达，同C争夺内存，由于D运行时间短，按照短作业优先的调度算法，D被调入内存；D与A的优先数相比，A的优先级别高，获得处理器继续运行；9:10A运行结束，C进入内存，C的优先级别高于D，C开始运行；10:00C运行结束，

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

5、进入内存开始运行；8:20J1运行20分钟，剩余40分钟；J2到达，运行时间为35分钟，小于J1，取代J1开始运行。8:25J1剩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:40J3剩5分钟；J6到达，同理不可进入内存，J3继续运行。8:45J3运行结束；J5最短，进入内存并开始执行。8:50J5运行结束；J6进入

6、内存，运行时间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=4.011. 为什么要进行页面置换在请求分页存储管理系统中，由于使用了虚拟存储管理技术，使

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

8、页不再被使用的可能性要大于刚调入内存的页，因此，先进先出法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。先进先出法把一个进程所有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。如果一个页面刚被放入内存，就把它插在队尾。【例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算法的执行过程如下图所示。页面12342123

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

10、）简单易于实现，但是性能不好，存在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，

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

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

13、】教材第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算法的执行过程如下图所示。页面123421236块1111445551177222块222222666333333块33311122226611缺页打叉的表示发生了缺页，共缺页15次。提示：当LRU算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照LRU算法，在最近一段时间里最

14、久没有使用过的页面予以淘汰。这三个页面在4号页面之前的页面走向序列中的位置用绿色区域标记出来了，可见，1号页面是最久没有被使用过的，因此要淘汰1号页面。当内存块数量分别为5时，共缺页8次。LRU算法的执行过程如下。页面123421236块111111111块22222222块3333666块444433块55557缺页 优缺点：LRU算法是经常采用的页面置换算法。缺点是实现上需要大量的硬件支持。 3. 需要注意的问题（1） 不要把存储管理的页面置换算法与处理机调度算法混淆。有的同学可能会将FIFO和FCFS弄混，FIFO是先进先出页面置换算法，FCFS是先来先服务的作业调动算法，虽然道理相似，

15、却用在不同的地方。（2） 缺页率。教材中提到了缺页率，没有给出它的概念。缺页率=缺页次数/页面总数。以上面3个例题为例，缺页率如下：算法FIFOOPT LRU内存块为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。进程的页表虚页号状态位访问位