[内核内存] [arm64] 内存回收1---LRU链表机制

系统管理员 2023-01-16 14:25 131阅读 0赞

### 文章目录 ###

*  LRU机制与linux内存回收
 *   *  linux 内存回收引入 LRU链表的原因
     *  linux通过LRU链表筛选出理想的回收页框原理
     *  linux LRU缓存机制
 *  linux内核LRU实现
 *   *  LRU链表拆分原理分析
     *  LRU链表内核代码实现

对于linux内存回收来说，lru链表是关键，因为内存回收的整个过程都是处理lru链表的收缩。lru链表的作用就是对进行页排序，将应该回收的页放在链表尾部，最不该回收的页放在链表头部；内存回收主要是将lru链表中最近很少访问的尾部页框内容从内存转储到磁盘中，然后将转储后的页框释放到伙伴系统作为空闲内存使用。

# LRU机制与linux内存回收 #

## linux 内存回收引入 LRU链表的原因 ##

linux长时间运行后，内存会出现吃紧的状况，空闲内存慢慢变少。这个时候linux内存管理系统就会通过内存回收机制来回收进程正在使用的匿名页和文件页。回收这些页框时，如果内存管理系统不进行挑选，很可能刚刚回收释放的页框很快会被重新用到，这样又必须将转储到磁盘的内容再次写入内存，这样就会造成页抖动（page thrashing）或者缓存抖动（cache thrashing），极大降低系统性能。

那么在内存回收时如何合理地选择回收的页框，是减缓系统页抖动，提高系统性能的关键。通常为了防止刚回收的页框不会很快再次被内存使用，那么内存回收选则的页框应该是那些最近不被使用，不活跃的页框。

linux内存管理系统是通过引入LRU算法来对回收的页框进行筛选。主要是将分配给进程的页框储在对应的LRU链表中，通过LRU算法获取到最近不活跃的页框，并将这些页框转交给内存回收系统进行释放处理。

## linux通过LRU链表筛选出理想的回收页框原理 ##

linux内存管理系统如何通过引入LRU链表筛选出不活跃的页框？

linux维护了2个双向的lru链链表：

*  active\_list:该链表中包含的是最近使用的页面
 *  inactive\_list:该链表中包含的是最近不使用的页面

页框中struct page中的lru指向了其所在lru链表中前后页框的指针，且struct page的flags中使用了PG\_referenced和PG\_active两个标志位来标识页面的活跃程度。

*  PG\_active标志位指示了该页块因该在哪个lru链表，PG\_active标志位为1在activ\_list链表，为0在inactive\_list
 *  PG\_referenced标志位指示了该页框是否被使用；若页框被访问，mark\_page\_accessed()会检测该page的PG\_referenced位，PG\_referenced位为0，将其置为1.

void mark_page_accessed(struct page *page)
    { 
        ...
    	if (!PageActive(page) && PageReferenced(page)) { 
    	    activate_page(page);
    	} 
            else if (!PageReferenced(page)) { 
    	    SetPageReferenced(page);
    	}
        ...
    }

active\_list和inactive\_list都是采用先进先出（FIFO）的方式。新的页从链表头加入，链表中间的元素逐渐向尾部移动。而内存回收时，总是选择inactive\_list链表的尾部进行回收。两个链表中页的移动情况如下：

*  在inactive\_list上PG\_referenced为1的页在回收前被再次访问到，也就是说它在inactive\_list中被访问了2次，mark\_page\_accessed()就会调用activate\_page()将其置换到active\_list的头部，同时将其PG\_active位置1，PG\_referenced位清0(两个PG\_referenced才换来一个PG\_active)
 *  在inactive\_list中的页在移动到尾部时，若PG\_referenced位为0，则内存回收机制被触发时，该页框将会被回收
 *  在inactive\_list中的页在移动到链表尾部，若PG\_referenced位为1，该页是否被回收，要依赖与linux内核的机制。(在内存回收这一块，很多事后是根据经验来定的，根据实际效果的好坏来选择合适的机制)。inactive\_list可以被当做内核在不确定是否要立刻回收一个页面时，用于暂时保持该页面的一个场所，相当于给该页保留一次机会，若该页再次被访问就很有可能免于释放的惩罚，重新回到active\_list中）
 *  active\_list中的页移动到链表尾部时，若该页的PG\_referenced位为1，则该页会被放回active\_list的链表头同时该页的PG\_referenced会被清0;若果该页的PG\_referenced位为0，则该页会被放入inactive\_list的头部。

