페이지 교체 알고리즘
페이지 교체 알고리즘의 개요
- 스왑 영역으로 보낼 페이지를 결정하는 알고리즘
- 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상
페이지 교체 알고리즘의 성능 평가 기준
- 어떤 알고리즘이 다른 알고리즘보다 성능이 좋은지 평가하는 데에는 다양한 비교 방법이 있음
- 같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수와 페이지 성공 횟수를 비교
- 모든 페이지 교체 알고리즘은 그림처럼 메모리 접근순서를 사용하고 물리메모리는 3개의 프레임을 가졌다고 가정
- 상단의 숫자는 메모리 접근순서를 나타내며, 페이지는 번호대신 알파벳을 사용함
무작위 페이지 교체 알고리즘 (random page replacement algorithm)
- 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방법
- 스왑 영역으로 보낼 대상페이지를 특별한 로직없이 무작위로 선정
- 지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 하여 성능이 좋지 않음
FIFO 페이지 교체 알고리즘 (first in, first out page replacement algorithm)
- 시간상으로 메모리에 가장 먼저 올라온 페이지를 대상 페이지로 선정하여 스왑 영역으로 보냄
- 페이지 부재는 Fail, 메모리에 있는 경우 Success로 표시
- 알고리즘은 큐로 구현, 메모리 가장 위쪽에 있는 페이지는 가장 오래된 페이지, 새로운 페이지는 항상 맨 아래 삽입
- 메모리가 Full이면, 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들은 위쪽으로 이동함
- [그림 9-10]의 메모리 접근순서 4번을 보면 가장 오래된 페이지 A가 스왑 영역으로 가고, 페이지 B와 C가 위쪽으로 이동, 새로운 페이지 D가 아래쪽 남은 공간에 삽입됨
- 5번의 경우는 메모리에 있던 페이지 B를 요청했으므로 성공 S임
- 교체되어 새로 삽입된 페이지는 회색, 성공한 페이지는 녹색으로 구분
- 이 그림에서는 10번의 페이지 요구에 대해 3번 성공함
- 시간의 지역성을 고려하면 가장 오래된 페이지를 대상 페이지로 선정하는 것이 맞음
- 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어짐
FIFO 페이지 교체 알고리즘 (예)
FIFO 페이지 교체 알고리즘 (문제점을 보여주는 예)
문제점 : 벨래디의 변이Belady’s anomaly (b)와 같이 프레임이 많으면 페이지 부재 횟수가 줄어드는 것과 반대되는 현상 나타남. 이처럼 할당하는 프레임 수가 증가하면 페이지 부재 비율도 증가하는 현상을 말함
최적 페이지 교체 알고리즘 (optimal page replacement algorithm)
- 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김
- 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정
- 페이지 성공 횟수 : 5
- 이상적인 방법이지만 실제로 구현할 수 없음
최적 근접 알고리즘의 접근방식
- 실제 구현이 가능하면서도 성능이 최적 근접 알고리즘에 근접한 알고리즘
- LRU(least recently used) 페이지 교체 알고리즘: 페이지에 접근한 시간을 기준으로 대상 페이지를 선정
- 현재시간이 11시, 페이지 A, B, C에 마지막으로 접근한 시간이 각각 1시40분, 8시50분, 9시30분이라면 현재와 시간차가 가장 큰 페이지 A가 스왑 영역으로 이동
- LFU(least frequently used) 페이지 교체 알고리즘: 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정
LRU 페이지 교체 알고리즘
- '최근 최소 사용 페이지 교체 알고리즘'이라고도 함
- 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮김
- 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정
- 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있음
LRU 페이지 접근 시간에 기반한 구현
- 페이지에 접근한 지 가장 오래된 페이지를 교체. 즉, 페이지에 읽기, 쓰기, 실행과 같은 연산이 이루어진 시간을 기준으로 교체
- [그림 9-13]에서는 편의상 맨 위의 숫자(메모리 접근 순서)를 초 단위로 가정
- 페이지가 메모리에 올라오거나 사용될 때마다 그 시간을 사각형 아래에 표시
- 예를 들면 3초에 페이지 C가 메모리에 올라왔으므로 C아래의 숫자는 3
- 5초에 페이지 B에 접근했으므로 B아래 2가 5로 변경, 8초에도 페이지 A에 접근 A 아래의 6이 8로 변경됨
- LRU 페이지 교체 알고리즘에서는 숫자가 가장 작은 페이지, 즉 사용된 지 가장 오래된 페이지를 대상페이지로 선정함
- 6초의 경우 페이지 A를 올리기 위해 가장 오랫동안 접근하지 않았던 페이지 C를 스왑 영역으로 옮김
- 9초의 경우 가장 오랫동안 접근하지 않았던 페이지 D를 스왑 영역으로 옮기고 그 자리에 페이지 C를 올림
LRU 카운터에 기반한 구현
- LRU 페이지 교체 알고리즘을 카운터를 사용하여 구현
- [그림9-13]의 맨 위의 숫자를 시간이 아니라 카운터 숫자로 생각함
LRU 참조 비트 시프트 방법
- 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것
- 참조 비트의 초기값은 0이며 페이지에 접근할 때마다 1로 바뀜
- 참조 비트는 주기적으로 오른쪽으로 한 칸 씩 이동
- 참조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정
- 페이지 C가 대상페이지로 선정됨
- 참조 비트방식은 LFU 페이지 교체 알고리즘과 유사함
참조 비트 시프트 방식이 LFU가 아니라 LRU 페이지 교체 알고리즘인 이유
- LFU 페이지 교체 알고리즘은 페이지 접근회수를 측정해 대상 페이지를 선정
- [그림 9-15]를 보면 참조 비트 시프트 방식이 LRU 페이지 교체 방법이라는 것을 이해할 수 있음
- [그림 9-15]에서는 페이지 A에 네 번, 페이지 B에 한 번, 페이지 C에 다섯 번 접근
- 그러나 참조비트 중 가장 큰 값은 가장 최근에 접근한 페이지 B이고, 가장 작은 값은 가장 오랫동안 접근하지 않은 페이지 C
- 따라서 페이지 C가 대상페이지로 선정, 이 방법은 참조한 횟수가 아니라 참조한 시간을 기준으로 대상페이지를 선정함으로 LRU 페이지 교체 알고리즘의 한 방법임
LRU, Least Recently Used 교체 알고리즘
- 스택을 이용한 순서 결정 방법
- 페이지 번호를 스택에 넣어 관리하고 페이지를 참조할 때마다 페이지 번호를 스택의 톱에 두어 순서 결정
- Top에 있는 페이지 번호는 가장 최근에 사용한 페이지가 되고, Bottom에 있는 페이지 번호는 가장 늦게 사용한 페이지가 되어 페이지 부재를 일으킬 때 교체
- 최근 최소 사용 알고리즘의 스택 사용 예
LFU 페이지 교체 알고리즘
- 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정
- 현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김
- [그림9-16] 알파벳 아래 숫자는 사용빈도를 나타냄
- 예) 5번의 B(2) 페이지 B가 메모리에 올라온 후 지금까지 두 번 사용되었다는 표시, 사용빈도가 같은 경우 맨 위의 페이지를 대상페이지로 선정
- LFU 알고리즘은 처음메모리에 올라온 페이지의 사용빈도가 1이고, 페이지가 사용될 때마다 하나씩 증가
NUR(not used recently) 페이지 교체 알고리즘
- LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 추가적인 오버헤드가 큼 (페이지 접근 표시)
- 이를 개선한 NRU는 두 개의 비트만으로 구현 가능
- '최근 미사용 페이지 교체 알고리즘' 이라고도 불림
- 페이지마다 참조 비트와 변경 비트를 가짐
- 참조 비트: 페이지에 접근(read/execute)하면 1이 됨
- 변경 비트: 페이지가 변경(write/append)되면 1이 됨
- 모든 페이지의 초기 상태는 (0,0), 모든 값이 (1,1)이면 초기화 함
- 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾음
- 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정
- 모든 페이지의 비트가 (1,1)일 때는 어떤 페이지를 더 자주 사용했는지 알 수 없어 NUR을 적용 불가함. 따라서 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 초기화함
- [그림9-9]에서 읽기와 쓰기를 구분하지 않았기 때문에, [그림9-18]은 변경비트가 1이 되는 경우는 없음
- 처음메모리에 올라온 모든 페이지의 참조 비트와 변경비트는 (0,0)
- 이후 메모리 접근순서 5번에서 페이지 B에 접근하면 페이지 B는 (1,0) 으로 변함
- 메모리 접근순서 6번에서 페이지 A에 접근, 페이지 B는 대상페이지에서 제외되고, 페이지 C와 D 중 가장 위에 있는 페이지 D가 스왑 영역으로 교체됨
- LRU, LFU, NUR은 성능이 거의 비슷하지만, NUR 페이지 교체 알고리즘 2bit만 추가함
2차 기회 페이지 교체 알고리즘
- FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용하며, 특이점은 특정페이지에 접근해 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상페이지에서 제외함
- 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줌
- 이 알고리즘은 LRU, LFU, NUR은 성능이 약간 낮고, FIFO보다 우수하다고 알려짐
- 큐의 유지비용 및 중간에 있는 값을 이동하는 작업이 추가되는 단점이 있음
시계 알고리즘
- 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용
- 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용
- 포인터가 큐의 맨 바닥으로 내려가면 다음번에는 다시 큐의 처음을 가리키게 됨
- 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부름
- 2차 기회 페이지 교체 알고리즘에 비해 각 페이지 참조 비트가 하나씩 추가
- 참조 비트 값은 0이며, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경
- 대상 포인터는 메모리가 Full이면 스왑 영역으로 내려갈 페이지를 가리킴
- 가리키는 페이지가 스왑 영역으로 내려가면 대상 포인터를 밑으로 이동하는데 이때 참조 비트가 1인 페이지는 0으로 만든 후 건너뜀 (2차기회를 줌)
시계 알고리즘 동작 순서
- ① 1번에서 페이지 A가 메모리에 올라오면 대상 포인터는 페이지 A를 가리킴
- ② 2, 3번에서 페이지 B와 C가 메모리에 올라옴
- ③ 4번에서 대상 포인터가 가리키는 페이지 A가 스왑 영역으로 가고 페이지 D가 메모리에 올라옴. 대상 포인터는 한 칸 아래인 페이지 B로 이동
- ④ 5번에서 페이지 B가 페이지 참조에 성공하면 페이지 B의 참조비트는 1이 되어 기회를 얻음. 대상 포인터는 페이지 B의 참조비트를 0으로 만든 후 페이지 C로 이동
- ⑤ 6번에서 대상 포인터가 가리키는 페이지 C가 스왑 영역으로 가고 페이지 A가 메모리에 올라옴, 대상 포인터는 메모리의 맨 위인 페이지 D로 이동
- ⑥ 7, 8번에서 페이지 B와 A를 성공적으로 참조하여 참조비트를 1로 변경
- ⑦ 9번에서 대상 포인터가 가리키는 페이지 D가 스왑 영역으로 페이지 C가 메모리에 올라옴. 이때 대상 포인터는 밑으로 이동. 페이지 B, A 참조비트 1이므로 0으로 변경 후 스킵함. 대상 포인터는 맨 위 페이지 C를 가리킴
'전공 > 운영체제' 카테고리의 다른 글
| Ch10. 입출력 시스템과 저장장치_01)입출력 시스템(1) (0) | 2023.06.15 |
|---|---|
| Ch09. 가상 메모리 관리_04)스레싱과 프레임 할당 (0) | 2023.06.13 |
| Ch09. 가상 메모리 관리_02)요구페이징 (0) | 2023.06.12 |
| Ch09. 가상 메모리 관리_01)가상 메모리의 이해 (0) | 2023.06.12 |
| [심화]Ch08. 가상 메모리의 기초_05)캐시 매핑 기법 (0) | 2023.06.11 |
댓글