20. Demand Paging

 

 

virtual memory management는 디멘드 페이징(Demand paging)을 합니다. 디멘드 페이징은 위와 같은 4가지 정책(policy)을 따릅니다. page selection은 페이지 폴트가 발생했을 때 요청된 페이지만 읽어오는 것이 아니라 locality를 생각해 주변에 있는 페이지까지 읽어오는 것을 고려합니다.

 

page replacement는 새로운 페이지를 메모리에 적재할 때 메인 메모리에 사용할 수 있는 페이지 프레임이 없다면 다른 프로세스의 페이지를 뺏어와야 하는데 수많은 페이지 프레임에서 어떤 것을 뺏어올지 결정해줍니다. page frame allocation은 같은 page frame pool에서 페이지 프레임을 할당하는 global allocation을 할지 아니면 프로세스마다 가용한 페이지 프레임을 미리 결정하고 거기서 독립적으로 할당할지 결정합니다.

 

local page frame allocation은 프로세스에게 줄 수 있는 페이지 프레임의 수를 static하게 고정시킬지 아니면 dynamic하게 키울지 결정합니다. 이 4가지 정책들에 대해서 배울 것인데 이 중 가장 중요한 것은 page frame replcement 입니다.

 

 

 

프로세스가 페이지 폴트를 유발해야만 그 페이지를 읽어오는 방식으로 진행하면 성능상의 패널티가 발생합니다. prepaging은 페이지를 읽어올 때 sequential하게 액세스되니 한꺼번에 여러 페이지를 읽어오는 것입니다. 그래서 한 페이지가 요청이 되었을 때 함께 읽어들일 페이지를 몇 개로 정할 것인지를 설정해야 합니다.

 

 

 

request paging은 어떤 페이지가 요구되면 그 페이지가 속하는 그룹의 페이지를 전부 읽어오는 것입니다. 페이지를 그룹으로 묶어두고 그룹 내에 액세스가 발생하면 그룹 전체를 읽어들이는 것입니다. (과거의 방식, 프로그래머가 페이징 그룹을 전부 설정해야하는 불편함이 있음)

 

이렇게 page selection policy중 하나를 선택하거나 몇 가지를 선택해서 동작 방식을 설정합니다. 

 

 

 

OPT는 페이지 프레임을 뺏을 때 가장 먼 미래에 액세스될 페이지를 쫓아내는 방법으로 가장 이상적인 기법이지만 구현이 불가능합니다. (성능을 비교할 때 사용, optimal solution에 얼마나 가까운지) Random은 말 그대로 기준이 없이 페이지 프레임을 뺏어오게 됩니다.

 

 

 

FIFO는 메인 메모리에 들어온지 가장 오래된 페이지를 쫓아냅니다. FIFO는 프로세스 스케줄링과 다르게 메모리에서는 좋은 성능을 내지 못합니다. 부팅을 할 때 시스템을 관리하기 위해서 들어온 페이지들이 들어온지 오래됐다고 쫓아내면 문제가 생기게 됩니다. 

 

LRU는 OPT를 근사하여 구현한 것으로 가장 먼 미래에 사용될 페이지를 알 수 없으니 가장 오래전에 액세스된 페이지를 replace하는 방법입니다. 이건 locality와 연관이 있습니다. locality 안에 있는 페이지라면 오랫동안 사용되지 않을리 없으니 페이지 프레임을 뺏어오는 것입니다. (현재 사용 중인 프로세스의 프로그램이 아니라 다른 프로세스의 프로그램인 것을 제거)

 

 

 

FIFO 알고리즘은 문제가 있다고 했지만 실제로는 자주 사용이 됩니다. FIFO 알고리즘 자체로는 단점이 많지만 단점을 상쇄시킬 수 있는 메커니즘을 사용한다면 FIFO 알고리즘은 좋은 성능을 보여줍니다. (구현하기 쉽다는 장점도 있음)

 

VAX VMS OS에서는 page replacement에서 FIFO 알고리즘을 사용할 때 local page allocation을 같이 사용했습니다. local page allocation는 프로세스 단위로 그 프로세스가 메인 메모리에 가질 수 있는 페이지의 개수를 다 고정시킵니다. 이렇게 메인 메모리에 가지고 있는 페이지들의 집합을 resident set이라고 부릅니다.

 

이 resident set안에 페이지들이 FIFO 형식으로 정렬되어 있습니다. 그래서 프로세스의 페이지들 중 들어온지 가장 오래된 것이 큐의 제일 앞에 있게 됩니다. 그러면 이 front에 있는 페이지가 밀려나게 되는데 밀려난 페이지는 free page list로 이동하게 됩니다. free page list도 FIFO 형식으로 관리가 됩니다. (resident set list는 프로세스마다 존재하는 FIFO list이고 free page list는 글로벌하게 하나만 존재하는 FIFO list)

 

 

 

