Pagereplacalgo

title: 2025-09-16 (날짜) author: 강병호 (이름) date: 2025-09-16 (날짜) category: TIL/강병호/2025/09 (파일 경로 : TIL/{이름}/{연}/{월}) layout: post (자유) —

페이지 교체 알고리즘에 대해 설명해 주세요.

페이지 교체란 메모리 과할당 상태에서 페이지 폴트가 발생한 경우, 운영체제가 시스템의 성능 저하 없이 계속 운영되도록 하기 위한 방법으로 메모리에 있는 프레임 중 하나를 변경

표준 스와핑이 존재하나 이것은 오버헤드가 크다.

페이지 교체 방법

1. 보조저장장치에서 필요한 페이지의 위치 파악
2. 빈 페이지 프레임 찾기
   1. 비어 있는 프레임이 있다면 사용
   2. 비어 있지 않다면 희생될 프레임(f) 선정
   3. 희생될 페이지를 보조 저장장치에 기록 후 관련 테이블 수정
3. 새 페이지 가져온 후 테이블 수정
4. 페이지 폴트가 발생한 시점부터 프로세스 계속 진행

2-a의 경우에서 디스크를 두 번 접근하게 되는데 이는 오버헤드가 발생한다. 이를 변경 비트를 사용해서 감소시킬 수 있다. 페이지가 변경되었음을 나타내기 위해 설정되므로 희생시킬 페이지가 선정되는 경우에 변경 비트를 확인하여 변경되지 않은 경우 보조장치에 기록하는 과정이 필요하지 않다.

이러한 페이지 교체 과정에서 2-b의 변경할 프레임, 페이지를 선정할 필요가 존재한다.

이를 결정하는 규칙이 페이지 교체 알고리즘이며 다음 종류가 존재한다.

• FIFO Algorithm : 메모리에 올라온 지 가장 오래된 페이지를  교체
• Optimal Algorithm : 오랫동안 사용되지 않을 페이지를 교체
• Least Recently Used Algorithm : 가장 오랜 기간 동안 사용되지 않은 페이지를 제거
• LRU Approximation Algorithm : LRU의 하드웨어가 필요하다는 단점을 보완한 알고리즘