linux存儲管理

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

2、U在進(jìn)程提出內(nèi)存請求時完成實際的轉(zhuǎn)換工作。,LINUX的虛擬地址劃分,每一個用戶進(jìn)程都可以訪問4GB的線性虛擬內(nèi)存空間。從0到3GB的虛擬內(nèi)存地址是用戶空間，用戶進(jìn)程可以直接對其進(jìn)行訪問。從3GB到4GB的虛擬內(nèi)存地址為核心態(tài)空間，存放僅供核心態(tài)訪問的代碼和數(shù)據(jù)，用戶態(tài)進(jìn)程不可訪問。所有進(jìn)程從3GB到4GB的虛擬空間都是一樣的，有同樣的頁目錄項，同樣的頁表，對應(yīng)到同樣的物理內(nèi)存段。LINUX以此方式讓內(nèi)核態(tài)進(jìn)程共享代碼段和數(shù)據(jù)段。

3、內(nèi)核態(tài)虛擬空間從3GB到3GB+4M的一段（也就是進(jìn)程頁目錄第768項所管轄的范圍），被映射到物理空間0到4M段。因此，進(jìn)程處于核心態(tài)時，只要通過訪問虛擬空間3GB到3GB+4M段，偏移地址0到4M，即訪問了物理空間0到4M段。,虛擬地址轉(zhuǎn)換,,,PGD PMD PTE Page Frame,,,,,,,,,,,,,,,,,,,,,,,,,,,,,頁目錄索引，頁面中

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

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

6、、堆棧段等。屬于同一進(jìn)程的vma段通過vm_next指針連接，組成鏈表。對于一個給定的進(jìn)程，兩個VMAs決不會重疊，一個地址最多被一個VMA所覆蓋；進(jìn)程從未訪問過的的一個地址將不會在任何一個VMA中。 struct mm_struct結(jié)構(gòu)的成員struct vm_area_struct * mmap 表示進(jìn)程的vma鏈表的表頭。,,當(dāng)一個進(jìn)程有多于avl_min_map_count數(shù)目的VMA時，內(nèi)核也會創(chuàng)建一個AVL樹來存儲它們

7、，此時仍然是使用VMAs自己的指針對該樹進(jìn)行管理。AVL樹是一個平衡二叉樹結(jié)構(gòu)，因此這種方法在VMA數(shù)量巨大時查找效率十分高。,虛存段(VMA)的組織和管理,AVL樹,PCB對內(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)存以頁幀(page frame)為單位，頁幀的長度固定，等于頁長，對INTEL CPU缺省為4K字節(jié)。 LINUX對物理內(nèi)存的管理通過mem_map表描述(mm/memory.c)。 mem_map在系統(tǒng)初始化時由free_area_init()函數(shù)創(chuàng)建(mm/page_alloc.c)。 它本身是關(guān)于struct page mem_map_t (linux

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

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

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

13、 /* 若該頁幀作為緩沖區(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)初始化時由free_area_init()函數(shù)創(chuàng)建(mm/page_alloc.c)。 與一般性位圖不同的是，bitmap表分割成NR_MEM_LISTS組(缺省值6)。,bitmap 表,首先是第0組，初始化時設(shè)定了長度為(end_mem-start_mem) / PAGE_SIZE/20+3,每位表示20個頁幀的空閑狀況，置位表示已被占用。 接著是第1組，初始化時設(shè)定了長度為：

15、 (end_mem-start_mem) / PAGE_SIZE/21+3 ，每位表示連續(xù)21個頁幀的空閑狀況，置位表示其中1頁或2頁已被占用。 類似地，對第i組，初始化時設(shè)定了長度為： (end_mem-start_mem) / PAGE_SIZE / 2i+3 ，每位表示連續(xù)2i個頁幀的空閑狀況，置位表示其中1頁或幾頁已被占用。 例如對第5組，某個bit所對應(yīng)的連續(xù)32頁幀中只

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

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

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

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

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

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

23、）必須置位，SWAP_FLAG_PRIO_MASK(0X7FFF)指定一個正的優(yōu)先數(shù)。如果沒有指定優(yōu)先數(shù)，swapon自動給出一個負(fù)的優(yōu)先數(shù)，負(fù)優(yōu)先數(shù)的取值決定于swapon的調(diào)用次數(shù)。,每注冊一個交換空間，就在swap_info表中填一項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; /* 對于交換設(shè)備，swap_device屬性表示交換設(shè)備的主、次設(shè)備號 */ 52 spinlock_t sdev_lock; /* 對于此設(shè)備的互斥鎖 */ 53

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

26、t lowest_bit; /*交換空間中的第一個沒有被任何進(jìn)程使用的交換頁在swap_map數(shù)組中的下標(biāo) */ 57 unsigned int highest_bit; /* 交換空間中最后一個沒被任何進(jìn)程使用的交換頁的下標(biāo) */ 58 unsigned int cluster_next; /*上次從當(dāng)前的cluster中成功分配的交換頁面的后繼頁面在swap_map數(shù)組中的下標(biāo) */ 5

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

28、 unsigned long max; 63 int next; /*指向下一項交換空間的的指針 */ 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)程換出頁面時，調(diào)用try_to_swap_out() 測試頁面的年齡。如果某物理頁面可以換出，則調(diào)用get_swap_page向swap_list.next指示

