이전 post에서 가상 메모리 관리에 대해서 알아보았습니다. SW component에서 replacement strategies에 대해서 더 알아보겠습니다.
Locality
- 프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
- Replacement strategies에서 기준을 제시
- 원인 : loop 구조, 자료구조
- 공간적 지역성 : 참조한 영역과 인접한 영역을 참조하는 특성
- 시간적 지역성 : 한 번 참조한 영역을 곧 다시 참조하는 특성
Fixed allocation
- 프로세스를 정해진 크기의 page frame으로 분할하여 메모리에 할당
- 할당하려고 하니 자리가 없어서 어떤 것과 교첼할 것인가?
Fixed allocation을 위한 교체 기법
- MIN(OPT) 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
1) MIN(OPT) algorithm
- 앞으로 사용되지 않을 page를 알고 있다는 가정 하에 page fault frequency를 최소화하는 기법
- 단점
* 실현 불가능 : page reference string을 미리 알 수 없음
- 사용 : 교체 기법의 성능 평가 도구
* A라는 최적화 알고리즘이 알려져 있다. 본인은 B, C라는 알고리즘을 개발했을 때, 성능 평가하기 위해 MIN algorithm으로 A의 page reference string으로 B, C의 성능 평가를 할 수 있다.
- 동작
* 앞으로 가장 오랫동안 참조되지 않을 page를 교체
* 성능(page fault rate) : 6/14
2) Random algorithm
- 무작위로 교체할 page 선택하여 교체
- 장점
* low overhead
* no policy
- 사용 : 교체 기법의 성능 평가 도구. 일반적으로 random보다 높아야 함
3) FIFO(First In First Out) algorithm
- 가장 오래된 page를 교체
- page가 적재된 시간을 기록
- 단점
* 자주 사용되는 page가 교체될 수 있음
* Locality를 반영하지 않음
* FIFO anomaly : 더 많은 page frame을 할당했음에도 불구하고 page fault의 수가 증가하는 현상
+ 왼쪽 : page frame이 3개, page fault는 9개
+ 오른쪽 : page frame이 4개, page fault는 10개
- 동작
* 가장 오래된 page를 선택하여 교체
* 성능(page fault rate) : 10/14
4) LRU(Least Recently Used) algorithm
- 가장 오랫동안 사용되지(참조되지) 않은 page를 교체
- Locality 반영
- 실제로 가장 많이 사용되는 기법
- 단점
* 참조할 때마다 시간을 기록해야 하기 때문에 overhead
- 동작
* 성능(page fault rate) : 7/14
5) LFU(Least Frequently Used) algorithm
- 참조된 횟수가 가장 적은 page를 교체
- 메모리에 적재된 이후 page 참조할 때마다 참조 횟수를 누적 기록
- Locality 반영
- 단점
* 최근 참조된 page는 적재 횟수가 적어서 교체될 가능성이 높음
* 참조 횟수 누적은 overhead
- 동작
* Time 12에서 page 2번이 반납된 과정은 다음과 같다. Time 8에서 page 2가 적재된 이후에 1번 참조되었다. page 5는 Time 7에서 적재된 이후에 2번 참조되었다. page 4번도 적재된 이후에 2번 참조되었기 때문에 적재 이후 1번 참조된 page 2가 교체되었다.
* 성능(page fault rate) : 7/14
6) NUR(Not Used Recently) algorithm
- 최근에 사용하지 않은(0/1) page와 교체
- LRU보다 적은 overhead로 비슷한 성능 달성
- Bit vector 사용
* reference bit vector (r), update bit vector (m)
* 교체 우선 순위
1. (r, m) = (0, 0)
2. (r, m) = (0, 1)
3. (r, m) = (1, 0)
4. (r, m) = (1, 1)
* m = 0이 우선인 이유, update bit vector 값이 1이면 메모리를 나올 때 write-back 작업을 추가로 실행한다. 따라서 값이 0이면 작업을 하지 않으므로 m = 0이 우선이다.
7) Clock algorithm
- NUR을 실전에 적용하기 위한 알고리즘
- IBM VM/370 OS에 사용됨
- reference bit만 사용
- 주기적인 초기화 없음
- 동작
* page frame들을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 page 결정
* 교체를 해야할 때, pointer가 가리키는 page의 reference bit를 확인
+ reference bit = 0일 때, page 교체 후, pointer 이동
+ reference bit = 1일 때, reference bit을 0으로 초기화 후 pointer 이동
8) Second chance algorithm
- Clock algorithm과 유사
- reference bit (r) 과 update bit (m) 모두 사용
- 동작
* 교체 해야할 때, pointer가 가리키는 page의 (r, m) 확인
+ (r, m) = (0, 0)일 때, page 교체
+ (r, m) = (0, 1)일 때, (0, 0)으로 변경하고 write-back list에 추가 후 pointer 이동
+ (r, m) = (1, 0)일 때, (0, 0)으로 변경하고 pointer 이동
+ (r, m) = (1, 1)일 때, (0, 1)으로 변경하고 pointer 이동
Variable allocation을 위한 교체 기법
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
- VMIN(Variable MIN) algorithm
1) WS(Working Set) algorithm
- Working set : process가 최근 일정 시간 동안 자주 참조하는 page들의 집합
- 시간에 따라 변함
- Locality 반영
- Window size : [t- Δ, t] 시간대의 영역
- Window size 고정, Memory allocation은 변동
- Δ값이 성능을 결정 짓는 중요한 요소
- Working set을 메모리에 항상 유지
* Page fault rate 감소
- 특징 (동작에서 확인)
* 적재되는 page가 없더라도, 메모리를 반납하는 page가 있을 수 있음
* 새로 적재된 page가 있더라도, 교체되는 page가 없을 수 있음
- 단점
* Working set을 지속적으로 관리해야 하기 때문에 overhead
- 동작
* 가정 : Δ = 3, pages = {0, 1, 2, 3, 4, 5}, 초기 메모리 = {0, 3, 4}
* Time 2에서 working set은 0, 2, 3.그러나 page 4가 있으므로 page 4를 반납
* 적재하지 않았지만 메모리를 반납
* Time 4에서 working set은 1, 2, 3. 그러나 page 0이 있으므로 page 0 반납
* Page 1을 적재해야 함으로 page fault 발생
* Time 6에서 page 4를 적재해야 하므로 page fault 발생
* Page를 새로 적재 했는데 교체되는 page가 없음
- 성능 평가
* Fixed allocation과 다른 방식 도입 why? Fixed allocation에서는 고정된 전체 page frame에서 page fault된 개수의 비율을 적용 가능했지만, variable allocation에서는 page frame의 크기가 제각각 이기 때문
* 수치화 : (page fault의 개수 * page fault 처리 비용) + (평균 할당 page frame 수 * 전체 page frame 개수 * page frame 유지 비용)
(평균 할당 page frame 수 : 위 표에서 # of frames allocated / entire time)
* 예시 : page fault의 개수 5, 평균 할당 page frame의 개수 3.2 VS page fault의 개수 6, 평균 할당 page frame의 개수 3.2 일 때, 결과는 570 VS 550로 후자가 성능이 더 좋음
2) PFF(Page Fault Frequency) algorithm
- WS algorithm은 working set을 page fault가 발생하지 않아도 관리해야 하는 문제를 가짐
- 지속적으로 관리하지 말고 page fault 발생할 때마다 residence set size(page들 집합 크기)를 조절하는 방식
- IFT(Interval fault time) : 현재 page fault가 일어난 시간 - 직전 page fault가 일어난 시간
- t(타우) : Page fault rate의 높고 낮음을 판단할 기준으로 IFT와 비교
- 동작
* Page fault가 발생하면, IFT을 계산
* IFT > t일 경우, residence set = (tc-1, tc]동안 참조됨 page들만 유지
* IFT < t일 경우, 기존 page들 + 현재 참조된 page 추가
* 가정 : t = 2, page들 = {0, 1, 2, 3, 4}, 초기 메모리 = {0, 3, 4}
* residence set size = 3인데 새로운 page 2가 들어올려고 했기 때문에 page fault 발생
* IFT = 1 - 0
* IFT < t 이므로 기존 page들 유지하고 새로운 page 2 추가
* residence set size = 4인데 새로운 page 1이 들어올려고 했기 때문에 page fault 발생
* IFT = 4 -1
* IFT > t 이므로 residence set size 줄이기
* 2 ~ 4 사이에 참조된 2, 3, 1만 적재하고 0, 4는 반환
* residence set size = 3인데 새로운 page 4가 들어올려고 했기 때문에 page fault 발생
* IFT = 6 - 4
* IFT = t 이므로 기존 page들 유지하고 새로운 page 4 추가
- 성능 평가
* WS algorithm과 동일한 성능 평가
* # of page fault = 5, 평균 할당 page frame 수 = 3.7
3) VMIN(Variable MIN) algorithm
- 평균 메모리 할당량과 page fault 발생 횟수를 모두 고려하여 교체
- 실현 불가능 : page reference string을 미리 알지 못하기 때문에
- 최적의 Δ 값
* Δ = R / U
* R : page fault 발생 시 처리 비용
* U : 한 번의 참조 시간 동안 page를 메모리에 유지하는 비용
- 동작
* page r이 t시간에 참조되면, page r이 (t, t+ Δ] 사이에 다시 참조되는지 확인
+ 참조될 것이라면, page r 유지
+ 참조되지 않을 것이라면, page r을 메모리에서 반환
* 가정 : Δ = 4, page들 = {0, 1, 2, 3, 4}, 초기 메모리 = {3}
* Time 3에서 page 3은 미래에 Δ시간 동안 참조되지 않으므로 반환되고 page 1이 적재
- 성능 평가
* WS algorithm과 동일한 성능 평가
* # of page fault = 5, 평균 할당 page frame 수 = 1.6
본 내용은 한국기술교육대학교 김덕수 교수님의 유튜브 강의를 듣고 정리한 내용입니다.
'Software Courses > Operating System' 카테고리의 다른 글
| Disk System (0) | 2020.12.13 |
|---|---|
| [Memory] Other considerations (0) | 2020.12.13 |
| [Memory] Virtual memory management (0) | 2020.12.12 |
| [Memory] Hybrid paging segmentation system (0) | 2020.12.10 |
| [Memory] Segmentation system (0) | 2020.12.10 |