4　挑战内存管理（harib06d）

刚才笔者一个劲儿地说内存管理长，内存管理短的，那到底什么是内存管理呢？为什么要进行内存管理呢?

比如说，假设内存大小是128MB，应用程序A暂时需要100KB，画面控制需要1.2MB……，像这样，操作系统在工作中，有时需要分配一定大小的内存，用完以后又不再需要，这种事会频繁发生。为了应付这些需求，必须恰当管理好哪些内存可以使用（哪些内存空闲），哪些内存不可以使用（正在使用），这就是内存管理。如果不进行管理，系统会变得一塌糊涂，要么不知道哪里可用，要么多个应用程序使用同一地址的内存。

内存管理的基础，一是内存分配，一是内存释放。“现在要启动应用程序B了，需要84KB内存，哪儿空着呢？”如果问内存管理程序这么一个问题，内存管理程序就会给出一个能够自由使用的84KB的内存地址，这就是内存分配。另一方面，“内存使用完了，现在把内存归还给内存管理程序”，这一过程就是内存的释放过程。

■■■■■

先假设有128MB的内存吧。也就是说，有0x08000000个字节。另外我们假设以0x1000个字节（4KB）为单位进行管理。大家会如何管理呢？答案有很多，我们从简单的方法开始介绍。

0x08000000/0x1000 = 0x08000 = 32768，所以首先我们来创建32768字节的区域，可以往其中写入0或者1来标记哪里是空着的，哪里是正在使用的。

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

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

  1.     j = 0;
  2. 再来一次:
  3.     for (i = 0; i < 25; i++) {
  4.         if (a[j + i] != 0) {
  5.             j++;
  6.             if (j < 32768 - 25) goto 再来一次;
  7.             "没有可用内存了";
  8.         }
  9.     }
  10.     "从a[j]到a[j + 24]为止，标记连续为0";

如果找到了标记连续为0的地方，暂时将这些地方标记为“正在使用”，然后从j的值计算出对应的地址。这次是以0x1000字节为管理单位的，所以将j放大0x1000倍就行了。

  1. for (i = 0; i < 25; i++) {
  2.     a[j + i] = 1;
  3. }
  4. "从 j * 0x1000 开始的100KB空间得到分配";

■■■■■

如果要释放这部分内存空间，可以像下面这样做。比如，如果遇到这种情况：“刚才取得的从0x00123000开始的100KB，已经不用了，现在归还。谢谢你呀。”那该怎么办呢？用地址值除以0x1000，计算出j就可以了。

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

很简单吧。以后再有需要内存的时候，这个地方又可以再次被使用了。

■■■■■

上面这个方法虽然很好懂，但是有一点问题。如果内存是128MB，管理表只需要32768字节（32KB）；如果内存最大是3GB，管理表是多大呢？0xc0000000 / 0x1000 = 0xc0000 = 786432，也就是说光管理表就需要768KB。当然，虽说768KB不小，但从3GB看来，只不过是0.02%。

事实上，0.02%的比例是与容量没有关系的。用32KB管理128MB时，比例也是0.02%。如果容量是个问题，这个管理表可以不用char来构成，而是使用位（bit）来构成。归根到底，储存的只有0和1，用不了一个字节，一位就够了。这样做，程序会变得复杂些，但是管理表的大小可缩减到原来的1/8。如果是3GB内存，只需要96KB就可以管理整个内存了。这个比例只有0.003%。

我们后面还会讲到，这虽然不是最好的方法，但Windows的软盘管理方法，与这个方法很接近（1.44MB的容量，以512字节为单位分块管理）。

■■■■■

除了这个管理方法之外，还有一种列表管理的方法，是把类似于“从xxx号地址开始的yyy字节的空间是空着的”这种信息都列在表里。

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

大体就是这个样子。之所以有1000个free，是考虑到即使可用内存部分不连续，我们也能写入到这1000个free里。memman是笔者起的名字，代表memory manager。

比如，如果需要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开始的100KB空间，可以使用哦！";
  5.     }
  6. }
  7. "没有可用空间";

