상 메모리의 관리(적재, 배치, 할당 기법)

가상 메모리란 프로그램의 일부분이 메모리에 올라오도록 함으로써 보다 많은 개수의 프로세스를 메모리에 수용함과 동시에 아무리 큰 프로그램도 실행 가능하게 해준다.

이 방법이 유용하게 작용하려면 사상 과정을 최대한 빨리해야하고, 참조하고자 하는 페이지가 메모리에 있어 줄수록 높아진다.

이번에는 가상 메모리의 관리기법에 대해서 알아보자.

우선 크게 두가지 방법이 있다.

첫째, 하드웨어를 사용하는 기법. 이것은 TLB라는 추가의 하드웨어를 사용한 방법이다.(내 블로그에 보면 TLB에 관한 내용이 있다. 읽어보도록...)

둘째, 정책들을 정해놓고, 소프트웨어적으로 관리를 하는 기법들이다.

<적재 정책>

실행에 필요한 페이지를 언제 메모리에 적재할 것인가를 결정하는 정책이다.

1. 요구 적재

페이지가 참조될 때 적재하는 기법이다. 당연하게 보이는 이 기법은 참조하는 페이지들로만 메모리를 사용하게 되므로 메모리에 관한 한 오버헤드가 없으나, 참조시 페이지 부재일 경우 입출력 부담이 있게 된다.

2. 예측 적재

예측을 통해 확률적으로 참조될 가능성이 높다고 판단되는 페이지를 미리 적재 시키는 기법이다. 예측이 잘 될 경우 페이지 부재 빈도를 낮출 수 있으나, 반대의 경우에는 예측을 위한 오버헤드와 함께 참조되지 않을 페이지를 적재한 메모리 낭비 발생한다.

<배치 정책>

디스크로부터 가져온 페이지를 메모리의 어디에 적재할 것인가를 결정하는 정책이다. 페이징을 사용하는 시스템에서는 빈 프레임만 발견되면 어떤 프레임에 적재하든 문제가 없다. 세그먼테이션을 사용할 경우는 세그먼트의 크기가 얼마든지 다를 수 있으므로, 다양한 크기의 세그먼트를 수용할 수 있는 배치 정책(최초 적합 등)이 요구된다. (최초, 최적, 최악기법이 있음)

<할당 정책>

프로세스들에게 메모리를 얼마큼씩 줄 것인지를 결정하는 정책이다. 페이징의 경우 각 프로세스에게 메모리 프레임을 몇 개 사용할 수 있도록 해 줄 것인가를 결정하는 정책이다. 개수의 변동이 없도록 운영한다면 고정 할당이라 부른다. 반면에 실행 도중 프로세스에 부여된 프레임의 수에 변동이 있도록 한다면 가변 할당이라 부른다.

<교체 정책>

메모리에 빈 프레임이 없을 때 적재될 페이지를 위해 적재된 페이지 중 누군가는 자신이 차지한 프레임을 비워주어야 하는 교체 대상이 되어야 할 텐데, 이때 어떤 페이지를 선택할 것인가를 결정하는 정책이다.

1. 최적기법

현 시점에서 앞으로 가장 오랫동안 참조되지 않을 페이지 즉, 미래에 참조될 때까지의 시간이 가장 긴 페이지를 선택하여 교체하는 기법이다.

페이지 부재를 최소로 해주지만, 프로세스들이 앞으로 어떤 페이지들을 참조할지를 미리 알 수는 없으므로 현실적으로 구현 불가능하다.(미래 예측 불가능)

 

 

2. FIFO(First In First Out) 기법

적재된 지 가장 오래된 페이지를 교체하는 기법이다. 시간 기록 기법(각 페이지가 적재될 때의 시간을 기록한 후, 교체 시 이 시간이 가장 오래전인 페이지를 선택하는 방식)을 사용한다.

큐를 사용하여 큐에서의 상대적인 위치가 적재된 순서를 나타내는 것으로 교체의 대상은 항상 큐의 맨 앞이 되도록 유지, 관리하는 기법이다.

