1. 리눅스 운영체제에서 메모리 관리

VMA(Virtual Memory Area)

• VMA 정의
  • 프로세스의 가상 메모리 공간은 여러 영역(VMA)으로 나뉘며 영역은 특정 속성(읽기, 쓰기, 실행 가능 여부 등)
• VMA 구조
  • VMA는 주소를 기준으로 레드-블랙 트리(Red-Black Tree) 구조로 관리
  • 트리를 통해 특정 주소가 속한 VMA를 빠르게 파악

페이지 폴트(Page Fault) 처리 과정

• 문제 발생
  • CPU가 메모리 접근 시 해당 주소에 대한 매핑이 없거나 권한이 없을 경우 페이지 폴트가 발생
• VMA 검색
  • 페이지 폴트 발생 시 커널은 주소가 속한 VMA 파악
  • 검색 결과
    • VMA 존재
      • 해당 VMA의 속성을 확인 후 적절히 처리
    • VMA 없음
      • 접근하려는 주소가 어떤 VMA에도 속하지 않으면 프로세스에 SEGFAULT 신호 전송

메모리 매핑 구조

• 가상 메모리
  • 프로세스가 사용하는 논리적 주소 공간
  • 이 공간은 물리적 메모리가 아닌 페이지 테이블(Page Table)을 통해 물리적 메모리에 매핑
• 페이지 테이블
  • 가상 주소를 물리적 주소로 변환하는 데이터 구조
  • 페이지 디렉토리는 페이지 테이블을 관리하는 상위 계층

SRWX 속성

• VMA는 SRWX 속성
  • S
    • 공유 가능(Shared)
  • R
    • 읽기(Read)
  • W
    • 쓰기(Write)
  • X
    • 실행 가능(eXecute)

2. 요구 페이징 개념

기본개념

• 동작 원리
  • 페이지는 실제로 참조될 때까지 메모리에 로드되지 않음
  • 페이지 폴트가 발생하면 필요한 페이지를 메모리에 로드
• 장점
  • 메모리 공간 절약
  • 초기 로딩 시간을 단축
  • 메모리 사용을 최적화하고 불필요한 메모리 할당을 방지하여 시스템의 성능을 향상
  • 페이지 폴트가 발생할 때만 페이지를 메모리에 로드하므로 초기 메모리 사용량을 줄이고 프로세스의 실행 속도를 높이는 데 기여

페이지 폴트 처리 과정

1. 파일 기반 페이지
   • 페이지 캐시에서 해당 페이지를 검색
   • 페이지 캐시에 없으면 파일 I/O를 통해 디스크에서 읽기
2. 스왑 아웃된 페이지
   • 스왑 캐시에서 페이지를 검색
   • 스왑 캐시에 없으면 스왑 영역에서 읽기
3. 익명 페이지
   • 로드되지 않은 BSS, 힙, 스택과 같은 영역에 대해 제로 페이지를 사용하거나 Copy-on-Write 방식으로 처리

성능 최적화를 위한 Read-ahead

• 메이저 폴트
  • 디스크 I/O를 동반하는 경우 발생
  • swapin_nr_pages()를 사용해 최대 8개 페이지를 한 번에 읽기
  • 파일 기반 페이지는 최대 32개까지 Read-ahead 수행
• 마이너 폴트
  • 바이트(fault_around_bytes)를 미리 읽어오는 방식으로 처리

요구 페이징과 캐시

• 파일에서 읽어온 페이지는 페이지 캐시에 저장
• 스왑 디바이스에서 읽어온 페이지는 스왑 캐시에 저장
• 익명 페이지는 anon_vma 구조체와 연결

페이지 교체 시스템과 협력

• 요구 페이징은 LRU(Least Recently Used) 기반의 페이지 교체 시스템과 협력하여 동작
  • 파일 또는 스왑에서 가져온 페이지는 ACTIVE 또는 INACTIVE LRU 리스트에 추가
  • 처음 로드된 페이지는 기본적으로 INACTIVE 리스트에 추가되며 자주 사용되지 않는 경우 빠르게 제거(2Q 정책)

