[ Paging System에서 LRU, LFU 사용 가능? ]
만약 CPU에서 프로세스 A가 Running 중일 경우, 프로세스 A의 논리적인 메모리에서 Instruction을 하나씩 읽어와서 실행한다.
CPU가 프로세스 A에 대한 논리적 주소를 주면 Page Table을 통해서 물리적 메모리 주소로 변환하여 해당 주소의 내용을 CPU로 읽어 들어야 한다.
주소 변환 후, 해당 페이지가 물리적 메모리에 올라와 있으면 물리적 메모리에서 직접 내용을 읽어 CPU로 가져간다.
이 과정에서 운영체제가 하는 일은 없다.
주소 변환은 하드웨어적으로 일어나는 일이며, CPU는 프로세스 A가 가지고 있으면서 주소 변환 후 메모리 참조를 한다.
반면에 프로세스 A가 Running 하면서 주소 변환을 요청했는데 Invalid라면 요청한 페이지가 Backing Store에 있어 Page Fault가 난다.
Page Fault Trap이 발생하면 CPU 제어권이 프로세스 A에서 운영체제로 넘어가며, 운영체제는 Disk에 있는 페이지를 읽어와서 물리적 메모리에 올려놔야 한다.
이 과정에서 Replacement를 해 어떤 페이지를 쫓아낼지 정해야 한다.
Paging System에서는 운영체제한테 주어지는 정보가 반쪽이다.
메모리에 그 페이지가 이미 있으면 운영체제가 알 수 있는 정보가 없고, 메모리에 해당 페이지가 없다면 CPU 제어권이 운영체제에게 넘어와서 여러 정보들이 주어진다.
결론적으로, Page Fault가 발생하면 운영체제는 디스크에 있던 페이지가 메모리로 올라오는 시간을 알 수 있지만, 그렇지 않다면 운영체제는 알지 못한다.
LFU 알고리즘을 사용한다면 이 중에서 참조 횟수가 가장 적은 페이지를 쫓아내야 하는데, 운영체제는 페이지들의 참조 횟수를 알 수 없다.
페이지가 이미 물리적 메모리에 올라왔을 경우에는 CPU 제어권이 운영체제에게 넘어가지 않고 하드웨어적으로 주소 변환해 CPU로 읽어 들이기 때문이다.
그래서 운영체제는 어떤 페이지가 가장 최근에 참조되었는지, 어떤 페이지의 참조 횟수가 제일 많은지 모르기 때문에 Paging System에서는 사용할 수 없다.
✓ 캐싱 기법
- 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시, 캐시로부터 직접 서비스하는 방식
- Paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용 (LRU, LFU 사용 가능)
✓ 캐시 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- Buffer caching이나 Web caching의 경우 : 시간 복잡도 O(1)에서 O(logn) 정도까지 허용
✓ Paging System인 경우
- Page Fault인 경우에만 OS가 관여함, 페이지가 이미 메모리에 존재하는 경우 참조 시각 등의 정보를 OS가 알 수 없음.
- O(1)인 LRU의 list 조작 불가능
[ Clock Algorithm ]
Paging System에서는 LRU, LFU 알고리즘을 사용하지 못하기 때문에 Clock 알고리즘을 사용한다.
운영체제는 가장 오래전에 사용된 페이지를 내쫓는 것 대신에 최근에 사용되지 않은 페이지를 쫓아내지 않는 방법을 사용한다.
페이지들을 참조할 때, 하드웨어는 Referecne Bit를 1로 세팅하는 역할을 하고 운영체제는 0인 페이지를 내쫓는다.
각각의 사각형이 물리적 메모리에 들어있는 Page이며 각 페이지에는 Reference Bit가 있다. 어떤 페이지가 참조되어서 CPU가 그 페이지를 읽어가기 전에 Reference Bit을 1로 표시해 준다.
Page Fault가 나서 운영체제가 어떤 페이지를 쫓아내려고 할 때, 하드웨어가 세팅해 놓은 Reference Bit를 확인한다.
만약 그 Bit가 1이면 0으로 바꾸고 그다음 페이지의 Bit를 확인한다. 그 페이지의 Bit도 1이면 0으로 바꾸고 다음 페이지를 확인한다.
이런 방식으로 확인하다가 Bit가 0인 페이지를 만나면 그 Page를 내쫓는다.
그리고, Reference Bit 외에 Modified Bit도 함께 사용한다.
페이지는 Read로 참조될 수도 있고 Write로 참조될 수도 있으며, 만약 Write로 참조되면 하드웨어가 Modified Bit를 1로 세팅한다.
Reference Bit가 0이면 쫓아내야 하는데, 그 페이지의 Modified Bit가 0이면 Backing Store에서 물리적 메모리에 올라온 이후로 Write가 발생하지 않은 것이다.
이러한 페이지를 쫓아낼 때에는 어차피 동일한 값이 Backing Store에 존재하기 때문에 그냥 메모리에서 쫓아내기만 하면 된다.
반면에 Modified Bit가 1이면 물리적 메모리에 올라온 이후로 적어도 한 번은 CPU에서 내용을 수정했다는 뜻이다.
이런 페이지를 쫓아낼 때에는 Backing Store에 변경된 내용을 반영한 다음에 메모리에서 내쫓아야 한다.
가능하면 Modified Bit가 0인 걸 우선해서 쫓아낸다면 조금 더 빠를 수 있다.
✓ LRU의 근사 (Approximation) 알고리즘
- 여러 명칭으로 불림 : Second Chance Algorithm, NUR (Not Used Recently) 또는 NRU (Not Recently Used)
- Reference bit을 사용해서 교체 대상 페이지 선정 (Circular List)
- Reference bit 가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
- 포인터 이동하는 중에 reference bit 1은 모두 0으로 바꿈
- Reference bit가 0인 것을 찾으면 그 페이지를 교체
- 한 바퀴 되돌아와서도 (=second chance) 0이면 그때에는 replace 당함
- 자주 사용되는 페이지라면 second chance가 올 때 1
✓ Clock Algorithm의 개선
- reference bit 과 modified bit (dirty bit)을 함께 사용
- reference bit = 1 : 최근에 참조된 페이지
- modified bit =1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)
