23.12.14 최초 작성

유휴 페이지의 갯수가 부족할 경우 발생

1. Linux Page Replacement

1.1 Page Replacement concept

• working-set알고리즘을 활용한 dual-LRU

• 2개의 LRU list queue 자료구조를 두어 각각에 대해 LRU approximation 적용

  • Anon : anonymous page 관리, 페이지를 swap space에 반납
  • File : shared page 관리, 페이지를 filesystem space에 반납
  • 위 둘 사이에 어떤 페이지를 교체할지(swappiness) 정책을 결정
  • UNEVICTALBE : 교체되지 않는 페이지 관리

• LRU approximation

  • clock-based second chance algorithm

  • working set : 최근 time-window동안 접근되는 페이지들

    • 각 ANON/File LRU list는 ACTIVE, INACTIVE로 나눠지며 주로 INACTIVE에서 교체 수행
    • 각 ACTIVE, INACTIVE의 출구를 LRU, 입구를 MRU 위치라고 함
    • ACTIVE의 LRU 위치에 있는 페이지 부터 INACTIVE의 MRU로 보냄
    • INACTIVE의 LRU 위치에 있는 페이지는 정책에 따라 ACTIVE의 MRU로 보낼지, 디스크로 보낼지 결정

  • 2Q replacement

    • LRU list를 2개의 queue(ACTIVE, INACTIVE)로 관리해 최우선적으로 single use data를 교체해 메모리 부담 완화
    • 만약 페이지를 queue에 넣을 때 오래 참조되지 않았다면 INACTIVE로 보냄

1.2 LRU list

• 각 리스트는 node단위로 5개 존재하며(ACTIVE_ANON/FILE, INACTIVE_ANON/FILE, UNEVICTALBE) linked list로 관리 됨

• ACTIVE → INACTIVE를 demotion, 반대를 promotion이라 함

• 각 노드에 접근할 때마다 spinlock을 획득해야 하며 per-CPU-pagevec정책에 따라 한번 삽입할 때 15페이지를 모아야 함

1.2.1 UNEVICTALBE

• 교체되지 않는 페이지 관리 (RAM file system, Locked shared memory 영역, mlocked된 페이지)

1.3 Page Replacement policy

• Page Fault 발생 시 cold miss이거나 refault_distance > size(ACTIVE + INACTIVE)일 경우 INACTIVE list로, refault_distance < size(ACTIVE + INACTIVE)이면 ACTIVE list로

• ACTIVE list

  • 해당 리스트에 충분한 페이지가 모일 시 shrink_active_list()를 통해 1, 2할지 결정

    1. rotate
vma가 실행 가능, 파일영역에 존재, pte의 accessed플래그가 설정된 경우ACTIVE list의 MRU로 이동

    2. deactivate : 일반적으로 pte의 accessed플래그를 해제하고 INACTIVE로 이동

• INACTIVE list

  • 해당 리스트에 충분한 페이지가 모일 시 shrink_inactive_list(), shrink_page_list를 통해 1, 2, 3할지 결정

    1. reclaim : buddy system으로 페이지 반환

    2. keep

       페이지가 참조되지 않고 pte의 accessed플래그가 1로 설정된 경우(!page.oldref && PTE.accessed == 1) page.ref유지, accessed플래그 해제하고 INACTIVE list의 MRU로 이동시켜 second chance 제공

    3. activate

       페이지가 참조되고 있고 pte의 accessed플래그가 1로 설정된 경우(page.oldref && PTE.accessed == 1) or PTE.accessed > 2 or vma가 실행 가능, 파일영역에 존재, pte의 accessed플래그가 설정된 경우 page.ref유지, accessed플래그 해제하고 ACTIVE list의 MRU로 이동시켜 second chance 제공

accessed flag 조작 함수

• page.ref
  • mark_page_accessed() : 페이지에 file api에 의해 접근되었을 때page.ref조작하는 함수
  • page_referenced() : 해당 페이지를 참조하는 pte 중 accessed 플래그가 세팅된 플래그의 갯수 반환
    reclaim되는 동안 해당 함수의 반환값이 많을 경우 second chance 얻음

mark_page_accessed() 동작

