分段和分頁

先看一幅圖

?

也就是我們實際中編碼時遇到的內存地址并不是對應于實際內存上的地址，我們編碼中使用的地址是一個邏輯地址，會通過分段和分頁這兩個機制把它轉為物理地址。而由于linux使用的分段機制有限，可以認為，linux下的邏輯地址=線性地址。也就是，我們編碼使用的是線性地址，之后只需要經過一個分頁機制就可以把這個地址轉為物理地址了。所以我們更重要的可能是去說明一下linux的分頁模型。

系統會將整個物理內存分為多個頁框，每個頁框大小一般是4K(硬件允許的擴展分頁(PSE)情況下也可設置為4M，不過linux并不使用PSE，而可能使用PAE)，也就是如果我們有1GB的物理內存，系統就會將這個物理內存分為262144個頁框。當我們提供一個線性地址時，系統就會通過分頁機制將這個線性地址轉換為對應于某個物理頁中的某個內存地址。下圖是linux的分頁模型

?

linux采用四級分頁模型，這四種頁表是：頁全局目錄(PGD)、頁上級目錄(PUD)、頁中間目錄(PMD)、頁表(PTE)。這里的所有頁全局目錄、頁上級目錄、頁中間目錄、頁表，它們的大小都是一個頁。linux下各個硬件上并不一定都是使用四級目錄的，當使用于沒有啟動物理地址擴展(PAE)的32位系統上時，只使用二級頁表，linux會把頁上級目錄和頁中間目錄置空。而在啟用了物理地址擴展的32位系統上時，linux使用的是三級頁表，頁上級目錄被置空。而在64位系統上，linux根據硬件的情況會選擇三級頁表或者四級頁表。這個整個由線性地址轉換到物理地址的過程，是由CPU自動進行的。

每個進程都有它自己的頁全局目錄，當進程運行時，系統會將該進程的頁全局目錄基地址保存到cr3寄存器中；而當進程被換出時，會將這個cr3保存的頁全局目錄地址保存到進程描述符中。之后我們還會介紹一個cr2寄存器，用于缺頁異常處理的。當進程運行時，它使用的是它自己的一套頁表，當它通過系統調用或陷入內核態時，使用的是內核頁表，實際上，對于所有的進程頁表來說，它們的線性地址0xC0000000以上所涉及到的頁表都是主內核頁全局目錄(保存在init_mm.pgd)，它們的內容等于主內核頁全局目錄的相應表項，這樣就實現了所有進程的進程空間相互隔離，但是內核空間相互共享的情況。當某個進程修改了內核頁表的一些映射情況后，系統只會相應的修改主內核頁全局目錄中的表項(只能修改高端內存中非連續內存區的映射)，當其他進程訪問這些線性地址時，會出現缺頁異常，然后修改該進程的頁表項重新映射該地址。

因為說到每個進程都有它自己的頁全局目錄，如果有100個進程，內存中就要保存100個進程的整個頁表集，看起來會耗費相當多的內存。實際上，只有進程使用到的情況下系統才會分配給進程一條路徑，比如我們要求訪問一個線性地址，但是這個地址可能對應的頁上級目錄、頁中間目錄、頁表和頁都不存在的，這時系統會產生一個缺頁異常，在缺頁異常處理中再給進程的這個線性地址分配頁上級目錄、頁中間目錄、頁表和頁所需的物理頁框。

地址空間

一個線性地址經過分頁機制轉為一個對應的物理地址，我們稱之為映射，比如我們的一個線性地址0x00000001經過分頁機制處理后，對應的物理地址可能是0xffffff01。

