第九天 內(nèi)存管理

1.整理源文件

這一節(jié)只是進(jìn)行了代碼整理，把鼠標(biāo)鍵盤相關(guān)的內(nèi)容轉(zhuǎn)移到了特定的文件里。

2.內(nèi)存容量檢查（1）

要做內(nèi)存管理，首先得知道內(nèi)存的容量，怎么知道內(nèi)存的容量呢？BIOS可以告訴我們答案。但使用BIOS稍微有點(diǎn)麻煩，于是，作者決定自己寫程序檢查內(nèi)存容量。

內(nèi)存檢查程序主要有以下幾步：

1. 檢查CPU是386芯片還是486芯片。若為486芯片，則禁止cache。（386沒有cache）

2. 不斷向內(nèi)存寫入然后讀取數(shù)據(jù)。如果寫入和讀取的內(nèi)容一樣，則內(nèi)存連接正常。

怎么判斷CPU是386還是486呢？這里需要用到狀態(tài)寄存器。狀態(tài)寄存器的第18位AC位（Alignment Check，對齊檢查），在386中即使將它設(shè)置為1，它也會變成0，而486中不會出現(xiàn)這種情況。于是，根據(jù)這個特點(diǎn)，我們就可以判斷出CPU是386還是486的，然后再確定需不需要禁止緩存。相關(guān)的代碼如下所示。

?unsigned int memtest(unsigned int start, unsigned int end)?{? ? ?char flg486 = 0;? ? ?unsigned int eflg, cr0, i;??? ? ?/* 確認(rèn)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，即使設(shè)定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）的函數(shù)定義如下。

?_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

接下來是第二步，向內(nèi)存讀寫數(shù)據(jù)，檢查內(nèi)存是否正確。

?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; ? ? ? /* 反轉(zhuǎn) */? ? ? ? ?if (*p != pat1) ? ? ? ? /* 檢查反轉(zhuǎn)結(jié)果 */? ? ? ?  {?not_memory:? ? ? ? ? ? ?*p = old;? ? ? ? ? ? ?break;? ? ? ?  }? ? ? ? ?*p ^= 0xffffffff; ? ? ? /* 再次反轉(zhuǎn) */? ? ? ? ?if (*p != pat0) ? ? ? ? /* 檢查值是否恢復(fù) */? ? ? ?  {? ? ? ? ? ? ?goto not_memory;? ? ? ?  }? ? ? ? ?*p = old; ? ? ? ? ? ? ? /* 恢復(fù)為修改前的值 */? ?  }? ? ?return i;?}

可以看到，這段代碼很簡單，不斷對內(nèi)存地址的值進(jìn)行翻轉(zhuǎn)，若翻轉(zhuǎn)后的值與預(yù)期的不同，則說明內(nèi)存有問題。這里還要思考一個問題，上面函數(shù)的參數(shù)start和end應(yīng)該賦予什么值？為什么？

上面內(nèi)存檢查的代碼看起來不錯，但是運(yùn)行速度太慢了，畢竟它對每個地址都進(jìn)行檢查。作者讓檢查程序偷偷懶，讓它能夠執(zhí)行得更快，代碼如下所示。

?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; ? ? ? /* 反轉(zhuǎn) */? ? ? ? ?if (*p != pat1) ? ? ? ? /* 檢查反轉(zhuǎn)結(jié)果 */? ? ? ?  {?not_memory:? ? ? ? ? ? ?*p = old;? ? ? ? ? ? ?break;? ? ? ?  }? ? ? ? ?*p ^= 0xffffffff; ? ? ? /* 再次反轉(zhuǎn) */? ? ? ? ?if (*p != pat0) ? ? ? ? /* 檢查值是否恢復(fù) */? ? ? ?  {? ? ? ? ? ? ?goto not_memory;? ? ? ?  }? ? ? ? ?*p = old; ? ? ? ? ? ? ? /* 恢復(fù)為修改前的值 */? ?  }? ? ?return i;?}

修改后，檢查程序每4K地址只檢查4字節(jié)地址，速度自然是比之前快多了。另外，這段代碼只是為了檢查內(nèi)存的容量，不要記錯了它的功能。

接下來改一改HariMain就能運(yùn)行了，將內(nèi)存檢查放在死循環(huán)之前。

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

運(yùn)行的顯示如下。

