《30天自制操作系统》第9天

第九天 内存管理

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源码或其他操作系统的源码也有帮助。

(0)

相关推荐