[OS] 페이지 교체 알고리즘 (Page Replacement Algorithm)

네트워크

[OS] 페이지 교체 알고리즘 (Page Replacement Algorithm)

위시리 2025. 3. 20. 13:33

페이징 교체 알고리즘의 목표 : 페이지 부재율을 최소화하여 성능을 높이는 것

페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 메모리에 적재되지 않았을 경우(Page Fault),
어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법

메모리가 꽉 차있으면 기존 페이지 중 하나를 물리 메모리에서 디스크의 스왑 영역으로 내보내야 하는데, 이때 기존 페이지들 중에서 어떤 것을 내려서 교체할 지 결정
대상 페이지(victim page) : 교체될 페이지

페이지 교체 방식: Global vs. Local 교체

운영체제(OS)는 메모리를 효율적으로 관리하기 위해 페이지 교체 알고리즘을 사용해 victim page(교체될 페이지)를 선정한다.

1. Global 교체 방식
메모리에 올라온 모든 프로세스의 페이지 중에서 교체할 페이지를 선택하는 방식
즉, 어떤 프로세스든 관계 없이 교체 대상이 될 수 있다.

2. Local 교체 방식
각 프로세스가 할당받은 페이지 내에서만 교체를 수행하는 방식
즉, 자신의 페이지 중에서만 victim page를 선정한다.

이 중, 프로세스마다 메모리 사용량이 다르고 운영체제는 여러 개의 프로세스를 동시에 실행해야 하므로 Local 교체 방식에서는 각 프로세스가 메모리를 독립적으로 관리해야 하므로 불필요한 교체가 많이 발생할 수 있다.
따라서 다중 프로그래밍 환경에서 필요에 따라 할당을 조정할 수 있는 Global 교체 방식이 더 효율적이다.

페이지 교체 알고리즘 종류

