某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页号的序列为0，1，2，7，0，5，3，5，0，2，7，6，则进程访问上述页的过程中，产生页置换的总次数是（ ）
A.3 B.4 C.5 D.6
下面谈谈本人对LRU最近最少使用(Least Recently Used)置换算法的理解，请多多指教，这个算法也可称为【最近最久未被使用算法】。
| 首先，我们需要了解，什么是LRU页置换算法？什么是局部置换策略？ | ||||||||||||
| 题目讲到，某系统采用LRU页置换算法和局部置换策略 | 局部置换策略算法 主要用于操作系统严格隔离内存资源使用的场景，尤其是在实时系统或多任务操作系统的页面置换算法中，每个进程的物理页面分配数量在运行期间保持不变，当发生缺页时，只能在当前进程分配的页面范围内选择一个页面进行置换操作，避免因为一个进程的内存需求而影响其他进程的运行，确保关键任务的内存资源不被其他任务占用。 但无法动态调整页面分配数量，可能导致某些进程的内存利用率较低。 |
|||||||||||
局部置换策略算法分为以下几种（简单了解下就行，主要是LRU） |
||||||||||||
先进先出算法FIFO 是选择驻留时间最长的页面进行简单的置换 但可能导致 Belady 现象。 最近最少使用算法LRU(Least Recently Used) 是选择距离最近、最久未被使用的页面进行置换 但开销较大。 时钟置换算法Clock 结合了 FIFO 和 LRU 的优点 通过环形链表和访问位实现高效置换。 最不常用算法LFU 是选择访问次数最少的页面进行置换 但可能导致长期未使用的页面难以被替换。 |
||||||||||||
| 回归题目 | 【进程P访问页号的序列】如下 | |||||||||||
| 0 | 1 | 2 | 7 | 0 | 5 | 3 | 5 | 0 | 2 | 7 | 6 | |
| 若系统为进程P预分配了4个页框 | 因为 最近最久未使用算法LRU(Least Recently Used)是选择最长时间未被访问的页面进行置换， 故 我们可以反过来想 是不是从右往左数的话，在固定分配数量的物理页面范围内【固定分配数量+1那个位置】出现不同的就是参与进行置换的那个页面？ 从右往左数属于倒着推理，它因为与范围内数字都不同才会参与置换（因为固定范围限制必须挤掉范围内的1个），而它会参与置换基本就能判定那个被它置换的数之前就是那个最长时间未被访问的页面。 ======================================== 于是我们先设【进程访问上述页的过程中，产生页置换的次数】为n，这个n=0 比如从右边往左数4个页框（重复出现的不算），即 【6720】 因为【固定分配数量+1那个位置】，所以固定分配4个页框，4+1=5，所以我们要看第5个数，第5个数是5，5距离【6720】里的6最近，那么把6换掉换成5，那么换掉的这一次就算【进程访问上述页的过程中，产生页置换的1次】，故n+1=1 那么现在也就变成【5720】 继续数，第6个数是3，3距离【5720】里的2最近，那么把2换掉换成3，那么换掉的这一次就算【进程访问上述页的过程中，产生页置换的1次】，故n+1=2 那么现在也就变成【5730】 继续数，第7个数是5，而【5730】里已经有5了，故这第7个数不算，即重复的数不算。 继续数，第8个数是0，而【5730】里已经有0了，故这第8个数不算，即重复的数不算。 继续数，第9个数是7，而【5730】里已经有7了，故这第9个数不算，即重复的数不算。 继续数，第10个数是2，2距离【5730】里的3最近，那么把3换掉换成2，那么换掉的这一次就算【进程访问上述页的过程中，产生页置换的1次】，故n+1=3 那么现在也就变成【5720】 继续数，第11个数是1，1距离【5720】里的2以及0最近，但2是刚换过来的，我们要最近最久，于是我们需要换掉的是0，那么把0换掉换成1，那么换掉的这一次就算【进程访问上述页的过程中，产生页置换的1次】，故n+1=4 那么现在也就变成【5721】 继续数，第12个数是0，0距离【5721】里的2以及1最近，但1是刚换过来的，我们要最近最久，于是我们需要换掉的是2，那么把2换掉换成0，那么换掉的这一次就算【进程访问上述页的过程中，产生页置换的1次】，故n+1=5 那么现在也就变成【5701】 |
|||||||||||
| 故进程访问上述页的过程中，产生页置换的总次数n最终为5 | ||||||||||||
| 关于产生缺页的总次数 | 关于缺页，根据 在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。 所以我的理解是， 设缺页k=0 一开始是空的，4个页框都是空的，故【0127】先进来就产生4个缺页，k+4=4 下一个是0，此时0已在内存中，所以不会产生缺页 故进程访问上述页的过程中，产生缺页的总次数为9页。 |
|||||||||||