第九天 內存管理

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源碼或其他操作系統的源碼也有幫助。