[Operating System/운영체제][Working set page replacement algorithm, WSClock page replacement algorithm]

 

 

 

 

 

 

지난 시간에 이어서 마지막인 Working set page replacement algorithm과

WSClock page replacement algorithm에 대해서 알아보도록 하겠습니다.

 

 

 

 

 

 

 

The Working Set Page Replacement Algorithm

 

 

 

 

 

Working Set Page Replacement Algorithm은 Locality 개념을 기반으로 한 페이지 교체 알고리즘입니다. 프로세스가 실행되는 동안 자주 사용되는 페이지 집합을 유지하여 page fault를 줄이는 것을 목표로 합니다.

간단히 말해, 프로세스가 일정 시간 동안 활성 상태로 유지하는 페이지들의 집합을 Working Set이라고 합니다.

 

 

working set의 정의는 $\text{W(k , t)}$로 나타낼 수 있습니다.

 

만약에 k를 4개로 잡게 되면 아래와 같은 순서로 page를 참조한다고 했을 때,

 

 $\text{W(k , t) = 4, 5, 6}$이 됩니다.  

 

만약 k 값이 커진다면 어떻게 될까요?

 

 

 

 

 

k 값이 커질수록 Working Set에 포함되는 페이지의 수가 늘어나게 됩니다.
극단적으로 k 값을 매우 크게 설정하면, 모든 페이지가 Working Set에 포함됩니다.

 

그러나 k 값을 너무 크게 설정하면 문제가 발생할 수 있습니다.
Working Set의 크기가 커지면 불필요한 페이지까지 메모리에 남게 되어 메모리 낭비가 발생하게 됩니다.

또한 오래된 페이지가 포함되면 Locality를 벗어나기 때문에 페이지 폴트를 줄이는 데 도움이 되지 않습니다.

 

 

 

 

 

 

Working Set page Replacement Algorithm의 동작 원리

 

 

 

 

 

 

이제 working set에 대한 정의와 기본적인 내용을 알게 되었습니다.

본론으로 돌아가서 working set page replacement algorithm을 살펴보자면,

 

 

위에서 말한 것과 같이 만약에 오래되고 참조되지 않은 page는 교체되어야 합니다.

왜냐하면 필요없는 page까지 메모리에 남아있다면 당연히 메모리를 낭비하는 것이기 때문입니다.

 

이제 오래된 page들을 걸러내야 하는데, 걸러내기 위해서 사용하는 개념이 window zise를 이용한 것 입니다.

 

window size의 기본적인 개념을 이야기 하자면,

 

실제 구현에서는 K 참조 대신, 시가늘 사용하여 Working set을 근사합니다.

여기서 메모리 참조 횟수 대신 시간을 기준으로 페이지 집합을 정의하는데,

프로세스가 CPU를 사용하는 시간(Virtual time)을 기준으로, 최근$\tau$초 동안

참조된 페이지들의 집합을 working set으로 정의하게 됩니다.

 

 

여기서 "왜 참조 수 대신 시간을 사용하지?" 라는 의문이 드실 수 있는데, 

 

 

메모리 참조 수는 프로그램의 참조 패턴에 따라 다를 수 있기 때문입니다.

어떤 프로그램은 짧은 시간에 많은 메모리를 참조할 수 있고, 어떤 프로그램은 긴 시간동안

적은 메모리를 참조할 수 도 있기 때문에 참조 패턴이 다르게 되는 것 입니다.

 

 

본론으로 돌아가서, $\tau$안에 들어오는 page들을 working set으로 지정하고,

page fault가 일어났을 때 time of last use라는 추가된 field에 virtual time을 설정하고 난 이후에

$\tau$바깥에 있다면 page가 working set 바깥에 있다고 가정해서 교체하게 됩니다.

만약에 $\tau$안에 들어와 있다면 working set안에 들어와 있다고 간주해서 건너띄게 됩니다.

 

 

또한 clock interrupt마다 R bit = 1이라면, interrupt된 virtual time을 기록하게 됩니다.

 

 

위 두 가지 기본 사항을 가지고 아래의 time of last use를 보고 page를 교체하는 과정을 살펴보면,

 

 

 

current virtual time인 2204를 기준으로 R bit과 함께 비교하면서 교체해주는 것 입니다.

 

page table에서 2032를 보자면 R bit = 1이기 때문에 current virtual time인 2204로 교체해줍니다.

이렇게 교체해주는 것은 clock interrupt일 때에도 마찬가지 입니다.

 

  그렇다면 만약에 1620과 같이 R bit = 0인 상태에서는 어떻게 해야 할까요?

 

 

 

 

 

