페이지 교체 알고리즘

운영체제에서 메모리 관리는 매우 중요한 역할을 합니다. 특히, 프로세스가 필요한 데이터를 메모리에 로드할 공간이 부족할 때, 기존의 데이터를 교체해야 하는데, 이때 페이지 교체 알고리즘이 사용됩니다. 이번 글에서는 페이지 교체 알고리즘 개념과 주요 알고리즘을 비교하며 설명하겠습니다.

페이지 교체 알고리즘이란?

운영체제는 한정된 물리적 메모리를 효율적으로 사용하기 위해 가상 메모리 개념을 도입합니다. 프로세스 실행 중 필요한 페이지가 메모리에 없을 경우, 페이지 폴트(Page Fault) 가 발생하고, 새로운 페이지를 불러오기 위해 기존 페이지 중 하나를 제거해야 합니다. 이때, 어떤 페이지를 제거할지를 결정하는 방법이 페이지 교체 알고리즘입니다.

주요 페이지 교체 알고리즘

FIFO(First In First Out)

가장 먼저 들어온 페이지를 가장 먼저 제거하는 방식입니다. 큐(Queue) 자료구조를 이용하여 페이지를 관리합니다.

• 장점: 구현이 간단하며, 큐를 이용한 관리가 용이함.

• 단점: 가장 오래된 페이지가 항상 제거되므로, 자주 사용하는 페이지도 교체될 가능성이 있음.

• 예시:

  • 페이지 프레임: [1, 2, 3] → 4가 들어오면 1이 제거됨.

OPT(Optimal Page Replacement)

앞으로 가장 오랫동안 사용되지 않을 페이지를 제거하는 방식입니다.

• 장점: 가장 적은 페이지 폴트를 발생시킴.

• 단점: 미래의 페이지 참조를 미리 알아야 하므로 현실적으로 구현이 불가능함.

• 예시:

  • 페이지 프레임: [1, 2, 3] → 4가 들어오고, 이후 1이 가장 늦게 사용되므로 1이 제거됨.

LRU(Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 제거하는 방식입니다. 최근에 사용한 페이지일수록 계속 유지됩니다.

• 장점: FIFO보다 효율적이며 자주 사용되는 페이지가 유지될 가능성이 큼.

• 단점: 페이지 참조 시간을 기록해야 하므로 구현이 복잡하고 오버헤드가 발생할 수 있음.

• 예시:

  • 페이지 프레임: [1, 2, 3] → 4가 들어오고, 가장 오랫동안 사용되지 않은 1이 제거됨.

LFU(Least Frequently Used)

가장 적게 사용된 페이지를 제거하는 방식입니다. 페이지 참조 횟수를 기반으로 교체를 결정합니다.

• 장점: 자주 사용하는 페이지를 오래 유지 가능.

• 단점: 초기 참조가 적었던 페이지는 필요하더라도 삭제될 가능성이 있음.

• 예시:

  • 페이지 프레임: [1(3회), 2(2회), 3(1회)] → 4가 들어오고, 3이 가장 적게 사용되었으므로 제거됨.

MFU(Most Frequently Used)

가장 많이 사용된 페이지를 제거하는 방식입니다. LFU와 반대 개념으로, 자주 사용된 페이지는 앞으로 덜 필요할 가능성이 높다고 가정합니다.

• 장점: 초기에 자주 사용된 페이지가 오래 유지되는 LFU의 단점을 보완함.

• 단점: 여전히 현실적인 적용이 어려움.

• 예시:

  • 페이지 프레임: [1(5회), 2(3회), 3(2회)] → 4가 들어오고, 1이 가장 많이 사용되었으므로 제거됨.

페이지 교체 알고리즘 비교

결론

운영체제에서 페이지 교체 알고리즘은 시스템의 성능을 크게 좌우하는 요소입니다. FIFO는 단순하지만 비효율적이고, OPT는 최적이지만 구현이 어렵습니다. LRU와 LFU는 현실적인 대안이지만 추가적인 오버헤드가 발생할 수 있습니다. 각 알고리즘의 특성을 잘 이해하고, 시스템 환경에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

페이지 교체 알고리즘에 대한 여러분의 생각은 어떠신가요? 여러분이 사용해 본 알고리즘이나 더 궁금한 점이 있다면 댓글로 남겨주세요!

프로세스 교착상태(Deadlock)