2024. 2. 7. 13:00ㆍ프로그래밍 공부/OS
Virtual Memory Management
가상 메모리 (기억장치)
- Non-continuous allocation
* 사용자 프로그램을 block으로 분할하여 적재/실행
- Paging/Segmentation system
가상 메모리 관리의 목적
- 가상 메모리 시스템 성능 최적화
* Cost model ↓ 모호
* 다양한 최적화 기법
Cost Model for Virtual Mem. Sys.
Page fault frequency (발생 빈도)
Page fault rate (발생률)
Pi → |v| pf ← CPU
|_| |=| |
|_| |=| ←x-------
swap device Memory
Page fault rate를 최소화할 수 있도록 전략들을 설계해야 함
overhead↑
- Context switch 및 Kernel 개입을 최소화
- 시스템 성능 향상 cost↑
running
↗ ↘
ready ← asleep
↑↓
suspend
Paging system 가정
용어 참조 문자열
Page reference string (d)
- 프로세스의 수행 중 참조한 페이지 번호 순서
- w = r1r2...rk...rT
ri = 페이지 번호, ri ∈ {0, 1, 2, ..., N-1}
N : 프로세스의 페이지 수 (0~N-1)
↓ input
왜? 쓸려고 기준 평가
효율적으로 사용하기 위해서
Page fault rate = F(w)
- F(w) = (Num.of page faults during w) / |w|
길이
|PF| / |w|
|O| 갯수
Hardware Components
SW comp.
변환
Address translation device (주소 사상 장치)
- 주소 사상을 효율적으로 수행하기 위해 사용
* E.g., TLB (associated memories), Dedicated page-table register,
Cache memories
BV
Arrays {0, 1, 0, 0, 1, ..., 1}
정보, 기준
↗ v Ov Ov
pf → v O Ov
↘ v Ov O
"Bit Vectors"
- Page 사용 상황에 대한 정보를 기록하는 비트들
참조
- Reference bits (used bit)
* 참조 비트
- Update bits (modified bits, write bits, dirty bits)
* 갱신 비트
Bit Vectors
reference bits update bits
r0 w0 page frame 0
r1 w1 page frame 1
r2 w2 page frame 2
rm-1 wm-1 page frame m-1
In PMT main memory
Reference bit vector
pf 1→0
→| 1 |v
→| 2 |x
- 메모리에 적재된 각각의 page가 최근에 참조되었는지를 표시
- 운영
① 프로세스에 의해 참조되면 해당 page의 Ref.bit를 1로 설정
② 주기적으로 모든 reference bit를 0으로 초기화
- Reference bit를 확인함으로서 최근에 참조된 page들을 확인 가능
→ locality
이 순간 모든 페이지 프레임들의
참조 비트는 0으로 재설정됨
↓ ↓
●-------|-------○----|------------------->
reset |______|
↑
이 기간동안 참조된 페이지
프레임들의 참조 비트는 1로 설정됨
swap device ≠ pf_____↙ write
→ |Page| ㅁv ← Pi
↙ Mem
Update bit vector
- page가 메모리에 적재된 후, 프로세스에 의해 수정 되었는지를 표시
- 주기적 초기화 없음
- Update bit = 1
* 해당 page의 (Main memory 상 내용) ≠ (Swap device의 내용)
* 해당 page에 대한 Write-back (to swap device)이 필요
SD
□ ← □ □→ 0
Mem
Outline
Virtual Memory Management 성능↑
Cost Model → PF
Hardware Components Bit vector
Software Components → Next Chapter!
Page replacement schemes
- FA-based schemes
- VA-based schemes
Other considerations
Software Components
가상 메모리 성능 향상을 위한 관리 기법들
- Allocation strategies (할당 기법)
- Fetch strategies
- Placement strategies (배치 기법)
- Replacement strategies (교체 기법)
- Cleaning strategies (정리 기법)
- Load control strategies (부하 조절 기법)
Allocation strategies
각 프로세스에게 메모리를 얼마 만큼 줄 것인가?
- Fixed allocation (고정 할당)
* 프로세스의 실행 동안 고정된 크기의 메모리 할당
P←
#| |pf
| | pf
Mem
- Variable allocation (가변 할당)
* 프로세스의 실행 동안 할당하는 메모리의 크기가 유동적
Pi
3
pf # 4 ↕
2
고려사항
- 프로세스 실행에 필요한 메모리의 양을 예측해야 함
- 너무 큰 메모리 할당 (Too much allocation), 10pf ← 100
* 메모리가 낭비됨
- 너무 적은 메모리 할당 (Too small allocation), 10pf ← 1
* Page fault rate ↑
* 시스템 성능 저하
Fetch strategies
가져오는 것
|=| Swap |=|
Mem ←
특정 page를 메모리에 언제 적재할 것인가?
요구
- Demand fetch (demand paging)
* 프로세스가 참조하는 페이지들만 적재 만화 1권 3권 4권
* Page fault overhead
- Anticipatory fetch (pre-paging) pre fetch
* 참조될 가능성이 높은 page 예측
*v 가까운 미래에 참조될 가능성이 높은 page를 미리 적재
* 예측 성공 시, page fault overhead가 없음
*+ "Prediction overhead" (Kernel의 개입), Hit ratio에 민감함 성능
실제 대부분의 시스템은 Demand fetch 기법 사용
-★ 일반적으로 준수한 성능을 보여줌
- Anticipatory fetch
* Prediction overhead, 잘못된 예측 시 자원 낭비가 큼
Program A → B
OS
PRfetch VM
disk ↗
Placement strategies
Page/segment를 어디에 적재할 것인가?
Paging system에는 불필요
| |
| v |
| | ↖
| v |
Segmentation system에서의 배치 기법
- First-fit
- Best-fit
- Worst-fit
- Next-fit
Replacement strategies
새로운 page를 어떤 page와 교체할 것인가?
(빈 page frame이 없는 경우)
Pi
| A |
full | B | ↔
| C | ← D
- Fixed allocation을 위한 교체 기법
* MIN(OPT, B0) algorithm
* Random algorithm
* FIFO(First In First Out) algorithm
* LRU(Least Recently Used) algorithm
* LFU(Least Frequently Used) algorithm
* NUR(Not Used Recently) algorithm
* Clock algorithm
* Second chance algorithm
- Variable allocation을 위한 교체 기법
* VMIN(Various MIN) algorithm
* WS(Working Set) algorithm
* PFF(Page Fault Frequency) algorithm
Cleaning strategies
update Bit, dirty bit
1
Swap device
Pi → | | → □
d = 1 ↓
변경 된 page를 언제 write-back할 것인가?
- 변경된 내용을 swap device에 반영
v Demanding cleaning
* 해당 page에 메모리에서 내려올 때 write-back
- Anticipatory cleaning (pre-cleaning)
* 더 이상 변경될 가능성이 없다고 판단 할 때, 미리 write-back
* Page 교체 시 발생하는 write-back 시간 절약
* Write-back 이후, page 내용이 수정되면, overhead!
실제 대부분의 시스템은 Demand cleaning 기법 사용
- 일반적으로 준수한 성능을 보여줌
★ Anticipatory cleaning
* Prediction overhead, 잘못된 예측 시 자원 낭비가 큼
Load Control Strategies
부하
시스템의 multi-programming degree 조절
- Allocation strategies와 연계됨
100p
1p
적당히
적정 수준의 multi-programming degree를 유지해야 함
- Plateau(고원) 영역으로 유지
- 저부하 상태 (Under-loaded), 100, 10
* 시스템 자원 낭비, 성능 저하 ↓
- 고부하 상태 (Over-loaded), 100, 1000
* 자원에 대한 경쟁 심화, 성능 저하
* Thrashing(스레싱)현상 발생
과도한 page fault가 발생하는 현상
Hwp 5초
sps performance
throughput ↑
| |-------------------|
| / | | \ ☆
| / | | \ thrashing
| / | | \ ↙
| / | | \
| / | 고원 | \
------------------------------------------------------------->
underloaded plateau overloaded multiprogamming degree
Software Components
가상 메모리 성능 향상을 위한 관리 기법들
Allocation strategies (할당 기법)
Fetch strategies
Placement strategies (배치 기법)
Replacement strategies (교체 기법) Next Video!!
Cleaning strategies (정리 기법)
Load control strategies (부하 조절 기법)
Locality
프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
원인
- Loop structure in program
- Array, structure 등의 데이터 구조
공간적 지역성 (Spatial locality)
- 참조한 영역과 인접한 영역을 참조하는 특성
시간적 지역성 (Temporal locality)
- 한 번 참조한 영역을 곧 다시 참조하는 특성
Locality (Example)
가정
- Paging system word| v |←
- Page size = 1000 words 1000| | page
★ Machine instruction size = 1 word
- 주소 지정은 word 단위로 이루어짐
- 프로그램은 4번 page에 continuous allocation 됨
- n = 1000
...
1000
for ← 1 to n do ↗ page
A[i] ← B[i] + C[i]; Array[n]
end for
...
| Memory address | Machine code |
| 4000 4001 4002 4003 4004 4005 4006 4007 4008 ... 6000-6999 7000-7999 8000-8999 9000 9001 |
(R1) ← ONE (R2) ← n compare R1, R2 branch greater 4009 4 (R3) ← B(R1) 7 (R3) ← (R3) + C(R1) 8 A(R1) ← (R3) (R1) ← (R1) + 1 branch 4002 ... storage for array A 6 storage for array B 7 storage for array C 8 storage for ONE 9 storage for n |
w = 494944(474846444)^1000 4 7 8 6 9 → locality
11000번의 메모리 참조 중 5개의 page만을 집중적으로 접근하게 됨
Replacement strategies
Fixed allocation => Pi ← pf 수가 고정 eg.) Pi ← 4pf
A 고체
B
C
D G
- MIN(OPT, B0) algorithm
- Random algorithm
- FIFO(First In First Out) algorithm
- LRU(Least Recently Used) algorithm
- LFU(Least Frequently Used) algorithm
- NUR(Not Used Recently) algorithm
- Clock algorithm
- Second chance algorithm
This video ↑
Variable allocation
- VMIN(Various MIN) algorithm
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
Min Algorithm (OPT algorithm)
1966년 Belady에 의해 제시
최소화 ↓
Minimize page fault frequency (proved)
★ Optimal solution
최적
4 5 6 .......
↖7
★기법
w
- 앞으로 가장 오랫동안 참조되지 않을 page 교체
* Tie-breaking rule : page 번호가 가장 큰/작은 페이지 교체
실현 불가능한 기법 (Unrealizable) ↑ 3초 120(x)
★ Page reference string을 미리 알고 있어야 함 x
교체 기법의 성능 평가 도구로 사용됨
x 최적 기준
Current Refernce time for
time pages x, y, z after t
| Page ______| | |____
↓ w ↓ ↓ ↓
w x z y
-------○-------[--○---------○--------○--]------>
#pf3 t time
x
y -------→ Replace page y and load
z page w in the frame
Current
memory
state
Example
- 4 page frames for the process, initially empty
- w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5
Pi
| Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Ref. string | 1 | 2 | 6 | 1 | 4 | 5 | 1v | 2v | 1 | 4v | 5 | 6v | 4v | 5v |
| Memory state | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | ||
| 6 | 6 | 6 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | |||||
| Page fault | F | F | F | F | F | F |
Number of page faults = 6
Time 11에서 1, 2 중
규칙 tie-breaking-rule
Random Algorithm
무작위로 교체할 page 선택
Low overhead
No policy
x
Current
time
|
↓
w
-------○--------------------------------------------->
t time
x
y -------→ Replace a page randomly
z among pages x, y, z and
Current load page w in the frame
memory
state
FIFO Algorithm
First In First Out
- 가장 오래된 page를 교체
Page가 적재된 시간을 기억하고 있어야 함
Code 4 ↑ 중요하다
자주 사용되는 page가 교체될 가능성이 높음
- Locality에 대한 고려가 없음
FIFO anomaly (Belady's anomaly)
- FIFO 알고리즘의 경우,
더 많은 page frame을 할 당 받음에도 불구하고 page
fault의 수가 증가하는 경우가 있음
The time that pages x, y, z Current
are loaded into memory time
_____| | |__ |
↓ ↓ ↓ ↓
z x y w
--[-○--------○-----○-]---------○---------------->
time
x
y
z Replace a page z and load
Current page w in the frame
memory
state
Example
- 4 page frames for the process, initially empty
- w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5
| Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Ref. string | 1 | 2 | 6 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 6 | 4 | 5 |
| Memory state | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 4 | 4 |
| 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 5 | ||
| 6 | 6 | 6 | 6 | 6 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 6 | 6 | 6 | |||||
| Page fault | F | F | F | F | F | F | F | F | F | F |
Number of page faults = 10
6↗
Pi PF
Mem
paging pf더
Example(FIFO Anomaly)
- w = 1 2 3 4 1 2 5 1 2 3 4 5
| Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Ref. string | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
| Memory state 3pf |
1 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
| 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | ||
| 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | |||
| Page fault | F | F | F | F | F | F | F | F | F |
Number of page faults = 9
| Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Ref. string | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
| Memory state 4pf |
1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 4 | 5 |
| 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 5 | ||
| 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 3 | 3 | 3 | ||||
| Page fault | F | F | F | F | F | F | F | F | F | F |
Number of page faults = 10
Mem↑ → pf↓
LRU(Least Recently Used) Algorithm
가장 오랫동안 참조되지 않은 page를 교체 ← locality
Page 참조 시 마다 시간을 기록해야 함
Locality에 기반을 둔 교체 기법
↓
MIN algorithm에 근접한 성능을 보여줌
실제로 가장 많이 활용되는 기법
The time that pages x, y, z Current
are loaded into memory time
_____| | |__ |
↓ ↓ ↓ ↓
z x y w
--[-○--------○-----○-]---------○---------------->
time
x
y
z Replace a page x and load
Current page w in the frame
memory
state
단점
- 참조 시 마다 시간을 기록해야 함 (Overhead)
* 간소화된 정보 수집으로 해소 가능
예) 정확한 시간 대신, 순서만 기록
- Loop 실행에 필요한 크기보다 작은 수의 page frame이
할당된 경우, page fault 수가 급격히 증가함
* 예) loop를 위한 |Ref.string| = 4 / 할당된 page frame이 3개
* Allocation 기법에서 해결해야 함
↗ 4개 for( )
pf 3개 1
1 2
2 3
3 4
Example
- 4 page frames for the process, initially empty
- w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5
| Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Ref. string | 1 | 2 | 6 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 6 | 4 | 5 |
| Memory state | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | ||
| 6 | 6 | 6 | 6 | 6 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | |||||
| Page fault | F | F | F | F | F | F | F |
Number of page faults = 7
6
LFU(Least Frequently Used) Algorithm
가장 참조 횟수가 적은 page를 교체
- Tie-breaking rule : LRU
Page 참조 시 마다, 참조 횟수를 누적시켜야 함
++
Locality 활용
- LRU 대비 적은 overhead
page
w
-------|--------
1
단점
- 최근 적재된 참조될 가능성이 높은 page가 교체될 가능성이 있음
- 참조 횟수 누적 overhead
x 27 Current
Number of references y 16 time
to the pages x, y, z z 23 |
↓
__________________________ w
----------------------------------○---------------->
0 time
x
y
z → Replace a page y and load
Current page w in the frame
memory
state
Example
- 4 page frames for the process, initially empty
- w = 1 2 6 1 4 5 1 2 1 4 5 6 4 5
| Time | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Ref. string | 1 | 2 | 6 | 1 | 4 | 5 | 1 | 2 | 1 | 4 | 5 | 6 | 4 | 5 |
| Memory state | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | ||
| 6 | 6 | 6 | 6 | 6 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | |||||
| Page fault | F | F | F | F | F | F | F |
Number of page faults = 7
NUR (Not Used Recently) Algorithm
횟수! 간략
LRU approximation scheme
- LRU보다 적은 overhead로 비슷한 성능 달성 목적
| v |
| |
| |
| | ----|-----------|------
0 0
Bit vector 사용 ↓
- Reference bit vector (r), Update bit vector (m)
1 → 0
| | → write-back!
교체 순서
1순위
① (r, m) = (0, 0)
② (r, m) = (0, 1)
2순위
③ (r, m) = (0, 1)
④ (r, m) = (0, 1)
Clear reference bits to 0
for all page frames
| |
----- -----------
↓ reset t r→1 ↓ reset
time-----|--------------○-----|---------------------------->
t1 \___________/ ↖ t2
↑ ＼
| ＼
Set reference bit to 1 When replaces a page,
for the accessed page frame choose on that have not been
accessed during (t1, t2)
Clock Algorithm
IBM VM/370 OS
★ Reference bit 사용함
- 주기적인 초기화 없음
Page frame들을 순차적으로 가리키는 pointer
(시계바늘)를 사용하여 교체될 page 결정
|시침
reference bit reference bit
□ 1 page page □ 1→0
pw px
시계침
↗
page page
pz py
reference bit reference bit
□ 1 □ 1
Pointer를 돌리면서 교체 page 결정
- 현재 가리키고 있는 page의 reference bit(r) 확인
- r = 0 인 경우, 교체 page로 결정
- r = 1 인 경우, reference bit 초기화 후 pointer 이동
→0
먼저 적재된 page가 교체될 가능성이 높음
- FIFO와 유사
Reference bit를 사용하여 교체 페이지 결정
- LRU (or NUR) 과 유사 → locality
Example
- 4 page frames for the process, initially it has a, b, c, d
- w = c a b d e b a d c d
| Time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Ref. string | c | a | d | b | e | b | a | b | c | d | ||
| Memory state | frame 0 frame 1 frame 2 frame 3 |
→a/1 b/1 c/1 d/1 |
→a/1 b/1 c/1 d/1 |
→a/1 b/1 c/1 d/1 |
→a/1 b/1 c/1 d/1 |
e/1 →b/0 c/0 d/0 |
e/1 →b/1 c/0 d/0 |
e/1 b/0 a/1 →d/0 |
e/1 b/1 a/1 →d/0 |
→e/1 b/1 a/1 c/1 |
d/1 →b/0 a/0 c/0 |
|
| Page fault Pclock(loaded page) Qclock (displaced page) |
F e a |
F a c |
F c d |
F d e |
Second Chance Algorithm
Clcok algorithm과 유사 r, m
Update bit(m)도 함께 고려함
- 현재 가리키고 있는 page의 (r, m) 확인
- 1 (0, 0): 교체 page로 결정
- 2 (0, 1): → (0, 0), write-back (cleaning) list에 추가 후 이동
- 3 (1, 0): → (0, 0) 후 이동
- 4 (1, 1): → (0, 1) 후 이동
r m r m
page page
pw px
↗
page page
pz py
r m r m
Example
- 4 page frames for the process, initially it has a, b, c, d
- w = c a^w b d^w e b a^w d c d
write op
m → 1 w-B bit
| Time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Ref. string | c | a^w | d | b^w | e | b | a^w | b | c | d | ||
| Memory state |
frame 0 frame 1 frame 2 frame 3 |
→a/10 b/10 c/10 d/10 |
→a/10 b/10 c/10 d/10 |
→a/11 b/10 c/10 d/10 |
→a/11 b/10 c/10 d/10 |
→a/11 b/11 c/10 d/10 |
a/00 →b/00 e/10 d/00 |
a/00 →b/10 e/10 d/00 |
a/11 b/10 e/10 →d/00 |
a/11 b/10 e/10 →d/00 |
→a/11 b/10 e/10 c/10 |
a/00 →d/10 e/00 c/00 |
| Page fault P2nd-chance Q2nd-chance |
F e a |
F a c |
F c d |
F d e |
Other Algorithms
Additional-refernce-bits algorithm
- LRU approximation
- 여러 개의 reference bit를 가짐
* 각 time-interval에 대한 참조 여부 기록
* History register for each page
- MRU (Most Recently Used) algorithm
* LRU와 정반대 기법
- MFU (Most Frequently Used) algorithm
* LFU와 정반대 기법
Replacement strategies
- Fixed allocation
* MIN(OPT, B0) algorithm
* Random algorithm
* FIFO(First In First Out) algorithm
* LRU(Least Recently Used) algorithm MA: 고정 △: 가변 pf: 3
* LFU(Least Frequently Used) algorithm
* NUR(Not Used Recently) algorithm
* Clock algorithm
* Second chance algorithm
- Variable allocation
* WS(Working Set) algorithm
* PFF(Page Fault Frequency) algorithm
* VMIN(Various MIN) algorithm
Pi |가변|
Working Set (WS) algorithm
1968년 Denning이 제안
Working set locality
- Process가 특정 시점에 자주 참조하는 page들의 집합
- 최근 일정시간 동안(△) 참조된 page들의 집합
- 시간에 따라 변함
- W(t, △) [ (
* The working set of a process at time t
* Time interval [t-△, t] 동안 참조된 pages들의 집합
* △: window size, system parameter
Working set at time t:
Set of pages referenced during
the time interval [t - △, t )
↓ 최대 △ + 1
____________ 최소 1
| | ↑
--------○------------○---------------->
0 t-△ window t time
↑
Current time
Working set memory management
- Locality에 기반을 둠
- Working set을 메모리에 항상 유지 window
* Page fault rate (thrashing) 감소↓
* 시스템 성능 향상↑
- Window size(△)는 고정
* Memory allocation은 가변
fixed
MA가 고정 and △가 가변 = ?
* △ 값이 성능을 결정 짓는 중요한 요소
Working Set (WS) algorithm
Window size vs. WS size
△ M△
working set ↑
size |
|----------|-------------|-----------------
program | | | /
size | | / |
| / | |
| / | |
| / | |
|/________|___________|_________________>
window size
locality
Example: working set translation
| p0 ● ←|
| p1 |___| loop-1 → working set = {p0, p1}
| p2 ● ←| ↓ws? 2
process | p3 | |
execution | p4 |___| loop-2 → working set = {p2, p3, p4}
| p5 ↓ws? 3
| p6 ● ←|
| p7 |___| loop-3 → working set = {p6, p7}
2
Working set transition
number of ↑
page frames | transition
allocated | ↓ _______↓ |_____
| | | |
| _____ | | ↓ _______
| | | | WS-2 | | |
| |WS-1 | | loop | _____ | WS-4 |
| | loop | | | |WS-3| | |
---------------------------------------------->
time
[t-△, t]
1-3 1
=-2
Example
- △ = 3, number of pages = 5(0, 1, 2, 3, 4)
- Initially pages {0, 3, 4} in the memory at time 0
- w = 2 2 3 1 2 4 2 4 0 3
| Time | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Ref. string | 4 | 3 | 0 | 2 | 2 | 3 | 1 | 2 | 4 | 2 | 4 | 0 | 3 | |
| Memory state |
Page 0 Page 1 Page 2 Page 3 Page 4 |
? ? ? ? ? |
? ? ? ? ? |
0 - - 3 4 |
0 - 2 3 4 |
0 - 2 3 - |
0 - 2 3 - |
- 1 2 3 - |
- 1 2 3 - |
- 1 2 3 4 |
- 1 2 - 4 |
- - 2 - 4 |
0 - 2 - 4 |
0 - 2 3 4 |
| Page fault Pws Qws |
? ? ? |
? ? ? |
? ? ? |
F 2 |
4 |
F 1 0 |
F 4 |
3 |
1 |
F 0 |
F 3 |
||
| # of frames allocated | ? | ? | 3 | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 2 | 3 | 4 |
Working Set (WS) algorithm
성능 평가
- Page fault 수 외 다른 지표도 함께 봐야 함
- Example 1. cost = 50 x 5 + 3.2 x 10 x 10
* Time interval [1, 10] = 250 + 320 = 570
# of page fault = 5 cost(pf)=50 2. 6 x 50 = 300
평균 할당 page fault 수 = 3.2 cost(p)=10 2.5 x 100 = 250
* 평가 cost = 550
평균 3.2개의 page frame을 할당 받은 상태에서
5번의 page fault 발생
특성
- 적재되는 page가 없더라도, 메모리를 반납하는 page가 있을 수 있음
- 새로 적재되는 page가 있을 더라도, 교체 되는 page가 없을 수 있음
지속 관찰
단점
- Working set management overhead
- Residence set (상주 집합)을 Page fault가 없더라도,
지속적으로 관리해야 함
Mean number of frames allocated vs. page fault rate
↑
1 ○ |
lifetime | \ /
& | \ /
page fault rate | \ / lifetime => page유지 비용↑
| \ /
| / \
| / \
| / \ page fault rate
0 | | \
-------------------------------------------------------->
0 mean resident set size ws
(window size)
Page Fault Frequency (PFF) algorithm
"Residence set size"를 page fault ra↑te에 따라 결정
- Low page fault rate (long inter-fault time) μΔ↓
* Process에게 할당된 PF 수를 감소
- High page fault rate (short inter-fault time) μΔ↑
* Process에게 할당된 PF 수를 증가
Resident set 갱신 및 메모리 할당
★ Page fault가 발생시에만 수행
- Low overhead
Criteria for page fault rate
- IFT > τ : Low page fault rate
- IFT < τ : High page fault rate
- τ: threshold value
* System parameter
자주 기준? τ
페이지 폴트 사이의 시간 = IFT
Algorithm
1) Page fault 발생 시, IFT 계산
- IFT = tc - tc-1 10-5=5
* tc-1: time of previous page fault
* tc: time of current page fault tc-1 tc
2) IFT > τ (Low page fault rate) (tc, tc-1] 1 2 3 4
- Resident set ← (tc, tc-1] 동안 참조된 page들만 유지
- 나머지 page들은 메모리에서 내림
* 메모리 할당(#of page frames) 유지 or 감소
3) IFT ≤ τ (High page fault rate) ↑
- 기존 pages들 유지
- + 현재 참조된 page를 추가 적재
* 메모리 할당(#of page frames) 증가
Example
- τ = 2, number of pages = 5(0, 1, 2, 3, 4)
- Initially pages {0, 3, 4} in the memory at time 0
- w = 2 2 3 1 2 4 2 4 0 3
| Time | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Ref. string | 4 | 3 | 0 | 2 | 2 | 3 | 1 | 2 | 4 | 2 | 4 | 0 | 3 | |
| Memory state |
Page 0 Page 1 Page 2 Page 3 Page 4 |
- - - 4 |
- - - 3 4 |
0 - - 3 4 |
0 - 2 3 4 |
0 - 2 3 4 |
0 - 2 3 4 |
- 1 2 3 - |
- 1 2 3 - |
- 1 2 3 4 |
- 1 2 3 4 |
- 1 2 3 4 |
0 - 2 - 4 |
0 - 2 3 4 |
| Page fault PPFF QPFF |
F 0 |
F 2 |
F 1 0,4 |
F 4 |
F 0 1,3 |
F 3 |
|||||||
| # of frames allocated | - | - | 3 | 4 | 4 | 4 | 3 | 3 | 4 | 4 | 4 | 3 | 4 |
IFT = 1-0=1
1<τ
IFT = 4-1=3 > 2
(1, 4]
성능 평가
- Page fault 수 외 다른 지표도 함께 봐야 함
- Example
* Time interval [1, 10]
# of page fault = 5
평균 할당 page fault 수 = 3.7
* 평가 ↓3.2 WS
평균 3.7개의 page frame을 할당 받은 상태에서 5번의
page fault 발생
특징
- 메모리 상태 변화가 page fault 발생 시에만 변함
* Low overhead
Variable MIN (VMIN) algorithm
Variable allocation 기반 교체 기법 중 optimal algorithm
- 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 Optimal
★실현 불가능한 기법 (Unrealizable)
- Page reference string을 미리 알고 있어야 함
(평가의 기준으로 이용할 수 있어서 배움)
기법
- [t, t + △]을 고려해서 교체할 page 선택
Algorithm
- Page r이 t시간에 참조되면,
page r이 (t, t + △] 사이에 다시 참조되는지 확인
- 참조 된다면, page r을 유지
- 참조 안 된다면, page r을 메모리에서 내림 ↓
Example
- △ = 4, number of pages = 5(0, 1, 2, 3, 4)
- w = 2 2 3 1 2 4 2 4 0 3
(t, t + △]
| Time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Ref. string | 0 | 2 | 2 | 3 | 1 | 2 | 4 | 2 | 4 | 0 | 3 | |
| Memory state |
Page 0 Page 1 Page 2 Page 3 Page 4 |
- - - 3 - |
- - 2 3 - |
- - 2 3 - |
- - 2 3 - |
- 1 2 - - |
- - 2 - - |
- - 2 - 4 |
- - 2 - 4 |
- - - - 4 |
0 - - - - |
- - - 3 - |
| Page fault PVMIN QVMIN |
F 2 |
F 1 3 |
1 |
F 4 |
2 |
F 0 4 |
F 3 0 |
||||
| # of frames allocated | - | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 1 | 1 | 1 |
성능 평가
- Page fault 수 외 다른 지표도 함께 봐야 함
- Example
* Time interval [1, 10]
# of page fault = 5
평균 할당 page frame 수 = 1.6
* 평가
평균 1.6개의 page frame을 할당 받은 상태에서 5번의
page fault 발생
최적 성능을 위한 △값은?
- △ = R / U
* U: 한번의 참조 시간 동안 page를 메모리에 유지하는 비용
* R: page fault 발생 시 처리 비용
- R > △ * U, (△가 작으면) △ < R / U => △ * U < R
* 처리 비용 > page 유지 비용
- R < △ * U, (△가 크면) △ > R / U => △ * U > R
* page fault 처리 비용 < 유지 비용
Other Considerations
- Page size
- Program restructuring
- TLB reach
Page Size
|=|page |=| page frame
시스템 특성에 따라 다름
- No best answer! 적당한!
- 점점 커지는 경향 ↑
일반적인 page size
- 2^7 (128) bytes ~ 2^22 (4M) bytes
| Small page size | Large page size |
| Large page table / # of PF ↑ | Small page table / # of PF ↓ |
| High overhead (kernel) | Low overhead (kernel) |
| 내부 단편화 감소 ↓ | 내부 단편화 증가 ↑ |
| I/O 시간 증가 ↑ | I/O 시간 감소 ↓ |
| Locality 향상 ↑ | Locality 저하 ↓ |
| Page fault 증가 ↑ | Page fault 감소 ↓ |
[HW 발전 경향]
CPU ↑, Memory size ↑
→ 상대적인 Page fault 처리 비용 ↑
Program Restructuring
가상 메모리 시스템의 특성에 맞도록 프로그램을 재구성
OS
사용자가 가상 메모리 관리 기법(예, paging system)에 대해 이해하고 있다면,
프로그램의 구조를 변경하여 성능을 높일 수 있음
Example
- Paging system, Page size = 1KB
- sizeof(int) = 4 bytes
// program-1
int main()
{ 행 열
int zar[256][256]; 256x4=1KB
int i, j;
for(j = 0; j < 256; j++)
for(i = 0; i < 256; i++)
zar[i][j] = 0;
return 0;
}
Row-major order for array
1 pf zar[0][0]
4 pf zar[0][1] 1KB
... page 0
zar[0][255]
2 pf zar[1][0]
5 pf zar[1][1]
... page 1
zar[1][255]
...
3 pf zar[255][0]
6 pf zar[255][1]
... page 255
zar[255][255]
1 word (4 bytes)
// program-1
int main()
{
int zar[256][256];
int i, j;
for(j = 0; j < 256; j++)
for(i = 0; i < 256; i++)
zar[i][j] = 0;
return 0;
}
// program-2
int main()
{
int zar[256][256];
int i, j;
for(i = 0; i < 256; i++)
for(j = 0; i < 256; j++)
zar[i][j] = 0;
return 0;
}
TLB reach
HW
TLB를 통해 접근할 수 있는 메모리의 양
- (The number of entries) * (the page size) = TLB Reach
TLB의 hit ratio를 높이려면,
-① TLB의 크기 증가
* Expensive
-② Page 크기 증가 or 다양한 page size 지원
* OS의 지원이 필요
최근 OS의 발전 경향
Summary
Virtual memory management
Cost model
Hardware components
Software components
Page replacement schemes
- FA-based schemes
- VA-based schemes
Other considerations
'프로그래밍 공부 > OS' 카테고리의 다른 글
| 12 입출력 시스템 & 디스크 관리 (0) | 2024.02.13 |
|---|---|
| 11 파일 시스템 (0) | 2024.02.11 |
| 9 Virtual Storage (Memory) (0) | 2024.02.05 |
| 8 메모리(주기억장치) 관리 (0) | 2024.02.02 |
| 7 Deadlock (0) | 2024.01.31 |