操作系统实验：页面置换算法——FIFO、LRU 代码实现

FIFO(First-In-First-Out)

        最简单的页面置换算法是FIFO。在分配内存页面数（AP）小于进程页面数（PP）时，最先运行的AP个页面放入内存；当内存分配页面被占满时，如果又需要处理新的页面，则将原来放的内存中的AP个页中最先进入的调出（FIFO），再将新页面放入；所使用的内存页面构成一个队列。

实验要求：

（1）初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（这个序列由page[ap]的下标随机构成）表示待处理的进程页面顺序，diseffect置0。

（2）看main[]中是否有下一个元素，若有，就由main[]中获取该页面下标，并转（3），如果没有则转（7）。

（3）如果该页已在内存中，就转（2），否则转（4），同时未命中的diseffect加1。

（4）观察pagecontrol是否占满，如果占满则须将使用队列（在第（6）步中建立的）中最先进入的（就是队列的第一个单元）pagecontrol单元“清干净”，同时将page[]单元置为“不在内存中”。

（5） 将该page[]与pagecontrol[]建立对应关系（可以改变pagecontrol[]的标志位，也可以采用指针链接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，二是哪个page[]单元使用的。page[]单元也包含两个信息：对应的pagecontrol单元号和本page[]单元已在内存中）。

 (6) 将用到的pagecontrol置入使用队列（这里的队列是一种FIFO的数据结构），返回（2）。

(7) 显示计算1-diseffect / total_instruction*100%，完成。

程序框图： 

代码实现： 

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

#define ProcessPageNum 10       //进程页面数
#define MemPageNum 5            //内存页面数
#define totalInstruction 100    //引用次数
int diseffect = 0;              //缺页错误数
/*定义进程页面结构体*/
struct pageNode{
    int pageID;             //进程页面ID
    int flag;               //1表示页面在内存中，0表示不在
    int pagecontrolIndex;   //所在内存页面ID 不在内存中时值为-1
};
/*定义内存页面结点*/
struct pagecontrolNode{
    int pagecontrolID;      //内存页面ID
    int flag;               //1表示被占用，0表示空闲
    int pageIndex;          //所加载进程页面ID
    struct pagecontrolNode *next;
};
/*定义FIFO队列*/
struct pagecontrolQueue{
    struct pagecontrolNode *front;
    struct pagecontrolNode *rear;
};
/*返回队首结点*/
struct pagecontrolNode* getFront(struct pagecontrolQueue *queue){
    return queue->front;
}
/*入队*/
void inQueue(struct pagecontrolQueue *queue,struct pagecontrolNode *p){
    if(queue->front == NULL){
        queue->front = p;
        queue->rear = p;
    }else{
        queue->rear->next = p;
        queue->rear = p;
        queue->rear->next = NULL;
    }
}
/*出队*/
void outQueue(struct pagecontrolQueue *queue){
    if(queue->front == NULL) exit(-1);
    else{
        queue->front = queue->front->next;
        if(queue->front == NULL) queue->rear = NULL;
    }
}
/*判断内存页面是否被占满 1为满*/
int isFull(struct pagecontrolNode *pagecontrol[MemPageNum]){
    int i = 0;
    for (i;i < MemPageNum;i++){
        if(pagecontrol[i]->flag == 0) return 0;
    }
    return 1;
}
/*初始化page数组*/
void initPage(struct pageNode *page[ProcessPageNum]){
    int i = 0;
    for(i;i < ProcessPageNum;i++){
        page[i] = (struct pageNode*)malloc(sizeof(struct pageNode)); 
        page[i]->flag = 0;
        page[i]->pageID = i;
        page[i]->pagecontrolIndex = -1;
    }
}
/*初始化pagecontrol数组*/
void initPagecontrol(struct pagecontrolNode *pagecontrol[MemPageNum]){
    int i = 0;
    for(i;i < MemPageNum;i++){
        pagecontrol[i] = (struct pagecontrolNode*)malloc(sizeof(struct pagecontrolNode)); 
        pagecontrol[i]->pagecontrolID = i;
        pagecontrol[i]->flag = 0;
        pagecontrol[i]->pageIndex = -1;
        pagecontrol[i]->next = NULL;
    }
}

