欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

页面置换FIFO与LRU的实现

程序员文章站 2022-07-12 17:15:33
...

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

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;
}

实测效果:

页面置换FIFO与LRU的实现

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更低): 

页面置换FIFO与LRU的实现