[OS] 페이지 교체 알고리즘(Page Replacement Algorithm) 5가지와 스레싱(Thrashing) 현상
1. 페이지 교체 알고리즘 종류
메모리가 다 찬 상태에서, 메모리에 올라간 상태의 페이지들 중 어떤 것을 내리고 새 페이지로 교체할지 최선책을 내려야 한다. 최소한의 횟수로 페이지 폴트 인터럽트가 발생해야 CPU가 여러 프로그램을 동시에 실행할 때 처리 지연이 적다. 이를 판단하는 대표적인 알고리즘에는 5가지 정도가 있다.
1-1. FIFO
- 단순하게 가장 먼저 들어온 페이지를 내리고 새 페이지로 교체하는 알고리즘이다.
- 만약 page 1 -> page 3-> page 4 -> page 5 순으로 페이지가 올라가서 꽉 찬 상태라면, 새로 참조해야 하는 페이지인 page 2는 page 1과 교체가 된다.
1-2. OPT(OPTimal Replacement Algorithm)
- 가장 이상적으로 페이지 교체를 최소화하는 방법은 바로 애초에 인터럽트가 발생하지 않도록 준비하는 것이다.
- 앞으로 가장 오랫동안 사용하지 않을 것 같은 페이지를 내리고, 해당 공간에 새 페이지를 올리는 방식이다.
- 이건 앞으로 어떤 페이지가 필요할지 100% 알기 어렵기 때문에 일반적인 OS에서는 불가하다.
1-3. LRU(Least Recently Used)
- 가장 오래 전에 참조된 페이지를 교체하는 방법이다.
- 가장 많이 사용되는 페이지 교체 알고리즘이다.
1-4. LFU(Least Frequently Used)
- 가장 적게 사용된 페이지를 교체하는 방법이다.
1-5. NUR(Not Used Recently)
- LRU와 마찬가지로, 최근에 사용하지 않은 페이지부터 교체하는 방법이다.
- 각 페이지마다 참조비트(R), 수정비트(M)를 둔다.
- (0,0), (0,1), (1,0), (1,1) 순으로 페이지가 교체된다.
2. 메모리 지역성
메모리 지역성이란 지금 참조하는 메모리 주변을 다음에도 참조할 확률이 높다는 원리다. CPU가 프로그램을 실행하기 위해서는 메모리에서 데이터를 가져와야 하는데, 그 데이터가 메모리에 없다면 하드디스크로부터 데이터를 가져와 메모리에 올려야 한다. 이 과정을 최소화하기 위한 예측이 필요한데 바로 메모리 지역성이라는 원리가 여기에 활용된다.
3. 스레싱(Thrashing)
프로그램을 과도하게 많이 띄워 놓으면 어느 순간까지는 페이지 교체를 진행하면서 CPU가 실행을 잘 하다가 성능이 급격하게 떨어지는 순간이 온다. 원인은 프로세스가 실제 실행 시간 보다도 더 많은 시간을 페이징에 사용하고 있기 때문이다. 필요한 프로그램만 띄워서 사용해야 쾌적하게 컴퓨터를 사용할 수 있는 이유다.
참고