《30天自制操作系统》第9天
第九天 内存管理
1.整理源文件
这一节只是进行了代码整理，把鼠标键盘相关的内容转移到了特定的文件里。
2.内存容量检查（1）
要做内存管理，首先得知道内存的容量，怎么知道内存的容量呢？BIOS可以告诉我们答案。但使用BIOS稍微有点麻烦，于是，作者决定自己写程序检查内存容量。
内存检查程序主要有以下几步：
检查CPU是386芯片还是486芯片。若为486芯片，则禁止cache。（386没有cache）
不断向内存写入然后读取数据。如果写入和读取的内容一样，则内存连接正常。
怎么判断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源码或其他操作系统的源码也有帮助。