3. PTE 플래그/필드

• Present
  • 페이지가 메모리에 존재하는지 여부
• Writable
  • 페이지가 쓰기 가능한지 여부
• User
  • 페이지가 사용자 모드에서 접근 가능한지 여부
• Referenced
  • 페이지가 최근에 참조되었는지를 나타내며, 페이지 교체 알고리즘에 사용
• Dirty
  • 페이지가 수정되었는지를 나타내며, 스왑 아웃 시 디스크에 기록

4. 커널 캐시의 struct pages

• 리눅스 커널에서는 페이지를 관리하기 위해 struct page라는 자료구조를 사용
• 페이지의 상태, 참조 카운트, 플래그 등을 포함하여 페이지의 메모리 관리를 지원
• 커널 캐시는 페이지의 재사용을 최적화하기 위해 페이지를 캐시하고 필요할 때 빠르게 접근

5. 페이지 캐시

개념

• 파일 시스템과 디스크 I/O 성능을 최적화하기 위해 사용
• 구조는 디스크에서 데이터를 읽거나 쓰는 대신 메모리에 저장된 데이터를 재사용할 수 있도록 설계

구성 요소 및 동작

• struct address_space
  • 파일(또는 inode)은 고유한 페이지 캐시를 가짐
  • 구조체는 파일과 관련된 페이지를 추적
  • Radix Tree 또는 Xarray를 사용하여 페이지를 인덱싱
    • Radix Tree
      • 효율적인 트리 기반 데이터 구조로 페이지를 빠르게 검색
• 페이지 폴트(Page Fault) 처리
  • 프로세스가 메모리에 없는 페이지에 접근하려고 하면 페이지 폴트가 발생
    • pte_none()
      • 페이지 테이블 엔트리가 존재하지 않음
    • pte_present()
      • 페이지가 이미 메모리에 있음
  • 커널은 디스크 I/O를 줄이기 위해 먼저 페이지 캐시를 확인
    • 페이지가 캐시에 있으면 바로 반환
    • 없으면 디스크에서 데이터를 읽어와 페이지 캐시에 저장
• 페이지와 PTE(Page Table Entry)
  • 물리적 페이지는 여러 개의 PTE(Page Table Entry)가 참조하거나 아무도 참조하지 않을 수 있음
  • 공유 메모리 또는 파일 매핑에서 발생할 수 있는 구조

• inode
  • 파일의 메타데이터
• Address Space
  • 파일의 모든 페이지를 관리하는 공간
• Radix Tree(또는 Xarray)
  • 파일의 특정 오프셋에 해당하는 페이지를 찾기 위한 데이터 구조
• Pages
  • 데이터가 저장된 물리적 메모리 블록

5. Reverse Mapping

• 운영체제 메모리 관리에서 페이지 프레임이 어떤 프로세스의 가상 메모리 영역(VMA, Virtual Memory Area)과 연결되어 있는지 추적 하는 개념

Reverse Mapping의 필요성

• 페이지와 프로세스 간 매핑 추적
  • 물리적 페이지 프레임(Page Frame)이 여러 프로세스의 가상 메모리 영역(VMA)에 공유
    • fork() 호출 시 부모와 자식 프로세스가 동일한 페이지를 공유
• 효율적인 메모리 관리
  • 페이지 교체(swap-out) 시 페이지를 참조하는 모든 Page Table Entry(PTE)를 찾기
• 구조체 크기 제한
  • struct page의 크기를 작게 유지해야 하므로 모든 매핑 정보를 직접 저장하지 않고 효율적으로 관리

익명 페이지(Anonymous Pages)

• 파일과 무관하게 동적 메모리 할당이나 스택에서 사용
• Reverse Mapping을 위해 anon_vma 구조 사용
  • anon_vma는 VMA들을 연결(link)하여 특정 페이지가 어떤 VMA와 연결되어 있는지 추적
  • 이전에는 anon_vma_chain이 사용되었으나 더 효율적인 anon_vma interval tree가 사용
  • page->anon_vma와 page->index를 이용해 PTE를 찾을 수 있음

