10. Virtual Memory(1)

Size of a Logical Address Space

[stack]
   ↑
[heap]

[data]

[text]
   ↑
   0

32비트 주소의 경우, 최대 주소 공간:
$2^{32} - 1 \Rightarrow 4 \text{GB}$
- 각 프로세스당 최대 4GB 논리 주소 공간
- 이 중 많은 부분이 실제로는 사용되지 않음

Background

가상 메모리: 논리 메모리와 물리 메모리를 분리하는 구조
장점:
- 프로그램의 일부분만 메모리에 있어도 실행 가능
- 논리 주소 공간은 물리 주소 공간보다 훨씬 클 수 있음
- 여러 프로세스가 주소 공간 공유 가능
- 프로세스 생성을 더 효율적으로 수행 가능
- 페이지를 스왑인/스왑아웃 할 수 있어야 함
구현 방식:
- Demand paging
- Demand segmentation

Virtual Memory Larger than Physical Memory

virtual memory:
  page 0
  page 1
  page 2
  ...
  page n

→ memory map → physical memory 일부만 유지
→ 나머지는 secondary storage(디스크 등)에 저장

Demand Paging

페이지가 필요할 때만 메모리에 불러옴
- I/O 감소
- 메모리 절약
- 반응 속도 향상
- 사용자 수 증가
페이지가 필요한 경우:
- 잘못된 참조 → abort
- 메모리에 없으면 → 불러오기
Lazy swapper:
- 필요한 순간까지 페이지를 불러오지 않음
- 이 기능을 수행하는 모듈을 pager라고 부름

Valid-Invalid Bit

각 페이지 테이블 항목에는 valid-invalid 비트가 있음
Valid (V): 메모리에 있음
Invalid (I):
- 해당 페이지가 프로세스 주소 공간에 없음 (illegal)
- 디스크에서 아직 로딩되지 않음 (not-in-memory)
- 디스크에서는 유효하지만 메모리에는 없음 (obsolete)
- 예: 항공 예약 시스템
  - 하나의 전역 디스크 + 여러 컴퓨터/지점
모든 항목은 초기에는 invalid 상태로 설정
주소 변환 중, invalid이면 ⇒ page fault

Page Table when Some Pages are not in Main Memory

일부 페이지가 메모리에 없을 경우:
- page table에는 valid-invalid 비트가 존재
- 물리 메모리에 없는 페이지는 디스크에 저장됨
- 접근 시 page fault 발생

Page Fault

유효하지 않은 페이지 접근 → MMU가 trap 발생 → page fault trap
Trap handler는 OS 내부에 구현되어 있음
OS가 page fault를 처리하는 순서:
1. OS가 다른 테이블을 조회하여 원인을 결정
  - illegal reference? bad address? protection violation?
  - 메모리에 없는 경우 → 계속 진행
2. 빈 프레임 확보
  - 없으면 교체 (replacement)
