北航linux課件-LINUX存儲(chǔ)管理

1、LINUX存儲(chǔ)管理1地址空間地址空間（address space）是一段表示內(nèi)存位置的地址范圍。地址空間有兩種：物理地址空間邏輯地址空間，也被稱(chēng)為虛擬地址空間在邏輯地址和物理地址之間相互轉(zhuǎn)換的工作是由內(nèi)核和硬件內(nèi)存管理單元（MMUmemory management unit）共同完成的。MMU是被集成進(jìn)現(xiàn)代的CPU里的，它們都是同一塊CPU芯片內(nèi)的一個(gè)部分。內(nèi)核告訴MMU如何為每個(gè)進(jìn)程把某邏輯頁(yè)面映射到某特定物理頁(yè)面，而MMU在進(jìn)程提出內(nèi)存請(qǐng)求時(shí)完成實(shí)際的轉(zhuǎn)換工作。 2LINUX的虛擬地址劃分每一個(gè)用戶(hù)進(jìn)程都可以訪問(wèn)4GB的線性虛擬內(nèi)存空間。從0到3GB的虛擬內(nèi)存地址是用戶(hù)空間，用戶(hù)進(jìn)程可以直

2、接對(duì)其進(jìn)行訪問(wèn)。從3GB到4GB的虛擬內(nèi)存地址為核心態(tài)空間，存放僅供核心態(tài)訪問(wèn)的代碼和數(shù)據(jù)，用戶(hù)態(tài)進(jìn)程不可訪問(wèn)。所有進(jìn)程從3GB到4GB的虛擬空間都是一樣的，有同樣的頁(yè)目錄項(xiàng)，同樣的頁(yè)表，對(duì)應(yīng)到同樣的物理內(nèi)存段。LINUX以此方式讓內(nèi)核態(tài)進(jìn)程共享代碼段和數(shù)據(jù)段。內(nèi)核態(tài)虛擬空間從3GB到3GB+4M的一段（也就是進(jìn)程頁(yè)目錄第768項(xiàng)所管轄的范圍），被映射到物理空間0到4M段。因此，進(jìn)程處于核心態(tài)時(shí)，只要通過(guò)訪問(wèn)虛擬空間3GB到3GB+4M段，偏移地址0到4M，即訪問(wèn)了物理空間0到4M段。3虛擬地址轉(zhuǎn)換PGD PMD PTE Page Frame頁(yè)目錄索引，頁(yè)面中間目錄、頁(yè)表索引和偏移量虛擬內(nèi)存和

3、物理內(nèi)存都分為大小固定的塊，叫做頁(yè)面。每一個(gè)頁(yè)面有一個(gè)唯一的頁(yè)面號(hào)，叫做PFN(page frame number)。 4轉(zhuǎn)換后備緩存（Translation Lookaside Buffers：TLBs)如果簡(jiǎn)單的執(zhí)行從邏輯地址到物理地址的轉(zhuǎn)換過(guò)程，在跟蹤指針鏈時(shí)將會(huì)需要幾個(gè)內(nèi)存引用。RAM雖然不像磁盤(pán)那么慢，但是仍然比CPU要慢的多，這樣就容易形成性能的瓶頸。為了減少這種開(kāi)銷(xiāo)，最近被執(zhí)行過(guò)的地址轉(zhuǎn)換結(jié)果將被存儲(chǔ)在MMU的轉(zhuǎn)換后備緩存（translation lookaside buffers：TLBs）內(nèi)。虛擬地址轉(zhuǎn)換5虛存段(VMA)的組織和管理VMA:vitual memory are

4、a一個(gè)vma段是某個(gè)進(jìn)程的一段連續(xù)的虛存空間；在這段虛存里的所有單元擁有相同的特征。例如：屬于同一進(jìn)程，相同的訪問(wèn)權(quán)限，同時(shí)被鎖定（locked），同時(shí)受保護(hù)（protected），等等。進(jìn)程通常占用幾個(gè)vma段，分別用于代碼段、數(shù)據(jù)段、堆棧段等。屬于同一進(jìn)程的vma段通過(guò)vm_next指針連接，組成鏈表。對(duì)于一個(gè)給定的進(jìn)程，兩個(gè)VMAs決不會(huì)重疊，一個(gè)地址最多被一個(gè)VMA所覆蓋；進(jìn)程從未訪問(wèn)過(guò)的的一個(gè)地址將不會(huì)在任何一個(gè)VMA中。 struct mm_struct結(jié)構(gòu)的成員struct vm_area_struct * mmap 表示進(jìn)程的vma鏈表的表頭。67 當(dāng)一個(gè)進(jìn)程有多于avl_mi