이렇게 설정을 하면 밀려난 가장 오래된 페이지는 free page list에 맨 뒤로 이동하여 오랫동안 남아있게 되는데 나중에 다른 프로세스에서 액세스하게 되면 다시 resident set list의 맨 뒤로 올라오게 됩니다. 시스템 전역적으로 free page list가 time buffer 역할을 해주는 것입니다. FIFO 알고리즘으로 사라질 수 있는 페이지를 유예하는 것

 

 

 

이와 같은 방식을 hybrid FIFO LRU 기법이라고 부릅니다. LRU가 붙은 이유는 global free page list에서 레퍼런스 되면 다시 부활하는 메커니즘이 LRU와 비슷하기 때문입니다. 이 기능을 구현하기 위해서는 software emulation을 사용해야 합니다. software emulation을 이해하기 위해서는 page table entry에 있는 reference bit을 알아야 합니다.

 

reference bit은 어떤 프로세스가 페이지에 액세스하면 켜지는 bit로 0이라면 리셋된 이후로 한번도 액세스되지 않은 entry라는 것을 의미합니다. 이 bit가 있어야 free page list에 있는 페이지가 액세스 되었는지 아닌지를 알 수 있습니다.

 

이를 통해서 페이지가 액세스 될 때 resident set에 있는 페이지인지 free page list에 있는 페이지인지 구별을 하여 전자라면 그냥 address translation을 진행하고 후자라면 address translation을 중지하고 free page list에서 resident set으로 옮기는 작업을 합니다.

 

VAX VMS OS에서는 reference bit를 지원하지 않기 때문에 emulation을 해줘야 합니다. resident set에 있는 페이지들이 액세스 될 때는 valid bit를 다 켜놓고 정상적으로 동작하게 합니다. 그러다 오래된 페이지가 global free page list로 쫓겨난다면 그 페이지의 valid bit를 0으로 바꿉니다. (free page list도 메인 메모리에 있기 때문에 valid 지만 여기서는 0으로 바꿈)

 

나중에 프로세스가 쫓겨난 페이지를 refer하게 되면 valid bit가 꺼져있기 때문에 페이지 폴트가 발생하고 페이지 폴트 핸들러가 메인 메모리에 있지 않아서 valid bit이 꺼진 건지 아니면 fake하게 꺼진 것인지 구별합니다. 이를 통해서 free list에 강제로 쫓겨난 것이라면 resident set으로 이동을 시킵니다.

 

 

 

reference bit를 하드웨어적으로 제공해준다면 문제가 없지만 제공해주지 않는 경우가 굉장히 많습니다. 이런 문제는 소프트웨어적으로 reference bit를 지원함으로써 해결이 가능합니다. 소프트웨어로 구현하던지 하드웨어적으로 지원하던지, reference bit는 1bit 플래그로 한 번 켜지면 계속 켜져있는 상태가 지속됩니다.

 

계속 켜져있으면 카운트를 할 수 없기 때문에 OS가 주기적으로 0으로 리셋해줘야 합니다. 이렇게 bit를 끄거나 킬 때 조심해야 하는 부분이 존재합니다. 메인 메모리의 page table entry에도 reference bit가 있지만 TLB에도 reference bit가 존재한다는 점입니다. 그래서 TLB도 업데이트를 해줘야 합니다.

 

만약 reference bit가 변경된다면 page table entry를 변경하고 TLB도 해당 정보를 flush시켜야 합니다. 하지만 TLB의 한 entry만 flush할 수 없기 때문에 전체 entry를 flush 해야합니다.

 

 

 

LRU 알고리즘은 액세스된지 제일 오래된 페이지를 쫓아냅니다. 때문에 제일 오래된 페이지를 구별하는 방법이 필요하게 됩니다. reference 빈번하게 일어나므로 reference가 될때마다 체크를 하는 것은 이런 정보를 기록하는 레지스터가 존재해야 하기 때문에 실행하기 힘든 방법입니다.

 

 

 

위와 같은 이유로 LRU를 직접 구현하는 것은 굉장히 어려운 일입니다. 그래서 대부분의 경우 LRU를 approximation합니다. reference bit를 두고 1로 증가시키는 방법을 사용하는데 이 방법은 카운트할 수 없기 때문에 얼마나 여러 번 reference된 페이지인지 알 수 없습니다. 또한 reference bit이 계속 켜져있다면 어느 시점에 켜졌는지 알 수 없기 때문에 주기적으로 clear합니다.

 

