11. Virtual Memory(2)

Allocation of Frames

여러 프로세스에 page frame을 어떻게 분배할 것인가?
각 프로세스는 최소한의 페이지 수가 필요함
- HW 예: IBM 370 → SS MOVE 명령어 실행에 6페이지 필요
  - instruction 6바이트 → 2페이지에 걸칠 수 있음
  - source 2페이지, destination 2페이지 필요
- SW 관점:
  - Loop 내에서 page를 충분히 할당하는 것이 유리
  - 고객의 loop마다 page fault 발생 → CPU/disk I/O 비용 상승
두 가지 주요 분배 방식:
- fixed allocation
- priority allocation

Fixed Allocation

Equal allocation (균등 분배):
- 모든 프로세스에 동일한 수의 frame 할당
- 예: 총 100 frames, 5개의 프로세스 → 각 20개씩 할당
Proportional allocation (비례 분배):
- 프로세스 크기에 비례하여 frame을 분배
- 수식:
  - $a_i = \frac{s_i}{S} \times m$
  - 예:
    - $m = 64$ , $s_1 = 10$ , $s_2 = 127$ , $S = 137$
    - $a_1 = \frac{10}{137} \times 64 \approx 5$
    - $a_2 = \frac{127}{137} \times 64 \approx 59$

Priority Allocation

프로세스 **우선순위(priority)**에 따라 비례적으로 frame을 할당
우선순위가 높은 프로세스에는 더 많은 frame을 제공
→ 더 빨리 종료되도록 함 (I/O 대기 시간 감소 → 실행 시간 단축)
프로세스가 page fault 발생 시:
- 자신의 frame 중 하나에서 victim 선택
- 또는 더 낮은 우선순위 프로세스의 frame 중 하나에서 선택

Global vs. Local Replacement

Global replacement:
- 모든 프로세스의 frame 중에서 교체할 frame을 선택
- 한 프로세스가 다른 프로세스의 frame을 가져갈 수 있음
Local replacement:
- 각 프로세스는 자신에게 할당된 frame 안에서만 교체

Thrashing

프로세스에 충분한 페이지가 없는 경우 page fault rate 급증
결과:
- CPU 사용률 급감
- 운영체제는 multiprogramming degree를 늘려야 한다고 잘못 판단
- 또 다른 프로세스 추가 → 상황 악화
Thrashing: 페이지 스왑에 대부분의 시간을 소모
→ CPU는 대기만 하며 throughput 매우 낮아짐

예시 코드:

main() {
  for (i = 1; i < 100000; i++) {
    A = B + X;
  }
}

Thrashing Diagram

그래프: CPU Utilization vs. Degree of Multiprogramming
처음에는 증가 → 일정 지점 이후 급격히 감소 (thrashing 발생)
왜 paging이 효과적인가?
- Locality model
  - 프로세스는 지역적으로만 접근
  - locality는 시간이 지남에 따라 바뀜
왜 thrashing이 발생하는가?
- 모든 프로세스의 locality 총합 > 전체 메모리에서 할당된 공간

Locality

프로그램의 메모리 참조는 **고도의 지역성(locality)**을 가짐
임의 시간 Δ 내에 프로그램의 일부만 집중적으로 참조됨
시간 지역성 (Temporal Locality):
- 최근 참조된 메모리가 가까운 미래에도 참조될 가능성이 높음
- 예: loop, subroutine, stack
공간 지역성 (Spatial Locality):
- 하나의 메모리가 참조되면 그 주변 메모리도 자주 참조됨
- 예: 배열 탐색, 명령어 순차 실행

Locality In a Memory-Reference Pattern

여러 프로세스의 메모리 참조를 시간 축으로 나타낸 그래프
특정 지역이 집중적으로 참조됨 → locality 시각화

Working-Set Model

Δ: working-set window
- 일정한 수의 최근 페이지 참조 (예: 최근 10,000 instruction)
$WS(t, \Delta) = \{ \text{최근 } \Delta \text{ 동안 참조된 페이지들} \}$
- Δ가 너무 작으면 → locality를 모두 포함하지 못함
- Δ가 너무 크면 → 여러 locality가 포함되어 과도한 메모리 사용
- Δ → 실행 중인 프로그램의 locality 집합을 결정
$ D = \sum WS_i $: 전체 프로세스의 working set frame 수
$ m = \text{가용 프레임 수} $
- D > m 이면 → thrashing 발생
정책:
- D > m이면 → 프로세스 일부를 suspend
- → 멀티프로그래밍 정도(MPD) 결정

Working-Set model (예시)

page reference table:

. . 2 6 1 5 7 7 7 7 5 1 1 2 6 3 4 4 3 4 4 3 3 4 . . .

Δ 동안 참조된 페이지들:

WS(t₁) = {1, 2, 5, 6, 7}
WS(t₂) = {3, 4}

Working-Set Model (설명)

WS(t, Δ): Δ 시간 동안 참조된 페이지 집합
만약 페이지 P가 Δ 기간 동안 참조되었다면, 메모리에 유지
- 즉, WS(t)에 포함되어야 한다
WS(t)의 원칙:
- WS에 포함된 페이지만 메모리에 유지
- 그렇지 않으면 swap-out 대상
- suspend 여부는 WS가 모두 보장되는가 여부로 결정됨

Keeping Track of the Working Set

