操作系統(tǒng)xv6第三次作業(yè)

1、XV6 第三次作業(yè)信息科學(xué)技術(shù)學(xué)院 1100012736 邢捷1. 什么是臨界區(qū)？什么是同步和互斥？什么是競(jìng)爭(zhēng)狀態(tài)？臨界區(qū)操作時(shí)中斷是否應(yīng)該開啟？中斷會(huì)有什么影響？XV6 的鎖是如何實(shí)現(xiàn)的，有什么操作？xchg 是什么指令，該指令有何特性？答：臨界區(qū)：對(duì)某個(gè)共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作的程序片段；同步和互斥：同步是指系統(tǒng)中多個(gè)進(jìn)程（線程）中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互 合作共同完成一項(xiàng)任務(wù)，互斥是指以某種手段確保當(dāng)一個(gè)進(jìn)程在使用一個(gè)共享變量或文件時(shí)，其他進(jìn)程不能做同樣的操作。競(jìng)爭(zhēng)條件：兩個(gè)或多個(gè)進(jìn)程讀寫某些共享數(shù)據(jù)，而最后的結(jié)果取決于進(jìn)程運(yùn)行的精確時(shí)序，這個(gè)成為競(jìng)爭(zhēng)條件；臨界區(qū)操

2、作時(shí)不應(yīng)該開啟中斷，如果開啟中斷，就有可能改變共享區(qū)的數(shù)據(jù)，從而破壞了整個(gè)程序最后獲得的結(jié)果。struct spinlock uint locked;/ For debugging: char *name; struct cpu *cpu; uint pcs10;/ Is the lock held?/ Name of lock./ The cpu holding the lock./ The call stack (an array of program counters)/ that locked the lock.;XV6 中，鎖的結(jié)構(gòu)如上代碼，鎖是通過(guò) spinlock.c 中的各個(gè)函

3、數(shù)實(shí)現(xiàn)的，包括初始化，獲取鎖，釋放鎖等操作。xchg 為一條 CPU 原子指令，指令格式為 xchg(va,newvalue),作用是交換內(nèi)存地址 va 中的值和newvalue，返回值為內(nèi)存地址 va 中運(yùn)行 xchg 之前的值。2.基于 XV6 的 spinlock，請(qǐng)給出實(shí)現(xiàn)信號(hào)量、讀寫鎖、信號(hào)機(jī)制的設(shè)計(jì)方案（三選一，請(qǐng)寫出相應(yīng)的偽代碼）答：讀寫鎖偽代碼：初始化鎖；程序運(yùn)行至想要獲得鎖關(guān)閉中斷，保存寄存器值；看此時(shí)此 CPU 是否占有鎖，如果不是則運(yùn)行下面；While(鎖不空閑)；/鎖處于空閑狀態(tài) Xchg()；更改鎖的 cpu 指向，說(shuō)明哪個(gè) cpu 獲得鎖；cs(&lk,lk-pcs

4、);獲得鎖時(shí)的函數(shù)調(diào)用棧Getcall程序運(yùn)行；程序鎖If(!holding(lk)判斷當(dāng)前 CPU 是否拿到這把鎖(報(bào)錯(cuò)；)將鎖的 CPU將中斷打開；和函數(shù)調(diào)用棧；結(jié)束3.XV6 初始化之后到執(zhí)行 main.c 時(shí)，內(nèi)存布局是怎樣的（其中已有哪些內(nèi)容）？答：在 main 函數(shù)中，內(nèi)存空間的初始化使用函數(shù) kinit1 完成的，創(chuàng)建了一個(gè) 4M 頁(yè)大小的空閑頁(yè)，分配一個(gè)內(nèi)核頁(yè)表 entrypgdir。此時(shí)在 XV6 中，在 entry.s 文件中詳細(xì)說(shuō)明的內(nèi)存的布局，兩部分內(nèi)存被到了物理內(nèi)存上，va 的0,4M)和kernbase ,kernbase+4M同時(shí)被到了 pa 的0,4M上。4.