int main(){
    struct pageNode *page[ProcessPageNum];
    struct pagecontrolNode *pagecontrol[MemPageNum];
    initPage(page);
    initPagecontrol(pagecontrol);
    /*初始化队列*/
    struct pagecontrolQueue *queue;
    queue = (struct pagecontrolQueue*)malloc(sizeof(struct pagecontrolQueue));
    queue->front = NULL;
    queue->rear = NULL; 
    /*构造随机序列buffer*/
    int buffer[totalInstruction];
    int i = 0;
    srand((unsigned)time(NULL));
    for(i;i < totalInstruction;i++){
        buffer[i] = rand() % ProcessPageNum;
    }
    int j = 0;
    int index = 0;  //当前内存页面下标
    for(j;j < totalInstruction;j++){
        if(page[buffer[j]]->flag == 0){ //若当前页面不在内存中
            diseffect++;                //缺页错误数加1
            page[buffer[j]]->flag = 1;
            if(isFull(pagecontrol)){    //若内存已满，则需要页面置换
                page[queue->front->pageIndex]->flag = 0;    //队首页面被换出
                page[queue->front->pageIndex]->pagecontrolIndex = -1;
                queue->front->pageIndex = page[buffer[j]]->pageID; //存入当前页面
                struct pagecontrolNode *temp;
                temp = getFront(queue);
                outQueue(queue);        //队首页面出队列
                inQueue(queue,temp);    //修改后再加入队列
            }else{                      //如果内存未满，则按照先后顺序存入
                pagecontrol[index]->flag = 1;
                pagecontrol[index]->pageIndex = page[buffer[j]]->pageID;
                page[buffer[j]]->pagecontrolIndex = pagecontrol[index]->pagecontrolID;
                inQueue(queue, pagecontrol[index]);
                index++;
            }
        }
    }
    double rightRate = (1.0 - ((double)diseffect / (double)totalInstruction))*100;
    printf("错误次数%d\n",diseffect);
    printf("正确率%.2f%%\n",rightRate);
}

LRU(Least-Recent-Used algorithm)

        计数器实现法：在最简单的情况下，为每个页表条目关联一个使用时间域，并为CPU添加一个逻辑时钟或计数器。每次内存引用都会递增时钟；且每当进行页面引用时，时钟寄存器的内容会复制到相应页面的页表条目的使用时间域。这样我们总是找到每个页面最后被引用的时间，便可以置换拥有最小使用时间的页面。

实验要求：

(1) 初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（这个序列由page[ap]的下标随机构成）表示待处理的进程页面顺序，diseffect置0。

(2) 看序列main[]中是否有下一个元素，如果有，就由main[]中获取该页面下标，并转（3），如果没有则转（6）。

(3) 如果该page[]单元在内存中便改变页面属性，使它保留“最近使用”的信息，转（2），否则转（4），同时diseffect加1。

(4) 看是否有空闲页面，如果有，就返回页面指针，并转到（5），否则，在内存页面d将其“清干净”，并返回该页面指针。

(5) 在需处理的page[]与（4）中得到的pagecontrol[]之间建立联系，同时让对应的page[]单元保存“最新使用”的信息，转（2）。

         (6) 如果序列处理完成，就输出计算1-diseffect / total_instruction*100%的结果

程序框图： 

 代码实现：

