Chapter10. 가상 메모리 관리(2)
카테고리: OS
태그: CS
유튜브에 있는 김덕수 교수님의 Operating System 강의를 듣고 정리한 내용입니다.
중간에 등장하는 ppt 내용들은 모두 강의자료를 캡처한 것입니다.
🔧 Replacement strategies (교체 기법)
Locality
- 프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
- Loop structure
- Array structure
- 등등…
- 예시의 경우 4,7,8,6 4개의 page만을 집중적으로 접근
🔧 Fixed allocation
MIN algorithm (OPT algorithm)
| Replacement | Example |
|---|---|
 |
 |
- 앞으로 가장 오랫동안 참조되지 않을 page 교체
- Minimize page fault frequency (Optimal solution)
- Proved
- 실현 불가능 (Inrealizable)
- Page reference string을 미리 알고 있어야 함
- 교체 기법의 성능 평가 도구로 사용됨
Random algorithm
- 무작위로 교체할 page 선택
- Low overhead
- No policy
FIFO algorithm
| Replacement | Example |
|---|---|
 |
 |
- First In First Out : 가장 오래된 page를 교체
- Page가 적재된 시간을 기억하고 있어야함
- 자주 사용되는 page가 교체될 가능성이 큼
- Locality에 대한 고려가 없음
- FIFO anomaly
- 더 많은 page frame을 할당 받음에도 불구하고 page fault의 수가 증가하는 경우가 있음
LRU (Least Recently Used) algorithm
| Replacement | Example |
|---|---|
 |
 |
- 가장 오랫동안 참조되지 않은 page를 교체
- Page 참조할 때마다 시간을 기록해야 함
- Locality에 기반을 둔 교체 기법
- MIN algorithm에 근접한 성능을 보여줌
- 실제로 가장 많이 활용되는 기법
- 단점
- 참조할 때마다 시간 기록 (overhead)
- 정확한 시간 대신 순서만 기록하는 등 간소화 가능
- Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault 수가 급격히 증가
- Allocation 기법으로 해결해야 함
- 참조할 때마다 시간 기록 (overhead)
LFU (Least Frequently Used) algorithm
| Replacement | Example |
|---|---|
 |
 |
- 참조 횟수가 가장 적은 page를 교체
- Page 참조할 때마다 참조 횟수를 누적시켜야 함
- LRU 대비 적은 overhead
- 단점 : 최근 적재된 참조될 가능성이 높은 page가 교체될 수 있음
NUR (Not Used Recently) algorithm
- LRU와 비슷
- 시간이 아닌 참조 여부만 다짐
- LRU보다 적은 overhead & 비슷한 성능
- Bit vector 사용하면 편함!
- reference bit 주기적으로 초기화
Clock algorithm
| Replacement | Example |
|---|---|
 |
 |
- Reference bit 주기적인 초기화 없음
- Page frame들을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 page를 결정
- 현재 가리키고 있는 page의 reference bit (r) 확인
- r = 0인 경우 교체 page로 결정
- r = 1인 경우 reference bit 초기화 후 pointer 이동
- 먼저 적재된 page가 교체될 가능성이 높음
- FIFO와 유사
- Reference bit을 이용하여 교체 page 결정
- LRU (NUR)과 유사
- 더 적은 overhead
Second chance algorithm
| Replacement | Example |
|---|---|
 |
 |
- Update bit (m)도 함께 고려 (write-back 필요 없는 page 먼저 교체)
- (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
- reference bit 여러 개 정의
- MRU (Most Recently Used) algorithm
- LRU와 정반대 기법
- MFU (Most Frequently Used) algorithm
- LFU와 정반대 기법
🔧 Variable allocation
Working Set (WS) algorithm
Working set
- 프로세스가 일정시간(window size) 동안 참조된 page들의 집합
Working set memory management
- Locality 기반
- Working set을 메모리에 항상 유지
- Page fault rate (thrashing) 감소
- Window size는 고정
- memory allocation은 가변
- size 값이 성능을 결정짓는 요소
| process | working set size |
|---|---|
 |
 |
- Working set은 시간에 따라 크기가 변함
- 특징
- 적재되는 page가 없더라도, 메모리를 반납하는 page가 있을 수 있음
- 새로 적재되는 page가 있더라도, 교체되는 page가 없을 수 있음
- 단점
- window 계속 쳐다봐야 함
- page fault가 없더라도 메모리 지속적으로 관리해야 함
- window size가 너무 크면 page fault는 감소하지만, 메모리를 비효율적으로 쓰게 됨
- 적당하게 유지해야 함
Page Fault Frequency (PFF) algorithm
메모리에 적재할 page frame 갯수를 page fault rate에 따라 결정
- low page fault rate (long inter-fault time)
- 프로세스에게 할당된 page frame 수 감소
- high page fault rate (short inter-fault time)
- 프로세스에게 할당된 page frame 수 증가
- page fault 발생시에만 갱신 (low overhead)
Criteria for page fault rate
- threshold value t(타우) 설정
- IFT : inter-fault time
- page fault와 page fault 사이의 간격
- IFT > t (low page fault rate)
- 최근 IFT 동안 참조된 page들만 유지
- 나머지 page들은 메모리에서 내림
- 메모리 할당은 유지 및 감소
- IFT < t (high page fault rate)
- 기존 page들 유지
- 현재 참조된 page들 추가 적재
- 메모리 할당 증가
Variable MIN (VMIN) algorithm
- variable allocation 기반 교체 기법 중 optimal algorithm
- Page reference string을 미리 알고 있어야 함
- 실현 불가능한 기법
- 성능 평가에 이용
🔧 Page size
Page 크기에 따른 장단점이 있지만, 가장 크리티컬한 문제는 I/O bottleneck 현상이다. 최근 나오는 CPU는 연산 속도가 너무 빠르기 때문에 데이터 가져오는 속도가 이를 못 따라온다. 따라서 I/O 시간을 단축시키는 것이 중요하기 때문에 Page 크기는 점점 커지는 경향이다.
댓글 남기기