[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가 프로그램을 실행하기 위해서는 메모리에서 데이터를 가져와야 하는데, 그 데이터가 메모리에 없다면 하드디스크로부터 데이터를 가져와 메모리에 올려야 한다. 이 과정을 최소화하기 위한 예측이 필요한데 바로 메모리 지역성이라는 원리가 여기에 활용된다. 

 

메모리 지역성을 설명하는 그림. 특정 시간 동안 일관된 범위의 코드가 지속적으로 읽혀진다. 

 

간단한 구구단 코드에서 (a) 블록의 코드는 한 번에 9회 반복하고, (b) 코드는 가장 나중에 한 번 실행된다.

 

3. 스레싱(Thrashing)

스레싱: 띄워 놓은 프로그램 수가 많아지면 어느 순간 페이지 부재가 과도하게 발생한다.

프로그램을 과도하게 많이 띄워 놓으면 어느 순간까지는 페이지 교체를 진행하면서 CPU가 실행을 잘 하다가 성능이 급격하게 떨어지는 순간이 온다. 원인은 프로세스가 실제 실행 시간 보다도 더 많은 시간을 페이징에 사용하고 있기 때문이다. 필요한 프로그램만 띄워서 사용해야 쾌적하게 컴퓨터를 사용할 수 있는 이유다. 

 

참고

https://blog.naver.com/jevida/140192459532