第九天 内存管理

1.整理源文件

这一节只是进行了代码整理，把鼠标键盘相关的内容转移到了特定的文件里。

2.内存容量检查（1）

要做内存管理，首先得知道内存的容量，怎么知道内存的容量呢？BIOS可以告诉我们答案。但使用BIOS稍微有点麻烦，于是，作者决定自己写程序检查内存容量。

内存检查程序主要有以下几步：

1. 检查CPU是386芯片还是486芯片。若为486芯片，则禁止cache。（386没有cache）

2. 不断向内存写入然后读取数据。如果写入和读取的内容一样，则内存连接正常。

怎么判断CPU是386还是486呢？这里需要用到状态寄存器。状态寄存器的第18位AC位（Alignment Check，对齐检查），在386中即使将它设置为1，它也会变成0，而486中不会出现这种情况。于是，根据这个特点，我们就可以判断出CPU是386还是486的，然后再确定需不需要禁止缓存。相关的代码如下所示。

 unsigned int memtest(unsigned int start, unsigned int end) {     char flg486 = 0;     unsigned int eflg, cr0, i; ​     /* 确认CPU是386还是486以上 */     eflg = io_load_eflags();     eflg |= EFLAGS_AC_BIT;              /* 对AC位置1 */     io_store_eflags(eflg);     eflg = io_load_eflags();     if ((eflg & EFLAGS_AC_BIT) != 0)    /* 如果是386，即使设定AC=1，AC的值还会自动回到0 */     {         flg486 = 1;     }     eflg &= ~EFLAGS_AC_BIT;             /* 将AC位置0 */     io_store_eflags(eflg); ​     if (flg486 != 0)     {         cr0 = load_cr0();         cr0 |= CR0_CACHE_DISABLE;       /* 禁止缓存 */         store_cr0(cr0);     } ​     i = memtest_sub(start, end); ​     if (flg486 != 0)     {         cr0 = load_cr0();         cr0 &= ~CR0_CACHE_DISABLE;      /* 允许缓存 */         store_cr0(cr0);     } ​     return i; }

其中，加载和保存控制寄存器0（CR0）的函数定义如下。

 _load_cr0:          ; int load_cr0(void);     MOV EAX, CR0     RET ​ _store_cr0:         ; void store_cr0(int cr0);     MOV EAX, [ESP + 4]     MOV CR0, EAX     RET

接下来是第二步，向内存读写数据，检查内存是否正确。

 unsigned int memtest_sub(unsigned int start, unsigned int end) {     unsigned int i, *p, old, pat0 = 0xaa55aa55, pat1 = 0x55aa55aa;     for (i = start; i <= end; i += 4)     {         p = (unsigned int *) i;         old = *p;               /* 先记住修改前的值 */         *p = pat0;              /* 试写 */         *p ^= 0xffffffff;       /* 反转 */         if (*p != pat1)         /* 检查反转结果 */         { not_memory:             *p = old;             break;         }         *p ^= 0xffffffff;       /* 再次反转 */         if (*p != pat0)         /* 检查值是否恢复 */         {             goto not_memory;         }         *p = old;               /* 恢复为修改前的值 */     }     return i; }

可以看到，这段代码很简单，不断对内存地址的值进行翻转，若翻转后的值与预期的不同，则说明内存有问题。这里还要思考一个问题，上面函数的参数start和end应该赋予什么值？为什么？

上面内存检查的代码看起来不错，但是运行速度太慢了，毕竟它对每个地址都进行检查。作者让检查程序偷偷懒，让它能够执行得更快，代码如下所示。

 unsigned int memtest_sub(unsigned int start, unsigned int end) {     unsigned int i, *p, old, pat0 = 0xaa55aa55, pat1 = 0x55aa55aa;     for (i = start; i <= end; i += 0x1000)     {         p = (unsigned int *) (i + 0xffc);         old = *p;               /* 先记住修改前的值 */         *p = pat0;              /* 试写 */         *p ^= 0xffffffff;       /* 反转 */         if (*p != pat1)         /* 检查反转结果 */         { not_memory:             *p = old;             break;         }         *p ^= 0xffffffff;       /* 再次反转 */         if (*p != pat0)         /* 检查值是否恢复 */         {             goto not_memory;         }         *p = old;               /* 恢复为修改前的值 */     }     return i; }

修改后，检查程序每4K地址只检查4字节地址，速度自然是比之前快多了。另外，这段代码只是为了检查内存的容量，不要记错了它的功能。

