实验八、页面置换模拟程序设计

一、实验目的

  1. 通过软件模拟页面置换过程，加深对请求页式存储管理实现原理的理解
  2. 理解和掌握OPT、FIFO和LRU三种页面置换算法，深入分析三者之间的优缺点

二、实验环境

  • 硬件环境：计算机一台，局域网环境；
  • 软件环境：Linux Ubuntu 操作系统，gcc 编译器；

三、实验内容和步骤

  1. 重要数据结构

    1. 页表数据结构
    1
    2
    3
    4
    5
    6
    7
    typedef struct {
        int vmn;
        int pmn;
        int exist;
        int time;
    } vpage_item;
    vpage_item page_table[VM_PAGE];
    • 页表是虚地址向物理地址转换的依据，包含虚页号所对应的实页号，是否在物理内存中。
    • 页表中增加了一个time项，用于替换算法选择淘汰页面，在不同的替换算法中，time含义不一样。
    • 在LRU算法中，time为最近访问的时间。该虚页每访问一次，time置为当前访问时刻，淘汰页面时，淘汰time值最小的，即最久没有被使用的。
    • 在FIFO算法中，time为该虚页进入内存的时间。只有当该虚页从外存进入内存时，才置该标志。淘汰页面时，淘汰time值最小的，即最早进入内存的虚页。
    • 在OPT算法中，time没有任何意义。
    1. 物理页位图数据结构
    1
    vpage_item *ppage_bitmap[PM_PAGE];

    物理页位图是用于记录物理页是否被使用，用于物理页内存的分配。正常情况下是一个数组，元素值为0时，代表相应物理页没有装入任何虚页，值为1时，代表该物理页装入虚页。但为方便替换算法检索要替换出去的虚页，数组的每个元素值为当前放在该物理页的页表项的指针。若值为NULL，则表示该物理页没有被占用，当值不为NULL时，表示正在占用该物理页的虚页。

    1. 指令相关数据结构
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //每条指令信息
    typedef struct {
    int  num;
    int  vpage;
    int  offset;
    int  inflow;
    } instr_item;
    //指令数组
    instr_item instr_array[TOTAL_INSTR];
    //指令流数据结构
    struct instr_flow {
    instr_item *instr;
    struct instr_flow *next;
    };
    //指令流头数据结构
    struct instr_flow_head {
    int num;
    struct instr_flow *next;
    };
    struct instr_flow_head iflow_head;

    每条指令包括指令号、该指令所属虚页及页内偏移（这两项可以根据指令号计算出来，增加这两项是为了方便编程）。inflow 是一个辅助项，用于构建指令流。
    本题要求，按照规则生成的指令流中，应包含所有的共320条指令。但每次随机生成的指令号，可能已在指令流中，因此最终指令流中的指令数可能远远超过320条指令。
    设置 inflow 的目的是为了便于统计是否320条指令均已加入到指令流中。在该条指令加入到指令流中时，如果 inflow 为0，表示该指令尚未在指令流中，则统计数加1；如果 inflow 为1，表示该指令已经加入过指令流，该指令虽然再次加入指令流，但统计数不增加。这样，当统计计数为320时，表示所有的指令均已加入到指令流中。
    struct instr_flow为指令流数据结构，struct instr_flow_head始终指向指令流的头，其中 num 用于指令流中指令数量计数，用于计算缺页率。

  2. 主程序

主程序图

  1. 指令流生成流程
    指令流的生成按照实验要求生成，其算法流程如下图所示:

指令流生成流程图

  1. 物理内存分配流程
    物理内存分配时，需要根据当前置换算法选择淘汰页面。其算法流程下图所示:

物理内存分配流程图

  1. 运行流程

运行流程图

  1. 三种置换算法

    1. OPT算法：
      在当前指令的后续指令流中，寻找已在内存中的虚页，哪个最远才被使用，反过来，如果先找到最近三个（物理页面总数为4）也在内存中的虚页，则剩下的那个虚页肯定就是最远才被使用的虚页，该虚页被淘汰，其物理内存分配给当前指令所在的虚页。
    2. FIFO算法：
      在已在物理内存中的虚页中，寻找 time 最小的虚页（最早进入物理内存的虚页），该虚页即是被淘汰的虚页。
    3. LRU算法：
      思想同 FIFO 算法，但 time 最小的虚页含义是最久没有被使用的虚页。

    在这三种置换算法中，OPT的算法稍微复杂一些，下图给了该的程序流程图:

    OPT算法程序流程图

  2. 实验代码

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
205
206
207
#include<stdio.h>
#include<stdlib.h>

