페이지 대치 알고리즘

가상 메모리의 성능은 얼마나 페이지폴트를 줄이냐가 관건이다.

물론 프레임 수가 증가하면 페이지폴트도 줄어든다. 

 

한번 대치 알고리즘에 대해 알아보자

 

선입선출 대치 알고리즘

 

각 페이지가 메모리 안으로 들어간 시간을 이용하여 가장 오래된 페이지부터 대치하는 방식이다.

 

 

 

선입선출이 간단한 구조를 가지고 있으나, 성능이 항상 좋은 것은 아니다

 

 

이렇게 프레임이 증가함에도 불구하고 페이지 폴트 수가 증가한다. 이러한 현상을 벨레디의 변이라고 한다.

 

최적 페이지 대치 알고리즘

앞으로 가장 오랫동안 사용하지 않는 페이지를 대치하는 알고리즘이다. 당연히 모든 알고리즘 중에 페이지 폴트 비율이 가장 낮다

아니 근데, 언제 사용할지 예측을 어떻게 하는데~

그래서 보통 최적 대치 알고리즘은 비교 연구하는 데에서만 사용해용

 

최근 최소 사용 대치 알고리즘

보통 가장 최근에 엑세스한 페이지는 빠른 시간 내에 다시 엑세스 할 가능성이 있다.(시간 지역성)

그래서 과거 오랫동안 사용하지 않은 페이지를 대치하는게 효율적이다. 이러한 방식이 최근 최소 사용 대치 알고리즘이다.

최근 최소 사용 대치 알고리즘은 과거의 데이터를 이용하여 미래를 예측하는 통계적 개념이다. 

메모리의 지역성을 이용한 알고리즘으로 각 페이지에 마지막으로 사용한 시간을 연관한다.

 

해당 알고리즘을 구현하려면 프레임 순서를 결정해야한다. 이는 다음 두 가지 방겁으로 구현할 수 있다.

 

1. 카운터를 이용한 순서 결정

프로세서에 논리 클록을 추가한 후 카운터 필드를 덧붙여서 프레임 순서를 결정한다.

MMS는 페이지 참조가 있을 때 마다 페이지 항목에 업데이트한다.

따라서 페이지를 참조할 때마다 클록은 증가한다.

가장 시간값이 작은 페이지가 대체된다.

 

2. 스택을 이용한 순서 결정

페이지 번호를 스택에 넣어 관리하고, 참조시마다 스택의 탑에 두어 순서를 결정한다.

 

최근 최소 사용 근접 알고리즘

최근 최소 사용 대치 알고리즘은 하드웨어에서 지원하지 않는 경우도 있어서 다른 알고리즘을 사용하기도 한다.

상당수 시스템이 참조 비트 형태를 지원하여 이 비트를 이용한 최근 최소 사용 알고리즘을 구현한다.

아래가 그 예시다.

 

1. 참조 비트 알고리즘

8비트(1바이트)에 일정한 간격으로 참조 비트를 기록한다.

그리고 8비트 시프트 레지스터를 이용하여 순서 정보를 얻는다.

값이 낮을 수록 참조가 오래 됐다는 것이다.

 

2. 시계(2차적 기회 대치) 알고리즘

가장 오랫동안 메인 메모리에 있던 페이지 중 자주 사용하는 페이지의 대치를 방지하는 것에 목적이 있다.

2차적 기회 대치 알고리즘이라고도 한다. 

 

처음에는 0으로 설정하고, 페이지 사용 시 1로 대체한다.

페이지 교체 시기가 되면 원형 버퍼에서 페이지들을 탐색하고, 1이면 0으로 변환, 0이면 해당 페이지를 대치한다.

 

 

3. NUR 알고리즘

최근에 사용하지 않는 페이지는 가까운 미래에도 사용하지 않을 가능성이 높다는 전제로 만들어졌다.

비트를 2개 사용하는데

참조 비트(R)는 해당 페이지의 엑세스 여부를 확인하여 최근 사용한 페이지를 메모리에 유지하는 역할을 하고,

수정비트(M)는 페이지 수정 여부를 확인한다.

 

따라서 페이지 폴트 발생 시 (0,0) (0,1),(1,0),(1,1), 순서로 대치한다.

 

4. 최소 사용 빈도수 알고리즘

 참조 횟수 카운터가 있으며, 가장 작은 페이지를 대치한다. 

근데 옛날에 카운트를 오래 늘린 페이지가 오래 있을 수도 있으니 일정 간격으로 카운트를 지수적으로 감소시켜야 한다.

5. 최대 사용 빈도수 알고리즘

방금 들어와서 아직 사용 안했기 때문에, 앞으로 사용할 확률이 높다고 가정한다.

그러고 나서 가장 많이 사용한 페이지를 대체한다.

성능이 개판이다.

6. 페이지 버퍼링

교체 대상으로 선택된 페이지가 즉시 교체되지 않은 채 잠시 메인 메모리에 유지하는 것을 말한다.

 

 

프레임 할당 알고리즘

페이지 대치 알고리즘을 쓰면 유연하게 메모리를 관리할 수 있다. 

그러나, 프레임을 적절히 할당하여 페이지 부재 횟수를 줄이는 방법도 매우 중요하다.

글머 어떤 식으로 할당할 수 있을까?

 

균일 - 비례 프레임 할당 알고리즘

가장 쉬운 방법이다 각 프로세스에 똑같이 프레임을 엔빵하는 것이다.

하지만, 서로 요구하는 메모리 양이 다르기 때문에 좋은 방법은 아니다.

그렇다고 맞춤으로 제공을 한다?

그러면 운영체제가 프로세스 정보를 알아야 한다는 문제가 있어 오버헤드가 발생한다.

 

따라서 현대 운영체제에서는 균일 할당하는 방식과 프로세스 실행 과정에 다르게 할당하는 비례 할당 방법을 혼합하여 이용한다.

 

스레싱

페이지 교환이 계속 일어나는 현상을 말한다.

보통 어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 길면 스레싱에 걸렸다고 표현한다.

 

스레싱은 왜 발생할까?

프로세스에 고정된 프레임 수가 현재 활동에 충분하지 않아서 서로 뺏고 빼앗기기 때문이다. 

스레싱을 줄이려면 다중 프로그래밍의 정도를 낮춰야만 한다

스레싱을 예방할 수 있을까?

프로세서 사용률과 페이지 폴트 비율을 검사하여 감지할 수 있다.