虚拟内存管理模拟

虚拟内存管理系统模拟实践

这个项目堪称操作系统课程实践中最牛掰的项目。代码量虽然不大，只有200+行，但是实现思路比较困难，对各种数据结构的配合比较高。

一.基本原理概述

1.任务综述：

本项目编写C程序来实现一个虚拟内存到物理内存的转换。程序使用了TLB和页表，并通过LRU进行页面替换。

2.页表：

采用一个长度为256的数组来寻址。由于每一个地址的地址位有8位，从而用256长度足够。页表中记录对应到内存中的位置，与低8位的偏移量一起作为内存地址。

3.TLB：

一个高速内存。当要进行内存寻址时首先在TLB中进行查找，如果没有的话才到页表中查找，同时进行TLB中的元素的更新。其长度很短，只有16位。

4.页面替换

由于我们的内存长度只有128而基地址有256个，所以不可能所有的地址都能够存到内存中。那如果有一个地址没有在内存中而内存帧已满，就需要进行页面替换。我们这里采用的是LRU进行内存替换。即：选择最长时间没有被访问到的帧来进行替换。这一要求的实现用了一个链接栈。

二.代码逻辑

主要函数的代码段的逻辑是这样的：

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
int address_get(int pagenum)//不管是从TLB还是从页表中，最后都要给出一个内存中的地址！！如果内存中没有空闲帧就采用页面置换算法
{
    for (int i = 0; i < TLB_SIZE; i++)//遍历整个TLB
    {
        if (tlb_key[i] == pagenum)//找到了！有记录！
        {
            ++tlb_hit;//成功数++
            update_tlbstack(pagenum);//在这一步更新中，num_tlb的值不变，因为原来就有只是改变了在栈中的顺序而已
            return tlb_value[i];//直接在TLB里面找到的，省事！！
        }
    }//这里应该没有问题
    if (valid[pagenum])//虽然tlb里没有，但是页表里显示这个帧可以用，也挺方便
    {
        if (num_tlb < TLB_SIZE)//TLB没有满
        {
            tlb_key[num_tlb] = pagenum;//将新东西写入tlb中
            tlb_value[num_tlb] = page[pagenum];
            update_tlbstack(pagenum);//在这一步更新中，num_tlb的值+1

        } else//满了
        {
            int result = delete_tlbstack();//要被删除的那个最不活跃的pagenum
            for (int i = 0; i < TLB_SIZE; i++) {
                if (tlb_key[i] == result)//找到了那个
                {
                    tlb_key[i] = pagenum;
                    tlb_value[i] = page[pagenum];
                    break;
                }
            }
            update_tlbstack(pagenum);
        }
        return page[pagenum];
    }
    //坏的情况————内存里没有！！
    ++fault_num;//统计次数加
    int address_num = get_frame();//可以被写进去的内存地址
    if (address_num != -1)//谢天谢地内存没有满
    {
        fseek(back_store, pagenum * FRAME_SIZE, SEEK_SET);
        fread(mem[address_num], sizeof(char), FRAME_SIZE, back_store);//读进那个可用的内存
        page[pagenum] = address_num;
        valid[pagenum] = true;//该页表可以被使用
        if (num_tlb < TLB_SIZE)//TLB没有满
        {
            tlb_key[num_tlb] = pagenum;//将新东西写入tlb中
            tlb_value[num_tlb] = page[pagenum];
            update_tlbstack(pagenum);//在这一步更新中，num_tlb的值+1
        } else//满了
        {
            int result = delete_tlbstack();//要被删除的那个最不活跃的pagenum
            for (int i = 0; i < TLB_SIZE; i++) {
                if (tlb_key[i] == result)//找到了那个
                {
                    tlb_key[i] = pagenum;
                    tlb_value[i] = page[pagenum];
                    break;
                }
            }
            update_tlbstack(pagenum);
        }
        update_memstack(address_num);
        return address_num;//最后返回那个地址
    }
    //更糟糕的情况内存满了
    address_num = delete_memstack();
    //首先把表中的清除了
    for(int i=0;i<PAGE_SIZE;i++)
    {
        if(page[i]==address_num)
        {
            valid[i]=false;
            break;
        }
    }
    fseek(back_store, pagenum * FRAME_SIZE, SEEK_SET);
    fread(mem[address_num], sizeof(char), FRAME_SIZE, back_store);
    page[pagenum] = address_num;
    valid[pagenum] = true;//该页表可以被使用
    if (num_tlb < TLB_SIZE)//TLB没有满
        {
        tlb_key[num_tlb] = pagenum;//将新东西写入tlb中
        tlb_value[num_tlb] = page[pagenum];
        update_tlbstack(pagenum);//在这一步更新中，num_tlb的值+1
        } else//满了
        {
        int result = delete_tlbstack();//要被删除的那个最不活跃的pagenum
        for (int i = 0; i < num_tlb; i++) {
            if (tlb_key[i] == result)//找到了那个
                {
                tlb_key[i] = pagenum;
                tlb_value[i] = page[pagenum];
                break;
                }
        }
        update_tlbstack(pagenum);
        }
    update_memstack(address_num);
    return address_num;

}

