이전내용
컴퓨터의 메모리를 사용하려고 하는데, 여러개의 프로세스를 띄우고 싶다. 어떻게 하면 메모리를 효과적으로 잘 사용할 수 있을까??라고 해서 나온 것들이
fixed partitioning, variable partitioning, segmentation 이다.
process마다 momory를 일정 크기로 나누는 fixed partitioning을 사용했을때는, internal fragmentation이 생겼다.
그래서 그때그때마다 momory를 끌어다 주는 variable partitioning을 사용했고, 이 또한 반복하다 보니깐, 새로운 process가 사용하려고 하는 메모리를 사용하려고 하는데, 빈공간을 하나를 사용하기는 힘들고, 여러 빈공간을 합쳤을때는 가능한 메모리 크기이지만 메모리를 합칠 수 없어 사용하지 못하는 external fragmentation이 발생했다.
한 프로세스를 모아 놓지 말고 여러 군대에 퍼뜨려 놓는게 더 좋겠다 해서 나온게 segmentation 이었다. 그래도 external fragmentation이 하는 수 없이 발생했다.
이를 해결하기 위해 memory를 page 단위로 나눠서 linking해주는 paging을 사용하게 되었다.
logical page는 page 단위로 쪼개고, physical page는 frame 단위로 쪼개서 page table을 통해 맵핑해주는 방법이다.
address translation
virtaul address는 48bit, Physical Address는 36bit이다. 한 페이지의 사이즈는 16KB이다.
실제로 이 컴퓨터에 꽂을 수 있는 메모리의 최대 크기는 2^36 byte = 64GByte이다. 그리고, 이 페이지는 16KB이므로, 14bit면 표현할 수 있다.
그렇다면 VA에서 14bit는 offset으로 사용될 것이고, 나머지 34bit는 VPN으로 사용될 것이다.
그렇다면 PA에서는 14bit를 offset으로 사용하고 나머지 22bit는 PFN로 사용한다.
VPN이 page table을 통해 22bit의 PFN로 변환되어야 한다. 그러려면 page table entry 하나의 크기는 최소한 22bit 이상이어야 한다. 왜냐하면 22bit의 PFN을 나타낼 수 있어야 하기 때문이다.
page table entry의 개수는 VPN이 34bit이기 때문에 2^34개이다.
위 그림은 앞에 설명한 것과 숫자는 다르지만 어떻게 그림으로 나타낼 수 있는지 보여준다.
PTE(page table entry)
- valid bit은 PTE에서 VP가 PF 맵핑하고 있는지 확인시켜준다. 맵핑하고 있지 않다면 해당 PF는 비어있다.
- prot(Protection bit)은 맵핑되어 있는 PF가 read,write,excute중 뭐가 가능한지 알려준다.
Hierarchical page table
만약에 내가 쓰고 있는 일기가 있다. 1월에도 쓸것이고, 2월,3월... 쓰는데 못 쓴 달도 있다. 내가 언제 일기를 못쓰고 썼는지 관리하고 싶은데, 아무런 표시가 없으면 처음부터 다 뒤져봐야 알 수 있다. 만약에 4월달에 내가 쓴 일기를 보고 싶다면, 1월부터 4월이 나올때 까지 뒤져봐야 한다. 그래서, 표시를 해주었다. 1월은 10p, 2월은 40.p 3월은 70.p ... 이런식으로 표시를 해주었더니, 내가 보고 싶은 달을 찾을때 훨씬 빠르게 찾을 수 있게 되었다.
위의 address translation 파트에서 설명한것처럼, PFN이 22bit로 이루어진다면, PTE 하나의 크기도 22bit 이상이어야 하므로, 4MB이고 2^34개 만큼있다. 그러면 너무 큰 메모리 공간이 필요해지기 때문에 말이 안되는 숫자이다.
page table을 cpu가 찾아서 처리하게 하려면 메모리 상에 저장해야 하는데, 각 PTE는 메모리상에서 연속적으로 저장되어야 한다. 그래야 찾을 수가 있다.
그런데, 문제는 너무 큰 숫자의 용량을 차지 한다는 점이다. 메모리를 효율적으로 사용하기 위해서 page로 나눠서 여러군대에 나눠서 저장했는데, 이 page를 찾기위한 page table을 메모리에 연속적인 물리적 공간에 큰 용량을 차지하게 만드는것 자체가 사실 말이 안된다.
그래서 생각해 낸것이 Hierarchical page table이다.
이렇게 사용하면, physically continuous할 필요도 없다. 새로운 윗 계층의 page table이 찾고자 하는 page table의 위치를 포인팅만 하고 있으면 되므로, 메모리에 연속적으로 있을 필요가 없다.
frame 3, frame70이 있는 page table을 찾기위한 frame10을 만들면, frame 10만 찾으면 3,70으로 다가갈 수 있다. 이렇게 여러 레벨의 page table을 만들 수 있다.
인덱싱할 frame수가 많아진다 하면은 depth를 늘려주면 된다.
그렇다면, 어떻게 내가 원하는 frame으로 찾아갈 수 있을까??
bit를 이용한다.
한 level에 4개씩 묶여 있으므로, 2개의 비트만 보면 된다.
위 그림대로 찾는다고 하면, outer page table에서 10(2진수)을 찾고 0b10이후 비트를 찾아서 10(십진수)을 찾으면 된다.
위 그림은 한 레벨에 8개씩 묶여 있으므로, 3비트씩 보면 된다.
Hirarchical page table bit 정하는 법
hirarchical이 여러 계층으로 나눈다는건 알겠는데, 그럼 한 레벨의 PTE 수는 어떻게 정하는 걸까?
예를들어, virtaul page는 32bit physical page는 48bit라고 하자.
한 page의 크기는 4KB이다. 그렇다면, offset은 4KB = 2^12 이므로 12 bit이다.
PTE의 크기가 8byte라면, 4KB/8byte = 2^12/2^3 = 2^9이다. 따라서, VPN은 2^9개이고, 9bit씩 한레벨로 하면된다.
다시, virtual page로 가서, 총 32bit중 12bit는 offset, 9bit를 한레벨, 9bit 한레벨,나머지 2bit를 최상위 레벨로 한다. 그러면, 결과적으로, 최상위 level에는 2^2개의 PTE가 있고, 2^2개의 각각 PTE마다 그 밑에 2^9개의 PTE를 가리키고 2^9개의 각 PTE마다 또 ,그밑에 2^9개의 PTE를 갖는다.
장점
-
process가 사용하는 address space가 한쪽에 몰려있지 않고 듬성듬성 퍼져서 사용한다. 이걸 관리하기가 좋다.
-
physcial memory를 관리하기 쉽다. 비트맵을 통해서 해당 page를 사용하고 있는지 아닌지 표현할수 있다.
-
page table을 하드웨어로 구현하기가 쉬워진다.
page table address translation은 결국 프로그램이 돌면서 메모리를 참조해야 할때가 있을때마다 MMU(하드웨어)가 page table을 보고 내가 읽어야할 데이터가 physical memory 어디에 있는지 확인하고 translation 해서 데이터를 가져다 주는것이다.
우리가 프로그램을 짜서 돌리면 이 프로그램이 만들어내는 메모리 access가 MMU에 요청이 가고 MMU가 알아서 translation을 해준다.
단점
- linear page-table보다는 더 복잡하다.
