운영체제 Ch.6 - 페이지교체 알고리즘 : FIFO, LRU, NUR, LFU

스와핑이 일어날 때 페이지교체 알고리즘(page replacement algorithm)에 의해 페이지가 교체되게 됩니다.

오프라인알고리즘

오프라인알고리즘은 가장 좋은 알고리즘(스와핑이 적게 일어남)이라고 일컫는 알고리즘이며 이는 가장 먼 미래에

참조되는 페이지와 현재의 페이지를 바꾸는 알고리즘(LFD, Longest Forward Distance)입니다. 예를 들어 0, 1, 2, 3, 4, 2 이렇게 들어온다고 가정하면 가장 미래에 참조되는 2와 스와핑하는 것을 말합니다.

그러나 미래에 사용되는 프로세스를 우리는 알지 못합니다. 즉, 사용할 수 없는 알고리즘이지만 다른 알고리즘과의 성능비교에 대한 상한선을 제공합니다.

오늘 : word → ppt → 게임 했다고 해서 내일도 이런 순서대로 하는건 아니다. 미래는 아무도 모른다.

오프라인 알고리즘은 페이지 교체 알고리즘에 대한 상한선(upper bound)을 제공합니다. 이는 페이지 교체 알고리즘의 성능을 평가하고 비교하는 데 도움이 됩니다. 오프라인 알고리즘은 다른 페이지 교체 알고리즘의 성능을 측정하고 개선하기 위한 기준으로 활용됩니다.

 

 

FIFO

FIFO(First In First Out)는 가장 먼저 온 페이지부터 교체하는 방법을 말합니다.

앞의 그림처럼 1, 3, 0 순서대로 바뀌는 것을 볼 수 있습니다.

 

LRU

LRU(Least Recently Used)는 최근에 사용되지 않은 페이지를 바꾸는 방법입니다.

즉, 참조가 오래된 페이지를 바꿉니다. 이를 위해서 각 페이지마다 최근 사용한 횟수를 나타내는 자료구조를 따로 만들어야 할 수도 있습니다. 예를 들어 7 0 1 2 0 3 0 4로 페이지 요청이들어온다고가정하고4개의페이지만담는다고 가정하면 다음과 같이 됩니다.

1. 처음 7 0 1 2 를담고 그 다음 0이들어왔을때는 페이지 히트가 되서 스와핑이일어나지않습니다.
2. 그 다음 3이 들어왔을 때 참조가 가장 오래된 7을 바꿉니다.
3. 이후 0이 다시 들어어고 스와핑이 일어나지 않습니다.
4. 그리고 4가 들어왔을 때 그때 가장 오래된 1과 바꿉니다.

NUR

LRU에서 발전한 알고리즘이자 NUR(Not Used recently) 또는 NRU(Not Recently Used) 라고도 불리는 알고리즘입니다.

일명 clock 알고리즘이라고 하며 먼저 페이지마다 0과 1을 가진 비트를 둡니다. 1은 최근에 참조되었고 0은 참조되지 않음을 의미합니다. 만약 한 바퀴 도는 동안 사용되지 않으면 0이 됩니다. 시계 방향으로 돌면서 0을 찾고 0을 찾은 순간 해당 페이지를 교체하고,해당 부분을 1로 바꾸는 알고리즘입니다.

LFU

LFU(Least Frequently Used) 알고리즘은 가장 참조 횟수가 적은 페이지를 교체하는

알고리즘입니다. 예를 들어 0, 1, 2, 0, 0, 1, 2, 3이렇게 들어오고3개의페이지밖에없다고하면다음과같이 교체가 됩니다.

1. 0, 1, 2를 그대로 담습니다.

2. 0페이지히트입니다.0의참조횟수:2

3. 0페이지히트입니다.0의참조횟수:3

4. 1페이지히트입니다.1의참조횟수:2

5. 2페이지히트입니다.2의참조횟수:2

6. 3 페이지 히트입니다.  가장 참조횟수가 적은 1과 스와핑하게 됩니다.

 

페이지 교체 알고리즘의 중요성

페이지 교체 알고리즘은 면접에서 자주 물어보는 주제 중 하나입니다. 이는 캐싱과 관련된 기본 개념을 이해하는 데 중요한 이유가 있습니다.

캐시 관리에서 핵심적인 질문은 어떤 데이터를 캐시에 올려야 하는가와 어떻게 스와핑을 최소화하는가입니다. 이것은 대규모 서비스에서 성능 최적화를 위해 중요한 고려 사항 중 하나입니다.

 

따라서 페이지 교체 알고리즘에 대한 이해는 캐시 및 메모리 관리를 개선하는 데 도움이 되며, 대규모 시스템에서 성능을 향상시키는 데 필수적입니다.