5、n_map_count數(shù)目的VMA時(shí)，內(nèi)核也會(huì)創(chuàng)建一個(gè)AVL樹(shù)來(lái)存儲(chǔ)它們，此時(shí)仍然是使用VMAs自己的指針對(duì)該樹(shù)進(jìn)行管理。AVL樹(shù)是一個(gè)平衡二叉樹(shù)結(jié)構(gòu)，因此這種方法在VMA數(shù)量巨大時(shí)查找效率十分高。 虛存段(VMA)的組織和管理8AVL樹(shù)9PCB對(duì)內(nèi)存的控制Task structmm_struct_vm_area_structvm_mmpgd mm vm_operations_structvm_nextmmapvm_opspgd vm_area_structpte ptepage page frameframevm_next *open10物理空間管理物理空間的組織空閑物理內(nèi)存管理空閑內(nèi)存的組

6、織分配回收11物理空間的組織(include/linux/fs.h,struct page) 物理內(nèi)存以頁(yè)幀(page frame)為單位，頁(yè)幀的長(zhǎng)度固定，等于頁(yè)長(zhǎng)，對(duì)INTEL CPU缺省為4K字節(jié)。 LINUX對(duì)物理內(nèi)存的管理通過(guò)mem_map表描述(mm/memory.c)。 mem_map在系統(tǒng)初始化時(shí)由free_area_init()函數(shù)創(chuàng)建(mm/page_alloc.c)。 它本身是關(guān)于struct page mem_map_t (linux/mm.h)的數(shù)組，每項(xiàng)mem_map_t對(duì)應(yīng)一個(gè)關(guān)于核心態(tài)、用戶(hù)態(tài)代碼和數(shù)據(jù)等的頁(yè)幀。12mem_map在物理空間的位置0X000000(

7、0K)empty_Zero_Page 由mem_init初始化0X001000(4K) s核心態(tài)訪問(wèn)空間的頁(yè)目錄0X002000(8K) pg00X003000(12K) bad_pages0X004000(16K) bad_pg_table0X005000(20K) floppy_track_buffer0X006000(24K) kernel_code+text FREE0X0A0000(640K RESERVED0X100000(1M) pg_tables(4K) s mem_map bitmap FREE13struct page134 typedef struct page 135

8、struct list_head list;136 struct address_space *mapping; 137 unsigned long index; /* 若該頁(yè)幀的內(nèi)容是文件，則index指出文件的inode和偏移位置 */ 138 struct page *next_hash;139 atomic_t count; /* 指明目前使用該頁(yè)面的用戶(hù)數(shù)。count=0意味著此頁(yè)空閑 */140 unsigned long flags; /* atomic flags, some possibly updated asynchronously */141 struct list_h

9、ead lru;142 unsigned long age; /* 頁(yè)幀的年齡，越小越先換出 */ 143 wait_queue_head_t wait;144 struct page *pprev_hash;145 struct buffer_head * buffers; /* 若該頁(yè)幀作為緩沖區(qū)，則指示地址 */ 146 void *virtual; /* non-NULL if kmapped */147 struct zone_struct *zone;148 mem_map_t;14空閑內(nèi)存的組織15bitmap 表 在物理內(nèi)存低端，緊跟mem_map表的bitmap表以位圖方式記

10、錄了所有物理內(nèi)存的空閑狀況。 與mem_map一樣，bitmap表在系統(tǒng)初始化時(shí)由free_area_init()函數(shù)創(chuàng)建(mm/page_alloc.c)。 與一般性位圖不同的是，bitmap表分割成NR_MEM_LISTS組(缺省值6)。16bitmap 表 首先是第0組，初始化時(shí)設(shè)定了長(zhǎng)度為(end_mem-start_mem) / PAGE_SIZE/20+3,每位表示20個(gè)頁(yè)幀的空閑狀況，置位表示已被占用。 接著是第1組，初始化時(shí)設(shè)定了長(zhǎng)度為： (end_mem-start_mem) / PAGE_SIZE/21+3 ，每位表示連續(xù)21個(gè)頁(yè)幀的空閑狀況，置位表示其中1頁(yè)或2頁(yè)已被占用

11、。 類(lèi)似地，對(duì)第i組，初始化時(shí)設(shè)定了長(zhǎng)度為： (end_mem-start_mem) / PAGE_SIZE / 2i+3 ，每位表示連續(xù)2i個(gè)頁(yè)幀的空閑狀況，置位表示其中1頁(yè)或幾頁(yè)已被占用。 例如對(duì)第5組，某個(gè)bit所對(duì)應(yīng)的連續(xù)32頁(yè)幀中只要有一個(gè)被占用，此位即置1，只有當(dāng)所有32頁(yè)幀全部回收后才清0。17free_area數(shù)組 LINUX用free_area數(shù)組記錄空閑的物理頁(yè)幀。free_area數(shù)組由NR_MEM_LISTS個(gè)free_area_struct結(jié)構(gòu)類(lèi)型的數(shù)組元素構(gòu)成，每個(gè)元素均作為一條空閑塊鏈表的表頭。 struct free_area_struct struct pag

12、e *next; /* 此結(jié)構(gòu)的next,prev指針與struct page匹配 */ struct page *prev; unsigned int * map; /* 指向bitmap */ ; static struct free_area_struct free_areaNR_MEM_LISTS; 所有單個(gè)空閑頁(yè)幀組成的鏈表掛到free_area數(shù)組的第0項(xiàng)后面。連續(xù)2 i個(gè)空閑頁(yè)幀則被掛到free_area數(shù)組的第i項(xiàng)后面。18操作函數(shù)分配內(nèi)存塊由_get_free_pages()函數(shù)和宏定義_get_free_page()執(zhí)行釋放內(nèi)存塊可以調(diào)用free_pages()函數(shù)執(zhí)行。1

13、9分配算法 LINUX采用buddy算法分配空閑塊，塊長(zhǎng)可以是2i個(gè) (0= i NR_MEM_LISTS) 頁(yè)幀。 當(dāng)分配長(zhǎng)度是2i頁(yè)幀的塊時(shí)，從free_area數(shù)組的第i條鏈表開(kāi)始搜索，找不到再搜索第i+1條鏈表，以此類(lèi)推。 若找到的空閑塊長(zhǎng)正好等于需求的塊長(zhǎng)，則直接將它從free_area刪除，返回首地址。 若找到的空閑塊長(zhǎng)大于需求的塊長(zhǎng)，則將空閑塊一分為二，前半部分插入free_area中前一條鏈表，取后半部分。 若還大，則繼續(xù)對(duì)半分，留一半取一半，直至相等。 bitmap表也相應(yīng)調(diào)整。每分配一個(gè)2i頁(yè)幀長(zhǎng)的塊，都要將bitmap表從第i組到第NR_MEM_LISTS組的對(duì)應(yīng)的bit

14、置1。20釋放算法 回收空閑塊時(shí)，change_bit()函數(shù)根據(jù)bitmap表的對(duì)應(yīng)組，判斷回收塊的前后鄰居是否也為空。 若空則合并，即修改bitmap表中對(duì)應(yīng)位，從free_area的空閑鏈表中取下該相鄰塊。 此判斷是個(gè)遞歸過(guò)程，直至找不到空閑鄰居為止。 將最后合并的最大塊插入free_area的相應(yīng)鏈表中。21交換空間兩種交換空間：一種用整個(gè)塊設(shè)備，如硬盤(pán)的一個(gè)分區(qū)，稱(chēng)作交換設(shè)備，效率較高；另一種用文件系統(tǒng)中固定長(zhǎng)度的文件，稱(chēng)作交換文件，效率較低。LINUX允許并行管理MAX_S個(gè)交換空間（MAX_S的缺省值為8）。22交換空間的格式前4096字節(jié)是一個(gè)以字符串 “S”結(jié)尾的位圖。位圖的

15、每一位（bit）對(duì)應(yīng)一個(gè)交換空間的頁(yè)面，置位表示對(duì)應(yīng)的頁(yè)面可用于換頁(yè)操作。第4096字節(jié)之后則是真正存放換出頁(yè)面的空間。這樣，每個(gè)交換空間最多可容納 （4096-10）* 8 1 = 32687個(gè)頁(yè)面。23啟用交換空間 int sys_swapon(const char * s, int s);第一個(gè)參數(shù)s是設(shè)備名或文件名，s規(guī)定交換空間的優(yōu)先數(shù)。該參數(shù)中，S（0X8000）必須置位，S(0X7FFF)指定一個(gè)正的優(yōu)先數(shù)。如果沒(méi)有指定優(yōu)先數(shù)，swapon自動(dòng)給出一個(gè)負(fù)的優(yōu)先數(shù)，負(fù)優(yōu)先數(shù)的取值決定于swapon的調(diào)用次數(shù)。24每注冊(cè)一個(gè)交換空間，就在s表中填一項(xiàng)s結(jié)構(gòu) 25 struct s s

16、MAX_S; 49 struct s 50 unsigned int flags; /* 如果SWP_USED位置位，則被占用。如果SWP_WRITEOK，則該交換空間準(zhǔn)備就緒。 */ 51 kdev_t s; /* 對(duì)于交換設(shè)備，s屬性表示交換設(shè)備的主、次設(shè)備號(hào) */ 52 spinlock_t sdev_lock; /* 對(duì)于此設(shè)備的互斥鎖 */ 53 struct dentry * s; /* 對(duì)于交換文件，s屬性指向該文件的inode */ 54 struct vfsmount *s; 55 unsigned short * s* 指向一張表，其每一字節(jié)按順序?qū)?yīng)交換空間的一個(gè)頁(yè)面，字