30、的交換空間申請空閑頁面，得到一地址entry。該地址寫入進(jìn)程頁表中那個原來描述換出物理頁面的頁表項，替換了其中的頁幀地址。最后，調(diào)用rw_swap_page(),將換出的物理頁面寫到entry指定的交換空間某個頁面中。 反過來，當(dāng)缺頁中斷發(fā)生時，缺頁中斷服務(wù)程序可以根據(jù)產(chǎn)生缺頁的地址（由CR2寄存器給出），找到描述該頁面的頁表項。頁表項的Present位應(yīng)該為0，最高20位指出該頁面保存在哪個交換空間的哪個頁面中。

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

32、換空間（交換區(qū)或交換文件），它也保證系統(tǒng)中有足夠的空閑頁面以保持存儲系統(tǒng)高效地運行。,請求調(diào)頁,一旦一個可執(zhí)行鏡像映射到了一個進(jìn)程的虛擬內(nèi)存中，它就可以開始執(zhí)行了。因為開始時只有鏡像開頭的一小部分裝入到了系統(tǒng)的物理內(nèi)存中，所以不久進(jìn)程就會存取一些不在物理內(nèi)存中的虛擬內(nèi)存頁，這時處理器會通知L i n u x發(fā)生了頁面錯誤。頁面錯誤將會描述頁面錯誤發(fā)生時的虛擬內(nèi)存地址和存取內(nèi)存操作的類型。,產(chǎn)生缺頁中斷,當(dāng)一個進(jìn)程訪問了一個還沒有有效頁表

33、項的虛擬地址時（即頁表項的P位為0），處理器將產(chǎn)生缺頁中斷，通知操作系統(tǒng)，并將出現(xiàn)缺頁的虛存地址（在CR2寄存器中）和缺頁時訪問虛存的模式一并傳遞給LINUX的缺頁中斷服務(wù)程序。,缺頁中斷服務(wù)程序為do_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傳遞的缺頁地址，找到用來表示出現(xiàn)缺頁的虛擬存儲區(qū)的vm_area_struct結(jié)構(gòu)。如果沒有找到與缺頁相對應(yīng)的vm_area_struct結(jié)構(gòu)，那么說明進(jìn)程訪問了一個非法存儲區(qū)，LINUX向進(jìn)程發(fā)送信號SIG

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

36、面表。,頁面置換,當(dāng)一個進(jìn)程需要把一個虛擬內(nèi)存頁面裝入到物理內(nèi)存而又沒有空閑的物理內(nèi)存時，操作系統(tǒng)必須將一個現(xiàn)在不用的頁面從物理內(nèi)存中扔掉以便為將要裝入的虛擬內(nèi)存頁騰出空間。選擇換出頁對換出頁的處理,檢查是否存在可以從緩沖區(qū)中回收的塊若無，試圖回收共享內(nèi)存保留的頁框若無，用近似的LRU(全局的最近最少使用）替代算法找到換出頁。,頁面置換,頁面換出,如果將要扔掉的物理內(nèi)存頁一直沒有被改寫過，則操作系統(tǒng)將不保存此內(nèi)存頁，而只是簡單地

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

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

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