[Operating System/운영체제][Inverted page table, Page replacement algorithm]

 

 

 

 

 

 

 

 

 

Inverted page table

 

 

 

 

 

 

 

지난 시간에 multilevel page table에 대해서 배워봤습니다.

multilevel page table을 사용해도 되는데 Inverted page table은 왜 사용할까요?

 

 

Inverted page table은 모든 프로세스가 공유하는 단일 테이블을 사용하고 이 방식으로 인해서

프로세스별로 개별적인 페이지 테이블을 가지고 있는 일반적인 방법과 다르게 메모리 사용량이 크게 줄어드는 것 입니다.

 

쉽게 생각해보면, 일반적으로는 프로세스의 모든 가상 페이지에 대한 엔트리를 page table이 가지고 있지만,

Inverted page table은 각 physical page마다 하나의 엔트리만 유지하기 때문에 메모리를 적게 사용한다는 것 입니다.

 

 

 

 

 

 

 

Inverted page table은 위와 같은 구조를 가지고 있습니다.

 

 

여기서 특이한 점은 virtual address에 다른 방식과는 다르게 pid를 가지고 있다는 것 입니다.

pid와 p인 virtual page number의 index를 가지고 page table을 서칭하면서 매칭되는 주소를 찾는다면 

i(Frame number)를 가지고와서 page offset과 합쳐서(concat) physical address를 얻게 됩니다.

 

 

 

여기서 이미 눈치채셨을 수도 있지만, Inverted page table의 단점은 

 

일반적인 page table에서는 virtual page number가 나오면 index로 access를 했습니다. 찾아가야 할 entry의 address가 바로 계산이 됐지만,  Inverted page table은 어느 entry에 있는지 모르기 때문에 전체를 다 서치해서 frame number인 i를 찾아야 합니다.

 

page table을 전체 다 찾아봐야 하기 때문에 만약 정보가 맨 뒤에 있다면 

엄청 많은 시간이 걸릴 수 있다는 단점이 있습니다.

 

여기서 page table을 다 봤을 때 정보가 없다면 당연히 page fault가 발생합니다.

 

그렇다면 page table을 전체 다 서치해야 하는 문제는 어떻게 해결할 수 있을까요?

 

여기서도 마찬가지로 TLB를 사용하게 됩니다.

 

그럼 이전에 배웠던 것 처럼 "TLB miss가 발생하면 어떻게 처리해야 할까?"

라는 질문까지 이어지게 됩니다. 이 부분을 해결하기 위해서 hash table이라는 것을 사용합니다.

 

 

 

 

 

 

pid와 virtual page number가 나오면 이를 hash function( h(pid, vpn) )에 넣어주면 index값을 내보내게 되고

여기서 나온 index를 가지고 그림에 보여지는 node에 access를 하게 되고 만약에 index에 해당하는 node가 있다면

node 안에 기록되어 있는 page frame number를 가지고 physical memory에 접근하면 됩니다.

 

 

hash를 사용할 때 항상 발생하는 문제로 collision문제가 발생하는데,

서로 다른 가상 페이지가 동일한 해시 entry를 가질 때 발생하게 됩니다.

 

원래 hash collision이 발생하면 open addressing이나 linked list를 사용하지 않으면 해당 항목을

hash table에 저장할 수 없기 때문에 그림에서는 linked list 방법을 이용한 해법을 적용한 것 입니다.

 

 

hash function을 이용해서 hash table을 찾아봤을 때 해당 entry에 node가 없다면

Frame에 assign이 안되었다는 것이고 page fault가 일어나게 됩니다.

 

 

page가 fault가 발생한 상태에서 page table에서 하나의 공간을 만들기 위해서

replace를 수행해줘야 합니다. replace에도 어떻게 하느냐에 따라서 overhead가 줄어들기도 하고

늘어나기도 하기 때문에 replace를 최적화 하기 위한 algorithm이 존재하게 됩니다.

 

 

 

 

 

 

 

page replacement algorithm

 

 

 

 

 

 

 