실제 구현은 복잡:
- 각 페이지마다 최근 참조 시간 저장 → 공간, 연산 비용 큼
근사 모델:
- Interval timer + reference bit
예:
- Δ = 10K
- 5K time unit마다 interrupt 발생
- 페이지마다 2비트 유지
- interrupt마다 copy & reset
- 적어도 1 비트라도 1이면 → working set에 포함
문제점:
- 완벽한 추적은 어려움
- 개선 예: 10비트로 추적 + 1000 time unit마다 인터럽트
질문:
- Δ는 어떻게 결정할까?

Page-Fault Frequency Scheme

페이지 폴트율에 따라 프레임 수를 조절

page fault rate
  ↑
  │      upper bound (감소해야 함)
  │       ↘
  │         ↘
  │           ↘
  │             ↘
  │ lower bound (증가해도 됨)
  └────────────────────→ number of frames

"허용 가능한" page fault rate 범위를 설정
실제 fault rate가 너무 낮으면 → 프로세스의 프레임 수 감소
너무 높으면 → 프로세스의 프레임 수 증가
Working set 방식: 일정 시간 동안 참조된 페이지 기반 조절
PFF 방식: page fault 발생 시점 기준으로 조절

Other Benefits of VM: Process Creation

가상 메모리는 프로세스 생성 시 다음과 같은 이점을 제공:
- Copy-on-Write (COW)
- Memory-Mapped Files

Copy-on-Write

Copy-on-Write (COW):
- 부모와 자식 프로세스가 동일한 메모리 페이지를 초기에는 공유함
- 어느 한 쪽이 페이지를 수정할 경우 → 그때 복사됨
장점:
- 실제로 수정된 페이지만 복사하므로 프로세스 생성이 매우 효율적임

Before Process 1 Modifies Page C

process₁           physical memory           process₂
   │                   ┌────────┐               │
   ├──────▶  page A ◀──┤ page A ├──▶────────────┤
   ├──────▶  page B ◀──┤ page B ├──▶────────────┤
   └──────▶  page C ◀──┤ page C ├──▶────────────┘

After Process 1 Modifies Page C

process₁           physical memory           process₂
   │                   ┌────────┐               │
   ├──────▶  page A ◀──┤ page A ├──▶────────────┤
   ├──────▶  page B ◀──┤ page B ├──▶────────────┤
   ├──────▶  page C     page C ◀──▶────────────┤
   └──────▶  copy of page C

Memory-Mapped Files

메모리 매핑 파일 I/O:
- 파일 I/O를 일반 메모리 접근처럼 다룸
- 디스크 블록을 메모리 페이지에 매핑함으로써 가능
파일은 demand paging 방식으로 메모리에 로드됨:
- 초기에는 파일의 페이지 크기 단위 일부만 물리 메모리에 로드
- 이후 접근은 일반 메모리처럼 처리
장점:
- 파일 접근을 간소화 (read/write 대신 메모리 접근)
- 여러 프로세스가 동일 파일 페이지를 공유할 수 있음

Memory Mapped Files

프로세스 A와 B가 동일한 파일을 물리 메모리 상에서 공유
디스크 파일을 메모리 페이지에 매핑하여, 접근 시 메모리를 통해 처리
메모리 매핑 기법은 여러 프로세스 간 페이지 공유를 가능하게 함

Other Issues – Prepaging

Prepaging: 프로세스 시작 시 다량의 page fault를 줄이기 위해,
- 프로세스가 실제로 참조하기 전에 일부 또는 전체 페이지를 미리 로드
문제:
- 불필요한 페이지를 미리 로드하면 메모리 낭비
모델:
- s 페이지를 미리 로드했고, 그 중 d 페이지만 사용되었을 때
- 비용 절감 조건: $\text{cost of s \text{ page faults saved}} > s \times (1 - d)$
d가 1에 가까우면 prepaging이 유리함

Other Issues – Page Size

페이지 크기 선택 시 고려사항:
- 내부 단편화
- 페이지 테이블 크기
- 디스크 전송 효율 (seek/회전 vs. 블록 전송)
- I/O 빈도
- 지역성 향상
트렌드:
- 페이지 크기 증가
- CPU 및 메모리 속도 증가로 인해 큰 페이지가 유리해짐
- 단, page fault의 비용이 상대적으로 커지고 있음

Other Issues – TLB Reach

TLB Reach:
- TLB를 통해 접근 가능한 메모리 양
- $\text{TLB Reach} = \text{TLB Size} \times \text{Page Size}$
이상적 조건:
- 각 프로세스의 working set이 TLB에 들어가는 것이 이상적
- 그렇지 않으면 TLB miss 증가
해결 방법:
- 페이지 크기 증가
  - 단, 모든 애플리케이션이 큰 페이지를 요구하지는 않음 → 단편화 우려
- 여러 크기의 페이지 제공
  - 큰 페이지를 요구하는 애플리케이션에 유리

Other Issues – Program Structure

프로그램 구조가 page fault 수에 미치는 영향
예:

int data[128][128]; // row당 하나의 페이지 사용

Program 1:

for (j = 0; j < 128; j++)
  for (i = 0; i < 128; i++)
    data[i][j] = 0;

→ 128 × 128 = 16,384 page faults

Program 2:

for (i = 0; i < 128; i++)
  for (j = 0; j < 128; j++)
    data[i][j] = 0;

→ 128 page faults
→ 데이터 접근 순서만 달라져도 성능 차이가 큼

Other Issues – I/O Interlock

I/O Interlock: 페이지가 메모리에 잠금(lock)되어야 할 경우
예:
- 장치에서 파일을 메모리로 복사하는 중인 페이지는 교체되면 안 됨
- → 해당 페이지를 page replacement의 victim으로 선택하면 안 됨
해결:
- 해당 페이지는 일정 시간 동안 고정(lock) 상태로 유지