demand paging
process를 memory에 적재할 때 처음부터 모든 page를 적재하지 않고 필요한 page만을 memory에 적재하도록 하는 기법을 말한다.
기본적인 양상은 아래와 같다.
1. CPU가 특정 page에 접근하는 명령어를 실행
2. 해당 page가 현재 memory에 있을 경우 CPU는 page가 적재된 frame에 접근
3. 해당 page가 현재 memory에 없을 경우 page fault가 발생
4. page fault 처리 routine은 해당 page를 memory로 적재하고 유효 bit를 1로 설정
4. 다시 1번을 수행
아무런 page도 memory에 적재하지 않은 상태로 실행도 가능한데 이 경우 page fault가 계속 발생하게 되고 어느정도 적재된 이후 점점 page fault 발생 빈도가 줄어들게 된다.
이를 pure demand paging이라 부른다.
위와 같은 요구사항들을 해결하기 위해서는 page 교체, frame 할당 2가지를 해결해야 한다.
요구 페이징을 처리하여 memory에 page를 적재하다 보면 언젠가 memory가 가득 차게 되고, 당장 실행할 page를 적재하기 위해 memory에 적재된 page를 보조기억장치로 내보내야 한다.
이를 결정하는 방법을 page 교체 알고리즘이라고 한다.
page 교체 알고리즘
한 알고리즘을 통해 page 교체를 했을때, 너무 자주 page fault가 일어난다면 좋은 알고리즘이라고 할 수 없다.
-
FIFO
가장 단순하게 memory에 먼저 올라온 page를 먼저 swap하는 방식으로 가장 오래된 page부터 교체하는 방식이다.
구현은 단순하나 단점이 확실하다.비슷한 방식으로 2차 기회 방식도 있다.
FIFO와 유사하나 1번의 기회를 더 주는 방식의 알고리즘이며 CPU가 한번이라도 참조했었다면 유효 bit를 다시 0으로 만들기만 하고 교체하지는 않는다.
만약 bit가 0이며 오래 머물렀다면 이는 사용하지 않는 page라고 판단할 수 있고 이를 교체하면 된다. -
optional page replacement
CPU에 의해 참조되는 횟수를 고려하는 page 교체 알고리즘
사용 빈도가 가장 낮은 알고리즘으로 가장 낮은 page fault율을 보장하지만 구현이 어렵다.
주로 다른 page 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용되는 방식이다. -
LRU
optional page replacement 알고리즘을 조금 변형한 가장 오래 사용되지 않은 page를 교체하기 위한 방식이다.
외에도 여러 방식이 존재하나 기본적인 idea에 의한 파생이기 때문에 대표적인 것의 idea를 이해하는게 중요하다.
thrashing과 frame 할당
사실 page fault는 page replacement 외에도 frame 수가 적은데에 더 큰 이유를 갖고 있다.
frame 수가 많으면 일반적으로 page fault 빈도가 감소하고 CPU의 이용률도 높아진다고 볼 수 있다.
이처럼 process가 실행 시간보다 paging에 더 많은 시간을 소요하여 성능이 저해되는 문제를 thrashing이라 한다.
memory와 동시에 실행되는 process의 수를 degree of multiprogramming이라고 하는데 정도가 낮을수록 현재 memory에는 적은 process가 실행중이라고 할 수 있다.
thrashing이 일어나는 근본적인 원인은 process가 필요로 하는 최소한의 frame 수가 보장되지 않기 때문이다.
이를 보장하기 위해서는 process에 적절한 frame을 할당할 수 있어야 하는데 이를 위한 frame 할당 방식부터 생각해봐야 한다.
- equal allocation
권장할만한 방법은 아니다.
각 process의 크기는 천차만별이고 동일한 frame을 전달한다고 하면 비 합리적이라고 할 수 있다. - proportional allocation
process의 크기별로 frame을 할당하는 방식
크기가 큰 process에게 더 많은 frame을 할당하고 크기가 작은 process에게 더 적은 frame을 할당한다.
정적 할당 방식이라고도 부른다.
process를 실행하는 과정에서 배분할 frame을 결정하는 방식에 대해서는 아래 2가지가 있다.
-
working set model
CPU가 어떤 process를 실행하는 동안 몇개의 process를 집중적으로 참조했다면 OS는 그 process를 위해 그 순간만큼은 최소한만 할당하는 방식이다.
process가 일정 시간동안 참조한 page의 집합을 working set이라고 하고 CPU가 과거에 주로 참조한 page를 working set에 포함한다면 OS는 working set만큼만 frame을 할당하면 된다. -
PFF(page fault frequency)
page fault의 빈도를 기반으로 비율이 너무 높으면 너무 적은 frame을, 너무 낮으면 너무 큰 frame을 가진것으로 판단하고 frame을 더 지급하거나 회수하도록 한다.
