首页 > 代码库 > 《30天自制操作系统》笔记(07)——内存管理

《30天自制操作系统》笔记(07)——内存管理

《30天自制操作系统》笔记(07)——内存管理

进度回顾

上一篇中处理掉了绝大部分与CPU配置相关的东西。本篇介绍内存管理的思路算法

现在想想,从软件工程师的角度看,CPU也只是一个软件而已:它的功能就是加载指令、执行指令和响应中断,而响应中断也是在加载指令、执行指令。就像火车沿着一条环形铁轨前进;当中断发生时,就好像铁轨岔口处变轨了,火车就顺着另一条轨迹走了;走完之后又绕回来重新开始。决定CPU是否变轨的,就是CPU里的特定寄存器。

软件工程师的角度看CPU

这是题外话,就此为止。

什么是内存管理

假设内存大小是128MB,应用程序A暂时需要100KB,画面控制需要1.2MB……。

像这样,操作系统有时要分配一定大小的内存,用完后又要收回。因此,必须管理好哪些内存空闲可用,哪些正在被占用。这就是内存管理。

内存管理的两个任务,一是内存分配,一是内存释放。

如何获取内存容量

检查内存容量的方法

要管理内存,首先得知道操作系统所在的这个计算机内存有多大。检查内存容量的方法很简单,就是从要检查的起始位置到最后位置依次写入一个数值(例如0xaa55aa55),然后按位反转,检查是否正确地完成了反转(变成0x55aa55aa);然后再次反转,检查是否正确地完成了反转。如果反转结果都是正确的,说明这个地址的内存是存在的;否则就说明内存的最大地址就到此为止了。其代码如下。

 1 unsigned int memtest_sub(unsigned int start, unsigned int end)
 2 {
 3     unsigned int i, *p, old, pat0 = 0xaa55aa55, pat1 = 0x55aa55aa;
 4     for (i = start; i <= end; i += 0x1000) {
 5         p = (unsigned int *) (i + 0xffc);
 6         old = *p;            /* 先记住修改前的值 */
 7         *p = pat0;            /* 试写 */
 8         *p ^= 0xffffffff;    /* 反转 */
 9         if (*p != pat1) {    /* 检查反转结果 */
10 not_memory:
11             *p = old;
12             break;
13         }
14         *p ^= 0xffffffff;    /* 再次反转 */
15         if (*p != pat0) {    /* 检查是否恢复 */
16             goto not_memory;
17         }
18         *p = old;            /* 恢复为修改前的值 */
19     }
20     return i;
21 }

但直接用C语言来写这个函数的话,C编译器会把它优化成这个样子。

1 unsigned int memtest_sub(unsigned int start, unsigned int end)
2 {
3     unsigned int i, *p, old, pat0 = 0xaa55aa55, pat1 = 0x55aa55aa;
4     for (i = start; i <= end; i += 0x1000) {
5         //全部被优化掉 了
6     }
7     return i;
8 }

C编译器不会理睬"内存到头了"这种事情,它只在应用程序的层面看问题。所以它认为for循环里的if判定都是必然为真(或为假)的,认为没有被其它代码使用的变量都是没用的。所以它就干脆把这些"没用的"代码删掉了。

为了解决这个问题,还是用汇编语言来写这个memtest_sub函数好了。代码如下。

 1 _memtest_sub:    ; unsigned int memtest_sub(unsigned int start, unsigned int end)
 2         PUSH    EDI                        ; (由于还要使用EBX, ESI, EDI)
 3         PUSH    ESI
 4         PUSH    EBX
 5         MOV        ESI,0xaa55aa55            ; pat0 = 0xaa55aa55;
 6         MOV        EDI,0x55aa55aa            ; pat1 = 0x55aa55aa;
 7         MOV        EAX,[ESP+12+4]            ; i = start;
 8 mts_loop:
 9         MOV        EBX,EAX
10         ADD        EBX,0xffc                ; p = i + 0xffc;
11         MOV        EDX,[EBX]                ; old = *p;
12         MOV        [EBX],ESI                ; *p = pat0;
13         XOR        DWORD [EBX],0xffffffff    ; *p ^= 0xffffffff;
14         CMP        EDI,[EBX]                ; if (*p != pat1) goto fin;
15         JNE        mts_fin
16         XOR        DWORD [EBX],0xffffffff    ; *p ^= 0xffffffff;
17         CMP        ESI,[EBX]                ; if (*p != pat0) goto fin;
18         JNE        mts_fin
19         MOV        [EBX],EDX                ; *p = old;
20         ADD        EAX,0x1000                ; i += 0x1000;
21         CMP        EAX,[ESP+12+8]            ; if (i <= end) goto mts_loop;
22         JBE        mts_loop
23         POP        EBX
24         POP        ESI
25         POP        EDI
26         RET
27 mts_fin:
28         MOV        [EBX],EDX                ; *p = old;
29         POP        EBX
30         POP        ESI
31         POP        EDI
32         RET
汇编版本的memtest_sub

