1. 개념 정리: 전에 이어서 계속
주소 변환의 원리
먼저 위에서도 언급했듯, 운영체제 단독으로 주소 변환 작업을 하는 게 아니라 하드웨어의 지원을 받는다. 효율성을 높이려면 하드웨어의 지원을 받는 것이 좋다. C언어가 파이썬보다 빠른 것처럼 전기적 신호(=HW)가 C언어(=SW)보다 훨씬 빠르지 않겠나. 여기에는 TLB, 페이지 테이블 등이 필요하다.
주소 변환을 통해 하드웨어는 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제로 존재하는 물리 주소로 변환한다. 하지만 하드웨어는 가속화에 도움을 줄 뿐, 실질적인 메모리 가상화는 운영체제가 구현해야 한다. 따라서 운영체제는 메모리의 빈 공간과 사용 중인 공간을 항상 알고 있어야 하고, 메모리 사용을 제어하고 관리한다. 이 모든 작업의 목표는 프로그램이 자신 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만드는 것이다. 여기서 윗단에서 볼드 처리한 문장이 나온다. "각 프로세스 및 커널은 물리 메모리의 다른 영역을 참조하는 동일한 주소를 가질 수 있기 때문에 즉시 메모리를 공유할 수 없다."는 말은 즉 많은 프로그램이 물리 메모리를 공유하기 때문에 이를 적절하게 위치시켜야 한다는 뜻이다.
동적 재배치, 베이스 & 바운드
하드웨어 기반 주소 변환에 사용하는 아이디어는 Base & Bound이다. 우리는 이를 동적 재배치(Dynamic relocation)이라고도 한다. 둘은 같은 의미로 사용한다. 이 아이디어에서 각 CPU마다 2개의 하드웨어 레지스터가 필요한데, 하나는 베이스(base) 레지스터이고 다른 하나는 바운드(bound) 레지스터이다. 이 한 쌍의 레지스터는 우리가 원하는 위치에 주소 공간을 배치할 수 있게 한다. 이때, 배치하자마자 하나의 프로세스가 오직 자신의 주소 공간에만 접근한다는 것을 보장한다.
이 설정에서 각 프로그램은 물리 주소(실제로는 가상 주소에 해당) 0에 탑재되는 것처럼 작성되고 컴파일된다. 프로그램 시작 시, 운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고 베이스 레지스터를 그 주소로 지정한다. 그러면 프로세스가 실행되면서 아래와 같은 방식으로 프로세서가 주소를 변경한다.
Physical address = virtual address + base
운영체제가 32KB를 base 레지스터에 지정했다고 하면, 실제 물리 메모리에는 아래와 같이 들어간다. (아직 페이징 기법을 적용하지 않은 상황이며, 따라서 하나의 프로세스에 들어가는 메모리가 물리 메모리 상에서 연속적으로 들어가있다.)
여기서 base 레지스터 값은 가상 메모리와 실제 메모리 간 offset 개념이라고 생각하면 되겠다.
(가상 메모리 상에서 주소 0 == 물리 메모리 상에서 주소 base)
그러면 bound 레지스터는 어디에 쓰는 거지? 바운드 레지스터는 보호를 지원하기 위해 존재한다. 프로세서는 먼저 메모리 참조가 합법적인가를 확인하기 위해 가상 주소가 바운드 안에 있는지 확인한다. 위의 이미지로 치면 바운드 레지스터 값은 16KB이다. (그 이하는 운영체제 공간이기 때문에 건들면 안됨 => 이를 바운드 레지스터가 보호해주는 것.) 만약 프로세스가 바운드보다 큰 가상 주소 혹은 혹은 음수인 가상 주소를 참조하면 CPU는 예외를 발생시키고 프로세스는 종료된다. 이러한 주소변환(하드웨어는 프로세스가 참조하는 가상 주소를 받아들여 데이터가 실제로 존재하는 물리 주소로 변환하는 과정)은 프로세스가 실행될 때 일어나며 그 이후에도 주소 공간이 이동할 수 있기에 동적 재배치라고 하는 것이다.
이 베이스와 바운드 레지스터는 앞서 말했듯 CPU 칩 상에 존재하는 하드웨어이며, 이들을 메모리 관리 장치(Memory management unit, MMU)라고 한다. 이들에 값을 변경하는 명령어를 제공하는 건 운영체제의 특권 명령(커널 모드)이다. 만약 프로세스 범위 바깥 메모리를 참조하려 하면 운영체제가 exception handler를 실행시킨다(보통은 프로세스를 종료시킴).
정리하면, 주소 변환이라고 하는 가상 메모리 기법을 통해 운영체제는 프로세스의 모든 메모리 접근을 제어하며 접근이 항상 주소 공간의 범위 내에서 이루어지도록 보장한다. 이 기술을 가속화하는 것은 하드웨어의 지원으로, MMU라는 한 쌍의 레지스터(베이스, 바운드)가 가상주소로부터 실제 주소로 변환시킨다. 이 방식을 베이스 & 바운드(=동적 재배치)라고 한다. 하지만 위에서 말했듯, 위 내용은 아직 페이징 기법이 적용되지 않은 원시적인 형태의 베이스 & 바운드라 세그멘테이션을 마저 설명하고 아래 페이징까지 쭉 이어서 소개한다.
세그멘테이션
앞에서는 프로세스 주소 공간 전체를 메모리에 탑재하는 것을 가정했다. 하지만 이렇게 되면 단편화가 일어나 메모리 낭비가 심하다. 이를 해결하기 위한 아이디어가 세그멘테이션이다. 아이디어는 MMU에 하나의 베이스, 바운드 값이 존재하는 것이 아니라 세그멘트마다 베이스와 바운드 값이 존재한다. 쉽게 말해 코드/스택/힙 각 세그멘트에 대해 베이스와 바운드 값이 존재해 하나의 가상 주소 공간이 물리 주소 공간 상에서 연속적으로 붙어있는 게 아니라 세그멘트 단위로 흩어지게 만드는 것이다. 이렇게 하면 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지할 수 있다.
다시 아래 그림을 보자. 아래 왼쪽은 가상 주소인데, 빈 공간을 미리 만들어 둔 상황이다. 그런데 이것이 실제 물리 메모리 상에도 동일하게 구현되어 있으니 안 쓰는 공간을 굳이 남겨두게 되는 셈이다. 따라서 오른쪽과 같이 코드-힙-빈공간-스택을 연결하지 않고 스택 따로 코드 따로 힙 따로 물리 메모리 상에 배치해두고 스택과 힙의 방향을 각각 반대로 하면 확장도 할 수 있으면서 남는 미사용 공간이 줄어든다.
왼쪽 공간을 오른쪽에 어떻게 배치했을까? 프로그램 코드 세그먼트는 2KB 크기로 물리 메모리 32KB 위치에 배치한다. 힙 세그먼트는 코드 세그먼트 바로 아래인 34KB에 위치해 아래 방향으로 확장한다. 이때 세그먼트의 사이즈는 각 세그먼트마다 배치된 바운드 레지스터와 일치한다. 이 세그먼트에 몇 바이트가 유효한지는 운영체제가 하드웨어에게 알려준다. 따라서 프로그램이 바운드 바깥으로 접근할 때 하드웨어가 알 수 있다.
만약 힙의 마지막을 벗어난 주소에 접근하려고 하면? 하드웨어가 그 주소가 범위를 벗어났다는 것을 감지하고 운영체제에 트랩을 발생시킨다. 이것이 바로 그 망할 놈의 segment fault..
세그먼트 종류와 파악
하드웨어는 세그멘테이션 기법으로 가상 주소를 물리 주소로 변환하기 위해 필요한 정보는 1) 이 주소가 어느 세그먼트에 존재하는 것인지와 2) 이를 바탕으로 어디에 배치할지이다. 이를 위해 가상주소는 세그먼트 정보와 오프셋으로 구성되어 있다. 세그먼트의 종류는 코드/스택/힙이니 2비트면 모든 세그먼트 정보를 표현할 수 있고, 나머지 12비트로 레지스터가 실제 물리 주소를 계산한다. 가상 주소의 오프셋에 베이스 레지스터 값을 더한 것이 최종 물리주소이며, 바운드 검사는 오프셋 값이 바운드 값보다 작은지만 검사하면 된다. 이때, 스택은 다른 애들과 달리 반대 방향으로 메모리를 확장하기 때문에 이 부분을 다른 방식(음수 오프셋)으로 확장한다는 사실 정도만 알아두자.
이런 식으로 세그멘테이션 기법을 적용하면 시스템이 각 주소 공간(세그멘트) 단위로 가상 주소 공간을 물리 메모리에 재배치하기 때문에, 전체 주소 공간이 하나의 베이스-바운드 값을 갖는 방식에 비해 메모리를 절약할 수 있다. 스택/힙 사이 공간에는 물리 메모리를 할당하지 않기 때문.
하지만 세그멘테이션 기법에서 운영체제가 직면하는 세 가지 문제가 있다. 1) context switching에서 운영체제는 세그멘트 레지스터를 저장 및 복원해줘야 한다. 2) 세그멘트 크기 변경. 힙의 경우 malloc()을 호출해 늘릴 것이다. 그런데 메모리가 고갈됐다면 할당을 거절할 수 있다. 3) 미사용 중인 물리 메모리 공간 관리. 세그멘테이션 기법으로도 여전히 외부 단편화 문제를 해결할 수 없는데, 이를 해결하기 위한 방법 중 하나는 물리 메모리를 압축하는 것이다. 하지만 이는 굉장히 부하가 큰 연산(복붙이다보니)이기에 비용이 많이 든다. 간단한 방법은 빈 공간 리스트를 관리하는 알고리즘을 사용하는 것인데, 이 알고리즘 종류로는 best-fit, worst-fit, first-fit, buddy 알고리즘 등이 있다.
하지마 근본적으로 이 문제는 세그멘트의 크기가 일정하지 않기 때문에 발생하는데, 이를 해결하기 위한 방법으로 페이징을 소개한다.
페이징
다시 리마인드하자. 지금 이 글을 쓰는 목적은 커널이 유저 주소 공간에 어떻게 접근하는지에 대해 알아보기 위해서였다. 이를 위해 알아야 할 중요한 개념은 가상 주소와 물리 주소를 매핑하는 역할을 제공하는 페이지 테이블이다. 이를 이해하기 위한 개념으로 페이징을 다시 정리한다.
이전의 세그멘테이션 기법은 물리 주소를 가변 크기의 조각(세그멘트)로 분할하는 것이었다. 이렇게 분할하면 태생적인 한계가 발생하는데, 바로 다양한 크기의 chunk(뭉태기)로 분할할 때 공간 자체가 단편화될 수 있어 할당이 갈수록 어려워진다는 점이다. 이를 해결하기 위한 방법인 페이징 기법은 동일 크기의 조각으로 분할하는 방식이다. 즉, 프로세스 주소 공간을 몇 개의 가변 크기의 논리 세그멘트(코드, 힙, 스택)으로 나누는 게 아니라 고정 크기의 단위로 나누며 이 고정 크기의 단위를 페이지라고 한다. 여기서 핵심 질문은 아래와 같다.
- 세그멘테이션의 문제점을 해결하기 위해 페이지를 사용하여 어떻게 메모리를 가상화할 수 있는가?
- 기본적인 기법은 무엇인가?
- 공간과 시간 오버헤드를 최소로 하면서 그 기법을 잘 동작하게 만들기 위한 방법은 무엇인가?
페이징을 사용하면 이전 방식에 비해 가장 큰 장점이 바로 유연성과 단순함으로, 페이징을 사용하면 프로세스 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예컨대 이전의 세그멘테이션에서는 힙과 스택이 확장하는 방향성 등을 고려했으나 여기서는 상관이 없다. 공간이 분할되어 있기 때문이다. 따라서 가상 주소에서 연속적인 공간을 요청하더라도 운영체제는 불연속적인 페이지 여러 개와 매핑해주면 된다.
주소 공간의 각 가상 페이지에 대한 물리 메모리 위치를 기록하기 위해 운영체제는 각 프로세스마다(이게 매우 중요!!!) 페이지 테이블(page table)이라는 자료 구조를 유지한다. 이 페이지 테이블의 역할은 주소 공간의 가상 페이지 주소 변환 (address translation) 정보를 저장하는 것이다. 이 테이블을 통해 각 페이지가 저장된 물리 메모리의 위치를 확인할 수 있다.
예시로 64바이트 주소 공간을 갖는 유저 프로세스가 128바이트짜리 물리 메모리에 접근한다고 해보자. 이때 하나의 페이지 크기는 16바이트이다.
프로세스가 생성한 가상 주소의 변환을 위해 아래 이미지와 같이 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내 오프셋 2개의 구성 요소로 분할한다. 가상 주소 번호(VPN)을 나타내려면 주소 공간 크기가 64바이트이니 각 주소 공간 하나에 대한 정보를 표기하기 위해 총 6비트가 필요하다. (2**6 = 64). Va5는 가상 주소의 최상위 비트이고 Va0은 최하위 비트이다. 주소의 최상위 2비트는 물리 주소의 페이지를 식별하는 값이다. 16바이트짜리 페이지가 4개 있으니 2비트(2**2=4)면 4개에 대한 정보를 각각 식별 가능하다. 따라서 앞 2비트는 가상 주소 번호인 VPN이다.
나머지 4비트 오프셋은 페이지 내에서 우리가 접근하기를 원하는 바이트의 위치를 나타낸다.(페이지도 하나의 공간이니 해당 공간에서 특정 정보에 접근하기를 원할 테니까)
이를 물리 주소로 어떻게 변환할까? 예를 들어 프로세스가 생성한 가상 주소가 21이라고 하자. 그러면 먼저 21을 이진수 010101(2)로 변환한다. 앞 번호 01은 VPN, 뒤 0101은 오프셋이다.
/* virtual addr> 데이터를 eax 레지스터에 탑재(move) */
movl <virtual address>, %eax이를 위 어셈블리 명령으로 %eax 레지스터에 복사한다. 이어서 이 가상 페이지 번호를 가지고 페이지 테이블로부터 물리 프레임 번호(=물리 페이지 번호, PFN or PPN)을 찾는다. 즉, 페이지 테이블이 VPN에서 PFN으로 주소를 변환하여 물리 메모리에 탑재를 실행한다. 이때, 오프셋은 가상주소나 물리 주소나 동일하다.(여기 영역은 페이지 내에서 원하는 정보의 위치임. 즉, 가상 주소의 단일 페이지와 물리 주소의 단일 페이지는 일대일 대응한다는 뜻.)
페이지 테이블은 어디에 저장되는가?
여기서 의문 하나. 페이지 테이블에 가상 주소를 물리 주소로 변환하기 위한 정보가 담겨있다고 했다. 그럼 이 페이지 테이블 자체는 어디에 저장될까? 얘도 메모리를 관리하는 놈이니 MMU 안에 있을까? 결론부터 얘기하면 페이지 테이블은 자체는 메모리에 저장한다. 페이지 테이블은 실행 중인 프로세스 수가 많을수록 매우 커질 수 있기 때문이다.
예를 들어, 4KB 크기의 페이지를 갖는 32비트 주소 공간을 생각해보자. 이 가상 주소는 20비트 VPN과 12비트 오프셋으로 구성된다. 20비트 VPN이면 각 프로세스를 관리하는 변환 개수가 2**20이라는 것을 의미한다. 물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위해 페이지 테이블 항목(Page table entry, PTE)마다 4바이트가 필요하다고 가정하면 각 페이지 테이블을 저장하기 위해서만 4MB 메모리가 필요하다. 만약 100개 프로세스가 실행 중이면 400MB가 필요하다는 것이다.
이렇게나 사이즈가 크기 때문에 MMU 레지스터에 이를 넣을 수는 없다. 따라서 메모리에 저장하는 것. 이는 페이징 기법의 문제 중 하나이다. 하나 더 문제가 있는데, 페이징이 너무 느리다는 것. 페이지 테이블 크기가 메모리 상에서 매우 크니 이로 인해 처리 속도가 저하될 수 있다.
정리하면, 페이징 기법을 이용하면 가상 주소의 페이지 영역과 실제 물리 주소의 페이지 영역을 맵핑하는 정보인 페이지 테이블이 반드시 필요하다. 이 페이지 테이블은 각 프로세스마다 존재하는데, 실행 중인 프로그램 수가 많아지면 페이지 테이블 역시 많아지는데, 이로 인해
- 시스템이 매우 느려질 수 있다
- 너무 많은 메모리를 차지한다
다음 글에서 이 두 가지 문제를 해결하는 기법으로 TLB 하드웨어, 그리고 페이징과 세그멘트를 함께 사용하는 방법을 소개한다.