[운영체제] 페이지 교체 알고리즘

Page reference string

페이지 교체 알고리즘을 살펴보기 전에 Page reference string이라는 용어를 알아야 한다.

CPU가 내는 주소는 이진수 단위이지만, 페이지 교체 알고리즘을 계산하기 위해서는 이진수 주소 단위가 아닌 페이지 단위로 계산해야한다.

 

CPU 논리 주소	요청할 페이지 번호
100	1
101	1
432	4
612	6
103	1
104	1
611	6
612	6

예를 들어, CPU가 내는 주소를 위와 같이 표현해보자. 편의를 위해 주소는 십진수로 표현했다.

만약 페이지 크기를 100이라 하면, 우측과 같이 된다.

주소 100번지는 1번 페이지에서 offset이 0인 위치이고, 101은 1번 페이지의 offset 1인 위치라고 볼 수 있다.

마지막으로 페이지 번호로 나타낸 것을 page reference string으로 나타내면 {1, 4, 6, 1, 6}이다.

이는 간단히 말하면 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다.

이 이유는 연속된 페이지를 참조할 때는 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없기 때문이다.

즉, CPU가 가리키는 page의 번호가 연속적으로 동일하다면 disk로 가서 page를 가져올 필요가 없으므로 위의 번호들만 가지고 판단하는 것이 바람직하다.

 

 

요구 페이징(Demand Paging)

프로세스의 주소 공간을 메모리로 적재하는 기법이다.

프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라, 당장 사용될 페이지만 올리는 방식이다.

특정 페이지에 대해 CPU의 요청이 들어온 후에 해당 페이지를 메모리에 적재한다.

 

특정 프로세스를 구성하는 페이지 중, 어떤 페이지가 메모리에 존재하고 존재하지 않는지를 구별해야 한다.

요구 페이징에서는 valid-invalid bit(유효-무효 비트)를 사용해 각 페이지가 메모리에 존재하는지를 표시한다.

 

CPU가 참조하려는 페이지가 현재 메모리에 올라와있지 않아서 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재라고 한다.

 

 

페이지 부재 시 동작 과정

[운영체제] 페이징 교체 알고리즘

 

페이지 교체란

• 페이지 부재 발생 시 요청된 페이지를 디스크에서 메모리로 읽어와야 하는데, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
• 이런 경우 메모리에 올라와있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하여 새로운 페이지를 메모리에 올려야 한다.
• 이러한 과정을 페이지 교체라고 부르며, page-out이 된 페이지를 victim page라고 한다.

 

 

페이지 교체 알고리즘의 종류

• OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO - First-In First-Out
• LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
• LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체
• MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체
• NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체

 

FIFO (First In First Out)

https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

First-In First-Out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘 

• 가장 먼저 메모리에 올라온 페이지를 교체한다.
• 일반적인 경우에서 프레임수가 늘어날수록 페이지 부재수가 줄어든다.
• Belady's Anomaly - 프레임 수가 늘어난다고 항상 페이지 부재 수가 줄어드는 것은 아니다. 
• RS(Reference String)에 지역성이 있다면 그렇지 않은 경우보다 상대적으로 페이지 부재 수가 줄어든다. 

 

OPT (Optimal)

Optimal 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보내는 알고리즘 

• 가장 이상적인 알고리즘이다. 
• FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있다. 
• 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘이다. 
• 프로세스가 앞으로 사용할 페이지를 미리 알아야 하므로 실제 시스템에서 온라인으로 사용할 수 없는 오프라인 알고리즘이다.

 

LRU (Least Recently Used)

Least Recently Used, 가장 오랫동안 사용하지 않은 페이지를 교체 

• FIFO의 이상 현상이 발생하지 않는다.
• 메모리 페이지의 참조 성향 중 시간 지역성을 고려한 알고리즘이다. 
  • 시간 지역성 : 최근에 참조된 페이지가 가장 가까운 미래에 다시 참조될 가능성이 높음 → 페이지마다 카운터가 필요하다.
• Queue로 구현할 수 있다. 사용한 데이터를 큐에서 제거하여 맨 위로 다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제
• 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생한다.

 

 

LFU (Least Frequently Used) 

Least Frequently Used, 참조 횟수가 가장 낮은 페이지를 교체

• 페이지의 참조 횟수로 교체할 페이지를 결정한다.
• LRU는 직전 참조된 시점만을 반영하지만, LFU는 참조 횟수를 통해 장기적 시간규모에서의 참조 성향을 고려할 수 있다.
• 가장 최근에 불러온 페이지가 교체될 수도 있어 이에 따른 오버헤드가 발생할 수 있다. 
• 초기한 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 메모리에 잔존해 문제가 될 수 있다. 

 

 

SCR (Second Chance Replacement)

Second Chance Replacement, 가장 오랫동안 주기억장치에 있었던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 알고리즘 

• FIFO 기법의 단점을 보완하는 기법이다.
• 큐의 상단에서 꺼낸 대상의 참조 비트를 검사하여 0이면 교체 대상으로 선택하고 1이면 0으로 바꿔 큐의 뒤에 삽입한다.
• 만약 모든 페이지의 참조 비트가 세팅되어 있다면, 큐의 첫번째 요소였던 페이지가 두번 검사될 것이고, 해당 페이지를 내쫓는다.

 

 

정리

• 페이지 교체 알고리즘에서는 일반적인 경우 프레임 수가 늘어날수록 페이지 부재수는 줄어든다.
• FIFO, Random 알고리즘에서는 프레임 크기가 증가할 때 페이지 부재수도 증가하는 모순 현상이 나타난다.
• RS에 지역성이 있을 때에는 그렇지 않을 때보다 전체적으로 페이지 부재수가 더 낮은 것을 확인할 수 있다.
• 모순 현상을 나타내는 FIFO, Random 알고리즘의 사용은 가급적 피하고 LRU, LFU 알고리즘의 사용이 효율적이다.
• 가장 많이 쓰는 알고리즘은 LRU 알고리즘이다.

 

 

 

참고

https://steady-coding.tistory.com/526

https://doh-an.tistory.com/28

https://matice.tistory.com/3

https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

https://wansook0316.github.io/cs/os/2020/04/06/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%A0%95%EB%A6%AC-17-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.html