9-2.[os] 페이지 교체 알고리즘
재배치 정책:
- 메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 정책
페이지 교체 알고리즘:
- 스왑 영역으로 보낼 페이지를 결정하는 알고리즘
- 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상
페이지 교체 알고리즘의 종류
- 가장 간단한 방식(무작위, FIFO) -> 성능은 좋으나 구현하기 어려운 방식(최적) -> 이상적인 방식과 유사하게 구현한 방식(LRU, LFU, NUR) -> FIFO 변형 알고리즘
페이지 교체 알고리즘의 성능 평가 기준
- 페이지 부재 횟수를 세어본다
- 페이지 요청 후 작업에 들어갈 때까지의 평균 대기 시간을 측정해본다
- 전체 작업에 걸리는 시간을 비교해본다
성능이 뛰어나도 계산이 많이 필요하거나 메모리를 많이 차지함 -> 유지 비용도 고려해야
여기선 페이지 부재 횟수, 페이지 성공 횟수 비교
- 숫자: 접근 순서
- 알파벳: 페이지 번호
무작위 페이지 교체 알고리즘
random page replacement algorithm
가장 간단하게 구현 가능
- 특별한 로직없이 무작위로 쫓아낼 페이지 선정
- 자주 사용하는 페이지가 대상 페이지로 선정되기도 함
- 성능 안 좋아서 잘 사용되지 않음
FIFO 페이지 교체 알고리즘
First In First Out page replacement algorithm
선입선출 페이지 교체 알고리즘
시간상 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다
페이지 부재가 일어난 경우(원하는 페이지가 메모리에 없는 경우) -> F (fail)
- 원하는 페이지가 메모리에 있는 경우 -> S (success)
- 큐로 구현
- 오래된 페이지가 위
- 예시) 총 10, 성공 3, 페이지부재 7
- 시간의 지역성: 가장 오래된 페이지를 대상 페이지로 선정
- 메모리에 올라온 지 오래되었어도 자주 사용되는 페이지가 있음
- 성능 떨어짐
최적 페이지 알고리즘
- optimal page replacement algorithm
- 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다
- 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정
- 예시) 4번: 앞으로 사용할 페이지에 A, B, C가 있는지 살펴봄
- A 6번, B는 5번, C는 9번에서 사용된다
- 가장 늦게 사용되는 페이지 C -> 스왑 영역
- 단점: 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다
- -> 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정 -> 최적 근접 알고리즘
LRU 페이지 교체 알고리즘:
- 예시) 현재 시간: 11시
- 현재와 시간 차가 가장 큰 1시 40분에 접근한 페이지 A -> 스왑 영역
LFU 페이지 교체 알고리즘:
- 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정
- 8번 사용된 페이지 -> 스왑 영역
LRU 페이지 교체 알고리즘
- Least Recently Used page replacement algorithm
- 최근 최소 사용 페이지 교체 알고리즘
- 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다
- 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정
- 시간을 기준으로 구현
- 카운터나 참조 비트로 구현
페이지 접근시간에 기반한 구현
- 페이지에 접근한 지 가장 오래된 페이지를 교체
- 상 맨 위의 숫자를초 단위로 가정
페이지가 메모리에 올라오거나 사용될 때마다 그 시간(초)을 사각형 아래에 표시
일반적으로 LRU 페이지 교체 알고리즘의 성능은 FIFO 페이지 교체 알고리즘보다 우수하고 최적 페이지 교체 알고리즘보다는 조금 떨어지는 것으로 알려져 있다.
카운터에 기반한 구현
맨 위의 숫자를 시간(초)이 아니라카운터 숫자라 고 생각하면 된다
단점: 접근 시간을 기록하든 카운트를 하든 추가적인 메모리 공간을 필요로 함
- 예) 0〜 1024초를 표시하려면 l0bit가 필요하고 더 큰 숫자를 표시하려면 더 많은 비트를 사용해야 한다
참조 비트 시프트 방식
- reference bit shift
- 참조 비트의 초깃값은 0
- 페이지에 접근할 때마다 1
- shift: 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다
- 참조 비트 시프트 방식의 단점: 작지 않은 공간을 사용하므로 공간을 낭비
- LRU 페이지 교체 알고리즘의 단점: 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다
LFU 페이지 교체 알고리즘
- Least Frequently Used Page replacement algorithm
최소 빈도 사용 알고리즘
페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정
- 현재 프레임에 있는 페이지마다 사용 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다
LRU, LFU : 일반적인 경우 두 알고리즘의 성능이 비슷, FIFO 페이지 교체 알고리즘보다 우수
단점: 페이지 접근 횟수(빈도)를 표시하는 데 추가 공간이 필요하므로 메모리가 낭비
NUR 페이지 교체 알고리즘
- Not Used Recently Page replacement algorithm
최근 미사용 페이지 교체 알고리즘
LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결
미래를 추정할 때 95번 접근한 페이지와 91 번 접근한 페이지는 앞으로 접근할 확률이 비슷
- 접근 시간이든 접근 빈도든 정확한 값을 유지하는 것은 공간만 많이 차지할 뿐 의미가 없다
- 참조 비트, 변경 비트 = 2비트 뿐
- 참조 비트: 페이지에 접근 read/execute하면 1이 된다
변경 비트: 페이지가 변경 write/append되면 1이 된다
‘접근’: (1, 0)
- '변경’: (0, 1)
대상 페이지 선정 순서: (0, 0), (0, 1), (1, 0), (1, 1)
장점:
- 2bit만 추가하여 다른 알고리즘과 유사한 성능
- 쉽게 구현할 수 있음
- 가장 많이 사용
LRU, LFU, NUR 페이지 교체 알고리즘의 성능은 거의 비슷하며 FIFO 페이지 교체 알고리즘보다 우수
FIFO 변형 알고리즘
2차 기회 페이지 교체 알고리즘
- second chance page replacement algorithm
- FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용
- 성공한 페이지를 큐의 맨 뒤로 옮김
- 성능: FIFO < 2차 기회 << LRU, LFU, NUR
- 단점:
- 큐 유지하는 비용이 높다
- 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가됨
시계 알고리즘
- clock algorithm
- 원형 큐 사용
- 옮길 대상 페이지를 가리키는 포인터를 사용
- 포인터가 큐의 맨 바닥으로 내려가면 다시 큐의 처음을 가리킴
- 포인터가 시계처럼 한 방향으로 돈다
- 장점: 대상 포인터와 각 페이지당 참조 비트 하나만 추가하면 되기 때문에 NUR 페이지 교체 알고리즘보다 추가 공간이 적게 든다
- 단점: 알고리즘이 복잡하고 계산량이 많다