存储管理：先进先出算法和最近最少使用算法_先进先出算法是最近最少使用算法的两倍吗

这个学期学习操作系统，其实主要就是系统对于一些情况的应对算法，我们要做的就是写代码模拟这个情况，来了解操作系统是怎么解决的。

一、简介

提高内存管理的效率始终是操作系统研究的重要课题之一，虚拟存储技术是用来提高存储容量的一种重要方法，所以，本项实验的目的是立地设计几个常用的存储分配算法，并用高级语言编写程序对各种算法进行分析比较，评测其性能的优劣，从而加深对这些算法的了解。
在存储管理中有两类主要算法：分区分配算法、请求式分页存储管理算法，本次讲解请求式分页存储管理算法中的先进先出算法FIFO和最近最少使用页面淘汰算法LRU

二、算法

先进先出算法：

对于每个使用的页面记录进入内存块的先后，若某个页面重复使用且命中，那么他的进入内存的时间不变，还是最开始进入的那个时间。即每次把停留时间最长那个页面去掉。

最近最少使用：

淘汰的方式就是使用较少的，也就是把刚使用过的留下来。

举个例子：

参照这个：https://blog.csdn.net/qq_38680137/article/details/82722302
例如在一个虚存系统中，进程的内存空间为3页，已开始内存为空，有以下访问序列：2,3,2,1,5,2,4,5,3,2,5,2。分别用以上两种方法分别计算缺页次数。
A：使用FIFO（页面淘汰算法）
FIFO:先进先出，也就是，
先调2（缺） 内存为2.
调3（缺） 内存2.3.
调2（不缺）内存2.3
调1（缺）内存2.3.1
调5（缺）内存5.3.1（因为先进先出，所以替换调最先进来的2）
调2（缺）内存5.2.1（同样替换调3）
调4（缺）内存5.2.4
调5（不缺）内存5.2.4
调3（缺）3.2.4
调2（不缺）3.2.4
调5（缺）3.5.4
调2（缺）3.5.2 所以一共缺了9次
B：使用LRU（最近最少使用算法）
LRU：最近最少使用算法，也就是替换掉最远没有使用的，看示例：
还是跟上面一样，先调用2（缺） 内存2
调3（缺） 内存2.3
调2（不缺） 内存2.3
调1（缺） 内存2.3.1
调5（缺） 内存2.5.1（替换掉3，因为最近使用了1和2 而3没有进行使用）
调2（不缺）内存2.5.1
调4（缺）内存2.5.4（1最近没有使用）
调5（不缺）内存2.5.4
调3（缺）3.5.4
调2（缺）3.5.2
调5（不缺）3.5.2
调2（不缺）3.5.2 所以一共缺页7次

说明：

主要有2大难题：内存空闲是否存在和选择替换掉参照哪个参数。
第一个问题要大量判断，在判断重复后还要判断有没有内存空闲，因为空闲是是优先加入的额，而不用执行替换操作，这样就真的很动态。
第二个问题有点小难，后来网上查了很多资料，想了想，决定采用累加方式：每次访问新页面时，旧的页面存在时间加一。听起来很简单，但是这就涉及到把这个标志位放到哪，真的难。至于最近最少使用，可以也是累加，然后重复访问时把累加值清零。我花了大量的小时优化了数据结构，把2种算法写到一个函数里面，而只有对计数器的调整不一样，这样代码行数大大减少。

三、结果

四、代码