在linux系統中分兩個地址空間，一個是進程地址空間，一個是內核地址空間。對于每個進程來說，他們都有自己的大小為3G的進程地址空間，這些進程地址空間是相互隔離的，也就是進程A的0x00000001線性地址和進程B的0x00000001線性地址并不是同一個地址，進程A也不能通過自己的進程空間直接訪問進程B的進程地址空間。而當線性地址大于3G時(也就是0xC0000000)，這里的線性地址屬于內核空間，內核地址空間的大小為1G，地址從0xC0000000到0xFFFFFFFF。在內核地址空間中，內核會把前896MB的線性地址直接與物理地址的前896MB進行映射，也就是說，內核地址空間的線性地址0xC0000001所對應的物理地址為0x00000001，它們之間相差一個0xC0000000。

linux內核會將物理內存分為3個管理區，分別是：

ZONE_DMA：包含0MB~16MB之間的內存頁框，可以由老式基于ISA的設備通過DMA使用，直接映射到內核的地址空間。

ZONE_NORMAL：包含16MB~896MB之間的內存頁框，常規頁框，直接映射到內核的地址空間。

ZONE_HIGHMEM：包含896MB以上的內存頁框，不進行直接映射，可以通過永久映射和臨時映射進行這部分內存頁框的訪問。

整個結構如下圖

對于ZONE_DMA和ZONE_NORMAL這兩個管理區，內核地址都是進行直接映射，只有ZONE_HIGHMEM管理區系統在默認情況下是不進行直接映射的，只有在需要使用的時候進行映射(臨時映射或者永久映射)。

結點和管理區描述符

為了用于NUMA架構，使用了node用來描述一個地方的內存。對于我們PC來說，一臺PC就是一個node。node用struct pglist_data結構表示：

/* 內存結點描述符，所有的結點描述符保存在 struct pglist_data *node_data[MAX_NUMNODES] 中 */
typedef struct pglist_data {
    /* 管理區描述符的數組 */
    struct zone node_zones[MAX_NR_ZONES]; 
    /* 頁分配器使用的zonelist數據結構的數組，將所有結點的管理區按一定的關聯鏈接成一個鏈表，分配內存時會按照此鏈表的順序進行分配 */
    struct zonelist node_zonelists[MAX_ZONELISTS];
    /* 結點中管理區的個數 */
    int nr_zones;
#ifdef CONFIG_FLAT_NODE_MEM_MAP    /* means !SPARSEMEM */
    /* 結點中頁描述符的數組，包含了此結點中所有頁框描述符，實際分配是是一個指針數組 */
    struct page *node_mem_map;
#ifdef CONFIG_MEMCG
    /* 用于資源限制機制 */
    struct page_cgroup *node_page_cgroup;
#endif
#endif
#ifndef CONFIG_NO_BOOTMEM
    /* 用在內核初始化階段 */
    struct bootmem_data *bdata;
#endif
#ifdef CONFIG_MEMORY_HOTPLUG
    /* 自旋鎖 */
    spinlock_t node_size_lock;
#endif
    /* 結點中第一個頁框的下標，在numa系統中，頁框會有兩個序號，所有頁框的一個序號，還有就是在此結點中的一個序號
     * 比如結點2中的頁框1，它在結點2中的序號是1，但是在所有頁框中的序號是1001，這個變量就是保存這個結點首頁框的序號1000，用于方便轉換
     */
    unsigned long node_start_pfn;
    /* 內存結點的大小，不包括洞(以頁框為單位) */
    unsigned long node_present_pages; 
    /* 結點的大小，包括洞(以頁框為單位) */
    unsigned long node_spanned_pages; 
    
    /* 結點標識符 */
    int node_id;
    /* kswaped頁換出守護進程使用的等待隊列 */
    wait_queue_head_t kswapd_wait;
    wait_queue_head_t pfmemalloc_wait;
    /* 指針指向kswapd內核線程的進程描述符 */
    struct task_struct *kswapd;    /* Protected by
                       mem_hotplug_begin/end() */
    /* kswapd將要創建的空閑塊大小取對數的值 */
    int kswapd_max_order;
    enum zone_type classzone_idx;
#ifdef CONFIG_NUMA_BALANCING
    /* 以下用于NUMA的負載均衡 */
    /* Lock serializing the migrate rate limiting window */
    spinlock_t numabalancing_migrate_lock;

    /* Rate limiting time interval */
    unsigned long numabalancing_migrate_next_window;

    /* Number of pages migrated during the rate limiting time interval */
    unsigned long numabalancing_migrate_nr_pages;
#endif
} pg_data_t;

