투기장

10 Virtual Memory (1)

14 min read

1. Background

1.1 Logical Address Space의 크기

  • 프로세스의 Logical address space는 text, data, heap, stack으로 구성
  • Stack은 위에서 아래로, Heap은 아래에서 위로 성장하며, 사이에 큰 빈 공간(hole)이 존재

  • 32-bit 주소 사용 시: max = 2^32 - 1 - 프로세스당 4 GB의 Logical address space
  • 이 중 대부분은 실제로 사용되지 않음 (A large portion of the address space is unused)

1.2 Virtual Memory 개념

Virtual memory: Logical memory를 Physical memory로부터 분리(separation)하는 기법

  • 프로그램의 일부분만 메모리에 올려도 실행 가능
  • Logical address space가 Physical address space보다 훨씬 클 수 있음
  • 여러 프로세스가 Address space를 공유 가능
  • 프로세스 생성이 더 효율적
  • Page를 필요에 따라 Swap in/out 해야 함

1.3 Virtual Memory 구현 방식

구현 방식설명
Demand pagingPage 단위로 필요할 때만 메모리에 적재
Demand segmentationSegment 단위로 필요할 때만 메모리에 적재

2. Demand Paging

2.1 기본 개념

Page가 필요할 때만(when it is needed) 메모리에 적재하는 방식.

장점:

  • I/O 감소
  • 메모리 사용량 감소
  • 응답 시간 단축
  • 더 많은 사용자 수용 가능

Page 참조 시 동작:

  • Invalid reference - abort (잘못된 참조)
  • Not-in-memory - bring to memory (디스크에서 가져옴)

2.2 Lazy Swapper (= Pager)

  • 해당 Page가 필요하지 않으면 절대 Swap in하지 않음
  • Page 단위로 Swap을 다루는 Swapper를 Pager라고 부름

3. Valid-Invalid Bit

각 Page table entry에 Valid-invalid bit가 연결됨:

비트 값의미
Valid (v)해당 Page가 메모리에 존재(in-memory)
Invalid (i)(1) Illegal: 프로세스의 Address space에 속하지 않는 Page, (2) Not-in-memory: 디스크에서 아직 로드되지 않음, (3) Obsolete: 디스크에서 가져왔으나 원본(디스크)이 갱신됨
  • 초기에는 모든 entry가 invalid로 설정
  • 주소 변환 시 Page가 invalid이면 - Page fault 발생

3.1 일부 Page만 메모리에 있는 경우

  • Logical memory의 Page 0~7 중 Page 0, 2, 5만 Physical memory에 존재 (valid)
  • Page 1, 3, 4, 6, 7은 디스크(Backing store)에 있음 (invalid)

4. Page Fault 처리

4.1 Page Fault 발생 과정

Invalid page에 대한 접근 시 HW(MMU)가 Page fault trap을 발생시킴.

4.2 Page Fault 처리 단계

  1. Reference: 프로세스가 메모리 참조 (load M)
  2. Trap: Page table에서 invalid bit 확인 - OS에 Page fault trap 전달
  3. Page is on backing store: OS가 디스크에서 해당 Page의 위치를 확인
  4. Bring in missing page: 디스크에서 Page를 읽어 Free frame에 적재
    • 이 동안 프로세스는 Wait 상태
  5. Reset page table: Page table entry 갱신 (Frame 번호 기록, Valid/invalid bit - valid)
    • 프로세스를 Ready queue로 이동
  6. Restart instruction: CPU가 다시 할당되면 Page fault를 일으킨 명령어를 재실행

4.3 OS의 Page Fault 처리 상세

1. OS가 다른 테이블을 확인하여 판단:
   - Illegal reference? (잘못된 주소, Protection violation)
     -> abort process
   - Not in memory?
     -> 계속 진행

2. Empty page frame 확보
   - Free frame이 없으면 -> Page replacement!

3. 디스크에서 Page를 Frame으로 읽어들임
   - 디스크 I/O 완료까지 Wait 상태
   - I/O 완료 후 Page table 갱신

4. 프로세스를 Ready queue로 이동

5. Page fault를 일으킨 명령어 재시작

5. Page Fault 처리의 HW 설계상 어려움

5.1 Page Fault 발생 시점에 따른 문제

발생 시점처리
Instruction fetch 시문제 없음 (단순히 명령어 재시작)
Operand fetch 시Instruction fetch, Decode, Operand fetch를 다시 수행해야 함
명령어가 여러 위치를 수정하는 경우최악의 경우

5.2 최악의 경우 예시: Block Copy Instruction

