fifo算法_页面置换算法学习总结

101 阅读 0 评论 67 点赞

我是靠谱客的博主高兴奇异果，这篇文章主要介绍fifo算法_页面置换算法学习总结，现在分享给大家，希望可以做个参考。

近期，学习了操作系统页面置换算法，为了巩固所学知识，主要用先进先出（FIFO）页面置换算法和最近最久未使用（LRU）置换算法进行一个复习。

1.FIFO页面置换算法

此算法是淘汰最先进入内存的页面，选择在内存中驻留最久的页面予以淘汰，而替换此时需要调用的页面。

实现原理：需把一个进程已调入内存的页面按先后顺序链接成一个队列，设置一个指针（替换指针），将指针指向最久调入的页面，若在此队列中已存在，则不进行替换；否则将替换指针所指向的页面出队，新调用的页面入队。

参考实验所做的代码：

复制代码

1
2
#define MAXSIZE	20

（由于太懒，就用书上的图吧(#^.^#)）

最开始队列为空，所以7,0，1顺序入队，在进程第一次访问页面2时，由于7页面最先调入内存，故被换出；当在第一次访问页面3时，将最久未被使用的0号页面换出，由此类推，当换入最后一个1时，共进行了12次页面置换。

2.LRU页面置换算法：

由于FIFO算法性能较差，所以出现了LRU页面置换算法，该算法是根据页面调入内存后的使用情况来做决策的。无法预估页面将来的使用情况，利用过去的页面使用情况来进行置换的。

实现原理：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问页面时，便将该页面的页面号从栈中移除，将它压入栈顶。因此，栈顶元素始终是最新被访问页面的编号，而栈底则是最近最久没有被使用的页面的编号。

参考实验所做的代码：

复制代码

#define MAXSIZE	20
#include <iostream>
using namespace std;
void main()
{
    int ibel = 0;//标记此页是否已经装入内存
    int input = 0;	//用于输入作业号
    int worknum = 0;	//记录作业个数
    int storesize = 0;	//系统分配的存储区块数
    int interrupt = 0;	//中断次数
	int temp=0;    //临时变量
	int top=0;   //栈顶指针
    int stack[MAXSIZE];	//队列，FIFO算法的主要数据结构
    int workstep[MAXSIZE];	//记录作业走向
    /*初始化*/
    for (int i = 0;i < MAXSIZE;i++)
    {
        stack[i] = 0;
        workstep[i] = 0;
    }
    cout << "请输入存储区块数：";
    cin >> storesize;
    cout << "请输入作业走向（输入0结束）：n";
    for (int j = 0;j < MAXSIZE;j++)
    {
        cout << "页面号" << j + 1 << "：";
        cin >> input;
        workstep[j] = input;
        if (input == 0)
        {
            cout << "输入结束！n";
            break;
        }
        worknum++;
    }
    if (workstep[0] == 0)
    {
        cout << "未输入任何作业，系统将退出！n";
        return;
    }
    cout << "置换情况如下：n";
    for (int k = 0;k < worknum;k++)
    {
        ibel = 0;
        /*在队列中找相等的页号或空位置*/
        for (int l = 0;l < storesize;l++)
        {
            /*是否有相等的页号*/
            if (stack[l] == workstep[k])
            {
                cout << "内存中有" << workstep[k] << "号页面，无须中断！n";
				temp = workstep[k];
				for(int n=l;n<storesize;n++){
					stack[n]=stack[n+1];
				}
				stack[top]=temp;
                ibel = 1;//标记此页面已装入内存
                break;
            }
            /*找队列中是否有空位置*/
            if (stack[l] == 0)
            {
                stack[l] = workstep[k];
                cout << "发生中断，但内存中有空闲区，" << workstep[k] << "号页面直接调入！n";
                top=l;   //保持top指栈顶
				interrupt++;
                ibel = 1;
                break;
            }
        }
        /*上述情况都不成立则调出队首，将调入页面插入队尾*/
        if (ibel == 0)
        {
            cout << "发生中断，将" << stack[0] << "号页面调出，" << workstep[k] << "号装入！n";
            interrupt++;
            for (int m = 0;m < storesize;m++)
            {
                stack[m] = stack[m + 1];
            }
            stack[storesize - 1] = workstep[k];
        }
    }
    cout << "  作业 " << worknum << "  个， " << "  中断 " << interrupt << " 次， " << "  缺页率： " << float(interrupt) / float(worknum) * 100 << " % n";
}

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
#define MAXSIZE	20
#include <iostream>
using namespace std;
void main()
{
    int ibel = 0;//标记此页是否已经装入内存
    int input = 0;	//用于输入作业号
    int worknum = 0;	//记录作业个数
    int storesize = 0;	//系统分配的存储区块数
    int interrupt = 0;	//中断次数
	int temp=0;    //临时变量
	int top=0;   //栈顶指针
    int stack[MAXSIZE];	//队列，FIFO算法的主要数据结构
    int workstep[MAXSIZE];	//记录作业走向
    /*初始化*/
    for (int i = 0;i < MAXSIZE;i++)
    {
        stack[i] = 0;
        workstep[i] = 0;
    }
    cout << "请输入存储区块数：";
    cin >> storesize;
    cout << "请输入作业走向（输入0结束）：n";
    for (int j = 0;j < MAXSIZE;j++)
    {
        cout << "页面号" << j + 1 << "：";
        cin >> input;
        workstep[j] = input;
        if (input == 0)
        {
            cout << "输入结束！n";
            break;
        }
        worknum++;
    }
    if (workstep[0] == 0)
    {
        cout << "未输入任何作业，系统将退出！n";
        return;
    }
    cout << "置换情况如下：n";
    for (int k = 0;k < worknum;k++)
    {
        ibel = 0;
        /*在队列中找相等的页号或空位置*/
        for (int l = 0;l < storesize;l++)
        {
            /*是否有相等的页号*/
            if (stack[l] == workstep[k])
            {
                cout << "内存中有" << workstep[k] << "号页面，无须中断！n";
				temp = workstep[k];
				for(int n=l;n<storesize;n++){
					stack[n]=stack[n+1];
				}
				stack[top]=temp;
                ibel = 1;//标记此页面已装入内存
                break;
            }
            /*找队列中是否有空位置*/
            if (stack[l] == 0)
            {
                stack[l] = workstep[k];
                cout << "发生中断，但内存中有空闲区，" << workstep[k] << "号页面直接调入！n";
                top=l;   //保持top指栈顶
				interrupt++;
                ibel = 1;
                break;
            }
        }
        /*上述情况都不成立则调出队首，将调入页面插入队尾*/
        if (ibel == 0)
        {
            cout << "发生中断，将" << stack[0] << "号页面调出，" << workstep[k] << "号装入！n";
            interrupt++;
            for (int m = 0;m < storesize;m++)
            {
                stack[m] = stack[m + 1];
            }
            stack[storesize - 1] = workstep[k];
        }
    }
    cout << "  作业 " << worknum << "  个， " << "  中断 " << interrupt << " 次， " << "  缺页率： " << float(interrupt) / float(worknum) * 100 << " % n";
}

前三次访问依次将4,7，0放入栈中，4为栈底，0为栈顶；第四次是访问第7页，因此7变为栈顶；当第八次访问页面2时，栈满，在九、十次访问时，没有发生缺页；而在第十一次访问时，页面6发生了缺页，4为最久没有被访问的页面，被替换出去。

除此之外还有最佳（Optimal）置换算法，所选择的页面是以后永不被使用的或者在最长（未来）时间内不再被访问的页面。此算法也有着最低的缺页率，但缺点是无法预知未来将调用那个页面。还有最少使用（LFU）置换算法，在使用该算法时在每个页面设置一个位移寄存器，来记录此页面被访问的频率，并选择最近时期使用频率最低的页面作为淘汰页。还有一些算法例如Clock置换算法、页面缓冲算法（PBA）等，由于没有过多去学习，故不过多赘述。

若文中有错误的地方，请批评指正，谢谢！