這里顯示內(nèi)存有3G內(nèi)存，而系統(tǒng)內(nèi)存實(shí)際只有32M，這明顯不對，是什么地方出錯了？

3.內(nèi)存內(nèi)容檢查（2）

上一節(jié)為什么會出錯呢？這全都是編譯器的鍋。

在從C語言轉(zhuǎn)換成匯編的過程中，編譯器發(fā)現(xiàn)內(nèi)存檢查過程中沒有什么實(shí)際的改變，就把這段給優(yōu)化掉了。比如，首先給一個地址存入0xaa55aa55，翻轉(zhuǎn)后變成0x55aa55aa，然后再次反轉(zhuǎn)變成0xaa55aa55，從結(jié)果而言并沒有發(fā)生什么變化。

為了防止代碼被優(yōu)化，采用匯編代碼編寫內(nèi)存檢查的函數(shù)。

?_memtest_sub: ? ; unsigned int memtest_sub(unsigned int start, unsigned int end)? ? ?PUSH ? ?EDI ? ? ? ? ? ? ? ? ; （保存EBX、ESI、EDI中的數(shù)據(jù)）? ? ?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語言代碼是一樣的，相信大家很容易理解。

運(yùn)行結(jié)果如下。

4.挑戰(zhàn)內(nèi)存管理

相信學(xué)過操作系統(tǒng)的人都知道內(nèi)存管理的重要性，畢竟沒了內(nèi)存管理，操作系統(tǒng)怎么知道哪塊內(nèi)存能用哪塊內(nèi)存不能用？

這個操作系統(tǒng)比較小，沒有虛擬存儲器，也沒有什么頁面置換算法，更沒有什么分頁分段，直接采用可變長度分配這種簡單粗暴的方法。作者認(rèn)為分頁所需的管理表會占用不少空間就放棄了。

我們對每段空間的管理只記錄兩個信息：起始地址和長度。而為了方便管理，把這兩個數(shù)據(jù)放在一個結(jié)構(gòu)體中。

?struct FREEINFO ? ? /* 可用信息 */?{? ? ?unsigned int addr, size;?};???struct MEMMAN ? ? ? /* 內(nèi)存管理 */?{? ? ?int frees;? ? ?struct FREEINFO free[1000];?};

在MEMMAN結(jié)構(gòu)體中，frees是已使用的FREEINFO結(jié)構(gòu)體的數(shù)量，并且還有一個大小為1000的FREEINFO結(jié)構(gòu)體數(shù)組。

對于MEMMAN結(jié)構(gòu)體而言，有增刪改移位等操作。在了解這些操作的實(shí)現(xiàn)之前，我們要知道內(nèi)存的分配算法是哪種，這個操作系統(tǒng)采用的是首次適應(yīng)算法，首次適應(yīng)算法的空閑分區(qū)要按地址由低到高進(jìn)行排序，從空閑分區(qū)表的第一個表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配出去。

1.改變。只是改動addr和size的值。

2.增加。內(nèi)存中，從0x400000開始的長度為0x7c00000的內(nèi)存塊未被使用，首先把這塊內(nèi)存添加到MEMMAN結(jié)構(gòu)體中。

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

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

4.刪除。申請的大小與空閑塊大小一致。

5.合并。釋放的內(nèi)存塊與前后地址的內(nèi)存塊合并。

對于內(nèi)存空閑塊的操作就這5種操作，我們只需根據(jù)這五種操作編寫代碼即可。

為了使得功能更完善，我們要為MEMMAN結(jié)構(gòu)體添加一些東西。

?#define MEMMAN_FREES ?  4090 ? ? ? ?/* 大約是32KB */???struct FREEINFO ? ? /* 可用信息 */?{? ? ?unsigned int addr, size;?};???struct MEMMAN ? ? ? /* 內(nèi)存管理 */?{? ? ?int frees, maxfrees, lostsize, losts;? ? ?struct FREEINFO free[MEMMAN_FREES];?};

使用可變長度的內(nèi)存分配不可避免地會產(chǎn)生一些內(nèi)存碎片，losts用于記錄碎片地?cái)?shù)量，lostsize用于記錄碎片的總大小。

下面介紹內(nèi)存相關(guān)的函數(shù)。

