페이지 교체 정책[Page Replacement Policy]

 페이지 교체란?

프로세서가 프로그램을 실행하기 위해서 필요한 페이지 A가 필요하다고 가정하자.

그래서 해당 페이지가 메모리에 존재하는지 확인하는데... 없다!!

그러면 찾아서 메모리에 올려야 할 것이다. 하지만 물리 메모리가 가득 차있다면?

4G중 4G가 가득 차있다면 ... 그러면 가장 필요없다고 생각되는 친구를 디스크로 쫓아

내고 공간을 마련해야 할것이다.

그러면 어떤 페이지를 디스크로 쫓아 낼 것인가? 고민을 해보자..

그냥 내맘대로?... 쫓아 냈다고 가정하자. 

그런데 막상 쫓아 내고 보니까.. 다음에 또 필요한 친구였다. 그러면 또 이를 해결하기 

위해서 과정이 필요 할 것이다. 

최대한 효율적으로 미래를 알순 없지만 미래를 예상해서 쫓아 내야 할것이다.

그러면 가장 효율적인 쫓아냄 == 가장 효율적인 페이지 교체 방법은 무엇일까?

LRU라고 들어 보았을 것이다. Least Recently Used --> 오래전에 사용된 이라는 뜻

--> 주관적으로 이해를 이용한 생각.

가장 오래전에 사용되었다라.... 우리 일상 생활을 예를들어서 생각해보자.

우리가 회사를 다니거나 학교를 다닌다고 가정하자. 그러면 자주 입는 옷이 있을 것.

비록 대학생이지만 고등학교를 생각하자. 교복을 입을 것이다. 

그런데 옷을 사놓다 보니까.. 옷장이 가득 찼다.[물리 메모리] 그럼 이제 가장 불필요한

옷을 버려야 할것이다. 그러면 뭘 버릴것인가?

매일 매일 입고가는 교복을 버릴 것인가?, 아니면 10년전에 입은 티를 버릴것인가.

당연 10년전에 입은 티를 버릴것이다. 이러한 관점으로 생각해보면 좀 더 이해하기 쉬

울거 같다.

앞서 설명 할 때, 최대한 효율적으로 미래를 알순 없지만 미래를 예상해서 쫓아 내야 

할것이다. 라고 하였다.

이러한 내용을 표현 하는것이 지역성[Locality]라는 개념이다. 

시간 지역성 :현재 참조된 메모리가 가까운 미래에 다시 참조될 가능성이 높다는 내용이다 그리고 반복문, 동일한 함수 등... 에서 많이 일어날 것이다.

공간 지역성: 하나의 메모리 주소 공간이 참조되어지면 그 근처의 메모리 주소 공간이 계속 참조될 수 있다는 특성이다. 순처적으로 실행되는 코드, 배열등을 생각해보자.

이러한 지역성을 잘 표현 한것이 LRU의 특성 자주 사용되는 놈, 오래 사용되지 않는놈을 쫓아 낸다는 개념과 잘 어우러 질것이다.

그러면 이러한 LRU 교체 방식을 어떻게 구현 할 것인가?

이를 구현하기 위해서 참조 비트[Reference Bit]를 사용하는 것이다.

참조 비트란 해당 페이지가 참조 될때마다 최근에 사용되었다 라고 프로세서가 침을 

발라놓는 개념이다. 그러면 그 침?을 통해서 이게 최근에 사용되었지! 라고 찾는 것

이러한 개념[Reference Bit]을 이용하여서 2가지 알고리즘이 있다고 한다.

1. Additional Reference Bits 알고리즘

개인적으로는 해당 알고리즘은 비효율적이라고 생각되지만.

해당 알고리즘은 메모리에 올라와 있는 페이지에 각 8bit를 유지하는 테이블을 구축 

하는 것이다. --> 이게 비효율 적이라는 것이다. 페이지가 1000개 있다고 하면

얼마나 많은 바이트를 낭비하는 것인가?...

이를 이용해서 일정 시간마다 [Timer Interrupt]를 이용해서 참조되었는지 아닌지를

확인 하는것이다.

참조 되었으면 1을 셋팅하고 아니면 0으로 나둔다. 그리고 시간이 지나면 이를 shift 

연산을한다. 이를 8bit 주기 동안 진행한다.

그리고 해당 주기가 끝나고 나서 가장 작은 bit가 생성된 페이지를 아웃 시키는 것이다

2. Second Chance 알고리즘

해당 알고리즘은 위의 알고리즘 보다는 효율적이라고 생각하고, 내가 구현한다고 하면

위와 같은 알고리즘을 이용하여서 구현할 것이다. 

Circular Queue[순환 큐]를 사용하여서 다음에 교체될 페이지들에 대한 목록을 저장.

각 페이지마다 1bit의 참조 비트를 구현한다. 그리고 참조되어 진다면 1로 셋팅한다.

그리고 이제 Page를 아웃 시켜야 하는 상황이 오면 해당 순환 큐를 탐색 할 것이다.

탐색 할 때 발생되는 상황은 2가지이다.

한가지는 참조 비트가 1인 비트는 이제 0으로 변경되어진다.

다른 한가지는 참조 비트가 0인 비트는 이제 Out되는 것이다.

즉 2번의 기회를 주는 알고리즘 인것이다. 

자주 사용되는 페이지는 1에서 0으로 바껴도 다시 참조 될 것이기 때문에 1로 변경되

살아 남을 것이기 때문이다.