요구 페이징 & 페이지 교체 알고리즘

• 요구 페이징

프로세스를 메모리에 적재할때 모든 페이지가 아닌, 필요한 페이지만 메모리에 적재하는 방식

 

1. CPU가 특정 페이지 접근 명령어 실행

2. 해당 페이지가 메모리에 있으면 CPU는 페이지가 적재된 프레임에 접근

3. 해당 페이지가 메모리에 없으면 페이지 폴트

4. 페이지 폴트 처리 루틴이 해당 페이지를 메모리에 적재하고 유효비트를 1으로 설정

5. 반복

 

- 순수 요구 페이징

메모리에 아무 페이지도 없는 경우부터 실행할 수도 있다

그렇게 하면 연속적으로 페이지 폴트를 발생시키면서 페이지를 메모리에 적재하고 어느정도 적재가 된 후 부터는

페이지 폴트 발생 빈도가 떨어진다

이렇게 아무 페이지도 없을 때부터 요구 페이징을 하는 경우를 순수 요구 페이징이라고 한다

 

요구 페이징 시스템의 안정적인 작동을 위해서는 페이지 교체와 프레임 할당이 필요하다

 

• 페이지 교체 알고리즘

 

페이지 폴트를 적게 일으키는 알고리즘이 좋은 페이지 교체 알고리즘

페이지 폴트 횟수는 페이지 참조열을 통해서 알 수 있다

CPU가 2 2 2 3 5 5 3 3 7 페이지에 접근한 경우 연속된 페이지가 아닌 새로운 페이지에 접근한 경우가 페이지 참조열이다

페이지 참조열 : 2 3 5 3 7

 

- FIFO 페이지 교체 알고리즘

 

페이지 프레임에 들어온 순서대로 교체된다

구현과 아이디어가 간단하지만 먼저 들어온 페이지가 중요한 경우일 수도 있으니 마냥 좋지는 않다

 

자주 참조되는 페이지가 쫒겨나는 부작용을 개선한 2차 기회 페이지 교체 알고리즘도 있다

가장 오래된 페이지의 참조 비트가 1(CPU가 접근한 적이 있는 페이지)이면 내쫒지 않고

참조 비트를 0으로 바꾸고 현재 시간을 적재 시간으로 만든다

가장 오래된 페이지의 참조 비트가 0이면 오래되고, 사용하지 않은 페이지라 생각해 쫒겨난다.

 

- 최적 페이지 교체 알고리즘

 

앞으로 오랫동안 사용되지 않을, 사용 빈도가 가장 낮은 페이지를 교체하는 방식

이론상 가장 효율적이지만 앞으로 오랫동안 사용되지 않을 페이지를 예측하는 건 거의 불가능하다

 

그러므로 최적 페이지 교체 알고리즘을 OS에서 사용하기 보다는 다른 페이지 교체 알고리즘의 이론상의 성능을 확인하기 위해서 사용된다

최적 페이지 교체 알고리즘에 비해서 다른 페이지 교체 알고리즘에서 얼마나 페이지 폴트가 일어났냐를 통해 페이지 교체 알고리즘을 평가

 

- LRU 페이지 교체 알고리즘

가장 오래 사용되지 않을 페이지를 예측하는게 불가능에 가깝지만

가장 오래 사용되지 않'은' 페이지를 교체하는 건 가능하다! 이게 LRU 알고리즘의 방식이다

최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것 이라는 개념으로

가장 오래 사용하지 않은 페이지를 교체한다