[OS]Inverted Page Table

모든 process는 page table을 가지고 있다.

 

page table을 다시 복기해보면 virtual address 가 physical memory의 어디에 있는지 알려주는 table이다.

이렇게 Process 마다 page table을 만들게 되면 process가 많아질 수록 table 수도 많아지고 그럼 메모리 사용량도 많아지게 될 것이다.

또한 invalid한 page 마저 가지고 있게 되며 memory issue가 발생하는 것을 지금까지 확인했다.

 

그렇다면 반대로 physical memory에 직접 어떤 process가 사용하는지에 대한 정보를 저장하는 것이 효율적이지 않을까? 라는 아이디어에서 나온 방법이 Inverted Page table이다.

 

inverted page table의 방법은 다음과 같다.

 

실제 Physical memory의 page 개수에 맞는 table을 하나만 만들고 각 table entry에 virtual address, process 정보들을 저장하는 것이다.(One entry for each real page of memory)

 

기존 logical address 는 VPN+ OFFSET이었다면

inverted page table address 는 PID + Page number + OFFSET로 저장이 된다.

pid+p 를 이용하여 table에서 탐색을 하고 frame number로 바꾸어 준다.

이러한 방식의 단점은 table의 page개수가 많아질 수록 search 시간이 매우 길어진다는 단점이 있는데

이는 hash table을 이용한 탐색으로 줄일 수가 있을 것이다.

 

예를 들어보자,

physical memory 크기가 1MB = 2^20 B라고 하고 page 크기를 1KB = 2^10B라고 한다면

table entry개수는 2^10개가 필요하게 된다.

 

이때 entry 하나의 크기를 4 바이트라고 한다면 4KB의 page table이 되게 된다.