这段代码实现了给定虚拟内存到物理内存的映射；
首先在TLB中查找，同时维护TLB的栈。保证在TLB满的时候如果有新的元素要被插入TLB，就把历史最远古的那一个条目移除，这个功能是通过函数update_tlbstack()实现的。

如果在TLB中找不到，那么到页表中查找。如果valid[pagenum]=true,说明内存中存有此项，我们直接在页表中找到，并且更新TLB即可。

更糟糕的情况，这一项在内存中现在没有，那么我们获取一个空的内存帧将它存入内存中。更新内存栈和TLB栈。

最最不济的情况，不仅在内存中没有，甚至内存还满了。这个时候就要使用我们的页面调度算法了。通过delete_memstack()函数选出要被更新的内存，更新其值并在将其从页表和TLB中删除。最后存入新的值，并且维护我们的两个栈。

三.代码实现

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PAGE_SIZE 256
#define FRAME_NUMBER 128
#define FRAME_SIZE 256
#define TLB_SIZE 16
#define true 1
#define false 0
char mem[FRAME_NUMBER][FRAME_SIZE];//内存
int page[PAGE_SIZE];//页表
int tlb_key[TLB_SIZE];//tlb里的键
int tlb_value[TLB_SIZE];//tlb里的值
int valid[PAGE_SIZE];//页表中每个元素是否可用，开始时当然设置成不可用
int fault_num;
int tlb_hit;
FILE *back_store;
struct stack_element {
    int value;
    struct stack_element *next;
};
int num_tlb;
int num_mem;
struct stack_element *mem_head;
struct stack_element *mem_tail;
struct stack_element *tlb_head;
struct stack_element *tlb_tail;

int delete_tlbstack()//当某一个表满了的时候把栈底的元素删除
{
    if (num_tlb < TLB_SIZE) {
        printf("something wrong happened\n");
        return -1;
    }
    int result = tlb_head->next->value;
    struct stack_element *delete = tlb_head->next;
    tlb_head->next = tlb_head->next->next;
    free(delete);
    --num_tlb;
    return result;
}

int delete_memstack()//当某一个表满了的时候把栈底的元素删除
{
    if (num_mem < TLB_SIZE) {
        printf("something wrong happened\n");
        return -1;
    }
    int result = mem_head->next->value;
    struct stack_element *delete = mem_head->next;
    mem_head->next = mem_head->next->next;
    free(delete);
    --num_mem;
    return result;
}