系統中所有的結點描述符都保存在node_data這個數組中。在pg_data_t這個結點描述符中，node_zones數組中保存了這個結點中所有的管理區描述符，雖然系統將物理內存分為三個區，但是在邏輯上，系統分為了四個管理區，多出的一個是ZONE_MOVABLE，這個區是一個虛擬的管理區，它并沒有對應于內存的某個區域，它的主要目的就是為了避免內存碎片化，它的內存要么全部來自ZONE_HIGHMEM區，要么全部來自ZONE_NORMAL區。這些我們在后面的初始化函數中將會看到。

每個結點都有一個內核線程kswapd，它的作用就是將進程或內核持有的，但是不常用的頁交換到磁盤上，以騰出更多可用內存。

我們再看看管理區描述符：

/* 內存管理區描述符 */
struct zone {
    /* Read-mostly fields */

    /* zone watermarks, access with *_wmark_pages(zone) macros */
    /* 包括pages_min,pages_low,pages_high
     * pages_min: 管理區中保留頁的數目
     * pages_low: 回收頁框使用的下界，同時也被管理區分配器作為閥值使用，一般這個數字是pages_min的5/4
     * pages_high: 回收頁框使用的上界，同時也被管理區分配器作為閥值使用，一般這個數字是pages_min的3/2
     */
    unsigned long watermark[NR_WMARK];

    /* 指明在處理內存不足的臨界情況下管理區必須保留的頁框數目，同時也用于在中斷或臨界區發出的原子內存分配請求(就是禁止阻塞的內存分配請求) */
    long lowmem_reserve[MAX_NR_ZONES];

#ifdef CONFIG_NUMA
    int node;
#endif

    /*
     * The target ratio of ACTIVE_ANON to INACTIVE_ANON pages on
     * this zone's LRU.  Maintained by the pageout code.
     */
    unsigned int inactive_ratio;

    /* 指向此管理區屬于的結點 */
    struct pglist_data    *zone_pgdat;
    /* 實現每CPU頁框高速緩存，里面包含每個CPU的單頁框的鏈表 */
    struct per_cpu_pageset __percpu *pageset;

    /*
     * This is a per-zone reserve of pages that should not be
     * considered dirtyable memory.
     */
    unsigned long        dirty_balance_reserve;

#ifndef CONFIG_SPARSEMEM
    /*
     * Flags for a pageblock_nr_pages block. See pageblock-flags.h.
     * In SPARSEMEM, this map is stored in struct mem_section
     */
    unsigned long        *pageblock_flags;
#endif /* CONFIG_SPARSEMEM */

#ifdef CONFIG_NUMA
    /*
     * zone reclaim becomes active if more unmapped pages exist.
     */
    unsigned long        min_unmapped_pages;
    unsigned long        min_slab_pages;
#endif /* CONFIG_NUMA */

    /* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
    /* 管理區第一個頁框下標 */
    unsigned long        zone_start_pfn;

    /* 所有正常情況下可用的頁，總頁數(不包括洞)減去保留的頁數 */
    unsigned long        managed_pages;
    /* 管理區總大小(頁為單位)，包括洞 */
    unsigned long        spanned_pages;
    /* 管理區總大小(頁為單位)，不包括洞 */
    unsigned long        present_pages;
    /* 指向管理區的傳統名稱，"DMA" "NORMAL" "HighMem" */
    const char        *name;

