2022. 6. 4. 14:56ㆍMajor`/운영체제
시스템 내부에서는 "여러 프로세스들"이 CPU와 메인 메모리 등의 자원을 공유한다.
CPU를 공유하는 부분에 대해서는 단지 어느 프로세스에게 할당해주고 & 이 과정에서 Context Switch가 발생하고 & .... 이러한 것들은 Response Time이나 이러한 시간적 측면에서 느려질 뿐, 시스템에 심각한 오류가 발생하지는 않는다
반면에 여러 프로세스들이 공유하는 "메인 메모리"는 다르다
각 프로세스들이 메인 메모리에 예전 방식으로는 Contiguous하게 올라갈 수도 있고, 아니면 고정 크기로 분할한 Paging 기법을 사용해서 올라갈 수도 있고, 의미있는 가변 크기로 분할한 Segmentation 기법을 사용해서 올라갈 수도 있다.
여기서 각 프로세스들은 본인에게 할당된 영역만 access해야 한다는 것은 당연한 규칙이다
하지만 여기서 메인 메모리의 크기가 모든 프로세스들을 수용할 수 없다면??
수용할 수 없는데 모든 프로세스들을 한번에 올리려고 하면 프로세스들의 의지와는 무관하게 시스템상에 심각한 오류를 유발한다
>> 이러한 문제들을 방지하기 위해서 탄생한 기법이 "가상 메모리"이다
가상 메모리 기법은 user과 전혀 상관하지 않아도 된다. 왜냐하면 OS가 Page들을 Swapping해주고 따라서 가상 메모리 관리를 OS가 알아서 해주기 때문이다
그리고 가상 메모리 기법이 필요한 또 다른 이유는 "(Paging 전제) 프로세스의 모든 Page가 매번 반드시 필요한 것은 아니다"
예를 들어서 어떤 Page는 해당 프로세스의 Error Handling을 위한 코드들이 모여있다고 하자
이러한 Error Handling Code는 에러가 발생할 때만 유효한 코드들이고, 결정적으로 에러가 엄청난 빈도로 발생하는 것은 아니다
따라서 이러한 Page들을 메인 메모리에 처음부터 올려버리는 것은 메모리를 낭비하고 있다고 볼 수 있다
>> 가상 메모리를 통해서 "필요한 Page(Demand Paging)"만 메모리에 올려서 활용하자
Demand Paging
Demand Paging은 실제로 Request가 들어오면 해당 Page를 메모리에 올리는 기법이다.
Demang Paging이 가지는 이점은 다음과 같다
I/O 사용량이 감소된다
해당 프로세스에게 Memory를 덜 할당할 수 있다
응답시간이 빠르다
결론적으로 메인 메모리상에 더 많은 프로그램을 올릴 수 있다
여기서 메모리에 올라간 Page들말고 올라가지 않는(쉬고 있는) Page들은 "Backing Store"라는 곳에서 보관되고 있다
Backing Store에 있는 Page들에 대한 Request가 들어가면 "Swapping"이 발생해서 Page가 메인 메모리로 올라간다
- 메인 메모리에 Free Frame이 존재하면 그냥 올리면 된다
- Free Frame이 없을 경우 "Page Replacement Algorithm"을 통해서 Page 교환을 해줘야 한다
그러면 여기서 가장 중요한 것은 "올라간 Page와 쉬고 있는 Page를 구분"하는 것이다
이것은 Page Table에 "Valid/Invalid Bit"를 설정해줌으로써 구분해준다
Valid/Invalid Bit
▶ Valid
Valid Bit로 설정된 Page는 다음 2가지 조건을 모두 만족한다
- 해당 Page는 Physical Memory상에 올라가 있는 상태이다
- 해당 Page는 access가 가능한 상태이다
▶ Invalid
Invalid Bit로 설정된 Page는 2가지 type이 존재한다
- Backing Store에서 쉬고 있는 Page
- 아예 해당 프로그램이 사용되지 않는 주소 영역
(1)의 경우 Swapping이 발생해서 메인 메모리로 올라가게 되면 Valid Bit로 재설정이 된다
(2)의 경우 access조차 못하고, access 시도를 하게되면 바로 (Addressing Error : Trap)이 발생하게 된다
(2)와 같은 상황이 발생하는 이유는 다음과 같다
어쨌든 Page Table은 "index"로 접근하는 Table Data Structure이다
따라서 Table이라는 자료구조 특성상 사이에 빈 공간이 존재하면 안된다
하지만 프로그램을 고정크기의 Page로 나눌 때는 어쩔 수 없이 프로그램이 사용하지 않는 Page가 분명히 존재할 것이다
따라서 이러한 "사용하지 않는 Page"들도 Page Table상에서 index를 가져야 하기 때문에 이러한 상황이 발생하게 된다
Backing Store에서 쉬고 있는 Page에 대한 access가 들어가게 되면 해당 Page가 즉시 메인 메모리로 올라가서 실행이 되는게 아니라 먼저 "Page Fault"가 발생하게 된다
Page Fault
Page Fault란, 요청한 Page가 메인 메모리에 적재되어 있지 않을 때 발생하는 것이다
Page Fault가 발생하게 되면 CPU는 자동적으로 OS로 넘어가게 된다
- Page Fault Trap
CPU를 넘겨받은 OS가 요청된 Page를 메인 메모리로 올려주는 역할을 수행해준다
※ Page Fault 과정
1. Invalid Bit로 표시된 Page에 access하면 MMU가 Trap을 발생시킨다 (Page Fault Trap)
2. Kernel Mode로 들어가서 Page Fault Handler가 invoke되고, Page Fault를 처리해준다
- 여기서 먼저 access 자체는 올바른 access인지 검사한다
- 올바른 access : Page가 존재하긴 하는데 Backing Store에서 쉬고 있음
- 잘못된 access : 해당 Page는 프로그램이 아예 사용하지 않는 Page or Page에 대한 접근 권한을 위반
- 잘못된 access의 경우 해당 프로세스를 abort시킨다 / 올바른 access의 경우 먼저 메인 메모리에 Free Frame이 있는지 확인한다
- Free Frame 존재 O : 그냥 Free Frame에 요청된 Page를 적재
- Free Frame 존재 X : 적재된 Page중에 victim을 골라서 교환 (Page Replacement Algorithm)
- 요청된 Page를 Disk로부터 읽어온다
- Disk에서 어떤 것을 읽어오는 작업은 굉장히 느린 작업이다
- 따라서 Disk I/O가 발생하는 동안에 해당 프로세스는 CPU를 선점당하게 되고 statusBlocking이 된다
- Disk I/O가 끝나게 되면 Page Table에서 해당 Page의 bit를 Valid Bit로 변경해주고, 적재된 Frame Number도 적어준다
- 여기서 Page Replacement Algorithm에 의해서 victim page가 swap out이 된다면 victim page의 bit를 invalid bit로 바꿔줘야 한다
3. Page Fault가 처리된 후, Page Fault가 발생한 프로세스는 다시 Ready Queue로 들어가서 CPU를 기다린다
4. 이후 해당 프로세스가 다시 CPU를 잡게 된다면 아까 Page Fault가 발생한 Instruction을 다시 실행한다
Demand Paging에서의 EAT(Effective Access Time)
Page Fault가 얼마나 발생하냐에 따라서 EAT는 달라진다
Page Fault Rate는 [0, 1]사이에 존재한다
- 0 : 절대 Page Fault 발생 X
- 1 : 매번 명령어 실행할 때마다 Page Fault 발생
- 일반적이니 시스템에서의 Page Fault Rate는 약 0.9정도 된다
>> EAT = (1 - p) × (Memory Access Time) + p × (Page Fault Time)
여기서 Page Fault Time은 다음을 포함한다
1. Page Fault Overhead : OS로 CPU가 넘어가서 Page Fault를 처리하는 순수한 Overhead
2. Swap Page Out : Free Frame이 없을 경우 victim page를 swap out시키는 시간
3. Swap Page In : Disk에 존재하는 요청된 Page가 Swap In되는 시간
4. Restart Overhead : 프로세스를 재시작시킬 때 발생하는 Overhead
여기서 (3) Swap Page In의 시간이 가장 오래 걸린다
왜냐하면 Disk I/O가 발생하는 시간이기 때문이다
그리고 (2)의 경우 Free Frame이 없을 경우에만 발생하는 시간이다
Page Replacement
Page fault가 발생할 경우, 요청된 Page를 Free Frame에 올려줘야 한다
여기서 Free Frame이 없는 경우 victim page를 선택해서 "Page Replacement"를 해줘야 한다
그런데 여기서 victim page가 메모리상에 올라온 이후로 1번이라도 modify되었다면 변경된 내용을 commit해주고 replace를 해줘야 한다
따라서 이러한 modify가 발생한 page는 가급적이면 victim page로 선택하지 않는 것이 좋다
여기서 활용되는 bit가 "Dirty Bit"이다
Dirty Bit는 해당 Page가 modify된 여부를 파악하기 위한 bit이다
- 0 : modify X
- 1 : modify O
따라서 가급적이면 Dirty Bit가 0인 page를 victim page로 선택하자
Page Replacement Algorithm
이 알고리즘의 목표는 Page Replace를 할 때, "Page Fault Rate"를 최소화하는 것이다
여기서는 "Reference String"이라는 String을 활용해서 알고리즘을 돌린다
Reference String이란 "Page가 참조된 순서"를 나열한 String이다
- 1 2 3 4 1 2 5 1 2 3 4 5 ....
1. Optimal Algorithm
Optimal Algorithm은 이름그대로 "최적화 알고리즘"이다. 따라서 이 알고리즘보다 Page Fault Rate를 최소화할 수 없다
Optimal Algorithm은 "가장 먼 미래에 Reference 되는 Page (앞으로 오랫동안 사용하지 않을 Page)를 replace"해주는 알고리즘이다
하지만 여기서 당연하게 생각해야 하는 것은 "미래는 알 수 없다"라는 것이다
따라서 Optimal Algorithm은 현실성이 없는 알고리즘이다. 동시에 가장 최적인 알고리즘이다
Example)
Reference String : <1 2 3 4 1 2 5 1 2 3 4 5> & Free Frame Size : 4
→ <1 2 3 4 1 2 5 1 2 3 4 5>
처음 1 2 3 4는 당연히 메모리에 없기 때문에 Page Fault가 발생한다
- Page Fault : 4회
- 현재 메모리 : <1 2 3 4>
| 1 | 2 | 3 | 4 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, 현재 Free Frame도 없기 때문에 victim page를 선택해야 한다
앞으로 참조될 page 순서를 보면 <1 2 3 4 5> 순서이다
따라서 page에 올라가있는 <1 2 3 4>중에서 가장 먼 미래에 참조되는 page는 4이므로 4를 victim page로 선택
- Page Fault : 5회
- Update 메모리 : <1 2 3 5>
| 1 | 2 | 3 | 5 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2 3은 메모리에 존재하기 때문에 그냥 access하면 된다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
4는 메모리에 없기 때문에 Page Fault가 발생하고, 현재 Free Frame도 없기 때문에 victim page를 선택해야 한다
앞으로 참조될 page 순서를 보면 <5>이다
따라서 1 2 3중에서 아무거나 victim page로 선택해주자
- Page Fault : 6회
- Update 메모리 : <4 2 3 5>
| 4 | 2 | 3 | 5 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 존재하기 때문에 그냥 access하면 된다
▶ Optimal Algorithm에서 Page Fault는 총 6번 발생한다
- 실제 시스템에 사용하기는 힘들지만 Optimal Algorithm은 다른 알고리즘의 성능에 대한 "Upper Bound"를 제공해준다
2. FIFO Algorithm
FIFO는 말그대로 먼저 들어온 page를 victim page로 선정해주는 알고리즘이다
Example 1)
Reference String : <1 2 3 4 1 2 5 1 2 3 4 5> & Free Frame Size : 3
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2 3은 메모리에 없기 때문에 Page Fault가 발생한다
- Page Fault : 3회
- 현재 메모리 : <1 2 3>
| 1 | 2 | 3 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
4는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
1이 가장 먼저 메모리에 올라갔기 때문에 1을 victim page로 선택해주자
- Page Fault : 4회
- Update 메모리 : <4 2 3>
| 4 | 2 | 3 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1은 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
2가 가장 먼저 메모리에 올라갔기 때문에 2를 victim page로 선택해주자
- Page Fault : 5회
- Update 메모리 : <4 1 3>
| 4 | 1 | 3 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
2는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
3이 가장 먼저 메모리에 올라갔기 때문에 3을 victim page로 선택해주자
- Page Fault : 6회
- Update 메모리 : <4 1 2>
| 4 | 1 | 2 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
4가 가장 먼저 메모리에 올라갔기 때문에 4를 victim page로 선택해주자
- Page Fault : 7회
- Update 메모리 : <5 1 2>
| 5 | 1 | 2 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
3은 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
1이 가장 먼저 메모리에 올라갔기 때문에 1을 victim page로 선택해주자
- Page Fault : 8회
- Update 메모리 : <5 3 2>
| 5 | 3 | 2 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
4는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
2가 가장 먼저 메모리에 올라갔기 때문에 2를 victim page로 선택해주자
- Page Fault : 9회
- Update 메모리 : <5 3 4>
| 5 | 3 | 4 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 존재하기 때문에 그냥 access하면 된다
▶ FIFO Algorithm(Frame Size : 3)에서 Page Fault는 총 9번 발생한다
Example 2)
Reference String : <1 2 3 4 1 2 5 1 2 3 4 5> & Free Frame Size : 4
일반적인 생각으로는 Frame Size를 늘리면 Free Frame이 많아지니까 Page Fault가 더 줄어들거라는 예상을 할 수 있다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
처음 1 2 3 4는 당연히 메모리에 없기 때문에 Page Fault가 발생한다
- Page Fault : 4회
- 현재 메모리 : <1 2 3 4>
| 1 | 2 | 3 | 4 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
1이 가장 먼저 메모리에 올라갔기 때문에 1을 victim page로 선택해주자
- Page Fault : 5회
- Update 메모리 : <5 2 3 4>
| 5 | 2 | 3 | 4 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1은 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
2가 가장 먼저 메모리에 올라갔기 때문에 2를 victim page로 선택해주자
- Page Fault : 6회
- Update 메모리 : <5 1 3 4>
| 5 | 1 | 3 | 4 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
2는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
3이 가장 먼저 메모리에 올라갔기 때문에 3을 victim page로 선택해주자
- Page Fault : 7회
- Update 메모리 : <5 1 2 4>
| 5 | 1 | 2 | 4 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
3은 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
4가 가장 먼저 메모리에 올라갔기 때문에 4를 victim page로 선택해주자
- Page Fault : 8회
- Update 메모리 : <5 1 2 3>
| 5 | 1 | 2 | 3 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
4는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
5가 가장 먼저 메모리에 올라갔기 때문에 5를 victim page로 선택해주자
- Page Fault : 9회
- Update 메모리 : <4 1 2 3>
| 4 | 1 | 2 | 3 |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
1이 가장 먼저 메모리에 올라갔기 때문에 1을 victim page로 선택해주자
- Page Fault : 10회
- Update 메모리 : <4 5 2 3>
| 4 | 5 | 2 | 3 |
▶ FIFO Algorithm(Frame Size : 3)에서 Page Fault는 총 10번 발생한다
Free Frame을 늘렸는데도 불구하고 역설적으로 Page Fault가 더 많이 발생하는 것을 알 수 있다
※ Belady's Abnomaly
Frame이 더 많은데도 불구하고 Page Fault가 더 발생하는 역설적인 현상을 "Belady's Abnomaly"라고 한다
3. LRU Algorithm (Least Recently Used)
LRU는 말그대로 "가장 최근에 덜 사용된 :: 가장 오래전에 사용된 Page를 Victim"으로 정하는 알고리즘이다
FIFO와 다른점은 가장 먼저 들어왔어도 최근에 access된 흔적이 있다면 해당 page는 victim이 아니라는 것이다
Example)
Reference String : <1 2 3 4 1 2 5 1 2 3 4 5> & Free Frame Size : 4
→ <1 2 3 4 1 2 5 1 2 3 4 5>
처음 1 2 3 4는 당연히 메모리에 없기 때문에 Page Fault가 발생한다
- Page Fault : 4회
- 현재 메모리 : <1 2 3 4>
| 1 (time 1) | 2 (time 2) | 3 (time 3) | 4 (time 4) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
| 1 (time 5) | 2 (time 6) | 3 (time 3) | 4 (time 4) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 오래전에 참조된 page는 3이니까 3을 victim page로 선택하자
- Page Fault : 5회
- Update 메모리 : <1 2 5 4>
| 1 (time 5) | 2 (time 6) | 5 (time 7) | 4 (time 4) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
| 1 (time 8) | 2 (time 9) | 5 (time 7) | 4 (time 4) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
3은 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 오래전에 참조된 page는 4이니까 4를 victim page로 선택하자
- Page Fault : 6회
- Update 메모리 : <1 2 5 3>
| 1 (time 8) | 2 (time 9) | 5 (time 7) | 3 (time 10) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
4는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 오래전에 참조된 page는 5이니까 5를 victim page로 선택하자
- Page Fault : 7회
- Update 메모리 : <1 2 4 3>
| 1 (time 8) | 2 (time 9) | 4 (time 11) | 3 (time 10) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 오래전에 참조된 page는 1이니까 1을 victim page로 선택하자
- Page Fault : 8회
- Update 메모리 : <5 2 4 3>
| 5 (time 12) | 2 (time 9) | 4 (time 11) | 3 (time 10) |
▶ LRU Algorithm(Frame Size : 4)에서 Page Fault는 총 8번 발생한다
4. LFU Algorithm (Least Frequently Used)
LRU는 말그대로 "가장 참조 빈도가 작은 Page를 Victim"으로 정하는 알고리즘이다
참조 빈도가 가장 적은 Page가 여러개일 경우 성능 최적화를 위해서 "가장 오래전에 참조된 Page : LRU"를 섞어서 활용할 수 있다
<장점>
LRU처럼 이전 참조 시점만 보는것이 아니라 장기적인 시간 규모로 판단하기 때문에 Page와 관련된 인기도를 고려할 수 있다
<단점>
구현이 복잡하다
Example)
Reference String : <1 2 3 4 1 2 5 1 2 3 4 5> & Free Frame Size : 4
→ <1 2 3 4 1 2 5 1 2 3 4 5>
처음 1 2 3 4는 당연히 메모리에 없기 때문에 Page Fault가 발생한다
- Page Fault : 4회
- 현재 메모리 : <1 2 3 4>
| 1 (1) | 2 (1) | 3 (1) | 4 (1) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
| 1 (2) | 2 (2) | 3 (1) | 4 (1) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 참조 빈도가 낮은 page은 3, 4 : 2개이다. 따라서 여기서 가장 오래전에 참조된 것도 고려함에 따라서 3을 Victim Page로 선택하자
- Page Fault : 5회
- 현재 메모리 : <1 2 5 4>
| 1 (2) | 2 (2) | 5 (1) | 4 (1) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
1 2는 메모리에 존재하기 때문에 그냥 access하면 된다
| 1 (3) | 2 (3) | 5 (1) | 4 (1) |
→ <1 2 3 4 1 2 5 1 2 3 4 5>
3은 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 참조 빈도가 낮은 page은 4, 5 : 2개이다. 따라서 여기서 가장 오래전에 참조된 것도 고려함에 따라서 4를 Victim Page로 선택하자
- Page Fault : 6회
- 현재 메모리 : <1 2 5 3>
| 1 (3) | 2 (3) | 5 (1) | 3 (1) |
여기서 잠깐 미래를 보자면 → 이 다음에 바로 4가 참조되는 것을 확인할 수 있다
하지만 여기서 4가 참조가 가장적게 일어나고 가장 오래전에 참조됨에 따라 Swap Out시켜버렸다
이렇게 LFU는 페이지의 인기도와 얼마나 오랫동안 참조되지 않았나를 고려할 수 있지만, 앞으로 다가올 참조 미래를 예상하지는 못한다
그래서 이러한 경우 효율성이 떨어질 수 있다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
4는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 참조 빈도가 낮은 page은 3, 5 : 2개이다. 따라서 여기서 가장 오래전에 참조된 것도 고려함에 따라서 5를 Victim Page로 선택하자
- Page Fault : 7회
- 현재 메모리 : <1 2 4 3>
| 1 (3) | 2 (3) | 4 (1) | 3 (1) |
여기서도 위와 같이 미래를 예상하지 못하기 때문에 곧바로 참조되는 Page를 Swap Out시키는 것을 볼 수 있다
→ <1 2 3 4 1 2 5 1 2 3 4 5>
5는 메모리에 없기 때문에 Page Fault가 발생하고, Free Frame도 없기 때문에 victim page를 선택해야 한다
가장 참조 빈도가 낮은 page은 3, 4 : 2개이다. 따라서 여기서 가장 오래전에 참조된 것도 고려함에 따라서 4를 Victim Page로 선택하자
- Page Fault : 8회
- 현재 메모리 : <1 2 5 3>
| 1 (3) | 2 (3) | 5 (1) | 3 (1) |
▶ LFU Algorithm(Frame Size : 4)에서 Page Fault는 총 8번 발생한다
현실적인 Paging System에서의 Replacement Algorithm
위에서 예시로 확인한 LRU나 LFU는 꽤 좋은 알고리즘이라고 생각된다
하지만 이러한 LRU나 LFU를 현실적인 Paging System에서의 Replacement Algorithm으로 사용할 수 있을까??
>> 결론적으로는 사용할 수 없다
LRU나 LFU를 사용한다는 것은 과정을 처음부터 살펴보자면
1. CPU가 어떤 Page의 Logical Address로 접근
2. MMU가 Physical Address로 변환해주고 Physical Address가 정상적인 access인지 확인
3. 비정상이라면 abort시키고, 정상이라면 Free Frame확인
4. Free Frame있으면 그냥 Swap In시키고, Free Frame없으면 "Replacement Algorithm"
애초에 "Address"를 통해서 접근을 했을 때 page fault가 발생하고 그에 따라서 Free Frame이 없으면 Replacement Algorithm을 돌린다
그런데 OS가 이렇게 주소 변환을 하는 과정을 알 수 있을까?? OS는 전혀 알 수 없다
LRU는 가장 오래전에 참조된 Page를 찾고, LFU는 참조 횟수가 가장 적은 Page를 찾는다
예를 들어서 Page Fault가 발생했다고 하자
그러면 Page Fault Trap이 발생함에 따라 CPU는 여기서 OS로 넘어가게 된다
그러면 OS는 Disk로 가서 요청된 Page를 Swapping함에 따라서 이 과정에서는 OS가 직접 개입하기 때문에 Page가 참조된 시간이나 횟수를 알 수 있다
하지만 Page Fault가 발생하지 않는 시간동안은 OS가 전혀 개입을 할 수가 없다
따라서 Page Fault가 발생하지 않는 시간동안 변환된 "시간 & 참조 & 주소 & bit & ..."는 OS가 어떠한 과정에 의해서 변경되었는지 알 수가 없기 때문에 LRU나 LFU 알고리즘을 현실적으로 사용할 수 없다는 것이다
>> 따라서 현실적으로는 Clock Algorithm이라는 LRU Approximation Algorithm을 사용한다
LRU Approximation Algorithm (Second-Chance Algorithm)
이 알고리즘에서는 각 Page별로 "Reference Bit"라는 것을 할당해준다
Reference Bit가 1이라는 것은 참조가 된 적이 있다는 의미이고, 0은 참조가 된 적이 없다는 의미이다
- 하지만 1이라고 설정되었다고 해서 언제 참조되었는지는 정확히 알 수 없다
이 알고리즘에서는 Page들이 원형 리스트 형태로 연결되어 있다
<Reference Bit가 0인 Page를 찾을 때까지 Pointer를 앞으로 이동시키기>
1. 이동하는 중에 Reference Bit가 1인 Page들은 전부 0으로 바꿔준다
>> 해당 Page가 자주 사용되는지 판별하기 위해서 0으로 바꿔준다 :: 만약 자주 사용된다면 다음 Pointer가 가리킬 때 1이 되어있을 것이다
2. Reference Bit가 0인 Page를 찾으면 해당 Page를 Victim Page로 선정한다
>> 1바퀴를 다 돌았는데도 불구하고(Second Chance) bit가 0이라는 의미는 해당 Page가 그 시간동안 참조가 안되었고 인기도 없는 Page라는 의미라고 생각하면 된다 / 자주 사용되는 Page라면 다음 chance때 bit가 1이 되어있을 것이다
여기서 처음에 모든 Page들의 Reference Bit가 1이었다면, 모든 Page가 Second-Chance를 부여받게 되고, 결국 FIFO와 비슷하게 돌아가기 때문에 Abnomaly현상이 발생하게 된다
Enhanced Second-Chance Algorithm
Enhanced라는 것은 Second-Chance에 Special Hardward를 하나 더 추가해준 알고리즘이다
>> "Dirty Bit" 추가
| Reference Bit | Dirty Bit | 설명 |
| 0 | 0 | 참조도 되지 않고, modify도 되지 않은 Page >> Victim으로 고르기 가장 좋은 Page이다 |
| 0 | 1 | 최근에 참조되지는 않았지만, modify가 된 Page이다 >> 만약 이 Page를 victim으로 골랐다면 replace되기전에 commit을 해주고 Swap Out해야 한다 |
| 1 | 0 | 최근에 참조 되었고, modify 되지 않은 Page >> 아마 다음에 또 참조될 확률이 높은 Page일 것이다 |
| 1 | 1 | 최근에 참조 되었고, modify도 된 Page |
Page Frame Allocation
이제는 각 프로세스에게 메인 메모리의 Page Frame을 "최소 몇개"를 할당해야 원활하게 동작할 수 있을까와 관련된 여러 문제를 고려해야 한다
메모리를 access하는 Instruction을 호출했는데 해당 Instruction을 까보니까 "여러 Page를 동시에 참조"한다고 하자
이런 경우는 명령어 수행을 위해서 최소한으로 할당되어야 하는 Frame의 개수가 존재한다
1) Fixed Allocation vs Priority Allocation
Fixed Allocation에는 {Equal Allocation & Proportional Allocation}이 존재한다
Equal은 각 프로세스별로 동일한 개수의 frame을 할당하는 것이고, Proportional은 프로세스의 크기에 비례해서 frame을 할당해주는 것이다
Priority Allocation은 프로세스의 우선순위에 의거해서 frame을 할당해주는 것이다
2) Global Allocation vs Local Allocation
Global Allocation
Global은 Replace할 때 "메인 메모리 전체 Frame"을 대상으로 replace할 page를 정하는 것이다
따라서 다른 프로세스에게 할당된 frame을 빼앗아 올 수 있다
Replacement Algorithm을 모든 프로세스들에 대해서 공통적으로 운영할 때 사용하는 할당 방법이다
Local Allocation
Local은 Replace할 때 "자신에게 할당된 Frame 내부에서 Victim"을 찾는 것이다
Replacement Algorithm을 프로세스별로 운영할 때 사용하는 할당 방법이다
하지만 Local은 메모리를 비효율적으로 사용하는 문제가 발생할 수 있기 때문에 일반적으로는 Global Allocation을 사용한다
Thrashing
Thrashing이란, 프로세스의 원활한 수행을 위한 최소 Frame조차 할당받지 못해서 Page Fault가 굉장히 많이 발생하는 현상을 뜻한다
- Thrashing : A process is busy swapping pages in and out
이렇게 Thrashing현상이 발생하면 프로세스는 본인의 일을 수행하기 위해서 CPU를 사용하는 것보다 Page Fault를 위한 Disk I/O에 더 많이 시간을 소비할 것이다
1. OS는 Thrashing : Page Fault가 너무 많이 발생하는게 "메모리에 너무 적은 Page를 올렸나"라고 오인해서 MPD(Multiprogramming Degree)를 높여야 한다고 생각해서 메모리에 다른 프로그램을 추가적으로 적재한다
2. 결국 추가적으로 적재됨에 따라서 프로세스별로 할당될 Page Frame이 더 줄어든다
3. 따라서 프로세스에게 더 잦은 Page Fault가 발생하게 된다
>> Swapping이 더 많이 발생함에 따라 CPU는 계속 더 놀게되니까 CPU 처리량이 계속 낮아지는 문제가 발생한다
이러한 Thrashing을 막기 위해서, 프로세스는 반드시 "필요한 최소 Frame"은 할당받아야 한다
여기서 "프로세스가 필요로 하는 최소 Frame 개수"는 어떻게 알 수 있을까???
>> 프로세스 실행 시 "Locality Model"을 활용해서 파악할 수 있을 것이다
static int add(int a, int b){
return a + b;
}이러한 함수가 프로세스 내부에 존재한다고 하자
그러면 여기서 Locality는 "저 함수를 수행할 수 있는 일련의 단위?"라고 보면 된다
따라서 Locality를 모두 수용할 수 있는 최소 Frame은 가져야 프로세스가 원활하게 수행될 수 있을 것이다
- Current Locality Size가 현재 할당된 Frame수보다 크다면 Thrashing이 발생할 것이다
- Current Locality Size > Allocated Frame Size
특정 시점에 그래프에서 "Memory Address 칠해진 부분"이 Locality라고 할 수 있다
당연히 프로세스는 실행함에 따라 계속 Locality가 변경된다
Working Set Model
Working Set Model에서는 "특정 시점에 집중적으로 참조되는 Page들의 집합"을 Locality Set = Working Set이라고 부른다
Working Set Model에서 프로세스는 본인의 Working Set전체가 메모리에 적재가 되어있어야만 수행이 된다
만약 Working Set 전체 중 일부가 메모리에 없는 경우 프로세스는 본인에게 지금까지 할당된 모든 Frame을 반납하고 Swap Out된다
- Thrashing을 방지하고, MPD를 결정한다
<Process A>
나는 Working Set 다 올리려면 Frame 5개 필요한데 3개만 할당해줬네
이 3개 다 반납하고 Swap Out되어야 겠다
※ Working Set 결정
Working Set은 "Working Set Window"를 통해서 결정된다
Working Set Window란 Integer값이고, 과거 어디 시점까지 Working Set으로 포함할지와 관련된 값이다
<Page Reference Table>
2 6 1 5 7 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 .....
이런 예시에서 Working Set Window값이 "10"이라고 하자
"1"시점에서 Working Set을 결정해보자
Working Set Window = 10이니까 6으로부터 과거 10까지 Reference를 살펴보자
<2 6 1 5 7 7 7 7 5 1>
>> Working Set = {1, 2, 5, 6, 7}
따라서 "1"시점에서 프로세스는 최소 {1, 2, 5, 6, 7}을 수용할 수 있는 5개의 Frame을 할당받아야 한다
"4"시점에서 Working Set을 결정해보자
Working Set Window = 10이니까 4로부터 과거 10까지 Reference를 살펴보자
<3 4 4 4 3 4 3 4 4 4>
>> Working Set = {3, 4}
따라서 "4"시점에서 프로세스는 최소 {3, 4}를 수용할 수 있는 2개의 Frame을 할당받아야 한다
※ Working Set Window
1) Window Size가 너무 작다면
Locality Set을 모두 수용하지 못할 수 있다
2) Window Size가 너무 크다면
너무 과거까지 보기 때문에 전혀 상관없는 Locality까지 포함할 수 있다
여러 규모의 Locality Set을 수용해서 처리율이 낮아질 수 있다
3) Window Size가 무한대라면
전체 프로그램을 구성하는 Page를 Working Set 자체라고 간주한다
※ Working Set 구현
Window Size = 10000이고, 시스템에서 5000마다 Interrupt를 발생시킨다고 하자
그러면 Page Table에는 2개(10000/5000)의 추가적인 column을 생성해줘야 한다
<Time : 0 ~ 5000>
0 ~ 5000사이에 Page에 대한 참조 기록을 Column(1)에 기입해준다
참조가 되면 1로 bit를 바꿔주기
5000에 interrupt가 발생함에 따라서 이러한 결과가 진행되었다고 하자
그러면 여기서 Column(1)의 내용을 전부 Column(2)로 coppy해주자
<Time : 5000 ~ 10000>
이 구간사이에도 참조되는 결과를 column(1)에 기입해주자
일단 표를 통해서 알 수 있는 사실은 "Column(2)"는 0 ~ 5000사이의 참조 결과이고 "Column(1)"은 5000 ~ 10000사이의 참조 결과이다
따라서 이를 통해서 추리할 수 있는 사실은 다음과 같다
Page(1) : 이 페이지는 0 ~ 5000 사이에서 참조가 되었구나
Page(2) : 이 페이지는 5000 ~ 10000 사이에서 참조가 되었구나
Page(3) : 이 페이지는 invalid bit이고, 0 ~ 10000사이에 참조된 적이 없구나
Page(4) : 이 페이지는 0 ~ 5000 사이에서도 참조가 되었고, 5000 ~ 10000 사이에서도 참조가 되었구나
※ Working Set & Page Fault Rate
Working Set은 Window Size를 통해서 과거의 access 패턴을 활용해서 Working Set을 결정한다
따라서 특정 시점에서 구한 Working Set은 정확할 수가 없다
>> Working Set을 처음 구할때는 Page Fault가 증가할 것이다
그리고 Window Size만큼 지나고 나서 보는 Working Set은 꽤 정확할 것이다
하지만 Window Size 이후에는 어차피 또 Working Set을 과거 access 패턴에 의해서 새로 구하기 때문에 Page Fault가 증가한다
Window Size 시간만큼 학습을 통해서 Working Set을 정확하게 파악할 수 있다.
>> 물론 학습하는 동안에는 Page Fault Rate가 증가한다
그리고 학습이 끝나게 되면 다시 Page Fault Rate가 감소한다
PFF Scheme (Page Fault Frequency)
Working Set Model처럼 Window Size에 의거해서 대략적인 Working Set을 추측하는게 아니라 PFF는 실제 Page Fault Rate를 통해서 frame을 더 할당해줄지 빼앗을지를 결정하는 것이다
▶ Page Fault Rate가 상한선을 넘는다면
지금 해당 프로그램이 Page Fault가 너무 많이 발생하고 있으니까 Frame을 더 할당해주자
▶ Page Fault Rate가 하한선 이하이면
지금 해당 프로그램이 Page Fault가 거의 발생하지 않았다는 것은, Frame이 너무 많다는 의미이므로 Frame을 빼앗아서 다른 프로세스에게 주자
