【随笔系列】C语言实现LRU置换算法_用c语言实现lru算法

LRU置换算法

1. LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

实验要求

1. 实验描述：

假设系统中有1个进程，其大小总共有n=10页，而操作系统仅分配了m=3个页面的物理内存空间供其运行。用随机函数随机产生包含有k=20个页面的访问序列。

2. 实验输出：

（1）每处理页面访问序列中的1个页面请求时，操作系统分配给该进程的m=3个页面空间的被占用情况；

（2）最后输出命中次数，缺页次数，以及缺页率。

3. 实验要求：

（1）根据参数n=10，m=3, k=20，编程实现LRU页面置换算法，计算缺页率。

简易分析

根据题意，需要实现的算法在整体上分为Init、LRU、Print

1. Init：初始化相关数据结构。

2. LRU：即实现算法的主体部分。

3. Print：穿插在上面几个部分之中，根据具体需要设计即可。

Init部分

由于实现起来相对简单，故不做对具体实现的讲解。

void Init(int Seq[], int PageAcc[], int PageArr[]);
1

LRU部分

这次实验较为简单，不用划分子函数也可快速的进行编程解题。

void LRU(int Seq[], int PageAcc[], int PageArr[]);
1

Print部分

由于实现起来相对简单，故不做对具体实现的讲解。

void Print_Seq(int Seq[]);
void Print_State(int idx, int PageArr[], bool hit);
void Print_Result(int Hit, int Miss);
1
2
3

整体代码实现

代码量较小，有问题看注释。

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

#define SequenceLen 20
#define MaxNumPages 10
#define NumAllocatedPages 3

void Init(int Seq[], int PageAcc[], int PageArr[]);
void LRU(int Seq[], int PageAcc[], int PageArr[]);

void Print_Seq(int Seq[]);
void Print_State(int idx, int PageArr[], bool hit);
void Print_Result(int Hit, int Miss);

int main() {
    srand((unsigned)time(NULL));    //刷新随机数种子
    int Sequence[SequenceLen] = {};
    int PageAccessTime[MaxNumPages] = {};
    int PageArray[NumAllocatedPages] = {};

    Init(Sequence, PageAccessTime, PageArray);
    LRU(Sequence, PageAccessTime, PageArray);
    return 0;
}

void Init(int Seq[], int PageAcc[], int PageArr[]) {
    for (int i = 0; i < NumAllocatedPages; i++)
        PageArr[i] = -1;

    for (int i = 0; i < MaxNumPages; i++)
        PageAcc[i] = 0;

    for (int i = 0; i < SequenceLen; i++)
        Seq[i] = rand() % MaxNumPages;

    Print_Seq(Seq);
    return;
}

void LRU(int Seq[], int PageAcc[], int PageArr[]) {
    bool hit = false;
    bool in = false;
    int numHit = 0;
    int numMiss = 0;

    for (int i = 0; i < SequenceLen; i++) {
        if (i == 0)printf("\tSeqID\tWorking Set\n");  //图方便
        
        for (int j = 0; j < NumAllocatedPages; j++) {   //看看能不能装，能装则直接输出状态，不能就进行下一个操作
            if (PageArr[j] == -1) {
                numMiss++;
                PageArr[j] = Seq[i];
                for (int k = 0; k < j; k++) {   //最抽象的一步，将之前已装入工作集的页计时+1
                    PageAcc[PageArr[k]]++;
                }
                in = true;
                break;
            }
        }

        if (!in) {  //不能装的话，又分两种情况：1.新来的工作集里面有，hit；2.新来的工作集里面没有，换掉计时最长的页
            for (int j = 0; j < NumAllocatedPages; j++) {
                if (PageArr[j] == Seq[i]) {
                    hit = true;
                    numHit++;

                    for (int k = 0; k < NumAllocatedPages; k++) {   //最抽象的一步，将除hit页之外已装入工作集的页计时+1
                        PageAcc[PageArr[k]]++;
                    }
                    PageAcc[Seq[i]] = 0;    //hit页计时归零
                    break;
                }
            }
            if (!hit) {
                numMiss++;
                int big_idx = PageArr[0];
                for (int j = 0; j < NumAllocatedPages; j++) {   //图方便，快速找到计时最长的页号
                    if (PageAcc[PageArr[j]] > PageAcc[big_idx])big_idx = PageArr[j];
                }
                for (int k = 0; k < NumAllocatedPages; k++) {   //找到相应的页号，换掉它
                    if (PageArr[k] == big_idx) {
                        PageArr[k] = Seq[i];
                        PageAcc[Seq[i]] = 0;    //计时归零
                    }
                    else PageAcc[PageArr[k]]++; //最抽象的一步，将除hit页之外已装入工作集的页计时+1
                }
            }
        }

        Print_State(i + 1, PageArr, hit);
        hit = false;    //重置
        in = false;
    }
    Print_Result(numHit, numMiss);
    return;
}

void Print_Seq(int Seq[]) {
    printf("Page sequence：");
    for (int i = 0; i < SequenceLen; i++) {
        printf("%d ", Seq[i]);
    }
    printf("\n");
    return;
}

void Print_State(int idx, int PageArr[], bool hit) {
    printf("\t%d\t",idx);
    for (int i = 0; i < NumAllocatedPages; i++) {
        printf("%2d ", PageArr[i]);
    }
    if (hit)printf("  *hit*");

    printf("\n");
    return;
}

void Print_Result(int Hit, int Miss) {
    double rate = double(Miss) / double(SequenceLen);   //强制转换，不然输出有问题
    printf("Hit = %d, Miss = %d\n", Hit, Miss);
    printf("Page fault Rate = %d/%d = %lf\n", Miss, SequenceLen, rate);
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

结果展示

总结及心得

1. 加急写的，没有什么难点，主要是费时间。