[Computer Science][Operating System] 📚 페이지 교체 알고리즘 이해하기

페이지 부재 발생 시 새로운 페이지를 할당해야 하는 상황에서, 현재 할당된 페이지 중 어떤 것을 교체할지 결정하는 방법을 다룬 글입니다.

🧩 가상 메모리와 요구 페이지 기법

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둡니다. 하지만 필요한 페이지만 올려도 결국 메모리는 가득 차게 되고, 올라와 있던 페이지가 사용이 다 된 후에도 자리를 차지할 수 있습니다.

따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해 사용하지 않는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 합니다. 이때 어떤 페이지를 out 시켜야 할지 결정해야 하며, 이를 victim page라고 부릅니다.

페이지 교체 시, 가능하면 수정되지 않은 페이지를 선택하는 것이 좋습니다. 그 이유는 수정된 페이지를 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 해야 하므로 시간이 오래 걸리기 때문입니다. 즉, 메모리에서 수정된 정보가 하드디스크에 없기 때문에, 유지하기 위해 하드디스크에서 수정을 진행해야 합니다.

이러한 상황에서 적절한 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재합니다.

📊 Page Reference String

CPU는 논리 주소를 통해 특정 주소를 요구합니다. 가상 메모리 시스템에서 메모리에 올라와 있는 주소들은 페이지 단위로 관리됩니다. 만약 CPU가 참조하는 주소들이 이미 메모리에 로드된 연속된 페이지들에 속해 있다면, 추가적인 페이지 결함이 발생하지 않습니다. 따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로 Page Reference String입니다. 즉, 특정 시점에서 요구한 페이지들의 순서를 나타냅니다.

1. FIFO 알고리즘 🥇

First-In First-Out 알고리즘은 메모리에 먼저 올라온 페이지를 먼저 내보내는 방식입니다. victim page는 가장 먼저 메모리에 올라온 페이지입니다. 이 알고리즘은 가장 간단한 방법으로, 특히 초기화 코드에서 적절하게 사용할 수 있습니다.

초기화 코드는 프로세스 실행 시 최초 초기화를 시키는 역할만 수행하므로, 메인 메모리에서 빼도 괜찮습니다. 하지만 초기화 코드가 반드시 필요한 코드이므로, FIFO 알고리즘을 사용하여 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능합니다.

2. OPT 알고리즘 🌟

Optimal Page Replacement 알고리즘은 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보내는 방식입니다. 이 알고리즘은 FIFO에 비해 페이지 결함의 횟수를 더 많이 감소시킬 수 있지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어렵습니다.

3. LRU 알고리즘 ⏳

Least-Recently-Used 알고리즘은 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 방식입니다. 최근에 사용하지 않았던 페이지는 나중에도 사용되지 않을 것이라는 아이디어에서 출발합니다. LRU는 OPT의 경우 미래 예측에 기반하지만, 과거를 보고 판단하므로 실질적으로 사용 가능한 알고리즘입니다.

실제로 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높기 때문에, 페이지 교체 알고리즘 중에서 가장 좋은 방법 중 하나로 평가받습니다.

⚖️ 교체 방식

Global 교체

• 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식입니다.

Local 교체

• 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식입니다.

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있습니다. 이때 다양한 프로세스의 페이지가 메모리에 존재하게 됩니다. 페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐 Local로 하느냐에 대한 차이가 있습니다.

실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적입니다. 그 이유는 더 많은 선택지가 생기고, 그 중에서 최선의 선택으로 교체할 수 있기 때문입니다. 반면, Local 교체에서는 각 프로세스가 자신에게 할당된 페이지들만 교체해야 하므로, 모든 프로세스가 개별적으로 페이지 교체를 수행해야 한다는 점에서 비효율적일 수 있습니다.

---

이 글에서는 페이지 교체 알고리즘에 대한 다양한 개념과 각 알고리즘의 특징을 설명했습니다. 페이지 교체 알고리즘을 이해하고 활용하는 데 도움이 되길 바랍니다! 😊

이런 자료를 참고했어요.
[1] velog - [운영체제]페이지 교체 알고리즘 (https://velog.io/@k4minseung/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)
[2] TISTORY - [운영체제] 페이지 교체 알고리즘 - 💻평범한 공대생의 개발 노트💻 (https://rob-coding.tistory.com/37)
[3] GitHub - 페이지 교체 알고리즘 (https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Operating%20System/PageReplacement.md)
[4] KOCW - 운영체제 13주차 (http://vod3.kocw.net/KOCW/document/2016/cup/byunsangseon/12.pdf)