操作系统作业与讲评2.docVIP

操作系统作业点评二 为什么要进行页面置换 在请求分页存储管理系统中，由于使用了虚拟存储管理技术，使得所有的进程页面不是一次性地全部调入内存，而是部分页面装入。 这就有可能出现下面的情况：要访问的页面不在内存，这时系统产生缺页中断。操作系统在处理缺页中断时，要把所需页面从外存调入到内存中。如果这时内存中有空闲块，就可以直接调入该页面；如果这时内存中没有空闲块，就必须先淘汰一个已经在内存中的页面，腾出空间，再把所需的页面装入，即进行页面置换。 有助于理解的关键词有：请求分页、虚拟存储、缺页中断、页面置换。 常用的页面置换算法 教材中介绍的常用页面置换算法有：先进先出法（FIFO）、最佳置换法（OPT）和最近最少使用置换法（LRU）。 先进先出法（FIFO） 算法描述：由于认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。法把一个进程所有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。如果一个页面刚被放入内存，就把它插在队尾。考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3，5时，试问置换算法FIFO）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）当内存块数量分别为3时，FIFOFIFO算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照FIFO算法，在内存中停留时间最长的页面被淘汰。三个页面在内存中的停留时间用绿色区域标记出来了，可见，1号页面是停留时间最长的，因此要淘汰1号页面。 当内存块数量分别为时，FIFO算法的执行过程如下。 页面 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 块1 1 1 1 1 1 6 6 6 6 6 块2 2 2 2 2 2 1 1 1 1 块3 3 3 3 3 3 2 2 2 块4 4 4 4 4 4 3 3 块5 5 5 5 5 5 7 缺页 ( ( ( ( ( ( ( ( ( ( 优缺点：先进先出法（FIFO）简单。最佳置换算法（OPT）为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。采用这种算法，能保证有最小缺页率。 考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3，5时，试问法OPT）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）当内存块数量分别为3时，OPTOPT算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照OPT算法，在最远的将来才被访问当内存块数量分别为时，OPT算法的执行过程如下。 页面 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 块1 1 1 1 1 1 1 1 块2 2 2 2 2 2 2 块3 3 3 3 3 3 块4 4 4 6 6 块5 5 5 7 缺页 ( ( ( ( ( ( ( 优缺点：OPT算法因为需要预先知道一个进程整个运行过程中页面走向的全部情况。算法来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。 最近最少使用法（LRU）选择在最近一段时间里最久没有使用过的页面予以淘汰以“最近的过去”作为“不久将来”的近似考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3，5时，试问最近最少使用法LRU）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。）当内存块数量分别为3时，LRULRU算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。按照LRU算法，在最近一段时间里最久没有使用过的页面予以淘汰当内存块数量分别为时，LRU算法的执行过程如下。 页面 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 块1 1 1 1 1 1 1 1 1 块2 2 2 2 2 2 2 2 块3 3 3 3 6 6 6 块4 4 4