如果找到了可用内存空间，就将这一段信息从“可用内存空间管理表”中删除。这相当于给这一段内存贴上了“正在使用”的标签。

  1. memman.free[i].addr += 100 * 1024; /* 可用地址向后推进了100KB */
  2. memman.free[i].size -= 100 * 1024; /* 减去100KB */

如果size变成了0，那么这一段可用信息就不再需要了，将这条信息删除，frees减去1就可以了。

释放内存时，增加一条可用信息，frees加1。而且，还要调查一下这段新释放出来的内存，与相邻的可用空间能不能连到一起。如果能连到一起，就把它们归纳为一条。

能够归纳为一条的例子：

free[0]:地址0x00400000号开始，0x00019000字节可用

free[1]:地址0x00419000号开始，0x07be7000字节可用

可以归纳为

free[0]:地址0x00400000号开始，0x07c00000字节可用

如果不将它们归纳为一条，以后系统要求“请给我提供0x07bf0000字节的内存”时，本来有这么多的可用空间，但以先前的查找程序却会找不到。

■■■■■

上述新方法的优点，首先就是占用内存少。memman是8×1000 + 4 = 8004，还不到8KB。与上一种方法的32KB相比，差得可不少。而且，这里的1000是个很充裕的数字。可用空间不可能如此零碎分散（当然，这与内存的使用方法有关）。所以，这个数字或许能降到100。这样的话，只要804字节就能管理128MB的内存了。

如果用这种新方法，就算是管理3GB的内存，也只需要8KB左右就够了。当然，可用内存可能更零碎些，为了安全起见，也可以设定10000条可用区域管理信息。即使这样也只有80KB。

这样新方法，还有其他优点，那就是大块内存的分配和释放都非常迅速。比如我们考虑分配10MB内存的情形。如果按前一种方法，就要写入2560个“内存正在使用”的标记“1”，而释放内存时，要写入2560个“0”。这些都需要花费很长的时间。

另一方面，这种新方法在分配内存时，只要加法运算和减法运算各执行一次就结束了。不管是10MB也好，100MB也好，还是40KB，任何情况都一样。释放内存的时候虽然没那么快，但是与写入2560个“0”相比，速度快得可以用“一瞬间”来形容。

■■■■■

事情总是有两面性的，占用内存少，分配和释放内存速度快，现在看起来全是优点，但是实际上也有缺点，首先是管理程序变复杂了。特别是将可用信息归纳到一起的处理，变得相当复杂。

还有一个缺点是，当可用空间被搞得零零散散，怎么都归纳不到一块儿时，会将1000条可用空间管理信息全部用完。虽然可以认为这几乎不会发生，但也不能保证绝对不能发生。这种情况下，要么做一个更大的MEMMAN，要么就只能割舍掉小块内存。被割舍掉的这部分内存，虽然实际上空着，但是却被误认为正在使用，而再也不能使用。

为了解决这一问题，实际上操作系统想尽了各种办法。有一种办法是，暂时先割舍掉，当memman有空余时，再对使用中的内存进行检查，将割舍掉的那部分内容再捡回来。还有一种方法是，如果可用内存太零碎了，就自动切换到之前那种管理方法。

那么，我们的“纸娃娃系统”（haribote OS）会采用什么办法呢？笔者经过斟酌，采用了这样一种做法，即“割舍掉的东西，只要以后还能找回来，就暂时不去管它。”。如果我们陷在这个问题上不能自拔，花上好几天时间，大家就会厌烦的。笔者还是希望大家能开开心心心地开发“纸娃娃系统”。而且万一出了问题，到时候我们再回过头来重新修正内存管理程序也可以。

■■■■■

根据这种思路，笔者首先创建了以下程序。