위의 사진 오른쪽에 나와있는 것을 그림으로 표현해서 설명해보자면,

우선 clock interrupt나 fault가 발생했을 때, R bit = 0일 때에는 아래의 경우를 따릅니다.

current virtual time과 기존 time of last use를 빼주고 난 이후에 $\tau$와 비교해주게 됩니다.

만약에 빼준 값이 $\tau$보다 커서 위에 2204-1213(age)과 같이 범위를 나가게 된다면 교체해주게 됩니다.

 

그렇다면 빼준값이 $\tau$의 범위 안에 들어오는 값이라면 어떻게 될까요?

 

$\tau$범위 안에 들어왔다는 것은 working set에 들어가는 page라고 생각하게 되어 교체하지 않게 됩니다.

이렇게 time of last use를 교체해주는 것은 하나가 교체되었다고 끝나는 것이 아니라 전체를 다 확인해줍니다.

 

 

만약에 전체를 다 살펴보고 난 이후에 또 다시 clock interrupt나 page fault가 발생하게 되면,

모두 R bit = 0인 page들의 age를 비교해주고 age가 가장 큰 page를 교체해주게 됩니다.

 

결국에 모든 page의 R bit=1이 되면 이때는 어쩔 수 없이 Random하게 page를 교체하게 됩니다.

여기서 Random하게 page를 교체하지만 가능하면 clean page라고 m bit = 0인 page로 교체하는것이 좋습니다.

 

 

위의 방법을 사용하면 entry가 너무 많기 때문에 효율성이 떨어진다는 단점이 있습니다.

단점을 보완하기 위해서 page frame를 circular linked list로 만든 이후에 적용해주는 방법인

WSClock page replacement algorithm에 대해서 배워보겠습니다.

 

 

 

 

 

 

 

The WSClock Page Replacement Algorithm

 

 

 

 

 

 

 

 

우선 동작을 살펴보자면,

앞에서 R bit = 1이라면 time of last use를 기록해줬고, 여기서도 똑같이 기록을 해줍니다.

여기서 다른 점은 기록하고 R bit을 바꾸지 않았는데 여기서는 R bit = 0으로 설정해주게 됩니다.

 

 

R bit = 0이라면 여기 또한 위와 같이 $\tau$와 비교해주게 됩니다.

$\tau$ 작게 되면 다음 entry로 전진한 이후에 정지합니다, 만약 $\tau$보다 크게 되면 교체해주게 됩니다.

 

 

여기서는 교체 해줄 때 조금 특이한 점이 있는데, page가 clean하게 되면 replace하게 됩니다.

만약에 해당 page가 dirty라면 교체해줄 때 I/O를 발생시켜서 Disk에 써주게 됩니다.

하지만 이 시간이 오래 걸리기 때문에 여기서는 나중에 처리해주기 위해서 scheduling해주게 됩니다.

queue에 request를 걸어주고 시간이 남을 때 Disk에 써주는 I/O를 queue에서 가져와서 처리하게 됩니다.

 

 

여기서 조금 정리를 하자면, WSClock replacement algorithm과 working set page replacement algorithm은

서로 유사하게 진행됩니다. 여기서 차이점은 위에서 말했던 교체해줄 때 I/O를 scheduling한다는 것과

working set page replacement algorithm은 time of last use를 바꿔주면 모든 entry를 확인하기 위해서 이동하게 되는데

WSClock replacement algorithm에서는 다음 entry로만 이동한 이후에 멈추고 그 다음에 page fault나 clock interrupt가

발생했을 때, 멈춘 entry부터 시작하게 된다는 차이점이 있습니다.

 

 

WSClock page replacement algorithm은 working set page replacement algorithm과 많은 부분에서 유사하기 때문에

차이점을 보시고 넘어가시면 될 것 같습니다.

 

 

 

마지막으로 지금까지 배워본 page replacement algorithm은 아래 그림의 표에 정리되어 있습니다.

각 algorithm을 보면서 어떤 것을 배워봤는지 간략하게 체크해보고 넘어가시면 됩니다.

 

 

 

---

 

 

 

 

지금까지 paging 기법에 대해서 살펴보고 단점을 보완하기 위해서 TLB라는 기법을 살펴보고 난 이후에,

page를 교체하기 위해서 최선의 방법을 선택하기 위한 algorithm들을 지금까지 살펴봤습니다.

 

 

 

뒤에 paging에 대해서 살짝 남은 부분들과 더불어서 memory management part의 나머지를 살펴보겠습니다.