[운영체제] Virtual Memory

soyoung·2025년 5월 25일
OS
0

1. Virtual Memory

  • Seperation of user logical memory from physical memory
  • 실행에 필요한 일부만 메모리에 올라가도 된다
  • 장점
    • 주소 공간 공유 가능
    • 여러 프로세스가 동시에 실행 가능
    • 효율적인 프로세스 생성
    • 입출력(I/O) 감소

2. Virtual Address Space

  • Virtual Address Space: 프로세스가 메모리에 어떻게 저장되는지에 대한 논리적 관점
  • MMU(Memory Management Unit): 논리 주소를 물리 주소로 매핑
  • 구현 방법
    • Demand Paging
    • Demand Segmentation

3. Demand Paging

  • 페이지를 메모리에 필요할 때만 불러오는 방식
  • 페이지가 참조될 때 → 존재하지 않으면 → 페이지 폴트
    페이지가 메모리에 없으면 디스크에서 불러옴
  • 기존의 페이징 시스템과 유사하지만, lazy swapper 개념 도입: 페이지가 필요할 때만 메모리에 로드
    • 이 작업을 수행하는 스왑퍼는 pager

Demand Paging with Valid-Invalid Bit

  • 페이지 테이블의 각 항목에 valid-invalid 비트 존재
    • v: 페이지가 메모리에 O
    • i: 페이지가 메모리에 X
  • 주소 변환 과정에서 해당 비트가 i일 경우 → Page Fault

4. Handling Page Fault

  1. 프로세스가 페이지를 참조하면 → 존재 여부 확인
  2. 페이지 폴트 발생 시,
    • 잘못된 참조라면 → 프로세스 종료
    • 단순히 메모리에 없는 경우 → 다음 단계로 진행
  3. 빈 프레임을 찾음
  4. 디스크에서 해당 페이지를 읽어 프레임에 적재
  5. 테이블 업데이트 → 유효 비트(v) 설정
  6. 페이지 폴트를 일으킨 명령어를 재실행

5. Performance of Demand Paging

  • Page Fault Rate (페이지 폴트율):

    0≤p≤10 \leq p \leq 1
    • p=0p = 0: 페이지 폴트 없음
    • p=1p = 1: 모든 메모리 접근이 페이지 폴트 발생

  • EAT (Effective Access Time, 유효 접근 시간):

    EAT=(1−p)×memory access time+p×(page fault overhead+swap out+swap in)EAT = (1 - p) \times \text{memory access time} + p \times (\text{page fault overhead} + \text{swap out} + \text{swap in})

Copy-on-Write (COW)

  • 부모와 자식 프로세스가 처음에는 메모리 페이지를 공유함
  • 어느 쪽이든 공유된 페이지를 수정하려 하면 그 시점에서 복사 발생
  • 예시:
    • Process1과 Process2가 페이지 C를 공유하다가
    • Process1이 수정 → 해당 페이지 복사 발생

Free-Frame List

  • Free-frame list: 페이지 폴트 발생 시 디스크에서 메모리로 페이지를 가져오기 위해 사용 가능한 프레임들의 목록
  • 운영체제는 일반적으로 zero-fill-on-demand 방식 사용:
    • 새 프레임 할당 전에 프레임 내용을 0으로 초기화
  • 시스템 시작 시 모든 사용 가능한 프레임이 이 목록에 등록

6. Page Replacement

  • 빈 프레임이 없을 경우, 메모리에 존재하지만 당장 사용되지 않는 페이지를 교체(Page Replacement) 해야 함
  • 교체 알고리즘이 어떤 페이지를 제거할지 결정
  • 목표: 페이지 폴트 수를 최소화하는 알고리즘 사용
  • Dirty bit(변경 비트) 사용으로 불필요한 디스크 쓰기 줄일 수 있음

Basic Page Replacement

  1. 디스크에서 원하는 페이지의 위치를 찾음
  2. 빈 프레임 존재 여부 확인
    • 있다면 그대로 사용
    • 없다면 교체 알고리즘으로 victim frame 선택
    • dirty page일 경우 디스크에 기록
  3. 원하는 페이지를 빈 프레임에 로드하고, 페이지 및 프레임 테이블 갱신
  4. 페이지 폴트를 일으킨 명령어 재시작

이 과정에서는 페이지 교체를 위한 디스크 전송이 최대 2번 발생할 수 있음

Page Replacement Algorithms

  • 프레임 할당 알고리즘: 각 프로세스에 몇 개의 프레임을 할당할지 결정
  • 페이지 교체 알고리즘: 어떤 프레임을 교체할지 결정
  • 알고리즘은 참조 문자열(reference string) 을 통해 평가됨
    • 참조 문자열은 단순히 페이지 번호들의 나열
    • 결과는 사용 가능한 프레임 수에 따라 달라짐

1. FIFO Page Replacement

  • 가장 먼저 들어온 페이지를 가장 먼저 교체
  • FIFO 큐를 사용하여 페이지의 삽입 순서를 추적
  • Belady’s Anomaly 발생 가능
    • 프레임 수를 늘렸는데 오히려 페이지 폴트가 증가하는 현상

2. Optimal Page Replacement

  • 가장 오래 동안 사용되지 않을 페이지를 교체
  • 이상적인 방식이지만, 미래를 알 수 없으므로 실제 적용 불가
  • 주로 다른 알고리즘 성능 평가의 기준선으로 사용

3. LRU (Least Recently Used) Page Replacement

  • 가장 오랫동안 사용되지 않은 페이지를 교체
  • 과거의 접근 기록을 기반으로 결정
  • 실제로 OPT보다는 성능이 떨어지지만, FIFO보다는 우수
  • 일반적으로 자주 사용되는 실용적인 알고리즘

