페이지 교체 알고리즘[Reference bit, Aging, Clock , NRU , LFU , MFU ], 프레임 할당 알고리즘 [고정, 가변 할당 알고리즘]

LRU 의 문제점

너무 많은 작업이나 하드웨어 자원이 필요

counter 이용은 페이지 테이블 검색 시간 O(n)이 필요

Stack 이용은 페이지 접근 당 6개의 포인터 변경 필요

 

LRU 근사 알고리즘

대충 그럴꺼 같다는 식으로 희생자를 선택합니다.

• Reference bit
• Aging
• Clock (Second chance)
• NRU Not Recently Used
• LFU Least Frequently Used
• MFU Most Frequently Used
• 페이지 버퍼링

 

Reference bit algorithm

• 참조비트를 두는 것입니다. 각 페이작 참조비트를 참조할 때 마다 1로 변환시킵니다.( 초기값은 0입니다.)
• 참조 비트가 1이면 최근에 참조가 됬다는 뜻입낟.
• 참조 비트가 0이면 페이지를 교체합니다.
• 참조 비트들은 주기적으로 0으로 바꿔줘야하죠
• 너무 단순합니다.

Reference bit algorithm 개선

• Aging
• Clock (Second chance)
• NRU Not Recently Used

 

Aging

개선시킨 알고리즘 입니다.

나이를 참조 비트들로 먹게 하빈다.

 

• 페이지 3을 참조하면 참조비트 1이 생기겠죠?
• 그 다음 페이지 모두다 right shift를 합니다.

 

• 그러면 모두 0으로 다시 셋팅되어있습니다.
• 그 순간! 페이지 2, 3이 참조되어서 참조비트가 1이 됩니다.

 

• 또 반복하고 페이지1, 3이 참조되었습니다.
• 다음 참조는 페이지 2,4가 참조되었습니다. 

이런 식으로 희생자를 찾습니다.

 

맨 앞에 1이 나왔다는 뜻은 최근에 참조 되었다는 뜻입니다.

그럼 희생자를 어떻게 찾나요? 

숫자가 가장 작은 것(페이지 5)

 

우측 쉬프트는 과거의 영향력을 약하게 합니다.

 

Clock(Second chance) algorithm

2번째 기회를 준다는 알고리즘, 시계처럼 돌아서 시계알고리즘이라고도 합니다.

• 오래되고 사용하지 않는 페이지 교체
• FIFO 큐에서 다음 희생자 선택
• 만약 다음 희생자의 참조 비트가 1이면 0으로 바꾸기만 하고 전진

프레임들을 차례대로 돌아가면서 희생자로 삼습니다.

FIFO와 비슷하죠?

여기서 프레임 마다 참조비트를 추가합니다.

 

참조비트가 1이면 "최근에 참조 되었어요 살려주세요" 하고 0으로 바꾸고 지나갑니다.

Clock algorithm 예시입니다.

프레임 번호는 다음 희생자를 선택하는 역할을 합니다.

 

4번이 희생자 될뻔 했는데 0으로 바꾸고 넘어갔습니다.

 

프레임이들이 있고요

7,0,1,2,0H들은 페이지 번호 입니다.

 

프레임 안에는 페이지번호, 참조비트가 있습니다.

 

화살표는 돌아가면서 희생자를 찾게됩니다.

• 처음에 7은 희생자 프레임에 아무도 없으니 들어갑니다
• 0, 1도 들어갑니다.
• 2가 들어오려 합니다. -> 7이 나가야 합니다.
• 0을 다시 엑세스 하려하면 희생자를 고를 필요가 없습니다. -> 참조비트 1로 바꾸기
• 3이 들어오려고 합니다. 그 때 {0, 1}이 희생자로 지목되었습니다.
• 근데 최근 참조했으니 봐줘야 합니다. -> 다음 페이지로 희생자 포인터가 넘어갑니다.
• ???에는 [   { 2,0 }  ,   { 0, 0 }  ,  { 3, 0 }   ]

 

• 0이 참조되러 합니다. -> 0의 참조비트를 1 로 만들어야 합니다.
• 다음 4를 엑세스 하려 합니다. { 2, 0 } 이 희생되어야 하죠
• 다음 2를 엑세스 하려합니다. 하지만 희생자가 참조비트가 1이니 살려줘야 합니다.
• 다음 프레임으로 희생자 포인터를 이동시킵니다.  -> {3, 0} 
• ???에는 [   { 4,0 }  ,   { 0, 0 }  ,  { 2, 0 }   ] 페이지 교체가 일어난 후 다음 희생자 포인터를 옮겨야 합니다.

 

NRU(Not Recently Used) 알고리즘

페이지 항목에 2비트를 추가합니다.

• 참조 비트 - 읽거나 쓰기가 되었는가?
• 수정 비트 - 수정이 되었는가?

참조되고 수정되면 희생자가 될 가능성이 낮습니다.

 

어떻게 참조도 안되면서 수정이 될 수있지?

시간이 지나면 참조비트든 수정 비트든 0으로 바꿔줘야 합니다.
참조 비트는 수정비트보다 더 많이 참조가 됩니다.
2개 비트 다 주기적으로 0으로 리셋해야 합니다.
그런대 참조비트가 더 많이 0으로 리셋되서 0 1 로 보여질 수도 있는 것입니다.

 

시계 알고리즘에서 참조비트가 1이면 살려주었었습니다.

그런데 2개의 비트를 줘서 2번의 기회를 더 줄 수 있습니다.

 

 

Counting Algorithms