#define VM_PAGE 7      /*假设每个页面可以存放10条指令,则共有32个虚页*/
#define PM_PAGE 4         /*分配给作业的内存块数为4*/
#define TOTAL_INSERT 18

typedef struct {
    int vmn;
    int pmn;
    int exist;
    int time;
} vpage_item;
vpage_item page_table[VM_PAGE];

vpage_item *ppage_bitmap[PM_PAGE];

int vpage_arr[TOTAL_INSERT] = {1, 2, 3, 4, 2, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6};

void init_data() //数据初始化
{
    int i;
    for (i = 0; i < VM_PAGE; i++) {
        page_table[i].vmn = i + 1;  //虚页号
        page_table[i].pmn = -1;    //实页号
        page_table[i].exist = 0;
        page_table[i].time = -1;

    }
    for (i = 0; i < PM_PAGE; i++) /*最初4个物理块为空*/
    {
        ppage_bitmap[i] = NULL;
    }
}

void FIFO()/*FIFO页面置换算法*/
{
    int k = 0;
    int i;
    int sum = 0;
    int missing_page_count = 0;
    int current_time = 0;
    bool isleft = true;   /*当前物理块中是否有剩余*/
    while (sum < TOTAL_INSERT) {
        if (page_table[vpage_arr[sum] - 1].exist == 0) {
            missing_page_count++;
            if (k < 4) {
                if (ppage_bitmap[k] == NULL) /*找到一个空闲物理块*/
                {
                    ppage_bitmap[k] = &page_table[vpage_arr[sum] - 1];
                    ppage_bitmap[k]->exist = 1;
                    ppage_bitmap[k]->pmn = k;
                    ppage_bitmap[k]->time = current_time;
                    k++;
                }
            } else {
                int temp = ppage_bitmap[0]->time;    /*记录物理块中作业最早到达时间*/
                int j = 0;                    /*记录应当被替换的物理块号*/
                for (i = 0; i < PM_PAGE; i++) {
                    if (ppage_bitmap[i]->time < temp) {
                        temp = ppage_bitmap[i]->time;
                        j = i;
                    }
                }
                ppage_bitmap[j]->exist = 0;
                ppage_bitmap[j] = &page_table[vpage_arr[sum] - 1];      /*更新页表项*/
                ppage_bitmap[j]->exist = 1;
                ppage_bitmap[j]->pmn = j;
                ppage_bitmap[j]->time = current_time;
            }
        }
        current_time++;
        sum++;
    }
    printf("FIFO算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f", missing_page_count,
           missing_page_count / (float) TOTAL_INSERT, missing_page_count - 4,
           (missing_page_count - 4) / (float) TOTAL_INSERT);
}

void LRU() {
    int k = 0;
    int i;
    int sum = 0;
    int missing_page_count = 0;
    int current_time = 0;
    bool isleft = true;   /*当前物理块中是否有剩余*/
    while (sum < TOTAL_INSERT) {
        if (page_table[vpage_arr[sum] - 1].exist == 0) {
            missing_page_count++;
            if (k < 4) {
                if (ppage_bitmap[k] == NULL) /*找到一个空闲物理块*/
                {
                    ppage_bitmap[k] = &page_table[vpage_arr[sum] - 1];
                    ppage_bitmap[k]->exist = 1;
                    ppage_bitmap[k]->pmn = k;
                    ppage_bitmap[k]->time = current_time;
                    k++;
                }
            } else {
                int temp = ppage_bitmap[0]->time;    /*记录物理块中作业最早到达时间*/
                int j = 0;                    /*记录应当被替换的物理块号*/
                for (i = 0; i < PM_PAGE; i++) {
                    if (ppage_bitmap[i]->time < temp) {
                        temp = ppage_bitmap[i]->time;
                        j = i;
                    }
                }
                ppage_bitmap[j]->exist = 0;
                ppage_bitmap[j] = &page_table[vpage_arr[sum] - 1];      /*更新页表项*/
                ppage_bitmap[j]->exist = 1;
                ppage_bitmap[j]->pmn = j;
                ppage_bitmap[j]->time = current_time;
            }
        } else {
            for (i = 0; i < PM_PAGE; i++) {
                if (ppage_bitmap[i]->vmn == page_table[vpage_arr[sum] - 1].pmn) {
                    ppage_bitmap[i]->time = current_time;
                    break;
                }
            }
        }
        current_time++;
        sum++;
    }
    printf("LRU算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f", missing_page_count,
           missing_page_count / (float) TOTAL_INSERT, missing_page_count - 4,
           (missing_page_count - 4) / (float) TOTAL_INSERT);
}