FIFO 모순(Belady’s Anomaly) - FIFO에서 부재율을 낮추기 위해 프레임을 더 주었을 경우 오히려 부재율이 올라가는 현상을 발생할 수 있음

 

3. LRU(Least Recently Used) 기법

참조된 지가 가장 오래된 페이지가 교체 대상으로 하는 기법이다.

시간 기록 기법을 사용하여 페이지들이 적재될 때 의 시간을 기록한 후 이 페이지가 메모리에 있는 동안 참조될 때마다 가장 최근의 참조 시간으로 갱신(FIFO랑 다른 점)해 놓으면, 가장 오래전 시간이 기록되어 있는 페이지가 교체의 대상이 된다.

스택(Stack)을 사용하는 방법으로, 스택의 가장 밑(Bottom)에 있는 페이지가 교체 대상이 되도록 스택에서의 위치가 상대적인 참조 순서를 나타내도록 관리하는 방법이다.

 

 

4. Second-chance 기법

적재된 후 한번이라도 더 참조된 페이지를 바로 교체시키지 않고 한 번 더(Second) 메모리에 머무를 수 있는 기회(Chance)를 주는 기법이다. 적재된 페이지에 참조 비트를 두어 교체 대상인 페이지의 참조 비트가 0이면 바로 교체되고, 1로 되어 있을 경우 즉, 적재 도중 한번 이상 참조된 경우 이 비트를 0으로 만들면서 큐의 맨 뒤로 보냄으로써 메모리에 머무를 기회를 한 번 더 주는 것이다.

 

 

5. 개선된 Second-chance (또는 NUR) 기법

Clock 기법에 갱신 비트를 추가하면 보다 나은 교체 정책을 만들 수 있다는 생각으로 출발한 기법이다.

(갱신 비트가 1이란 말은 이 페이지가 적재 중 변경되었다는 것을 의미)

교체가 될 경우 변경된 내용으로 디스크에 기록을 해 주어야 하는 부담이 있으므로 가급적 교체를 미루어 디스크에 대한 쓰기 작업을 줄이고자하는 의도이다.

참조 비트와 갱신 비트 값의 조합은 네 종류로서 참조도 변경도 되지 않은 경우부터 참조되고 변경까지 된 경우 -> 11, 10, 01, 00

- 첫 번째 단계로, 현재 포인터 위치에서 포인터를 이동하며 참조와 갱신 비트가 모두 0인 페이지를 찾아 교체하고 다음 페이지로 포인터를 위치시킨다.

- 첫 번째 단계에서 그런 페이지를 찾지 못하면 두 번째로 참조는 0, 갱신은 1로 되어 있는 페이지를 찾아 교체

- 포인터를 이동하면서 모든 프레임의 참조 비트를 0으로 바꿈

- 두 번째 단계에서도 해당 페이지를 찾지 못했다면 포인터는 제자리로 돌아와 있을 것이며, 모든 프레임의 참조 비트는 0이 되어 있을 것이므로 다시 첫 번째 단계를 시도하고 안 되면 두 번째 단계까지 시도 해 보면 교체 대상 페이지가 발견될 것임

NUR 역시 참조와 갱신 비트를 사용하되, 참조 비트는 시스템에서 주기적으로 0으로 만들어줌

6. LFU (Least Frequently Used) 기법

적재되어 있는 동안 참조된 횟수를 누적하여 기록한 후 그 값으로 교체 대상을 선택하는 기법

LFU는 많이 참조된 페이지는 앞으로도 참조될 확률이 높을 것이란 판단에 근거하여 값이 가장 작은 페이지를 선택

7. MFU (Most Frequently Used) 기법

MFU는 많이 참조된 페이지는 충분히 참조가 이루어졌으므로 더 이상 참조되지 않을 것이란 판단에 근거하여 값이 가장 큰 페이지를 선택

LFU와 MFU 두 기법 모두 편향된 시각에 근거함으로써 실제로 구현되는 경우는 매우 드뭄

Copyrightⓒ2014 By 휴먼사이언스