实验课程: 操作系统
实验名称: Lab7 内存管理
1. 实验要求
Assignment 1
复现参考代码，实现二级分页机制，并能够在虚拟机地址空间中进行内存管理，包括内存的申请和释放等，截图并给出过程解释。
Assignment 2
参照理论课上的学习的物理内存分配算法如first-fit, best-fit等实现动态分区算法等，或者自行提出自己的算法。
Assignment 3
复现“虚拟页内存管理”一节的代码，完成如下要求。
- 结合代码分析虚拟页内存分配的三步过程和虚拟页内存释放。
- 构造测试例子来分析虚拟页内存管理的实现是否存在bug。如果存在，则尝试修复并再次测试。否则，结合测例简要分析虚拟页内存管理的实现的正确性。
- （不做要求，对评分没有影响）如果你有想法，可以在自己的理解的基础上，参考ucore，《操作系统真象还原》，《一个操作系统的实现》等资料来实现自己的虚拟页内存管理。在完成之后，你需要指明相比较于本教程，你的实现的虚拟页内存管理的特点所在。
Assignment 4
参照理论课上虚拟内存管理的页面置换算法如FIFO、LRU等，实现页面置换，也可以提出自己的算法。
2. 实验过程
Assignment1
BitMap
setup.cpp中
char*pages_0= (char*)memoryManager.allocatePhysicalPages(AddressPoolType::KERNEL, 128);
调用了 MemoryManager的成员函数allocatePhisicalPages
接着我们进入 allocatePhysicalPages,这里的resources是一个Bitmap变量，allocate在给的代码中默认采用的是first_fit的算法，Bitmap::allocate的功能是按照分配方式找到位图对应的位置，都置为1。位图位与内核空间中。
第一次调用 Bitmap::allocate的返回值为0，分配完128pages，后第二次调用 Bitmap::allocate返回值为128（返回值为分配时bitmap数组的起始位置）
则 AddressPool::allocate的返回值为PAGE_SIZE*start+startAddress 即从哪个地址开始分配 ,这里的startAddress可认为是起始地址的基址，是2097152，即0x200000。
release的过程类似:(address - startAddress/PAGE_SIZE)算出bitmap对应的位置index,然后从该位置开始把后面count个元素置零。
Assignment2
- first_fit：从低地址开始搜索,找到第一个可以容纳请求块的空闲分区
- best_fit：从所有可用分区中找到最小的能够满足请求的分区
- worst_fit：从所有可用分区中找到最大的能够满足请求的分区
具体实现见关键代码处
Assignment3
虚拟页内存分配的三步：
- 从虚拟地址池中分配连续的多个虚拟页 。
我们建立了用户虚拟地址池,首先定义虚拟地址起始地址的宏，使得分配的页空间虚拟地址仅在3-4GB之
间
1
| #define KERNEL_VIRTUAL_START 0xc0100000
|
从地址池中分配count个连续页的过程在assignment1中已经提到，不再赘述。
这是 kernel/memory.cpp中的 MemoryManager::allocatePages函数：
1
| int MemoryManager::allocatePages(enum AddressPoolType type, const int count);
|
1
2
3
4
5
6
|
int virtualAddress = allocateVirtualPages(type, count);
if (!virtualAddress)
{
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
| bool flag;
int physicalPageAddress;
int vaddress = virtualAddress;
for (int i = 0; i < count; ++i, vaddress += PAGE_SIZE)
{
flag = false;
physicalPageAddress = allocatePhysicalPages(type, 1);
if (physicalPageAddress)
{
flag = connectPhysicalVirtualPage(vaddress, physicalPageAddress);
}
else
{
flag = false;
}
if (!flag)
{
releasePages(type, virtualAddress, i);
releaseVirtualPages(type, virtualAddress + i * PAGE_SIZE, count - i);
return 0;
}
}
return virtualAddress;
|
- 在页目录表和页表中建立虚拟页和物理页之间的对应关系 。此时，由于分页机制的存在，物理页的地址可以不连续。CPU的MMU会在程序执行过程中将虚拟地址翻译成物理地址。
我们具体来看这个函数：connectPhysicalVirtualPage(vaddress, physicalPageAddress);
- 首先得到虚拟地址对应的页目录项pde和页表项pte
- 如果页目录项无页表则1.分配物理页给页表 2.使页目录项指向页表 3.进行空间的分配
- 有的话直接将页表项指向物理页
一些关键代码的解释:
*pde & 0x00000001表示获取存在位（P位），若为0则取分配物理页
将页表项指向物理页，*physicalPageAddress | 0x7中的按位或运算是为了设置页目录项的标志位
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
| bool MemoryManager::connectPhysicalVirtualPage(const int virtualAddress, const int physicalPageAddress)
{
int *pde = (int *)toPDE(virtualAddress);
int *pte = (int *)toPTE(virtualAddress);
if(!(*pde & 0x00000001))
{
int page = allocatePhysicalPages(AddressPoolType::KERNEL, 1);
if (!page)
return false;
*pde = page | 0x7;
char *pagePtr = (char *)(((int)pte) & 0xfffff000);
memset(pagePtr, 0, PAGE_SIZE);
}
*pte = physicalPageAddress | 0x7;
return true;
}
|
释放内存过程：分为两步,首先释放物理页再释放虚拟页。
要注意把页表项pte置空，防止再次被访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void MemoryManager::releasePages(enum AddressPoolType type, const int virtualAddress, const int count)
{
int vaddr = virtualAddress;
int *pte;
for (int i = 0; i < count; ++i, vaddr += PAGE_SIZE)
{
releasePhysicalPages(type, vaddr2paddr(vaddr), 1);
pte = (int *)toPTE(vaddr);
*pte = 0;
}
releaseVirtualPages(type, virtualAddress, count);
}
|
通过打印测试用例发现，确实达到了虚拟内存连续分配，物理内存分配不连续的效果
测试用例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
printf("%x %x %x\n", p1, p2, p3);
memoryManager.releasePages(AddressPoolType::KERNEL, (int)p2, 10);
p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
printf("%x\n", p2);
p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
printf("%x\n", p2);
|
虚拟内存分配结果:p2释放后重新分配100页的空间时，从0xc01d2000,而分配10页空间时从原来释放内存的0x164000开始
物理内存则在分配100页时从原来释放的地址的开始，如果孔空间不够继续找到下一个空的空间。
一些bug:
没有使用互斥机制导致不同线程可能都进入临界区，分配到相同的物理地址。我们延长了等待时间使得这个错误发生。具体错误见实验结果处。
解决方案：使用信号量解决.
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
| Semaphore semaphore;
void MemoryManager::initialize()
{
semaphore.initialize(1);
...
}
int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
semaphore.P();
int virtualAddress = allocateVirtualPages(type, count);
if (!virtualAddress)
{
return 0;
}
bool flag;
int physicalPageAddress;
int vaddress = virtualAddress;
for (int i = 0; i < count; ++i, vaddress += PAGE_SIZE)
{
flag = false;
physicalPageAddress = allocatePhysicalPages(type, 1);
if (physicalPageAddress)
{
flag = connectPhysicalVirtualPage(vaddress, physicalPageAddress);
}
else
{
flag = false;
}
semaphore.V();
if (!flag)
{
releasePages(type, virtualAddress, i);
releaseVirtualPages(type, virtualAddress + i * PAGE_SIZE, count - i);
return 0;
}
}
return virtualAddress;
}
|
还有可能在其他地方也会出现没有互斥访问导致的问题没有解决。
Assignment 4
本实验中我在win环境中模拟LRU
LRU页面置换
核心原理是基于“最近使用的数据将来被使用的概率更高”这一假设，即如果一个数据最近被访问过，那么它在不久的将来很可能再次被访问；相反，如果一个数据很长时间没有被访问，那么它在将来被访问的概率较低。我们使用一个times变量来记录多少次没有被访问过，取最大的淘汰。
实现代码见关键代码
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
| #include <stdio.h>
using namespace std;
struct memory{
int id;
int times;
};
class LRUCache {
private:
int num;
int capacity;
memory mem[3];
public:
LRUCache(int capacity){
this->capacity = capacity;
num = 0;
for(int i = 0;i<capacity;i++){
mem[i].id = -1;
mem[i].times = 0;
}
}
void tihuan(int k){
int max = -1;
int max_id = -1;
for(int i = 0;i<num;i++){
if(mem[i].times>max){
max = mem[i].times;
max_id = i;
}
}
printf("%d被替换为%d\n",mem[max_id].id,k);
mem[max_id].id= k;
mem[max_id].times = 0;
}
bool find(int n){
int flag = 0;
for(int i = 0;i<num;i++){
if(mem[i].id== n){
flag = 1;
mem[i].times = 0;
break;
}
}
return flag;
}
void put(int k){
for(int i = 0;i<num;i++){
mem[i].times++;
}
if(!find(k)){
if(num<capacity){
mem[num].id=k;
mem[num].times=0;
num++;
}else{
tihuan(k);
}
}else{
printf("id %d hit\n",k);
}
printf("page id now:\n");
for(int i = 0;i<num;i++){
printf("%d ",mem[i].id);
}
printf("\n");
}
};
int main() {
int seq[10]= {7,0,1,2,0,3,0,4,2,3};
LRUCache cache1(3);
for(int i=0; i<10;i++){
cache1.put(seq[i]);
}
return 0;
}
|
3. 关键代码
Assignment1中分配内存用的是和Assignment2一样的测试代码
Assignment2中first_fit:
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
| int BitMap::allocate(const int count)
{
if (count == 0)
return -1;
int index, empty, start;
index = 0;
while (index < length)
{
while (index < length && get(index))
++index;
if (index == length)
return -1;
empty = 0;
start = index;
while ((index < length) && (!get(index)) && (empty < count))
{
++empty;
++index;
}
if (empty == count)
{
for (int i = 0; i < count; ++i)
{
set(start + i, true);
}
return start;
}
}
return -1;
}
|
best_fit:使用min_space和min_start记录当前最小且大于count的最小空间，和其对应的起始地址。
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
| int BitMap::best_fit(const int count){
if (count == 0)
return -1;
int index, empty, start;
int min_space = 0xffffff;
int min_start = 0;
index = 0;
while (index < length)
{
while (index < length && get(index)){
++index;
}
if (index == length)
break;
empty = 0;
start = index;
while ((index < length) && (!get(index)))
{
++empty;
++index;
}
if(empty>=count && empty<min_space){
min_space = empty;
min_start = start;
}
}
if(min_space == 0xffffff){
return -1;
}
start = min_start;
for (int i = 0; i < count; ++i)
{
set(start + i, true);
}
return start;
}
|
worst_fit:则与best_fit相反
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
| int BitMap::worst_fit(const int count){
if (count == 0)
return -1;
int index, empty, start;
int max_space = -1;
int max_start = 0;
index = 0;
while (index < length)
{
while (index < length && get(index)){
++index;
}
if (index == length)
break;
empty = 0;
start = index;
while ((index < length) && (!get(index)))
{
++empty;
++index;
}
if(empty>=count && empty>max_space){
max_space = empty;
max_start = start;
}
}
if(max_space == -1){
return -1;
}
start = max_start;
for (int i = 0; i < count; ++i)
{
set(start + i, true);
}
return start;
}
|
Assignment4
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
| #include <stdio.h>
using namespace std;
struct memory{
int id;
int times;
};
class LRUCache {
private:
int num;
int capacity;
memory mem[3];
public:
LRUCache(int capacity){
this->capacity = capacity;
num = 0;
for(int i = 0;i<capacity;i++){
mem[i].id = -1;
mem[i].times = 0;
}
}
void tihuan(int k){
int max = -1;
int max_id = -1;
for(int i = 0;i<num;i++){
if(mem[i].times>max){
max = mem[i].times;
max_id = i;
}
}
printf("%d被替换为%d\n",mem[max_id].id,k);
mem[max_id].id= k;
mem[max_id].times = 0;
}
bool find(int n){
int flag = 0;
for(int i = 0;i<num;i++){
if(mem[i].id== n){
flag = 1;
mem[i].times = 0;
break;
}
}
return flag;
}
void put(int k){
for(int i = 0;i<num;i++){
mem[i].times++;
}
if(!find(k)){
if(num<capacity){
mem[num].id=k;
mem[num].times=0;
num++;
}else{
tihuan(k);
}
}else{
printf("id %d hit\n",k);
}
printf("page id now:\n");
for(int i = 0;i<num;i++){
printf("%d ",mem[i].id);
}
printf("\n");
}
};
int main() {
int seq[10]= {7,0,1,2,0,3,0,4,2,3};
LRUCache cache1(3);
for(int i=0; i<10;i++){
cache1.put(seq[i]);
}
return 0;
}
|
4. 实验结果
Assignment 2
分配四次，释放两次内存后的内存空间如左图所示，右侧是采用不同方法继续分配两次空间后的结果
best_fit:
可以看到，
worst_fit
Assignment 3
没有实现互斥机制时的错误：分配到了同样的虚拟地址
测试用例：
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
| memoryManager memoryManager;
void second_thread(void *arg)
{
char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 1);
printf("thread2 %x\n",p2);
}
void third_thread(void *arg)
{
char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 1);
printf("thread3 %x\n",p3);
}
void first_thread(void *arg)
{
int pid1 = programManager.executeThread(second_thread, nullptr, "second thread", 1);
int pid2 = programManager.executeThread(third_thread, nullptr, "third thread", 1);
char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 1);
printf("thread1 %x\n",p1);
|
改正后的结果：
Assignment 4
LRU算法，引用串为7,0,1,2,0,3,0,4,2,3，可用帧为3时的结果
5. 总结
通过这次实验，我更加深刻认识到内存管理的重要意义，了解了二级页表的实现机制。了解了位图，内存池等相关概念和实现。了解了虚拟内存管理机制，页内存的分配和释放过程，最后实现用FIFO算法实现了页面置换。用LRU算法在win环境下模拟了页面置换的过程。