[OS/운영체제] Paging

1. Paging

Paging이란 프로그램을 일정한 크기의 페이지 단위로 나눠서 실제 메모리에 불연속적으로 할당하는 방법을 말한다. 페이지는 4KB, 8KB, 16KB, 32KB 등으로 설정되지만 일반적으로는 페이즈의 크기를 4KB로 사용한다. 이 글에서도 4KB로 생각하면 된다. 페이지 크기가 줄어들수록 내부 조각이 적어지지만 페이지 테이블의 크기가 증가하고 반대로 페이지 크기가 크면, 내부 조각이 많이 생기지만 페이지 테이블의 크기는 줄어든다.
여기서 페이지(Page)와 프레임(Frame) 두 가지 용어를 먼저 알고 가자.

페이지(Page) : 논리적인 메모리(프로세스의 가상 주소)를 일정한 크기로 나눈 것
프레임(Frame) : 실제 물리적인 메모리(RAM)를 일정한 크기로 나눈 것

페이지는 가상 주소, 프레임은 실제 메모리 주소를 의미하며 이 둘은 Page table을 통해 매핑된다.

아래 그림과 함께 페이징에 대해 더 자세히 알아보자.

2. Page Table

위의 그림에서 보면 하나의 프로세스는 메모리에 적재 될 때 여러개의 페이지로 분리돼서 물리적인 메모리에 불연속적으로 적재된다. 이때 논리적인 가상 주소와 실제 메모리에 올라갈 때 주소가 다르기 때문에 이를 매핑해주는 역할을 하는것이 바로 Page table이다. 
위의 그림과 같이 프로세스가 0~3번까지 페이지로 잘렸고 페이지테이블의 인덱스가 프로세스의 페이지를 의미한다. 실제 메모리에는 불연속적으로 적재되기 때문에 0번째 페이지는 실제 메모리의 1번 주소에 매핑되어 있다는 것을 저장하는 배열이다.
 하지만 페이지 테이블은 메모리에 붙어있기 때문에 CPU에서 메모리까지 가서 Table을 조회하려면 시간이 걸린다. 그렇기때문에 CPU는 바로 Page table을 참조하지 않고 TLB라는 캐시를 먼저 참조한다.

3. TLB(Translation Lookaside Buffer)

잠깐 컴퓨터 구조로 넘어가 보자. 컴퓨터 안에는 캐시 메모리(Cache Memory)라는 친구가 존재한다. 캐시는 처리 속도가 매우 빠른 CPU와 처리 속도가 상대적으로 느린 메인 메모리 사이에 위치하며, CPU가 자주 사용하는 명령어나 데이터를 저장하는 고속 메모리이다. 캐시에 대해서는 간단히 여기까지만 알아보고 넘어가자.

다시 돌아와서, CPU는 프로세스의 논리-물리적 주소를 매핑 후 이 정보를 TLB라는 캐시에 저장한다. 그리고 다음 매핑시 메인 메모리에 저장된 Page table을 참조하기 전에 CPU와 가까히 있는 캐시인 TLB를 먼저 조회한다. 만약 매핑했던 이력이 있으면 TLB를 통해 매핑을 빠르게 수행하고, 만약 TLB에 이력이 없다면(TLB miss) 페이지 테이블에서 조회한다. 

4. Two-Level Page Table

프로그램이 프로세스로 변경되어 메모리에 적재될 때 운영체제에게 자원을 할당받는다. 이때 프로세스를 구성하는 코드들은 Memory segment에 따라 크게 Code, Data, Heap, Stack로 나눠져서 적재된다. Heap과 Stack은 스택이 위에서 아래로, 힙이 아래에서 위의 방향으로 메모리가 적재되는데 Heap, Stack의 사이 부분은 모두 사용하지 않는 논리 주소로 이루어져 있다. 이 얘기를 한 이유는, Heap과 Stack 사이의 논리적 주소를 Page table에 안만들고 넘어갈 수는 없기 때문이다. 왜냐하면 페이지 테이블은 배열이고, 배열의 인덱스를 통해 바로 물리적 주소와 매핑하기 때문에!

그래서 지금까지 살펴본 1차적인 Page table은 메모리 낭비가 심하다. 그래서 메모리를 효율적으로 사용하기 위해 나온게 이번에 살펴볼 2단계 페이지 테이블이다.

2단계 페이지 테이블은 말 그대로 페이지 테이블을 2개를 사용하여 주소를 매핑하는 방법이다. CPU가 논리적 주소를 포인팅하면 outer page table - page table 총 2번의 조회를 사용해서 물리적 메모리 주소를 가져온다.

32bit 운영체제를 기준으로 설명하면 32bit는 총 4GB까지 메모리를 인식 할 수 있다. 이유는 2^10 > KB, 2^20 > MB, 2^30 > GB만큼의 메모리를 의미하기 때문이다. 쉽게 10승씩 올라갈 때마다 단위가 하나씩 바뀐다고 생각하면 쉽다.

그래서 32bit 운영체제는 4GB의 메모리를 4KB의 페이지 단위로 쪼갠다. 그럼 outer page table은 총 4KB의 페이지가 1M(백만)개 나온다. 그럼 하나의 outer page table entry는 4KB를 4bite로 쪼갠 1000개의 엔트리를 가진 inner page table이 나오게 된다.

 

이게 맞나 싶을것이다. 단편적으로만 보면 공간복잡도는 100만*100만으로 이루어지기 때문에 1조?라고 생각할 것이다. 하지만 전체 주소공간 중 대부분은 사용하지 않는 공간이기 때문에 아까 언급했던 Heap과 Stack의 사이 공간에 대한 outer page table은 생성되지만 inner page table은 생성되지 않기 때문에 공간을 효율적으로 사용할 수 있는 것이다.

이 부분에 대한 직관적인 CMU자료를 스택오버플로우에서 얻었다. 참고하면 될 것 같다.

https://stackoverflow.com/questions/59816941/how-do-multi-level-page-tables-actually-save-space

 

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