自己做商务网站有什么利弊,大型网站建设规范,全球设计在线,wordpress如何添加导航存储管理的页面置换算法 存储管理的页面置换算法在考试中常常会考到#xff0c;操作系统教材中主要介绍了3种常用的页面置换算法#xff0c;分别是#xff1a;先进先出法#xff08;FIFO#xff09;、最佳置换法#xff08;OPT#xff09;和最近最少使用置换法#xff…存储管理的页面置换算法 存储管理的页面置换算法在考试中常常会考到操作系统教材中主要介绍了3种常用的页面置换算法分别是先进先出法FIFO、最佳置换法OPT和最近最少使用置换法LRU。大家要理解3种置换算法的含义然后能熟练地运用在具体的练习中就可以了。 为什么要进行页面置换
在请求分页存储管理系统中由于使用了虚拟存储管理技术使得所有的进程页面不是一次性地全部调入内存而是部分页面装入。
这就有可能出现下面的情况要访问的页面不在内存这时系统产生缺页中断。操作系统在处理缺页中断时要把所需页面从外存调入到内存中。如果这时内存中有空闲块就可以直接调入该页面如果这时内存中没有空闲块就必须先淘汰一个已经在内存中的页面腾出空间再把所需的页面装入即进行页面置换。
有助于理解的关键词有请求分页、虚拟存储、缺页中断、页面置换。 常用的页面置换算法
教材中介绍的常用页面置换算法有先进先出法FIFO、最佳置换法OPT和最近最少使用置换法LRU。 先进先出法FIFO
算法描述由于认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页因此先进先出法总是淘汰在内存中停留时间最长的一页即先进入内存的页先被换出。先进先出法把一个进程所有在内存中的页按进入内存的次序排队淘汰页面总是在队首进行。如果一个页面刚被放入内存就把它插在队尾。
【例1】教材第4章课后习题。
考虑下述页面走向12342156212376321236。当内存块数量分别为35时试问先进先出置换算法FIFO的缺页次数是多少注意所有内存块最初都是空的凡第一次用到的页面都产生一次缺页。
解当内存块数量分别为3时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 4 4 4 6 6 6 3 3 3 2 2 2 6 块2 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1 块3 3 3 3 5 5 5 1 1 1 6 6 6 3 3 缺页 打叉的表示发生了缺页共缺页16次。
提示当FIFO算法执行到蓝色的4号页面时这时内存中有三个页面分别是123。按照FIFO算法在内存中停留时间最长的页面被淘汰。三个页面在内存中的停留时间用绿色区域标记出来了可见1号页面是停留时间最长的因此要淘汰1号页面。
当内存块数量分别为5时共缺页10次。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简单易于实现但是性能不好存在Belady现象。例如对于以下页面123412512345当内存块为3时出现9次缺页中断当内存块为4时出现10次缺页中断。缺页率随着内存块增加而增加的现象称为Belady现象。有兴趣的同学可以试一试看看是不是这样的。 最佳置换法OPT
算法描述最佳置换算法OPT在为调入新页面而必须预先淘汰某个老页面时所选择的老页面应在将来不被使用或者是在最远的将来才被访问。采用这种算法能保证有最小缺页率。
【例2】教材第4章课后习题。
考虑下述页面走向12342156212376321236。当内存块数量分别为35时试问最佳置换法OPT的缺页次数是多少注意所有内存块最初都是空的凡第一次用到的页面都产生一次缺页。
解当内存块数量分别为3时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 3 3 3 3 6 块2 2 2 2 2 2 2 7 2 2 2 块3 3 4 5 6 6 6 6 1 1 缺页 打叉的表示发生了缺页共缺页11次。
提示当OPT算法执行到蓝色的4号页面时这时内存中有三个页面分别是123。按照OPT算法在最远的将来才被访问的页面先淘汰。这三个页面在未来页面走向序列的位置用绿色区域标记出来了可见3号页面是最晚被访问到的因此要淘汰3号页面。到了最后一个6号页面时由于没有后续的页面序列了可以随机选择一个页面淘汰。
当内存块数量分别为5时共缺页7次。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
算法描述最近最少使用置换法LRU是选择在最近一段时间里最久没有使用过的页面予以淘汰。借鉴FIFO算法和OPT算法以“最近的过去”作为“不久将来”的近似。
【例3】教材第4章课后习题。
考虑下述页面走向12342156212376321236。当内存块数量分别为35时试问最近最少使用置换法LRU的缺页次数是多少注意所有内存块最初都是空的凡第一次用到的页面都产生一次缺页。
解当内存块数量分别为3时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 4 4 5 5 5 1 1 7 7 2 2 2 块2 2 2 2 2 2 6 6 6 3 3 3 3 3 3 块3 3 3 1 1 1 2 2 2 2 6 6 1 1 缺页 打叉的表示发生了缺页共缺页15次。
提示当LRU算法执行到蓝色的4号页面时这时内存中有三个页面分别是123。按照LRU算法在最近一段时间里最久没有使用过的页面予以淘汰。这三个页面在4号页面之前的页面走向序列中的位置用绿色区域标记出来了可见1号页面是最久没有被使用过的因此要淘汰1号页面。
当内存块数量分别为5时共缺页8次。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 4 3 3 块5 5 5 5 7 缺页 优缺点LRU算法是经常采用的页面置换算法。缺点是实现上需要大量的硬件支持。 3. 需要注意的问题 不要把存储管理的页面置换算法与处理机调度算法混淆。有的同学可能会将FIFO和FCFS弄混FIFO是先进先出页面置换算法FCFS是先来先服务的作业调动算法虽然道理相似却用在不同的地方。 缺页率。教材中提到了缺页率没有给出它的概念。缺页率缺页次数/页面总数。以上面3个例题为例缺页率如下 算法 FIFO OPT LRU 内存块为3 16/2080% 11/2055% 15/2075% 内存块为5 10/2050% 7/2035% 8/2040% 影响缺页率的因素有分配给进程的内存块数和页面尺寸等。一般来说内存块数多页面增大使得发生缺页的可能性下降。但是这不是绝对的还存在着Belady现象。
3衡量页面置换算法好坏的标准是好的算法能适当减少缺页率避免系统“抖动”。 说明以上内容仅作为教学辅导材料不作为考核内容。