void OPT() {
    int k = 0;
    int sum = 0;
    int missing_page_count = 0;
    int current_time = 0;
    bool isleft = true;   /*当前物理块中是否有剩余*/
    while (sum < TOTAL_INSERT) {
        if (page_table[vpage_arr[sum] - 1].exist == 0) {
            missing_page_count++;
            if (k < 4) {
                if (ppage_bitmap[k] == NULL) /*找到一个空闲物理块*/
                {
                    ppage_bitmap[k] = &page_table[vpage_arr[sum] - 1];
                    ppage_bitmap[k]->exist = 1;
                    ppage_bitmap[k]->pmn = k;
                    ppage_bitmap[k]->time = current_time;
                    k++;
                }
            } else {
                int used[VM_PAGE] = {0}, i, l;
                int count = 0;
                for (i = sum + 1; i < TOTAL_INSERT; i++) {
                    if (page_table[vpage_arr[i] - 1].exist == 1) {
                        used[page_table[vpage_arr[i] - 1].vmn - 1] = 1;
                    }
                    int count = 0;
                    for (l = 0; l < VM_PAGE; l++) {
                        if (used[l] == 1) {
                            count++;
                        }
                    }
                    if (count == 3) {
                        break;
                    }
                }
                for (i = 0; i < PM_PAGE; i++) {
                    if (used[ppage_bitmap[i]->vmn - 1] == 0) {
                        ppage_bitmap[i]->exist = 0;
                        ppage_bitmap[i] = &page_table[vpage_arr[sum] - 1];
                        ppage_bitmap[i]->exist = 1;
                        ppage_bitmap[i]->pmn = i;
                        ppage_bitmap[i]->time = current_time;
                    }
                }
            }
        }
        current_time++;
        sum++;
    }
    printf("OPT算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f", missing_page_count,
           missing_page_count / (float) TOTAL_INSERT, missing_page_count - 4,
           (missing_page_count - 4) / (float) TOTAL_INSERT);
}

int main() {
    int a;
    printf("\t\t\t\t*****************请输入需要选择的页面置换算法********************\n");
    printf("\t\t\t\t\t\t\t1:FIFO\n\t\t\t\t\t\t\t2:LRU\n\t\t\t\t\t\t\t3:OPT\n\t\t\t\t\t\t\t输入0结束\n");
    do {
        scanf("%d", &a);
        switch (a) {
            case 1:
                init_data();
                FIFO();
                break;
            case 2:
                init_data();
                LRU();
                break;
            case 3:
                init_data();
                OPT();
                break;
        }
    } while (a != 0);
    return 0;
}

四、实验总结

  1. 分析实验结果产生的原因，总结从实验观察到的结果。分析三种置换算法的缺页率的差异。
    答：FIFO 算法每次先替换最先进入的页面，LRU 算法每次先替换最近最久未使用的页面，OPT 算法每次先替换将来最长时间内不再被访问的页面。通过计算得到，FIFO 算法缺页13次，置换9次。LRU 算法缺页10次，置换6次。OPT 算法缺页7次，置换3次。

  2. 结合操作系统课程中讲授的原理，写出本次实验的心得体会。
    答：FIFO 算法、LRU 算法和 OPT 算法是操作系统中用来管理内存的置换算法，用于决定哪些页应该被从内存中交换出去，以便为正在运行的进程腾出空间。 其中：

    • FIFO 算法是选择在内存中驻留时间最久的页面予以替换，实现简单，要求的硬件支持较少。但是，它所依据的条件是各个页面调入内存的时间，而页面调入内存的先后并不能反映页面的使用情况。
    • LRU 算法是选择过去最长时间未被访问的页面予以替换，利用“最近的过去”代替“最近的将来”，以此模拟 Optimal 算法，是实际应用中缺页率最低的算法。 但是，其实际应用时要求较多的硬件支持，因而多采用近似算法。
    • OPT 算法是选择永不使用或在未来最长时间内不再被访问的页面予以替换。它可保证获得最低的缺页率，并且可以用来评价其他算法。但是，目前该算法是无法实现的。
课程报告
#河北工业大学 #操作系统实验
实验八、页面置换模拟程序设计
https://flowerdown.org/posts/20230612-203744.html
作者
Unrealfeather
发布于
2023年6月12日
许可协议