[운영체제] 대치 알고리즘

• 페이지 대치가 일어날 때는 앞으로 page fault가 최대한 일어나지 않도록 최선의 페이지를 대치시켜야한다.
• 그를 위한 다양한 알고리즘들이 존재한다.

최적알고리즘과 최악알고리즘

• 최적 대치 알고리즘 : 앞으로 오랫동안 사용되지 않을 페이지를 찾아서 교체하는 것이 최적일 것이다. 이러한 최적 대치 알고리즘은 벨러디알고리즘 또는 BO 알고리즘이라고 불린다. 하지만 해당 알고리즘은 오랫동안 사용되지 않을 페이지를 미리 아는 방법이 없기 때문에 사실상 실현이 어렵다. (cf. 이렇게 미래를 미리 예측하는 알고리즘은 lookahead 알고리즘이라고 불린다.)
• 실현은 어렵지만 해당 알고리즘이 가지는 의미는 크다. 해당 알고리즘이 있어 이에 근접한 알고리즘을 연구할 수 있고, 이를 능가하는 알고리즘은 존재할 수 없기 때문에 더 이상 무모한 연구는 하지 않아도 되도록 해주기 때문이다.
• 최악 대치 알고리즘 : 아무 고려도 하지 않는 랜덤 알고리즘이 최악이라고 할 수 있다. 페이지 대치 알고리즘의 하한선 역할을 해준다.

FIFO 알고리즘

• 메모리에 올라온 지 가장 오래된 페이지를 택하여 대치하는 알고리즘이다.
• 페이지 오류율이 할당되는 프레임의 수가 증가함에도 오히려 증가하는 Belady’s Anomaly(벨러디 변이)가 발생할 수 있다.

LRU 알고리즘

• 가장 오랫동안 사용하지 않은 페이지를 대치한다.
• 스택 알고리즘의 일종이지만 Pop은 Bottom에서, Push는 Top에서 이루어진다.
• Locality of reference에 근거하여 가장 오랫동안 사용하지 않은 페이지는 앞으로도 상당한 기간 사용되지 않을 것을 가정한 기법이다.
• 현재 시점을 기준으로 왼쪽(과거)에서 가장 멀리 있는 페이지를 대치한다는 점에서 오른쪽(미래)에서 가장 멀리 있는 페이지를 대치하는 최적 대치 알고리즘과 유사하다.
• 임의의 참조 스트링 S에 최적 대치 알고리즘을 적용했을 때의 페이지 부재율은 S의 역순 스트링 Sr에 최적 대치 알고리즘을 적용했을 때의 페이지 부재율과 같다. 마찬가지로 임의의 참조스트링 S에 LRU 알고리즘을 적용했을때의 페이지 부재율과 참조스트링 S의 역순 Sr에 적용했을 때의 페이지 부재율이 같다. 이는 LRU가 최적대치 알고리즘에 거의 근접한다는 것을 시사한다.

LRU의 시간정보

• FIFO는 프레임에 적재된 순서를 이용하기 때문에 큐 메커니즘을 사용할 수 있어서 비교적 단순하지만 page fault rate 면에서 우수하지 않다. 반면 LRU는 적재된 순서가 아닌 '참조시간'을 정보로 활용해 부재율 면에서 우수하지만, 참조된 시간을 관리하는 것이 적재 순서를 관리하는 것보다 어려워 성능에 문제가 생길 수 있다. 시간정보를 구현하는 방법은 크게 두가지가 있다.
• 참조시간에 대해 시간값을 그대로 활용할 수 있다. 페이지 테이블에 타임 필드를 두고 페이지 참조가 일어날 때마다 시스템의 클럭 레지스터 값을 복사하여 기록하고, 페이지 대치가 필요할 때 페이지 테이블의 타임필드들을 비교해 희생할 페이지를 찾아내는 방법이다. 하지만 해당 방법은 CPU가 메모리에 접근할 때마다 시간값을 기록해야하고 희생 페이지 결정을 위해 페이지 테이블을 탐색해야하기 때문에 성능이 좋지 못하다.
• 앞서 말했듯 스택을 이용하는 방법도 있다. 이는 마이크로코드로 구현해낼 수 있지만, 메모리 참조가 일어날 때마다 스택 업데이트에 드는 시간 소모가 조금 과다할 수 있다.

LRU 근사 알고리즘

