페이지 교체 알고리즘.md

페이지 교체 알고리즘

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

• 좀 더 자세하게 생각해보면?

가상 메모리는 요구 페이지 기법(= 요구 페이징)을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둠

하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있음

따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 함

여기서 어떤 페이지를 out 시켜야할 지 정해야 함.

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

페이지 교체 알고리즘

1. FIFO 알고리즘

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

2. OPT 알고리즘

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

FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음

하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘임

1. LRU 알고리즘

   Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

   최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나옴

   OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘

   (실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)

   OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나임

   

Q. 면접 질문

요구 페이징이란?

가상메모리에서 필요한 프로그램만 메모리에 적재하는 방법이다.

LRU에 대해서 설명해 보세요. (N사 전화면접)

LRU는 페이지 교체 알고리즘 중 하나로, 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 방식이다.