nru置换算法c语言,页面置换算法及例题(示例代码)

一、页面置换算法

不适当的算法可能会导致进程发生“抖动”：即刚被换出的页很快又要被访问，需要将他重新调入，此时又需要再选一页调出。而此刚被调出的页面很快又被访问，又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上，我们称该进程发生了“抖动”。

一个好的页面置换算法应该具有较低地页面更换频率。从理论上讲，应将哪些以后不再会访问地页面换出，或把那些在较长时间内不会再访问的页面调出。目前已有多种置换算法，他们都试图更接近于理论上的目标。下面介绍几种常用的置换算法。

二、常用的页面置换算法

1.最佳(Optimal)置换算法

其所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，是理想化的算法(因为我们很难预知未来要访问哪些页面)，可以用来评测其他实际应用算法的好坏。

2.先进先出(FIFO)置换算法

总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面给予淘汰(由于与页面的使用规律不符，可能是性能最差的算法)。

3.最近最久未使用LRU(Least Recently Used)置换算法

选择最近最久未使用的页面予以淘汰。

4.最少使用LFU(Least Frequently Used)置换算法

选择在最近时期使用最少的页面作为淘汰页(当使用次数相同时，谁最先来淘汰谁)。

5.Clocks置换算法

(1)简单的Clocks置换算法(最近未使用NRU(Not Recently Used)算法)

为每一页设置一个访问位，再将内存中所有页面通过指针链接成一个循环队列。当某页被访问时，其访问位置1。在选择某一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出，若为1，则重新将他置0，暂不换出，给予该页第二次驻留内存的机会，再检查下一个页面。当检查到队列中最后一个页面时，若访问位仍为1，则再返回队首去检查第一个页面。

图为简单Clocks算法的流程示意图

(2)改进型Clocks置换算法

在简单型的基础上再增加一个修改位M，组合成四类页面：

①(A=0，M=0)：表明该页最近既未被访问，又未被修改，是最佳淘汰页

②(A=0，M=1)：表明该页最近未被访问，但已被修改，并不是很好的淘汰页

③(A=1，M=0)：表明该页最近已被访问，但未被修改，该页有可能再被访问

④(A=1，M=1)：表明该页最近已被访问且被修改，该页可能再被访问

算法执行过程可以总结如下：

<1>指针从当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A

<2>第一步失败，则进行第二轮扫描，寻找A=0且M=1的第二页页面，将所遇到的第一个这类页面作为淘汰页，在第二轮扫描期间，将所有扫描过的页面的访问位都置0

<3>第二步失败，则指针返回开始位置，并将所有访问位复0，重复第一步，若仍失败，再重复第二步，一定能找到被淘汰的页

三、页面置换算法举例

1.最佳分配置换算法

插入顺序

1

2

3

4

1

2

5

1

2

3

4

5

内存

1

1

1

1

1

1

1

1

1

3

3

3

2

2

2

2

2

2

2

2

2

4

4

3

4

4

4

5

5

5

5

5

5

是否缺页

+

+

+

+

+

+

+

理想条件下缺页次数为7次，缺页率为7/12

2.先进先出置换算法

插入顺序

1

2

3

4

1

2

5

1

2

3

4

5

内存

1

1

1

4

4

4

5

5

5

5

5

5

2

2

2

1

1

1

1

1

3

3

3

3

3

3

2

2

2

2

2

4

4

是否缺页

+

+

+

+

+

+

+

+

+

缺页次数为9次，缺页率为3/4

3.最久未使用置换算法

插入顺序

1

2

3

4

1

2

5

1

2

3

4

5

内存

1

1

1

4

4

4

5

5

5

3

3

3

2

2

2

1

1

1

1

1

1

4

4

3

3

3

2

2

2

2

2

2

5

是否缺页

+

+

+

+

+

+

+

+

+

+

缺页率次数为10次，缺页率为5/6

4.简单Clocks置换算法

插入顺序

1

2

3

4

1

2

5

1

2

3

4

5

内存

1

A=0

1

A=0

1

A=0

4

A=0

4

A=0

4

A=0

5

A=0

5

A=0

5

A=0

3

A=0

4

A=0

4

A=1

A=0

2

A=0

2

A=0

2

A=0

1

A=0

1

A=0

1

A=0

1

A=1

1

A=1

1

A=1

1

A=0

5

A=0

A=0

A=0

3

A=0

3

A=0

3

A=0

2

A=0

2

A=0

2

A=0

2

A=1

2

A=1

2

A=0

2

A=0

是否缺页

+

+

+

+

+

+

+

+

+

+

缺页次数为10次，缺页率为5/6