17、節(jié)的值代表了引用該頁(yè)面的進(jìn)程數(shù) */ 56 unsigned int lowest_bit; /*交換空間中的第一個(gè)沒(méi)有被任何進(jìn)程使用的交換頁(yè)在s數(shù)組中的下標(biāo) */ 57 unsigned int highest_bit; /* 交換空間中最后一個(gè)沒(méi)被任何進(jìn)程使用的交換頁(yè)的下標(biāo) */ 58 unsigned int cluster_next; /*上次從當(dāng)前的cluster中成功分配的交換頁(yè)面的后繼頁(yè)面在s數(shù)組中的下標(biāo) */ 59 unsigned int cluster_nr; /* 當(dāng)前cluster中可供使用的交換頁(yè)面的個(gè)數(shù) */ 60 int prio; /*交換空間的優(yōu)先級(jí)。優(yōu)先級(jí)越

18、高，交換文件申請(qǐng)交換頁(yè)面的時(shí)候越優(yōu)先考慮 */ 61 int pages; /* 表示該交換空間尚有多少空閑空間可供保存進(jìn)程換出的物理頁(yè) */ 62 unsigned long max; 63 int next; /*指向下一項(xiàng)交換空間的的指針 */ 64 ;153 struct s 154 int head; /* head of priority-ordered s list */155 int next; /* s to be used next */156 ;23 struct s s = -1, -1;25注銷(xiāo)交換空間int sys_s(const char * s);26交換空間的

