linux存儲(chǔ)管理

1、LINUX存儲(chǔ)管理,,地址空間,地址空間（address space）是一段表示內(nèi)存位置的地址范圍。地址空間有兩種：物理地址空間邏輯地址空間，也被稱為虛擬地址空間在邏輯地址和物理地址之間相互轉(zhuǎn)換的工作是由內(nèi)核和硬件內(nèi)存管理單元（MMU—memory management unit）共同完成的。MMU是被集成進(jìn)現(xiàn)代的CPU里的，它們都是同一塊CPU芯片內(nèi)的一個(gè)部分。內(nèi)核告訴MMU如何為每個(gè)進(jìn)程把某邏輯頁(yè)面映射到某特定物理頁(yè)面，而MM

2、U在進(jìn)程提出內(nèi)存請(qǐng)求時(shí)完成實(shí)際的轉(zhuǎn)換工作。,LINUX的虛擬地址劃分,每一個(gè)用戶進(jìn)程都可以訪問(wèn)4GB的線性虛擬內(nèi)存空間。從0到3GB的虛擬內(nèi)存地址是用戶空間，用戶進(jìn)程可以直接對(duì)其進(jìn)行訪問(wèn)。從3GB到4GB的虛擬內(nèi)存地址為核心態(tài)空間，存放僅供核心態(tài)訪問(wèn)的代碼和數(shù)據(jù)，用戶態(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ù)段。

3、內(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段。,虛擬地址轉(zhuǎn)換,,,PGD PMD PTE Page Frame,,,,,,,,,,,,,,,,,,,,,,,,,,,,,頁(yè)目錄索引，頁(yè)面中

4、間目錄、頁(yè)表索引和偏移量虛擬內(nèi)存和物理內(nèi)存都分為大小固定的塊，叫做頁(yè)面。每一個(gè)頁(yè)面有一個(gè)唯一的頁(yè)面號(hào)，叫做PFN(page frame number)。,轉(zhuǎn)換后備緩存（Translation Lookaside Buffers：TLBs)如果簡(jiǎn)單的執(zhí)行從邏輯地址到物理地址的轉(zhuǎn)換過(guò)程，在跟蹤指針鏈時(shí)將會(huì)需要幾個(gè)內(nèi)存引用。RAM雖然不像磁盤那么慢，但是仍然比CPU要慢的多，這樣就容易形成性能的瓶頸。為了減少這種開(kāi)銷，最近被執(zhí)行過(guò)的地址轉(zhuǎn)

5、換結(jié)果將被存儲(chǔ)在MMU的轉(zhuǎn)換后備緩存（translation lookaside buffers：TLBs）內(nèi)。,虛擬地址轉(zhuǎn)換,虛存段(VMA)的組織和管理,VMA:vitual memory area一個(gè)vma段是某個(gè)進(jìn)程的一段連續(xù)的虛存空間；在這段虛存里的所有單元擁有相同的特征。例如：屬于同一進(jìn)程，相同的訪問(wèn)權(quán)限，同時(shí)被鎖定（locked），同時(shí)受保護(hù)（protected），等等。進(jìn)程通常占用幾個(gè)vma段，分別用于代碼段、數(shù)據(jù)段