接下来改一改HariMain就能运行了，将内存检查放在死循环之前。

     i = memtest(0x00400000, 0xbfffffff) / (1024 * 1024);    /* 0x400000以前的内存已被使用，无需检查 */     sprintf(s, "memory %dMB", i);     putfonts8_asc(binfo->vram, binfo->scrnx, 0, 32, COL8_FFFFFF, s); ​     while (1)

运行的显示如下。

这里显示内存有3G内存，而系统内存实际只有32M，这明显不对，是什么地方出错了？

3.内存内容检查（2）

上一节为什么会出错呢？这全都是编译器的锅。

在从C语言转换成汇编的过程中，编译器发现内存检查过程中没有什么实际的改变，就把这段给优化掉了。比如，首先给一个地址存入0xaa55aa55，翻转后变成0x55aa55aa，然后再次反转变成0xaa55aa55，从结果而言并没有发生什么变化。

为了防止代码被优化，采用汇编代码编写内存检查的函数。

 _memtest_sub:   ; unsigned int memtest_sub(unsigned int start, unsigned int end)     PUSH    EDI                 ; （保存EBX、ESI、EDI中的数据）     PUSH    ESI     PUSH    EBX     MOV ESI, 0xaa55aa55         ; pat0 = 0xaa55aa55;     MOV EDI, 0x55aa55aa         ; pat1 = 0x55aa55aa;     MOV EAX, [ESP + 12 + 4]     ; i = start; (由于栈中增加了3个元素，地址要多加12) ​ mts_loop:     MOV EBX, EAX     ADD EBX, 0xffc              ; p = (i + 0xffc);     MOV EDX, [EBX]              ; old = *p;     MOV [EBX], ESI              ; *p = pat0;     XOR DWORD [EBX], 0xffffffff ; *p ^= 0xffffffff;     CMP EDI, [EBX]              ; if (*p != pat1) goto fin;     JNE mts_fin     XOR DWORD [EBX], 0xffffffff ; *p ^= 0xffffffff;     CMP ESI, [EBX]              ; if (*p != pat0) goto fin;     JNE mts_fin     MOV [EBX], EDX              ; *p = old;     ADD EAX, 0x1000             ; i += 0x1000;     CMP EAX, [ESP + 12 + 8]     ; if (i <= end) goto mts_loop;     JBE mts_loop     POP EBX     POP ESI     POP EDI     RET ​ mts_fin:     MOV [EBX], EDX              ; *p = old;     POP EBX     POP ESI     POP EDI     RET

这段汇编代码的逻辑与之前C语言代码是一样的，相信大家很容易理解。

运行结果如下。

4.挑战内存管理

相信学过操作系统的人都知道内存管理的重要性，毕竟没了内存管理，操作系统怎么知道哪块内存能用哪块内存不能用？

这个操作系统比较小，没有虚拟存储器，也没有什么页面置换算法，更没有什么分页分段，直接采用可变长度分配这种简单粗暴的方法。作者认为分页所需的管理表会占用不少空间就放弃了。

我们对每段空间的管理只记录两个信息：起始地址和长度。而为了方便管理，把这两个数据放在一个结构体中。

 struct FREEINFO     /* 可用信息 */ {     unsigned int addr, size; }; ​ struct MEMMAN       /* 内存管理 */ {     int frees;     struct FREEINFO free[1000]; };

在MEMMAN结构体中，frees是已使用的FREEINFO结构体的数量，并且还有一个大小为1000的FREEINFO结构体数组。

对于MEMMAN结构体而言，有增删改移位等操作。在了解这些操作的实现之前，我们要知道内存的分配算法是哪种，这个操作系统采用的是首次适应算法，首次适应算法的空闲分区要按地址由低到高进行排序，从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配出去。

1.改变。只是改动addr和size的值。

2.增加。内存中，从0x400000开始的长度为0x7c00000的内存块未被使用，首先把这块内存添加到MEMMAN结构体中。

 struct MEMMAN memman; memman.frees = 1; memman.free[0].addr = 0x00400000; memman.free[0].size = 0x07c00000;

3.增加并移位。这里的移位操作使用的是插入排序算法。如下图所示。

4.删除。申请的大小与空闲块大小一致。

5.合并。释放的内存块与前后地址的内存块合并。

对于内存空闲块的操作就这5种操作，我们只需根据这五种操作编写代码即可。

为了使得功能更完善，我们要为MEMMAN结构体添加一些东西。

 #define MEMMAN_FREES    4090        /* 大约是32KB */ ​ struct FREEINFO     /* 可用信息 */ {     unsigned int addr, size; }; ​ struct MEMMAN       /* 内存管理 */ {     int frees, maxfrees, lostsize, losts;     struct FREEINFO free[MEMMAN_FREES]; };