• 시간정보 활용의 어려움때문에 하드웨어의 지원을 받는 방법으로 속도는 빠르고 page fault rate가 LRU에 근접하도록 하는 LRU 근사 알고리즘이 고안되었다.
• 해당 알고리즘 구현을 도와주는 방법에는 참조 비트, 참조 바이트, 2차 기회 알고리즘 등이 있다.
• 참조비트(reference bit) : 페이지 테이블에 참조비트가 추가된다. 처음엔 모든 비트가 운영체제에 의해 0으로 설정되고, 참조된 페이지의 참조비트가 하드웨어에 의해 1로 변경된다. 약간의 시간이 지난 다음 해당 비트를 검사하면 어떤 페이지가 참조되었었는지 알 수 있다. 이런 방식을 이용하면 특정 기간에 참조가 일어난 페이지와 일어나지 않은 페이지를 구별할 수 있으므로 부분적으로나마 페이지의 참조 순서정보를 추출할 수 있다. 따라서 LRU에 근사한 다양한 대치 알고리즘에서 사용할 수 있다.
• 참조바이트 : 페이지마다 참조바이트를 하나씩 마련한다. 타이머 인터럽트를 활용해 일정기간(ex.100ms)마다 참조바이트를 우측으로한 비트 쉬프트를 하고, 참조비트를 참조바이트의 맨 왼편 최고위 비트, MSB(Most Significant Bit)에 복사한다. 그리고 다시 0으로 설정한다. 그 결과 참조바이트는 해당 페이지에 대해 최근 8회(8비트)의 인터럽트 기간동안의 페이지 참조기록을 간직하게 된다. 매번 오픈편으로 쉬프트 후 참조비트를 MSB에 복사했기 때문에 최근에 참조된 페이지일수록 참조바이트의 값이 클 것이다. 반면 가장 오랫동안 사용하지 않은 것일수록 값이 작을 것이다. 따라서 참조바이트의 값이 가장 작은 페이지를 대치한다.(겹칠경우 FIFO 등 하드웨어 지원 없이 구현되는 방법을 사용한다.) 해당 방법은 바이트를 활용하기 때문에 8회의 클럭 인터럽트 기간보다 이전의 참조 상황은 파악할 수 없다.

2차 기회 알고리즘(Second-chance Algorithm)

• 시스템에 따라 참조바이트가 제공되지 않거나 더 적은 수의 비트만 제공될 수 있다. 이러한 경우를 위해 고안된 알고리즘이 2차 기회 알고리즘이다.
• 페이지 테이블을 순서대로 하나씩 보면서, 각 페이지의 참조비트가 0이면 해당 페이지를 희생시키고 만약 1이면 0으로 변경 후 넘어간다. 즉, 1이면 0으로 변경하고 넘어가면서 0인 페이지가 나타나면 바로 해당 페이지를 희생시키는 것이다. 모든 페이지 테이블 검사 후에도 희생시킬 페이지가 없을 경우 처음으로 다시 돌아가 검사한다.
• 해당 알고리즘의 효율은 거의 LRU에 근접한다.
• 이러한 순환식 검사를 구현하기 위해 순환 큐를 활용한다. 해당 큐 에는 포인터 또는 시계침같은 것이 있어 페이지들을 순환적으로 돌아가며 가리키다 희생페이지를 찾으면 해당 위치에서 멈추었다가 다음번 페이지 대치요구 발생 시 해당 위치에서 재가동된다. (이런 이유로 해당 알고리즘은 클럭 폴리시라고도 한다.)
• 두번째 바퀴가 발생하면 모두 0으로 바꿔놓고 돌아가는 것이므로 FIFO와 마찬가지가 된다.

2차 기회 알고리즘 개선

• 2차 기회 알고리즘에 일전에 설명한 변경비트(dirty bit or modify bit)를 추가 활용한다.
• 이를 이용해 각 페이지의 등급을 나눈다.
• 1등급은 (0, 0)으로 최근에 참조되지도 않고 변경되지도 않은 페이지 (write back 불필요)
• 2등급은 (0, 1)로 최근에 참조되지 않았지만 변경은 된 페이지 (write back 필요)
• 3등급은 (1, 0)으로 최근에 참조는 되었으나 변경은 되지 않은 페이지 (재활용 가능성 높음, write back 불필요)
• 4등급은 (1, 1)로 최근에 참조되고 변경도 된 페이지 (재활용 가능성 높음, write back 필요)
• 1등급인 페이지를 가장 우선 희생시킨다.
• 입출력 횟수를 줄일 수 있어 기존의 2차 기회 알고리즘보다 성능이 좋다.
• cf. 이 외에도 LFU(Lease Frequently Used) 알고리즘, MFU(Most Frequently Used) 알고리즘 등 많은 다른 알고리즘이 있지만 이들을 구현하는데에는 많은 비용이 들고 최적대치 알고리즘에 근사하지 못해 일반적으로 잘 사용되지 않는다.

사전 대치, 사전 부재

• 페이지의 부재가 한번 발생하면 많은 오버헤드가 야기된다. 트랩에 의해 처리되고 해당 프로세스를 다시 실행시키기 위한 스케줄링도 수반되며, 페이지 대치까지 수행되어야하면 더 많은 시간이 소요된다. 오염비트는 write-back을 줄일 수 있어 약간의 도움이 되지만 한번 페이지 부재가 일어나면 많은 작업이 수행된다.
• 이를 방지하기 위해 페이지 대치 알고리즘을 사전에 실행해 희생 페이지를 미리 준비하는 사전대치 방법이 있다. 해당 방법은 기선정된 희생 페이지를 디스크로 write back하는 작업을 CPU와 병행할 수 있기 때문에 매우 효과적이다.
• 페이지 부재가 발생한 시점에 페이지를 적재하도록 하는 것이 아니라 미리 여러 페이지를 적재하는 사전부재 방법이 있다. 이를 위해선 참조될 페이지를 예측해 적절한 페이지들을 사전 적재해야한다. 이를 위해 함수나 행렬이 참조될 경우 연관 페이지를 모두 적재하는 방식등을 활용할 수 있다. 해당 필요정보는 컴파일러에 의해 제공받을 수 있다.