第九天 記憶體管理
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原始碼或其他作業系統的原始碼也有幫助，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298182.html
標籤：其他
上一篇：物聯網工程畢業設計 - 選題推薦