LRU Lists & pagevecs

 

Memory Reclaiming

메모리가 부족하면 주기적으로 페이지를 해지하는 프로세스가 돌며 페이지를 회수하여 재사용 하는데 여러 가지 메모리 교체 정책이 있다. 그 중 리눅스는 LRU 알고리즘을 사용한다.

 

LRU (Least Recently Used)

  •  최소 빈도로 사용되는 페이지를 회수하는 방식이다.
  • 커널 2.6.28-rc1 부터는 기존에 zone별로 2개의 LRU(active_list 와 inactive_list) 리스트로 관리하였었는데 이를 5개로 확대하여  사용한다.
  • 속성
      •  ANON
        • annoonymous user page(메모리 할당 API를 사용하여 할당 받은 페이지)
        • 메모리 부족 시 swap file(영역)에 옮긴다.
          • 현재 리눅스 커널은 성능상의 이유로 swap 크기가 default 0으로 설정되어 있다.
          • 최근 tovalds는 ssd 타입의 디스크를 사용하여 다시 swap을 사용하는 것에 관심을 갖고 있다.
      • FILE
        • mapped user mode page로 정규 파일에서 읽어 들인 페이지의 한 종류
        • 메모리 부족 시 clean 페이지들은 그냥 회수하고, dirty된 페이지들은 file(backing store)에 기록 후에 회수한다.
      •  ACTIVE
        • 처음 할당된 페이지들은 active 리스트의 선두(hot)에 추가된다.
        • 주기적으로 active와 inactive의 ratio를 비교하여 참조되지 않는 페이지는 inactive 리스트로 옮기고 참조된 페이지는 다시 active list의 선두로 옮긴다(rotate).
      •  INACTIVE
        • 회수 매커니즘이 동작할 때 inactive 리스트의 후미(cold)에서 회수를 시도한다.
          • ANON: swap file에 옮긴다.
            • 옮길 swap 공간이 부족하면… ^^;
          • FILE: clean 페이지를 회수하고 dirty 페이지인 경우 writeback을 동작(async)시켜 원래의 화일에 기록하게 해놓고 페이지를 inactive list의 선두로 옮긴다(rotate)
            • inactive 리스트의 선두로 rotate된 경우 roatate되어 후미로 밀려나면 그 때 다시 페이지 회수 판단하게 된다.
      • UNEVICTABLE
        • 메모리 회수 메커니즘에서 사용할 수 없도록 한 페이지로 다음의 경우 사용된다.
          • ramfs
          • SHM_LOCK(공유 메모리 락)’d shared memory regions
          • VM_LOCKED VMAs
        • 다음 3가지 case에서는 isolation을 통한 migration을 허용한다.
          • 메모리 파편화 관리
          • 워크로드 관리
          • 메모리 hotplug
        • LRU pagevec 매커니즘을 사용하지 않는다.
      • lru 리스트는 양방향 리스트로 선두는 hot, 페이지 후미는 cold 페이지 성격을 갖는다.

     

 

pagevecs

  • 빠른 성능을 갖기위해 멀티페이지 컨테이너 cpu 캐시가 있고, 아래와 같이 4개의 pagevecs가 있으며 각각은 14개의 페이지를 갖을 수 있다.
    • lru_add_pvec
    • lru_rotate_pvecs
    • lru_deactivate_pvecs
    • activate_page_pvecs

 

구조체

pagevec 구조체

struct pagevec {                        
        unsigned long nr;
        unsigned long cold;
        struct page *pages[PAGEVEC_SIZE];
};

lruvec 구조체

include/linux/mmzone.h

struct lruvec {
        struct list_head lists[NR_LRU_LISTS];
        struct zone_reclaim_stat reclaim_stat;
#ifdef CONFIG_MEMCG
        struct zone *zone;
#endif
};

 

zone_reclaim_stat 구조체

include/linux/mmzone.h

struct zone_reclaim_stat {
        /*
         * The pageout code in vmscan.c keeps track of how many of the
         * mem/swap backed and file backed pages are referenced.
         * The higher the rotated/scanned ratio, the more valuable
         * that cache is.
         *
         * The anon LRU stats live in [0], file LRU stats in [1]
         */
        unsigned long           recent_rotated[2];
        unsigned long           recent_scanned[2];
};

 

lru_list

include/linux/mmzone.h

/*
 * We do arithmetic on the LRU lists in various places in the code,
 * so it is important to keep the active lists LRU_ACTIVE higher in
 * the array than the corresponding inactive lists, and to keep
 * the *_FILE lists LRU_FILE higher than the corresponding _ANON lists.
 *
 * This has to be kept in sync with the statistics in zone_stat_item
 * above and the descriptions in vmstat_text in mm/vmstat.c
 */
#define LRU_BASE 0
#define LRU_ACTIVE 1
#define LRU_FILE 2

enum lru_list {
        LRU_INACTIVE_ANON = LRU_BASE,
        LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
        LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
        LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
        LRU_UNEVICTABLE,
        NR_LRU_LISTS
};

전역 pagevec 캐시

mm/swap.c

static DEFINE_PER_CPU(struct pagevec, lru_add_pvec);
static DEFINE_PER_CPU(struct pagevec, lru_rotate_pvecs);
static DEFINE_PER_CPU(struct pagevec, lru_deactivate_pvecs);
static DEFINE_PER_CPU(struct pagevec, activate_page_pvecs);

 

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.