3. 디스크에서 페이지를 읽어 옴
  - 디스크 I/O 완료까지 프로세스는 wait 상태
  - 완료 후 page table 갱신 (frame #, valid bit)
  - 프로세스를 Ready 큐에 넣고 dispatch
4. 페이지 fault 처리 완료 → 프로세스 재할당
5. fault가 발생했던 명령 재실행

Steps in Handling a Page Fault

프로세스가 페이지 참조
        ↓
해당 페이지가 디스크에만 존재 → trap 발생
        ↓
운영체제가 페이지 테이블과 free frame 조회
        ↓
디스크에서 해당 페이지를 메모리로 불러옴 (bring in)
        ↓
page table 갱신
        ↓
명령 재시작

Difficulties in actual HW design

언제 page fault가 발생하는가?
1. 명령어 fetch 중: 문제 없음
2. 피연산자 fetch 중: instruction fetch → decode → operand fetch 중 재시작 필요
3. 최악의 경우: 명령어가 여러 위치를 갱신할 때
  - 예: block copy 명령어
```
copy count from_address to_address
```
    - to_address가 두 블록에 걸쳐 있을 경우
    - 두 번째 블록 접근 중 fault 발생하면 이전 작업 Undo 필요
해결을 위해 임시 주소/값 저장을 위한 하드웨어 지원 필요

Performance of Demand Paging

페이지 폴트 확률 $0 \leq p \leq 1.0$
- $p = 0$ → page fault 없음
- $p = 1$ → 모든 참조가 fault
유효 접근 시간 (Effective Access Time, EAT) 계산:
$EAT = (1 - p) \times \text{memory access time} + p \times (\text{page fault overhead})$
예시:
- 메모리 접근 시간 = 200ns
- 평균 page fault 처리 시간 = 8ms = 8,000,000ns
- $p = \frac{1}{1000}$ 일 때: $EAT = (1 - \frac{1}{1000}) \times 200 + \frac{1}{1000} \times 8,000,000 = 8.2~\mu s$ → 속도 저하 약 40배
순수한 demand paging:
- 참조 전까지 swap-in 하지 않음
- 시작 시 아무 페이지도 메모리에 없음
참조의 지역성 (Locality of reference):
- 거의 모든 workload에서 나타남
- 일정 시간 동안 특정 소수 페이지만 집중적으로 참조
- 이 특성 덕분에 demand paging이 실용적

What happens if there is no free frame?

Page replacement
- page-fault 처리 루틴을 수정하여 프레임이 부족할 때 page replacement 수행
- modify (dirty) bit를 사용하여 디스크 전송 비용 최소화 (수정된 페이지만 디스크로 swap-out)
- 논리 메모리와 물리 메모리의 분리를 완성
  - 더 작은 물리 메모리로 큰 가상 메모리 제공 가능
  - 같은 페이지가 실행 중 여러 번 메모리에 올라올 수 있음
Page replacement algorithm
- victim page(교체 대상 페이지)를 선택하는 알고리즘
- 목표: page fault 수 최소화

Basic Page Replacement

디스크에서 필요한 페이지 위치 찾기
빈 프레임 찾기
- 빈 프레임이 있으면 → 그대로 사용
- 없으면 → page replacement 알고리즘으로 victim frame 선택
디스크에서 해당 페이지를 victim frame에 불러오고, page table과 free frame table 업데이트
중단된 프로세스 재시작

Page-Replacement Algorithms

최소 page-fault 비율을 갖는 알고리즘이 이상적
알고리즘을 특정 reference string에 대해 실행하여 성능 평가
예시 reference string:

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

Graph of Page Faults vs. the Number of Frames

프레임 수가 증가하면 page fault 수는 감소
단, 항상 그런 것은 아님 (→ Belady’s anomaly)

First-In-First-Out (FIFO) Algorithm

Reference string:

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

3 프레임일 때:

1 2 3  →  page fault
4      →  page fault, replace 1
1      →  page fault, replace 2
2      →  page fault, replace 3
5      →  page fault, replace 4
1 2 3 4 5 → 총 9 page faults

4 프레임일 때:

page fault 더 많아짐 → 10
→ Belady’s Anomaly (프레임이 늘었는데도 page fault가 증가)

Optimal Algorithm

가장 오랫동안 사용되지 않을 페이지를 교체
예시:

Reference: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
4개의 프레임 사용 시 → 총 6 page faults

실제 시스템에서 적용 불가능 (미래 참조를 알 수 없기 때문)
알고리즘 성능 평가의 기준으로 사용됨

Least Recently Used (LRU) Algorithm

Reference string:

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

LRU 문제점:
- LRU를 그대로 구현하려면:
  - 각 페이지에 타임스탬프 필요 → page table traffic 증가
  - 가장 오래된 타임스탬프를 찾는 연산 필요
  - 커널에 적용하기에는 공간/시간 오버헤드가 큼
- → 근사 모델 필요

LRU Implementation Algorithms

카운터 기반 구현:
- 각 페이지마다 카운터 유지
- CPU가 메모리 참조마다 카운터 증가
- 페이지 참조 시 현재 카운터 값을 저장
- 교체 시 가장 작은 카운터 값을 가진 페이지를 선택
- 단점:
  - 매 접근 시 카운터 접근 비용
  - 교체 시 전체 검색 필요
  - 오버헤드 큼
스택 기반 구현:
- 페이지 번호를 이중 연결 리스트(stack) 형태로 유지
- 참조 시 해당 페이지를 top으로 이동
- 이동 시 포인터 6개 수정 필요
- 교체 시 검색 불필요

Use of a Stack to Record the Most Recent Page References

Reference string:

4 7 0 7 1 0 1 2 7 b

스택 상태 변화:

stack before:
top → 2
       1
       0
       4

stack after:
top → 7
       2
       1
       0
       4

최근 사용된 페이지가 top에 위치

LRU Approximation Algorithms

Reference bit 방식:
- 각 페이지에 1비트 레퍼런스 비트 할당 (초기값 0)
- 페이지가 참조되면 비트 = 1
- 교체 시 reference bit가 0인 페이지를 선택
추가 참조 비트 방식:
- 각 페이지에 8비트 할당
- 일정 주기마다 reference bit를 가장 높은 비트로 시프트
- 나머지 비트는 오른쪽으로 쉬프트 (하위 비트 삭제)
- 예:
  - 00000000: 참조 안 됨
  - 10101010: 2주기마다 참조됨

LRU Approximation Algorithms (계속)

Second-Chance (Clock) 알고리즘
- reference bit 사용
- 원형 큐로 페이지 유지
- 포인터가 reference bit가 0인 페이지를 찾을 때까지 이동
- reference bit가 1이면 0으로 리셋하고 다음 페이지로 이동
- 사실상 FIFO와 유사하지만 참조된 페이지에 기회 한 번 더 줌
특징:
- 포인터는 순환적으로 회전
- 1이면 bit만 0으로 바꾸고 지나침
- 0이면 victim으로 선택
향상된 Second-Chance 알고리즘
- Reference bit + Modify bit 조합
- 우선순위:
  - Not-Referenced + Not-Modified: 최우선으로 교체
  - Referenced + Modified: 마지막 우선순위

Second-Chance (Clock) Page-Replacement Algorithm

시각적 예시:

(a)

reference bit: 1 1 0 1 0
next victim → 찾을 때까지 한 칸씩 이동하며 검사

(b)

reference bit가 1인 경우는 무시하고 다음으로 진행

한 바퀴 돌면서 적절한 교체 대상 선택

Counting Algorithms

각 페이지에 대해 참조 횟수 카운터를 유지함
LFU (Least Frequently Used) 알고리즘
- 참조 횟수가 가장 적은 페이지를 교체
MFU (Most Frequently Used) 알고리즘
- 가장 적게 참조된 페이지는 최근에 불러온 후 아직 사용되지 않았을 가능성이 높다는 가정에 기반하여,
- 참조 횟수가 가장 많은 페이지를 유지하고, 가장 적은 페이지를 유지하지 않음

Virtual Memory & Page Replacement - 교수님 강의 요약

Frame Allocation과 Priority

각 프로세스에 프레임 수를 어떻게 할당할지는 OS 정책에 달려 있음
우선순위 기반 정책(priority allocation): 우선순위가 높은 프로세스에 프레임을 더 많이 할당
- 하지만 우선순위가 높다고 무조건 많이 줄 필요는 없음
중요한 목표는 page fault를 줄이는 것
- 자주 접근하는 페이지들을 식별해서 해당 프레임 수만큼만 할당해주는 것이 핵심