우선 page fault가 발생했을 때 교체하는 방법에 대해서 짚고 넘어가겠습니다.

 

프로세스가 특정 가상 메모리 주소의 페이지를 참조합니다.

만약에 TLB나 hash table이 있다면 해당 테이블을 참고한 이후에 Page table을 확인하고,

TLB와 hash table이 없다면 page table을 참고하게 됩니다.

 

TLB와 hash table miss가 발생하게 되면 page table을 확인하고,

TLB와 hash table이 없다면 page table을 확인한 이후에 valid bit이 0으로 설정되어 있으면 해당 페이지는

메모리에 없음을 나타내며 page fault가 발생하게 됩니다.

 

page fault는 운영체제가 가상 메모리를 관리하면서 page를 Disk에서 memory로 불러올 필요가 있을 때 발생하게 됩니다.

이렇게 page fault가 발생해서 Disk에서 하나의 page 가지고 오는 것을 demand paging이라고 부릅니다.

 

여기서 page를 Disk에서 가지고 올 때 확인해줘야 할 것이 있습니다. modify bit(or dirty bit)을 확인하고

만약에 modify bit = 1(dirty)이라면 Disk에 해당 주소의 Data를 바꿔주고,

modify bit $\neq$ 1 (clean)이라면 새로 가져온 페이지에 overwrite하기만 하면 됩니다.

한마디로 딱히 다른 무언가를 해줄 필요가 없습니다.

 

 

만약 page fault가 발생해서 Disk에서 해당 page를 가지고 올 때, memory가 꽉 차게 된다면 어떻게 될까요?

 

 

memory에 빈 공간을 만들어 주기 위해서 page replacement를 해야하는데

빈 공간을 아무 생각없이 아무 page나 내보내고 만든다면 당연히 page fault rate를 고려하지 않았기 때문에

해당 page가 다시 fault가 발생하고 또 Disk에 가서 memory로 page를 가지고 와야 하기 때문에

CPU는 대부분의 시간을 교체하는 작업에 할애하게 됩니다. 여기서 빈번한 page fault로 인해서

시스템 성능이 급격히 저하되는 것을 Thrashing이라고 부르며

Thrashing을 피하기 위해서 효율적인 page replacement algorithm이 필요하게 됩니다.

 

 

 

 

 

 

 

Belady's Algorithm (Optimal Algorithm)

 

 

 

 

 

 

 

Belady's algorithm의 기본 아이디어는 가장 오랜기간 동안 미래에 사용되지 않을 page를 replace하는 것 입니다.

이렇게 오랫동안 사용되지 않을 페이지를 선택하여 교체함으로써 page fault rate를 최소화하는 것 입니다.

이 알고리즘에서 문제가 되는 것은 미래에 자주 사용되지 않을 page를 알기 어렵다는 것 입니다.

그렇기 때문에 이론적인 최적 알고리즘 입니다.

 

교체가 되는 순서는 위의 그림을 따라가 보시면 되고, 마지막에 AED가 page frame에 들어와 있을 때 부터

그 다음에 D 그리고 마지막 C가 miss로 교체될 때 그 다음에는 page fault가 발생하는 경우가 없기 때문에

어떤 순서로든 바꿔줘도 상관이 없게 됩니다.

 

 

 

 

 

 

 

NRU(Not Recently Used Page Replacement Algorithm)

 

 

 

 

 

NRU는 페이지의 최근 사용 여부와 수정 여부에 따라서 교체할 페이지를 선택하는 알고리즘입니다.

 

R bit(Referenced bit)은 페이지가 읽기나 쓰기 작업으로 참조될 때 하드웨어에 의해서 설정됩니다.

또한 R bit은 운영체제의 시계 인터럽트 주기마다 초기화되기 때문에 페이지가 최근에 참조되었는지 아닌지를 알 수 있습니다.

 

 

M bit(modify bit or dirty bit)은 페이지가 쓰기 작업에 의해 수정되었을 때 설정되며,