19、工作 kswapd進(jìn)程換出頁(yè)面時(shí)，調(diào)用try_to_s() 測(cè)試頁(yè)面的年齡。如果某物理頁(yè)面可以換出，則調(diào)用get_s向s指示的交換空間申請(qǐng)空閑頁(yè)面，得到一地址entry。該地址寫(xiě)入進(jìn)程頁(yè)表中那個(gè)原來(lái)描述換出物理頁(yè)面的頁(yè)表項(xiàng)，替換了其中的頁(yè)幀地址。最后，調(diào)用rw_s(),將換出的物理頁(yè)面寫(xiě)到entry指定的交換空間某個(gè)頁(yè)面中。 反過(guò)來(lái)，當(dāng)缺頁(yè)中斷發(fā)生時(shí)，缺頁(yè)中斷服務(wù)程序可以根據(jù)產(chǎn)生缺頁(yè)的地址（由CR2寄存器給出），找到描述該頁(yè)面的頁(yè)表項(xiàng)。頁(yè)表項(xiàng)的Present位應(yīng)該為0，最高20位指出該頁(yè)面保存在哪個(gè)交換空間的哪個(gè)頁(yè)面中。然后，經(jīng)一系列函數(shù)調(diào)用后，讀入該頁(yè)面。27kswapd當(dāng)物理頁(yè)面不夠時(shí)，利

20、用kswapd釋放部分物理頁(yè)面，將它們的內(nèi)容寫(xiě)到交換空間。kswapd是一特殊的進(jìn)程，稱(chēng)內(nèi)核態(tài)線程（kernel thread）。注意，kernel thread完全不同于通常意義上的線程。它是沒(méi)有虛擬存儲(chǔ)空間的進(jìn)程，它只運(yùn)行在內(nèi)核態(tài)，直接使用物理地址空間。同類(lèi)型的進(jìn)程還有bdflush和init。kswapd的作用超越了字面上的描述。它不僅能將頁(yè)面換出到交換空間（交換區(qū)或交換文件），它也保證系統(tǒng)中有足夠的空閑頁(yè)面以保持存儲(chǔ)系統(tǒng)高效地運(yùn)行。28請(qǐng)求調(diào)頁(yè)一旦一個(gè)可執(zhí)行鏡像映射到了一個(gè)進(jìn)程的虛擬內(nèi)存中，它就可以開(kāi)始執(zhí)行了。因?yàn)殚_(kāi)始時(shí)只有鏡像開(kāi)頭的一小部分裝入到了系統(tǒng)的物理內(nèi)存中，所以不久進(jìn)程就會(huì)存