reference bit이 clear된 시점부터 지금까지 reference bit이 0이라면, 한 번도 사용된 적이 없는 것이고 1이라면 한 번이라도 사용된 페이지라는 걸 알 수 있습니다. 이를 통해 reference bit이 0일때 페이지를 쫓아낸다면 LRU와 비슷한 동작을 진행할 수 있습니다. 

 

 

 

과거에는 reference byte라던지 counter를 통해서 횟수를 샌다던지 이런 추가적인 reference 정보를 담을려고 했지만 어떤 페이지가 여러 프로세스에 의해서 공유되면 reference 정보들이 제 역할을 하지 못하게 되기 때문에 실용성이 없는 접근이였습니다.

 

 

 

실제로 가장 많이 사용되는 LRU approxmation은 unix OS에서 사용되던 BSD 계열의 클락 알고리즘입니다. 컴퓨터 피지컬 메모리에 있는 페이지 프레임들에 대해서 제일 낮은 주소부터 높은 주소까지 번호를 다 매길 수 있을 겁니다. 이 번호를 매긴 page frame array들이 존재할 때 제일 낮은 프레임과 제일 높은 프레임을 연결한다면 서클이 만들어 집니다.

 

 

 

위 사진에서 오른쪽에 있는 서클을 클락 알고리즘이라고 부릅니다. 이 프레임 서클에는 하나의 clock hand가 존재하며 이 clock hand가 current frame을 가르키게 됩니다. 이제 동작에 대해서 자세히 알아보겠습니다.

 

새로운 프레임에 대한 요청이 들어오면 clock hand가 가르키는 페이지 프레임을 얻어 오려합니다. 이때 이 페이지 프레임은 한번도 reference되지 않은 경우에만 얻어 오게 됩니다. 만약 reference 된 적이 있어 reference bit가 1이라면 clock hand가 이 bit를 0으로 바꾸고 다음 페이지 프레임으로 이동하게 됩니다. (1을 0으로 바꾸는 이유는 이전에 참조된 페이지로 1번 기회를 주는 것, 0인 페이지만 교체)

 

만약 모든 페이지들의 reference bit가 1이라면 clock hand는 한 바퀴를 돌아서 제일 첫 장소로 온 다음 해당 페이지 프레임을 제공해주게 됩니다. 이렇게 한 바퀴를 돌게 된다면 이 메인 메모리는 over commit 되었다고 이야기 할 수 잇습니다. 너무 경합이 심하기 때문에 FIFO와 같이 동작하게 됩니다. (프로세스가 특정한 페이지 몇 개만을 사용하는데 여기서는 너무 많은 페이지를 사용하는 것)

 

 

 

이런 클락 알고리즘을 조금 더 변형한 기법으로 page replace를 할 때 reference bit가 0이면서 clean page를 먼저 할당하는 기법이 존재합니다. 이런 방법은 Enhanced clock 알고리즘이라고 합니다. 클락 알고리즘을 관찰하면 컴퓨터 시스템의 메인 메모리가 얼마나 utilize 되고 있는지 또는 경합이 많이 발생하는지를 clock hand의 회전수로 파악할 수 있습니다.

 

경합이 심하게 일어나게 되면 page replace가 자주 일어나는 것이고 이 때문에 페이지를 액세스 할려면 매번 디스크를 갔다와야 하는 문제가 발생합니다. replacement가 너무 자주 일어나는 것을 thrashing이라고 부릅니다. 이런 thrashing 문제를 해결하기 위한 기법으로 working set 이 존재합니다.

 

 

 

page allocation 기법 중 global allocation의 경우 구현하기 쉽고 페이지를 적절히 utilize 할 수 있지만 한 프로세스가 너무 많이 사용할 수 있는 fairness 문제가 발생할 수 있습니다. 이런 문제를 해결하기 위해서는 프로세스당 할당 받을 수 있는 페이지 프레임의 개수를 고정시켜서 localize하면 됩니다. 

 

이 방법을 Pre-process allocation 이라고 부릅니다. per-process allocation이나 local allocation도 할당할 페이지 프레임 개수를 너무 작게 예측하면 swapping이 많이 발생할 수도 있고 너무 많이 할당하여 불필요한 페이지도 메모리에 올려둘 수 있습니다.

 

Per-job allocation은 동일한 속성을 가지는 프로세스들을 job으로 묶은 다음 프로세스들끼리 페이지 프레임을 할당하는 기법입니다.