가상 메모리 관리
가상 메모리 (기억장치)
Non-continuous allocation
사용자 프로그램을 block으로 분할하여 적재/실행
Paging/Segmentation system
가상 메모리 관리의 목적
가상 메모리 시스템 성능 최적화
Cost model
다양한 최적화 기법
가상 메모리 시스템을 위한 Cost model
Page fault frequency (발생 빈도)
Page fault rate (발생률)
Page fault rate를 최소화 할 수 있도록 전략들을 설계해야 함
Context switch 및 Kernel 개입을 최소화
시스템 성능 향상
Page reference string (d)
프로세스의 수행 중 참조한 페이지 번호 순서
Page fault rate = F(ω)
F(ω) = page faults 수/|ω|
Hardware Components
Address translation device (주소 사상 장치)
주소 사상을 효율적으로 수행하기 위해 사용
예) TLB, Dedicated page-table register, Cache memories
Bit Vectors
Page 사용 상황에 대한 정보를 기록하는 비트들
Reference bits (used bit)
참조 비트
Update bits (modified bits, write bits, dirty bits)
갱신 비트
Bit vectors
Reference bit vector
메모리에 적재된 각각의 page가 최근에 참조 되었는지를 표시
운영
1. 프로세스에 의해 참조되면 해당 page의 Reference bit를 1로 설정
2. 주기적으로 모든 reference bit를 0으로 초기화
Reference bit를 확인함으로써 최근에 참조된 pagte들을 확인 가능
Update bit vector
Page가 메모리에 적재된 후, 프로세스에 의해 수정 되었는지를 표시
주기적 초기화 없음
Update bit = 1
해당 page의 (Main memory 상 내용) != (Swap device의 내용)
해당 page에 대한 Write-back (to swap device)이 필요
Software Components
가상 메모리 성능 향상을 위한 관리 기법들
Allocation strategies (할당 기법)
Fetch strategies
Placement strategies (배치 기법)
Replacement strategies (교체 기법)
Cleaning strategies (정리 기법)
Load control strategies (부하 조절 기법)
지역성 (Locality)
프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
원인
Loop structure in program
Arrapy, structure 등의 데이터 구조
공간적 지역성 (Spatial locality)
참조한 영역과 인접한 영역을 참조하는 특성
시간적 지역성 (Temporal locality)
한 번 참조한 영역을 곧 다시 참조하는 특성
Replacement strategies (교체 기법)
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
WS(Working Set) algorithm
PFF(Page Fault Frequency) algorithm
VMIN(Variable MIN) algorithm
Min Algorithm (OPT algorithm)
1966년 Belady에 의해 제시
Minimize page fault frequency (proved)
Optimal solution
기법
앞으로 가장 오랫동안 참조되지 않을 page 교체
Tie-breaking rule: page 번호가 가장 큰/작은 페이지 교체
실현 불가능한 기법 (Unrealizable)
Page reference string을 미리 알고 있어야 함
교체 기법의 성능 평가 도구로 사용됨
Random Algorithm
무작위로 교체할 page 선택
Low overhead
No policy
FIFO Algorithm
First In First Out
Page가 적재 된 시간을 기억하고 있어야 함
자주 사용되는 page가 교체될 가능성이 높음
FIFO anomaly (Belady's anomaly)
FIFO 알고리즘의 경우, 더 많은 page frame을 할당 받음에도 불구하고 page fault의 수가 증가하는 경우가 있음
LRU(Least Recently Used) Algorithm
가장 오랫동안 참조되지 않은 page를 교체
Page 참조할때 마다 시간을 기록해야 함
지역성(Locality)에 기반을 둔 교체 기법
MIN algorithm에 근접한 성능을 보여줌
실제로 가장 많이 활용되는기법
단점
참조할때 마다 시간을 기록해야 함 (Overhead)
Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault 수가 급격히 증가함
LFU(Least Frequency Used) Algorithm
참조 횟수가 가장 적은 Page를 교체
Tie-breaking rule: LRU
Page 참조할때 마다 참조 횟수를 누적 시켜야함
지역성(Locality) 활용
LRU 대비 적은 overhead
단점
최근 적재된 참조될 가능성이 높은 page가 교체 될 가능성이 있음
참조 횟수 누적 overhead
NUR(Not Used Recently) Algorithm
LRU approximation scheme
LRU보다 적은 overhead로 비슷한 성능 달성 목적
+### Bit vector 사용Reference bit vector (r)
Update bit vector (m)
교체 순서
(r, m) = (0, 0)
(r, m) = (0, 1)
(r, m) = (1, 0)
(r, m) = (1, 1)
Clock Algorithm
IBM VM/370 OS
Reference bit 사용함
주기적인 초기화 없음
Page frame들을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 page 결정
Pointer를 돌리면서 교체 page 결정
현재 가리키고 있는 page의 reference bit(r) 확인
r = 0인 경우, 교체 page로 결정
r = 1인 경우, reference bit 초기화 후 pointer 이동
먼저 적재된 page가 교체될 가능성이 높음
FIFO와 유사
Reference bit를 사용하여 교체 페이지 결정
LRU (or NUR)과 유사
Second Chance Algorithm
Clock Algorithm과 유사
Update bit (m)도 함께 고려함
현재 가리키고 있는 page의 (r, m) 확인
(0, 0): 교체 page로 결정
(0, 1): -> (0, 0), write-back (cleaning) list에 추가 후 이동
(1, 0): -> (0, 0) 후 이동
(1, 1): -> (0, 1) 후 이동
Other Algorithms
Additional-reference-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와 정반대 기법
[참고]
https://drive.google.com/file/d/1JJgtRMTka8A5FMYRYwuMaGCzupkrAwO_/view
계속해서 배우고 성장하고 싶다.