[OS] 페이지 교체 알고리즘 (FIFO, LRU, LFU, NRU, NUR)

 

페이지 교체 알고리즘 (FIFO, LRU, LFU, NRU, NUR)

---

안녕하세요? 장장스입니다.

 

가상 메모리 기법을 구현하는 방식 중 하나인 요구 페이징 방식은 페이지 부재가 발생하게 됩니다. 페이지를 교체하는 작업은 오버헤드를 동반하므로 가능하면 페이지 교체가 적게 일어나도록 하는 것이 좋습니다. 페이지 교체가 무엇인지,

 

 

페이지 교체

---

페이지 부재(page fault)가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 합니다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있습니다. 이 경우 물리적 메모리에 올라와 있는 페이지 중 하나를 선택해서 디스크의 스왑 영역으로 보내야 합니다. 이와 같은 과정을 페이지 교체라고 합니다.

 

 

 

 

페이지 교체 알고리즘

---

어떠한 프레임에 있는 페이지를 디스크의 스왑 영역으로 보낼 것인지를 결정하는 알고리즘을 교체 알고리즘이라고 합니다. 이 알고리즘의 목표는 페이지 부재율을 최소화 하는 것입니다. 그러므로 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내보내는 것이 성능을 향상 시킬 수 있는 방안이 될 것입니다.

 

 

선입선출 알고리즘(FIrst In First Out: FIFO)

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내보내는 알고리즘입니다. 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있습니다.

 

아래 그림은 3개의 페이지 프레임을 가질 경우 9번의 페이지 부재와 3번의 페이지 히트가 발생했습니다.

 

이번엔 페이지 프레임을 4개로 증가 시켰을 때의 과정입니다.

10번의 페이지 부재와 2번의 페이지 히트가 발생했습니다.

분명 페이지 프레임을 더 많이 사용하는데 오히려 페이지 부재 횟수가 증가하는 이상현상이 나타났습니다.

 

선입선출 알고리즘에서 메모리를 증가해도 페이지 부재가 더 증가하는 FIFO의 이상 현상(FIFO abnomaly)이 발생할 수 있습니다.

---

 

 

LRU 알고리즘 (Least Recently Used Algorithm)

페이지 교체 알고리즘의 성능 향상을 위해선 앞으로 사용 가능성이 낮은 페이지를 우선적으로 내보내는 것이 좋다. 이와 관련해서 시간 지역성이라는 성질이 있다. 시간 지역성은 최근에 참조된 페이지가 미래에 다시 참조될 가능성이 높은 성질을 말한다. LRU 알고리즘은 이와 같은 성질을 활용해서 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내보낸다.

 

LRU 알고리즘을 사용하니 8번의 페이지 부재와 4번의 페이지 히트가 발생했습니다. FIFO 알고리즘에 비해 페이지 부재 횟수가 감소 했음을 알 수 있습니다.

---

 

 

LFU 알고리즘 (Least Frequently Used Algorithm)

물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적은 페이지를 교체 시킬 페이지로 결정하는 알고리즘입니다. LFU 알고리즘은 크게 2가지로 나뉘어집니다.

 

• Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
• Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식

(Perfect-LFU의 경우 정확하게 참조 횟수를 참조할 수 있지만 시간에 따른 참조의 변화를 반영하지 못하고, 구현이 복잡하다는 단점이 있습니다.)

 

 

11번째로 5번을 참조 하려고 하면 페이지 폴트가 발생합니다. 이 때 LRU 알고리즘은 1번 페이지 프레임을 교체하게 됩니다. 이에 반해 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지 프레임을 교체하게 됩니다.

 

1번 페이지가 오랫동안 쓰이지 않았지만 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지를 교체 했습니다. 그러나 앞으로 4번 페이지가 계속 사용되는 페이지 일 수도 있습니다. 이처럼, LFU는 최신 흐름을 잘 반영하지 못할 수도 있습니다.

 

 

---

클럭 알고리즘 (NRU or NUR)

클럭 알고리즘은 하드웨어적인 자원을 통해 기존(LRU, LFU)알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식입니다. NRU(Not Used Recently) 또는 NUR(Not Recently Used) 알고리즘이라고도 부르기도 합니다.

 

클럭 알고리즘은 LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.

 

클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작합니다. 

1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅됩니다.

2. 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나갑니다.

3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체합니다.

 

즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘입니다.

 

클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘이라 부르기도 한다.

 

 

Post

---

• 2021.12.06 - [OS] - [OS] 요구 페이징(가상메모리)

References

---

• KOCW 운영체제 강의 - 반효경 교수

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)