Beyond Physical Memory: Policies(2)+(3)

stack property

stack property란, 캐시사이즈가 n개일때 들어있는 내용이 캐시사이즈가 n+1개일때도(캐시사이즈를 늘렸을때도) 다 들어있는 성질이다.

optimal, LRU정책의 경우 stack property를 만족하기 때문에 캐시 사이즈가 늘어나면 hit ratio가 좋아진다.

반면, FIFO의 경우 stack property를 만족하지 않기 때문에 캐시사이즈를 늘렸을 때 오히려 성능이 나빠지기도 한다. (Belady's anomaly)

 

 

각 정책별 workload

optimal과 LRU는 locality에 따라 캐시를 교체하고, FIFO는 locality 고려 없이 무조건 오래된 캐시를 교체하고, random은 아무런 기준없이 랜덤하게 캐시를 교체한다.

이런 여러 정책별로 캐시사이즈를 0부터 100까지 늘려가며 access를 진행했을때  그 workload의 차이를 살펴보자.

locality가 전혀 없을 경우이다. 이 경우 LRU, FIFO, Random 정책은 동일하게 linear하게 증가한다. 캐시 크기에 비례하게 증가하는 것이다. optimal의 경우에만 미래를 예측할 수 있기 때문에 성능이 좀 더 잘 나온다.

 

다음은 80%의 레퍼런스가 20%의 페이지에 몰리게 해서 locality를 준 경우이다.

이때는 optimal, LRU, FIFO와 Random순으로 성능이 나타난다.

 

그런데 앞선 포스팅에서 언급했듯이 LRU에서는 Looping의 문제가 있다.

 

Looping이란 access pattern이 특정한 형태로 반복되는데(ex : 1,2,3,... 50. 다시 1,2,3,...50) 이때 캐시사이즈가 Loop를 받쳐주지 못할 경우 hit ratio가 0이 되는 현상이고, 특이한 점은 캐시사이즈가 점점 증가하다가 loop를 모두 담을 수 있게 되는 그 순간부터는 hit ratio가 갑자기 0에서 100으로 급증한다는 것이다.

 

Looping은 FIFO와 LRU 정책에서 발생하고,

그래프를 보면 이러한 Looping 상황에서도 optimal은 안정적이며, random 또한 생각보다 성능 측면에서 선방하는 것을 볼 수 있다.

 

 

Historical Algorithm

캐시 교체 기준을 정할때 과거를 반영하는 교체정책은 LRU이다. 이는 통상 linked list로 구현되는데, 실제 하드웨어 메모리 캐싱과정에서 이 linked list를 사용하는 것은 매우 느리고 비효율적이다.

 

따라서 하드웨어에 의해 page frame별 time stamp(메모리에 접근하는 시간)를 기록하게 하고, 이후에 페이지 교체가 일어날 때 운영체제가 이 Page frame들을 스캔해서 time stamp가 가장 빠른것을 찾아내는 방법을 사용할 수 있다.

 

그런데 이런 방법을 쓰더라도 오늘날의 컴퓨터처럼 메모리가 아주 큰 경우, page의 frame 역시 매우 많아져서 교체할 페이지를 찾기 위한 시간이 매우 오래 걸린다는 한계를 극복하기는 어렵다.

 

그래서 다른 생각을 하게된다.

가장 오래된 것이 아닌 '적당히' 오래된 것을 찾으면 어떨까?

이런 아이디어에서 LRU보다는 못하지만 FIFO보다는 나은 성능의 clock algorithm이 등장하게 된다.

 

이런 아이디어에서 clock algorithm이 등장하게 된다.

clock algorithm은 oldest가 아닌 old를 찾아내는, 한마디로 LRU를 approximate하는 방법이다.

 

 

Clock algorithm

clock algorithm에서는 하드웨어적인 support가 필요하다. 

LRU의 경우 time stamp를 필요로 하는 것과 달리 clock algorithm에서는 use bit, dirty bit를 사용한다.

 

1. use bit(reference bit)

use bit는 해당 페이지가 접근된적이 있는지를 표시하는 비트이다. (load, store, 프로그램 코드가 fetch되는 등..)

페이지가 reference될때 0에서 1로 바꾸는 과정은 하드웨어에 의해 일어나고, 이것이 다시 0으로 초기화되는 과정은 운영체제에 의해 일어난다. (mmu하드웨어에 use bit가 있는 일반적인 경우)

1. use bit가 mmu하드웨어에 있다면 (일반적인 케이스)

clock algorithm은 소프트웨어적으로 실행된다.
0>1로 세팅하는 것은 하드웨어가 한다. 그리고 use bit를 리셋하는 것은 software가 하고,

2. use bit가 mmu하드웨어에 없다면

use bit를 1로 세팅하고 0으로 리셋하는 일을 모두 software(OS kernel)가 한다.

그런데 use bit가 언제 0으로 초기화되는지는 clock algorithm의 진행과정을 살펴봐야 알 수 있다.

원형의 physical memory에서 page fault로 인해 교체가 일어나야 할 때

next frame을 가리키는 포인터, 즉 clock hand는 각 프레임을 빙빙 돌며 use bit=0인 교체 대상 프레임을 찾고자 한다.

page fault가 자주 일어날수록 clock hand 바늘이 도는 속도는 더욱 빨라진다.

(이 경우 clock algorithm이 FIFO기반으로 진행되었지만 물론 random정책을 사용할 수도 있고, 그럴 경우 clock hand가 frame을 무작위로 가리킨다.)

 

그런데 이렇게 돌면서 use bit=1인 프레임을 만날 경우엔 교체 대상이 아니어서 교체는 못하지만 use bit=0으로 clear하고 지나간다.

즉, cloch hand가 지나갈 때, 1이었던 use bit가 0이 되는 것이다.

 

지금 당장은 use bit=1인 프레임을 교체할 수 없지만 한바퀴를 돌고 다음에 돌아왔을때는 교체할 수 있도록 만들어주는 과정인데, 한바퀴를 도는 사이에 다시 해당페이지가 접근되어서 use bit가 다시 1로 변하면 또 지울 수 없게 된다.

이렇게 clock algorithm을 사용하면 LRU와 비슷한 성능을 더 효율적인 방법으로 만들어낼 수 있다.

 

2. dirty bit(modified bit)

dirty bit는 store명령을 통해 메모리 프레임에 한번이라도 값을 썼는지를 보여주는 비트이다.

만약 페이지 교체 과정에서 이렇게 dirty한 페이지가 교체 대상 페이지로 선택되었다면 이를 교체할때 그 변경내용을

하드디스크에 다시 써줘야 한다.

 

그런데 그 과정에서는 dist io가 사용되어서 교체를 빠르게 할 수가 없다.

따라서 dirty page는 되도록이면 교체 대상으로 삼지 않고, 교체시에 disk io요청이 필요없는 clean page가 우선 교체 대상이 된다.

교체대상 결정 순위
1순위 : use bit=0 & dirty bit=0
1순위 : use bit=0 & dirty bit=1

 

 

N'th chance algorithm

clock algorithm을 한층 더 정교하게 만든 방법으로, n번째 기회를 준다고 하여 이렇게 부른다.

 

page fault가 나면 clock algorithm과 동일하게 clock hand가 frame들을 탐색하는데,

만약 use bit=1이라면 0으로 clear해주고 이때 count값도 0으로 초기화해준다.

반면 use bit=0이라면 이를 바로 교체해주지 않고 count값을 증가시킨다. 

그리고 이후에 이 count값이 N에 도달하면 그때 교체한다.

 

즉, 기회를 더 부여하는 것이다. (use bit=0, count=N일때 교체)

 

N값이 크면 LRU에 더 근사해지지만 효율성은 다소 떨어지는 반면, N값이 작으면 매우 효율적이다.

때문에 이 N값을 효과적으로 사용하기 위해서 일반적으로는 clean page와 dirty page의 N값을 다르게 준다.

clean page : N=1
dirty page : N=2

 

 

clock algorithm에서 사용되는 PTE entry bit

clock algorithm에서 유용하게 쓰이는 PTE의 bit들은 다음과 같다.

 

use bit(reference bit)	해당 페이지 접근 여부
dirty bit(modified bit)	해당 페이지 값 변경 여부 (store)
valid bit	해당 페이지 유효 여부
read only	해당 페이지에 대한 접근 권한 여부 (protection bit)

 

그런데 만약 dirty bit나 use bit가 하드웨어적으로 없다면 소프트웨어적으로 이를 어떻게 보완할 수 있을까?

우선 mmu가 하드웨어적으로 바라보는 page table과 운영체제가 소프트웨어적으로 처리하는 보조적인 page table의 분리가 필요하다.

이것을 전제로 각 케이스를 살펴보기로 하자.

 

1. use bit(=reference bit)가 하드웨어에 없을 경우 (VAX의 운영체제인 VMS)

일단 mmu가 바라보는 page table의 모든 페이지의 valid bit=0으로 두어서 모든 PTE가 invalid한것처럼 mmu를 속인다.
mmu가 사용하는 page table에 의도적으로 가짜 정보를 넣어두는 것이다.

반면 운영체제(os kernel)가 소프트웨어적으로 처리하는 page table에는 진짜 정보, 즉 실제 valid bit를 넣어둔다.

따라서 처음 mmu가 해당 PTE에 접근하면 trap이 발생하고, OS kernel로 진입하게 된다.

그러면 OS kernel이 자신이 관리하는 별도의 page table을 보고 진짜 valid bit를 확인한다.
그런데 실제로는 valid해서 문제가 없으면 지금 해당 페이지에 접근하려고 했다는 뜻이므로 use bit=1로 세팅한다.

그리고 이제는 use bit의 값이 세팅되었으므로, mmu가 보는 page table의 valid bit도 valid로 바꿔준다.

이렇게 use bit를 처리하고 나면 이제 dirty bit를 기록하기 위해 mmu가 보는 page table의 모든 protection bit를 readonly로 둔다. (mmu를 한번 더 속임)

 

2. dirty bit(=modified bit)가 하드웨어에 없을 경우 (BSD unix사용)

mmu가 바라보는 page table의 모든 페이지의 protection bit를 무조건 readOnly로 세팅하여 mmu를 속인다.

따라서 cpu에서 실행하는 명령어가 load일 경우에는 문제가 없지만, 만약 store명령을 실행하려고 할 경우 mmu가 바라보는 page table의 protection bit가 readOnly이므로 trap이 발생하여 OS kernel로 진입한다.

그러면 OS kernel이 자신이 관리하는 별도의 page table을 보고 진짜 protection bit를 확인한다.
그런데 알고보니 실제 protection bit는 writable로, 문제가 없는 상황이라면 지금 값을 바꾸려 했다는 뜻이므로 dirty bit=1로 세팅한다.

그리고 이제는 dirty bit의 값이 세팅되어서 mmu를 더이상 속일 필요가 없으므로, mmu가 보는 page table의 protection bit도 read+write로 바꿔준다.

 

 

use bit, modified bit가 초기화되는 시점

1. use bit

clock hand가 지나갈때 초기화됨.

이때 mmu가 바라보는 page table entry의 valid bit 역시, 다시 invalid로 바꿔줘야 함.

 

2. modified bit

해당 페이지가 disk로 기록되어 dirty>clean한 페이지가 될 때 초기화됨.

그리고 disk로 기록된 해당 페이지가 다시 메모리로 돌아올때, protection bit를 다시 readOnly로 바꿔줘야 함.

 

 

other VM policies

1. prefetching

prefetching은 compulsory miss를 최대한 피하려는 정책으로, spatial locality를 이용한다.

특정 구간이 access되면 그 주변 구간 역시 access될 가능성이 높으므로,

페이지가 하드디스크에서 메모리로 캐싱될 때 그 근처의 여러 페이지를 묶어 한번에 캐싱한다.

 

2. clustering, grouping

메모리에서 하드디스크로 write요청을 할 때,여러 페이지를 묶어서 한번에 write하는 방식이다.

이 정책을 사용하면 한번의 write요청으로 굉장히 많은 양을 하드디스크에 쓸 수 있게 된다.

 

 

Thrashing

physical memory는 모자라는데 process가 굉장히 많아서 발생하는 현상으로,

context switching이 계속 일어나서 page fault + swapping만 반복적으로 일어나는 상황을 말한다.

이렇게 되면 cpu는 거의 안쓰고, page fault로 인한 Disk IO 작업만 계속해서 수행되기 때문에 cpu 성능에 심각한 저하가 생긴다.

 

이런 thrashing을 어떻게 피할 수 있을까?

thrashing의 원인은 과도한 multi programming에 있다.

과도하게 많은 프로세스가 함께 실행되면서 physical memory가 이것을 버틸 수 없게 되는 것이다.

따라서 동시에 메모리에 올라가는 프로세스의 개수를 적당히 조절해야 한다.

 

그러면 어떻게 메모리에 올라가는 프로세스 개수를 조절할까? 그 해결책은 working set model이다.

working set을 만들어 실행시간에 따라 달라지는 "메모리에서 사용되는 페이지 집합"을 정의한다.

실행시간에 따라 메모리에 올라와있는 page들

특정한 시간(구간)을 working set window로 정의하고,

그 working set window안에 들어온 page들의 집합을 working set이라고 한다.

ws(process i) = 프로세스 i를 위한 working set. 

그런데 working set window(Δ)를 정할때, Δ가 너무 작으면 충분한 locality를 담을 수 없고, Δ가 너무 크면 여러개의 locality를 담게 되므로 Δ는 적당해야 한다.

 

결국 multi programming을 할 때, 우리는 각 프로세스들의 working set을 모두 더한 D를 알 수 있기 때문에

이것이 memory frame의 크기(M)를 넘지 않도록 관리해야 한다. (프로세스들의 working set들이 적당히 나누어서 실행되도록 함.)

D>M이면 Thrashing이 발생하기 때문이다.