M bit은 운영체제가 page fault로 인해서 page가 메모리에서 교체되기 전에 디스크에 써야 하는지를 판단하는 bit입니다.

 

 

위의 R bit과 M bit의 조합으로 4개의 class로 분류가 가능하며, 이를 통해서 작동하게 됩니다.

 

class 1: (0, 0) (최근에 참조되지도 않았고 수정되지도 않음)

class 2: (0, 1) (최근에 참조되지도 않았지만 수정됨)

class 3: (1, 0) (최근에 참조되었고 수정되지는 않음)

class 4: (1, 1) (최근에 참조되었고 수정됨)

 

 

 

 

 

페이지를 교체할 때에는 위의 class로 우선순위를 나누며 가장 낮은 클래스의 페이지를 선택해서 교체합니다.

위에서 제일 우선순위가 낮은 것은 class 0 이고 우선 순위가 가장 높은 것은 class 4입니다.

 

 

 

 

 

 

 

 

FIFO

 

 

 

 

우선 FIFO알고리즘의 장점에 대해서 이야기 하자면 개념이 쉽고 구현하기가 쉽다는 장점이 있습니다.

단점으로는 가장 오래된 페이지를 교체 대상으로 선택하지만, 그 페이지가 자주 사용될 수도 있다는 것 입니다.

 

 

 

 

 

위의 그림을 보면 확실히 Optimal한 것과 비교해 봤을 때 FIFO는 해당 stream에서

더 많은 fault를 발생시키게 되고 많은 오버헤드를 가지게 됩니다.

 

 

 

 

 

 

 

page frame을 늘리더라도 page fault ratio가 반드시 줄어든다는 보장은 없습니다.

여기서 사용되는 이론이 Belady's anomaly입니다. 페이지를 늘리면 page fault ratio가 내려갈 것이라고 생각하기 쉽지만

실제로 늘려서 사용해보면 꼭 그렇지만도 않다는 것 입니다.

 

 

 

 

 

 

 

 

Second Chance Page Replacement Algorithm

 

 

 

 

 

 

Second chance algorithm은 FIFO 알고리즘을 개선한 페이지 교체 기법입니다.

 

FIFO의 단점 중에서 오래된 페이지가 여전히 사용 중임에도 불구하고 교체될 수 있다는 점이 있는데

Second chance algorithm은 이 문제를 해결하기 위해 페이지의 R bit을 사용하여 교체할 페이지를

선택하기 전에 한 번 더 기회를 준다는 것 입니다. 

 

R bit이 0인 경우, modify bit을 확인하고 dirty 상태라면 Disk에 기록하고 그렇지 않다면 바로 제거합니다.

 

R bit이 1인 경우, 최근에 참조된 것으로 간주되어 교체되지 않고 리스트의 끝 부분으로 이동시키고

R bit은 0으로 초기화하고 그 다음 페이지를 확인합니다.

 

 

그렇다면 만약에 모든 페이지의 R bit이 1인 경우에는 어떻게 될까요?

 

 

모든 페이지가 참조된 적이 있다면, R bit가 0이 될 때 까지 리스트를 한 번 순회하고 난 이후에

FIFO본래의 방식으로 교체를 진행하게 됩니다.

 

 

FIFO 알고리즘을 보완하기 위해서 만들어진 만큼 FIFO에 의해 교체될 페이지가

최근에 참조되었다면 또 참조될 가능성이 있기 때문에 한 번의 기회를 더 줘서 교체를 피할 수 있고,

불필요한 교체로 발생하는 오버헤드를 방지할 수 있게 됩니다.

 

하지만 모든 page list를 순회해야 하는 과정에서 오버헤드가 발생할 수 있습니다.

 

여기서 순회하는 오버헤드를 줄이기 위한 방법으로 아래에서 배울 Clock algorithm으로 발전합니다.

 

 

 

 

 

 

 

 

Clock page Replacement Algorithm

 

 

 

 

 

 

