1. Allocation of Frames (Frame 할당)
여러 프로세스에 Page frame을 어떻게 배분할 것인가의 문제.
1.1 최소 Page 수의 필요성
각 프로세스는 최소한의 Page 수를 필요로 한다.
- HW 측면: IBM 370의 SS MOVE 명령어 처리에 6 pages 필요
- 명령어 자체가 6 bytes로 2 pages에 걸칠 수 있음
- from 주소 처리를 위한 2 pages
- to 주소 처리를 위한 2 pages
- SW 측면:
- Loop 내의 page는 한꺼번에 allocate하는 것이 유리
- 그렇지 않으면 매 loop마다 Page fault 발생 - CPU/disk 부하 심한 불균형
1.2 Fixed Allocation (고정 할당)
Equal Allocation (균등 할당)
모든 프로세스에 동일한 수의 Frame을 할당한다.
예: 100 frames, 5 processes -> 각 프로세스에 20 frames
Proportional Allocation (비례 할당)
프로세스 크기에 비례하여 Frame을 할당한다.
si = 프로세스 Pi의 크기
S = Σsi (전체 프로세스 크기의 합)
m = 전체 사용 가능한 Frame 수
ai = (si / S) x m (프로세스 Pi에 할당되는 Frame 수)
예시:
s1 = 10, s2 = 127
m = 64
a1 = (10 / 137) x 64 ≈ 5
a2 = (127 / 137) x 64 ≈ 59
1.3 Priority Allocation (우선순위 할당)
크기 대신 우선순위를 기반으로 Proportional allocation을 수행한다.
- High priority process에 더 많은 메모리를 할당
- I/O 감소 - Waiting 상태 시간 감소 - 빠른 완료
- 프로세스 Pi가 Page fault를 발생시키면:
- 자신의 Frame 중에서 Victim을 선택하거나
- 더 낮은 우선순위 프로세스의 Frame에서 Victim을 선택
2. Global vs Local Replacement
| 방식 | 설명 | 특징 |
|---|---|---|
| Global replacement | 모든 Frame 중에서 교체 대상을 선택 | 한 프로세스가 다른 프로세스의 Frame을 빼앗을 수 있음 |
| Local replacement | 자기 자신의 Frame 중에서만 교체 대상을 선택 | 프로세스별 할당량이 고정됨 |
3. Thrashing
3.1 개념
프로세스가 “충분한” Page를 갖지 못하면 Page-fault rate가 매우 높아진다.
악순환:
- Page fault가 빈번하게 발생
- CPU utilization이 낮아짐
- OS가 Multiprogramming degree(MPD)를 높여야 한다고 판단
- 새로운 프로세스를 추가
- 더 심한 Page fault 발생 - Thrashing
Thrashing: 프로세스가 Page를 swap in/out하느라 바쁘고, CPU는 대부분의 시간 동안 idle 상태인 현상. Throughput이 급격히 떨어진다.
예시:
main() { for (I=1, 100000) { A = B + X } }
변수 A, B, X가 각각 다른 Page에 있고 Frame이 부족하면,
매 반복마다 Page fault가 발생할 수 있다.
3.2 Thrashing Diagram
- X축: Degree of multiprogramming
- Y축: CPU utilization
- MPD가 증가할수록 CPU utilization이 올라가다가, 특정 지점을 넘으면 급격히 떨어짐
- 이 급락 구간이 바로 Thrashing
3.3 Paging이 작동하는 이유: Locality Model
Paging이 잘 작동하는 이유는 프로그램이 Locality(지역성)를 가지기 때문이다.
- 프로세스는 하나의 Locality에서 다른 Locality로 이동(migrate)
- Locality들은 서로 겹칠(overlap) 수 있음
Thrashing 발생 조건:
Σ (Locality의 크기) > 할당된 메모리 총 크기
4. Locality (지역성)
프로그램의 메모리 참조는 고도의 지역성을 가진다. 임의 시간 t 내에 프로그램의 일부분만을 집중적으로 참조한다.
| 유형 | 설명 | 예시 |
|---|---|---|
| Temporal Locality (시간 지역성) | 현재 참조된 메모리가 가까운 미래에도 참조될 가능성이 높음 | Loop, Subroutine, Stack |
| Spatial Locality (공간 지역성) | 하나의 메모리가 참조되면 주변 메모리가 계속 참조될 가능성이 높음 | Array traversal, 명령의 순차 실행 |
Locality in a Memory-Reference Pattern
- X축: Execution time
- Y축: Memory address / Page numbers
- 특정 시간 구간에서 제한된 범위의 Page들만 집중적으로 참조되는 패턴을 보여줌
5. Working-Set Model
5.1 개념
Working-set model은 Locality에 기반한 Frame 할당 및 교체 정책이다.
- Delta (Δ): Working-set window. 고정된 Page 참조 횟수 (예: Δ = 10,000 instructions)
- WS(ti): 시간 ti에서의 Working set =
{ 과거 Δ 번의 참조 동안 참조된 Page들의 집합 }
WS(ti) = { pages referenced in [ti - Δ, ti] }
Δ의 크기에 따른 특성:
| Δ 크기 | 특성 |
|---|---|
| 너무 작으면 | 전체 Locality를 포함하지 못함 |
| 너무 크면 | 여러 Locality를 포함하게 됨 |
| Δ = 무한대 | 전체 프로그램을 포함 |
5.2 Working-Set Model 예시
Page reference table:
... 2 6 1 5 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 4 4 4 3 4 4 4 ...
| |
t1 t2
<----- Δ -------> <----- Δ ------->
WS(t1) = {1, 2, 5, 6, 7} (WSS = 5)
WS(t2) = {3, 4} (WSS = 2)
5.3 Working Set 기반 정책
- WSSi: 프로세스 Pi의 Working set size
- D = Σ WSSi: 전체 Demand frames (모든 프로세스의 WSS 합)
- m: 전체 사용 가능한 Frame 수
D > m -> Thrashing 발생!
정책:
D > m이면, 프로세스 하나를 Suspend (MPD 감소)- 각 프로세스에 WSS 이상의 Frame이 보장되어야 실행(run) 가능
- WSS만큼 Frame을 받지 못하면 - Suspend
- 즉, 프로세스는 (WSS 전체 보장) 또는 (Suspend) 중 택일
5.4 Working Set의 할당/교체 통합
Working-set model은 Allocation과 Replacement를 동시에 결정한다.
- Page P가 시간 ti에 WS(ti)에 속하면 - 메모리에 유지 (keep in memory)
- Page P가 시간 ti에 WS(ti)에 속하지 않으면 - 메모리에서 제거 (out of memory)
- 시간에 따라 Allocation size가 동적으로 변함
6. Keeping Track of the Working Set (Working Set 추적)
6.1 정확한 구현의 문제
매 Reference마다 각 Page의 최근 Reference time을 Δ와 비교하는 것은 너무 비용이 큼.
- Reference time field를 위한 공간 + 비교를 위한 시간 소요
6.2 근사적 구현: Interval Timer + Reference Bit
예시: Δ = 10,000
- Timer interrupt: 매 5,000 time unit마다 발생
- 각 Page마다 2 bits를 메모리에 유지
- Timer interrupt 발생 시:
- Reference bit를 History bits로 복사(copy)
- Reference bit를 0으로 초기화(reset)
- History bits 중 하나라도 1이면 - 해당 Page는 Working set에 속함
한계: 완전히 정확하지 않음. Timer interval 사이의 참조를 구분할 수 없다.
개선: 10 bits를 사용하고 매 1,000 time unit마다 interrupt 발생 - 더 정밀한 근사
Q: Window size(Δ)는 어떻게 결정하는가? - 시스템 특성에 따라 경험적으로 조정
7. Page-Fault Frequency (PFF) Scheme
“허용 가능한” Page-fault rate의 Upper bound와 Lower bound를 설정한다.
| 상황 | 조치 |
|---|---|
| 실제 Page-fault rate가 Upper bound 초과 | 프로세스에 Frame을 추가 할당 (increase number of frames) |
| 실제 Page-fault rate가 Lower bound 미만 | 프로세스의 Frame을 회수 (decrease number of frames) |
Working Set vs PFF 비교
| 특성 | Working Set | PFF |
|---|---|---|
| Page 집합 수정 시점 | 매 Page 참조 시 | Page fault 발생 시에만 |
| 오버헤드 | 상대적으로 높음 | 상대적으로 낮음 |
| 정밀도 | Δ 설정에 의존 | Bound 설정에 의존 |
8. Other Benefits of VM: Process Creation
Virtual memory는 프로세스 생성 시에도 이점을 제공한다.
- Copy-on-Write (COW)
- Memory-Mapped Files
9. Copy-on-Write (COW)
9.1 개념
fork() 시 Parent와 Child 프로세스가 초기에는 같은 Page를 공유한다.
- 어느 한 쪽이 공유 Page를 수정(modify)할 때만 해당 Page를 복사
- 수정되지 않은 Page는 계속 공유 - 효율적인 프로세스 생성
9.2 Before Modification (수정 전)
- Process 1과 Process 2가 Physical memory의 Page A, B, C를 모두 공유
- 두 프로세스의 Page table이 같은 Physical frame을 가리킴
9.3 After Modification (수정 후)
- Process 1이 Page C를 수정하면:
- Page C의 복사본(Copy of page C)이 생성됨
- Process 1은 새 복사본을 가리키고, Process 2는 원본을 계속 사용
- Page A, B는 여전히 공유 상태
10. Memory-Mapped Files
10.1 개념
Memory-mapped file I/O는 파일 I/O를 일반적인 메모리 접근처럼 다룰 수 있게 한다.
- Disk block을 메모리의 Page에 매핑(mapping)
- 파일은 처음에 Demand paging을 통해 읽힘
- 파일의 Page-size 분량이 File system에서 Physical page로 읽혀짐
- 이후 파일에 대한 Read/Write는 일반 메모리 접근으로 처리
10.2 장점
read(),write()System call 대신 메모리 접근으로 파일 I/O 수행 - 단순화- 여러 프로세스가 같은 파일을 매핑하여 Page를 공유할 수 있음
10.3 Memory Mapped Files 다이어그램
- Process A와 Process B가 같은 Disk file을 Virtual memory에 매핑
- Physical memory에서 해당 Page들이 공유됨
- Disk file의 각 Block이 Physical frame에 매핑되어 접근됨
11. Other Issues
11.1 Prepaging
프로세스 시작(startup) 시 발생하는 대량의 Page fault를 줄이기 위한 기법.
- 프로세스가 필요로 할 Page들을 참조되기 전에 미리 로드
- 단점: Prepage된 Page가 사용되지 않으면 I/O와 메모리가 낭비됨
비용 분석:
s = Prepage된 Page 수
α = 실제로 사용되는 Page의 비율
비교:
s x α 개의 Page fault가 절약되는 비용
vs.
s x (1 - α) 개의 불필요한 Page를 prepage하는 비용
α ≈ 0 -> Prepaging은 손해
α ≈ 1 -> Prepaging은 이득
11.2 Page Size 선택
Page size 결정 시 고려 사항:
| 고려 사항 | 작은 Page size | 큰 Page size |
|---|---|---|
| Internal fragmentation | 적음 | 많음 |
| Page table 크기 | 큼 (엔트리 많음) | 작음 (엔트리 적음) |
| Disk 전송 효율 | 비효율적 (seek/rotation 비중 높음) | 효율적 (전송 비중 높음) |
| I/O 연산 빈도 | 높음 | 낮음 |
| Locality | 좋음 (필요한 정보만 격리) | 불필요한 데이터도 포함 |
추세: Page size가 점점 커지는 방향
- CPU 속도, 메모리 용량은 Disk 속도보다 빠르게 향상됨
- Page fault의 상대적 비용(penalty)이 점점 높아지고 있음
- 큰 Page로 Page fault 횟수를 줄이는 것이 유리
11.3 TLB Reach
TLB Reach: TLB에서 접근 가능한 메모리의 양
TLB Reach = (TLB Size) x (Page Size)
- 이상적으로, 각 프로세스의 Working set이 TLB에 저장되어야 함
- 그렇지 않으면 높은 TLB miss rate 발생
TLB Reach를 높이는 방법:
| 방법 | 설명 | 단점 |
|---|---|---|
| Page size 증가 | 단순하게 TLB Reach 확대 | Internal fragmentation 증가 |
| Multiple page sizes 지원 | 큰 Page가 필요한 애플리케이션에만 큰 Page 사용 | HW/OS 복잡도 증가, 하지만 fragmentation 방지 |
11.4 Program Structure (프로그램 구조)
프로그램의 데이터 접근 패턴이 Page fault 횟수에 큰 영향을 미친다.
예시: int data[128][128], 각 행(row)이 하나의 Page에 저장. Data를 위한 Free frame이 128개 미만이라 가정.
Program 1 (열 우선 접근 - Column-major)
for (j = 0; j < 128; j++)
for (i = 0; i < 128; i++)
data[i][j] = 0;결과: 128 x 128 = 16,384 Page faults
- 매 접근마다 다른 행(Page)으로 점프하므로, 매번 Page fault 발생
Program 2 (행 우선 접근 - Row-major)
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i][j] = 0;결과: 128 Page faults (Data를 위한 Frame이 1개만 있어도)
- 같은 행(Page) 내의 요소를 순차적으로 접근하므로, 행이 바뀔 때만 Page fault 발생
교훈: Spatial locality를 활용하는 방향으로 데이터 접근 패턴을 설계해야 한다. C/C++에서 2차원 배열은 Row-major 순서로 저장되므로, 행 단위 접근이 효율적이다.
11.5 I/O Interlock
- I/O를 위해 사용 중인 Page는 반드시 메모리에 고정(lock)되어야 함
- 파일 복사 등의 I/O 작업에 사용되는 Page가 Page replacement algorithm에 의해 Eviction 대상으로 선택되면 안 됨
- 해당 Page를 Lock(pin)하여 교체 방지
핵심 정리
Frame 할당 전략
| 전략 | 방식 |
|---|---|
| Equal allocation | 모든 프로세스에 동일한 Frame 수 |
| Proportional allocation | 프로세스 크기에 비례 |
| Priority allocation | 우선순위에 비례 |
Thrashing 방지 기법
| 기법 | 핵심 아이디어 |
|---|---|
| Working-Set Model | Δ 크기의 Window 내 참조된 Page 집합 유지. D > m이면 Suspend |
| PFF Scheme | Page-fault rate의 Upper/Lower bound로 Frame 수 동적 조절 |
VM의 추가 활용
| 기법 | 설명 |
|---|---|
| Copy-on-Write | fork() 시 수정된 Page만 복사 |
| Memory-Mapped Files | 파일 I/O를 메모리 접근으로 처리 |
| Prepaging | 필요한 Page를 미리 로드하여 초기 Page fault 감소 |
| I/O Interlock | I/O 중인 Page를 Lock하여 교체 방지 |