페이지 교체 알고리즘

 

운영체제가 페이지 부재가 발생했을 때 메모리에 새 페이지를 적제하기 위해
기존 페이지 중 하나를 선택하여 교체하는 방법

 

 

▶ 페이지

가상 메모리 시스템에서 프로그램의 주소 공간은 일정 크기의 블록으로 나눠지는데, 이 블록을 페이지라고 함

→ 컴퓨터 운영체제의 가상 메모리 관리에서 사용하는 메모리 관리 단위

→ 가상 메모리와 실제 물리적 메모리 간의 매핑을 관리하는 기본 단위

→ 일반적으로 4KB, 8KB 등의 크기를 가짐

운영체제는 프로그램을 실행할 때 필요한 메모리를 페이지 단위로 나눠서 관리함

이 과정을 통해 메모리 효율성을 높이고, 프로그램이 필요한 만큼의 메모리만 실제로 할당받아 사용할 수 있게 됨

 

▶ 페이지 테이블

각 프로세스는 페이지 테이블을 가지고 있으며, 이 테이블은 가상 주소와 물리적 주소 간의 매핑 정보를 포함함

페이지 테이블의 항목은 각 페이지가 메모리의 어디에 있는지, 디스크의 스왑 영역에 있는지를 나타냄

 

▶ 페이지 부재

프로그램이 참조하려는 페이지가 현재 물리적 메모리에 없을 때 발생

페이지 부재가 발생하면 운영체제는 디스크에서 해당 페이지를 메모리로 로드해야 함

이 과정에서 페이지 교체 알고리즘이 사용됨

 

▶ 페이지 교체

물리적 메모리가 가득 찼을 때 새로운 페이지를 메모리에 로드하기 위해 기존 페이지 중 하나를 교체하는 과정

페이지 교체 알고리즘은 어떤 페이지를 교체할지 결정하는 과정

 

 

 

FIFO (First-In, First-Out)

• 개념: 가장 먼저 메모리에 적재된 페이지를 가장 먼저 교체
• 장점: 구현 간단
• 단점: 오래된 페이지가 여전히 자주 사용되고 있을 수 있어 비효율적

페이지 참조 순서: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 수: 3

FIFO 교체 과정:
1 2 3 | 첫 3개의 페이지는 단순히 적재
4 2 3 | 1이 가장 오래되었으므로 4로 교체
4 2 5 | 2가 가장 오래되었으므로 5로 교체
1 2 5 | 3이 가장 오래되었으므로 1로 교체

 

 

 

LRU (Least Recently Used)

• 개념: 가장 오랫동안 사용되지 않은 페이지 교체
• 장점: 자주 사용되는 페이지가 메모리에 남아 있을 가능성 높음
• 단점: 구현 복잡, 시간 및 공간 오버헤드 큼

페이지 참조 순서: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 수: 3

LRU 교체 과정:
1 2 3 | 첫 3개의 페이지는 단순히 적재
4 2 3 | 1이 가장 오랫동안 사용되지 않았으므로 4로 교체
4 2 5 | 3이 가장 오랫동안 사용되지 않았으므로 5로 교체
1 2 5 | 4가 가장 오랫동안 사용되지 않았으므로 1로 교체

 

 

 

LFU (Least Frequently Used)

• 개념: 참조 횟수가 가장 적은 페이지를 교체
• 장점: 자주 사용되지 않는 페이지를 제거해서 메모리 효율성 높임
• 단점: 최근 참조된 페이지라도 이전에 참조 횟수가 적으면 교체될 수 있음

페이지 참조 순서: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 수: 3

LFU 교체 과정:
1 2 3 | 첫 3개의 페이지는 단순히 적재
4 2 3 | 1의 참조 횟수가 가장 적으므로 4로 교체
4 2 5 | 3의 참조 횟수가 가장 적으므로 5로 교체
4 1 5 | 2의 참조 횟수가 가장 적으므로 1로 교체

 

 

 

Optimal (OPT)

• 개념: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
• 장점: 가장 적은 페이지 부재를 발생시킴
• 단점: 실제 구현이 불가능, 이상적인 경우에만 사용

페이지 참조 순서: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 수: 3

Optimal 교체 과정:
1 2 3 | 첫 3개의 페이지는 단순히 적재
4 2 3 | 1이 앞으로 가장 오랫동안 사용되지 않으므로 4로 교체
4 2 5 | 3이 앞으로 가장 오랫동안 사용되지 않으므로 5로 교체
4 1 5 | 2가 앞으로 가장 오랫동안 사용되지 않으므로 1로 교체

 

 

 

Second Chance (Clock)

• 개념:
  FIFO 알고리즘을 변형하여 각 페이지에 사용 비트를 추가
  → 페이지가 교체되기 전에 사용 비트를 확인함
  → 비트가 1이면 0으로 설정하고 다음 페이지로 넘어감
• 장점: FIFO의 단점을 보완
• 단점: LRU만큼 효율적이지 못함

페이지 참조 순서: 1 2 3 4 1 2 5 1 2 3 4 5
프레임 수: 3

Second Chance 교체 과정:
1 2 3 | 첫 3개의 페이지는 단순히 적재
4 2 3 | 1의 비트를 확인하고 0으로 설정, 4로 교체
4 2 5 | 2의 비트를 확인하고 0으로 설정, 5로 교체
4 1 5 | 3의 비트를 확인하고 0으로 설정, 1로 교체

 

 

---

 

예시

페이지 참조 순서 : 1 2 3 1 2 4 1 2 5 7

 

 

LRU:

• 페이지 프레임 변동: [1], [1, 2], [1, 2, 3], [2, 3, 1], [3, 1, 2], [1, 2, 4], [2, 4, 1], [4, 1, 2], [1, 2, 5], [2, 5, 7]

LFU:

• 페이지 프레임 변동: [1], [1, 2], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 5], [2, 5, 7]