    /* 對應于伙伴系統中MIGRATE_RESEVE鏈的頁塊的數量 */
    int            nr_migrate_reserve_block;

#ifdef CONFIG_MEMORY_ISOLATION
    /*
     * Number of isolated pageblock. It is used to solve incorrect
     * freepage counting problem due to racy retrieving migratetype
     * of pageblock. Protected by zone->lock.
     */
    /* 在內存隔離中表示隔離的頁框塊數量 */
    unsigned long        nr_isolate_pageblock;
#endif

#ifdef CONFIG_MEMORY_HOTPLUG
    /* see spanned/present_pages for more description */
    seqlock_t        span_seqlock;
#endif

    /* 進程等待隊列的hash表，這些進程在等待管理區中的某頁 */
    wait_queue_head_t    *wait_table;
    /* 等待隊列散列表的大小 */
    unsigned long        wait_table_hash_nr_entries;
    /* 等待隊列散列表數組大小 */
    unsigned long        wait_table_bits;

    ZONE_PADDING(_pad1_)

    /* Write-intensive fields used from the page allocator */
    /* 保護該描述符的自旋鎖 */
    spinlock_t        lock;

    /* free areas of different sizes */
    /* 標識出管理區中的空閑頁框塊，用于伙伴系統 */
    /* MAX_ORDER為11，分別代表包含大小為1,2,4,8,16,32,64,128,256,512,1024個連續頁框的鏈表 */
    struct free_area    free_area[MAX_ORDER];

    /* zone flags, see below */
    /* 管理區標識 */
    unsigned long        flags;

    ZONE_PADDING(_pad2_)

    /* Fields commonly accessed by the page reclaim scanner */
    /* 活動及非活動鏈表使用的自旋鎖 */
    spinlock_t        lru_lock;
    struct lruvec        lruvec;

    /* Evictions & activations on the inactive file list */
    atomic_long_t        inactive_age;

    /*
     * When free pages are below this point, additional steps are taken
     * when reading the number of free pages to avoid per-cpu counter
     * drift allowing watermarks to be breached
     */
    unsigned long percpu_drift_mark;

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
    /* pfn where compaction free scanner should start */
    unsigned long        compact_cached_free_pfn;
    /* pfn where async and sync compaction migration scanner should start */
    unsigned long        compact_cached_migrate_pfn[2];
#endif

#ifdef CONFIG_COMPACTION
    /*
     * On compaction failure, 1<

此管理區描述符中的實際把所有屬于該管理區的頁框保存在兩個地方：struct free_area free_area[MAX_ORDER]和struct per_cpu_pageset __percpu * pageset。free_area是這個管理區的伙伴系統，而pageset是這個區的每CPU頁框高速緩存。對管理區的理解需要結合伙伴系統和每CPU頁框高速緩存

管理區頁框分配器(管理所有物理內存頁框)

ZONE_NORMAL和ZONE_DMA的地址直接映射到了內核地址空間，但是也不代表內核的代碼可以隨心所欲的通過線性地址直接訪問物理地址。內核通過一個管理區頁框分配器管理著物理內存上所有的頁框，在管理區分配器里的核心系統就是伙伴系統和每CPU頁框高速緩存(不是硬件上的高速緩存，只是名稱一樣)。在linux系統中，管理區頁框分配器管理著所有物理內存，無論你是內核還是進程，需要將一些內存占為己有時，都需要請求管理區頁框分配器，這時才會分配給你應該獲得的物理內存頁框。當你所擁有的頁框不再使用時，你必須釋放這些頁框，讓這些頁框回到管理區頁框分配器當中。特別的，對于高端內存，即使從管理區頁框分配器中獲得了相應的頁框，我們還需要進行映射才能夠使用。

有時候目標管理區不一定有足夠的頁框去滿足分配，這時候系統會從另外兩個管理區中獲取要求的頁框，但這是按照一定規則去執行的，如下：

如果要求從DMA區中獲取，就只能從ZONE_DMA區中獲取。

如果沒有規定從哪個區獲取，就按照順序從 ZONE_NORMAL -> ZONE_DMA 獲取。

如果規定從HIGHMEM區獲取，就按照順序從 ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA 獲取。

注意系統是不允許在一次分配中從不同的兩個管理區獲取頁框的，并且當請求多個頁框時，從伙伴系統中分配給目標的頁框是連續的，并且請求的頁數必須是2的次方個數。

?


管理區分配器主要做的事情就是將頁框通過伙伴系統或者每CPU頁框高速緩存分配出去，這里涉及到三個結構，頁描述符，伙伴系統，每CPU高速緩存。

我們先說說頁描述符，頁描述符實際上并不專屬于描述頁框，它還用于描述一個SLAB分配器和SLUB分配器，這個之后再說，我們先說關于頁的：

/* 頁描述符，描述一個頁框，也會用于描述一個SLAB，相當于同時是頁描述符，也是SLAB描述符 */
struct page {
    /* First double word block */
    /* 用于頁描述符，一組標志(如PG_locked、PG_error)，也對頁框所在的管理區和node進行編號 */
    unsigned long flags;        /* Atomic flags, some possibly
                     * updated asynchronously */
    union {
        /* 用于頁描述符，當頁被插入頁高速緩存中時使用，或者當頁屬于匿名區時使用 */
        struct address_space *mapping;  
        /* 用于SLAB描述符，用于執行第一個對象的地址 */
        void *s_mem;            /* slab first object */
    };