从上面的机制可以看出liux采用LRU算法并不是按照严格的时间顺序来置换页框的，算是一种伪LRU算法（采用先进先出和第二次机会算法结合的方式来筛选出理想的可回收页）。

## linux LRU缓存机制 ##

上面的两条lru双向链表中inactive\_list尾部会不断有页框被释放，而active\_list会不断将尾部的页框添加到inactive\_list的头部。这样inactive\_list就像一个消费者，而active\_list就像一个生产者。在多核的硬件环境中一定会存在同时对lru链表进行修改的情况出现，因此当我们对lru链表进行修改时必须给该链表加一个锁，只有拥有锁的情况下才能对链表进行修改。

linux在多核的硬件环状中，对lru链表进行修改时，锁的竞争会非常的频繁；若inactive\_list和acti\_list两条链表的页面转移工作是一页一页的进行，那么由于锁的平凡竞争，必然会让linux内核系能大幅下降。为此linux内核提出了lru缓存机制来解决上诉问题；lru缓存就是将一些需要相同处理的页整合在一起，当缓存中的页框数量达到一定的数量时在对它进行一次批量处理，这样可以让linux对锁的需求集中在缓存处理的这一个时间点上，缓解竞争压力。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]

# linux内核LRU实现 #

## LRU链表拆分原理分析 ##

实际中linux内核系统使用了5个lru链表存储分配了的页面：

*  LRU\_INACTIVE\_ANON和 LRU\_ACTIVE\_ANON----活跃和非活跃匿名页
 *  LRU\_INACTIVE\_FILE和LRU\_ACTIVE\_FILE----活跃和非活跃文件页
 *  LRU\_UNEVICTABLE----不可回收页（内存回收扫描的时候忽略LRU\_UNEVICTABLE链表）

为什么要将两个LRU链表拆分成5个lru链表呢？

linux系统中使用的页框分为三类

1.  可以存放到swap磁盘分区的匿名页
    
    1.  进程堆，栈，数据段使用的匿名页
    2.  进行匿名mmap共享内存使用的页
    3.  进行shmem共享内存使用的页
2.  映射了磁盘文件的文件页
    
    1.  进程代码段映射的可执行文件页
    2.  打开文件进行文件读写使用的文件页
    3.  进行文件映射mmap共享内存使用的页
3.  被锁在内存中禁止换出的进程页（包括文件页和匿名页）
    
    1.  内核使用的页（内核代码段等）

linux内存回收的页主要就是上面提到的1和2类页框----进程使用的匿名页或文件页。

若内存回收匿名页必须先将匿名页的内容回写到swap磁盘，然后才能将该匿名页释放到伙伴系统中去，回写磁盘的io操作是非常耗时的，所以过多地回收进程匿名页会让系统性能降低。

若内存回收文件页：（1）文件页是dirty page，回收前同样需要将文件页的内容回写到磁盘文件中去，然后才能释放该页到伙伴系统；（2）文件页是非dirty page，回收是直接将该文件页释放到伙伴系统中去，不需要回写磁盘。另外linux提供了page cache机制，提供一块内区域存缓存磁盘文件内容的，这样加速了磁盘回写时的io操作；同时由于page cache中会定期启动flusher线程去回写page cache中的页内容到磁盘对应的文件中去；因此page cache中的大部分页都是非dirty page。这样内核在内存不足触发内存回收时，会更倾向于回收page cache中的文件页；只有当内存面临相当大的压力时，才会去回收进程使用的匿名页。linux还提供/proc/sys/vm/swappiness接口，让用户能够根据实际情况调节内存回收回收匿名页和文件页的比例情况。swappiness值的取值范围为0-100，默认值是60:该值取值越高，内存回收时会越优先选择匿名页;该值越低，内存回收时会越优先选择文件页。当swappiness0时内存回收只选择文件页，而当swappness100,回收匿名页和文件页的权重相同。