#include<stdio.h>
#include<stdlib.h> 
#include<time.h>
/*实现方法与FIFO算法大同小异，无需定义队列，而是用计数器实现选择牺牲帧*/
#define ProcessPageNum 10       //进程页面数
#define MemPageNum 5            //内存页面数
#define totalInstruction 100    //引用次数
int diseffect = 0;              //缺页错误数
/*定义进程页面结构体*/
struct pageNode{
    int pageID;             //进程页面ID
    int flag;               //1表示页面在内存中，0表示不在
    int pagecontrolIndex;   //所在内存页面ID 不在内存中时值为-1
    int useTime;            //最后被引用时间
};
/*定义内存页面结点*/
struct pagecontrolNode{
    int pagecontrolID;      //内存页面ID
    int flag;               //1表示被占用，0表示空闲
    int pageIndex;          //所加载进程页面ID
};
/*初始化page数组*/
void initPage(struct pageNode *page[ProcessPageNum]){
    int i = 0;
    for(i;i < ProcessPageNum;i++){
        page[i] = (struct pageNode*)malloc(sizeof(struct pageNode)); 
        page[i]->flag = 0;
        page[i]->pageID = i;
        page[i]->pagecontrolIndex = -1;
        page[i]->useTime = 0;
    }
}
/*初始化pagecontrol数组*/
void initPagecontrol(struct pagecontrolNode *pagecontrol[MemPageNum]){
    int i = 0;
    for(i;i < MemPageNum;i++){
        pagecontrol[i] = (struct pagecontrolNode*)malloc(sizeof(struct pagecontrolNode)); 
        pagecontrol[i]->pagecontrolID = i;
        pagecontrol[i]->flag = 0;
        pagecontrol[i]->pageIndex = -1;
    }
}
/*判断内存页面是否被占满 1为满*/
int isFull(struct pagecontrolNode *pagecontrol[MemPageNum]){
    int i = 0;
    for (i;i < MemPageNum;i++){
        if(pagecontrol[i]->flag == 0) return 0;
    }
    return 1;
}
/*找到内存中页面最后引用时间最小的page结点并返回*/
struct pageNode* findMinUseTime(struct pageNode *page[ProcessPageNum]){
    struct pageNode *temp;
    temp = (struct pageNode*)malloc(sizeof(struct pageNode)); 
    temp->useTime = totalInstruction;
    int i = 0;
    for(i;i < ProcessPageNum;i++){
        if(page[i]->useTime < temp->useTime && page[i]->flag == 1){
            temp = page[i];
        }
    }
    return temp;
}
int main(){
    struct pageNode *page[ProcessPageNum];
    struct pagecontrolNode *pagecontrol[MemPageNum];
    initPage(page);
    initPagecontrol(pagecontrol);
    /*构造随机序列buffer*/
    int buffer[totalInstruction];
    int i = 0;
    srand((unsigned)time(NULL));
    for(i;i < totalInstruction;i++){
        buffer[i] = rand() % ProcessPageNum;
    }
    int j = 0;
    int timer = 0;  //设置计数器
    int index = 0;  //当前内存页面下标
    for(j;j < totalInstruction;j++){
        timer++;    //计数器递增
        page[buffer[j]]->useTime = timer;
        if(page[buffer[j]]->flag == 0){ //若当前页面不在内存中
            diseffect++;                //缺页错误数加1
            page[buffer[j]]->flag = 1;
            if(isFull(pagecontrol)){    //若内存已满
                struct pageNode *temp = findMinUseTime(page);   //找到将被置换的页面
                temp->flag = 0;
                temp->useTime = 0;
                pagecontrol[temp->pagecontrolIndex]->pageIndex = page[buffer[j]]->pageID;   //修改pagecontrol数组
                page[buffer[j]]->pagecontrolIndex = pagecontrol[temp->pagecontrolIndex]->pagecontrolID; //修改page数组
                temp->pagecontrolIndex = -1;
            }else{                      //若内存未满，则按顺序存入
                pagecontrol[index]->flag = 1;
                pagecontrol[index]->pageIndex = page[buffer[j]]->pageID;
                page[buffer[j]]->pagecontrolIndex = pagecontrol[index]->pagecontrolID;
                index++;
            }
        }
    }
    double rightRate = (1.0 - ((double)diseffect / (double)totalInstruction))*100;
    printf("错误次数%d\n",diseffect);
    printf("正确率%.2f%%\n",rightRate);
}

参考资料：

《操作系统概念（第九版）》文章来源地址https://www.toymoban.com/news/detail-473933.html

到了这里，关于操作系统实验：页面置换算法——FIFO、LRU 代码实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！