Paging

Paging

이제 더 이상 physical address에서 프로세스들은 contiguous하지 않다. 지금부터는 물리적 메모리 공간을 고정된 사이즈 블록인 frame으로 나눌 것이다. 그리고 논리적 메모리 공간은 frame과 같은 크기를 가진 page로 나눌 것이다. 따라서 프로세스가 실행될 때 각각의 페이지들은 이용 가능한 frame에게 할당될 것이다.

이를 통해 우리는 외부 단편화 문제를 해결할 수 있지만, 여전히 내부 단편화 문제는 남아있다.

Page table

각각의 프로세스들은 논리적 주소를 물리적 주소에 매핑하기 위해 page table을 가지고 있다. page table은 page number와 page offset을 저장하는 두 가지 공간으로 나뉘어져 있다.

• Page Number
  : page number는 논리적 주소의 상위 비트 부분으로, page table의 인덱스로 사용되고 있다. 각 프로세스는 자신의 page table을 가지고 있으며, 테이블은 프로세스의 논리 주소를 물리 주소의 프레임으로 매핑한다. 즉, page table에서 page number에 해당하는 인덱스로 이동하면 매핑되어 있는 frame을 찾을 수 있는 것이다.

• Page Offset
  : page offset은 논리 주소의 하위 부분으로, 해당 page에서 특정 위치를 저장하고 있다. 따라서 page number에 page offset을 더하면 물리적 주소에서 해당 page의 특정 위치를 정확하게 찾을 수 있다.

logical address space가 32 bit ($2^m$, m = 32)의 크기를 가지고 있고, page size가 4 KB ($2^n$, n = 12)이라면, page number는 22bit를 저장할 수 있고, page offset은 10bit를 저장할 수 있다.

p = page number, d = page offset, f = frmae number

위의 다이어그램은 page table이 어떻게 frame과 매핑되는지 나타내고 있다. cpu는 논리적 주소의 p와 d 값을 확인하는데, p는 page number로써, page table의 인덱스이다. page table에서는 페이지가 매핑되어 있는 frame number를 함께 저장하고 있으며, frame number와 page offset을 이용해 물리적 주소의 정확한 위치를 찾을 수 있다. page와 frame은 같은 사이즈를 가지고 있기 때문에 page와 frame의 offset은 공유될 수 있다.

page numebr = 4 bit ( m = 6, n = 2 => m - n = 4 bit )
page offset = 2 bit ( page size = 4 bytes = $2^2$ => n = 2 )

page table을 확인해보면, page number가 인덱스를 나타내고, 인덱스마다 매핑되어 있는 frame number가 있음을 확인할 수 있다.

Translation Look - Aside Buffer

CPU가 데이터와 instruction에 접근하기 위해서는 어떤 경우에든 2번의 메모리 접근이 필요하다. logical address를 통해 page table에 한 번 접근하고, 실제 데이터와 instruction이 저장되어 있는 physical memory에 또 한번 접근해야 하기 때문이다.

따라서 CPU는 Tlanslation look - side buffer (이하, TLB)를 통해 메모리 액세스 시간을 줄이고자 한다. TLB란 기존에 접근했던 page table을 저장하는 하드웨어 캐시로, CPU는 우선 TLB에 방문해서 table page가 저장되어 있는지 확인한다. 이후, TLB에서 miss가 발생하면 그때, page table에 접근한다. TLB는 캐시 구조로서 빠른 액세스 타임을 가지고 있기 때문에 메모리 액세스 타임을 더욱 효과적으로 줄일 수 있다.

Memory Protection

• Protection bit
  : 각각의 frame이 read-only or read-write 인지를 나타내는 비트이다.

• Valid - Invalid Bit
  valid : page가 프로세스의 논리적 주소에 할당되어 있다는 의미이다. 즉, 정상적으로 page에 접근할 수 있다!
  Invalid : page가 프로세스의 논리 주소에 할당되어 있지 않다는 의미이다. 해당 page를 이용할 수 없다!

Page Table Structure

32 bit의 logical address space를 가지는 컴퓨터가 있다고 가정해보자.

• page의 사이즈는 4KB 이다. = $2^{12}$ bytes

• page table이 가질 수 있는 entry 공간 = ($2^{32} / 2^{12}$) = page 개수

• 각각의 entry가 4 bytes의 크기를 가질 때, 각각의 프로세스는 page table을 위해 4 MB 크기를 할당해야 한다.

physical address에 4 MB 크기의 page table을 프로세스마다 할당하는 것은 매우 비효율적이다!!!

따라서 일반적으로 page table을 어떤 구조로 활용하는지 알아보자!

Hierarchical Page Tables

Multi - Level Page Table 이라고도 불리는 hierarchical page table은 2개의 page table을 가지고 있는 것이 특징이다.

• Outer page table
  : outer page table은 pointer를 통해 inner page table을 가리킨다. 정확히 말하면 논리 주소의 상위 비트(page number)에 inner page table 인덱스를 저장하고 있다.

• Inner page table
  : inner page table에서는 논리 주소의 나머지 비트를 사용하여 실제 frame을 가리킨다.

Two - Level Paging

Logical address (on 32 bit machine with 4KB page size)

• a page number consisting of 20 bits
• a page offset consisting of 12 bits

page number가 20 bit를 저장할 수 있다면 two - level paging에서는 outer page와 inner page가 각각 10 bit를 자신의 page number로 사용한다.

그러므로,

위와 같은 그림이 완성되고,

위와 같은 방식으로 adrress translation이 이루어진다.

Hashed Page Table

hased page table의 기본 구조는 hash table이다. logical address는 hash function을 통해 하나의 hash 값을 가지며 hash table의 해당하는 해시 버켓에 담긴다. 동일한 hash 값을 갖는 page 들은 연결 리스트의 형태로 관리되며, 버킷 내에서 순차적 탐색을 통해 해당하는 page를 검색한다.

Inverted Page Table

Inverted page table은 page가 아니라 frame이 table의 인덱스가 된다.
따라서 table의 크기가 실제 메모리 용량과 비례하기 때문에 테이블에 필요한 메모리가 줄어든다. 각 엔트리에는 해당 frame에 저장된 프로세스 Id와 page number가 저장된다.

frmae index	pid	page num
frmae 0	-	-
frmae 1	5	3
frmae 2	5	1
frmae 3	-	-
frmae 4	1	2

frame이 인덱스가 되고 해당 엔트리에는 매핑된 프로세스 id와 page umber가 저장된다.

메모리 주소가 4GB이고 페이지 크기가 총 4KB이라면,
inverted page table에서는 총 $1024^2$개의 entry가 존재한다고 할 수 있다.