/* * With swappiness at 100, anonymous and file have the same priority. * This scanning priority is essentially the inverse of IO cost. */
    anon_prio = swappiness;
    file_prio = 200 - anon_prio

linux最后为了能够实现优先回收page cache中的文件页，于是设计了LRU\_INACTIVE\_ANON,LRU\_ACTIVE\_ANON， LRU\_INACTIVE\_FILE和LRU\_ACTIVE\_FILE。

linux系统被分配出去中的有些页是不允许被回收的物理页，比如像内核中大部分页框都不允许回收；因此linux内核还设计了一个LRU\_UNEVICTABLE链表用于存储这些页，这些页的flag的PG\_unevictable被置位为1，内存回收时，内核将不会扫描LRU\_UNEVICTABLE链表上的页，以此来减少回收时扫描分配页的总体时间。

## LRU链表内核代码实现 ##

linux内核源码中，每个Node节点会维护一个lruvec结构，该结构用于存放5种不同类型的LRU链表，在内存进行回收时，在LRU链表中检索最少使用的页面进行处理。

typedef struct pglist_data { 
    /* lru链表使用的自旋锁 * 当需要修改lru链表描述符中任何一个链表时，都需要持有此锁，也就是说，不会有两个不同的lru链表同时进行修改 */
    spinlock_t        lru_lock;
    ...
    /* Fields commonly accessed by the page reclaim scanner */
    struct lruvec		lruvec;
    ...
    }
    
    /* 5种不同类型的LRU链表 */
    enum lru_list { 
    //匿名页lru链表
        /*称为非活动匿名页lru链表，此链表中保存的是此node中所有最近没被访问过的并且可以存放到swap分区的页描述符， *在此链表中的页描述符的PG_active标志为0 */
    	LRU_INACTIVE_ANON = LRU_BASE,
        /*称为活动匿名页lru链表，此链表中保存的是此node中所有最近被访问过的并且可以存放到swap分区的页描述符，此链 *表中的页描述符的PG_active标志为1 */
    	LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    //文件页lru链表
        /*为非活动文件页lru链表，此链表中保存的是此node中所有最近没被访问过的文件页的页描述符，此链表中的页描述符的 *PG_active标志为0 */
    	LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
      	/*称为活动文件页lru链表，此链表中保存的是此node中所有最近被访问过的文件页的页描述符，此链表中的页描述符的 *PG_active标志为1 */
    	LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
        /*LRU_UNEVICTABLE：此链表中保存的是此node中所有禁止换出的页的描述符,该链表中的页被所在内存中禁止换出包括 *文件页和匿名页 */
    	LRU_UNEVICTABLE,
    	NR_LRU_LISTS
    };
    
    struct lruvec { 
        /* 5个lru双向链表头 */
    	struct list_head		lists[NR_LRU_LISTS];
    	struct zone_reclaim_stat	reclaim_stat;  //与回收相关的统计数据
    	/* Evictions & activations on the inactive file list */
    	atomic_long_t			inactive_age;
    	/* Refaults at the time of last reclaim cycle */
    	unsigned long			refaults;
    #ifdef CONFIG_MEMCG
        /*所属node*/
    	struct pglist_data *pgdat;
    #endif
    }

内核主要是将对应页的页描述符加入到与自身属性相匹配的lru链表中去，比如一个页映射了磁盘文件，那么这个页就加入到文件页lru链表中，内核主要通过页描述符的lru成员和flags标志来描述该页是否属于lru链表，已经属于哪种类型的lru链表。

struct page { 
       // 用于页描述符，一组标志(如PG_locked、PG_error)，同时页框所在的管理区和node的编号也保存在当中
       /* 在lru算法中主要用到的标志 * PG_active: 表示此页当前是否活跃，当放到或者准备放到活动lru链表时，被置位 * PG_referenced: 表示此页最近是否被访问，每次页面访问都会被置位 * PG_lru: 表示此页是处于lru链表中的 * PG_mlocked: 表示此页被mlock()锁在内存中，禁止换出和释放 * PG_swapbacked: 表示此页依靠swap，可能是进程的匿名页(堆、栈、数据段)，匿名mmap共享内存映射，shmem共 * 享内存映射 */
    　　unsigned long flags;
    