?void memman_init(struct MEMMAN *man)?{? ? ?man->frees = 0; ? ? ? ? /* 可用信息數(shù)目 */? ? ?man->maxfrees = 0; ? ? ?/* 用于觀察可用狀況：frees的最大值 */? ? ?man->lostsize = 0; ? ? ?/* 釋放失敗的內(nèi)存的大小總和 */? ? ?man->losts = 0; ? ? ? ? /* 釋放失敗次數(shù) */?}???unsigned int memman_total(struct MEMMAN *man) ? /* 報(bào)告剩余內(nèi)存大小的合計(jì) */?{? ? ?unsigned int i, t = 0;? ? ?for (i = 0; i < man->frees; i++)? ?  {? ? ? ? ?t += man->free[i].size;? ?  }? ? ?return t;?}

memman_init初始化MEMMAN結(jié)構(gòu)體成員，memman_total計(jì)算出剩余內(nèi)存總大小，這些都比較簡單。

?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) ?/* 找到了足夠大的內(nèi)存 */? ? ? ?  {? ? ? ? ? ? ?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是內(nèi)存分配函數(shù)，采用的是首次適應(yīng)算法，也算簡單。

?int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size) ? /* 釋放 */?{? ? ?int i, j;? ? ?/* 為便于歸納內(nèi)存，將free[]按照addr的順序排列 */? ? ?/* 所以，仙居定應(yīng)該放哪兒 */? ? ?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) ?/* 若前面有可用內(nèi)存 */? ?  {? ? ? ? ?if (man->free[i - 1].addr + man->free[i - 1].size == addr) ?/* 若與前面的可用內(nèi)存相鄰，則歸納在一起 */? ? ? ?  {? ? ? ? ? ? ?man->free[i - 1].size += size;? ? ? ? ? ? ?if (i < man->frees) /* 若后面也有可用內(nèi)存內(nèi)存 */? ? ? ? ? ?  {? ? ? ? ? ? ? ? ?if (addr + size == man->free[i].addr) ? /* 若與后面的可用內(nèi)存相鄰，則歸納在一起 */? ? ? ? ? ? ? ?  {? ? ? ? ? ? ? ? ? ? ?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; ? /* 成功完成 */? ? ? ?  }? ?  }? ? ?/* 若不能與前面的內(nèi)存歸納在一起 */? ? ?if (i < man->frees) /* 若后面也有可用內(nèi)存內(nèi)存 */? ?  {? ? ? ? ?if (addr + size == man->free[i].addr) ? /* 若與后面的可用內(nèi)存相鄰，則歸納在一起 */? ? ? ?  {? ? ? ? ? ? ?man->free[i].addr = addr;? ? ? ? ? ? ?man->free[i].size += size;? ? ? ? ? ? ?return 0; ? /* 成功完成 */? ? ? ?  }? ?  }? ? ?/* 既不能與前面內(nèi)存歸納在一起，也不能與后面內(nèi)存歸納在一起 */? ? ?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; ? /* 成功完成 */? ?  }? ? ?/* 信息個數(shù)已達(dá)到最大 */? ? ?man->losts++;? ? ?man->lostsize += size; ?/* 失敗 */? ? ?return -1;?}

內(nèi)存釋放的算法邏輯可以看看上面的圖，理解起來應(yīng)該不會太困難。

最后還需修改一下HariMain，這里不做展示了，直接上結(jié)果圖。

書上的內(nèi)容到此結(jié)束。在此，給大家一點(diǎn)小建議，可以嘗試自己實(shí)現(xiàn)一個內(nèi)存管理算法，當(dāng)使用的內(nèi)存塊很少時，書中的內(nèi)存管理算法不算慢，但是一旦多起來（達(dá)到一兩千的量級），所需時間飆升（畢竟時間復(fù)雜度為O(n2)）。試試采用雙向鏈表或其他的數(shù)據(jù)結(jié)構(gòu)，把時間復(fù)雜度減至O(n)的水平。

其實(shí)已經(jīng)不準(zhǔn)備寫關(guān)于《30天自制操作系統(tǒng)》的博客了，因?yàn)檫@本書的代碼不是很系統(tǒng)，但是有人問我還有后續(xù)嗎，而且我覺得內(nèi)存管理比較有用，就寫了這一篇博客，后面還有任務(wù)切換、異常處理等內(nèi)容也有趣，但我應(yīng)該不會再寫了。現(xiàn)在正在看《一個64位操作系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)》，我也很推薦看這本書，代碼借鑒于Linux，對以后看Linux源碼或其他操作系統(tǒng)的源碼也有幫助。