Operating Systems 9. Main Memory - (2)

 

Structure of the Page Table

32비트 논리주소 공간이라고 가정하자.

page 크기 가 4KB (2^12) 라면, 

page table 은 2^32 / 2^12 인 2^20 , 1 million 개의 page를 가질 수 있다. (entries 개수) 

여기서 각 entry 크기가 4byte 라면, page table 의 크기는 2^20 * 4B = 2^22 -> 4MB 이 될 것이다.

이는 매우 큰 크기이므로 , 여러 페이지 테이블 구조가 등장하게 된다.

 

 

Hierachical Paging 

Multilevel Paging 이란 페이지 테이블이 계층 구조를 갖는 것이다. 

즉, page table 을 하나의 연속적 메모리로 사용하지 않고 여러 개의 조각으로 나누어서 계층적으로 구현하는 것이다.

 

 

 

Two-Level Page-Table Scheme

page table 자체가 paging 되는 것을 말한다. 

outer page table 이 있고, 이곳에 있는 값을 통해 page table 이 있는 곳으로 접근 해야 한다.

 

원래의 logical address 는 p(page number) 과 d(offset) 으로 구분되었다. 그러나 two-level paging example 에서는 

p가 2개의 레벨로 쪼개져서 p1, p2, d 로 구분된다.

 

예를 들어, 32-bit CPU 에서 page size가 1KB(2^10) 라고 하자.

원래의 논리 주소는 page number (p) 가 22bit , page offset (d) 가 10bit 를 차지할 것이다.

그러나 two-level Paging 에서는 page number 을 다시 쪼개어, 

p1(page-page number) = 12bit, p2 = 10bit(page-page offset), d = 10bit(page offset) 로 구성할 수 있다.

이때 p2 의 길이가 10bit 라는 것은, page of page table 의 entry 개수가 2^10 개라는 것을 뜻한다.

각 칸마다 4byte 를 가진다면 2^10 x 4 = 4k !!

하나의 page table 만 사용하였을 때는 4MB 였던 것이 page size 하나의 크기로 줄어들었다.

 

만약 64-bit CPU 로 two-level 을 사용한다면 어떨지 살펴보자. 

page size 는 4KB (2^12) 이고, Page table 은 2^52 개의 entry 를 가질 수 있다.

마찬가지로 p2 를 10bit 로 할당한다면, p1 은 64 - 12 - 12 = 42 bit 이다.

즉, p1(outer page table) 은 2^42 개의 entry 를 가질 것이다.

한 칸당 4byte 라고 가정한다면, page table 의 크기는 2^42 x 4byte = 2^44 byte 로 엄청 큰 사이즈를 가지게 되며, physical memory 까지 총 3번의 메모리 접근이 필요하다.

 

 

3-level 이라면 어떨까? 

p1 은 2^32 개의 entry 를 가지고, page table 의 크기는 2^32 x 4 = 2^32 byte 를 가지게 된다. 또한, physical memory 까지 총 4번의 메모리 접근이 필요하다.

 

level 이 깊어지면 엔트리 개수는 줄어들어 메모리 size는 작아지지만, 그 만큼 검색시간이 많아지고, 메모리 접근 시간이 길어지므로, 실제로 사용하기 힘들다.

 

 

Hashed Page Table

논리주소의 page number 의 hash function 값을 hash page table 의 index 로 사용한다.

hash table 의 각 엔트리는 linked list 구조로 이루어져 있으며, 같은 hash function 값을 가지는 페이지들의 paging 정보를 저장해 둔다.

연결리스트 원소 형식은 <page number, 매핑되는 page frame 값,  다음 pointer> 이다.

page table 의 각 entry 가 여러 page 에 대한 주소 변환 정보를 저장하기 때문에, 공간 크기는 작지만 탐색 시간은 길어질 수도 있다.

 

 

Inverted Page Table

프로세스 별로 따로 가지고 있던 page table 을 합치는 방법으로, <pid, p> 의 쌍으로 이루어진 단 하나의 page table 만이 존재하게 된다.

Page Table의 Entry가 프로세스의 페이지 개수만큼이 아니라 물리적인 메모리의 Page Frame 개수만큼 존재한다. 그리고 첫 번째 Entry는 물리적인 메모리의 첫 번째 Frame을 나타내고, 두 번째 Entry는 두 번째 Frame을 나타내는 방식이다. 

 

page table 에서 pid 가 일치하는 것이 있는지 검색하고, i번째 entry 에서 발견된다면 물리주소는      <i, d(offset)> 이 되고, 그렇지 않으면 잘못된 접근이다. 

메모리에서 훨씬 작은 공간을 차지하지만, 주소 변환의 시간이 증가하고, search time 이 증가하므로 성능이 좋지 않음을 알 수 있다. 

 

 

Swapping

프로세스를 메모리에서 일시적으로 disk 로 내보내고, 다시 실행하고자 할 때에 메모리로 불러오는 것을 swapping 이라고 한다. 이는 제한된 메모리를 사용하기 위함이다.

 

swap in 은 메모리로 다시 불러오는 것, swap out 은 메모리에서 내보내는 것을 의미한다.

Compile, Load time 때 binding 되었던 process 는 다시 올라올 때 같은 위치에 binding 되어야 한다는 번거로움이 있다.

그러나 대부분은 execution time 때 binding 되는 프로세스이므로, swap in 될 때 이전과 다른 비어있는 공간에 바인딩 될 수 있다. 

 

 

Context Switch Time including Swapping

만약, 다음에 실행되야 할 프로세스가 메모리에 없고, 현재 여유 메모리 공간이 없다면, 메모리에 있는 한 프로세스를 내보내고(swap out) 실행되야 할 프로세스를 메모리로 불러와야(swap in) 한다.

이런 context switching 과 swapping 이 같이 일어나는 경우엔 많은 시간이 소요된다. 

 

 

swapping 에는 제약조건이 있을 수도 있다. 

실행되고 있는 I/O (Pending I/O) 는 swap out 을 할 수 없다. 

또한, double buffering 을 통해 swap 될 수 있다. 이는 운영체제 buffer 을 통해 입출력 연산을 수행하는 것으로, 서로의 buffer 에 써주기만 하면 된다.

 

 

 

Swapping on Mobile Systems

모바일 시스템은 대체로 swapping 을 지원하지 않는다. 하드 디스크 대신에 플래시 메모리를 사용하기 때문에, 공간에 제약이 있으며 쓰기 횟수에 제한이 있다.

swapipng 을 사용하더라도 read only(읽기 전용 - code 영역, data X) 또는 백업이 필요하지 않은 것만 swap out 한다.

 

 

Intel 32 and 64-bit Architectures

segment 와 page 모두를 지원한다.

 

Arm Architecture

모바일 플랫폼에서 사용되는 구조로, two level 의 TLB 를 지원한다. 이때 section 과 page 의 단위를 구분하여 사용하는데, page 의 경우 two level, section 의 경우 1 level 로 사용한다.