memory management strategies2: page table의 구현

이전 포스팅에서 paging 기법과 이를 위한 핵심 알고리즘인 page table에 대해 살펴보았다.

2022.01.10 - [STUDY/운영체제] - memory management strategies

그렇다면 내부적으로 page table은 대체 어떻게 구현되어 있을까?

 

Implementation of page table

page table

: logical address를 physical address로 변환하기 위한 자료구조로써, main memory에 위치해 있다.

따라서 운영체제에서는 page table에 접근하기 위해 두가지의 register를 사용한다.

 

1. PTBR, page table base register

: 메모리 내에서 page table이 시작되는 위치를 찾는 용도

2. PTLR, page table length register

: page table의 크기를 저장하는 용도 (어디까지가 Page table인지 찾는 용도)

 

page table에 접근하여 정보를 가져올 때도 메모리 접근이 두번이 필요하다.

1. page table 자체에 접근할 때

2. page table을 통해 변환된 실제 주소에 접근할 때

 

메모리 접근이라는 것은 애초에 느리고 오버헤드가 큰 작업이다. 이를 두번이나 해야하는 것은 오버헤드가 크다.

따라서 이 오버헤드를 줄이고 메모리 접근 속도를 향상시키는 것이 주요한 목표이다.

이를 위해 하드웨어 캐시 메모리를 사용한다.

이 캐시를 TLB라고 한다. 

 

---

TLB, Translation Look-aside Buffer

: 지역성을 활용하여, 자주 사용되는 page에 대한 주소를 저장한다.

page table이 크기가 크기 때문에 cpu 구현을 하지 않고, Page table의 일부를 mmu에 넣어 cpu의 캐시 메모리의 형태로 사용한다. 또한 TLB 캐시 메모리를 따로 두고 page table을 access하여 오버헤드를 줄이는 작업이다.

 

paging hardware with TLB

 

TLB 캐시 메모리는 page number를 입력하면 이에 대한 frame number를 병렬로 찾아서 출력한다. 따라서 속도가 빠르다.

병렬 검색을 지원해야 하기 때문에 Fully Associative Memory로 구현된다.

이때 tag는 logical address로써, tag가 모든 데이터마다 1개씩 필요하다.

page table entry가 cache의 값이기 때문에 [page table entry + offset] 으로 mmu가 바로 physical address를 계산 가능하다.

 

TLB는 캐시 메모리인 만큼 지역성을 이용한다. 이때 두가지의 지역성이 활용된다.

1. temporal locality: 최근에 참조된 것은 또 참조될 확률이 높다.

2. spatial locality: 참조된 주변의 데이터도 참조될 확률이 높다.

 

하지만 TLB가 지역성을 활용한다고 하더라고, TLB에 찾는 데이터가 없을 수 있다. 이를 cache miss, 여기서는 TLB miss 라고 한다.

그렇다면 이를 어떻게 처리해야 할까?

 

handling TLB miss

: page table로 직접 가서 Page number에 해당하는 frame number를 찾아야한다.

intel x86에서는 mmu가 직접 Miss를 처리한다. 즉 cpu가 page table을 이미 다 알고있기 때문에 가서 찾아올 수 있다.

이 과정은 오버헤드가 크기 때문에 os가 처리할 수 없다.