LRU算法-模拟页面置换(C语言)源代码和图

下面是一个简单的LRU算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>

#define CACHE_SIZE 4

int cache[CACHE_SIZE];
int used[CACHE_SIZE];
int counter = 0;

void initCache() {
    for(int i=0; i<CACHE_SIZE; i++) {
        cache[i] = -1;
        used[i] = 0;
    }
}

void printCache() {
    printf("Cache: [");
    for(int i=0; i<CACHE_SIZE; i++) {
        if(cache[i] != -1) {
            printf("%d", cache[i]);
        } else {
            printf("-");
        }
        if(i < CACHE_SIZE-1) {
            printf("|");
        }
    }
    printf("]\n");
}

int findInCache(int page) {
    for(int i=0; i<CACHE_SIZE; i++) {
        if(cache[i] == page) {
            used[i] = counter++;
            return i;
        }
    }
    return -1;
}

int getLRUIndex() {
    int minIndex = 0;
    int minValue = used[0];
    for(int i=1; i<CACHE_SIZE; i++) {
        if(used[i] < minValue) {
            minIndex = i;
            minValue = used[i];
        }
    }
    return minIndex;
}

void insert(int page) {
    int index = findInCache(page);
    if(index == -1) {
        index = getLRUIndex();
        cache[index] = page;
        used[index] = counter++;
    } else {
        used[index] = counter++;
    }
}

int main() {
    initCache();
    printCache();
    insert(1);
    printCache();
    insert(2);
    printCache();
    insert(3);
    printCache();
    insert(4);
    printCache();
    insert(1);
    printCache();
    insert(2);
    printCache();
    insert(5);
    printCache();
    insert(1);
    printCache();
    return 0;
}

运行结果：

Cache: [-|-|-|-]
Cache: [1|-|-|-]
Cache: [1|2|-|-]
Cache: [1|2|3|-]
Cache: [1|2|3|4]
Cache: [2|1|3|4]
Cache: [2|1|3|5]
Cache: [1|2|3|5]

LRU算法的原理是将最近最少使用的页面置换出去，因此需要记录每个页面最近一次使用的时间戳。以上程序中使用一个计数器来记录时间戳，并将每个页面最近使用的时间戳存放在used数组中。在查找某个页面是否在缓存中时，需要遍历整个cache数组，时间复杂度为O(n)。在插入某个页面时，如果页面已经在缓存中，需要更新used数组中对应页面的时间戳；否则需要找到最近最少使用的页面，将其置换出去，并将新页面加入缓存中。时间复杂度为O(n)。