LRU在C语言下的实现

Author：碧云天
发布时间：December 4, 2019
3887 views
No comments
2612 words
Categories： C

### 什么是LRU算法

LRU是 `Least Recently Used` 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 `t`，当须淘汰一个页面时，选择现有页面中其 `t` 值最大的，即最近最少使用的页面予以淘汰。--（百度百科）

### 实现过程

- 结构体声明

```c
typedef struct{
    int page_id;//page id, -1 is not use page
    int ex_time;//existence time, -1 is not use
}PageBlock, *pPageBlock;//memory block
```

> `page_id` 表示当前块转载页面的页面号     
`ex_time` 表示从上一次访问到现在经历的时间

- 全局变量声明

```c
pPageBlock blocks;//define blocks

int adjust[PAGES_NUMS] = {3, 2, 1, 6, 1, 2, 3, 4, 6, 3}; 
```

> `blocks` 表示块列表     
`adjust` 转载任务数组

- 方法定义

```c
void init();//init blocks block

int getFreeBlock();//get free block

int getLRBlock();//get LRU block

int checkInBlocks(int num);//check if the adjust_page is in blocks

void timeUpdate();//update save time

void LRU();//LRU algorithm run function
```

> `init` 初始化块列表     
`getFreeBlock` 取得空闲块   
`getLRBlock` 取得最近最短未使用的块   
`checkInBlocks` 检查一个任务是否在块中   
`timeUpdate` 更新块的存在时间    
`LRU` LRU主函数

- 代码整合

```c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define PAGES_NUMS 10
#define MAX_BLOCK_NUMS 3
#define _for(i,a,b) for(int i = (a); i < b; ++i)
#define _rep(i,a,b) for(int i = (a); i <= b; ++i)
typedef struct{
    int page_id;//page id, -1 is not use page
    int ex_time;//existence time, -1 is not use
}PageBlock, *pPageBlock;//memory block
pPageBlock blocks;//define blocks
int adjust[PAGES_NUMS] = {3, 2, 1, 6, 1, 2, 3, 4, 6, 3};
int replace = 0;
void init()//init blocks block
{
    blocks = (pPageBlock)malloc(sizeof(PageBlock) * MAX_BLOCK_NUMS);
    _for(i,0,MAX_BLOCK_NUMS)
    {
        blocks[i].ex_time = blocks[i].page_id = -1;
    }
    replace = 0;
}
int getFreeBlock()//get free block
{
    _for(i,0,MAX_BLOCK_NUMS)
    {
        if(blocks[i].page_id == -1)
        {
            return i;
        }
    }
    return -1;
}
int getLRBlock()//get LRU block
{
    int idx = 0;
    _for(i,1,MAX_BLOCK_NUMS)
    {
        if(blocks[i].ex_time > blocks[idx].ex_time)
        {
            idx = i;
        }
    }
    return idx;
}
int checkInBlocks(int num)//check if the adjust_page is in blocks
{
    _for(i,0,MAX_BLOCK_NUMS)
    {
        if(blocks[i].page_id == num)
        {
            blocks[i].ex_time = 0;
            return 1;
        }
    }
    return 0;
}
void timeUpdate()//update save time
{
    _for(i,0,MAX_BLOCK_NUMS)
    {
        if(blocks[i].page_id != -1)
        {
            ++blocks[i].ex_time;
        }
    }
}
void LRU()
{
    int loss_page_count = 0;
    double loss_page_rate;
    int idx = 0;
    _for(i,0,PAGES_NUMS)
    {
        timeUpdate();
        int flag = 0;
        if(!checkInBlocks(adjust[i]))//check if the adjust[i] is in blocks
        {
            ++loss_page_count;
            idx = getFreeBlock();
            if(idx == -1)//if not have free blocks
            {
                idx = getLRBlock();//replace new idx from LRUBlock
            }
            blocks[idx].page_id = adjust[i];
            blocks[idx].ex_time = 0;
            flag = 1;
        }
        // view the replacement process / per round
        printf("round %d:\n", i+1);
        _for(j,0,MAX_BLOCK_NUMS)
        {
            printf("blocks[%d] -> id: %2d  time: %2d  ", j, blocks[j].page_id, blocks[j].ex_time);
            if(flag && idx == j) printf("<--");
            printf("\n");
        }

printf("\n");
    }
    loss_page_rate = 1.0*loss_page_count / PAGES_NUMS;
    printf("loss page count: %d\n", loss_page_count);
    printf("loss page rate : %.3lf\n", loss_page_rate);
}
int main()
{
    init();
    LRU();
    return 0;
}
```
> 编译 `gcc LRU.c -o LRU`    
运行:Windows `LRU`, Linux `./LRU`

### 运行结果
实验采用的内存块数为三块，试验任务十个，分别为 `{3, 2, 1, 6, 1, 2, 3, 4, 6, 3}`  
手动计算目标结果：
> 缺页次数：7   
缺页率：0.7

代码运行结果：   
```c
round 1:
blocks[0] -> id:  3  time:  0  <--
blocks[1] -> id: -1  time: -1
blocks[2] -> id: -1  time: -1

round 2:
blocks[0] -> id:  3  time:  1
blocks[1] -> id:  2  time:  0  <--
blocks[2] -> id: -1  time: -1

round 3:
blocks[0] -> id:  3  time:  2
blocks[1] -> id:  2  time:  1
blocks[2] -> id:  1  time:  0  <--

round 4:
blocks[0] -> id:  6  time:  0  <--
blocks[1] -> id:  2  time:  2
blocks[2] -> id:  1  time:  1

round 5:
blocks[0] -> id:  6  time:  1
blocks[1] -> id:  2  time:  3
blocks[2] -> id:  1  time:  0

round 6:
blocks[0] -> id:  6  time:  2  
blocks[1] -> id:  2  time:  0
blocks[2] -> id:  1  time:  1

round 7:
blocks[0] -> id:  3  time:  0  <--
blocks[1] -> id:  2  time:  1
blocks[2] -> id:  1  time:  2

round 8:
blocks[0] -> id:  3  time:  1
blocks[1] -> id:  2  time:  2
blocks[2] -> id:  4  time:  0  <--

round 9:
blocks[0] -> id:  3  time:  2
blocks[1] -> id:  6  time:  0  <--
blocks[2] -> id:  4  time:  1

round 10:
blocks[0] -> id:  3  time:  0
blocks[1] -> id:  6  time:  1
blocks[2] -> id:  4  time:  2

loss page count: 7
loss page rate : 0.700
```  
输出结果与预期符合

Last modification：December 11, 2019

如果觉得我的文章对你有用，请随意赞赏

LRU在C语言下的实现

碧云天 • 2019 年 12 月 04 日