#include <stdio.h>
#include <iostream>
#include<string.h>
#define MAX 100
int mark[MAX];
using namespace std;
typedef struct page_replacement_algorithm
{
    char page;
    char interrupt;
    int time;
}PRA;
PRA ans[MAX][MAX];//在这个结构中interrupt未使用
PRA pra[MAX];//在这个结构中time未使用
int n,m;//页面总数和内存块数
int hashad(int i,char temp)//判断当前页面是否不缺少，即是否重复，不重复返回-1
{
    int had=-1;
    for(int u=0; u<m; u++)
    {
        if(ans[u][i].page!='.')
        {
            if(ans[u][i].page==temp)had=u;
        }
        else break;
    }
    return had;
}
int hasempty(int i)//判断当前内存页面是否有空余，没有空余返回-1
{
    int had=-1;
    for(int u=0; u<m; u++)
    {
        if(ans[u][i].page=='.')
        {
            had=u;
            break;
        }
    }
    return had;
}
int wheremax(int i)//判断time最大的页面，即要被替换的页面,返回下角标
{
    int had=0;
    int maxtime=ans[0][i].time;
    for(int u=1; u<m; u++)
    {
        if(ans[u][i].time>maxtime)
        {
            had=u;
            maxtime=ans[u][i].time;
        }
    }
    return had;
}
void pageReplace(int ca)
{
    memset(ans,0,sizeof(ans));
    printf("请输入页面走向和物理块数:");
    scanf("%d %d",&n,&m);
    getchar();
    printf("请输入%d个字符:",n);
    for(int i=0; i<n; i++)
    {
        scanf("%c",&pra[i].page);
        getchar();
    }
    for(int i=0; i<MAX; i++)//初始化，'.'代表为空
        for(int p=0; p<MAX; p++)
            ans[i][p].page='.';
    ans[0][0]=pra[0];//先添加第一列
    pra[0].interrupt = '*';//第一个为缺少
    ans[0][0].time = 0;//第一次加入内存
    //!time数值越大代表越早进入内存(FIFO),数值越大代表最近使用较少(LRU)

    for(int i=1; i<n; i++)
    {
        for(int p=0; p<m; p++)//把上一列的数据复制过来
        {
            if(ans[p][i-1].page!='.')
            {
                ans[p][i]=ans[p][i-1];
                ans[p][i].time++;//每复制一次，time就加一，代表停留时间
            }
            else break;

        }
        char temp=pra[i].page;
        int ishad=hashad(i,temp);
        if(ishad>=0)//如果重复了，没重复返回-1
        {
            pra[i].interrupt=' ';
            if(ca==2)ans[ishad][i].time=0;//!对于LRU来说重复的代表最近刚使用了
            continue;
        }

        int isempty=hasempty(i);//此时肯定没重复
        if(isempty>=0)//如果当前列有空余内存
        {
            ans[isempty][i]=pra[i];
            pra[i].interrupt='*';
            ans[isempty][i].time=0;
            continue;
        }
        //此时肯定是没有空余内存，且一定要发生替换
        int where=wheremax(i);//找到time最大的那一个
        ans[where][i]=pra[i];
        pra[i].interrupt='*';
        ans[where][i].time=0;
    }
    printf("%s置换算法:\n",ca==1?"FIFO":"LRU");
    printf("%8s:","页面走向");
    for(int r=0; r<n; r++) printf("%3c ",pra[r].page);
    printf("\n---------------------------------------------------------\n");
    for(int i=0; i<m; i++)
    {
        printf("%6s%2d:","物理块",i+1);
        for(int j=0; j<n; j++) printf("%3c ",ans[i][j].page);
        printf("\n");
    }
    printf("%8s:","缺页中断");
    int ruptsum=0;
    for(int r=0; r<n; r++)
    {
        printf("%3c ",pra[r].interrupt);
        if(pra[r].interrupt=='*')ruptsum++;
    }
    printf("\n缺页率：%.2f%%\n\n",ruptsum*100.0/n);
}

int main()
{
    int ca = 0;
    while(1){
        printf("*********************欢迎您！**************************\n");
        printf("***             1、先进先出算法                     ***\n");
        printf("***             2、最近最少使用页面淘汰算法         ***\n");
        printf("***             0、结束程序                         ***\n");
        printf("*******************************************************\n");
        scanf("%d",&ca);
        if(ca<1||ca>2)break;
        pageReplace(ca);
    }
    return 0;
}
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145