繁依Fanyi0

这个屌丝很懒，什么也没留下！

热门标签

操作系统实验六——先进先出算法FIFO、最佳淘汰算法OPT、最近最久未被使用算法LRU_参考用c语言实现的先进先出算法fifo的代码,实现最佳置换算法opt和最近最少使用算

作者：繁依Fanyi0 | 2024-06-08 00:04:09

踩

参考用c语言实现的先进先出算法fifo的代码,实现最佳置换算法opt和最近最少使用算

操作系统实验六

一、实验内容

模拟页面调度算法:模拟先进先出算法FIFO，最佳淘汰算法OPT，最近最久未被使用算法LRU。

具体实验要求：

给定一个15个以上的内存页面序列和3-5块的物理块。
在实验5的基础上完善先进先出算法FIFO。
进一步实现最佳淘汰算法OPT。
实现最近最久未被使用算法LRU。

二、实验设计思想

（一）设计思路：

程序首先通过关键字const分别定义常量phyBlockNum表示内存总物理块的数量。然后通过c++中vector容器定义pageList序列，模拟页面调入。定义int型变量missingCount、replaceCount分别用来记录缺页次数、置换次数。
之后，定义结构体Page来记录不同页面调入算法中每个页面的附加信息，分别用pageIfo表示页面号，addIfo表示页面附加信息（ OPT 中表示重复元素距离，LRU中表示计时器），index表示页面号下标。用vector容器开辟Page类型数组模拟物理块，-1表示空闲。int型isVisited标志位表示是否需要页面替换。
主函数main()方法中首先调用init（）函数进行数据初始化。
然后，调用FIFO（）函数，模拟FIFO算法页面调度。FIFO()函数中设置pointer指针指向内存中最老留存的页面。之后依次调入内存页面，在物理块for循环中主要分三种情况进行页面分配判断，即（1）如果页面在内存中，则标志位isVisited置1表示已找到物理块，不需要置换。（2）如果页面不在内存中且物理块有空闲块，则需把页面装入第一个内存空闲物理块，标志位isVisited置1表示已找到物理块，不需要置换。然后，missingCount加1，表示产生一次页面中断。（3）如果页面不在内存中且物理块没有空闲块，则进行FIFO页面置换，同时pointer后移，并通过if (pointer > phyBlockNum - 1)判断指针位置，若指针指到尾部再通过pointer=0重头开始。同时，missingCount加1，表示产生一次页面中断。replaceCount加1，表示产生一次页面置换。编写printf_()函数，每次页面装入内存时展示当前内存状况。调用ResultAnalysis()分别展示该算法的缺页中断次数、缺页中断率、置换次数用于输出结果的分析。
之后，调用OPT（）函数，模拟OPT算法页面调度。OPT()函数中首先调用init（）函数初始化内存信息。然后通过Page类型page[pageList.size( )]数组存储预先处理的将来页面信息。使用map 容器，统计重复元素。通过时间复杂度为O（n）对pageList的遍历，依次用addIfo标记距离最近的两个相同元素之间的距离信息，index标记该元素下标。之后，for循环依次遍历内存页面，在物理块for循环中分三种情况进行页面分配判断，即（1）如果页面在内存中，则标志位isVisited置1表示已找到物理块，不需要置换，同时更新该块附加信息。（2）如果页面不在内存中且物理块有空闲块，则需把页面装入第一个内存空闲物理块，标志位isVisited置1表示已找到物理块，不需要置换。然后，missingCount加1，表示产生一次页面中断。（3）如果页面不在内存中且物理块没有空闲块，则进行OPT页面置换，for循环所有物理块中页面信息，通过pos记录以后永不使用或者最长时间后才会被防问页面的位置，通过计算找到物理快中当前页面下一次出现距离将要调入页面的最大值，即以后永不使用的,或者过最长的时间后才会被访问的页面，进行置换。同时，missingCount加1，表示产生一次页面中断。replaceCount加1，表示产生一次页面置换。编写printf_()函数，每次页面装入内存时展示当前内存状况。调用ResultAnalysis()分别展示该算法的缺页中断次数、缺页中断率、置换次数用于输出结果的分析。
最后，调用LRU（）函数，模拟LRU算法页面调度。LRU()函数中首先调用init（）函数初始化内存信息。设置time计时器，使页面每次进入改变计时器+1。之后for循环依次调入内存页面，在物理块for循环中主要分三种情况进行页面分配判断，即（1）如果页面在内存中，则标志位isVisited置1表示已找到物理块，不需要置换，附加信息通过计时器记录该页面调入时时间。（2）如果页面不在内存中且物理块有空闲块，则需把页面装入第一个内存空闲物理块，标志位isVisited置1表示已找到物理块，不需要置换。然后，missingCount加1，表示产生一次页面中断。附加信息通过计时器记录该页面调入时时间。（3）如果页面不在内存中且物理块没有空闲块，则进行LRU页面置换，for循环所有物理块中页面信息，通过pos记录最近最久未被使用过的位置信息，即找到计时器最小值页面下标，进行置换。同时，missingCount加1，表示产生一次页面中断。replaceCount加1，表示产生一次页面置换。编写printf_()函数，每次页面装入内存时展示当前内存状况。调用ResultAnalysis()分别展示该算法的缺页中断次数、缺页中断率、置换次数用于输出结果的分析。