최소 사용 빈도수(LFU) - count 횟수가 적은 것을 희생자로 삼습니다.( 사용 빈도가 낮았으니 앞으로노 낮을 것이다.)

 

최대 사용 빈도수(MFU) - 빈도수가 높다면 "아~ 이미 많이 사용됐구나" 하고 내쫒습니다.

카운트를 주기적으로 우측 쉬프트 시키면 과거의 영향력을 약화시킵시다.

그렇게 보정해서 사용할 수 있습니다.

 

그런데 이런 예측이 맞을 까요?

- 구현 비용  크고 성능 낮음

- LRU 근사를 잘 못하므로 일반적으로 사용 안됨

 

 

 

최소 사용 빈도수

제일 적게 count한 것이 희생자가 된다.

 

빈도수가 낮은 것이 2개 있다면 먼저 들어온 것을 희생자로 삼읍시다.

 

첫 번째 [ ?, ?, ?, ?] = [1 , 2 , 5 , 4] 

두 번째 [ ?, ?, ?, ?] = [1 , 2 , 5 , 3]

 

*는 뭘까요? 페이지 부재 입니다.

총 페이지 엑세스 횟수는 12 입니다.

 

페이지 부재 비률 = 8/12 

 

 

최대 사용 빈도수

제일 많이 count한 것이 희생자가 된다.

 

빈도수가 높은 것이 2개 있다면 먼저 들어온 것을 희생자로 삼읍시다.

 

첫 번째 [ ?, ?, ?, ?] = [5 , 2 , 3 , 4]

두 번째 [ ?, ?, ?, ?] = [5 , 1 , 2 , 3]

*는 뭘까요? 페이지 부재 입니다.

총 페이지 엑세스 횟수는 12 입니다.

 

페이지 부재 비율 = 10/12

 

---

페이지 버퍼링

빈 프레임들을 유지하는 알고리즘 입니다.

내쫒겨 나갈 페이지들을 잠깐동안 메모리에 유지합니다.

 

이미 디스크로 나갔어야 할 놈인데 잠시 메모리에 둡니다.

 

교체된 페이지의 리스트를 2개로 관리합니다.

• 수정된 적 없는 페이지 - 내용물은 없지만 빈 프레임 입니다.(할당 가능)
• 수정된 페이지 - 디스크로 바로 내쫒지 않고 한꺼번에 내쫒습니다.(속도 향상)

 

 

페이지 리스트 위쪽 그림에는 에서는 실제로 사용는 프레임이 있습니다.

 

 

신속 페이지 교체

• 수정된 페이지를 디스크에 쓰지 않으므로(그냥 모아둠)
• 부재 페이지를 디스크가 아닌 메인 메모리에서 가져 오는 경우도 있으므로(디스크에서 가져와야 하는 것을 그냥 메모리에서 가저옴)

 

페이지 교체 알고리즘의 비교

OPT가 가장 이상적입니다.(하지만 미래를 알지 못하기 때문에 구현할 수 없습니다.)

비슷하게 구현하려고 한것이 LRU(최근 최소 사용 교체)

선입선출 - 가장 성능이 않좋습니다.

 

시계는 중간 성능을 보여줍니다.

---

프레임 할당 알고리즘

가상 메모리를 구현하려 할 때 가장 중요한 것이 프레임 할당, 페이지 교체 알고리즘이 가장 중요합니다.

• 프레임 할당 - 프로세스에게 몇 개의 프레임을 줄 것인가
• 페이지 교체 알고리즘 - 어떤 페이지가 교체되어 나갈 것인가

 

그래프는 페이지의 부재 비율 / 할당되는 프레임의 갯수

 

프레임이 많아질 수록 페이지 부재 비율이 낮아 집니다.

적절한 프레임 수를 찾아서 프레임에 할당 합시다.

 

프레임 할당 알고리즘

• 고정 할당 알고리즘 - 각 프로세스에게 고정된 수의 프레임을 할당
  Proportional Allocation - 프로세스에 맞춰서 고정 할당
• 가변 할당 알고리즘 - 실행 중에 프레임이 변하는 것
  - working set model을 이용해서 프레임 수 변동
  - 페이지 부재율을 직접 조절하는 방법

 

균등 할당Equal allocation

• 각 프로세스에 같은 개수의 프레임을 할당
• 프로세스마다 메모리 필요량이 달라서, 어떤 프로세스는 프레임을 낭비하고, 어떤 프로세스는 빈번한 페이지 부재로 난항

비례 할당Proportional allocation

s는 각 프로세스의 가상 공간 크기 입니다.

각 프로세스의 가상 공간을 모두 더하면 모든 프로세스의 가상 공간의 크기가 나옵니다.

 

a는 i라는 프로세스에게 할당되는 프레임 수

(프로세스의 가상공간 크기 / 전체 가상공간 크기) * 사용 프레임 수(m) 

 

즉, 가상공간이 큰 프로세스는 크게, 작은 프로세스는 작게 할당합니다.

 

우선순위 비례 할당과 혼합해서 쓰면 가상공간이 크고 우선순위가 높으면 더 많이 주겠죠?

 

 

 

 

 

 

 

 

 

명령어(프레임) -> 간접주소(프레임) -> 데이터(프레임)

 

 

 

 

 

 

 

1번 입니다.

2번 - 최소 프레임 수 입니다.

3번 - 실행 도중 변경 안되는건 고정 할당 알고리즘 / 실행 도중 변경 되는건 가변 할당 알고리즘

4번 - 비례 할당 입니다.