All of the physical pages in the system are described by the mem_map  data structure which is a list of mem_map_t 

 

typedef struct page { 
// these must be first (free area handling)

struct page        *next;
struct page        *prev;
struct inode       *inode;
unsigned long      offset;
struct page        *next_hash;
atomic_t           count;        //本页使用者计数
unsigned           flags;    // atomic flags, some possibly
                                   updated asynchronously
unsigned           dirty:16, 
                          age:8;        //描述本页的年龄，用来判断该页是否为淘汰或交换的好的候选
struct wait_queue *wait;
struct page        *prev_hash;
struct buffer_head *buffers;
unsigned long      swap_unlock_entry;
unsigned long      map_nr;   // page->map_nr == page - mem_map 物理页的页帧号
} mem_map_t;

 

Each mem_map_t  describes a single physical page in the system. Important fields (so far as memory management is concerned) are:

count

This is a count of the number of users of this page. The count is greater than one when the page is shared between many processes,

age

This field describes the age of the page and is used to decide if the page is a good candidate for discarding or swapping,

map_nr

This is the physical PFN that this mem_map_t  describes.

 

allocation example:

The allocation algorithm first searches for blocks of pages of the size requested. It follows the chain of free pages that is queued on the list element of the free_area  data structure. If no blocks of pages of the requested size are free, blocks of the next size (which is twice that of the size requested) are looked for. This process continues until all of the free_area  has been searched or until a block of pages has been found. If the block of pages found is larger than that requested it must be broken down until there is a block of the right size. Because the blocks are each a power of 2 pages big then this breaking down process is easy as you simply break the blocks in half. The free blocks are queued on the appropriate queue and the allocated block of pages is returned to the caller.

 

deallocation example:

 if PFN 1 were to be freed, then that would be combined with the already free PFN 0 and queued onto element 1 of the free_area  as a free block of size 2 pages.