使用可变长度的内存分配不可避免地会产生一些内存碎片，losts用于记录碎片地数量，lostsize用于记录碎片的总大小。

下面介绍内存相关的函数。

 void memman_init(struct MEMMAN *man) {     man->frees = 0;         /* 可用信息数目 */     man->maxfrees = 0;      /* 用于观察可用状况：frees的最大值 */     man->lostsize = 0;      /* 释放失败的内存的大小总和 */     man->losts = 0;         /* 释放失败次数 */ } ​ unsigned int memman_total(struct MEMMAN *man)   /* 报告剩余内存大小的合计 */ {     unsigned int i, t = 0;     for (i = 0; i < man->frees; i++)     {         t += man->free[i].size;     }     return t; }

memman_init初始化MEMMAN结构体成员，memman_total计算出剩余内存总大小，这些都比较简单。

 unsigned int memman_alloc(struct MEMMAN *man, unsigned int size)    /* 分配 */ {     unsigned int i, a;     for (i = 0; i < man->frees; i++)     {         if (man->free[i].size >= size)  /* 找到了足够大的内存 */         {             a = man->free[i].addr;             man->free[i].addr += size;             man->free[i].size -= size;             if (man->free[i].size == 0) /* 如果free[i]变成了0，就减掉一条可用信息 */             {                 for (; i < man->frees; i++)                 {                     man->free[i] = man->free[i + 1];    /* 把之后的信息往前挪 */                 }                 man->frees--;             }             return a;         }     }     return 0;   /* 没有可用空间 */ }

从名字就可以看出memman_alloc是内存分配函数，采用的是首次适应算法，也算简单。

 int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size)   /* 释放 */ {     int i, j;     /* 为便于归纳内存，将free[]按照addr的顺序排列 */     /* 所以，仙居定应该放哪儿 */     for (i = 0; i < man->frees; i++)     {         if (man->free[i].addr > addr)         {             break;         }     }     /* free[i - 1].addr < addr < free[i].addr */     if (i > 0)  /* 若前面有可用内存 */     {         if (man->free[i - 1].addr + man->free[i - 1].size == addr)  /* 若与前面的可用内存相邻，则归纳在一起 */         {             man->free[i - 1].size += size;             if (i < man->frees) /* 若后面也有可用内存内存 */             {                 if (addr + size == man->free[i].addr)   /* 若与后面的可用内存相邻，则归纳在一起 */                 {                     man->free[i - 1].size += man->free[i].size;                     man->frees--;                     for (; i< man->frees; i++)  /* 删除free[i] */                     {                         man->free[i] = man->free[i + 1];                     }                 }             }             return 0;   /* 成功完成 */         }     }     /* 若不能与前面的内存归纳在一起 */     if (i < man->frees) /* 若后面也有可用内存内存 */     {         if (addr + size == man->free[i].addr)   /* 若与后面的可用内存相邻，则归纳在一起 */         {             man->free[i].addr = addr;             man->free[i].size += size;             return 0;   /* 成功完成 */         }     }     /* 既不能与前面内存归纳在一起，也不能与后面内存归纳在一起 */     if (man->frees < MEMMAN_FREES)     {         for (j = man->frees; j > i; j--)    /* 把信息往后移，腾出free[i] */         {             man->free[j] = man->free[j - 1];         }         man->frees++;         if (man->maxfrees < man->frees)         {             man->maxfrees = man->frees;         }         man->free[i].addr = addr;         man->free[i].size = size;         return 0;   /* 成功完成 */     }     /* 信息个数已达到最大 */     man->losts++;     man->lostsize += size;  /* 失败 */     return -1; }

内存释放的算法逻辑可以看看上面的图，理解起来应该不会太困难。

最后还需修改一下HariMain，这里不做展示了，直接上结果图。

书上的内容到此结束。在此，给大家一点小建议，可以尝试自己实现一个内存管理算法，当使用的内存块很少时，书中的内存管理算法不算慢，但是一旦多起来（达到一两千的量级），所需时间飙升（毕竟时间复杂度为O(n2)）。试试采用双向链表或其他的数据结构，把时间复杂度减至O(n)的水平。

其实已经不准备写关于《30天自制操作系统》的博客了，因为这本书的代码不是很系统，但是有人问我还有后续吗，而且我觉得内存管理比较有用，就写了这一篇博客，后面还有任务切换、异常处理等内容也有趣，但我应该不会再写了。现在正在看《一个64位操作系统的设计与实现》，我也很推荐看这本书，代码借鉴于Linux，对以后看Linux源码或其他操作系统的源码也有帮助。