파일 매핑 페이지(File-mapped Pages)

• mmap() 호출로 공유되며 파일 오프셋을 기준으로 매핑
• Reverse Mapping을 위해 VMA Interval Tree 사용
  • 동일한 파일에 대해 여러 VMA를 관리하며 VMA는 파일의 시작 오프셋에 정렬
  • 파일 오프셋을 키로 사용하여 관련 VMA를 효율적으로 찾기

struct address_space

• 파일 매핑을 위한 자료구조(파일의 페이지 캐시와 관련된 정보를 포함)
• 파일의 페이지를 관리하고 페이지 폴트 발생 시 필요한 페이지를 로드하는 데 사용

struct anon_vma

• 익명 페이지를 위한 자료구조로 스택, 힙, BSS와 같은 메모리 영역을 관리
• 익명 페이지는 파일에 매핑되지 않은 페이지로 프로세스가 동적으로 할당한 메모리

6. 페이지 폴트 핸들러

페이지 폴트의 종류

• Major Fault
  • 디스크 I/O가 필요한 경우 발생
    • 디스크에서 스왑 영역이나 파일을 읽어와야 할 때
• Minor Fault
  • 디스크 I/O가 필요하지 않은 경우 발생
    • 익명 메모리
      • 유효한 메모리 영역이지만 페이지 프레임이 없는 경우
        • 0으로 초기화된 페이지 프레임을 할당
    • 파일/스왑 기반 페이지
      • 페이지 캐시나 스왑 캐시에서 이미 존재하는 페이지를 찾기
    • 읽기 전용 페이지에 쓰기 요청
      • Copy-On-Write(COW) 처리를 통해 복사본을 생성하거나 권한 문제가 있으면 SIGSEGV 오류를 발생

핸들러 함수의 구조

• handle_mm_fault()
  • 기능
    • 페이지 테이블 엔트리(PTE) 및 상위 디렉토리(p4d, pud, pmd)가 없으면 할당
    • 가상 주소에 해당하는 페이지 테이블 엔트리를 가져옴
    • Transparent Huge Pages(THP) 관련 작업을 확인하고 우회
    • 최종적으로 handle_pte_fault()를 호출
• handle_pte_fault()
  • PTE 상태에 따라 분기 처리
    • pte_none
      • PTE가 비어 있으면 Cold Miss로 간주하며 익명 페이지(do_anonymous_page()) 또는 파일 매핑(do_fault())을 처리
    • pte_present
      • PTE가 이미 존재하지만 보호 권한이 부족하면 Protection Fault로 간주
    • pte_protnone
      • 보호 플래그가 누락된 경우 권한 오류로 처리
      • 쓰기 요청 시 Copy-On-Write(COW) 또는 적법한 쓰기 여부를 확인하여 처리
• do_read_fault()
  • 파일 매핑 및 PTE가 비어 있는 경우(pte_none)에 호출
  • 기능
    • find_get_page()로 페이지 캐시에서 해당 페이지를 찾기
    • 존재하지 않으면 디스크 I/O를 통해 데이터를 리딩(do_sync_mmap_readahead())
    • 읽어온 데이터를 활성/비활성 LRU 리스트에 추가하고 PTE 매핑을 설정
  • 페이지 폴트가 발생하면 커널은 페이지 폴트 핸들러를 호출하여 필요한 페이지를 메모리에 로드

7. 페이지 교체 알고리즘

개념