三、实验结果及分析

（一）实验结果

在这里插入图片描述

（二）运行结果分析：

从运行结果来看，FIFO算法OPT算法LRU算法对页面调入序列pageList [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]所对应的缺页中断率分别为75.00%，45.00%，60.00%，可以看出OPT算法始终是最优的置换算法，但OPT算法需要了解所有指令的构成情况，在实际的系统中不可能实现，故如果对效率要求较高，可以考虑使用更复杂的页面置换算法，如最近最少使用LRU算法等。

四、其他

（一）页式存储管理

分区式仔储管理的最大缺点是碎片问题严重,内存利用率低。主要原因在于连续分配的限制,即它要求每个作业在内存必须占用一个连续的分区。结合固定分区和离散存储的思想而产生的页式存储管理基本解决了碎片问题。它允许一个进程在内存中占有多个不连续的但是大小相等的区域,从而不用移动程序就能消除外碎片,而且内碎片也很少。所以是目前前内存利用率最高的一种存储管理方式,具体又分为实分页和虚分页两种存储管理方式。其中,虚分页存储管理是目前流行的一种存储管理方式,而实分页存储管理则是认为将在PC上最有发展前途的一种存储管理方式。

（二）实分页式存储管理

实分页式存储管理是一种在实存模式下的分页式存储管理方式,其最大优点就是内存利用率高,以及实现过程对用户透明,而且与现在流行的虚分页存储管理方式相比，具有实现简单、程序运行快的优点。目前,飞速发展的硬件制造技术使得物理内存越来越大,甚至足够大,特别是在用户负载并不太大的个人计算机上,同时让系统所能支持的最多个并发任务的程序全部驻留内存也是完全有可能的,小内存运行不了大程序的问题几乎不复存在。因此我们认为,实模式下的分页式存储管理方式,至少在个人计算机上,将是最有发展前途的一种存储管理方式。其基本思想如下。
1.采用分页存储管理技术的系统,将整个系统的内存空间划分成一系列大小相等的块,每一块称为一个物理块、物理页或实页,也有人称之为页架或页帧(Frame),可简称为块(Block)。所有的块按物理地址递增顺序连续编号为0、1、2等。
2.每个作业或进程的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个逻辑页或虚页,也有人称页面,可简称为页(Page)。所有的页按照逻辑地址递增顺序连续编号为0、1、2等。
3.一个作业或进程,只要它的总页数不大于内存中的可用块数,系统就可以对它实施分配。系统装入作业或进程时,以页为单位分配内存,一页分配一个块,作业或进程所有的页所占的块可以不连续。系统同时为这个作业或进程建立一个页号与块号的对照表,称为页表。
4.每个块的大小是固定的,一般值为512B-4KB，而且必须是2的幂次。

