[OS] 페이지 교체 알고리즘

페이지 부재 발생 → 새로운 페이지를 할당해야 함 → 현재 할당된 페이지 중 어떤 것 교체할 지 결정하는 방법

Demanding Paging은 요구되어지는 페이지만 backing store에서 가져온다. 하지만 프로그램들이 계속 실행함에 따라 요구 페이지도 계속 늘어나고, 언젠가는 메모리가 가득 차게 될 것이다.(memory full)
여기서 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면 이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내고(page-out), 새로운 페이지를 메모리에 올려야한다.(page-in) 이를 페이지 교체라고 한다. 여기서 backing store로 page-out이 된 페이지를 victim page라고 한다.

• 요구 페이징(Demanding Paging)
  • 필요한 페이지만 메모리 할당하는 페이징 기법.
  • 기존의 페이지 테이블과 다른 점은 valid bit가 추가되었다. 이는 현재 메모리에 페이지가 있는지 없는지를 나타내는 비트이다. 현재 페이지가 메모리에 있다면 1, 없다면 0값을 갖는다. 
  • 가상 메모리를 만드는 방법은 대표적으로 두 가지가 존재하지만, 대부분 요구 페이징을 사용하므로 가상 메모리와 요구 페이징을 같은 용어로 사용하는 경우가 많다.

 

1. 페이지 부재(Page Fault)

페이지 부재는 CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 즉, 페이지 테이블의 valid bit값이 0인 경우이다.

요구 페이지(Demanding Paging)

페이지 부재 처리 과정

위 그림은 page fault가 발생했을 때 처리하는 과정을 나타낸 것이다.

1. 해당 페이지가 메모리에 있는지 valid bit를 확인한다.
2. valid bit가 0이라면 CPU에 인터럽트 신호를 보내어 운영체제 내부 해당 ISR(Interrupt Service Routine)로 점프한다.
3. 해당 ISR에서 backing store(디스크)를 탐색하여 해당 프로세스의 페이지를 찾는다.
4. 해당 페이지를 비어있는 프레임에 할당한다.
5. 페이지 테이블을 갱신한다.(프레임 번호 설정, valid bit 1로 변경)
6. 다시 명령어로 돌아가서 실행한다.

1.2. 페이지 교체(Page Replacement)

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다. 하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다. 따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 page-out하고, 해당 공간에 현재 필요한 페이지를 page-in 시켜야 한다.

여기서 어떤 페이지를 page-out 시켜야할 지 정해야 하는데, 메모리에 올라가 있는 페이지 중 CPU에 수정(modigy)되지 않는 페이지를 고르는 것이 효율적이다. 수정되지 않은 페이지는 page-out이 될 때 backing store에 쓰기(write) 연산을 할 필요가 없기 때문이다. backing store는 읽는 시간도 느리지만, 거기에 더해 쓰기 작업까지 한다면 더욱 비효율적일 것이다.(이때, page-out 되는 페이지를 victim page라고 부른다)

1.2.1. Victim Page(희생양 페이지)

해당 페이지가 수정되었는지 안되었는지를 판단할 수 있어야 하는데, 이를 위해 페이지 테이블에 modified bit(=dirty bit)를 추가하여 이를 검사한다. 해당 페이지가 수정되었다면 이 비트를 1로 두고, 수정되지 않으면 0으로 둔다. 이를 이용해서 victim page는 최대한 수정되지 않은 페이지를 선택한다.

위 그림은 modified bit를 추가한 페이지 테이블의 모습이다. 여기서 수정되지 않은 페이지는 0, 2, 3번 3개의 페이지가 존재하는데 이 중에서는 어떤 페이지를 선택해야 할까?

제일 간단한 방법은 랜덤하게 선택하는 것이지만, 이는 성능을 보장할 수 없다. 그 다음은 가장 먼저 메모리에 올라온 페이지를 희생양 페이지로 선택하는 것이다. 이는 아주 유명한 FIFO(First-In First-Out) 방식이다. 이 외에도 여러가지 방법이 존재한다.

이와 같은 상황에서 상황에 맞는 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재한다.

 

2. 페이지 교체 알고리즘

Page Reference String

페이지 교체 알고리즘을 살펴보기 전에 Page reference string 이라는 용어를 알아야 한다. CPU가 내는 주소는 이진수 단위이지만, 페이지 교체 알고리즘을 계산하기 위해서는 이진수 주소 단위가 아닌 페이지 단위로 계산해야한다.

예를 들어, CPU가 내는 주소를 간단히 십진수로 표현하여 {100, 101, 102, 432, 612, 103, 104, 611, 612} 라고 하자. 만약 페이지 크기가 100bytes라면, 위 주소를 페이지 번호로 나타내면 {1, 1, 1, 4, 6, 1, 1, 6, 6} 이다. 주소 100번지는 1번 페이지에서 offset이 0인 위치이고, 101은 1번 페이지의 offset 1인 위치라고 볼 수 있다.

마지막으로 페이지 번호로 나타낸 것을 page reference string으로 나타내면 {1, 4, 6, 1, 6}이다. 이는 간단히 말하면 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다. 이 이유는 연속된 페이지를 참조할 때는 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없기 때문이다.

정리하면, page size = 100bytes 일때

• CPU 주소 = {100, 101, 102, 432, 612, 103, 104, 611, 612}
• Page 번호 = {1, 1, 1, 4, 6, 1, 1, 6, 6}
• Page reference string = {1, 4, 6, 1, 6}

2.1. First-In First-Out(FIFO)

• victim page : page-out 되는 페이지는, 가장 먼저 메모리에 올라온 페이지
• 아이디어 : 초기화 코드가 더 이상 사용되지 않을 것이라는 아이디어에서 시작되었다.
  

  

• First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
• 가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법이다.
• 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능하다.
• Belady's Anomaly : 프레임 수가 증가하면(= 메모리 용량이 증가하면) page fault 수가 줄어드는 것이 정상적이지만, 특정한 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault 수가 오히려 증가하는 이상 현상이 발생한다. 이를 Belady's Anomaly라 한다.

2.2. Optimal(OPT)

OPT는 말그대로 가장 효율적인 페이지 교체 알고리즘이다. 이 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 희생양 페이지로 선택한다.

• victim page : page-out 되는 페이지는, 가장 오랫동안 사용되지 않을 페이지

• Optimal 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄
• FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있다.
• 하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘이다.

2.3. Least-Recently-Used(LRU)

• victim page : page-out 되는 페이지는, 최근에 사용하지 않은 페이지
• 아이디어 : 최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이다. (실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)

• Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘
• LRU는 근사 해를 구하므로 OPT보다는 페이지 결함이 더 일어날 수 있지만, FIFO보다는 일반적으로 적게 일어난다. 그러므로 현재 대부분 환경에서는 LRU를 사용하고 있다.
• OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘
• 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다.
• 최근 참조 시각을 소프트웨어적으로 유지해야하므로 알고리즘 운영에 오버헤드가 발생한다.

 

3. 교체 방식

Global 교체

메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

Local 교체

메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

 

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있다. 따라서, 다양한 프로세스의 페이지가 메모리에 존재한다.

페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대해 차이가 있다. → 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 한다. 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적이다.

 

 

참고

• https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-15.-%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC
• https://gyoogle.dev/blog/computer-science/operating-system/Page%20Replacement%20Algorithm.html
• https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-16.-%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