21、取一些不在物理內(nèi)存中的虛擬內(nèi)存頁(yè)，這時(shí)處理器會(huì)通知L i n u x發(fā)生了頁(yè)面錯(cuò)誤。頁(yè)面錯(cuò)誤將會(huì)描述頁(yè)面錯(cuò)誤發(fā)生時(shí)的虛擬內(nèi)存地址和存取內(nèi)存操作的類(lèi)型。29產(chǎn)生缺頁(yè)中斷當(dāng)一個(gè)進(jìn)程訪問(wèn)了一個(gè)還沒(méi)有有效頁(yè)表項(xiàng)的虛擬地址時(shí)（即頁(yè)表項(xiàng)的P位為0），處理器將產(chǎn)生缺頁(yè)中斷，通知操作系統(tǒng)，并將出現(xiàn)缺頁(yè)的虛存地址（在CR2寄存器中）和缺頁(yè)時(shí)訪問(wèn)虛存的模式一并傳遞給LINUX的缺頁(yè)中斷服務(wù)程序。30缺頁(yè)中斷服務(wù)程序?yàn)閐o_page_fault()set_trap_gate(14, &page_fault); /* arch/i386/kernel/trap.c */ENTRY(page_fault) /* arc

22、h/i386/kernel/entry.S */ pushl $SYMBOL_NAME(do_page_fault) jmp error_code /* 異常中斷服務(wù)程序的統(tǒng)一入口 */31中斷服務(wù)流程根據(jù)控制寄存器CR2傳遞的缺頁(yè)地址，找到用來(lái)表示出現(xiàn)缺頁(yè)的虛擬存儲(chǔ)區(qū)的vm_area_struct結(jié)構(gòu)。如果沒(méi)有找到與缺頁(yè)相對(duì)應(yīng)的vm_area_struct結(jié)構(gòu)，那么說(shuō)明進(jìn)程訪問(wèn)了一個(gè)非法存儲(chǔ)區(qū)，LINUX向進(jìn)程發(fā)送信號(hào)SIGSEGV。接著檢測(cè)缺頁(yè)時(shí)訪問(wèn)模式是否合法。如果進(jìn)程對(duì)該頁(yè)的訪問(wèn)超越權(quán)限，例如試圖對(duì)只允許讀操作的頁(yè)面進(jìn)行寫(xiě)操作，系統(tǒng)也將向該進(jìn)程發(fā)送一個(gè)信號(hào)，通知進(jìn)程的存儲(chǔ)訪問(wèn)出錯(cuò)。如果

23、Linux認(rèn)為此頁(yè)面錯(cuò)誤是合法的，它將處理此頁(yè)面錯(cuò)誤。Linux還必須區(qū)分頁(yè)面是在交換文件中還是作為文件鏡像的一部分存在于磁盤(pán)中。它靠檢查出錯(cuò)頁(yè)面的頁(yè)面表來(lái)區(qū)分：如果頁(yè)面表的入口是無(wú)效的，但非空，說(shuō)明頁(yè)面在交換文件中。最后，Linux調(diào)入所需的頁(yè)面并更新進(jìn)程的頁(yè)面表。32頁(yè)面置換當(dāng)一個(gè)進(jìn)程需要把一個(gè)虛擬內(nèi)存頁(yè)面裝入到物理內(nèi)存而又沒(méi)有空閑的物理內(nèi)存時(shí)，操作系統(tǒng)必須將一個(gè)現(xiàn)在不用的頁(yè)面從物理內(nèi)存中扔掉以便為將要裝入的虛擬內(nèi)存頁(yè)騰出空間。選擇換出頁(yè)對(duì)換出頁(yè)的處理33檢查是否存在可以從緩沖區(qū)中回收的塊若無(wú)，試圖回收共享內(nèi)存保留的頁(yè)框若無(wú)，用近似的LRU(全局的最近最少使用）替代算法找到換出頁(yè)。頁(yè)面置換34頁(yè)面換出如果將要扔掉的物理內(nèi)存頁(yè)一直沒(méi)有被改寫(xiě)過(guò)，則操作系統(tǒng)將不保存此內(nèi)存頁(yè)，而只是簡(jiǎn)單地將它扔掉。如果再需要此內(nèi)存頁(yè)時(shí)，再?gòu)奈募R像中裝入。但是，如果此頁(yè)面已經(jīng)被修改過(guò)，操作系統(tǒng)就需要把頁(yè)面的內(nèi)容保存