    　　......
    
    　　union { 
          /* 页处于不同情况时，加入的链表不同 * 1.是一个进程正在使用的页，加入到对应lru链表和lru缓存中 * 2.如果为空闲页框，并且是空闲块的第一个页，加入到伙伴系统的空闲块链表中(只有空闲块的第一个页需要加入) * 3.如果是一个slab的第一个页，则将其加入到slab链表中(比如slab的满slab链表，slub的部分空slab链表) * 4.将页隔离时用于加入隔离链表 */
    　　　　struct list_head lru;   
    
    　　　　......
    
    　　};
    
    　　......

为了提高性能，每个CPU有5个struct pagevecs结构，存储一定数量的页面（默认14个页），最终一次性把这些页面加入到LRU链表中。比如:

1.  当一个新页需要加入lru链表时，就会加入到cpu的lru\_add\_pvec缓存；
2.  当一个非活动lru链表的页需要被移动到非活动页lru链表末尾时，就会被加入cpu的lru\_rotate\_pvecs缓存；
3.  当一个活动lru链表的页需要移动到非活动lru链表中时，就会加入到cpu的lru\_deactivate\_pvecs缓存；
4.  当一个非活动lru链表的页被转移到活动lru链表中时，就会加入到cpu的activate\_page\_pvecs缓存.

最后任意一个缓存被页填满后（==14）,缓存中的页将会被批量的用特定的方式在lru链表上移动。需要注意的是内核是为每个CPU提供四种lru缓存，每个CPU维护5个pagevec,每个pagevec能容纳14个page

/* 14 pointers + two long's align the pagevec structure to a power of two */
    /*一个lru缓存的大小为14，也就是一个lru缓存中最多能存放14个即将处理的页*/
    #define PAGEVEC_SIZE 14
    struct pagevec { 
        /* 当前数量 */
    	unsigned long nr;
    	unsigned long cold;
        /* 指针数组，每一项都可以指向一个页描述符，默认大小是14 */
    	struct page *pages[PAGEVEC_SIZE];  //存放14个page结构
    };
    
    /* 每个CPU定义5种类型 */
    /* 这部分的lru缓存是用于那些原来不属于lru链表的，新加入进来的页 */
    static DEFINE_PER_CPU(struct pagevec, lru_add_pvec);
    /* 在这个lru_rotate_pvecs中的页都是非活动页;在非活动lru链表中，将这些页移动到非活动lru链表的末尾 */
    static DEFINE_PER_CPU(struct pagevec, lru_rotate_pvecs);
    /* 在这个lru缓存的页原本应属于活动lru链表中的页，会强制清除PG_activate和PG_referenced，并加入到非活动lru *链表的链表表头中这些页一般从活动lru链表中的尾部拿出来的 */
    static DEFINE_PER_CPU(struct pagevec, lru_deactivate_file_pvecs);
    static DEFINE_PER_CPU(struct pagevec, lru_lazyfree_pvecs);
    #ifdef CONFIG_SMP
    /* 将此lru缓存中的页放到活动页lru链表头中，这些页原本属于非活动lru链表的页 */
    static DEFINE_PER_CPU(struct pagevec, activate_page_pvecs);
    #endif

知识点小结：

（1）linux系统中内存充足时，内核会尽量多的使用内存作为文件缓存，以此提高系统性能，且文件缓存会被加到LRU链表中。内存紧张的时候，文件缓存页面会被丢弃，或者被修改的文件缓存会被回写到存储设备中，与块设备同步后便释放物理内存。

（2）linux LRU链表被分成5个类型的原因是，linux当内存紧张时，总是会优先换出到page cache中的页面，而不是匿名页面。因为大多数情况下page cache页面不需要回写到磁盘，而匿名页总是要写入交换分区中。

参考:

https://zhuanlan.zhihu.com/p/70964195

https://blog.csdn.net/abc593043305/article/details/82025143

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/dd675262a318438ead122664688d136e.png