6、、堆棧段等。屬于同一進(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鏈表的表頭。,,當(dāng)一個(gè)進(jìn)程有多于avl_min_map_count數(shù)目的VMA時(shí)，內(nèi)核也會(huì)創(chuàng)建一個(gè)AVL樹來(lái)存儲(chǔ)它們

7、，此時(shí)仍然是使用VMAs自己的指針對(duì)該樹進(jìn)行管理。AVL樹是一個(gè)平衡二叉樹結(jié)構(gòu)，因此這種方法在VMA數(shù)量巨大時(shí)查找效率十分高。,虛存段(VMA)的組織和管理,AVL樹,PCB對(duì)內(nèi)存的控制,,,Task struct,mm_struct,_,vm_area_struct,,vm_mm,,,pgd,,,mm,vm_operations_struct,,vm_next,,,mmap,,,,,,vm_ops,,,pgd,,,vm_area_st

8、ruct,,pte pte,,,,,,,,,page page,,,frame,,,frame,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,vm_next,*open,物理空間管理,物理空間的組織空閑物理內(nèi)存管理空閑內(nèi)存的組織分配回收,物理空間的組織(include/linux/fs.h,str

9、uct 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

10、/mm.h)的數(shù)組，每項(xiàng)mem_map_t對(duì)應(yīng)一個(gè)關(guān)于核心態(tài)、用戶態(tài)代碼和數(shù)據(jù)等的頁(yè)幀。,mem_map在物理空間的位置,struct page,134 typedef struct page {135 struct list_head list;136 struct address_space *mapping; 137 unsigned long index; /* 若

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

12、ronously */141 struct list_head lru;142 unsigned long age; /* 頁(yè)幀的年齡，越小越先換出 */ 143 wait_queue_head_t wait;144 struct page **pprev_hash;145 struct buffer_head * buffers;

13、 /* 若該頁(yè)幀作為緩沖區(qū)，則指示地址 */ 146 void *virtual; /* non-NULL if kmapped */147 struct zone_struct *zone;148 } mem_map_t;,空閑內(nèi)存的組織,bitmap 表,在物理內(nèi)存低端，緊跟mem_map表的bitmap表以位圖方式記錄了所有物理內(nèi)存的空閑狀況。 與mem_map一樣，bitm

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

15、 (end_mem-start_mem) / PAGE_SIZE/21+3 ，每位表示連續(xù)21個(gè)頁(yè)幀的空閑狀況，置位表示其中1頁(yè)或2頁(yè)已被占用。 類似地，對(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è)幀中只

16、要有一個(gè)被占用，此位即置1，只有當(dāng)所有32頁(yè)幀全部回收后才清0。,free_area數(shù)組,LINUX用free_area數(shù)組記錄空閑的物理頁(yè)幀。free_area數(shù)組由NR_MEM_LISTS個(gè)free_area_struct結(jié)構(gòu)類型的數(shù)組元素構(gòu)成，每個(gè)元素均作為一條空閑塊鏈表的表頭。 struct free_area_struct { struct page *next;

17、 /* 此結(jié)構(gòu)的next,prev指針與struct page匹配 */ struct page *prev; unsigned int * map; /* 指向bitmap */ }; static struct free_area_struct free_area[NR_MEM_LISTS]; 所有單個(gè)空閑頁(yè)幀組成的鏈表

18、掛到free_area數(shù)組的第0項(xiàng)后面。連續(xù)2 i個(gè)空閑頁(yè)幀則被掛到free_area數(shù)組的第i項(xiàng)后面。,操作函數(shù),分配內(nèi)存塊由__get_free_pages()函數(shù)和宏定義__get_free_page()執(zhí)行釋放內(nèi)存塊可以調(diào)用free_pages()函數(shù)執(zhí)行。,分配算法,LINUX采用buddy算法分配空閑塊，塊長(zhǎng)可以是2i個(gè) (0<= i< NR_MEM_LISTS) 頁(yè)幀。 當(dāng)分配長(zhǎng)度是2i頁(yè)幀

19、的塊時(shí)，從free_area數(shù)組的第i條鏈表開(kāi)始搜索，找不到再搜索第i+1條鏈表，以此類推。 若找到的空閑塊長(zhǎng)正好等于需求的塊長(zhǎng)，則直接將它從free_area刪除，返回首地址。 若找到的空閑塊長(zhǎng)大于需求的塊長(zhǎng)，則將空閑塊一分為二，前半部分插入free_area中前一條鏈表，取后半部分。 若還大，則繼續(xù)對(duì)半分，留一半取一半，直至相等。 bitmap表也

20、相應(yīng)調(diào)整。每分配一個(gè)2i頁(yè)幀長(zhǎng)的塊，都要將bitmap表從第i組到第NR_MEM_LISTS組的對(duì)應(yīng)的bit置1。,釋放算法,回收空閑塊時(shí)，change_bit()函數(shù)根據(jù)bitmap表的對(duì)應(yīng)組，判斷回收塊的前后鄰居是否也為空。 若空則合并，即修改bitmap表中對(duì)應(yīng)位，從free_area的空閑鏈表中取下該相鄰塊。 此判斷是個(gè)遞歸過(guò)程，直至找不到空閑鄰居為止。 將

21、最后合并的最大塊插入free_area的相應(yīng)鏈表中。,交換空間,兩種交換空間：一種用整個(gè)塊設(shè)備，如硬盤的一個(gè)分區(qū)，稱作交換設(shè)備，效率較高；另一種用文件系統(tǒng)中固定長(zhǎng)度的文件，稱作交換文件，效率較低。LINUX允許并行管理MAX_SWAPFILES個(gè)交換空間（MAX_SWAPFILES的缺省值為8）。,交換空間的格式,前4096字節(jié)是一個(gè)以字符串 “SWAP_SPACE”結(jié)尾的位圖。位圖的每一位（bit）對(duì)應(yīng)一個(gè)交換空間的頁(yè)面，置

22、位表示對(duì)應(yīng)的頁(yè)面可用于換頁(yè)操作。第4096字節(jié)之后則是真正存放換出頁(yè)面的空間。這樣，每個(gè)交換空間最多可容納 （4096-10）* 8 – 1 = 32687個(gè)頁(yè)面。,啟用交換空間,int sys_swapon(const char * swapfile, int swapflags);第一個(gè)參數(shù)swapfile是設(shè)備名或文件名，swapflags規(guī)定交換空間的優(yōu)先數(shù)。該參數(shù)中，SWAP_FLAG_PREFER（0X8000

23、）必須置位，SWAP_FLAG_PRIO_MASK(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ù)。,每注冊(cè)一個(gè)交換空間，就在swap_info表中填一項(xiàng)swap_info_struct結(jié)構(gòu),25 struct swap_info_struct swap_info[MAX_SWAPFILES]; 49 struct swap_info_struct

24、{ 50 unsigned int flags; /* 如果SWP_USED位置位，則被占用。如果SWP_WRITEOK，則該交換空間準(zhǔn)備就緒。 */ 51 kdev_t swap_device; /* 對(duì)于交換設(shè)備，swap_device屬性表示交換設(shè)備的主、次設(shè)備號(hào) */ 52 spinlock_t sdev_lock; /* 對(duì)于此設(shè)備的互斥鎖 */ 53

25、 struct dentry * swap_file; /* 對(duì)于交換文件，swap_file屬性指向該文件的inode */ 54 struct vfsmount *swap_vfsmnt; 55 unsigned short * swap_map;/* 指向一張表，其每一字節(jié)按順序?qū)?yīng)交換空間的一個(gè)頁(yè)面，字節(jié)的值代表了引用該頁(yè)面的進(jìn)程數(shù) */ 56 unsigned in

26、t lowest_bit; /*交換空間中的第一個(gè)沒(méi)有被任何進(jìn)程使用的交換頁(yè)在swap_map數(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è)面在swap_map數(shù)組中的下標(biāo) */ 5

27、9 unsigned int cluster_nr; /* 當(dāng)前cluster中可供使用的交換頁(yè)面的個(gè)數(shù) */ 60 int prio; /*交換空間的優(yōu)先級(jí)。優(yōu)先級(jí)越高，交換文件申請(qǐng)交換頁(yè)面的時(shí)候越優(yōu)先考慮 */ 61 int pages; /* 表示該交換空間尚有多少空閑空間可供保存進(jìn)程換出的物理頁(yè) */ 62

28、 unsigned long max; 63 int next; /*指向下一項(xiàng)交換空間的的指針 */ 64 };153 struct swap_list_t {154 int head; /* head of priority-ordered swapfile list */155 int next; /* s

29、wapfile to be used next */156 };23 struct swap_list_t swap_list = {-1, -1};,注銷交換空間,int sys_swapoff(const char * swapfile);,交換空間的工作,kswapd進(jìn)程換出頁(yè)面時(shí)，調(diào)用try_to_swap_out() 測(cè)試頁(yè)面的年齡。如果某物理頁(yè)面可以換出，則調(diào)用get_swap_page向swap_list.next指示

30、的交換空間申請(qǐng)空閑頁(yè)面，得到一地址entry。該地址寫入進(jìn)程頁(yè)表中那個(gè)原來(lái)描述換出物理頁(yè)面的頁(yè)表項(xiàng)，替換了其中的頁(yè)幀地址。最后，調(diào)用rw_swap_page(),將換出的物理頁(yè)面寫到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è)面中。