（三）虚拟页式存储管理

虚拟页式存储管理技术也称请求分页存储管理技术,是实分页加虚拟存储的产物。其基本思想是:系统自动地将进程的地址空间分页,将系统的主存空间分块,页与块等大;在进程运行前,只把初始需要的一部分页面装入内存块里,运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调人内存,若此时内存中没有空闲物理块安置请求调入的新页面,则系统按预定的置换策略自动选择一个或一些在内存的页面,把它们换出到外存。这里的请求调入和置换功能都是相较实分页存储管理新增加的,是实现虚拟存储的主要功能。
为实现虚拟页式存储管理,页表表目需要增加外存块号、状态位、访问位或访问字段、修改位、存取控制字段等。其中,外存块号指出该页在外存的地址,供调入该页时用;状态位指示该页是否在内存,供程序访问时用,也是检查是否缺页的标志位;访问位或访问字段则是该页被访问过的标志或该页被访问过的次数,它和修改位一起供页面置换用;修改位表示该页是否被修改过;存取控制字段则用来限制页面被安全共享。

(四)页面调度算法

由缺页中断服务程序将所需的页面调入内存,若此时内存中没有空闲物理块安置请求调入的新页面,则系统按预定的置换策略自动选择一个(请求调入策略)或一些(预调入策略)在内存的页面,把它们换出到外存。页面调度算法也称淘汰算法或置换算法,其性能好坏对系统效率影响很大。它不仅可以用于页面调度,也可用于快表表目的更新以及段的调度。

(五)最佳淘汰算法（OPT淘汰算法）

这是美国IBM 的 Belady于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的,或者过最长的时间后才会被访问的页面。显然,采用这种算法会保证最低的缺页率,但它是无法实现的,因为它必须知道页面“将来”的访问情况。不过,该算法仍有一定意义,可作为衡量其他算法优劣的一个标准。

（六）先进先出淘汰算法（FIFO淘汰算法）

这是最早出现的淘汰算法。该算法总是淘汰最先进入内存的页面。它实现简单,只需把进程已调入内存的页面,按先后次序链成一个队列,并设置一个所谓的替换指针,使它总是指向内存中最老的页面。但该算法效率不高,因为它与进程实际的运行规律不相适应,比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。另外,它还有被Belady在1969年发现的异常现象(被称为“Belady现象”),即增加内存块数后进程的缺页率不降反增，具体例子可考虑页面访问序列为1、2、3、4、1、2、5、1、2、3、4、5的进程分别获得3块内存和4块内存的情况。

(七)最近最久未用淘汰算法（LRU淘汰算法）

该算法每次都选择最近最久未使用的页面淘汰,即淘汰最后一次访问时间距当前时间间隔最长的页面。前面的OPT算法使用页面将要被访问的时间， LRU算法使用页面最后一次被访问的时间。二者唯一的差别是:前者是向前看的,而后者是向后看的。如果设R(S)是页面访问序列S的反序,可以认为:OPT算法用于S上的缺页率=LRU算法用于R(S)上的缺页率。
LRU 的两个实现算法如下：
①计时法。对于每一页面增设一个访问时间计时器,每当一个页面被访问时,当时的绝对时钟内容被复制到对应的访问时间计时器中,这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时,选取访问时间计时器的值最小的页面。
②堆栈法。按照页面最后一次访问的时间次序将页面号依次地放入堆栈中。当一个页面被访问时,其对应的页面号被置入栈顶(包括新页面访问后,其页号置人栈顶以及在内存的页面刚刚被访问后,其页号被从栈中原来的位置移至栈顶);淘汰时,取栈底的页面号所对应的页面。这里的“栈”显然不是通常所定义的先进后出的堆栈,只不过可以看成是一个特殊的堆栈或者队列。为了便于实现对栈中任一处内容的操作,它应使用双向链表来构造,其链头和链尾各需一个指针。
LRU 的实现开销是很大的,必须有硬件的支持,完全由软件实现其速度至少会降低 10 倍,因此LRU近似算法更实用些。

