LRU 算法

LRU页面置换算法模拟 

 

一、设计目的

1、用C语言实现最近最久未使用（LRU）置换算法。

2、了解内存分页管理策略

3、掌握调页策略

4、掌握一般常用的调度算法

5、选取调度算法中的典型算法，模拟实现

 

二、设计任务

在Window98/2000 系统的TC2.0环境下运行程序；通过从一般常用的调页算法中选取典型算法LRU，了解页面管理的相关细节，并用程序设计实现LRU。

 

三、设计内容与步骤

分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。

一、调页策略

1)何时调入页面

如 果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访 问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很 有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

2)请求调页策略

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。

2、从何处调入页面

       在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：

(1)    系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。

(2)    系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。

(3)    UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。

3页面调入过程

       每当程序所要访问的页面未在内存时， 便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外在原物理 块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

二、页面置换算法

       在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。

       一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。

㈠常见置换算法

①     最佳置换算法(Optimal)：

它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。

②     先进先出(FIFO)页面置换算法：

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

③     LRU置换算法：这是本次设计的重点。

④     CLOCK置换算法：a,简单CLOCK置换算法；b,改进型CLOCK算法。LRU算法是较好的一种算法，而由于LRU在硬件上要求较多，在实际应用中多采用LRU的近似算法。CLOCK算法就是用得较多的一种LRU近似算法。

⑤     最少使用(LFU:Least Frequently Used)置换算法：在采用该算法时，应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。

⑥     页面缓冲算法(PBA：Page Buffering Algorithm)

㈡、最近最久未使用置换算法

LRU(Least Recently Used)置换算法的描述

       FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

2、LRU置换算法的硬件支持

　    LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：

1）  寄存器

       为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为

       R=R_n-1R_n-2R_n-3……R₂R₁R₀ 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为1˜˜8。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。

R   实   页	R7	R6	R5	R4	R3	R2	R1	R0
1	0	1	0	1	0	0	1	0
2	1	0	1	0	1	1	0	0
3	0	0	0	0	0	1	0	0
4	0	1	1	0	1	0	1	1
5	1	1	0	1	0	1	1	0
6	0	0	1	0	1	0	1	1
7	0	0	0	0	0	1	1	1
8	0	1	1	0	1	1	0	1

2)栈

       可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。

(三)、程序设计流程图

(四) LRU算法实现。

#include

#include

 

#define M 4

#define N 17

#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")      /*表格控制*/

typedef struct page

{

       int num;  /*记录页面号*/

       int time;   /*记录调入内存时间*/

}Page;                   /* 页面逻辑结构，结构为方便算法实现设计*/

 

Page b[M];            /*内存单元数*/

int c[M][N];   /*暂保存内存当前的状态：缓冲区*/

int queue[100];       /*记录调入队列*/

int K;             /*调入队列计数变量*/

 

/*初始化内存单元、缓冲区*/

void Init(Page *b,int c[M][N])

{

       int i,j;

       for(i=0;i

       {

              b[i].num=-1;

              b[i].time=N-i-1;

       }

       for(i=0;i

              for(j=0;j

                     c[i][j]=-1;

}

 

/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/

int GetMax(Page *b)

{

       int i;

       int max=-1;

       int tag=0;

       for(i=0;i

       {

              if(b[i].time>max)

              {

                     max=b[i].time;

                     tag=i;

              }

       }

       return tag;

}

 

/*判断页面是否已在内存中*/

int    Equation(int fold,Page *b)

{

       int i;

       for(i=0;i

       {

              if (fold==b[i].num)

                     return i;

       }

       return -1;

}

/*LRU核心部分*/

void Lru(int fold,Page *b)

{

       int i;

       int val;

       val=Equation(fold,b);

       if (val>=0)

       {

              b[val].time=0;

              for(i=0;i

                     if (i!=val)

                            b[i].time++;

       }

       else

       {

              queue[++K]=fold;/*记录调入页面*/

              val=GetMax(b);

              b[val].num=fold;

              b[val].time=0;

              for(i=0;i

                     if (i!=val)

                            b[i].time++;

       }

}

 

/*主程序*/

void main()

{

       int a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};

       int i,j;

 

start:

       K=-1;

       Init(b, c);

       for(i=0;i

       {

              Lru(a[i],b);

              c[0][i]=a[i];

              /*记录当前的内存单元中的页面*/

              for(j=0;j

                     c[j][i]=b[j].num;

       }

       /*结果输出*/

       printf("内存状态为：\n");

       Myprintf;

       for(j=0;j

              printf("|%2d ",a[j]);

       printf("|\n");

       Myprintf;

       for(i=0;i

       {     for(j=0;j

              {

              if(c[i][j]==-1)

                     printf("|%2c ",32);

              else

                     printf("|%2d ",c[i][j]);

              }

              printf("|\n");

       }

       Myprintf;

       printf("\n调入队列为:");

       for(i=0;i

              printf("%3d",queue[i]);

       printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/N);

       printf("\nAre you continuing!\ty?");

       if(getche()=='y')

              goto start;

}

 

 

四、测试与评价

1、程序运行结果输出

内存状态为：

|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|

| 1 | 0 | 1 | 0 | 2 | 4 | 1 | 0 | 0 | 8 | 7 | 5 | 4 | 3 | 2 | 3 | 4 |

|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|

| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 |

|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 |

|   |   |   |   | 2 | 2 | 2 | 2 | 2 | 8 | 8 | 8 | 8 | 3 | 3 | 3 | 3 |

|   |   |   |   |   | 4 | 4 | 4 | 4 | 4 | 7 | 7 | 7 | 7 | 2 | 2 | 2 |

|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|

 

调入队列为:  1  0  2  4  8  7  5  4  3  2

缺页次数为：    10

缺页率：        0.588235

Are you continuing!     y?

2、  程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，页面都必须更新这些记录项。这个记录项在此程序中为

typedef struct page

{

       int num;  /*记录页面号*/

       int time;   /*记录调入内存时间*/

}Page;                   /* 页面逻辑结构，结构为方便算法实现设计*/

如此显然要花费较大的系统开销(包括时间和空间上的)，这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因，但由于其在页面置换的优越性，实际系统常使用LRU的近似算法。

3、由于程序旨在页面置换算法的模拟，程序并没有设计自动执行的功能，这也是本设计的缺陷。