• 메모리가 가득 찼을 때 어떤 페이지를 제거할지를 결정하는 방법
  • LRU(Least Recently Used)
    • 가장 오랫동안 사용되지 않은 페이지를 제거
    • 페이지의 참조 시간을 기록하여 가장 오래된 페이지를 찾음
  • FIFO(First In, First Out)
    • 가장 먼저 들어온 페이지를 제거
    • 페이지가 메모리에 로드된 순서를 기반
  • Optimal
    • 미래에 가장 오랫동안 사용되지 않을 페이지를 제거
    • 이론적으로 가장 효율적이지만 실제로는 미래의 참조를 예측할 수 없기 때문에

add_to_page_cache_lru 함수

• 페이지를 페이지 캐시에 추가하고 적절한 LRU 리스트(활성 또는 비활성)에 삽입
• 코드 분석
  1. __SetPageLocked(page)
     1. 페이지를 잠금 상태로 설정
  2. __add_to_page_cache_locked(...)
     1. 페이지를 실제로 캐시에 추가
  3. Shadow 체크
     • shadow는 최근에 제거된 페이지의 정보를 가리킴
     • workingset_refault(shadow) 호출
       • 접근한 페이지가 "refault distance"(재접근 거리) 내에 있다면 이 페이지는 워킹셋(자주 사용되는 데이터 집합)에 속한다고 간주
       • 페이지는 활성 리스트로 이동
  4. LRU 리스트 업데이트
     • lru_cache_add(page) 호출
       • 페이지를 활성(Active) 또는 비활성(Inactive) 파일 LRU 리스트에 추가

LRU 리스트 구조

• Physical Memory(물리 메모리)
  • File Active List(파란색 상자)
    • 자주 사용되는 페이지들이 포함
    • MRU(Most Recently Used)에서 LRU (Least Recently Used) 순서로 정렬
  • File Inactive List(빨간색 상자)
    • 덜 사용된 페이지들이 포함
    • 리스트의 끝(LRU)은 제거(Evict) 대상
• File Shadow List(가상 메모리)
  • 물리 메모리에서 제거된 페이지들의 "메타데이터"가 저장
  • Shadow 리스트의 크기는 활성 리스트 크기와 동일
  • 제거된 페이지가 refault 거리 내에 다시 접근된다면 워킹셋에 속한다고 판단되어 활성 리스트로 복구

작동 원리

• 페이지 접근 시
  • 페이지가 이미 물리 메모리에 있다면 해당 LRU 리스트에서 위치가 갱신
  • 물리 메모리에 없는 경우(페이지 폴트) shadow 리스트를 확인하여 refault 여부를 판단
• Refault Distance
  • 접근한 페이지와 마지막으로 접근했던 시점 간의 거리
  • 이 거리가 워킹셋 크기보다 작으면 해당 페이지는 활성 리스트로 이동
• Eviction(제거)
  • 비활성 리스트의 끝(LRU)에 있는 페이지는 메모리가 부족할 때 제거

8. 최적화 기법 및 디버깅

• 페이지 크기 조정
  • 페이지 크기를 조정하여 페이지 폴트 발생률 감소
  • 큰 페이지를 사용하면 페이지 테이블의 크기를 줄이고 페이지 폴트 발생 시 더 많은 데이터를 한 번에 로드
• 프리페칭
  • 예상되는 페이지를 미리 로드하여 페이지 폴트를 줄이는 기법
  • 프로세스의 접근 패턴을 분석하여 자주 사용되는 페이지를 미리 로드
• 디버깅 도구 사용
  • perf, ftrace, gdb와 같은 도구를 사용하여 페이지 폴트 발생 원인을 분석하고 성능 병목 현상
  • 도구는 페이지 폴트 발생 시점과 관련된 정보를 제공하여 문제를 해결하는 데 도움

9. 결론

리눅스 운영체제의 메모리 관리 시스템은 요구 페이징과 효율적인 페이지 교체 알고리즘을 통해 메모리 자원을 최적화하고 성능을 유지합니다. VMA구조와 Reverse Mapping을 활용하여 프로세스와 물리적 메모리 간의 관계를 효율적으로 관리하며 페이지 캐시와 LRU 기반 교체 알고리즘은 디스크 I/O를 최소화하고 응답성을 향상시킵니다.