五、代码实现

#include<bits/stdc++.h>
using namespace std;

const int phyBlockNum = 3;//内存物理块数
vector <int> pageList({7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1});//调入页面序列
//vector <int> pageList({3,3,1,3,2,3,0,1,3,2,1,2,3,0,1,1,3,2,1,2});

int missingCount ;//统计缺页次数
int replaceCount;//统计置换次数
struct Page{  //不同算法中每个页面的附加信息
    int pageIfo; //页面号
    int addIfo; //页面附加信息（ OPT 中表示重复元素距离，LRU中表示计时器）
    int index;//页面号下标
};

vector <Page> phyBlock(phyBlockNum, {-1,-1,-1}); //内存物理块
int isVisited; //标志位表示是否需要页面替换
void ResultAnalysis();

void init( ){  //内存初始化
    vector <Page> temp(phyBlockNum, {-1,-1,-1});//-1表示物理块空闲
    phyBlock = temp;//初始化
    missingCount = 0; //缺页次数置0
    replaceCount = 0;//置换次数置0
}

//输出内存信息
void printf_(int i,int flag){
    printf("\n%d\t",pageList[i]);
    for (int j = 0; j < phyBlockNum; j++){
        if (phyBlock[j].pageIfo == -1) break;
        printf("  |%d|\t",phyBlock[j].pageIfo);
    }
    if(flag) cout << "缺页置换";
}

void FIFO( ){
    int pointer = 0;//指针指向内存中最老留存的页面
    for (int i = 0; i < pageList.size(); i++){
        isVisited = 0;//是否需要进行置换
        for (int j = 0; j < phyBlockNum; j++){
          //分三种情况
            if (phyBlock[j].pageIfo == pageList[i]){ //1.如果页面在内存中，
                isVisited = 1;   //已找到，不需要置换，标志位为1
                printf_(i,0);
                break;
            }
            else if (phyBlock[j].pageIfo == -1){ //2.如果页面不在内存中且物理块有空闲块
                phyBlock[j].pageIfo = pageList[i]; //页面装入内存块
                isVisited = 1;//已找到，不需要置换，标志位为1
                missingCount++ ; //页面中断次数+1
                printf_(i,0);
                break;
            }
        }
        //页面置换
        if (!isVisited){//3.如果页面不在内存中且物理块没有空闲块
            phyBlock[pointer].pageIfo= pageList[i];//进行FIFO页面置换
            pointer++;//指针向后移动
            if (pointer == phyBlockNum) pointer = 0;//指针指到尾部再重头开始
            missingCount++ ;//页面中断次数+1
            replaceCount++;//页面置换次数+1
            printf_(i,1);//展示内存信息
        }
    }
    ResultAnalysis();//结构分析
}