    /* Second double word */
    struct {
        union {
            /* 作為不同的含義被幾種內核成分使用。例如，它在頁磁盤映像或匿名區中標識存放在頁框中的數據的位置，或者它存放一個換出頁標識符 */
            pgoff_t index;        /* Our offset within mapping. */
            /* 用于SLAB描述符，指向第一個空閑對象地址 */
            void *freelist;    
            /* 當管理區頁框分配器壓力過大時，設置這個標志就確保這個頁框專門用于系統釋放其他頁框時使用 */
            bool pfmemalloc;  
        };

        union {
#if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE)
            /* SLUB使用 */
            unsigned long counters;
#else
            /* SLUB使用 */
            unsigned counters;
#endif

            struct {
                union {
                    /* 頁框中的頁表項計數，如果沒有為-1，如果為PAGE_BUDDY_MAPCOUNT_VALUE(-128)，說明此頁及其后的一共2的private次方個數頁框處于伙伴系統中，正在使用時應該是0 */
                    atomic_t _mapcount;

                    struct { /* SLUB使用 */
                        unsigned inuse:16;
                        unsigned objects:15;
                        unsigned frozen:1;
                    };
                    int units;    /* SLOB */
                };
                /* 頁框的引用計數，如果為0，則此頁框空閑，并可分配給任一進程或內核；如果大于0，則說明頁框被分配給了一個或多個進程，或用于存放內核數據。page_count()返回_count的值，也就是該頁的使用者數目 */
                atomic_t _count;        /* Usage count, see below. */
            };
            /* 用于SLAB描述符 */
            unsigned int active;    /* SLAB */
        };
    };


    /* Third double word block */
    union {
        /* 包含到頁的最近最少使用(LRU)雙向鏈表的指針，用于插入伙伴系統的空閑鏈表中，只有塊中頭頁框要被插入 */
        struct list_head lru;    


        /* SLAB使用 */
        struct {        /* slub per cpu partial pages */
            struct page *next;    /* Next partial slab */
#ifdef CONFIG_64BIT
            int pages;    /* Nr of partial slabs left */
            int pobjects;    /* Approximate # of objects */
#else
            short int pages;
            short int pobjects;
#endif
        };

        struct slab *slab_page; /* slab fields */
        struct rcu_head rcu_head;


#if defined(CONFIG_TRANSPARENT_HUGEPAGE) && USE_SPLIT_PMD_PTLOCKS
        pgtable_t pmd_huge_pte; /* protected by page->ptl */
#endif
    };