copy  count  from_address  to_address
<op-code> <bytes>  <source>       <destination>
  • 두 번째 Block에 쓰려다 Page fault 발생 시?
  • 이미 수정한 내용을 Undo 해야 함
  • 임시 주소와 값을 저장하는 추가적인 HW 필요
  • Source와 Destination이 두 Block에 걸쳐 있을 수 있음 (spans two blocks)

6. Demand Paging의 성능

6.1 Effective Access Time (EAT) 공식

  • p = Page Fault Rate (0 ⇐ p ⇐ 1.0)
    • p = 0: Page fault 없음
    • p = 1: 모든 참조가 Page fault
EAT = (1 - p) x memory_access
    + p x (page_fault_overhead + [swap_page_out] + swap_page_in + restart_overhead)

6.2 계산 예제

  • Memory access time = 200 ns
  • Average page-fault service time = 8 ms = 8,000,000 ns
EAT = (1 - p) x 200 + p x 8,000,000
    = 200 + p x 7,999,800 (ns)
시나리오EAT비고
p = 0 (Page fault 없음)200 ns이상적
p = 1/1000200 + 7,999.8 = 8,199.8 ns (약 8.2 us)40배 느려짐!
p = 1 (매번 Page fault)8,000,000 ns최악

6.3 Pure Demand Paging

  • 참조되기 전까지 절대 Swap in하지 않음
  • 프로그램 시작 시 메모리에 단 하나의 Page도 없음
  • 처음 실행 시 즉시 Page fault 발생

6.4 Locality of Reference (참조 지역성)

  • 거의 모든 Workload에서 발생
  • 특정 시간 구간 동안 매우 작은 Page 집합만 참조
  • Paging 시스템을 실용적으로 만드는 핵심 원리

7. Page Replacement

7.1 Free Frame이 없는 경우

  • Page replacement: 메모리의 Over-allocation을 방지하기 위해 Page fault 처리 루틴에 Page replacement를 포함
  • Modify (dirty) bit: 수정된 Page만 디스크에 기록(Swap out) - 오버헤드 감소
  • Page replacement는 Logical memory와 Physical memory의 완전한 분리를 실현
  • 작은 Physical memory로 큰 Virtual memory 제공 가능
  • 같은 Page가 실행 중 여러 번 메모리에 올라올 수 있음

7.2 Basic Page Replacement 절차

1. 디스크에서 원하는 Page의 위치를 찾음
2. Free frame 탐색:
   - Free frame이 있으면 -> 사용
   - Free frame이 없으면 -> Page replacement algorithm으로 Victim frame 선택
3. 원하는 Page를 (새로 확보한) Free frame에 적재
   -> Page table과 Free frame table 갱신
4. 프로세스 재시작

7.3 Page Replacement Algorithm의 목표

  • Page fault rate를 최소화하는 것이 목표
  • 특정 Reference string (메모리 참조 문자열)에서 알고리즘을 실행하고 Page fault 횟수를 계산하여 평가

이후 예제에서 사용하는 Reference string:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

7.4 Page Fault 수 vs Frame 수

  • Frame 수가 증가하면 일반적으로 Page fault 수가 감소
  • 하지만 항상 그런 것은 아님 (Belady’s Anomaly 참조)

8. FIFO (First-In-First-Out) Algorithm

가장 오래 전에 메모리에 적재된 Page를 교체.

8.1 예제

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3 Frames:

참조123412512345
Frame 1111444555555
Frame 222211111333
Frame 33332222244
Fault?FFFFFFFFF
  • 9 page faults

4 Frames:

참조123412512345
Frame 1111111555544
Frame 222222211115
Frame 33333332222
Frame 4444444333
Fault?FFFFFFFFFF
  • 10 page faults

8.2 Belady’s Anomaly

  • Frame 수를 3 → 4로 늘렸는데 Page fault가 9 → 10으로 오히려 증가
  • Belady’s Anomaly: Frame 수를 늘려도 Page fault가 증가할 수 있는 현상
  • FIFO algorithm에서 발생하는 반직관적 문제

9. Optimal Algorithm (OPT / MIN)

가장 오랫동안 사용되지 않을 Page를 교체.

9.1 예제

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (4 Frames)

참조123412512345
Frame 1111111111111
Frame 222222222222
Frame 33333333333
Frame 4444555545
Fault?FFFFFF
  • 6 page faults (최적)

9.2 특징

  • 미래에 어떤 Page가 참조될지 알아야 구현 가능 - 실제 구현 불가능
  • 다른 알고리즘의 성능 비교 기준(Upper bound)으로 사용

10. LRU (Least Recently Used) Algorithm

가장 오래 전에 사용된 Page를 교체.

10.1 예제

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (4 Frames)

참조123412512345
Frame 1111111111111
Frame 222222222222
Frame 33333555544
Frame 4444444335
Fault?FFFFFFFF
  • 8 page faults