知道了内存容量,就可以进行管理了。

关闭CPU高速缓存

486以上的CPU是有高速缓存(cache)的。CPU每次访问内存,都要将所访问的地址内容存入cache,也就是存放成这样"18号地址的值是54"。如果下次要用18号地址的内容,CPU就不需要再读内存了(速度慢),而是直接从cache中取得18号地址的内容(速度快)。

如果开启着CPU高速缓存(cache),上述的检测代码就不会正常工作。因为写入一个内存地址,然后立即读出,这样的操作符合cache到的情况,CPU不会从内存读,而是直接读cache到的东西。结果,所有的内存都"正常",检测代码就起不到作用了。

 1 #define EFLAGS_AC_BIT        0x00040000
 2 #define CR0_CACHE_DISABLE    0x60000000
 3 
 4 unsigned int memtest(unsigned int start, unsigned int end)
 5 {
 6     char flg486 = 0;
 7     unsigned int eflg, cr0, i;
 8 
 9     /* 确认CPU是386还是486以上的 */
10     eflg = io_load_eflags();
11     eflg |= EFLAGS_AC_BIT; /* AC-bit = 1 */
12     io_store_eflags(eflg);
13     eflg = io_load_eflags();
14     if ((eflg & EFLAGS_AC_BIT) != 0) { /* 如果是386,即使设定AC=1,AC的值还会自动回到0 */
15         flg486 = 1;
16     }
17     eflg &= ~EFLAGS_AC_BIT; /* AC-bit = 0 */
18     io_store_eflags(eflg);
19 
20     if (flg486 != 0) {
21         cr0 = load_cr0();
22         cr0 |= CR0_CACHE_DISABLE; /* 禁止缓存 */
23         store_cr0(cr0);
24     }
25 
26     i = memtest_sub(start, end);
27 
28     if (flg486 != 0) {
29         cr0 = load_cr0();
30         cr0 &= ~CR0_CACHE_DISABLE; /* 允许缓存 */
31         store_cr0(cr0);
32     }
33 
34     return i;
35 }

 

内存管理算法

假设内存有128MB(0x08000000字节),以4KB(0x1000字节)为单位进行管理。

最简单的方法

128MB/4KB=32768。所以我们创建32768字节的区域,写入0表示对应的内存是空闲的,写入1表示对应的内存是正在使用的。这个方法的名字我没有查到。

1 char a[32768];
2 for (i = 0; i < 1024; i++) {
3     a[i] = 1; //一直到4MB为止,标记为正在使用(BIOS、OS等)
4 }
5 for (i = 1024; i< 32768; i++) {
6     a[i] = 0; //剩下的全部标记为空闲
7 }

比如需要100KB的内存,那么只要从a中找出连续25个标记为0的地方就可以了。

 1 //从a[j]到a[j + 24]为止,标记连续为0";
 2 j = 0;
 3 再来一次:
 4 for (i = 0; i < 25; i++) {
 5     if (a[j + i] != 0) {
 6         j++;
 7         if (j < 32768 - 25) goto 再来一次;
 8         "没有可用内存了";
 9     }
10 }
11 //从j * 0x1000开始的100KB空间得到分配
12 for (i = 0; i < 25; i++) {
13     a[j + i] = 1;
14 }

需要收回这100KB的时候,用地址值/0x1000,计算出j就可以了。

1 j = 0x00123000 / 0x1000;
2 for (i = 0; i < 25; i++) {
3     a[j + i] = 0;
4 }

当然,我们可以用1bit来代替1个char,这样所需的管理空间就可以省下7/8,使用方法则是一样的。

列表管理

把类似于"从xxx号地址开始的yyy字节的空间是空闲的"这种信息都存储到列表里。

 1 struct FREEINFO {    /* 可用状况 */
 2     unsigned int addr, size;
 3 };
 4 
 5 struct MEMMAN {        /* 内存管理 */
 6     int frees, maxfrees, lostsize, losts;
 7     struct FREEINFO free[MEMMAN_FREES];
 8 };
 9 struct MEMMAN memman;
10 memman.frees = 1;//可用状况list中只有1件
11 memman.free[0].addr = 0x00400000;//从0x00400000号地址开始
12 memman.free[0].size = 0x07c00000;//有124MB可用

比如,如果需要100KB的内存,只要查看memman中free的状况,从中找到100MB以上的可用空间就行了。

1 for (i = 0; i < memman.frees; i++) {
2     if (memman.free[i].size >= 100 * 1024) {
3         //找到可用空间
4         memman.free[i].addr += 100 * 1024;
5         memman.free[i].size -= 100 * 1024;
6     }
7 }

