页面置换FIFO与LRU的实现

最近复习操作系统，想到了两个常用的页面置换算法，但之前一种没实现过，想想应如何实现。

FIFO（先进先出页面置换）

FIFO最易理解，也易于实现，但在应用中，其缺页率比较高。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1005;
int a[maxn];
int d[maxn];    //散列便于查询
int main()
{
    int m,n,x,c=0;
    printf("输入物理块数和页面数：\n");
    scanf("%d %d",&m,&n);
    for(int i=0;i<m;i++){
        a[i]=1004;
    }
    memset(d,0,sizeof(d));
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        if(d[x]==0){        //如果物理块中没有
            d[a[c%m]]=0;    //循环队列中将尾指针所指的元素删除
            a[c%m]=x;       //插入到尾指针
            d[x]=1;
            c++;            //尾指针进行自增
        }
    }
    printf("缺页数：%d\n",c);
    return 0;
}

实测效果：

LRU（最近最久未使用算法）

顾名思义，该算法每次将内存中最久未使用过的内存页面换到存中，通常情况下，缺页率比FIFO低，所以更优。但这里仅提高了单链表的实现方法，由于每次查询页面是否存在内存时，都需要进行遍历，时间复杂度为O(n)，效率比较低。如何使用哈希链表实现时间复杂度为O(1)，需要再去学习一下（本人太菜，暂时无能为力）。

/*单链表实现LRU*/
#include <bits/stdc++.h>

using namespace std;
typedef int ElemType;                       //链表的数据类型
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
int CreateList(LinkList &L,int n){          //&L为引用变量
    L = (LinkList)malloc(sizeof(LNode));    //分配空间
    L->data = n;
    L->next = NULL;                         //头指针为空
    for(int i=n;i>0;--i){
        LinkList p;                         //LinkList p 相当于 LNode *p
        p = (LinkList)malloc(sizeof(LNode));
        p->data = -1;                       //初始化时将链表值置为-1；
        p->next = L->next;                  //后插法
        L->next = p;
    }
    return 0;
}

int ListInsert(LinkList &L,int i,ElemType e){   //i为插入的位置
    LinkList p = L;
    LinkList s;
    int j = 0;
    while(p&&j<i-1){
        p = p->next;
        ++j;
    }
    if(!p || j>i-1){
        return 0;
    }
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

int ListDelet(LinkList &L,int i){   //删除第i位置上的元素
    LinkList p = L;int j = 0;
    while(p->next && j<i-1) {
        p = p->next;++j;
    }
    if(!(p->next) || j>i-1)return 0;
    LinkList q = L;
    q = p->next;
    p->next = q->next;
    free(q);
    return 1;
}

int List_search(LinkList L,ElemType e){
    LinkList p;
    p = L->next;
    int j=1;
    while(p != NULL){
        if(p->data == e){
            return j;       //有该元素
            break;
        }
        else{
            p = p->next;
            j++;
        }
    }
    return 0;               //没有该元素
}
int main(){
    int m,n,x;
    int c = 0;
    LinkList L;
    printf("输入物理块数和页面数：\n");
    scanf("%d %d",&m,&n);   //m为内存空间，n为元素的个数
    CreateList(L,m);
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        int p = List_search(L,x);
        if(p>0){                //找到该点要更新
            ListDelet(L,p);
            ListInsert(L,1,x);
        }
        else{                   //没找到该点要将该点插入头节点，然后删除尾节点
            ListDelet(L,m);
            ListInsert(L,1,x);
            c++;
        }
    }
    printf("缺页数：%d\n",c);
    return 0;
}

实现效果（通常情况下缺页率比FIFO更低）：