5、XV6 的動(dòng)態(tài)內(nèi)存管理是如何完成的？有一個(gè) kmem（鏈表），用于管理可分配的物理內(nèi)存頁(yè)。（vend=0 x00400000，也就是可分配的內(nèi)存頁(yè)最大為 4Mb）答：kmem 的結(jié)構(gòu)為StructStruct spinlock lock; Struct run *freelist;kmem;通過(guò) kinit1，kinit2 來(lái)初始化物理內(nèi)存，通過(guò) freerange,kfree 來(lái)回收一段內(nèi)存，kalloc 來(lái)分配一段內(nèi)存來(lái)管理XV6 的動(dòng)態(tài)內(nèi)存。XV6 中的內(nèi)存是以連續(xù)的段的方式進(jìn)行的，通過(guò)單鏈表的方式空閑的段。Kinit1 用來(lái)初始化一段物理地址用來(lái)當(dāng)做臨界區(qū)，Kinit2 用來(lái)初始化一段

6、物理地址用來(lái)當(dāng)做非臨界區(qū)。Freerange 函數(shù)將從 vstart 到 vstop 之間的每個(gè)頁(yè)，以 4k 為存。，都調(diào)用 kfree 來(lái)內(nèi)Kree 每次回收一個(gè)頁(yè)時(shí)，將回收的頁(yè)加入到空閑頁(yè)序列中。Kalloc 進(jìn)行分配空閑頁(yè)時(shí)，去除 kmem 的隊(duì)首元素并且刪除首元素。5. XV6 的虛擬內(nèi)存是如何初始化的？畫出 XV6 的虛擬內(nèi)存布局圖，請(qǐng)說(shuō)出每一部分對(duì)應(yīng)的內(nèi)容是什么。見 memlayout.h 和 vm.c 的 kmap 上的注釋答：Vm.c 中調(diào)用mappages()函數(shù)將一段虛擬地址映射到對(duì)應(yīng)長(zhǎng)度的物理地址上，記錄在頁(yè)表中。然后通過(guò) walkpgdir 來(lái)進(jìn)行地址的轉(zhuǎn)換。0 xFF

7、FFFFFF0 xFE0000000 x8E0000000 x80000000+data0 x801000000 x800000000 x00000000虛擬地址到物理地址虛擬地址 0KERNBASE 即用戶空間(text+data+stack+heap),對(duì)應(yīng)的物理內(nèi)存有內(nèi)核來(lái)分配虛擬地址KERNBASEKERNBASE+EXTMEM 映射到 0EXTMEM 即 I/O 地址空間 BIOS虛擬地址KERNBASE+EXTMEMdata 映射到 EXTMEMV2P(data) 內(nèi)核 text 和 ro 段虛擬地址 dataKERNBASE+PHYSTOP 映射到 V2P(data)PHYSTO

8、P,內(nèi)核 data 段 BSS 段和可供內(nèi)核分配的內(nèi)存虛擬地址 0 xfe0000000 直接映射(devices such as ioapic)其中KERNBASE = 0 x80000000;#define EXTMEM0 x100000#define PHYSTOP 0 xE000000/ Start of extended memory/ Top physical memory內(nèi)核 text 段和 ro 段I/O 地址空間和 BIOS用戶空間直接映射內(nèi)核 data 段，BSS 段6. 關(guān)于 XV6 的內(nèi)存頁(yè)式管理。發(fā)生中斷時(shí)，用哪個(gè)頁(yè)表？一個(gè)內(nèi)頁(yè)是多大？頁(yè)目錄有多少項(xiàng)？頁(yè)表有多少項(xiàng)？最

