서론
앞서 가상 메모리 포스팅을 하면서 프로세스를 이루는 모든 페이지가 메모리에 적재되지 않아도 된다는 것과, 이처럼 메모리에 필요한 페이지만을 적재하는 기법이 요구 페이징이라고 하는 것을 알아보았다.
요구 페이징을 통해 페이지들을 메모리에 점차 적재하다 보면 언젠가는 메모리가 가득 찰 것이다. 메모리에 페이지가 가득 찬 상태에서 추가적으로 페이지를 적재해야 한다면 메모리에 적재된 일부 페이지를 스왑 아웃해야 한다.
이때 메모리에 적재된 페이지 중 보조기억장치로 내보낼 페이지를 선택하는 방법을 페이지 교체 알고리즘이라고 한다.
페이지 교체 알고리즘은 컴퓨터 전체 성능과 직결된다. 어떤 알고리즘이 사용되느냐에 따라 페이지 폴트의 발생 빈도가 달라질 수 있기 때문이다. 어떤 것이 좋은 페이지 교체 알고리즘일까? 바로 페이지 폴트가 적은 알고리즘이다. (페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능이 저하되기 때문)
대표적인 알고리즘 3개를 알아보도록 하자.
FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)
이름 그대로 메모리에 가장 먼저 적재된 페이지부터 스왑 아웃하는 페이지 교체 알고리즘이다.
페이지가 올라온 시간을 페이지마다 기록해도 되고, 아니면 페이지들이 올라온 순서대로 큐를 만들어 가지고 있어도 된다. 그러면 큐의 머리 부분 페이지를 교체하고 새로 올라온 페이지는 큐의 끝에 삽입하면 된다.
FIFO 페이지 교체 알고리즘은 이해하기도 쉽고, 구현도 쉽다. 그러나 성능이 항상 좋지는 않다.
예를 들어, 스왑 아웃된 페이지가 실제로는 더 이상 사용되지 않을 오래된 초기화 모듈이라면 괜찮지만, 반대로 그 페이지가 자주 참조되는 페이지였던 경우에는, 다음에 다시 해당 페이지가 필요해질 때 스왑 인이 발생하게 되어 불필요한 페이지 폴트(page fault)와 디스크 I/O가 증가한다.
최적 페이지 교체 알고리즘(Optimal Page Replacement Algorithm)
앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다. 메모리에 적재된 페이지들 중 앞으로 가장 적게 사용할 페이지를 스왑 아웃해 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다. 이름 그대로 최적의 알고리즘이라고 할 수 있지만, '앞으로 가장 적게 사용할 페이지'를 미리 예측하기 어렵기 때문에 실제 구현이 어려운 알고리즘이다. 따라서 최적 페이지 교체 알고리즘은 주로 비교 연구 목적을 위해 사용한다.
LRU 페이지 교체 알고리즘(Least Recently Used Replacement Algorithm)
최적 페이지 교체 알고리즘이 가장 적게 '사용할' 페이지를 스왑 아웃하는 알고리즘이라면 LRU 페이지 교체 알고리즘은 가장 적게 '사용한' 페이지를 교체하는 알고리즘이다. 보편적으로 사용되는 페이지 교체 알고리즘의 원형이며, 이를 기반으로 만들어진 다양한 파생 알고리즘이 있다.
LRU 페이지 교체 알고리즘은 페이지마다 마지막 사용 시간을 유지한다. 페이지 교체 시에 LRU는 가장 오랫동안 사용되지 않은 페이지를 선택한다.
틀린 부분이 있다면 댓글로 알려주세요! 감사합니다.😊
[Reference]
'Development > 운영체제' 카테고리의 다른 글
| 가상메모리 (0) | 2025.01.12 |
|---|