31、然后，經(jīng)一系列函數(shù)調(diào)用后，讀入該頁(yè)面。,kswapd,當(dāng)物理頁(yè)面不夠時(shí)，利用kswapd釋放部分物理頁(yè)面，將它們的內(nèi)容寫到交換空間。kswapd是一特殊的進(jìn)程，稱內(nèi)核態(tài)線程（kernel thread）。注意，kernel thread完全不同于通常意義上的線程。它是沒(méi)有虛擬存儲(chǔ)空間的進(jìn)程，它只運(yùn)行在內(nèi)核態(tài)，直接使用物理地址空間。同類型的進(jìn)程還有bdflush和init。kswapd的作用超越了字面上的描述。它不僅能將頁(yè)面換出到交

32、換空間（交換區(qū)或交換文件），它也保證系統(tǒng)中有足夠的空閑頁(yè)面以保持存儲(chǔ)系統(tǒng)高效地運(yùn)行。,請(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ì)存取一些不在物理內(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)存操作的類型。,產(chǎn)生缺頁(yè)中斷,當(dāng)一個(gè)進(jìn)程訪問(wèn)了一個(gè)還沒(méi)有有效頁(yè)表

33、項(xiàng)的虛擬地址時(shí)（即頁(yè)表項(xiàng)的P位為0），處理器將產(chǎn)生缺頁(yè)中斷，通知操作系統(tǒng)，并將出現(xiàn)缺頁(yè)的虛存地址（在CR2寄存器中）和缺頁(yè)時(shí)訪問(wèn)虛存的模式一并傳遞給LINUX的缺頁(yè)中斷服務(wù)程序。,缺頁(yè)中斷服務(wù)程序?yàn)閐o_page_fault(),set_trap_gate(14, &page_fault); /* arch/i386/kernel/trap.c */ENTRY(page_fault) /* arch/i38

34、6/kernel/entry.S */ pushl $SYMBOL_NAME(do_page_fault) jmp error_code /* 異常中斷服務(wù)程序的統(tǒng)一入口 */,中斷服務(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)SIG

