페이징(Paging) 기법들

본 내용은 학교 강의+반효경 교수님 강의를 통해 개인적으로 공부한 내용입니다. 책은 쉽게 배우는 운영체제(한빛 아카데미)를 참고했습니다. 조언은 언제든지 감사합니다 !

 

Two-Level Page Table

---

현대의 컴퓨터는 기본적으로 32 bit or 64 bit address를 사용하므로 address space가 매우 큰 프로그램을 지원한다.

만약 32 bit 아키텍처를 사용하는 컴퓨터라면 2^32 = 4GB 만큼의 주소 공간을 가지게 된다. 이를 page size가 4K인 page로 나누면 약 1M개(100,000,000)의 페이지로 나뉘어 진다. 그렇다면 logical address를 physical address로 주소 변환하는 매핑 정보를 담고 있는 page table의 entry 개수는 100만 개가 되어야 한다. (왜냐하면 page table은 기본적으로 index를 가지고 매핑하기 때문에 중간에 하나라도 빼먹으면 안됨)

32 bit 컴퓨터이므로 page entry 하나 당 32 bit 주소 체계를 가지게 되어 4B가 할당되므로, 프로세스당 4B x 1M = 4MB 크기의 page table을 가지게 된다. 그런데 이 page table은 프로그램이 메모리에 올라갈 때 physical memory에 할당된다. 따라서 physical memory의 주소 공간 낭비 문제가 발생하게 된다.

게다가 대부분의 프로그램은 주어진 4G의 주소 공간 중 지극히 일부분만 사용한다. 

윗 부분 (낮은 메모리 주소)을 text(code)와 data 영역으로 채우고 아랫 부분 (높은 메모리 주소)을 스택으로 사용해 가운데로 좁혀가는 방식인데, 위에서 주소 값을 보면 빈 공간이 상당히 큰 것을 알 수 있다. 하지만 위에서 말했듯이 page table은 이런 사용하지 않는 공간도 다 entry로 가지고 있어야 하므로 심하게 공간 낭비가 된다.

이러한 낭비 문제를 해결하기 위해 page table의 entry 정보를 가지고 있는 page table을 하나 더 만드는 기법이 Two-Level Page Table이다.

안쪽 page table (page of page table)은 원래의 page table (outer-page table)의 entry 1개를 각각 다시 page로 나눠 논 page table들을 가지고 있는 table이다. 즉 안쪽 page table 1개는 바깥쪽 table의 page 크기인 4KB의 크기를 갖게 된다. 또한 안쪽 page table 역시 entry의 크기는 4B일 것이므로 table 당 1K(1000)개의 entry를 가지게 된다.

이렇게 2개의 page table을 사용할 경우 속도는 줄어들지 않는다. 오히려 2번의 접근이 필요할 수 있으므로 늘어날 수 있다. 또한 table을 2개나 만들어야 하기 때문에 공간적으로도 손해같이 보인다. 하지만 사실 프로그램의 메모리는 위에서 말했듯이 상용하지 않는 공간이 많은데, 이 많은 공간들에 대해 바깥쪽 page table이 가리키는 안쪽 page table 값을 NULL로 설정해 줄 수 있다. 따라서 결과적으로 많은 메모리 공간 값들이 NULL을 가리키게 되어 page table을 사용하는 공간이 줄어들게 된다.

page의 크기가 4KB이므로 page 내부를 구분하기 위해서는 2^12 개의 bit가 필요하다. 그리고 안쪽 page table은 1K개의 entry를 가지고 있으므로 page table을 구분하기 위한 bit 수는 2^10 개다. 따라서 위와 같은 logical address 체계가 만들어 진다.

 

 

Multilevel Paging

---

address space가 더 커질경우 2단계 뿐만 아니라 다단계 페이지 테이블이 필요하게 된다.

문제는  주소 변환시 더 많은 메모리 접근이 필요하게 되어 소요 시간이 매우 길어진다는 점인데, 이를 TLB를 통해 해결할 수 있다.

TLB의 접근 시간은 매우 빠르므로 TLB의 hit ratio(적중률)을 높이면 빠른 시간내에 주소 변환도 할 수 있고 공간도 아낄 수 있다. 하지만 적중하지 못한다면 큰 시간적 손해를 보게 된다.

 

 

Valid/Invalid Bit & Protection in a Page Table

---

Valid/Invalid Bit

 

page table에 저장되어 있는 bit로 현재 프로세스에서 사용되고 있는 page일 경우 v로 표시(접근 허용)되고, 사용되고 있지 않으면 i로 표시(접근 불가)된다. (실제로는 0과 1로 저장)

예를들어 v로 표시되어 있는 entry는 0번 page가 2번 frame에 실제 올라가 있다는 것을 의미하고, i로 표시되어 있으면 6번 page는 프로세스에서 사용되지 않는 영역이거나, 아직은 사용되지 않고 backing store (swap area)에 저장되어 있는 경우다.

 

Protection bit

page에 대한 접근 권한을 지정하는 bit로 read/write/read-only 가 있다.

code 부분의 경우 내용이 바뀌지 않아야 하므로 read-only가 지정되어 있고, data나 stack 영역의 경우 read와 write 권한이 다 지정되어 있을 수 있다.

 

 

Inverted Page Table

---

page table의 가장 큰 문제는 모든 프로세스는 크기 만큼의 page table을 가져야 하고, 그 page table은 메모리 영역에 저장되어 공간이 낭비된다는 것이다. 이를 해결하기 위한 기법이다.

이 기법은 시스템 안에 page table이 딱 1개만 존재하고, entry가 프로세스 기준이 아닌 물리 메모리의 frame 개수만큼 존재한다.

따라서 위의 그림처럼 page table은 어떤 프로세스의 page인지 알 수 있는 pid(process ID)와 몇 번째 page인지의 p(page number)가 저장되어야 한다. 반대로 물리 메모리의 어느 위치에 저장되어야 하는 지는 frame의 index 정보로 알 수 있다. 

즉 주소 변환을 해야 할 경우 CPU는 논리 주소의 pid와 p와 맞는 entry를 찾기 위해 page table을 모두 서치한다. 찾았으면 찾은 index 정보를 가지고 frame 번호를 알아내어 pid와 p를 f로 바꿔준다. 여기서도 마찬가지로 page와 frame의 크기는 같으므로 d(distance = off set)는 그대로 가져간다.

공간적인 이득은 많이 보지만 처음에 index로 접근하는 것이 아니라 table의 모든 entry를 서치해야 하므로 시간적인 부분에서는 오버헤드가 발생할 수 있다. 따라서 associative register를 사용하여 병렬적으로 서치해야 한다.

 

 

Shared Page

---

몇몇의 프로세스들이 Shared code(Re-entrant code = Pure code)를 가질 경우 하나의 code 부분 page만 메모리에 올려 공유하는 방법이다.

예를들어 위의 P1, P2, P3는 ed1, ed2, ed3의 같은 code를 가지고 있는 page다. 따라서 ed1, ed2, ed3는 각각의 page table에 주소 변환이 3, 4, 6으로 동일하게 매핑되어 물리 메모리에 1개 씩만 올라간다.

이 공유되는 코드는 바뀌면 안되기 때문에 필수적으로 read-only되어 올라가야 한다. 그리고 CPU는 항상 logical address를 가지고 연산하기 때문에 각각 프로세스에 동일한 위치의 logical  address를 가져야 한다.