함수 호출 전	INACTIVE list page.ref == false	INACTIVE list page.ref == true	ACTIVE list page.ref == false	ACTIVE list page.ref == true
함수 호출 후	INACTIVE list page.ref == true	ACTIVE list page.ref == false	ACTIVE list page.ref == true	ACTIVE list page.ref == true

1.3.1 Refault Distance Implementation

• page fault handler는 해당 페이지를 INACTIVE list, ACTIVE list에 넣을지 결정

  • ACTIVE list : Refault distance < size(ACTIVE + INACTIVE)
  • INACTIVE list : cold page, Refault distance > size(ACTIVE + INACTIVE)

Refault distance

• 해당 페이지가 얼마나 LRU list에 존재했는지 나타내는 단위 (aging의 단위)

• 페이지는 새로운 페이지가 LRU list에 추가될 때마다 밀려나며 밀려난 거리가 얼마나 오래 LRU list에 존재했는지를 나타낸다고 할 수 있음

• Refault distance : 페이지가 INACTIVE list에 상주한 시간과 메모리에서 추방된 시간의 합
  (INACTIVE list의 길이 + Refault가 된 시점에서 위치 - INACTIVE list로부터 밀려난 거리)

• 만약 Refault distance가 size(ACTIVE + INACTIVE)보다 크면 자주 fault되지 않는다는 의미고 따라서 INACTIVE list에 두는 것이 효율적임

• 메모리에서 추방된 페이지는 radix tree에서 제거되고 그 위치에 추방된 시점을 기록해 메모리에서 추방된 시간의 합을 구할 때 사용

1.3.2 Reclaim Type

• try_to_free_page() : Watermark_min이하로 유휴 페이지 수가 줄어들 때

  • 필요하면 write-back 수행
  • 유휴 페이지 수 확보되면 멈춤

• kswapd : low_watermark이하로 유휴 페이지 수가 줄어들 때

  • 모든 zone의 유휴 페이지 수 균형있게 관리
    (balance_pgdat()에서 shrink_node_memcgs() 호출)

• mode_reclaim() :

  • zone의 유휴 페이지 수 확보하기 위해 해당 zone의 페이지 reclaim

2. Reclaim 흐름

2.1 try_to_free_page()

2.2 kswapd()

1. 조작할 메모리 node와 회수 크기를 결정하는 pg_data_t alloc_order값을 인자로 받고 alloc을 위한 zone index(new_classzone_idx)설정

2. alloc_order > last-balance-order, new_classzone_idx < last-balance-idx인 경우2.1, 아니면 2.2 분기

   2.1 balance_pgdat()호출 해 모든 zone을 균형있게 관리

   2.1.1  각 zone별로 Watermark_HIGH 만족(order보다 큰 페이지 확보)할때 까지 반복적으로 kswapd_shrink_node() 호출 
   (nr_to_scan = nr_lru_pages/2^priority)
    2.1.2 priority < 10일 시 write-back하고 dirty page 회수 시도 
    2.1.3 zone의 처음부터 끝까지 `kswapd_shrink_node()` 수행
    2.1.4 성공 시 페이지 할당을 기다리는 프로세스 wakeup
    2.1.5 계속 실패 시 scan priority를 줄여(scan할 page 증가) 재시도

   2.2 kswapd_try_to_sleep()를 호출해 kswapd() sleep 상태로 전환 시도

2.2.1 kswapd_shrink_node()

1. sc->nr_to_reclaim의 데이터 변경해 확인할 페이지 갯수 설정
2. shrink_node()을 통해 페이지 확인 실행
   3.1 스캔해 찾아낸 페이지 수가 reclaim할 페이지 수보다 많으면 true 리턴, 아니면 false (priority 높임)
   3.2 만약 필요 페이지 크기보다 2배 크기 확보 시 order을 0으로 수정해 다시 수행

2.2.2 shrink_node()

• 페이지 확인을 위한 정책 결정

  • deactivate_anon

    INACTIVE_ANON의 페이지 수가 적고 file refault가 발생 시 ACTIVE_ANON에서 demotion 수행하도록 설정

  • deactivate_file

    INACTIVE_FILE의 페이지 수가 적고 anon refault가 발생 시 ACTIVE_FILE에서 demotion 수행하도록 설정

  • cache_trim_mode

    INACTIVE_FILE 의 페이지 수가 많으면 해당 리스트에서 페이지 인출해 페이지를 확보하도록 설정

  • file_is_tiny

    FILE list+유휴 페이지 < Watermark_high && INACTIVE_ANON의 갯수가 2^priority보다 크면 ANON list에서 페이지 확보하도록 설정