4. LRU Approximation Algorithms

▪ Reference Bit 방식

  • 페이지마다 1비트 참조 비트 할당
  • 접근되면 비트 = 1, 주기적으로 0으로 초기화
  • 비트가 0인 페이지 우선 교체

▪ Second-Chance (Clock) Algorithm

  • FIFO 방식에 참조 비트 추가
  • 교체 대상이 참조 비트 = 1이면 비트를 0으로 하고 기회 한 번 더 줌
  • 비트가 0일 때 교체 수행 → ‘시계 바늘’ 방식으로 순환 검사

7. Thrashing

Global vs Local Replacement

  • Global Replacement
    • 모든 프레임 중에서 교체할 프레임을 선택
    • 다른 프로세스의 프레임도 교체 대상이 될 수 있음
      → 처리량(throughput)은 증가하지만, 개별 프로세스 성능은 불안정해질 수 있음
  • Local Replacement
    • 각 프로세스는 자신에게 할당된 프레임만 교체
      → 개별 성능은 일정하지만, 시스템 전체의 메모리 활용은 비효율적일 수 있음

Thrashing

  • Thrashing이란?
    • 프로세스가 지속적으로 페이지를 반복해서 교체(swap in/out)하는 상황
      → 페이지 폴트가 매우 자주 발생하고 CPU 사용률이 급감
  • 왜 발생하는가?
    • 운영체제가 CPU 사용률이 낮다고 판단해 멀티프로그래밍 수준을 높이면서 발생
    • 결과적으로 전체 메모리 요구량이 실제 물리 메모리보다 커짐

Working-Set Model

  • Locality의 개념을 기반으로 함
    • 프로세스는 특정 시간 구간 동안 일정한 페이지 집합(locality) 을 집중적으로 사용
  • Δ (working-set window): 최근 몇 번의 페이지 참조를 기준으로 함 (예: 10,000 instruction)
  • WSSi: 프로세스 Pi의 working set size = Δ 구간 내 참조한 페이지 수
  • Δ에 따른 영향
    • Δ가 너무 작으면 → locality를 포괄하지 못함
    • Δ가 너무 크면 → 여러 locality를 포함하여 정확도 감소
    • Δ = ∞이면 → 전체 프로그램을 포함
  • D = Σ WSSi: 전체 시스템의 프레임 수요
    • D > m (총 물리 프레임 수) → Thrashing 발생

Page-Fault Frequency (PFF)

  • Page Fault Rate를 기준으로 동적으로 프레임 조절
    • 페이지 폴트율이 너무 낮으면 → 프레임 회수
    • 페이지 폴트율이 너무 높으면 → 프레임 추가
  • Working Set Model보다 직접적이고 실용적인 접근 방식

8. Allocating Kernel Memory

  • 커널 메모리는 사용자 메모리와 다르게 관리되며, 연속된 물리 메모리가 필요한 경우가 많음 (예: 디바이스 I/O).
  • 다양한 크기의 커널 자료구조를 위해 유연하고 빠른 메모리 할당 방식이 필요
  • 주로 free-memory pool에서 할당되며, 이를 위한 대표적 방식이 Buddy System과 Slab Allocator

Buddy System Allocator

  • 연속된 메모리 블록을 2의 거듭제곱 크기 단위로 나누어 할당
  • 메모리 요청 시, 요청 크기보다 큰 가장 작은 2의 거듭제곱 블록을 찾아 할당
  • 남는 블록은 두 개의 buddy로 나누고, 필요할 때까지 재귀적으로 분할
  • 메모리 해제 시, 인접한 buddy가 모두 free라면 즉시 병합(coalesce) 하여 더 큰 블록으로 복구 가능

  • 예시

    256KB 블록 중 21KB 요청 시:
    → 256 → 128 → 64 → 32KB로 분할되어 32KB 블록이 할당됨

  • 장점: 빠른 병합과 분할, 구현 간단

  • 단점: 할당 단위가 고정되어 내부 단편화 발생 가능성 O

Slab Allocator

  • 슬랩(slab): 하나 이상의 연속된 페이지로 이루어진 메모리 덩어리
  • 같은 종류의 커널 자료구조마다 캐시(cache)를 따로 유지하며, 슬랩 안에는 해당 구조체 객체들이 여러 개 들어 있다
  • 구조체 요청이 들어오면 미리 할당된 객체를 바로 할당 (동적 생성 아님)
  • 구조체 반납 시에는 객체를 free 상태로만 표시, 슬랩은 그대로 유지
  • 슬랩 상태:
    1. Full – 모든 객체 사용 중
    2. Partial – 일부 사용, 일부 여유
    3. Empty – 전부 free 상태
  • 장점:
    • 단편화 없음, 빠른 할당/해제
    • 객체 재사용으로 초기화 비용 감소

Slab Allocator in Linux

  • 예시: struct task_struct (프로세스 생성 시 사용되는 커널 구조체)
  • 새로운 태스크 생성 시:
    • Partial 슬랩에 여유 객체가 있으면 → 바로 사용
    • 없으면 Empty 슬랩에서 사용
    • 그것도 없으면 새 슬랩 생성
  • 이 방식은 성능, 메모리 활용, 캐시 효율성 측면에서 매우 효과적이므로 리눅스 커널의 주요 메모리 할당기로 사용
profile
soyoung
이전 포스트

[운영체제] Main Memory

다음 포스트

[논문 리뷰] Can Large Language Models Replace Data Scientists in Biomedical Research?

0개의 댓글