프레임과 페이지

프레임과 페이지는 메모리를 일정한 크기의 공간으로 나누어 관리하는 단위이다.

프레임은 물리 메모리를 일정한 크기로 나눈 블록이고, 페이지는 가상 메모리를 일정한 크기로 나눈 블록이다.

페이지가 하나의 프레임을 할당 받으면, 물리 메모리에 위치할 수 있게 된다. 이 페이지를 가상기억장치에 편성해 운용하는 기법을 페이징 기법이라고 한다. 페이징 기법은 주소 공간을 페이지 단위로 나누고 실제 기억 공간은 페이지 크기와 같은 프레임으로 나누어 사용한다.

이 프레임에 요청한, 참조하려는 페이지가 이미 있으면 페이지 존재, 없으면 페이지 부재라고 한다. 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다. 그럼 메모리에 이미 있는 페이지 중 하나를 디스크로 쫓아내어 빈 공간을 확보해야한다.

이 작업을 페이지 교체 라고한다.

그리고 페이지교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 흐름을 결정하는 것을 이라고 한다. 오늘은 그 여러 페이지 교체 알고리즘 중 연관이 깊은 세가지의 알고리즘을 알아보겠다.

FIFO

첫번째로 FIFO 알고리즘이다.

FIFO 알고리즘은 First in First Out의 약자로

이름 그대로 먼저 들어온 페이지를 먼저 내쫓는다.

위의 표처럼 FIFO는 프레임이 가득 차면 항상 가장 먼저 들어온 페이지를 내쫓는다.
FIFO는 향후 참조 가능성을 고려하지 않고 그냥 프레임에 올라온 순서대로 내쫓을 대상을 선정한다. 그렇기 때문에 비효율 적인 상황이 발생할 수 있다. 이 빠른 FIFO에서 비효율적인 상황을 빌레이디의 모순 현상이라고 한다. 페이지 프레임 수가 많을수록 페이지 부재수가 줄어드는 것이 일반적인데, FIFO에선 페이지 프레임 수를 증가시켜도 페이지 부재가 더 많이 일어나는 현상이다. 결론적으로 비효율이 있다고 할 수 있다.

LRU

그리고 다음은 두번째로 LRU 알고리즘이다. 이 LRU 알고리즘은 초반만 보면 FIFO와 약간 유사하다. FIFO에서 향후 참조 가능성 조건을 하나 추가한 것이라고 보면 된다. 그 조건이 바로 페이지의 참조 횟수이다. LRU는 Lest Recently Used의 약자이다. LRU는 가장 오랫동안 참조되지 않은 것이 교체대상이다. LRU는 마지막 참조시점이 가장 오래된 페이지를 내쫓고, 그 자리에 페이지를 넣는 것이다. 예제를 같이 보자.

3까지 들어오고나면 프레임이 가득찬다. 다음 4가 들어오면 가장 예전에 참조했던 1을 내쫗고 4를 1 자리에 넣는다. 다음 1 또한 2,3,4 중 2가 가장 참조한지 오래됐으므로 2 자리에 1를 넣는다. 다음 3은 페이지 부재가 일어나지 않고, 다음 5는 4 1 3 중 가장 참조한 지 오래된 것이 4이므로 4 자리에 5를 넣는다. 이러한 흐름으로 가장 마지막 참조시점이 오래된 페이지를 내쫓는 것이 LRU다.

이 LRU 알고리즘도 단점이 있다. 스택과 같은 별도의 하드웨어가 필요하고 시간적인 오버헤드가 발생된다. 매번 참조시간을 기록해야하기 때문이다.

클럭

세번째로 클럭 알고리즘이다.

이 클럭 알고리즘은 방금 전에 본 LRU와 FIFO 알고리즘 모두와 유사하다. LRU와 유사한 것 같지만 조금 다르다. LRU알고리즘은 가장 오랫동안 참조하지 않은 페이지를 교체했었는데 비해 클럭 알고리즘은 오랫동안 사용하지 않은 페이지 중 하나를 교체한다. 즉, 최근에 참조되지 않은 페이지를 교체대상으로 선정한다는 측면에서 LRU와 아주 유사하지만 교체되는 페이지의 참조시점이 가장 오래되었다는 것을 보장하지는 못한다는 점에서 LRU와는 조금 다른, LRU를 근사시킨 알고리즘으로 볼 수 있다.

클럭 알고리즘은 FIFO를 기반으로 하며 LRU와 성능이 비슷하지만 과부하가 적다. 클럭 알고리즘은 이름 처럼 시계 모양이다. 원형 버퍼로 구성되고 시계의 초침처럼 각각 관련 포인터를 갖는다. 클럭 알고리즘은 참조비트를 가지는데, 이 참조비트는 각 프레임의 사용여부를 나타낸다. 페이지가 처음 프레임내의 적재되었을 때 1로 설정이 되고, 참조될때마다 다시 1로 설정하게 된다. 만약 페이지가 교체되면 포인터는 교체된 버퍼 다음 프레임을 가리키도록 설정되어있다. 페이지를 교체할 시기가 되면 참조비트가 0인 프레임을 찾기 위해 원형 버퍼를 훑게 된다. 프레임의 참조비트가 1이면 0으로 대치시키고 다음 검사시까지 대치시키지 않는다. 그래서 만약 모든 비트가 1이면 전체를 한바퀴 돌 수도 있다. 그래서 모든 비트가 1이면 가장 오래 있었던 페이지를 내쫓던 FIFO와 흐름이 같아진다. 예제를 같이 보자.

이 원형 버퍼에서 420을 새로 참조하려고 한다. 현재 프레임 포인터는 페이지 768을 가지고 있는 프레임 4번을 가리키고 있다. 이때 프레임 4번의 비트가 1이므로 교체되지 않지만 0으로 재설정 되고 포인터는 다음 페이지로 이동한다. 같은 방식을 다음 페이지 9도 교체되지 않고 비트만 0으로 바뀌고 포인터는 다음 페이지를 가리키게 된다. 이 프레임 6인 비트가 0이므로 페이지 11은 페이지 420으로 교체된다. 이때 비트는 1로 바뀌고 포인터는 다음 페이지를 가리키게 된다.

이 클럭 알고리즘은 하드웨어적인 자원으로 동작하기 때문에 LRU에 비해 교체 페이지의 선정이 훨씬 빠르게 결정된다는 장점이 있다. 그래서 대부분의 시스템이 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다고 한다.