    /* Remainder is not double word aligned */
    union {
        /* 可用于正在使用頁的內核成分(例如: 在緩沖頁的情況下它是一個緩沖器頭指針，如果頁是空閑的，則該字段由伙伴系統使用，在給伙伴系統使用時，表明的是塊的2的次方數，只有塊的第一個頁框會使用) */
        unsigned long private;        
#if USE_SPLIT_PTE_PTLOCKS
#if ALLOC_SPLIT_PTLOCKS
        spinlock_t *ptl;
#else
        spinlock_t ptl;
#endif
#endif
        /* SLAB描述符使用，指向SLAB的高速緩存 */
        struct kmem_cache *slab_cache;    /* SL[AU]B: Pointer to slab */
        struct page *first_page;    /* Compound tail pages */
    };

#if defined(WANT_PAGE_VIRTUAL)
    /* 此頁框第一個物理地址對應的線性地址，如果是沒有映射的高端內存的頁框，則為空 */
    void *virtual; 
#endif /* WANT_PAGE_VIRTUAL */
#ifdef CONFIG_WANT_PAGE_DEBUG_FLAGS
    unsigned long debug_flags;    /* Use atomic bitops on this */
#endif

#ifdef CONFIG_KMEMCHECK
    void *shadow;
#endif

#ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
    int _last_cpupid;
#endif
}
 

在struct page描述一個頁框時，我們比較關注的成員變量有unsigned long flags、struct list_head lru和atomic_t _count。

flags：包含有很多信息，包括此頁框屬于的node結點號，此頁框屬于的zone號和此頁框的屬性。

lru：用于將此頁描述符放入相應的鏈表，比如伙伴系統或者每CPU頁框高速緩存。

_count：代表頁框的引用計數，0代表此頁框空閑，大于0代表此頁框分配給了多少個進程使用(共享)。

linux為了防止內存中產生過多的碎片，一般把頁的類型分為三種：

不可移動頁：在內存中有固定位置，不能移動到其他地方。內核中使用的頁大部分是屬于這種類型。

可回收頁：不能直接移動，但可以刪除，頁中的內容可以從某些源中重新生成。例如，頁內容是映射到文件數據的頁就屬于這種類型。對于這種類型，在內存短缺(分配失敗)時，會發起內存回收，將這類型頁進行回寫釋放。

可移動頁：可隨意移動，用戶空間的進程使用的沒有映射具體磁盤文件的頁就屬于這種類型(比如堆、棧、shmem共享內存、匿名mmap共享內存)，它們是通過進程頁表映射的，把這些頁復制到新位置時，只要更新進程頁表就可以了。一般這些頁是從高端內存管理區獲取。

伙伴系統

伙伴系統的主要作用就是減少物理內存的外部碎片(SLAB/SLUB減少頁框的內部碎片)，它實際上是一個struct free_area的數組，數組長度是MAX_ORDER，也就是11，代表著每個數組元素中鏈表上保存的連續頁框長度是2的order次方。free_area[0]中鏈表保存的是長度為1的頁框，free_area[1]中鏈表上保存的是物理上連續的兩個頁框的首頁框鏈表，free_area[2]中鏈表上保存的是物理上連續4個頁框的首頁框鏈表，free_area[10]中鏈表上保存的是物理上連續1024個頁框的首頁框鏈表，所以整個伙伴系統中將管理區中的頁框分為連續的1,2,4,8,16,32,64,128,256,512,1024頁框放入不同鏈表中保存起來。而因為伙伴系統中每個鏈表保存的頁框都是連續的，所以只有第一個頁框會加入到鏈表中，因為有order，也可以知道此頁框之后的多少個頁框是屬于這一小塊連續頁框的。當需要在普通內存區申請4個頁框大小的內存時，系統會到普通內存管理區的伙伴系統中的free_area[2]中的第一個鏈表結點，這個結點的頁框及其之后3個頁框都是空閑的，然后把首頁框返回給申請者。

/* 伙伴系統的一個塊，描述1,2,4,8,16,32,64,128,256,512或1024個連續頁框的塊 */
struct free_area {
    /* 指向這個塊中所有空閑小塊的第一個頁描述符，這些小塊會按照MIGRATE_TYPES類型存放在不同指針里 */
    struct list_head    free_list[MIGRATE_TYPES];
    /* 空閑小塊的個數 */
    unsigned long        nr_free;
};
 

在伙伴系統中，因為頁的分類關系，在每種長度相同的連續頁框中又會分出多個不同類型的鏈表，如下，

enum {
    MIGRATE_UNMOVABLE,         /* 不可移動頁 */
    MIGRATE_RECLAIMABLE,       /* 可回收頁 */
    MIGRATE_MOVABLE,           /* 可移動頁 */
    MIGRATE_PCPTYPES,          /* 用來表示每CPU頁框高速緩存的數據結構中的鏈表的可移動類型數目 */
    MIGRATE_RESERVE = MIGRATE_PCPTYPES,     
#ifdef CONFIG_CMA
    MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    MIGRATE_ISOLATE,          /* 不能從這個鏈表分配頁框，因為這個鏈表專門用于NUMA結點移動物理內存頁，將物理內存頁移動到使用這個頁最頻繁的CPU */
#endif
    MIGRATE_TYPES
};

保存連續2個頁框的free_area[2]的結構如下：

?


在從伙伴系統中申請頁框時，有可能會遇到一種情況，就是當前需求的連續頁框鏈表上沒有可用的空閑頁框，這時后，伙伴系統會從下一級獲取一個連續長度的頁框塊，將其拆分放入這級列表；當然在擁有者釋放連續頁框時伙伴系統也會適當地進行連續頁框的合并，并放入下一級中。比如：我需要申請4個頁框，但是長度為4個連續頁框塊鏈表沒有空閑的頁框塊，伙伴系統會從連續8個頁框塊的鏈表獲取一個，并將其拆分為兩個連續4個頁框塊，放入連續4個頁框塊的鏈表中。釋放時道理也一樣，會檢查釋放的這幾個頁框的之前和之后的物理頁框是否空閑，并且能否組成下一級長度的塊。

每CPU頁框高速緩存

每CPU頁框高速緩存也是一個分配器，配合著伙伴系統進行使用，這個分配器是專門用于分配單個頁框的，它維護一個單頁框的雙向鏈表，為什么需要這個分配器，原因主要有兩點:

因為每個CPU都有自己的硬件高速緩存，當對一個頁進行讀取寫入時，首先會把這個頁裝入硬件高速緩存，而如果進程對這個處于硬件高速緩存的頁進行操作后立即釋放掉，這個頁有可能還保存在硬件高速緩存中，這樣我另一個進程需要請求一個頁并立即寫入數據的話，分配器將這個處于硬件高速緩存中的頁分配給它，系統效率會大大增加。

減少鎖的競爭，假設單頁框都是使用free_area來管理，那么多個CPU同時頻繁訪問時，每次都是只能單CPU獲取到頁框，其他CPU等待，這會造成大量的鎖競爭，導致分配效率降低。

在每CPU頁框高速緩存中用一個鏈表來維護一個單頁框的雙向鏈表，每個CPU都有自己的鏈表(因為每個CPU有自己的硬件高速緩存)，那些比較可能處于硬件高速緩存中的頁被稱為“熱頁”，比較不可能處于硬件高速緩存中的頁稱為“冷頁”。其實系統判斷是否為熱頁還是冷頁很簡單，越最近釋放的頁就比較可能是熱頁，所以在雙向鏈表中，從鏈表頭插入可能是熱頁的單頁框，在鏈表尾插入可能是冷頁的單頁框。分配時熱頁就從鏈表頭獲取，冷頁就從鏈表尾獲取。

在每CPU頁框高速緩存中也可能會遇到沒有空閑的頁框(被分配完了)，這時候每CPU頁框高速緩存會從伙伴系統中拿出頁框放入每CPU頁框高速緩存中，相反，如果每CPU頁框高速緩存中頁框過多，也會將一些頁框放回伙伴系統。

在內核中使用struct per_cpu_pageset結構描述一個每CPU頁框高速緩存，其中的struct per_cpu_pages是核心結構體，如下：

/* 描述一個CPU頁框高速緩存 */
struct per_cpu_pageset {
    /* 高速緩存頁框結構 */
    struct per_cpu_pages pcp;
#ifdef CONFIG_NUMA
    s8 expire;
#endif
#ifdef CONFIG_SMP
    s8 stat_threshold;
    s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
#endif
};

struct per_cpu_pages {
    /* 當前CPU高速緩存中頁框個數 */
    int count;        /* number of pages in the list */
    /* 上界，當此CPU高速緩存中頁框個數大于high，則會將batch個頁框放回伙伴系統 */
    int high;        /* high watermark, emptying needed */
    /* 在高速緩存中將要添加或被刪去的頁框個數 */
    int batch;        /* chunk size for buddy add/remove */