本次的bootpack.c节选

  1. #define MEMMAN_FREES        4090    /* 大约是32KB*/
  3. struct FREEINFO {   /* 可用信息 */
  4.     unsigned int addr, size;
  5. };
  7. struct MEMMAN {     /* 内存管理 */
  8.     int frees, maxfrees, lostsize, losts;
  9.     struct FREEINFO free[MEMMAN_FREES];
  10. };
  12. void memman_init(struct MEMMAN *man)
  13. {
  14.     man->frees = 0;         /* 可用信息数目 */
  15.     man->maxfrees = 0;      /* 用于观察可用状况：frees的最大值  */
  16.     man->lostsize = 0;      /* 释放失败的内存的大小总和  */
  17.     man->losts = 0;         /* 释放失败次数 */
  18.     return;
  19. }
  21. unsigned int memman_total(struct MEMMAN *man)
  22. /* 报告空余内存大小的合计 */
  23. {
  24.     unsigned int i, t = 0;
  25.     for (i = 0; i < man->frees; i++) {
  26.         t += man->free[i].size;
  27.     }
  28.     return t;
  29. }
  31. unsigned int memman_alloc(struct MEMMAN *man, unsigned int size)
  32. /* 分配 */
  33. {
  34.     unsigned int i, a;
  35.     for (i = 0; i < man->frees; i++) {
  36.         if (man->free[i].size >= size) {
  37.             /* 找到了足够大的内存 */
  38.             a = man->free[i].addr;
  39.             man->free[i].addr += size;
  40.             man->free[i].size -= size;
  41.             if (man->free[i].size == 0) {
  42.                 /* 如果free[i]变成了0，就减掉一条可用信息 */
  43.                 man->frees--;
  44.                 for (; i < man->frees; i++) {
  45.                     man->free[i] = man->free[i + 1]; /* 代入结构体 */
  46.                 }
  47.             }
  48.             return a;
  49.         }
  50.     }
  51.     return 0; /* 没有可用空间 */
  52. }

一开始的struct MEMMAN，只有1000组的话，可能不够。所以，我们创建了4000组，留出不少余量。这样一来，管理空间大约是32KB。其中还有变量 maxfrees、lostsize、losts等，这些变量与管理本身没有关系，不用在意它们。如果特别想了解的话，可以看看函数memman_init的注释，里面有介绍。

函数memman_init对memman进行了初始化，设定为空。主要工作，是将frees设为0，而其他的都是附属性设定。这里的init，是initialize（初始化）的缩写。

函数memman_total用来计算可用内存的合计大小并返回。笔者觉得有这个功能应该很方便，所以就创建了这么一个函数。原理很简单，不用解释大家也会明白。total这个英文单词，是“合计”的意思。

最后的memman_alloc函数，功能是分配指定大小的内存。除了free[i].size变为0时的处理以外的部分，在前面已经说过了。alloc是英文allocate（分配）的缩写。在编程中，需要分配内存空间时，常常会使用allocate这个词。

memman_alloc函数中free[i].size等于0的处理，与FIFO缓冲区的处理方法很相似，要进行移位处理。希望大家注意以下写法：

man->free[i].addr = man->free[i+1].addr;

man->free[i].size = man->free[i+1].size;

我们在这里将其归纳为了：

man->free[i] = man->free[i+1];

这种方法被称为结构体赋值，其使用方法如上所示，可以写成简单的形式。

■■■■■

释放内存函数，也就是往memman里追加可用内存信息的函数，稍微有点复杂。