void OPT(){
    init();//初始化
    Page page[pageList.size( )]; //预先处理将来页面信息
    map <int,int> mp; //统计重复元素
    for(int i = 0; i < pageList.size(); i++){ //数据预处理（复杂度O(n)）
        page[i].pageIfo =  pageList[i];
        page[i].addIfo = -1;
        page[i].index = i;
        int num = pageList[i];
        if(mp.find(num) == mp.end()) mp[num] = i;
        else{
            page[mp[num]].addIfo = i - mp[num];
            mp[num] = i;
        }
    }
    for (int i = 0; i < pageList.size(); i++){
        isVisited = 0;//是否需要进行置换
        for (int j = 0; j < phyBlockNum; j++){
               //分三种情况
            if (phyBlock[j].pageIfo == page[i].pageIfo){ //1.如果页面在内存中
                phyBlock[j] = page[i];//更新附加信息
                isVisited = 1;
                printf_(i,0);
                break;
            }
            else if (phyBlock[j].pageIfo == -1){//2.如果页面不在内存中且物理块有空闲块
                phyBlock[j] = page[i];//页面装入空闲块
                isVisited = 1;
                missingCount++;//缺页中断次数
                printf_(i,0);
                break;
            }
        }
        if (!isVisited){//3.如果页面不在内存中且物理块没有空闲块
            int maxn = -1, pos = -1; // pos记录以后永不使用或者最长时间后才会被防问页面的位置
            for (int j = 0; j < phyBlockNum; j++){
                if(phyBlock[j].addIfo == -1){ //-1表示以后永不使用
                    pos = j;
                    break;
                }
                int length = phyBlock[j].addIfo - i + phyBlock[j].index;
                if(length > maxn) maxn = length, pos = j;//找最大值表示最久未被访问
               // 找到当前位置下以后永不使用的,或者过最长的时间后才会被访问的页面
            }
            phyBlock[pos] = page[i];
            missingCount++;
            replaceCount++;
            printf_(i,1);
        }
    }
    ResultAnalysis();
}

void LRU(){
    init();
    int time = -1;
    for (int i = 0; i < pageList.size(); i++){
        time ++;//页面每次进入改变计时器+1
        isVisited = 0; //是否需要进行置换
        for (int j = 0; j < phyBlockNum; j++){
            if (phyBlock[j].pageIfo == pageList[i]){//1.如果页面在内存中
                phyBlock[j].addIfo = time;//附加信息记录计时器
                isVisited = 1;
                printf_(i,0);
                break;
            }
            else if (phyBlock[j].pageIfo == -1){//2.如果页面不在内存中且物理块有空闲块
                phyBlock[j].pageIfo = pageList[i];
                phyBlock[j].addIfo = time;
                isVisited = 1;
                missingCount++;
                printf_(i,0);
                break;
            }
        }
        if (!isVisited){//3.如果页面不在内存中且物理块没有空闲块
            int minn = INT_MAX, pos = -1; //pos记录最近最久未被使用过的位置
            for (int j = 0; j < phyBlockNum; j++){
                if(phyBlock[j].addIfo < minn) minn = phyBlock[j].addIfo, pos = j;
            } //for循环找到计时器最小值页面下标
            phyBlock[pos].pageIfo = pageList[i];
            phyBlock[pos].addIfo = time;
            missingCount++;
            replaceCount++;
            printf_(i,1);
        }
    }
    ResultAnalysis();
}

int main( ){
     init();//信息初始化
    cout <<"--------------页面调度算法---------------\n";
    cout <<"\n-------1.先进先出淘汰算法FIFO------------\n";
    cout <<"页面号\t";
    for(int i=0; i<phyBlockNum; i++) printf("物理块%d ",i+1);
    FIFO();//先进先出淘汰算法
    cout <<"\n----------2.最佳淘汰算法OPT---------------\n";
    cout <<"页面号\t";
    for(int i=0; i<phyBlockNum; i++) printf("物理块%d ",i+1);
    OPT();//最佳淘汰算法
    cout <<"\n-------3.最近最久未被使用算法LRU--------\n";
    cout <<"页面号\t";
    for(int i=0; i<phyBlockNum; i++) printf("物理块%d ",i+1);
    LRU();//最近最久未用淘汰算法
    return 0;
}

//结果分析
void ResultAnalysis( ){
    printf("\n----------------结果分析------------------\n");
    printf("缺页中断次数:%d\n", missingCount);
    double a=(double)missingCount/pageList.size();
    printf("缺页中断率:%.2f%%\n", a*100);
    printf("置换次数:%d\n", replaceCount);
    printf("------------------------------------------\n\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
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/687603