10.2 LRU의 구현 문제

  • 모든 Page에 대해 Timestamp 필요 - 추가 메모리 접근 오버헤드
  • 가장 작은 Timestamp를 가진 Page를 찾아야 함 - 검색 오버헤드
  • 공간/시간 오버헤드가 너무 커서 커널에 직접 구현하기 어려움
  • 근사 모델(Approximation model) 필요

11. LRU 구현 알고리즘

11.1 Counter Implementation

  • 모든 Page entry에 Counter 필드 추가
  • CPU counter는 메모리 참조마다 증가 (Logical clock)
    • CPU counter = 총 메모리 참조 횟수
  • Page A가 접근되면 - CPU counter 값을 A의 counter에 복사
  • Replacement 시 - Page table에서 최소 counter 값을 가진 Page 검색

오버헤드:

종류오버헤드
시간매 메모리 접근마다 Counter write 필요
시간Replacement마다 최소값 Search 필요
공간Counter 저장 공간 필요

11.2 Stack Implementation

  • Page 번호를 Double linked list 형태의 Stack으로 유지
  • Page A가 참조되면:
    • Page A를 Stack의 최상단(top)으로 이동
    • 6개의 포인터를 변경해야 함 (Stack top 포인터 포함)
  • Replacement 시 검색 불필요 - Stack 바닥(bottom)이 항상 LRU Page

12. LRU Approximation Algorithms

LRU를 정확히 구현하는 것은 오버헤드가 크므로, Reference bit를 활용한 근사 알고리즘 사용.

12.1 Reference Bit 기본

  • 각 Page에 1 bit 연결, 초기값 = 0
  • Page가 참조되면 bit를 1로 설정
  • Replacement 시 Reference bit가 0인 Page를 교체
  • 단, 순서는 알 수 없음

12.2 Additional-Reference-Bits Algorithm

  • 각 Page에 8 bits의 추가 Reference bits 할당
  • 주기적으로:
    1. 현재 Reference bit를 Additional reference bits의 최상위 비트(MSB)로 Shift
    2. 나머지 비트를 오른쪽으로 1 bit Shift (최하위 비트 버림)

예시:

값의미
00000000한 번도 참조되지 않은 Page
10101010매 두 주기마다 참조된 Page
11111111매 주기마다 참조된 Page
  • 값이 작을수록 오래 전에 참조됨 - Replacement 대상

12.3 Second Chance (Clock) Algorithm

구조:

  • Reference bit 필요
  • Page들을 Circular queue로 관리
  • 포인터가 시계 방향으로 이동

동작 알고리즘:

포인터를 전진시키며:
  if (현재 Page의 reference bit == 0):
      -> 이 Page를 교체 (victim으로 선택)
  else (reference bit == 1):
      -> reference bit를 0으로 설정
      -> Page를 메모리에 유지
      -> 다음 Page로 이동 (같은 규칙 적용)

핵심 특성:

  • 포인터가 이동하면서 Reference bit 1인 것은 모두 0으로 초기화
  • 한 바퀴 돌아와도(Second chance) 여전히 0이면 - 그때 교체
  • 자주 사용되는 Page라면 Second chance가 올 때 이미 bit가 다시 1
  • 최악의 경우: 모든 bit가 1이면 - 한 바퀴 돌고 - FIFO와 동일하게 동작

12.4 Enhanced Second Chance Algorithm

Reference bit와 Modify (dirty) bit을 함께 사용:

Reference bitModify bit우선순위설명
001순위 (최우선 교체)참조되지도, 수정되지도 않음
012순위참조되지 않았지만 수정됨 (Write-back 필요)
103순위참조되었지만 수정되지 않음
114순위 (가장 나중 교체)참조되고 수정도 됨

13. Counting Algorithms

각 Page에 대한 참조 횟수(Counter)를 유지하는 알고리즘.

알고리즘교체 대상근거
LFU (Least Frequently Used)참조 횟수가 가장 적은 Page적게 사용된 Page는 앞으로도 적게 사용될 것
MFU (Most Frequently Used)참조 횟수가 가장 많은 Page참조 횟수가 적은 Page는 방금 적재되어 아직 사용되지 않았을 것

14. 알고리즘 비교 요약

알고리즘Page Faults (4 Frames, 예제 Reference string)Belady’s Anomaly구현 가능성
FIFO10발생 가능구현 간단
Optimal6없음미래 예측 필요 - 구현 불가
LRU8없음오버헤드 큼 - 근사 알고리즘 사용
Second Chance--LRU 근사, Clock 방식으로 효율적 구현
LFU / MFU--Counter 기반

백링크

  • 백링크가 없습니다.

그래프 뷰