9、大支持多大的內(nèi)存？畫出從虛擬地址到物理地址的轉(zhuǎn)換圖。在 XV6中，是如何將虛擬地址與物理地址映射的（調(diào)用了哪些函數(shù)實(shí)現(xiàn)了哪些功能）？答：發(fā)生中斷時(shí)，用進(jìn)程的頁(yè)表；一個(gè)內(nèi)存頁(yè)為 4K；一個(gè)頁(yè)目錄有 1024 項(xiàng)；一個(gè)頁(yè)表有 220 個(gè)頁(yè)表項(xiàng)；最大支持 4G 的內(nèi)存；頁(yè)式內(nèi)存管理單元段式內(nèi)存管理單元物理地址線性地址虛擬地址物理地址通過(guò) DRAM 中的存儲(chǔ)單元實(shí)現(xiàn)，一個(gè)物理地址索引一個(gè)字節(jié)的物理內(nèi)存。上層程序使用虛擬地址，然后分段管理器和分頁(yè)管理器的工作就是將其轉(zhuǎn)換為物理地址，并將其發(fā)送到 DRAM 中進(jìn)行讀寫操作。在 XV6 中，虛擬地址和線性地址總是相同的。然后分頁(yè)管理器通過(guò)頁(yè)表完成從線性地址到

10、物理地址的映射。一個(gè)頁(yè)表中包含 220 個(gè)頁(yè)表項(xiàng)（PTE）。每個(gè)頁(yè)表項(xiàng)的結(jié)構(gòu)包括 20 位的物理頁(yè)號(hào)（PPN）和一些標(biāo)志位。在轉(zhuǎn)換時(shí)，分頁(yè)管理器以線性地址的高 20 位為索引在頁(yè)表中找到一個(gè)頁(yè)表項(xiàng)，之后用其中的物理頁(yè)號(hào)替換這 20 位，放回頁(yè)表項(xiàng)中，保留其低 12 位，從而得到其物理地址。在 XV6 中，利用利用 memlayout.h 中的 v2p()和 p2v()函數(shù)進(jìn)行虛擬地址和物理地址的相互轉(zhuǎn)換。同時(shí)利用 mappages 函數(shù)創(chuàng)建從線性地址到物理地址映射的頁(yè)表項(xiàng)；利用 walkpgdir 函數(shù)返回起始地址為 va 耳朵線性地址對(duì)應(yīng)的 PTE。static inline uint v2

11、p(void *a) return (uint) (a)- KERNBASE; static inline void *p2v(uint a) return (void *) (a) + KERNBASE); #define V2P(a) (uint) (a) - KERNBASE)#define P2V(a) (void *) (a) + KERNBASE)Mappages 函數(shù)static int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)char *a, *last; pte_t *pte;a = (cha

12、r*)PGROUNDDOWN(uint)va);last = (char*)PGROUNDDOWN(uint)va) + size - 1);for(;)if(pte = walkpgdir(pgdir, a, 1) = 0) return -1;if(*pte & PTE_P) panic(remap);*pte = pa | perm | PTE_P; if(a = last)break;a += PGSIZE; pa += PGSIZE;return 0;參數(shù) va 和 pa 分別代表虛擬地址和物理地址的起始地址，size 代表這段映射的長(zhǎng)度。計(jì)算出需要分配的虛擬地址的起始地址和最高地址

13、，然后循環(huán)每個(gè)頁(yè)頭的虛擬地址，調(diào)用walkpgdir 來(lái)得到相應(yīng)的 PTE，然后寫入對(duì)應(yīng)的權(quán)限。Walkpgdir 函數(shù)static pte_t * walkpgdir(pde_t *pgdir, const void *va, int alloc)pde_t *pde; pte_t *pgtab;pde = &pgdirPDX(va);if(*pde & PTE_P)pgtab = (pte_t*)p2v(PTE_ADDR(*pde); else if(!alloc | (pgtab = (pte_t*)kalloc() = 0) return 0;/ Make sure all those PTE_P bits are zero. memset(pgtab, 0, PGSIZE);/ The permissions here are overly generous, but they can/ be further restricted by the permissions in the page table/ entries, if