Clock algorithm은 Second Chance algorithm의 순회하는 오버헤드와 node를 움직일 때 발생하는 오버헤드를

해결하기 위해서 고안된 방법으로 circular linked list의 형태를 가진 알고리즘입니다.

 

 

 

 

 

해당 형태를 가지고 있으며 시계바늘이 움직이며 교체할 페이지를 선택하는 역할을 합니다.

처음부터 끝까지 순회할 필요 없이 포인터를 사용해 효율적으로 순회할 수 있습니다.

시계바늘이 가르키는 페이지의 R bit을 체크하며 교체할지 기회를 줄지는

위의 Second Chance algorithm과 똑같이 동작합니다.

 

 

 

 

 

 

 

LRU(Least Recently Used)

 

 

 

 

 

LRU는 많이 들어보신 알고리즘이실 것이라고 생각됩니다.

페이지 교체 시 가장 오래 전에 사용된 페이지를 교체하는 알고리즘입니다.

가장 오래 전에 사용된 페이지를 교체하는 이유는 가장 오래 참조되지 않은 페이지가 앞으로도

사용될 가능성이 적다는 가정을 토대로 이루어집니다.

 

 

LRU 알고리즘에는 구현 방법이 여러가지가 있는데, linked lis, counter 기반, 행렬 기반 하드웨어 구현이 있습니다.

 

또한 여기에 LRU의 완전한 구현을 시뮬레이션하거나 보완하기 위해서 개발된 NFU(Not Frequently Used)와

LFU(Least Frequently Used) 그리고 Aging algorithm이 있습니다.

 

 

NFU 알고리즘은 페이지가 메모리에 얼마나 참조되었는지를 기반으로 페이지를 교체합니다.

각 페이지에 카운터를 두고 특정 간격(clock interrupt)마다 R bit을 해당 페이지의 카운터에 추가하고

페이지를 교체할 때 가장 작은 카운터 값을 가진 페이지가 교체 대상이 됩니다.

 

단점으로는 참조횟수는 기록해도 최근에 참조한 것인지 여부는 반영하지 못해서 문제가 발생할 수 있습니다.

 

 

 

LFU 알고리즘은 NFU와 유사하지만 페이지가 지속적으로 가장 적게 참조된 페이지를 교체하는 방식입니다.

LFU은 누적된 참조 빈도를 기준으로 하고 최근 참조 여부보다는 전체 참조 빈도를 더 반영하는 알고리즘으로

단점은 NFU와 마찬가지로 시간이 지나면 처음에 자주 사용된 페이지가 그대로 남아있을 수 있기 때문에

최근 사용 정보가 반영되지 않는 문제가 발생할 수 있습니다.

 

 

Aging 알고리즘은 LRU를 소프트웨어적으로 근사하기 위한 알고리즘으로 페이지의 참조 기록을 비트 시프트 방식으로 관리합니다.

 

 

 

 

주기적으로 각 페이지의 카운터를 오른쪽으로 1bit 씩 시프트 하고 참조 비트를 카운터의 가장 왼쪽 비트에 추가합니다.

 

이 과정은 최근에 참조된 페이지는 카운터의 MSB가 1로 기록되고

페이지를 교체할 때에는 가장 낮은 카운터 값을 가진 페이지가 교체 대상이 되게 됩니다.

 

 

 

시간 순서에 따라 최근 참조 여부를 기반으로 페이지 교체를 수행하기 때문에 LRU와 가까운 동작을 보이지만

clock tick(clock interrupt)내에서 여러 번 참조된 페이지의 순서를 구분할 수 없기 때문에 정확한 LRU가 아닙니다.

 

또한 bit 수가 제한되기 때문에 정밀도가 떨어질 수 있다는 단점도 있을 수 있습니다.

 

 

 

 

 

---

 

 

 

아직 모든 알고리즘을 살펴보지 않았기 때문에 다음에는 나머지 알고리즘에 대해서 추가적으로 알아보도록 하겠습니다.

 

 

 

글 봐주셔서 감사합니다.