lab1和2概述：
本次作業系統實驗，我們對計算機的作業系統進行了初步的探究，通過完成作業和問題，我們對作業系統的啟動、核心載入、一些系統函數、堆棧的使用、記憶體管理有了更加深刻的了解，并且在完成作業的同時，深刻了解了計算機記憶體的結構以及每一塊兒對應的作用。從實踐的角度出發，很好的了解了一個作業系統的底層功能的實作。具體來說：
在啟動計算機的部分中，通過gdb 的單補調試和斷點控制，我們看到計算機執行一條條機器指令的過程，并且初步的了解了一些指令的作用以及總體了解了計算機啟動和核心載入的過程。之後，我們對于Kernal 中的格式化輸出函數進行了探究，其中着重觀察了其對于進制的控制以及輸出時頁面的控制。此外，我們還自主探究了一些較為底層的與I/O 有密切關系的函數，進而更加深刻的對I/O 功能有了一定的了解。之後，我們還探究了計算機堆棧的使用，了解了指針在堆棧中的作用，并且在作業中通過對于指針的操作改造了原有的堆棧顯示函數。在記憶體管理的部分，我們的一些對于計算機記憶體的了解的不足使我們曾一度停滞不前。之後，我們通過學習《深入了解Linux 核心》以及menlayout.h 檔案中的一些提示資訊逐漸了解了計算機對于記憶體管理的方法。在實體頁管理的部分，實作了boot 的配置設定、page 的初始化、配置設定以及釋放等。在虛拟記憶體部分，我們深入了解了計算機實體位址、線性位址、邏輯位址的互相轉化，實作了虛拟記憶體中頁表的管理，實作了頁目錄的初始化、boot 頁的映射、也得查詢删除及插入等。之後，我們将men_init()中的代碼補充完全，實作了對于核心部分線性空間的初始化，并最終通過了所有的check。
此外，在完成這兩大塊内容的同時，對于問題的完成也使我們對于一些基礎概念的了解，以及代碼部分知識的掌握有了進一步的提升。
介紹工具和環境的配置
進入我們的具體問題
問題1：
問題2.1：說明兩個函數之間的聯系
問題2.2解釋題目的代碼
作業1：改成8進制輸出
作業2
(一) 作業描述：
The above exercise should give you theinformation you need to implement a stack backtrace
function, which you should callmon_backtrace(). A prototype for this function is already
waiting for you in kern/monitor.c. You cando it entirely in C, but you may find the read_ebp()
function in inc/x86.h useful. You'll alsohave to hook this new function into the kernel
monitor's command list so that it can beinvoked interactively by the user.
The backtrace function should display alisting of function call frames in the following format:
Stack backtrace:
ebp f0109e58 eip f0100a62 args 00000001f0109e80 f0109e98 f0100ed2 00000031
ebp f0109ed8 eip f01000d6 args 0000000000000000 f0100058 f0109f28 00000061
...
The first line printed reflects thecurrently executing function, namely mon_backtrace itself,
the second line reflects the function thatcalled mon_backtrace, the third line reflects the
function that called that one, and so on.You should print all the outstanding stack frames. By
studying kern/entry.S you'll find thatthere is an easy way to tell when to stop.
(二) 解答：
1.堆棧是一種簡單的資料結構，是一種隻允許在其一端進行插入或删除的線性表。允許插入或删除操作的一端稱為棧頂，另一端稱為棧底，對堆棧的插入和删除操作被稱入棧和出棧。
2.有一組CPU 指令可以實作對程序的記憶體實作堆棧通路。其中，POP 指令實作出棧操作，PUSH 指令實作入棧操作。CPU 的ESP 寄存器存放目前線程的棧頂指針，EBP 寄存器中儲存目前線程的棧底指針。CPU 的EIP 寄存器存放下一個CPU 指令存放的記憶體位址，當CPU 執行完目前的指令後，從EIP寄存器中讀取下一條指令的記憶體位址，然後繼續執行。
3.實作原理：C 函數調用時，首先将參數push入棧，然後push 傳回位址，接着将原來的EBP push 入棧，然後将ESP 的值賦給EBP，令ESP 指向新的棧頂。而函數傳回時，會将EBP 的值賦予ESP，然後pop 出原來的EBP 的值賦予EBP指針。
int
mon_backtrace(int argc, char **argv, structTrapframe *tf)
{
// Your code here.
unsigned int ebp;
unsigned int eip;
unsigned int args[5];
unsigned int i;
ebp = read_ebp();
cprintf("Stack backtrace:\n");
do {
eip = *((unsigned int*)(ebp + 4));
for(i=0; i<5; i++)
args[i] = *((unsigned int*) (ebp + 8 +4*i));
cprintf(" ebp %08x eip %08x args %08x%08x %08x %08x %08x\n",
ebp, eip, args[0], args[1], args[2],args[3], args[4]);
ebp = *((unsigned int *)ebp);
} while(ebp != 0);
Return 0；
}
作業 3
作業描述
在檔案 kern/pmap.c 中,你需要實作以下函數的代碼(如下,按序給出):
boot_alloc()
mem_init() //(在調用check_page_free_list(1)之前的部分)
page_init()
page_alloc()
page_free()
解答
首先，我們要先來了解一下記憶體管理的機制。
1. 三個重要位址：
1） 邏輯位址為使用者程式所使用的位址；
2） 線性位址是作業系統根據x86 段式位址轉換将邏輯位址轉換後的位址，具體來說：線性位址 = 邏輯位址 -KERNBASE
3） 實體位址是作業系統位址轉換系統将線性位址通過頁表位址轉換後得到的資料真實存儲位址邏輯位址；
2. 實體記憶體分頁：
一個實體頁的大小為4K 位元組，第0 個實體頁從實體位址 0x00000000 處開始。由于頁的大小為4KB，就是0x1000 位元組，是以第1 頁從實體位址0x00001000處開始。第2 頁從實體位址 0x00002000 處開始。可以看到由于頁的大小是4KB，是以隻需要32bit 的位址中高20bit 來尋址實體頁。頁表：一個頁表的大小為4K 位元組(32bit)，放在一個實體頁中。由1024 個4位元組的頁表項組成。頁表中的每一項的内容（每項4 個位元組,32bit）高20bit 用來放一個實體頁的實體位址，低12bit 放着一些标志。
頁目錄：一個頁目錄大小為4K 位元組(32bit)，放在一個實體頁中。由1024 個4 位元組的頁目錄項組成。頁目錄中的每一項的内容（每項4 個位元組）高20bit 用來放一個頁表的實體位址，低12bit 放着一些标志。
3. 虛拟位址：
如果CPU 寄存器中的分頁标志位被設定，那麼執行記憶體操作的機器指令時，CPU 會自動根據頁目錄和頁表中的資訊，把虛拟位址轉換成實體位址，完成該指令。比如 mov eax,004227b8h ，這是把位址004227b8h 處的值賦給寄存器的彙編代碼，004227b8 這個位址就是虛拟址。CPU 在執行這行代碼時，發現寄存器中的分頁标志位已經被設定，就自動完成虛拟位址到實體位址的轉換，使用實體位址取出值，完成指令。對于Intel CPU 來說，分頁标志位是寄存器CR0 的第31位，為1 表示使用分頁，為0 表示不使用分頁。對于初始化之後的 Win2k 我們觀察 CR0 ，發現第31 位為1。表明Win2k 是使用分頁的。使用了分頁機制之後，4G 的位址空間被分成了固定大小的頁，每一頁或者被映射到實體記憶體，或者被映射到硬碟上的交換檔案中，或者沒有映射任何東西。對于一般程式來說，4G 的位址空間，隻有一小部分映射了實體記憶體，大片大片的部分是沒有映射任何東西。實體記憶體也被分頁，來映射位址空間。對于32bit的Win2k，頁的大小是4K 位元組。CPU 用來把虛拟位址轉換成實體位址的資訊存放在叫做頁目錄和頁表的結構裡。
4. 然後我們可以再inc/mmu.h 看到對于線性位址定義的闡述以及對于頁表、頁
目錄的值的宏定義。
5.在inc/memlayout.h 中看到虛拟記憶體的層次結構。
6.然後打開kern/pmap.c，首先來看boot——allocated（）函數。bootmain的最後一句跳轉到0x10000c 處,開始執行 entry.S 的代碼.kernel 結束之後就是freememory 了，而在free memory 的最開始存放的是pgdir，這塊記憶體就是由boot_alloc 申請。
于是，boot_alloc(unit32_t n)的功能就是申請n 個位元組的位址空間，傳回申請空間的首位址。如果n 是0，則傳回nextfree(未配置設定空間的首位址)。其中，配置設定的位址是頁對齊的，即4K 對齊。值得注意的是，未初始化的全局變量和靜态變量會被自動初始化為0。函數以首先定義靜态局部變量nextfree，它指向空閑記憶體空間的首位址。由于未初始化，是以變量自動初始化為0，是以首次調用boot_alloc()函數的時候，nextfree 的值是0，會執行下面的語句：
if (!nextfree) {
extern char end[];
nextfree = ROUNDUP((char *) end, PGSIZE);
}
還有一個細節就是需要4k 頁對齊，使用了ROUNDUP 宏定義。接下來，在你n>0時，我們将nextfree+n 記憶體加入，并傳回目前配置設定完的這塊記憶體的頭指針。
if(n>0){
result = nextfree;
nextfree = (char *)((uint32_t)nextfree+n);
nextfree = ROUNDUP(nextfree,PGSIZE);
return result;
}
else{
return nextfree;
}
7.接下來是mem_init()函數
這個函數隻需要補充一部分就可以了。主要是要為struct Page 的結構體的指針pages 申請一定的位址空間。首先來看structPage 的定義：
struct Page
{ //Next page on the free list.
struct Page *pp_link;
uint16_t pp_ref;
}
結構體裡主要有兩個變量:
1） pp_link 表示下一個空閑頁，如果pp_link=0,則表示這個頁面被配置設定了，否則，這個頁面未被配置設定，是空閑頁面。
2） pp_ref 表示頁面被引用數，如果為0，表示是空閑頁。(這個變量類似于智能指針中指針的引用計數)。補充的代碼比較簡單，就是位pages 申請足夠的空間(npages 的頁面)，來存放這些結構體，并且用memset 來初始化:
pages = (struct Page*)boot_alloc(sizeof(structPage)*npages);
memset(pages, 0, sizeof(struct Page)*npages);
8. page_init(void)函數，按照提示的記憶體劃分分别初始化page 就可以了。尤其注意提示4 要參考虛拟記憶體的層次圖，注意劃分Empty Memory。對于保留不能讓其他程式使用的page 均設定pp_ref=1 即可，對于可以使用的page 做成一個連結清單，在初始化可用page 時實際上就是做了一個連結清單的頭插入操作。
page_init(void)
{
// The example code here marks all physicalpages as free.
// However this is not truly the case. Whatmemory is free?
// Change the code to reflect this.
// NB: DO NOT actually touch the physicalmemory corresponding to
// free pages!
//以下按照提示的記憶體劃分分别初始化page
size_t i;
for (i = 0; i < npages; i++) {
if(i == 0)
{
// 1) Mark physical page 0 as in use.
// This way we preserve the real-mode IDTand BIOS structures
// in case we ever need them. (Currently wedon't, but...)
pages[i].pp_ref = 1;
pages[i].pp_link = NULL;
}
else if(i>=1 &&i<npages_basemem)
{
// 2) The rest of base memory, [PGSIZE,npages_basemem * PGSIZE)
// is free.
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
else if(i>=IOPHYSMEM/PGSIZE &&i< EXTPHYSMEM/PGSIZE )
{
// 3) Then comes the IO hole [IOPHYSMEM,EXTPHYSMEM), which must
// never be allocated.
pages[i].pp_ref = 1;
pages[i].pp_link = NULL;
}
else if( i >= EXTPHYSMEM / PGSIZE&&
i < ( (int)(boot_alloc(0)) -KERNBASE)/PGSIZE)
{
// 4) Then extended memory [EXTPHYSMEM,...).
// Some of it is in use, some is free.Where is the kernel
// in physical memory? Which pages arealready in use for
// page tables and other data structures?
//
pages[i].pp_ref = 1;
pages[i].pp_link =NULL;
}
else
{
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
}
}
9. page_alloc() 和 page_free()的函數思路比較簡單，一個是page申請，一個是page 釋放，主要也就是連結清單操作，和pp_ref 的指派。
struct Page *
page_alloc(int alloc_flags)
{
// Fill this function in
//如page_free_list 為空，則不能正确配置設定空閑記憶體，是以傳回空指針
if(page_free_list==NULL)
return NULL;
struct Page *result = page_free_list;
//将實體空閑清單的頭指針指派給result，相當于配置設定了一個空閑記憶體
page_free_list = result->pp_link;
result->pp_link = NULL;
if(alloc_flags & ALLOC_ZERO)
memset(page2kva(result),0,PGSIZE);
return result;
}
void
page_free(struct Page *pp)
{
// Fill this function in 通過修改清單的表頭，将pp加入到隊列中
//驗證pp_ref!=0 的情況,檢驗要釋放的page 沒有被任何程式使用
if(pp->pp_ref!=0){
panic("pp_ref!=0");
}
pp->pp_link = page_free_list;
page_free_list = pp;
}
問題三：
先給出答案：虛拟位址。對于這個問題，首先pdf 的上面一頁教學内容已經基本把知識講到了，下面的截圖就是響應的關鍵内容：
然後搜尋資料還發現一下很重要的地方：
From code executing on the CPU, once we'rein protected mode (which we
entered first thing inboot/boot.S),there'sno way to directly use a linear or physical
address. All memory references areinterpreted as virtual addresses and translated
by the MMU, which means all pointers in Care virtual addresses.
這句話就告訴我們，在程式裡面的所有位址，都是虛拟位址，系統會通過MMU來翻譯得到他的實體位址。也就是說，程式裡面的一切的位址都是虛拟位址。即使是實體位址，程式在調用的時候也會把他當成是虛拟位址，會轉化為實體位址。
綜上所述，這道題就是要厘清楚在JOS 系統裡面，什麼是實體位址，什麼是虛拟位址。由于系統會經常要進行位址的相關運算，是以經常要進行強制轉化，把一個unsigned int 型變量轉化為一個位址，或者相反，是以在程式裡面，需要對兩者進行區分。x 應該是uintptr_t，在程式裡面，任何指針都是虛拟位址(段偏移)。
作業四：
Now we set up virtual memory
看到這句話，進入我們的第四問。往下看一下mem_init的幾個注釋，接下來我們大緻要做的事是将虛拟記憶體空間[UPAGES,UPAGES+ROUNDUP((sizeof(structPage) * npages)映射到實體空間
[PADDR(pages),PADDR(pages)+ROUNDUP((sizeof(struct Page) *npages)中這個映射關系加入到頁目錄pagedir中去；然後又是對bootstack和KERNBASE的相關位址做相同相似的映射并加入頁目錄，然後就是一大堆check。我們需要寫下的相關程式就是上邊操作映射的page_insert和boot_map_region，以及在實作這兩個函數要用到的pgdir_walk、page_lookup和page_remove。
我們從最基本的也是最重要的操作pgdir_walk 說起。這個函數做的事情就是: 給定一個頁目錄表指針pgdir ，該函數應該傳回線性位址va 所對應的頁表項指針。兩個參數pde_t *pgdir, const void *va, int create，根據注釋可知具體要實作的東西是：pgdir 是一個指向page dictionary 的指針，然後va 是虛拟位址，這個函數要傳回這個虛拟位址指向的頁表項（PTE）。如果這個PTE 存在，那麼傳回這個PTE 即可，如果不存在，參數create 是指這個頁表項是否需要被建立，若需要就建立一個頁表項，不需要就傳回NULL。建立失敗傳回NULL，成功就為這個頁表項的引用計數+1。
是以我們的代碼如下：
1.首先得到這個虛拟位址所在的頁目錄偏移：
int pdeIndex = (unsigned int)va >>22;
2.通過頁目錄表pgdir+頁目錄偏移求得這頁在pagedirectory 的位址，按照注釋的幾種情況分别操作：
3.最後計算這個頁目錄項對應的頁表頁的基位址，傳回對應的頁表項指針
然後再來看看mem_init主要用到的boot_map_region函數。提示告訴我們要将虛拟記憶體空間[va, va+size)映射到實體空間[pa, pa+size)這個映射關系加入到頁目錄pagedir中。這個函數主要的目的是為了設定虛拟位址UTOP之上的位址範圍，這一部分的位址映射是靜态的，在作業系統的運作過程中不會改變，是以，這個頁的Page結構體中的pp_ref域的值不會發生改變。pde_t *pgdir,uintptr_t va, size_t size, physaddr_t pa,int perm，幾個參數意義也很明顯，一個頁目錄表指針pgdir，虛拟位址va和要映射的size，和va映射的實體位址pa，最後權限标志位perm。是以我們的代碼也很簡單：
接下來的insert函數也是在mem_init進行調用，其目的和boot_map_region很像，把一個實體頁pp與虛拟位址va建立映射，主要是操作的空間對象不同。pde_t *pgdir, struct Page *pp, void *va,int perm，幾個參數和前面也差不多。根據注釋需要注意的是：
如果虛拟記憶體va 處已經有一個實體頁與它映射，那麼應該調用page_removed()。如果必要的話，應該配置設定一個頁表并把它插入頁目錄中。pp->ref 應該在插入成功後+1。如果一頁原來就在va 處，那麼TLB 一定是無效的。若成功則傳回0，沒有成功配置設定頁表的話就傳回E_NO_MEM。
根據這些情況寫出我們的代碼：
來看看insert 要用到的page_remove 函數。取消虛拟位址va 處的實體頁映射，如果這個位址上本來就沒有實體頁，那麼就不用取消。注意細節就是：這處實體頁的引用計數要減1，然後要将它free，如果這個位址的頁表項存在，那麼頁表項要置0。頁表中remove 一個表項時要将TLB 置為無效。根據注釋資訊代碼也很明了：
最後，在remove 中我們又用了一個函數，也是本題的最後一個函數page_lookup。結合注釋顧名思義，這個函數将會傳回虛拟位址va 映射的頁page 結構體的指針。然後如果參數pte_store!=0，那麼我們将頁表項pte 的位址存儲到pte_store 中。如果va 處沒有實體頁，那麼傳回NULL。是以代碼：
作業五：
part3 主要是使用者空間和核心空間的一些東西。主要區分就是ULIM，在ULIM上面的就是核心空間，在下面的部分就是使用者空間
根據提示需要映射使用者僅可讀的頁，是以我們定義權限為PTE_U|PTE_P。之後，我們通過ROUNDUP 計算出pages 結構體的大小，并使用已經定義好的page_insert()進行映射。
此處根據要求我們把虛拟位址[KSTACKTOP-KSTKSIZE, KSTACKTOP)映射到以bootstack 為起點的實體位址(bootstack 實際存儲的是其虛拟位址，需要轉換位實體位址)，并且在權限上為核心可讀寫，使用者不可見，是以在設定權限後，使用boot_map_region()完成映射。
這段代碼要求把位址從[KERNBASE, 2^32)映射到[0, 2^32 - KERNBASE)。但是我們沒有2^32-KERNNASE byte 的記憶體，是以我們需要通過ROUNDUP 來得到size。
問題4：
根據menlayout.h 中的記憶體表我們可以補充表格如下
我們已經将核心和使用者環境放在了相同的位址空間,為什麼使用者程式不能讀或者寫核心記憶體？什麼樣的具體機制保護核心記憶體？
主要看低3 位，即U，W，P 三個标志位。
p：代表頁面是否有效，若為1，表示頁面有效。否則，表示頁面無效，不能映射頁面，否則會發生錯誤。
W:表示頁面是否可寫。若為1，則頁面可以進行寫操作，否則，頁面是隻讀頁面，不能進行修改。
U：表示使用者程式是否可以使用該頁面。若位1，表示此頁面是使用者頁面，使用者程式可以使用并且通路該頁面。若為0，則表示使用者程式不能通路該頁面，隻有核心才能通路頁面。
上面的頁面标志位，可以有效的保護系統的安全。由于作業系統運作在核心空間(微核心除外，其部分系統功能在使用者态下進行)中運作，而一般的使用者程式都是在使用者空間上運作的。是以使用者程式的奔潰，不會影響到作業系統，因為使用者程式無權對核心位址中的内容進行修改。這就有效的對作業系統和使用者程式進行了隔離，加強了系統的穩定性。
3. 這個作業系統最大能支援多大的實體記憶體？為什麼？
2GB
原因：作業系統使用4MB 的UPAGES 存放頁的結構體Page，每個頁占據8B 的空間，而每個頁映射4KB 的記憶體，是以總共映射的記憶體為：4MB/8B*4KB = 2GB.
4. 管理記憶體有多大的空間開銷，如果我們擁有最強大的實體記憶體？這個空間開
銷如何減小？
(1)存放所有的Page，需要1024*4B=4MB
(2)存放頁目錄表 kern_pgdir 4KB
(3)存放目前的頁表4MB。
總的開銷:8196 KB。
我們可以将每一頁的空間定為4MB 這樣空間使用率就會有很大的提升