本次的bootpack.c节选

  1. int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size)
  2. /* 释放 */
  3. {
  4.     int i, j;
  5.     /* 为便于归纳内存，将free[]按照addr的顺序排列 */
  6.     /* 所以，先决定应该放在哪里 */
  7.     for (i = 0; i < man->frees; i++) {
  8.         if (man->free[i].addr > addr) {
  9.             break;
  10.         }
  11.     }
  12.     /* free[i - 1].addr < addr < free[i].addr */
  13.     if (i > 0) {
  14.         /* 前面有可用内存 */
  15.         if (man->free[i - 1].addr + man->free[i - 1].size == addr) {
  17.             /* 可以与前面的可用内存归纳到一起 */
  18.             man->free[i - 1].size += size;
  19.             if (i < man->frees) {
  20.                 /* 后面也有 */
  21.                 if (addr + size == man->free[i].addr) {
  22.                     /* 也可以与后面的可用内存归纳到一起 */
  23.                     man->free[i - 1].size += man->free[i].size;
  24.                     /* man->free[i]删除  */
  25.                     /* free[i]变成0后归纳到前面去 */
  26.                     man->frees--;
  27.                     for (; i < man->frees; i++) {
  28.                         man->free[i] = man->free[i + 1]; /* 结构体赋值 */
  29.                     }
  30.                 }
  31.             }
  32.             return 0; /* 成功完成 */
  33.         }
  34.     }
  35.     /* 不能与前面的可用空间归纳到一起 */
  36.     if (i < man->frees) {
  37.         /* 后面还有 */
  38.         if (addr + size == man->free[i].addr) {
  39.             /* 可以与后面的内容归纳到一起 */
  40.             man->free[i].addr = addr;
  41.             man->free[i].size += size;
  42.             return 0; /* 成功完成 */
  43.         }
  44.     }
  45.     /* 既不能与前面归纳到一起，也不能与后面归纳到一起 */
  46.     if (man->frees < MEMMAN_FREES) {
  47.         /* free[i]之后的，向后移动，腾出一点可用空间 */
  48.         for (j = man->frees; j > i; j--) {
  49.             man->free[j] = man->free[j - 1];
  50.         }
  51.         man->frees++;
  52.         if (man->maxfrees < man->frees) {
  53.             man->maxfrees = man->frees; /* 更新最大值 */
  54.         }
  55.         man->free[i].addr = addr;
  56.         man->free[i].size = size;
  57.         return 0; /* 成功完成 */
  58.     }
  59.     /* 不能往后移动 */
  60.     man->losts++;
  61.     man->lostsize += size;
  62.     return -1; /* 失败 */
  63. }

程序太长了，用文字来描述不易于理解，所以笔者在程序里加了注释。如果理解了以前讲解的原理，现在只要细细读一读程序，大家肯定能看懂。

另外，我们前面已经说过，如果可用信息表满了，就按照舍去之后带来损失最小的原则进行割舍。但是在这个程序里，我们并没有对损失程度进行比较，而是舍去了刚刚进来的可用信息，这只是为了图个方便。

■■■■■

最后，将这个程序应用于HariMain，结果就变成了下面这样。写着“（中略）”的部分，笔者没做修改。

本次的bootpack.c节选

  1. #define MEMMAN_ADDR         0x003c0000
  3. void HariMain(void)
  4. {
  5.     （中略）
  6.     unsigned int memtotal;
  7.     struct MEMMAN *memman = (struct MEMMAN *) MEMMAN_ADDR;
  8.     （中略）
  9.     memtotal = memtest(0x00400000, 0xbfffffff);
  10.     memman_init(memman);
  11.     memman_free(memman, 0x00001000, 0x0009e000); /* 0x00001000 - 0x0009efff */
  12.     memman_free(memman, 0x00400000, memtotal - 0x00400000);
  13.     （中略）
  14.     sprintf(s, "memory %dMB   free : %dKB",
  15.             memtotal / (1024 * 1024), memman_total(memman) / 1024);
  16.     putfonts8_asc(binfo->vram, binfo->scrnx, 0, 32, COL8_FFFFFF, s);

memman需要32KB，我们暂时决定使用自0x003c0000开始的32KB（0x00300000号地址以后，今后的程序即使有所增加，预计也不会到达0x003c0000，所以我们使用这一数值），然后计算内存总量memtotal，将现在不用的内存以0x1000个字节为单位注册到memman里。最后，显示出合计可用内存容量。在QEMU上执行时，有时会注册成632KB和28MB。632+28672=29304，所以屏幕上会显示出29304KB。

那好，运行一下“make run”看看。哦，运行正常。今天已经很晚了，我们明天继续吧。

4　挑战内存管理（harib06d） - 图1

能正常显示出29304KB