【操作系统实验】内存管理_1、理解和掌握操作系统中fifo(先进先出)页面置换策略的工作原理。 2、培养学生编

【推荐阅读】
【操作系统实验】文件系统
【操作系统实验】磁盘管理实验

一、实验目的

1、了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
2、了解程序设计技术和内存泄露的原因

二、实验内容

1、模拟实现请求页式存储管理的几种基本页面置换算法
（1）最佳淘汰算法（OPT）
（2）先进先出的算法（FIFO）
（3）最近最久未使用算法（LRU））

三、实验原理

1、虚拟存储系统

UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。

2、页面置换算法

当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

（1）最佳淘汰算法（OPT）

选择永不使用或在未来最长时间内不再被访问的页面予以替换。

（2）先进先出的算法（FIFO）

选择在内存中驻留时间最久的页面予以替换。

（3）最近最久未使用算法（LRU）

选择过去最长时间未被访问的页面予以替换。

3、定义和产生指令序列

首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
A：50%的指令是顺序执行的
B：25%的指令是均匀分布在前地址部分
C：25%的指令是均匀分布在后地址部分
具体的实施方法是：
A：在[0，319]的指令地址之间随机选取一起点m
B：顺序执行一条指令，即执行地址为m+1的指令
C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
D：顺序执行一条指令，其地址为m’+1
E：在后地址[m’+2，319]中随机选取一条指令并执行
F：重复步骤A-E，直到320次指令
（2）将指令序列变换为页地址流
设：页面大小为1K；
用户内存容量4页到32页；
用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）
第10条-第19条指令为第1页（对应虚存地址为[10，19]）
………………………………
第310条-第319条指令为第31页（对应虚存地址为[310，319]）
按以上方式，用户指令可组成32页。

四、实验要求

1、画出每个页面置换算法流程图；

（1）最佳淘汰算法（OPT）

（2）先进先出的算法（FIFO）

（3）最近最久未使用算法（LRU））

