요구 페이징
요구 페이징 개요
- 요구 페이징: 프로세스가 요구할 때 해당 페이지를 메모리로 가져오는 방식.
- 미리 가져오기: 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식.
- 요구 페이지 장점
- 메모리를 효율적으로 관리할 수 있다.
- 모든 페이지를 메모리로 가져올 필요가 없기 때문에 응답 속도가 빠르다.
페이지 테이블 엔트리의 구조
PTE에는 페이지 번호(주소 영역), 프레임 번호 뿐만 아니라, 플래그 비트가 존재한다.
플래그 비트에는 아래와 같은 비트들이 있다.
- 접근 비트(access bit): 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트. 해당 메모리에 읽거나 실행 작업을 했다면 접근 비트가 1이 된다.
- 변경 비트(modified bit): 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 알려주는 비트. 변경된 적이 있으면 비트가 1이된다. 더티 비트라고도 한다.
- 유효 비트(valid bit): 페이지가 실제 메모리에 있는지 나타내는 비트. 프레젠트 비트(present bit)라고도 한다.
- 읽기, 쓰기, 실행 비트: 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트다. 세그먼테이션-페이징 혼용 기법에서는 해당 비트는 세그먼테이션 테이블에 있다.
페이지 부재
PTE의 유효 비트가 0인 경우 페이지가 물리 메모리에 존재하는 것으로 주소 필드는 프레임 번호를 나타낸다.
PTE의 유효 비트가 1인 경우 페이지가 스왑 영역에 존재하는 것으로 주소 필드는 저장장치 내 주소를 나타낸다.
페이지 부재(page fault): 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황.
페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리메모리로 옮긴다.(스왑인)
페이지 부재가 발생했는데 메모리에 빈 프레임이 없으면 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보낸 후(스왑 아웃), 스왑인을 진행한다.
지역성
- 페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때는 지역성(locality)을 바탕으로 한다.
- 지역성: 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질.
- 공간의 지역성(spatial locality): 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다.
- 시간의 지역성(temporal locality): 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다.
- 순차적 지역성(sequential locality): 여러 작업이 순서대로 진행되는 경향이 있다. 공간의 지역성의 특수한 케이스다.
- 케시 메모리의 동작과 페이지 교체 알고리즘은 지역성을 고려한다.
페이지 교체 알고리즘
페이지 교체 알고리즘의 개요
페이지 교체 알고리즘: 스왑 영역으로 보낼 페이지를 결정하는 알고리즘.
페이지 교체 알고리즘의 종류
| 종류 | 알고리즘 | 특징 |
| — | — | — |
| 간단한 알고리즘 | 무작위 | 무작위로 대상 페이지를 선정. |
| | FIFO | 처음 메모리에 올라온 페이지를 선정. |
| 이론적 알고리즘 | 최적 | 미래의 접근 패턴을 보고 대상 페이지를 선정. |
| 최적 근접 알고리즘 | LRU | 시간적으로 멀리 떨어진 페이지를 선정. |
| | LFU | 사용 빈도가 적은 페이지를 선정. |
| | NUR | 최근에 사용한 적이 없는 페이지를 선정. |
| | FIFO 변형 | FIFO 알고리즘을 변형. |
페이지 교체 알고리즘의 성능 평가 기준
- 페이지 부재 횟수, 페이지를 요청한 후 실제로 작업에 들어갈 때까지의 평균 대기 시간, 전체 작업에 걸리는 시간 등
- 이 책에서는 페이지 부재 횟수와 페이지 성공 횟수를 비교한다.
무작위 페이지 교체 알고리즘
- 지역성을 전혀 고려하지 않았다.
- 성능이 좋지 않다.
FIFO 페이지 교체 알고리즘
- 시간의 지역성을 고려하여 가장 오래된 페이지를 대상 페이지로 선정했다.
- 오래되었더라도 자주 사용하는 페이지는 스왑 아웃되면 안된다.
- 이를 개선한 것이 2차 기회 페이지 교체 알고리즘이다.
최적 페이지 교체 알고리즘
- 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다.
- 미래의 메모리 접근 패턴을보고 대상 페이지를 결정하기 때문에 성능이 좋다.
- 하지만 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다.
- 따라서, 성능이 최적 페이지 교체 알고리즘에 근접하는 방법인 최근 최소 사용 알고리즘 LRU(Least Recently Used), 최소 빈도 사용 알고리즘 LFU(Least Frequently Used), 최근 미사용 알고리즘 NUR(Not used recently) 등을 사용한다.
LRU 페이지 교체 알고리즘
- 최근에 사용한 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정한다.
- LRU 페이지 교체 알고리즘은 구현 방식이 다양하다.
- 페이지 접근 시간에 기반한 구현
- 페이지에 접근한 시간을 기록하여 구현한다.
- 페이지에 접근한 시간이 가장 오래된 페이지를 교체한다.
- 메모리 접근 패턴이 중간에 변경되면 FIFO 페이지 교체 알고리즘만큼 느려지기도하고 최적 페이지 교체 알고리즘만큼 좋아지기도 한다.
- 카운터에 기반한 구현
- 페이지에 카운터 숫자를 기록한다.
- 접근 시간과 마찬가지로 추가 공간이 필요하다는 단점이 있다.
- 참조 비트 시프트 방식
- 각 페이지에 일정 크기의 참조 비트를 만들어 사용한다.
- 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다.
- 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다.
- 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다.
- 접근 횟수를 측정하는 LFU와 다르다.
- 이 또한 메모리가 추가로 필요하다는 단점이 있다.
LFU 페이지 교체 알고리즘
- 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다.
- LRU와 성능이 비슷하다.
- LRU와 마찬가지로 낭비되는 메모리 공간이 많다.
NUR 페이지 교체 알고리즘
- LRU, LFU와 성능이 비슷하면서도 공간 낭비 문제를 해결했다.
- 1000번 접근한 페이지와 20번 접근한 페이지가 있다면 20번 접근한 페이지를 스왑아웃하는것이 맞지만, 95번 접근한 페이지와 91번 접근한 페이지는 어떤 페이지를 쫓아내도 상관없다.
- NUR에서는 참조 비트와 변경 비트를 사용한다.
- 모든 페이지의 초기 상태는 (0, 0)이다.
- 페이지에 읽기 또는 실행같은 접근이 발생하면 (1, 0)으로 바뀐다.
- 페이지에 쓰기 또는 추가 같은 변경이 일어나면 (0, 1)이 된다. 두 가지 다 발생하면 (1, 1)이 된다.
- NUR에서 우선 고려 대상은 참조 비트다. 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾아서 대상 페이지로 지정한다.
- 만약 모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 (0, 0)으로 초기화한다.
FIFO 변형 알고리즘
- 2차 기회 페이지 교체 알고리즘
- 2차 기회 FIFO 페이지 교체 알고리즘이라고도 한다.
- 페이지 부재 없이 성공한 페이지는 큐의 맨 뒤로 옮긴다.
- LRU, LFU, NUR 페이지 교체 알고리즘보다 성능이 약간 낮고 FIFO보다 약간 높다.
- 큐 유지비용이 높고, 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다는 단점이 있다.
- 시계 알고리즘
- 원형 큐를 사용한다.
- 스왑 영역으로 옮긴 대상 페이지를 포인터를 둔다.
- 참조 비트를 하나씩 두고, 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경한다.
- 시계 알고리즘의 대상 포인터는 메모리가 꽉 찰경우 스왑 영역으로 쫓겨날 페이지를 가리킨다.
- 만약 가리키는 페이지가 쫓겨나면 포인터를 밑으로 이동한다.
- 참조 비트가 1인 페이지는 건너뛰고, 그 비트는 0으로 만든다.
- 페이지당 참조 비트를 하나만 추가하면 되기 때문에 NUR 페이지 교체 알고리즘보다 공간이 적게들지만, 알고리즘이 복잡하고 계산량이 많다는 단점이 있다.