    /* Lists of pages, one per migrate type stored on the pcp-lists */
    /* 頁框的鏈表，如果需要冷高速緩存，從鏈表尾開始獲取頁框，如果需要熱高速緩存，從鏈表頭開始獲取頁框 */
    struct list_head lists[MIGRATE_PCPTYPES];
};

關于頁框回收

內存中并非所有物理頁面都是可以進行回收的，內核占用的頁不會被換出，只有與用戶空間建立了映射關系的物理頁面才會被換出。總的來說，以下這些種物理頁面可以被 Linux 操作系統回收：

進程映射所占的頁面，包括代碼段，數據段，堆棧以及動態分配的“存儲堆”（malloc分配的）。

用戶空間中通過mmap()把文件內容映射到內存所占的頁面。

匿名頁面(沒有映射到文件的都是匿名映射，用戶空間的堆和棧)：進程用戶模式下的堆棧以及是使用 mmap 匿名映射的內存區(共享內存區)。注：堆棧所占頁面一般不被換出。

特殊的用于 slab 分配器的緩存，比如用于緩存文件目錄結構 dentry 的 cache，以及用于緩存索引節點 inode 的 cache

tmpfs文件系統使用的頁。

Linux 操作系統使用如下這兩種機制檢查系統內存的使用情況，從而確定可用的內存是否太少從而需要進行頁面回收。

周期性的檢查：這是由后臺運行的守護進程 kswapd 完成的。該進程定期檢查當前系統的內存使用情況，當發現系統內空閑的物理頁面數目少于特定的閾值時，該進程就會發起頁面回收的操作。

“內存嚴重不足”事件的觸發：在某些情況下，比如，操作系統忽然需要通過伙伴系統為用戶進程分配一大塊內存，或者需要創建一個很大的緩沖區，而當時系統中 的內存沒有辦法提供足夠多的物理內存以滿足這種內存請求，這時候，操作系統就必須盡快進行頁面回收操作，以便釋放出一些內存空間從而滿足上述的內存請求。 這種頁面回收方式也被稱作“直接頁面回收”。

如果操作系統在進行了內存回收操作之后仍然無法回收到足夠多的頁面以滿足上述內存要求，那么操作系統只有最后一個選擇，那就是使用 OOM( out of memory )killer，它從系統中挑選一個最合適的進程殺死它，并釋放該進程所占用的所有頁面。

結尾

下篇再說slab了，內容太多。到這里，記住對于物理內存來說，系統都是以頁框作為最小的分配單位，而分配時必定是要通過管理區分配器進行分配的，在管理區分配器中又必定是通過伙伴系統或每CPU頁框分配器進行分配的，而我們編程使用到的malloc或者內核中使用的分配小額內存的情況，是使用slab實現的，slab的作用就是將一個頁框細分為多個小塊內存。

審核編輯：湯梓紅