2、程序代码

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#define N 320        //指令条数
int Instructions[N]; //指令的执行序列
int page[N];         //序列对应的页码
using namespace std;
void OPT(int index, int *memory, int Max);
void FIFO(int index, int *memory, int Max, int &fistPage);
void LRU(int index, int *memory, int Max);
//findValue()返回数组arr[start,end]中该元素value的位置（从左边开始数）
int findValue(int arr[], int start, int end, int value)
{
    int i = start;
    for (; i < end; i++)
        if (arr[i] == value)
            return i;
    return -1;
}
//findValueForR()返回数组arr[start,end]中该元素value的位置（从右边开始数）
int findValueForR(int arr[], int start, int end, int value)
{
    int i = end;
    for (; i > start; i--)
        if (arr[i] == value)
            return i;
    return -1;
}
//（1）最佳淘汰算法（OPT）：选择永不使用或在未来最长时间内不再被访问的页面予以替换。index：第index条指令  memory：内存, Max：内存块数
void OPT(int index, int *memory, int Max)
{
    int MT_WithoutAccess = -2; //Maximum time without access:永不使用或未来内不再被访问的页面最长时间
    int pageNums = -1;         //永不使用或在未来最长时间内不再被访问的页面在内存中位置
    int temp;
    for (int i = 0; i < Max; i++)
    {
        temp = findValue(page, index, N, memory[i]);
        if (temp == -1) //永不使用的页面
        {
            pageNums = i;
            break;
        }
        else if (temp > MT_WithoutAccess) //最长时间内不再被访问的页面
        {
            pageNums = i;
            MT_WithoutAccess = temp;
        }
    }
    memory[pageNums] = page[index]; //置换页面
}
//（2）先进先出的算法（FIFO）：选择在内存中驻留时间最久的页面予以替换。index：第index条指令  memory：内存,fistPage:内存中最先进入的页面 Max：内存块数
void FIFO(int index, int *memory, int Max, int &fistPage)
{
    memory[fistPage] = page[index]; //置换页面
    fistPage = (fistPage + 1) % Max;
}
//（3）最近最久未使用算法（LRU）：选择过去最长时间未被访问的页面予以替换。index：第index条指令  memory：内存, Max：内存块数
void LRU(int index, int *memory, int Max)
{
    int MT_WithoutAccess = 320; //过去最长时间未被访问的指令的位置
    int pageNums = -1;
    int temp;
    for (int i = 0; i < Max; i++)
    { //找到内存中页面上一次使用在page中
        temp = findValueForR(page, index, N, memory[i]);
        if (temp < MT_WithoutAccess)
        {
            MT_WithoutAccess = temp;
            pageNums = i;
        }
    }
    memory[pageNums] = page[index]; //置换页面
}
//页面置换算法
void PageReplacement(int Max) //Max:内存大小，即为能存储的最大页数
{
    int OPTmemory[Max] = {-1}; //内存
    int FIFOmemory[Max] = {-1};
    int LRUmemory[Max] = {-1};
    int OPTnums = 0, FIFOnums = 0, LRUnums = 0;             //记录内存是否满了
    int OPTMisspere = 0, FIFOMisspere = 0, LRUMisspere = 0; //缺页次数Misspere
    int fistPage = 0;                                       //内存中最先进入的页面，用于FIFO算法
    for (int i = 0; i < 320; i++)
    {
        if (findValue(OPTmemory, 0, Max, page[i]) == -1) //缺页中断
        {                                                //内存未满，直接容纳新页
            if (OPTnums < Max)
                OPTmemory[OPTnums++] = page[i];
            else
            {                           //内存已满,置换新页
                OPT(i, OPTmemory, Max); //1）最佳淘汰算法（OPT）
                OPTMisspere++;          //记录缺页次数
            }
        }
        if (findValue(FIFOmemory, 0, Max, page[i]) == -1) //缺页中断
        {                                                 //内存未满，直接容纳新页
            if (FIFOnums < Max)
                FIFOmemory[FIFOnums++] = page[i];
            else
            {                                       //内存已满,置换新页
                FIFO(i, FIFOmemory, Max, fistPage); //2）先进先出的算法（FIFO）
                FIFOMisspere++;
            }
        }
        if (findValue(LRUmemory, 0, Max, page[i]) == -1) //缺页中断
        {                                                //内存未满，直接容纳新页
            if (LRUnums < Max)
                LRUmemory[LRUnums++] = page[i];
            else
            {                           //内存已满,置换新页
                LRU(i, LRUmemory, Max); //（3）最近最久未使用算法（LRU）
                LRUMisspere++;
            }
        }
    }
    cout << "最佳淘汰算法（OPT）命中率：" << (320 - Max - OPTMisspere) * 100.0 / 320 << "%" << endl;
    cout << "先进先出的算法（FIFO）命中率：" << (320 - Max - FIFOMisspere) * 100.0 / 320 << "%" << endl;
    cout << "最近最久未使用算法（LRU）命中率：" << (320 - Max - LRUMisspere) * 100.0 / 320 << "%" << endl;
}
//生成测试数据
void init()
{
    srand((unsigned)time(NULL));
    int i = 0, n, m, x;
    bool flag = true;
    while (i < 319)
    {
        m = rand() % 320; //A
        Instructions[i] = m;
        page[i] = m / 10;
        if (i >= 319)
            continue;
        Instructions[++i] = m + 1; //B
        page[i] = (m + 1) / 10;
        if (i >= 319)
            continue;
        n = rand() % (m + 2);
        Instructions[++i] = n; //C
        page[i] = n / 10;
        if (i >= 319)
            continue;
        Instructions[++i] = n + 1; //D
        page[i] = (n + 1) / 10;
        while (flag && i < 320)
        {
            x = rand() % 320;
            if (x >= n + 2 && x <= 319)
            {
                Instructions[++i] = x; //E
                page[i] = x / 10;
                flag = false;
            }
        }
    }
}
//菜单
void show()
{
    cout << "***********菜单**************" << endl;
    cout << "*****************************" << endl;
    cout << "******  1、清屏         ******" << endl;
    cout << "******  2、内存管理     ******" << endl;
    cout << "******  任意数字退出    ******" << endl;
    cout << "*****************************" << endl;
    cout << "*****************************" << endl;
}
int main()
{
    while (true)
    {
        int select;
        show();
        cout << "请输入命令！" << endl;
        cin >> select;
        switch (select)
        {
        case 1:
        {
            system("cls");
            break;
        }
        case 2:
        {
            init();
            // int n;
            // cout << "请输入内存大小！" << endl;
            // cin >> n;
            // PageReplacement(n);
            srand((unsigned)time(NULL));
            for (int i = 4; i < 32; i++)
            {
                cout << "内存块数:" << i << endl;
                PageReplacement(i);
            }
            break;
        }
        default:
            system("pause");
            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
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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

五、截屏输出实验结果；

命中率对比