paging: Introduction

paging

paging은 base and bound, segmentation과는 달리 address space를 고정된 크기로 나눈다.

virtual memory(address space)의 이 고정된 크기의 한 단위를 page라고 하고, 이것을 실제로 가지고 있는 물리적 메모리에서는 slot, page frame, frame이라고 부른다.

 

왼쪽 그림과 같이 64 바이트의 address space를 addressing하려면 2^6 = 6비트가 필요하다. 

페이지가 4개로 나뉘기 때문에 상위 2비트는 virtual page number를 가리키고(VPN) 나머지 4비트는 한 페이지 내에서 addressing하는데에 사용된다.

 

또 virtual address가 오른쪽 그림같은 실제 물리적 메모리의 어디에 저장되는지를 알 수 있는 주소 변환 정보를 가져야한다.

그리고 이 주소 변환 정보를 가지고 주소변환을 진행하는데, 페이지 내에서의 거리는 바뀌지않으므로 offset은 그대로 오고 VPN > PFN의 과정에서만 변환이 일어난다.

mmu에서 1번 페이지는 7번 프레임으로 변환된다.

여기서 virtual address는 6비트로, physical address는 7비트로 표현되는 것은 단순히 생각해서 virtual address는 64바이트(2^6), physical address는 128바이트(2^7)의 크기를 가지고 있기 때문이다.

그런데 page와 frame의 크기는 같아야 하므로, physical address는 8개의 frame을 가져야 하는 것을 알 수 있다.

 

이렇게 paging을 사용하면 메모리를 고정된 크기로 나누어 할당하고 관리하기 때문에 메모리 관리가 굉장히 편해진다.

또한 각 page frame들간의 경계가 딱 붙어있으므로, external fragmentation이 존재하지 않는다. (internal fragmentation은 존재함.)

 

또한 각 page frame이 비었는지, 사용중인지를 1비트로 표현하고, 이것을 Bitmap이라고 한다.

위의 물리적 메모리 그림을 기준으로 하면 10110101이 된다. (physical memory의 사용상태를 표현)

이것을 통해서 비어있는 메모리를 찾고, 할당할 수 있다.

 

반면, direct indexing을 위해 address space는 연속된 공간이어야 하는데, 이것은 사실 가상공간에서 논리적으로만 연속적인 공간이면 된다. 실제 물리적 메모리에서는 꼭 같은 frame, 연속된 frame에 위치할 필요는 없다.

 

 

page table

paging을 할때 사용되는 주소변환정보는 page table로 만들어진다.

이 page table이 어디에 저장되는지, 이것을 구성하는 구성요소의 타입은 무엇인지 살펴보자.

 

page table은 프로세스의 주소를 변환하는 변환정보이므로 프로세스마다 각각의 page table이 존재하고,

오늘날 page의 개수는 매우 많아 mmu같은 단순한 하드웨어에 배치하기는 곤란하므로 page table의 실제 위치는 물리 메모리이다.

 

page table에서 virtual page number가 key가 되고, physical frame number가 value가 된다고 했을 때,

key값에 해당되는 부분을 순서대로 정렬해서, key값이 연속하고 정렬되어있게 되면 이것을 index로 대치가 가능하다.

즉 key는 사라지고(위치가 대신함) value값만 남아서 하나의 배열 table형태가 되는 것이다. (key값은 index가 대신함.)

 

그리고 이렇게 인덱스로 접근해서 값을 찾아갈 수 있는 것을 direct indexing이라고 하고, 이런 구조에서는 어떤 값에 접근하든지 그 정보를 찾는데에 걸리는 시간이 모두 동일하다.

위 페이지테이블의 한줄 한줄을 각각 page table entry라고 한다.

VPN은 인덱스로 대치되기 때문에 저장할 필요가 없고 PFN는 저장되어있다.

그리고 그림의 오른쪽에 보면 valid bit와 control bit(protect bit)들이 있는데, 이 각각의 비트에 따라서 해당 페이지들이 다르게 처리된다.

예를 들어, valid bit는 Sparse Address Space에서 사용하지 않는 페이지를 표현하기 위해서 사용하고

user만 사용하는지/supervisor도 사용하는지, 읽을수있는지/쓸수있는지, 등등을 control bit를 통해 나타낸다.

control bit (=protection bit) 

present bit : 해당 페이지가 디스크에 있는지 메모리에 있는지 표시한다.
>present bit(1) : 이 프레임에 내용이 들어있음
>present bit(0) : 이 프레임에 정보가 없음. page의 내용이 memory에 없는 경우. 이럴땐 swapping으로 가져와야한다.

dirty bit : 해당 페이지에 한번이라도 쓴적이 있는지 여부 (store명령을 통해 한번이라도 쓴적이 있는지)

reference bit : 해당 페이지에 접근한 적이 있는지 여부 (여기서 접근은 read/write를 말한다.)

 

 

그러면 paging에서 주소변환은 어떤 과정을 통해 일어날까?

(5번 라인) PTBR(page table의 시작 주소)에 VPN을 가지고 매핑하여 dirext indexing을 통해 PTE(page table entry)의 주소를 찾아내고,

 

(8번 라인) page table은 물리 메모리에 있으므로 메모리에 접근하여 PTE를 찾아온다.

그리고 그 PTE를 mmu가 읽어오는데, 그러면 mmu가 PTE의 내용을 분석하여 원하는 정보를 찾아낸다.

 

(11번 라인) PTE의 valid bit를 통해서 해당 페이지가 사용되고 있는지 아닌지 그 유효성을 검증하는데,

유효하지않으면(해당 페이지가 사용되고 있지 않으면) segmentation fault exception을 발생시켜 trap을 일으킨다.

 

(13번 라인) valid bit는 유효하지만 protect bit를 통해 검증했을때 접근(access)이 불가한 내용이 있으면 protection fault exception을 발생시켜 trap을 일으킨다.

 

(15번 라인) 문제가 없으면 offset mask와 virtual address를 통해 offset을 찾아내고, 그것을 이용해 physical address를 찾아내서 실제 물리적 메모리에 접근하게 된다.

 

mmu는 PTE(page table entry) 포맷을 읽을 수 있는 주소변환 전용 하드웨어로,
페이지의 시작주소를 가리키는 레지스터 PTBR를 가지고 있다.

 

그런데, 이러한 paging기법은 주소변환이 필요한 매 순간마다 물리적 메모리에 접근해서 찾아내야 하므로 느리다는 단점이 있다.

위와 같은 명령어를 처리한다고 생각해보자.

 

첫번째줄만 보더라도 명령어를 읽어오기 위해 명령어가 있는 주소를 알아내야 하므로 명령어 주소를 계산하기 위해 메모리에 접근하고,

명령어를 읽기 위해 또 메모리에 접근하고, 또 실제로 move명령을 통해 데이터를 변경해야 하므로 이를 위해 또 해당 레지스터에 대한 주소변환이 일어나고, 메모리 접근이 일어난다. (메모리에 4번 접근)

 

이렇게 명령어를 처리할 때마다 해당 명령어가 있는 페이지테이블을 읽어야 하고, 또 거기서 해당 명령어를 읽어야 하기 때문에 memory access 가 많이 필요하다는 것을 알 수 있다.

 

이런 단점은 TLB를 통해 크게 개선될 수 있는데, 다음 글에서 살펴보도록 하겠다.