Paging / Internal fragmentation / TLB

Paging

 

   - MMU에서 register에 logical address와 physical address의 차이를 저장하여, 메인 메모리에 적재되는 위치와 상관없이 logical한 address를 얻을 수 있었던 것처럼, 메모리 영역을 일정 크기로 잘게 나누고, 레지스터를 더 두어 그 차이를 저장하여 프로세스를 쪼개어 적재하는 방식이다. 이렇게 쪼개어 적재하는 것으로 외부 단편화를 해결한다.

 

   - 프로세스, 논리 주소를 자르는 단위를 페이지, 메모리를 자르는 단위를 프레임이라고 한다. 페이지 테이블을 두어, 논리 주소가 실제 메모리 안에서는 어느 프레임에 위치하고 있는지를 확인한다.

 

Paging

 

Paging Address Translation

 

   - CPU의 논리 주소는 페이지 테이블을 읽고, 페이지 테이블에서 얻은 프레임 번호 값으로 다시 메모리를 읽게 된다. 논리 주소는 pageNum bit와 offset bit로 구성되는데, offset 비트는 페이지 사이지를 n이라고 했을 때, n를 로그2 취한 값만큼 비트를 논리 주소의 뒤에서 갖는다. 나머지 offset 앞쪽 비트가 pageNum 비트가 되어 테이블 페이지의 인덱스를 결정한다.

 

   - 페이지 테이블에서 pageNum에 해당하는 데이터를 읽어 실제 메인 메모리에서 어디에 맵핑할지를 결정하는 프레임 인덱스, frameNum를 얻게된다. 

 

Paging address translation

  

   - 위 그림에서 pageSize=4이다. 4비트의 주소 체계라고 가정했을 때, 논리 주소의 하위 2비트가 offset, 상위 2비트가 pageNum가 된다. 논리 주소가 0010이라고 해보자. pageNum=0b00, offset=0b10이다. 페이지 테이블에서 0에 해당하는 값은 1이고, 따라서 frameNum=1, 즉 참조하고자 하는 메인 메모리의 프레임 인덱스는 1이고, offset은 동일하게 0b10으로 물리주소 0b0110을 얻게된다.

 

   - 반대로 물리주소가 0b1011인 경우 논리주소는 어떻게 될까. 우선 offset bit는 0b11이고, frameNum bit는 0b10이다. 프레임 인덱스 2를 얻기 위해서는 페이지 테이블 인덱스 3를 참고해야하므로 pageNum는 0b11일 것이다. 따라서 offset비트와 합쳐 논리주소는 0b1111이다.

 

Internal fragmentation

 

   - hole이 파편화되어 프로세스가 적재되지 못하는 문제는 페이징으로 프로세스를 조각으로 쪼개 해결할 수 있었다. 하지만 페이지 크기가 4byte인데 프로세스 크기가 15byte여서 결국 마지막 인덱의 프레임은 1byte 낭비되는 문제가 남아있다. 이런 상황을 내부 단편화라고 한다.

 

   - 내부 단편화의 최대 사이즈는 pageSize-1이다. pageSize를 최대한 작게하여 해결할 수 도 있겠지만 매핑하는데 사용되는 overhead와 비교하여 pageSize를 어떻게 잡아야 효율적인지 고민해야한다.

 

TLB (Translation Lookaside Buffer)

 

   - 페이지 테이블이 cpu 레지스터에 있다면 빠를 수 있지만 그 공간이 아까울 것이고, 메모리에 있다면 공간은 충분해도 느린 메모리를 참조하여 테이블을 확인하고, frameNum을 얻어 다시 메모리를 참조해야하므로 2배 가까운 시간이 소비될 것이다.

 

TLB

 

   - 페이지 테이블을 메모리에 둬 공간을 충분히하되, 페이지와 프레임 인덱스를 매핑하여 속도 문제를 해결할 수 있도록한 캐시가 TLB이다. 버퍼를 읽어 hit에 성공하면 메모리 바로 참조, 버퍼를 읽어 miss 됐을 때는 메모리에서 페이징 테이블을 읽고, 그 값으로 메모리를 읽으므로 다음의 기대 속도을 갖는다.  

 

Effective access time