<aside> ❗ 목차

  1. Virtual Memory

  2. Hash Table

  3. Pintos의 메모리 관리 방법

</aside>

  1. Virtual Memory

    일상생활에서 볼 수 있는 자동차나 엘레베이터 등 임베디드 시스템에도 작은 컴퓨터가 있다. 이런 임베디드 시스템에서는 아래 그림과 같이 cpu에서 물리 메모리에 직접 접근한다.

    Untitled

    하지만 우리가 사용하는 PC는 임베디드 시스템과 달리 cpu가 여러 프로세스를 수행하며 여러 프로세스는 물리 메모리를 공유한다. 따라서 위와 같이 프로세스마다 1대1 매핑을 하면 작업이 매우 복잡해지며 물리 메모리의 용량은 한계가 있어 매우 비효율적이다. 따라서 우리가 사용하는 PC에서는 프로세스마다 고유한 가상 메모리를 갖는다고 가정한다. 그리고 MMU에서 가상 메모리의 주소를 실제 물리 메모리로 변환하여 저장한다. 가상 메모리를 사용하면 크게 3가지 이점이 있다. 우선 물리 메모리를 가상 주소영역의 캐시로 사용하여 물리 메모리를 효율적으로 사용할 수 있다. 그리고 각 프로세스는 고유한 가상 영역이 있어 물리 메모리를 신경 쓰지않고 관리하여 관리가 수월하다. 사실 추상화의 이점이라 생각한다. 마지막으로 프로세스 별로 각자의 영역을 가지고 있기 때문에 다른 프로세스로 부터 고립되어 있다. 이는 다른 프로세스를 침범하지 않도록 한다. 이를 그림으로 나타내면 아래와 같다.

    Untitled

    이제 주소 변환까지 알아 보았다. 실제 가상 메모리는 페이지 단위로 관리한다. 데이터를 한번에 하나씩 올리고 내리면 비효율적이므로 페이지 단위로 메인 메모리에 올리고 디스크로 swap out 하기도 한다. 각 프로세스는 페이지 테이블을 가지고 있다. 각 페이지가 메인 메모리 어느 위치에 있는지 그리고 메인 메모리에 올라가 있는지 알 수 있다. 만약 메인 메모리에 해당 페이지가 올라가 있지 않다면 디스크의 주소를 가르키고 있다. 이 페이지 테이블은 메인 메모리에 저장되어 있다. 이를 그림으로 나타내면 아래와 같다.

    Untitled

    가상 주소가 주어졌을때 페이지 테이블을 탐색하며 결과는 물리 메모리에 올라가 있거나(page hit) 물리 메모리에 올라가 있지 않아 디스크를 가르키고 있다.(page fault) 아예 할당 되지 않은 경우도 있지만(위 그림의 PT 0번째,5번째로 null값이다) 해당 경우는 디스크에 빈 페이지를 만들고 디스크 페이지의 주소를 기입하면 되는 간단한 경우이므로 따로 살펴보지 않을 것이다. 두 결과 별로 물리 메모리에 접근하는 방법이 다르며 각각 설명하려한다. 설명에 들어가기 전에 cpu에서 멀어지면 멀어 질수록 접근하는데 걸리는 시간이 매우 오래 걸린다는 것을 명심해야한다. 우리가 구현이 복잡해지지만 캐시를 적용하고 난리치는 이유이다. 보통은 물리 메모리에 접근하는것도 cpu에서는 손해이며 디스크로 가는것은 최악이다. 그럼 page hit 부터 살펴 보자.

    1. Page Hit

      이 경우는 생각할 것이 별로 없다. 이미 물리 메모리에 원하는 페이지가 올라가 있으므로 PTE(page table entry)에 기록 되어 있는 물리 메모리 주소를 이용하여 데이터를 읽어 cpu로 전달하면 끝이다. 물리 메모리에 올라가 있는지 확인 하는 것은 valid bit를 이용한다.

    2. Page Fault

      Untitled

    위 그림에서 가상 주소를 통해 PT의 3번째 항목을 확인하며 valid bit 가 0이고 PTE는 디스크를 가르키는 것을 확인한다. 이 경우 vp3를 물리 메모리에 올려야한다. 그런데 물리 메모리에 빈자리가 없다. 따라서 물리 메모리에서 디스크로 내려보내야 할 페이지(victim)를 선택해야한다. 이번 예시에서는 VP4를 디스크로 내리기로 한다. 빈자리가 생기면 VP3를 그 자리에 올린다. 그리고 이러한 변경사항을 PT에 갱신시켜 준다. 이를 그림으로 나타내면 다음과 같다.

    Untitled

    이렇게 VP3가 물리 메모리에 올라가고 PT가 갱신되면 페이지 폴트가 일어 났던 인스트럭션을 재수행하고 정보가 갱신되어 있으므로 페이지 히트되어 작업이 계속된다. 페이지 폴트가 일어나기 전까지 디스크의 내용을 디램에 올리지 않는다. 이 방식을 demand paging이라 한다. 핀토스 깃북에 설명되어 있는 lazy loading과 유사한 것 같다.

    프로세스들이 표준 입출력과 같이 공통으로 사용하는 데이터가 있다. 해당 페이지를 공유 하지 않는다면 각 프로세스마다 동일한 페이지를 만들어야 하고 이는 메모리를 낭비하게 한다. 따라서 read-only 페이지는 프로세스가 공유하게끔 한다.

    Untitled

    또한 PTE에는 Valid bit 외에 여러 bit 들이 있다. 위와 같이 같은 물리 메모리의 페이지를 공유하면 침범할 가능성이 있으므로 PTE에 추가 비트를 추가하여 프로세스간 메모리를 보호한다. 리눅스에서 파일권한 설정하는 것과 유사하다.

    Untitled

    페이지 폴트가 일어나면 일어나는 일과 페이지를 어떻게 관리하는지를 알아보았다. 그런데 MMU는 가상 주소를 물리 주소로 어떻게 변환할까? 이를 간단하게 알아보려한다.

    Untitled

    위 그림은 가상 메모리 주소가 물리 메모리 주소로 어떻게 변환 되는지 과정을 나타낸 것이다. 우선 가상 주소는 VPN과 VPO로 구분된다. CR3 레지스터에는 페이지 테이블의 시작주소가 저장되어있다. VPN과 페이지 테이블의 시작주소를 통해 PTE에 접근한다. PTE에 기록되어 있는 PPN과 VPO를 결합하여 물리 주소를 얻는다. 여기서 눈여겨 봐야 할 것은 위그림의 VPO와 PPO는 동일하다. 가상 메모리의 페이지 시작주소를 물리 메모리 페이지 시작주소로 바꿔 주는 것이다.

    이를 위에서 살펴본 page hit, page fault와 합쳐서 살펴보면 아래와 같다.

    Untitled

    Untitled

    위 두 경우를 살펴보면 MMU는 PTE내의 PPN 정보를 확인하기 위해 메인 메모리에 여러번 접근해야 한다. MMU 입장에서는 매우 답답하다. 위에서 처음에 언급했듯이 메인 메모리나 디스크에 접근하는 횟수를 줄이기 위해 cpu 칩 내에 하드웨어 칩을 추가해 준다. 이를 TLB라 한다.

    TLB는 PT와 달리 모든 PTE를 순회하지 않고 set 별로 여러 PTE를 포함하고 있다. 따라서 PT가 ㅖPTE를 순회하며 원하는 데이터를 얻는것 보다 더 빠르다고 한다. 해쉬테이블과 배열의 탐색속도 차이랄까.. TLB에 접근하기 위해 VPN을 tag와 index로 나눈다. 이를 그림으로 나타내면 아래와 같다.

    Untitled

    이제 TLB도 테이블이며 크기가 작으므로 모든 PTE를 담고 있을 수 없다. 따라서 TLB hit와 TLB fault가 있다. 만약 TLB Hit라면 TLB에 있는 PTE를 이용하여 바로 물리 메모리 주소로 변환하여 물리 메모리로 접근한다. 반면 TLB fault의 경우 기존과 동일하게 메인 메모리에 접근해야한다. PT로 부터 전달받은 PTE를 TLB에 갱신하며 동시에 MMU로 전달한다. 그리고 물리 메모리로 변환하여 접근한다. TLB miss시 기존보다 비용이 더 발생하지만 지역성 때문에 TLB miss가 거의 발생하지 않는다. 이를 그림으로 나타내면 아래와 같다.

    Untitled

    Untitled

    이제 마지막으로 멀티레벨 페이지 테이블만 남았다. 48비트 주소 영역에서 한 페이지의 크기는 4KB($2^{12}$)이며 페이지 테이블 엔트리의 크기는 8바이트라 가정해보자. 이 경우 전체 페이지 테이블의 크기는 $2^{48}\times 2^{-12} \times 2^{3} = 2^{39} \text{ bytes(512GB)}$ 이다. 물론 페이지 사이즈를 늘리면 되지만 이는 내부 단편화를 일으킨다. 이를 해결하기 위해 아래와 같이 레벨을 나누어 페이지 테이블을 관리한다.

    Untitled

    레벨 1의 PTE에는 레벨 2의 PT의 시작주소를 가지고 있다. PT의 시작 주소와 인덱스를 이용하여 해당 페이지의 PPN 값을 얻고 이를 통해 물리 주소로 변환 할 수 있다. 이때 장점은 가상메모리에서 사용하지 않는 영역의 페이지 테이블이 필요가 없어 메모리를 효율적으로 사용할 수 있다. 위 그림에서도 가상 메모리의 페이지를 나타내기 위해 페이지 테이블은 단 4개만 사용하였다. 위와 같이 32비트 주소 체계에서는 레벨2로 충분하지만 더 큰 주소 체계에서는 더 많은 레벨이 필요하다. 실제로 현재 인텔에서는 4레벨을 사용 중이며 핀토스도 4레벨 페이지 테이블을 지원한다. 다단계 페이지 테이블에 접근하기 위한 주소 변환과 실제 인텔 i7 프로세서의 주소변환 모식도는 아래와 같다.

    Untitled

    Untitled

  2. Hash Table

    해쉬 테이블 이란 해쉬 함수를 이용하여 키를 변경하여 관리하는 자료구조이다. 왜 굳이 키를 변환할까? 만약 기존 배열을 생각해보자. 배열 내에서 특정 키를 찾기 위해서는 배열을 순차적으로 순회해야한다. 배열을 순회하며 키가 일치하는지 확인하고 아니면 다음으로 넘어가는 완전탐색이다. 하지만 해쉬 테이블의 경우 순회하지 않고 키 변환을 통해 가야할 곳을 바로 알 수 있다. 보통 고급 언어들은 내장함수로 이를 지원한다. 대표적으로 파이썬의 딕셔너리가 있다. 하지만 핀토스는 c언어이기 때문에 내장 함수가 없다. 대신 해쉬 테이블 라이브러리를 만들어 두었다. 이를 사용하기 위해 깃북에 나와있는 설명을 살펴보자.

  3. Pintos의 메모리 관리 방법

    X86-64bit 시스템에서 가상 메모리 구조를 나타낸 그림을 살펴보면 다음과 같다.

    Untitled

    이 중에서 Physical memory 영역은 물리 메모리와 1대1 대응된다. pml4를 거치지 않고 매크로를 통해 빠르게 물리 주소로 변환 할 수 있다고 한다. 32 비트 운영체제에도 물리 메모리 영역이 있지만 크기가 1기가 안쪽으로 사용이 제한적이다. 따라서 64비트 처럼 전체를 매핑하지는 못하고 일부분만 매핑을 한다고 한다. 핀토스도 x86-64 비트 시스템이지만 위와 약간 다르다. 아래 그림은 32 비트 시스템의 핀토스 가상메모리 구조이지만 전체적인 그림은 비슷하다.

    Untitled

    앞에서 살펴본 X86-64 시스템과 달리 커널 영역 전체가 물리 메모리와 1대1 매핑되어있다. palloc_get_page 함수를 통해 물리 메모리 페이지와 커널 영역의 페이지를 매핑 시킨다. 그리고 Install_page 함수를 통해 유저 영역으로 매핑 시킨다.