void update_tlbstack(int pagenum)//该函数维护tlb的栈,调用的前提是pagenum的页码被调用了
{
    if (tlb_head == NULL && tlb_tail == NULL)//如果链表为空，那么将该pagenum插入链表
    {
        tlb_tail = (struct stack_element *) malloc(sizeof(struct stack_element));
        tlb_tail->value = pagenum;
        tlb_tail->next = NULL;
        tlb_head = (struct stack_element *) malloc(sizeof(struct stack_element));
        tlb_head->next = tlb_tail;//注意head是空的
        ++num_tlb;
        return;
    }
    struct stack_element *temp = tlb_head;
    while (temp != tlb_tail) {
        if (temp->next->value == pagenum) {
            if(temp->next==tlb_tail)
            {
                tlb_tail = temp;
            }
            struct stack_element *delete = temp->next;
            temp->next = temp->next->next;
            --num_tlb;
            free(delete);

            break;
        }
        temp=temp->next;
    }
    //如果没找到就算了
    //将它插到最后面
    tlb_tail->next = (struct stack_element *) malloc(sizeof(struct stack_element));
    tlb_tail = tlb_tail->next;
    ++num_tlb;
    tlb_tail->value = pagenum;
    tlb_tail->next = NULL;
}

void update_memstack(int address)//该函数维护mem内存帧的栈
{
    if (mem_head == NULL && mem_tail == NULL)//如果链表为空，那么将该pagenum插入链表
    {
        mem_tail = (struct stack_element *) malloc(sizeof(struct stack_element));
        mem_tail->value = address;
        mem_tail->next = NULL;
        mem_head = (struct stack_element *) malloc(sizeof(struct stack_element));
        mem_head->next = mem_tail;//注意head是空的
        ++num_mem;
        return;
    }
    struct stack_element *temp = mem_head;
    while (temp != mem_tail) {
        if (temp->next->value == address) {
            if(temp->next==mem_tail)
            {
                mem_tail = temp;
            }
            struct stack_element *delete = temp->next;
            temp->next = temp->next->next;
            --num_mem;
            free(delete);
            break;
        }
        temp=temp->next;
    }
    //如果没找到就算了
    //将它插到最后面
    mem_tail->next = (struct stack_element *) malloc(sizeof(struct stack_element));
    mem_tail = mem_tail->next;
    ++num_mem;
    mem_tail->value = address;
    mem_tail->next = NULL;
}

int get_frame()//获得一个可以插入的内存帧
{
    return num_mem < FRAME_NUMBER ? num_mem : -1;
}

