페이징(Paging)과 페이지 테이블(Page table)

페이징과 페이지 테이블은 현대 운영체제 메모리 관련 컨셉에서 아주 중요한 것이므로 잘 정리해두자!

 

 

1. 페이징(Paging)

 

address space를 연속적으로 할당하지 말고, 페이지라는 단위로 쪼개서 사용하는 것이다.

 

먼저, 프로세스의 메모리를 page 단위로 자르고, 실제 physical 메모리도 page 단위로 쪼갠다. 이 때 쪼개진 physical memory를 page나 page frame이라고 부른다.

 

paging

 

그리고 Virtual address의 프레임을 Physical 메모리의 프레임으로 mapping 하는 방법이다.

 

이렇게 paging으로 메모리를 관리하면, external fragmentation이 발생하지 않는다. 물론 internal fragmentation은 발생할 수 있지만, 치명적인 정도는 아니라서 괜찮다.

 

 

 

2. 페이지 테이블(Page table)

 

앞서 VPN(Virtual Page Number)를 PFN(Pysical Frame Number)로 매핑해준다고 했다. 이 때 매핑해주는 표가 page table이다.

 

각각의 프로세스는 자신만의 page table을 독립적으로 가지고 있으며, 각 프로세스의 page table이 저장되어 있는 주소를 page table base register가 저장하고 있다.

 

page table은 OS로부터 관리되고, MMU가 접근해서 읽는다.

 

이 때, 각 page table의 원소 하나하나를 page table entry(pte)라고 한다.

 

page table entry

 

하나의 pte는 위의 그림과 같은 구조로 이루어져 있는데 (32비트의 경우) V는 valid bit로, pte가 유효한지 나타내고, R는 reference bit로 페이지가 참조된 적 있는지 나타낸다. M은 modify bit로 페이지가 사용된 적 있는지 나타낸다. prot는 protection bits로, 페이지가 일정 권한(read, write, execute,..) 등의 권한을 가지는지 나타낸다. 마지막으로 PFN은 physical frame number를 나타낸다.

 

 

 

3. page table structure

 

1) Linear page table

 

그냥 모든 Virtual Address의 page를 순서대로 다 담아놓은 page table이다. 즉, vpn 0번부터 vpn N번까지 쭈욱 늘려놓은 것인데, 이는 현대 컴퓨터 환경에서는 사용되지 않는다.

 

Linear page table

 

64비트 컴퓨터 기준으로, 페이지를 8KB로 쪼갰다고 했을 때, 2^64/2^13 = 2^51개의 pte가 필요하다. pte 하나가 8bytes라고 하면, 16페타바이트... 가 필요하다. 페이지 테이블 하나 저장하는데 16PB를 쓴다는것은 말이 안되기 때문에 Linear page table은 사용하지 않는다. (아니 사용할 수 없다...)

 

2) Hierarchy page table

 

위와같은 문제를 해결하기 위해 '안쓰는 page table은 할당하지 않고 있다가 필요할때만 할당하면 되지 않을까?' 라는 생각을 하였다. 그리고 그 해결법이 Hierarchy page table 방법이다.

 

Hierarchy page table

 

위의 그림과 같이 Outer page table과 page table을 나누어, 사용하는 Outer page table만 하위의 page table을 할당해주는 방식이다.

 

위와 같은 경우, 사용하지 않는 page의 경우, page table을 만들지 않아도 되고, outer page table로 손쉽게 관리할 수 있다는 장점이 있다.

 

Virtual address

 

위의 그림처럼 VA는 Outer page table entry를 나타내는 p1, page table entry의 위치를 나타내는 p2, page frame에서 실제 위치를 나타내는 d로 구성된다.

 

3) Hashed page table

 

해시 함수를 활용하여 VA를 PA로 mapping 하는 방법이다.

 

4) Inverted page table

 

VA를 보고 PA에 mapping하는 것이 아니라, 반대로 PA를 보고 VA를 찾는 방식이다.

 

프로세스마다 page table을 만들지 않아도 된다는 장점이 있지만, 여러가지 문제점이 많아 실험적으로만 사용된다.

 

 

 

4. TLB

 

앞서 말한 Hierarchy page table을 이용하면, VA를 PA로 변환하는데 굉장히 많은 시간이 필요하다.

 

따라서 더 빨리 메모리 변환을 하기 위해 생긴 녀석이 바로 TLB; Translation Look-aside Buffer이다.

 

TLB

 

TLB는 하드웨어에 구현된 표이다. TLB는 vpn과, vpn에 mapping되는 pfn를 가지고 있는데, 만약 어떤 vpn이 TLB에 있으면, page table을 뒤져보지 않고도 바로 pfn을 알 수 있다.

 

이 때, TLB에 있는 경우를 TLB hit, 없는 경우를 TLB miss라고 한다.

 

하지만, 프로세스가 바뀔 경우, TLB를 모두 flush 해줘야 한다는 문제점이 있다. (TLB에 pid를 추가시켜 flush해주지 않아도 되는 TLB도 많이 사용된다.)

 

 

오늘 배운 내용을 정리해보면,

 

1. 현대 운영체제에서 메모리는 paging 기법을 많이 사용한다.

 

2. paging은 LA와 PA를 같은 크기의 page로 쪼갠 뒤, page table이 이 둘을 mapping 하는 형식으로 사용된다.

 

3. Linear 하게 page table을 만드는 것은 거의 불가능하므로, Hierarchy하게 만드는 것이 좋다.

 

4. TLB는 실제 page table을 찾아보지 않고 빠르게 pfn을 찾을 수 있게 하는 하드웨어 로직이다.

 

 

위 내용은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.