페이지 교체 알고리즘
요구 페이징
컴퓨터를 오래 사용하면 느려지는 것을 경험할 것이다. 이는 작업을 하지 않고 쉬는 프로세스나 좀비 프로세스가 메모리를 차지하여 메모리 관리가 복잡해지기 때문이다.
용량이 큰 프로세스를 실행하면 운영체제는 프로세스를 구성하는 전부를 메모리에 올리는 것이 아니라, 필요한 모듈만 메모리에 올리고 나머진 필요하면 불러온다. 이는 메모리를 효율적으로 관리하고 응답 속도 향상을 위해서이다. 예를들어 포토샵의 다양한 필터들이 있는데 이를 한 번에 다 가져와서 쓰는 것이 아닌, 필요할때 불러와 쓰는 것이 그 예시이다. 이처럼 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구 페이징이라고 한다.
미리 가져오기는 요구 페이징과 반대로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식이다. 대표적인 예시로 캐시가 있다. 캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다 놓음으로써 시스템의 성능을 향상한다. 그러나 미리가져온게 쓸모없으면 망한다. 따라서 현대 운영체제는 요구 페이징을 기본으로 쓴다.
프로세스 입장에서는 프로세스 구성 모든 페이지가 메모리로 한 번에 올라오는 것이 좋은데 이를 순수한 스와핑(swapping)이라고 한다. 반대로 요구할 때 올라오는 것을 게으른 스와핑이(lazy swapper)라고 한다.
페이지 테이블 엔트리의 구조
가상 메모리의 크기는 물리 메모리와 스왑 영역을 합친 것이다. 스왑 영역은 하드 디스크에 존재하나 메모리 관리자가 관리하는 영역이다. 스왑 영역에 있는 경우는 크게 두 가지이다. 하나는 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우이고, 또 하나는 메모리가 꽉 차서 스왑영역으로 옮겨온 경우이다. 어쨋든 페이지 테이블에는 페이지가 메모리에 있는지, 스왑 영역에 있는지 표시해야 하는데 이때 사용하는 비트가 유효비트이다.
페이지 테이블 엔트리(PTE)는 페이지 테이블의 한 행을 말한다. 정확히 말하면 페이지 번호, 플래그 비트, 프레임 번호로 구성된다. PTE는 직접 매핑에서는 필요 없고 연관 매핑에서 페이지 번호, 프레임 번호 둘 다 필요하다. 페이지 번호는 매핑 방식에 따라 필요하기도하고 필요 없기도 하다. 핵심은 프레임 번호이다. 중간엔 비트가 있다.
- 접근 비트 : access bit는 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트이다. 참조 비트(reference bit)라고도 한다.
- 유효 비트 : 유효 비트(valid bit)는 페이지가 실제 메모리에 있는지를 나타내는 비트이다. 현재 비트(present bit)라고도 한다.
- 읽기,쓰기,실행 비트: 말그대로이다.
페이지 부재
가상 메모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지, 스왑 영역에 있는지 표시하기 위해 유효 비트를 사용한다. 페이지가 요청했을 때 그 페이지가 메모리에 없는 상황을 페이지 부재(page fault)라고 한다. 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다.
만약 페이지 부재가 발생하면 스왑 영역에서 비어 있는 프레임으로 스왑인을 통해 가져온다. 그리고 이를 페이지 테이블에 유효비트와 프레임위치를업데이트 한다.
그런데 만약 빈 프레임이 없을 떄는 프레임 중 하나를 스왑인해야 해당 페이지를 가져올 수 있다. 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘을 페이지 교체 알고리즘(page replacement algorithm)라고 한다. 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지라고 한다.(victim page)
메모리가 꽉 찬 페이지 부재 작업 순서
- 해당 페이지의 유효 비트가 1이여서 페이지 부재가 발생한다.
- 메모리가 꽉 차있어서 메모리의 페이지중 하나를 스왑 영역으로 내보낸다. (스왑아웃)
- 스왑 아웃 한 곳의 유효비트, 프레임을 스왑주소로 바꿔준다.
- 스왑인을한다.
- 스왑인 유효비트, 프레임을 업데이트한다.
세그먼테이션 오류와 페이지 부재는 많은 차이가 있다. 세그먼테이션 오류는 사용자의 프로세스가 주어진 메모리 권한을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생한다. 즉 사용자 프로세스에 의해 발생하며 해당 프로세스를 강제 종료하여 해결한다. 반면 페이지 부재는 물리 메모리가 없을 때 발생하는 오류로 사용자 프로세스와 관계없다.
지역성
페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때는 지역성(locality)을 바탕으로 한다. 지역성이란 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 것을 말한다.
- 공간의 지역성 : 집 바로 옆의 편의점과 건너편의 편의점중 가까이 있는 편의점에 갈 확률이 높은것 처럼 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다는 것이다.
- 시간의 지역성 : 1년 전에 구매한 CD와 어제 구매한 CD중 어제 구매한 CD를 들을 확률이 더 높다. 이와 마찬가지로 시간의 지역성(temporal locality)은 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다는 것이다.
- 순차적 지역성(sequentia; locality) : 작업이 순서대로 진행되는 경향이 있다는 것을 의미한다.
지역성 이론은 캐시 등 많은 곳에서 사용한다.
개요
메모리 꽉 찼을때 스왑 영역을 보낼 페이지를 결정하는 알고리즘이다.
종류
| 종류 | 알고리즘 | 특성 |
|---|---|---|
| 간단한 알고리즘 | 무작위 | 무직위로 대상 페이지를 선정하여 스왑 영역으로 보낸다. |
| 간단한 알고리즘 | FIFO | 처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다. |
| 이론적 알고리즘 | 최적 | 미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다. |
| 최적 근접 알고리즘 | LRU | 시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다. |
| 최적 근접 알고리즘 | LFU | 사용 빈도가 적은 페이지를 스왑 영역으로 보낸다. |
| 최적 근접 알고리즘 | NUR | 최근에 사용한 적이 없는 페이지를 스왑 영역으로 보낸다. |
| 최적 근접 알고리즘 | FIFO 변형 | FIFO 알고리즘을 변형하여 성능을 높인다. |
성능 평가 기준
페이지 부재 횟수, 실제로 작업에 들어갈 때까지의 평균 대기 시간, 전체 작업 시간 등등이 있지만 메모리 접근 패턴을 사용하여 페이지 부재 횟수와 페이지 성공 횟수를 보통 기준으로 한다. 또한 유지비도 고려해야한다.
무작위 페이지 알고리즘(random page replacement algorithm)
가장 간단한 구현 방식, 스왑 영역으로 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정한다. 딱봐도 거의 사용되지 않는데 진짜다.
FIFO 페이지 교체 알고리즘
선입선출 페이지 교체 알고리즘이라고도 하며 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 사용한다. 하지만 자주 들어오는 것과 가끔 들어오는 것도 그냥 공평하게 처리하기 떄문에 성능문제가 발생하는데 2차 기회 페이지 알고리즘이 이러한 문제를 개선하였다.
최적 페이지 교체 알고리즘
앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상으로 한다. 미래의 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋다. 하지만 미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없다. 그래서 구현이 가능하면서 최적 페이지 교체 알고리즘에 근접한 방법을 연구해서 LRU, LFU, NUR 등이 개발되었다. 이러한 알고리즘들은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(Optional approximation algorithm)이라고 부른다.현대의 인공지능과 참 유사하다.
LRU 페이지 교체 알고리즘(Least Recently Used page replacement algorithm)
최적 근접 알고리즘 중 하나로 최근 최소 사용 페이지 교체 알고리즘이라고도 한다. 이 알고리즘은 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다. LRU 교체 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있다.
1. 접근 시간에 기반한 구현 : 사용한 초를 기록해 두고 초가 가장 작은 페이지를 스왑아웃 대상으로 결정한다. 성능은 FIFO 페이지 교체 알고리즘 보다 우수하고 최적 페이지 교체 알고리즘보다는 조금 떨어지는 것으로 알려져 있다.
2. 카운터에 기반한 구현 : 초가 아니라 카운터로 표시한다.
어쨋든 두 방법 모두 추가적인 메모리 공간을 필요로 하는 것이 단점이다. 예를 들어 0~1024초는 10bit 더 높은 숫자는 더 높은 bit가 필요하므로 공간이 낭비될 수 있다.
- 참조 비트 시프트(reference bit shift) : 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것이다. 참조 비트의 초기값은 0이며 페이지에 접근할 때마다 1로 바뀐다.또한 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다. LFU 방식과 혼동되기도 하는데 참조비트는 접근 횟수가 아니라 가장 최근에 접근한 페이지를 기준으로 하기 때문에 LRU이다. 어쨋든 위의 두 방법보다는 메모리를 덜 쓰긴 하지만 공간을 낭비하는건 매한가지다.
LFU 페이지 교체 알고리즘(Least Frequently)
최소 빈도 사용 알고리즘이라고도 한다. 몇 번 사용 되었는지를 기준으로 대상 페이지를 선정한다. 다시 말해 현재 프레임에 있는 페이지마다 그동안 사용된 회수를 세어 횟수가 가장 적은 페이지를 스왑 아웃 한다. 차이는 횟수를 저장한다는 차이가 있으며 단점도 똑같이 추가 메모리를 사용한다.
NUR 페이지 교체 알고리즘(Not Used Recently page replacement algorithm)
LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서 불필요한 공간 낭비 문제를 해결한 알고리즘이다. 최근 미사용 페이지 교체 알고리즘 이라고도 한다. 만약 1000번 접근한 페이지와 20번 접근한 페이지가 있다면 당연히 20번 접근한 페이지를 스왑 아웃 한다. 하지만 95번과 91번은 큰 차이가 없기 때문에 누굴 보내도 상관 없다. 이러한 경향을 반영한 방식으로, 추가 비트 2개만 사용하여 미래를 추정한다.
NUR 페이지 교체 알고리즘에서는 페이지마다 참조 비트와 변경 비트를 가지므로 페이지 마다 추가되는 메모리 공간이 2비트 뿐이다. 여기서 참조 비트는 PTE의 접근 비트를 가리키고, 변경 비트는 PTE의 변경 비트를 가리킨다. 초깃값은 0이며 다음과 같은 경우에 1이 된다.
- 참조 비트 : 페이지에 접근(read/execute)하면 1이 된다.
- 변경 비트 : 페이지가 변경(write/append)하면 1이 된다.
00 01 10 11 중 00을 우선으로 하고 그다음 01,10,11 순으로 스왑아웃한다. 즉 우선 고려 대상은 참조 비트이다. 만약 0이면 변경 비트가 0인 비트를 찾는다. 만약 같은 비트가 여러개면 그중 무작위로 선정한다. 모든 페이지가 11이 되면 모든 페이지 비트를 00으로 초기화한다.
LFU,LRU와 성능은 비슷한데 메모리를 적게 쓰고 위와같이 구현도 쉽기 때문에 많이들 쓰고있다.
FIFO 변형 알고리즘
2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)
FIFO를 기반으로 하지만 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다. 다시 말해 성공한 페이지를 큐 매 뒤로 옮김으로 기회를 한 번 더 준다는 것이다. 성능은 교체 알고리즘보다 약간 낮고 FIFO보다 약간 높다. 그러나 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다.
시계 알고리즘
2차 기회 페이지 교체 알고리즘은 큐를 쓰지만 이는 원형 큐를 사용한다. 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 바닥으로 내려가면 다음번에는 다시 큐의 처음을 가리키게 된다. 포인터가 시계처럼 계속 돌기 때문에 시계 알고리즘이다. 만약 페이지 부재가 일어나지 않으면 큐를 가만히, 일어나면 한칸씩 이동하며 교체한다. 또한 참조비트를 통해 만약 페이지를 성공적으로 참조하면 0에서 1로 바뀐다. 포인터를 바꿀 때 참조비트가 1인 페이지는 건너뛴다.하지만 참조비트가 1인 페이지를 건너 뛸때 다시 0으로 참조비트트를 바꿔놓는다. 시계 알고리즘은 대상 포인터와 각 페이지당 참조 비트 하나만 추가하면 되기 때문에 NUR 페이지 교체 알고리즘보다 추가 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 것이 단점이다.
스레싱
메모리가 꽉 차고 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱(threshing)라고 한다. 멀티프로그래밍(동시의 실행하는 프로그램의 수) 정도가 너무 높으면 스레싱이 발생한다. 작업 불가능한 상태를 스레싱 발생 지점이라고 한다. 하지만 한계 이상으로 간다고 더 빨라지진 않는다. 즉 16GB와 32GB는 일반인은 차이를 느낄 수 없다.
남아있는 프레임을 실행 중인 프로세스에 적절히 나누어주는 정책이 필요한데 프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분된다.
정적 할당(static allocation)
프로세스 실행 초기에 프레임을 나눠준 후 그 크기를 고정하는 것으로, 균등 할당 방식과 비례 할당 방식이 있다.
균등 할당 방식
균등 할당(equal allocation) 방식은 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다. 크기가 큰 프로세스는 필요한만큼 할당 못받아서 페이지 부재 너무 발생한다. 작은애들은 내부단편화 발생한다.
비례 할당
프로세스 크기에 맞춰서 할당한다. 하지만 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못하고 사용하지 않을 메모리를 미리 확보하여 공간을 낭비한다.
동적 할당(working set model)
지역성 이론을 바탕으로, 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다는 가정에서 출발한다.
페이지 부재 빈도
페이지 부재의 상한선과 하한선을 적절하게 정해서 그에 대한 빈도에 맞게 메모리를 할당한다.
전역 교체와 지역 교체
전역 교체
전체 프레임을 대상으로 교체 알고리즘을 적용한다. 장점으로는 시스템 효율이 올라가지만 다른 프로세스의 영향을 줄 수 있다.
지역 교체
프로세마다 프레임을 적당하게 할당해주고 여기서 교체를 시행한다. 다른 프로세스에 영향을 미치지 않지만 시스템 효율성이 떨어진다.
쓰기 시점 복사
실제로 fork를 통해 복사를 하고 쓰기 직전까지 복사를 미루다가 실제로 쓰기 시작할때 복사를 하는 것을 말한다. 요구페이징과 닮은점이 많다. 요구 페이징은 사용자가 요구할 때까ㅏ지 페이지를 물리 메모리로 가져오는 것을 최대한 미루고, 쓰기 시점 복삳도 필요하다고 판단될 때까지 데이터의 복사를 최대한 미룬다. 프로세스복사를 해도 프로세스가 사용하는 변수는 공유할 수가 없다. 즉 fork를 한다고 바로 복사를 하는게 아니고 실제로 쓰기작업 전까지는 공유하여 사용하고 쓰기작업 후 메모리를 할당한다.