간단한 알고리즘
- Random : 무작위로 대상 페이지를 선정하여 페이지 교체
- FIFO : 먼저 들어와서 가장 오래 있었던 페이지 교체
이론적 알고리즘
- OPT : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
최적 근접 알고리즘
- LRU (Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지 교체
- LFU : 참조 횟수가 가장 적은 페이지 교체
- NUR : 최근에 사용하지 않은 페이지 교체
- FIFO 변형 : SCR과 clock 알고리즘

OPT (Optional Replacement, 최적 교체)

개념
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
- 가장 이상적이고 효율적이지만, 실제로 페이지의 참조 상황을 예측할 수 있는 일이 적기 때문에 실현 가능성이 희박하다.
- 실현이 거의 불가능하기 때문에 실제로 사용하기 보다는 연구 목적을 위해 사용된다.
특징
- 모든 페이지 교체 알고리즘 통틀어서 page fault 발생이 가장 적다.
- Belady's Anomaly 현상이 발생하지 않는다.
최적 페이지 교체 알고리즘에 근접하는 방법이 개발됨 → 최적 근접 알고리즘
- 최적 페이지 교체 알고리즘은 미래의 데이터를 참고하기 때문에 구현이 불가능하지만, 최적 근접 알고리즘은 과거의 데이터를 기반으로 미래를 예측하기 때문에 최적 페이지 교체 알고리즘과 유사한 성능을 보인다.
- LRU(최근 최소 사용 알고리즘), LFU(최소 빈도 사용 알고리즘), NUR(최근 미사용 알고리즘)

FIFO (First In Last Out)

개념
- 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 방법
- 가장 구현이 간단한 방법이지만 성능은 좋지 않다.
구현 방법
- 큐 : 메모리의 맨 위에 있는 페이지가 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래 삽입
- 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 보내진다.
단점
- 무조건 오래된 페이지를 대상으로 선정하기 때문에 성능이 떨어지는 문제가 있다.
  - 이를 개선한 것이 → 2차 기회 페이지 교체 알고리즘(SCR)
- Belady's Anomaly 현상 발생
  - Belady의 이상현상 (Belady's Anomaly) : 프레임 개수가 많아져도 page fault가 줄어들지 않고, 늘어나는 현상
  - 직관적으로는 프레임의 개수가 많아지면 page fault가 줄어들어야 하지만 FIFO 알고리즘을 사용하면 그렇지 않을 수도 있다.
  - ex) 페이지 프레임의 개수에 따른 page fault 횟수 비교
  - → 페이지 프레임 개수가 4개일 때 더 많은 page fault가 발생하는 것을 볼 수 있다.

페이지 프레임이 3개일 때 (9)

페이지 프레임이 4개일 때 (10)

LRU (Least Recently Used)

개념
- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 방법
- 가장 많은 운영체제가 채택하는 알고리즘으로, 간단하면서 효율적인 알고리즘
구현 방법 종류
1. 카운터로 구현
  - 카운터로 각 페이지마다 사용된 시간 저장
  - 가장 오랫동안 참조되지 않은 데이터 제거
    - 카운터 : 각 페이지 별로 존재하는 논리적인 시계, 카운터가 가장 작은 것이 가장 오래 전에 참조되었음을 의미
  - 가장 작은 카운터를 찾기 위한 시간과 페이지 테이블이 변경될 때마다 시간 값을 관리해야 하기 때문에 오버헤드 발생
2. 스택으로 구현
  - 참조된 순서만 기억하며 페이지 번호가 기록됨
  - 페이지가 참조되면 해당 페이지 번호를 삭제하고 다시 삽입하여 스택의 가장 위로 올린다.
    - 스택의 top : 항상 최근에 사용된 페이지들
    - 스택의 bottom : 가장 오랫동안 참조되지 않은 페이지들
  - 대상 페이지를 bottom에서 바로 찾을 수 있어 찾는 시간이 필요없고, 대신 참조할 때마다 스택의 위치 이동이 일어나기 때문에 오버헤드 발생
특징
- 시간 지역성 성질을 고려한 방법
- 페이지가 언제 사용되었는지에 대한 시간 정보가 필요
- FIFO 알고리즘보다 성능이 우수하지만, OPT 알고리즘보다 성능이 떨어진다.
- Belady's Anomaly 현상이 발생하지 않는다.
- LFU, NUR 보다 비교적 구현이 쉽고 오버헤드가 적다.
단점
- 프로세스가 주기억장치에 접근할 때마다 참조되어 페이지 시간을 기록해야하기 때문에 막대한 오버헤드가 발생한다.
- 카운터나 스택, 큐와 같은 별도의 하드웨어 지원이 반드시 필요하다.

LRU에 근사한 알고리즘 (LRU approximation algorithm)

LRU 구현에는 하드웨어의 지원이 있어야 하지만, 지원이 어려운 경우가 존재한다.
따라서 하드웨어 대신 참조 비트(Reference Bit)를 사용하여 LRU와 유사한 여러 알고리즘이 사용된다.

1. Reference bit Algorithm (참조 비트 알고리즘)

참조 비트 : 0으로 초기화 되고, 페이지가 참조되면 1로 바꾸어 저장되는 비트로, 주기적으로 초기화 된다.
참조 비트는 어떤 페이지가 특정 시점까지 사용되었는지, 사용되지 않았는지 알 수 있다.
하지만 페이지의 사용 순서까지는 모른다.

2. Additional-Reference Bits Algorithm (부가적 참조 비트 알고리즘)

참조 비트 시프트 (reference bit shift) 으로, 각 페이지 별로 8bit의 참조 비트를 만들어 사용한다.
일정 시간 간격으로 기록함으로써 페이지 참조 순서에 대한 추가적인 정보를 얻을 수 있다. (누가 먼저 사용되었는지 판별할 수 있다.)
- 일정한 시간 간격으로 모든 페이지의 참조 비트를 오른쪽으로 shift 연산을 수행하고, 도중에 참조를 하면 1로 set
- 8 bit의 참조 비트 기록을 정수로 변환했을 때, 가장 낮은 정수 값을 가지는 페이지가 가장 오랫동안 참조되지 않은 페이지가 된다.
참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 공간이 많아진다.

3. Second-Chance Algorithm (2차 기회 알고리즘)

FIFO 기반으로, 한 번 더 기회를 주는 알고리즘
페이지가 선택될 때마다 참조 비트를 확인하여 참조 비트가 0이면 바로 교체하고, 1이면 한 번 더 기회를 주고 다음 페이지를 선택하는 알고리즘

LFU (Least Frequently Used)

개념
- 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘
- 만약 대상 페이지가 여러 개인 경우, LRU 알고리즘에 따라 페이지를 교체 (빈도 → 시간)
- 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지 선정
특징
- LRU는 직전 참조된 시점만 반영하지만(가장 최근에 참조된 시간만 기록), LFU는 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다.
- LRU와 성능이 비슷하며, FIFO보다 성능이 우수하다.
종류
- Incache-LFU : 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
  페이지가 교체되면 해당 페이지의 과거 참조 횟수는 사라짐 → 다시 적재되면 새로운 페이지처럼 0부터 시작
- Perfect-LFU : 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트하는 방식
  페이지가 메모리에서 제거 되었다가 다시 적재되더라고, 이전 참조 횟수가 유지
단점
- 페이지 접근 빈도를 표시하기 위한 추가 공간이 필요하여, 낭비되는 메모리 공간이 많다.
- 앞으로 사용하지 않아도 초기에 사용된 참조 횟수가 높아서 메모리에 계속 남아있기 때문에
  초기에 한 페이지를 집중적으로 참조하다가 이후에 다시 참조하지 않는 경우에 문제가 될 수 있다.

NUR = NRU (Not Used Recently, Not Recently Used)

개념
- 최근에 사용하지 않은 페이지를 교체하는 방법
- LRU와 LFU의 불필요한 공간 낭비 문제를 해결한 알고리즘
구현 방법
- 최근 사용 여부를 확인하기 위해 각 페이지마다 두 개의 비트(참조 비트, 변형 비트)를 사용하여 미래를 추청한다.
  - 참조 비트(R) : 초기값이 0이며, 페이지에 접근(read / execute)하면 1이 된다.
  - 변형 비트(M) : 초기값이 0이며, 페이지가 변경(write / append)하면 1이 된다.
- 각 페이지 상태
  - Class 0 - (0,0) : 모든 페이지의 초기 상태
  - Class 1 - (0,1) : 페이지에 쓰기 또는 추가와 같은 변경이 일어난 경우
  - Class 2 - (1,0) : 페이지에 읽기 또는 실행과 같은 접근이 발생한 경우
  - Class 3 - (1,1) : 접근과 변경 두 가지 연산이 모두 발생한 경우
- NUR에서는 대상 페이지를 선정할 때 페이지를 위와 같이 4가지 클래스로 나누고, 가장 낮은 클래스의 랜덤한 페이지를 선택한디.
- 참조 비트를 먼저 고려하여 클래스의 우선순위 결정
- 모든 페이지의 비트가 (1,1)일 경우, 어떤 페이지가 더 자주 사용되는지 알 수 없어 교체 알고리즘을 정상적으로 사용할 수 없다.
- 따라서 NRU에서 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (0,0)으로 초기화 한다. (reset)
특징
- LRU와 LFU와 성능이 비슷하며, FIFO보다 성능이 우수하다.
- NUR은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 수 있다.
- 쉽게 구현 가능
단점
- 각 페이지의 참조를 유지 및 업데이트하고 비트를 수정하기 위해서는 추가적인 하드웨어 지원이나 소프트웨어 오버헤드가 필요하다.
- 이 때문에 실제로 LRU 알고리즘을 더 많이 사용한다.

FIFO 변형 알고리즘 (SCR, clock)
- FIFO 알고리즘을 기본으로 하되, 페이지에 접근할 때마다 순서의 변화를 주어 성능을 향상한 알고리즘
- SCR Algorithm과 clock Algorithm

SCR (Second Chance Replacement, 2차 기회 페이지 교체)

개념
- FIFO 기법의 단점을 보완하는 기법으로, 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하는 방법
- 한 페이지에 접근했을 때 page fault 없이 성공하면 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외시킨다.
- 성공할 기회를 한 번 더 주는 알고리즘
구현 방법
- FIFO 알고리즘과 reference bit(LRU 근사 알고리즘)를 함께 사용
  - 페이지 교체 수행 중 비트가 0일 경우 교체하고, 참조 비트가 1일 경우에는 참조 비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백시켜 다음 순서를 기다리게 한다.
- FIFO 순서대로 page를 검색
  1. 새로운 페이지가 접근되었을 때
    - 큐에 이미 존재하면?
      → 참조 비트(R)를 1로 설정하고, 해당 페이지를 큐의 맨 뒤로 이동
    - 큐에 없다면?
      → 페이지를 추가하는데, 교체가 필요하면 victim 페이지를 선택
  2. 페이지 교체가 필요할 때
    - 큐의 맨 앞 페이지부터 확인
    - R = 1이면?
      → R을 0으로 바꾸고, 맨 뒤로 이동 (한 번 더 기회 부여)
    - R = 0이면?
      → 해당 페이지를 교체
특징
- 큐의 맨 뒤로 옮기면 대상 페이지로 선정될 확률이 줄어드는 특징을 이용
- LRU, LFU, NUR 보다 성능이 약간 낮고, FIFO 보다 성능이 약간 높다.
단점
- 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다.

clock 알고리즘

개념
- SCR을 원형 큐를 이용하여 구현한 알고리즘
- 한 바퀴 도는 동안 사용되지 않은 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘
구현
- 각 페이지에 참조 비트를 사용해서 교체 대상을 선정한다.
  초기값은 0, 페이지를 성공적으로 참조하면 0 → 1
- 대상 페이지를 가리키는 포인터를 사용하는데, 포인터가 큐의 맨 아래로 내려가면 시계처럼 다시 큐의 처음을 가리키게 된다.
  1. 참조 비트가 0인 것을 찾을 때까지 포인터를 이동
  2. 참조 비트가 1인 경우, 0으로 바꾼 후 건너뜀
  3. 참조 비트가 0인 경우 페이지를 교체
특징
- LRU 근사 방식 알고리즘
- LRU 처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만, 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 않는다.
  - LRU : 가장 오랫동안 사용되지 않은 페이지를 찾는데 효과적
  - clock : 최근에 참조된 페이지를 보존하는데 효과적
- 참조 비트가 1인 페이지를 대상 페이지에 제외함으로써 SCR 처럼 기회를 한 번 더 제공
- but 대상에서 제외되는 경우는 단 한 번 뿐이고, 참조 비트가 1이면 다시 0으로 바꾸기 때문에 한 바퀴를 돌아 포인터가 오면 제외하지 않는다.
- NUR에 비해 각 페이지 당 참조 비트 하나만 추가하면 되기 때문에 추가 공간이 적게 든다.
단점
- 알고리즘이 복잡하고 계산량이 많다.