35、SEGV。接著檢測(cè)缺頁(yè)時(shí)訪問(wèn)模式是否合法。如果進(jìn)程對(duì)該頁(yè)的訪問(wèn)超越權(quán)限，例如試圖對(duì)只允許讀操作的頁(yè)面進(jìn)行寫操作，系統(tǒng)也將向該進(jìn)程發(fā)送一個(gè)信號(hào)，通知進(jìn)程的存儲(chǔ)訪問(wèn)出錯(cuò)。如果Linux認(rèn)為此頁(yè)面錯(cuò)誤是合法的，它將處理此頁(yè)面錯(cuò)誤。Linux還必須區(qū)分頁(yè)面是在交換文件中還是作為文件鏡像的一部分存在于磁盤中。它靠檢查出錯(cuò)頁(yè)面的頁(yè)面表來(lái)區(qū)分：如果頁(yè)面表的入口是無(wú)效的，但非空，說(shuō)明頁(yè)面在交換文件中。最后，Linux調(diào)入所需的頁(yè)面并更新進(jìn)程的頁(yè)

36、面表。,頁(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è)的處理,檢查是否存在可以從緩沖區(qū)中回收的塊若無(wú)，試圖回收共享內(nèi)存保留的頁(yè)框若無(wú)，用近似的LRU(全局的最近最少使用）替代算法找到換出頁(yè)。,頁(yè)面置換,頁(yè)面換出,如果將要扔掉的物理內(nèi)存頁(yè)一直沒(méi)有被改寫過(guò)，則操作系統(tǒng)將不保存此內(nèi)存頁(yè)，而只是簡(jiǎn)單地

37、將它扔掉。如果再需要此內(nèi)存頁(yè)時(shí)，再?gòu)奈募R像中裝入。但是，如果此頁(yè)面已經(jīng)被修改過(guò)，操作系統(tǒng)就需要把頁(yè)面的內(nèi)容保存起來(lái)。這些頁(yè)面稱為“臟頁(yè)面”（dirty page）。當(dāng)它們從內(nèi)存中移走時(shí)，將會(huì)被保存到一個(gè)特殊的交換文件中。,內(nèi)存管理中的高速緩存,硬件高速緩存：一個(gè)常用的硬件高速緩存是在處理器中，它一般保存著頁(yè)表的入口。（TLB)頁(yè)面高速緩存:它的作用是加快對(duì)磁盤中的文件的存取交換高速緩存：它只保存那些被修改過(guò)的頁(yè)面。只要在頁(yè)面被寫

38、入到交換文件中后沒(méi)有被修改過(guò)，那么此頁(yè)面下一次從內(nèi)存中交換出來(lái)時(shí)就不用再寫入到交換文件中了，因?yàn)榻粨Q文件中已經(jīng)有了該頁(yè)面。這樣，該頁(yè)面就可以簡(jiǎn)單地扔掉，節(jié)省了大量的系統(tǒng)操作。緩沖區(qū)高速緩存,頁(yè)面高速緩存,對(duì)于已經(jīng)作好了磁盤映射的文件，L i n u x每次讀取一頁(yè)，并將讀取的頁(yè)面存儲(chǔ)到頁(yè)面高速緩存中。頁(yè)面高速緩存由page_hash_table組成，page_hash_table 是一個(gè)包含指向mem_map_t結(jié)構(gòu)指針的數(shù)組。每

39、當(dāng)從一個(gè)內(nèi)存映射文件中讀取一個(gè)頁(yè)面時(shí)，頁(yè)面都要從頁(yè)面高速緩存中讀取。如果頁(yè)面在高速緩存中，則將一個(gè)指向mem_map_t的指針?lè)祷亟o頁(yè)面錯(cuò)誤處理程序。否則，頁(yè)面必須從磁盤上讀入到內(nèi)存中。如果可能，L i n u x系統(tǒng)將會(huì)提前讀取文件中的下一個(gè)頁(yè)面，這樣，如果文件是順序執(zhí)行的，那么下一個(gè)頁(yè)面就已經(jīng)在內(nèi)存中了。隨著文件的讀入和執(zhí)行，頁(yè)面高速緩存也將變得越來(lái)越大。不用的頁(yè)面將被移出高速緩存。,,緩沖區(qū)高速緩存,緩沖區(qū)高速緩存中包含了用于塊