• 이후 shrink_node_memcgs() 호출
  • root_memcg라는 그룹의 각 멤버들에 대해서 shrink_lruvec() 수행

2.2.3 shrink_lruvec()

1. nr[4] = get_scan_count()( [INACTIVE_ANON, ACTIVE_ANON, INACTIVE_FILE, ACTIVE_FILE])를 통해 확인할 리스트 및 확인할 비율 결정

   • 각 lru마다 총 몇 개의 페이지를 확인할지 결정
   • swap_device가 없거나 cache_trim_mode인 경우 FILE list만 확인
   • FILE list의 페이지 수가 작으면 `ANON_list만 확인
   • 둘 다 확인할 경우에는 swappiness에 맞춰 페이지 선정
     (100 -> 1:1, 60 -> 3:7)

2. shrink_list()를 통해 shrink_active_list() 수행, reclaim된 페이지 갯수 확인

3. 갯수 충족 시 남은 회수 작업 마치고 미충족 시 다시 수행

2.2.3.1 shrink_active_list()

• ACTIVE list에서 INACTIVE list로 demotion 수행

2.3 Inactive LRU

• PTE mapping 되어있는 페이지 (Page fault handler를 통해 들어오는 페이지)
• PTE mapping이 없거나 (file I/O를 통해 들어오는 페이지) address space mapping이 없는 페이지
• File-backed page 중 page.ref가 0이나 1인 페이지

page.ref setting

• file-backed page만 page.ref 설정 가능
• mark_page_accessed()될 때 수행
• INACTIVE-reclaim을 통해 다시 돌아온 페이지에 대해 수행 (page_check_references())

page.ref clear

• 처음 LRU list에 삽입된 페이지들에 대해 수행
• INACTIVE-reclaim을 통해 다시 돌아온 페이지 (page_check_references())

2.3.1 shrink_inactive_list()

1. isolate_lru_pages() 호출해 리스트 LRU위치의 페이지를 고립된 linked list에 저장해 관리

2. shrink_page_list() 호출해 고립된 linked list의 페이지 회수 실행

   • reclaim, reclaim-clean, keep-active 동작 결정
   • reclaim 시 페이지를
   • keep-active시 putback_inactive_lists()호출 해 LRU list 복귀

2.3.1.1 shrink_page_list()

1. page_check_references()를 통해 페이지가 pte에 의해 참조되는지 확인

   • page_referenced()를 통해 해당 페이지가 몇개의 pte에 의해 참조되는지 확인
   • page.ref를 확인하고 초기화

2. 페이지가 참조되는 카운트가 1 이상일 때 2.1 아니면 2.2

   2.1 SetPageReferenced()을 통해 page.ref 세팅, 이전에 참조되었는지 확인(old_ref), 참조되는 횟수가 2 이상일 때 또는 VM_EXECflag 세팅되어 있을 때 ACTIVATE 아니면 Keep

   2.2 reclaim 수행

3. add_to_swap() 호출

   • dirty한 anonymous page이고 swap_cache에 없을 경우 swap_cache에 삽입
   • swap device를 위한 공간 할당
   • page->private에 swap_entry 저장, dirty 플래그 세팅

4. try_to_unmap()을 통해 페이지를 참고하는 pte unmmap

5. 해당 페이지가 dirty일 경우

   • kswapd일 경우 write-back 수행
   • VM page일 경우 pageout()(write-back & clean)수행

6. __remove_mapping() 호출해 page/swap cache에서 제거, shadow entry에 삽입 (Refault distance계산 위함)

7. reclaimed된 페이지를 buddy system에 반납, KEEP, ACTIVE인 경우 해당하는 LRU list로 보냄

2.4 Unmap PTE

• try_to_unmap() : 페이지를 가리키는 pte의 내용 제거
  1. rmap_walk_anon() : anonymous page를 인자로 받았을 때 anon_vma->rb_root을 통해 vma 찾아 작업 수행
  2. rmap_walk_file() : page->mapping->i_mmap을 통해 interval tree를 찾아 작업 수행

---

---