int address_get(int pagenum)//不管是从TLB还是从页表中，最后都要给出一个内存中的地址！！如果内存中没有空闲帧就采用页面置换算法
{
    for (int i = 0; i < TLB_SIZE; i++)//遍历整个TLB
    {
        if (tlb_key[i] == pagenum)//找到了！有记录！
        {
            ++tlb_hit;//成功数++
            update_tlbstack(pagenum);//在这一步更新中，num_tlb的值不变，因为原来就有只是改变了在栈中的顺序而已
            return tlb_value[i];//直接在TLB里面找到的，省事！！
        }
    }//这里应该没有问题
    if (valid[pagenum])//虽然tlb里没有，但是页表里显示这个帧可以用，也挺方便
    {
        if (num_tlb < TLB_SIZE)//TLB没有满
        {
            tlb_key[num_tlb] = pagenum;//将新东西写入tlb中
            tlb_value[num_tlb] = page[pagenum];
            update_tlbstack(pagenum);//在这一步更新中，num_tlb的值+1

        } else//满了
        {
            int result = delete_tlbstack();//要被删除的那个最不活跃的pagenum
            for (int i = 0; i < TLB_SIZE; i++) {
                if (tlb_key[i] == result)//找到了那个
                {
                    tlb_key[i] = pagenum;
                    tlb_value[i] = page[pagenum];
                    break;
                }
            }
            update_tlbstack(pagenum);
        }
        return page[pagenum];
    }
    //坏的情况————内存里没有！！
    ++fault_num;//统计次数加
    int address_num = get_frame();//可以被写进去的内存地址
    if (address_num != -1)//谢天谢地内存没有满
    {
        fseek(back_store, pagenum * FRAME_SIZE, SEEK_SET);
        fread(mem[address_num], sizeof(char), FRAME_SIZE, back_store);//读进那个可用的内存
        page[pagenum] = address_num;
        valid[pagenum] = true;//该页表可以被使用
        if (num_tlb < TLB_SIZE)//TLB没有满
        {
            tlb_key[num_tlb] = pagenum;//将新东西写入tlb中
            tlb_value[num_tlb] = page[pagenum];
            update_tlbstack(pagenum);//在这一步更新中，num_tlb的值+1
        } else//满了
        {
            int result = delete_tlbstack();//要被删除的那个最不活跃的pagenum
            for (int i = 0; i < TLB_SIZE; i++) {
                if (tlb_key[i] == result)//找到了那个
                {
                    tlb_key[i] = pagenum;
                    tlb_value[i] = page[pagenum];
                    break;
                }
            }
            update_tlbstack(pagenum);
        }
        update_memstack(address_num);
        return address_num;//最后返回那个地址
    }
    //更糟糕的情况内存满了
    address_num = delete_memstack();
    //首先把表中的清除了
    for(int i=0;i<PAGE_SIZE;i++)
    {
        if(page[i]==address_num)
        {
            valid[i]=false;
            break;
        }
    }
    fseek(back_store, pagenum * FRAME_SIZE, SEEK_SET);
    fread(mem[address_num], sizeof(char), FRAME_SIZE, back_store);
    page[pagenum] = address_num;
    valid[pagenum] = true;//该页表可以被使用
    if (num_tlb < TLB_SIZE)//TLB没有满
        {
        tlb_key[num_tlb] = pagenum;//将新东西写入tlb中
        tlb_value[num_tlb] = page[pagenum];
        update_tlbstack(pagenum);//在这一步更新中，num_tlb的值+1
        } else//满了
        {
        int result = delete_tlbstack();//要被删除的那个最不活跃的pagenum
        for (int i = 0; i < num_tlb; i++) {
            if (tlb_key[i] == result)//找到了那个
                {
                tlb_key[i] = pagenum;
                tlb_value[i] = page[pagenum];
                break;
                }
        }
        update_tlbstack(pagenum);
        }
    update_memstack(address_num);
    return address_num;

}

int fetch_memory(int num)//解码
{
    int pagenum = (num >> 8);
    int offset = (num & 255);
    return (int) mem[address_get(pagenum)][offset];
}

void initialize() {
    tlb_hit = fault_num = num_tlb = num_mem = 0;
    mem_head = mem_tail = tlb_head = tlb_tail = NULL;
    back_store = fopen("D:\\test\\tiaoshi\\P8\\BACKING_STORE.bin", "rb");
}

int main(int argc, char *argv[]) {
    FILE *readin = fopen("D:\\test\\tiaoshi\\P8\\addresses.txt", "r");
    FILE *output = fopen("D:\\test\\tiaoshi\\P8\\output.txt", "w");
    initialize();
    int address;
    while (~fscanf(readin, "%d", &address)) {
        int temp= address_get(address>>8);
        fprintf(output, "Virtual address: %d Phisical address: %d value: %d\n", address,
                256 * temp + (address & 255),
                (int)mem[temp][address&255]);
       //test
        /* printf("page = %d\n",page[address>>8]);
        for(int i=0;i<16;i++)
            printf("%d %d    ",tlb_key[i],tlb_value[i]);
        struct stack_element*temp = tlb_head->next;
        while(temp!=tlb_tail->next)
        {
            printf("tlb=%d ",temp->value);
            temp=temp->next;
        }
        temp=mem_head->next;
        while(temp!=mem_tail)
        {
            printf("mem=%d ",temp->value);
            temp=temp->next;
        }*/
    }
    fprintf(output, "Page fault rate %3lf\n", (double) fault_num / 1000);
    fprintf(output, "TLB hit rate %3lf", (double) tlb_hit / 1000);
    return 0;
}

四.结果展示：

计算机科学
操作系统

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！