释放内存时,增加1条可用信息,frees加1。而且还要看看新释放出的内存与相邻的内存能不能连到一起,如果可以,就要归为1条。

与上文的最简单的方法相比,这种列表管理的方法,占用内存少,且内存的申请和释放更迅速。

缺点是释放内存的代码比较复杂。另外,如果内存变成零零碎碎的,那么需要的MEMMAN里的数组就会超过1000,这是个问题。如果真发生这种情况,只能将一部分零碎的空闲内存都视作被占用的,然后合并。

  1 void memman_init(struct MEMMAN *man)
  2 {
  3     man->frees = 0;            /* 可用信息数目 */
  4     man->maxfrees = 0;        /* 用于观察可用状况:frees的最大值 */
  5     man->lostsize = 0;        /* 释放失败的内存的大小总和 */
  6     man->losts = 0;            /* 释放失败次数 */
  7     return;
  8 }
  9 
 10 unsigned int memman_total(struct MEMMAN *man)
 11 /* 报告空余内存大小的合计 */
 12 {
 13     unsigned int i, t = 0;
 14     for (i = 0; i < man->frees; i++) {
 15         t += man->free[i].size;
 16     }
 17     return t;
 18 }
 19 
 20 unsigned int memman_alloc(struct MEMMAN *man, unsigned int size)
 21 /* 分配 */
 22 {
 23     unsigned int i, a;
 24     for (i = 0; i < man->frees; i++) {
 25         if (man->free[i].size >= size) {
 26             /* 找到了足够大的内存 */
 27             a = man->free[i].addr;
 28             man->free[i].addr += size;
 29             man->free[i].size -= size;
 30             if (man->free[i].size == 0) {
 31                 /* 如果是free[i]变成了0,就减掉一条可用信息 */
 32                 man->frees--;
 33                 for (; i < man->frees; i++) {
 34                     man->free[i] = man->free[i + 1]; /* 代入结构体 */
 35                 }
 36             }
 37             return a;
 38         }
 39     }
 40     return 0; /* 没有可用空间 */
 41 }
 42 
 43 int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size)
 44 /* 释放 */
 45 {
 46     int i, j;
 47     /* 为便于归纳内存,将free[]按照addr的顺序排列 */
 48     /* 所以,先决定应该放在哪里 */
 49     for (i = 0; i < man->frees; i++) {
 50         if (man->free[i].addr > addr) {
 51             break;
 52         }
 53     }
 54     /* free[i - 1].addr < addr < free[i].addr */
 55     if (i > 0) {
 56         /* 前面有可用内存 */
 57         if (man->free[i - 1].addr + man->free[i - 1].size == addr) {
 58             /* 可用与前面的可用内存归纳到一起 */
 59             man->free[i - 1].size += size;
 60             if (i < man->frees) {
 61                 /* 后面也有 */
 62                 if (addr + size == man->free[i].addr) {
 63                     /* 也可以与后面的可用内存归纳到一起 */
 64                     man->free[i - 1].size += man->free[i].size;
 65                     /* man->free[i]删除 */
 66                     /* free[i]变成0后归纳到前面去 */
 67                     man->frees--;
 68                     for (; i < man->frees; i++) {
 69                         man->free[i] = man->free[i + 1]; /* 结构体赋值 */
 70                     }
 71                 }
 72             }
 73             return 0; /* 成功完成 */
 74         }
 75     }
 76     /* 不能与前面的可用空间归纳到一起 */
 77     if (i < man->frees) {
 78         /* 后面还有 */
 79         if (addr + size == man->free[i].addr) {
 80             /* 可用与后面的内容归纳到一起 */
 81             man->free[i].addr = addr;
 82             man->free[i].size += size;
 83             return 0; /* 成功完成 */
 84         }
 85     }
 86     /* 既不能与前面归纳到一起,也不能与后面归纳到一起 */
 87     if (man->frees < MEMMAN_FREES) {
 88         /* free[i]之后的,向后移动 */
 89         for (j = man->frees; j > i; j--) {
 90             man->free[j] = man->free[j - 1];
 91         }
 92         man->frees++;
 93         if (man->maxfrees < man->frees) {
 94             man->maxfrees = man->frees; /* 更新最大值 */
 95         }
 96         man->free[i].addr = addr;
 97         man->free[i].size = size;
 98         return 0; /* 成功完成 */
 99     }
100     /* 不能往后移动 */
101     man->losts++;
102     man->lostsize += size;
103     return -1; /* 失败 */
104 }

 

  

总结

内存管理要结合GDT的设定进行。按段(Segment)设计的GDT,内存就得按段申请和回收。按页设计的GDT,额我不知道,以后再说。

内存管理需要的预备知识还包括"获取内存容量"、"禁止/启用高速缓存"、"数据结构-链表"。

内存管理的算法还有很多,本篇只给出了两种最基本最简单的,够做个简易的OS就行了,现在不是深究算法的时候。