주소 변환 (address translation) 의 원리

이 포스트는 OSTEP 의 15장 주소 변환에 관한 내용을 다룹니다.

메모리 가상화와 주소변환

CPU 가상화 부분에서, 대부분의 경우 프로그램은 하드웨어에서 직접 실행되지만 프로세스가 시스템 콜을 하거나 타이머 인터럽트가 발생할 때 등의 특정 순간에 운영체제가 개입하여 문제가 발생하지 않도록 하는 제한적 직접 실행 (Limited Direct Execution) 이 적용된다. 따라서 운영체제는 약간의 하드웨어 지원만 받고 실행 프로그램에게 방해가 되지 않는 효율적인 가상화를 제공하며, 중요한 순간에 운영체제가 관여하여 하드웨어를 직접 제어한다. 즉, 효율성과 제어를 바탕으로 CPU 가상화가 이루어진다.

 

메모리 가상화의 목적

메모리 가상화에서도 비슷한 전략이 추구된다. 가상화를 제공하는 동시에 효율성 (efficiency) 과 제어 (control) 과 함께 유연성 (flexiblity) 을 추구한다.

 

• 효율성 (efficiency)
  레지스터, TLB, 페이지 테이블 등 하드웨어의 지원
• 제어 (control)
  응용 프로그램이 자기 자신의 메모리 외에 다른 메모리에 접근하지 못함을 운영체제가 보장
• 유연성 (flexiiblity)
  프로그래머가 원하는 대로 주소 공간을 사용하고, 프로그래밍하기 쉬운 시스템 만들기

그렇다면 이제 다음의 질문에 답해야 한다.

 

• 어떻게 효율적인 메모리 가상화를 구축할 수 있을까?
• 어떻게 프로그램이 접근할 수 있는 메모리의 위치에 대한 제어를 유지하는가?
• 어떻게 프로그램이 필요로 하는 유연성을 제공하는가?

주소변환에서 하드웨어와 운영체제의 역할

메모리 가상화에서 다룰 기법은 주소 변환 (address translation) 이다. 주소 변환을 통해 하드웨어는 가상 주소를 정보가 실제 존재하는 물리 주소로 변환한다.

 

하드웨어에 의해 제공되는 low-level 기능들은 변환을 가속화하는데 도움이 되지만, 하드웨어만으로 메모리 가상화를 구현할수 없다. 정확한 변환이 일어날 수 있도록 하드웨어를 셋업하기 위해 운영체제가 관여해야 한다. 운영체제는 메모리의 빈 공간과 사용 중인 공간을 항상 알고 있어야 하고, 메모리 사용을 제어하고 관리해야한다.

 

하드웨어와 운영체제가 참여하는 이 모든 작업의 목표는 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만드는 것이다!

메모리 가상화의 출발

사용자의 주소 공간이 물리 메모리에 연속적으로 배치되어야한다고 가정하자. 프로그램의 관점에서 주소 공간은 아래 그림과 같이 주소 0 부터 시작하여 최대 16KB 까지이며. 프로그램이 생성하는 모든 메모리 참조는 이 범위 내에 있어야 한다.

 

메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소 0 이 아닌 다른 곳에 위치시키고 싶다. 어떻게 하면, 프로세스 주소 공간이 실제로는 다른 물리 주소에 배치되어 있을 때, 프로세스 모르게 메모리를 다른 위치에 재배치 하느냐가 해결해야할 문제이다.

 

 

위와 같이 물리 주소 0 ~ 16KB 에 배치되어 있던 프로세스의 메모리는 아래 그림과 같이 물리 메모리 32KB ~ 48KB 에 재배치될 수 있다. 만약 아래 그림이 물리 메모리가 아니라 가상 주소 기반의 주소 공간이라면, 재배치 시에 주소 변환이 필요하다. 앞에서 하드웨어에 의해 지원되는 그 주소 변환 (address translation) 말이다.

 

그런데, 왜 운영체제는 메모리를 재배치하고 싶어할까?

 

재배치의 목적

운영체제가 메모리를 재배치하지 않고, 항상 고정된 위치에 메모리를 배치하는 환경을 가정해보자. 운영체제는 메모리가 할당될 파티션 (partiton) 을 모두 동등한 크기 (equal size) 로 나눌 수도 있고, 다른 크기로 (unequal size) 로 나눌 수도 있다.

 

먼저 모두 동등한 크기로 파티션을 나누는 경우부터 생각해보자. 모든 파티션이 크기가 동일하므로 파티션 별로 대기큐가 없이, 프로세스가 컴파일 될 때 사용중이지 않은 파티션에 프로세스 메모리를 할당하면 된다. 하지만 파티션에 메모리를 적재할 때 항상 파티션의 크기보다 프로그램의 크기가 작아야하므로, 사용하지 않는 주소 공간이 낭비되는 문제가 발생한다 (internal fragmentation).

 

다른 크기로 파티션을 나누는 경우에는 아래 그림처럼 각 파티션마다 큐가 대기 큐가 존재해야 한다. 각 파티션마다 파티션을 사용중인 프로세스가 종료되어야 다음 프로세스가 메모리를 적재하고 실행할 수 있다. 따라서 어느 파티션은 바쁘고, 어느 파티션은 한가해지므로 비효율이 발생한다.

 

 

하지만 여기서 재배치가 가능하다고 생각해보자. 파티션을 미리 나누는 경우에는 각 파티션마다 대기 큐가 존재해야 했지만, 재배치가 가능하다면 실행 시에 프로그램의 크기에 따라 프로세스 메모리를 적절한 파티션에 배치할 수 있기 때문에 각 파티션마다 대기큐가 필요하지 않다. 즉, 아래 그림처럼 싱글 큐 (single queue) 로 메모리 배치가 가능해진다.

 

 

그렇다면 파티션의 메모리 적재와 주소 결정은 어떻게 이루어지는 걸까?

바로 동적 재배치의 베이스와 바운드 레지스터를 통해서 이루어진다.

하드웨어 : 동적 재배치

베이스 레지스터

하드웨어 기반 주소 변환의 시작은 동적 재배치 (dynamic relcation) 혹은 베이스와 바운드 (base and bound) 라 불리는 아이디어이다.

 

동적 재비치는 먼저 각 CPU 마다 베이스 (base), 바운드 (bound) 2개의 하드웨어 레지스터가 필요하다. 이 베이스와 바운드 쌍은 우리가 원하는 위치에 주소 공간을 배치할 수 있게 하며, 배치와 동시에 프로세스가 오직 자신의 주소 공간에만 접근한다는 것을 보장한다. 이 설정에서 각 프로그램은 주소 0 에 탑재되는 것처럼 작성되고 컴파일되지만, 프로그램 실행 시에 운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고 베이스 레지스터를 그 주소로 지정한다.

 

프로세스는 주소 0 부터 가상 주소를 생성하고, 하드웨어는 운영체제가 설정한 베이스 레지스터의 내용을 이 가상 주소에 더하여 물리 주소를 생성한다. 프로그램 실행 중에 프로세스가 메모리 접근을 위해 가상 주소를 참조하면, CPU 의 프로세서 (하드웨어) 는 물리 주소를 생성할 때 사용했던 아래 식을 이용해 물리 주소로 변환한다.

 

pyhsical address (하드웨어) = base (운영체제) + virtual address (프로세스)

 

위와 같은 가상 주소에서 물리 주소로의 변환이 주소 변환 (address translation) 이며, 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 주소 공간을 이동할 수 있으므로 동적 재배치라고 하는 것이다!

 

바운드 레지스터

그렇다면 바운드 레지스터는 어떤 역할을 하는가? 바운드 레지스터는 보호를 지원하기 위해 존재한다. 프로세서는 먼저 메모리 참조가 합법적인가를 확인하기 위해 가상 주소가 바운드 안에 있는지 확인한다. 만약 프로세스가 바운드보다 큰 가상 주소나 음수인 가상 주소를 참조하면 프로세서는 예외를 발생시키고 프로세스는 종료될 것이다.

 

바운드 레지스터는 2가지 방식 중 하나로 정의된다.

 

• 주소 공간의 크기를 저장하는 방식으로, 하드웨어는 가상 주소를 베이스 레지스터에 더하기 전에 먼저 바운드 레지스터와 비교한다.
• 주소 공간의 마지막 물리 주소를 저장하는 방식으로, 하드웨어는 먼저 베이스 레지스터를 더하고 그 결과가 바운드 안에 있는지 검사한다.

MMU

베이스와 바운드 레지스터는 CPU 칩 상에 존재하는 하드웨어 (CPU 당 1쌍만 존재) 로, 주소 변환에 도움을 주는 프로세서의 일부를 MMU (memory management unit) 라고 부른다.

 

MMU 의 베이스와 바운드 레지스터를 통해, 미리 시작 주소를 컴파일하기보다, 0번 주소를 기준으로 컴파일한 뒤 어느 파티션이든 적재하고, 실행할 떄 주소를 변환할 수 있게 된다. 아래와 같이 LAS (Logical Address Space) 의 파티션에 메모리를 적재하고, 베이스와 바운드 레지스터를 통해 PAS (Physical Memory Space) 의 파티션으로 주소를 변환해 배치할 수 있다.

 

 

하드웨어에 대한 지원

위의 주소 변환을 위해 하드웨어에게 제공되어야하는 것이 어떤 것이 있을까?

 

• 베이스/바운드 레지스터
• 가상 주소를 변환하고 범위 안에 있는지 검사하는 능력
• 베이스/바운드를 갱신하기 위한 특권 명령어
• 예외 핸들러 등록을 위한 특권 명령어
• 예외 발생 가능

운영체제의 관리

하드웨어 지원과 운영체제 관리가 결합되면 간단한 가상 메모리를 구현할 수 있는데, 베이스와 바운드 방식의 가상 메모리 구현을 위해 운영체제가 반드시 결합해야하는 3개의 시점이 존재한다.

 

1. 프로세스가 생성될 때, 운영체제는 주소 공간이 저장될 메모리를 찾아 조치를 취해야한다.
   운영체제는 물리 메모리를 슬롯의 배열로 보고 각 슬롯의 사용여부를 관리하는데, 새로운 프로세스가 생성되면 새로운 주소 공간 할당에 필요한 영역을 찾기 위해 free list 자료 구조를 검색
   
   
2. 프로세스가 종료할 때, 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있게 해야한다.
   
   
3. 프로세스 간 문맥교환 시, 운영체제는 프로세스의 베이스와 바운드 쌍을 저장하고 복원해야한다.
   운영체제가 프로세스를 중단하기로 결정하면, 메모리에 존재하는 프로세스 별 자료 구조 안에 베이스와 바운드 레지스터의 값을 저장해야한다. 이 자료 구조는 PCB (process control block) 이라고 불린다.
   
   운영체제가 프로세스를 실행시킬 때는, 프로세스에 맞는 값으로 CPU 의 베이스와 바운드 값을 설정해야 한다. 프로세스가 중단됐을 때 운영체제의 프로세스 메모리 재배치에 대해 생각해보자. 운영체제는 먼저 프로세스의 실행을 중지시키고, 현재 위치에서 새 위치로 주소 공간을 복사한다. 그리고 PCB 에 저장된 베이스 레지스터를 갱신해, 새 위치를 가리키도록 한다.
   
   
4. 운영체제는 예외 핸들러 혹은 호출될 함수를 제공해야 한다.
   예를 들면, 프로세스가 바운드 밖의 메모에 접근하려는 경우, 허가 받지 않은 메모리에 접근하므로 CPU 는 예외를 발생시킨다. 운영체제는 이런 예외가 발생할 때 조치를 취할 준비를 해야한다.
   
   

책에서 예시로 든 프로세스 A 의 실행과 A → B 의 문맥 교환, 프로세스 B 의 예외 처리와 종료 과정은 아래와 같다. A 의 생성은 위의 ①, A→ B 문맥 교환은 위의 ③, B 의 예외처리는 위의 ④, B 의 종료는 위의 ② 에 해당한다.

 

 

여기서 주목할 부분은 메모리 변환이 운영체제의 개입 없이 하드웨어에 처리된다는 것이다! 운영체제는 하드웨어를 적절하게 설정하고 프로세스가 CPU 에서 직접 실행할 수 있게 한다. 다만, B 의 예외처리와 같이 프로세스가 잘못된 행동을 했을 때만 개입한다.

 

앞에서 다루었던 효율성과 제어가 다시 의미를 가지는 순간이다.

 

문제점

동적 재배치, 특히 base-and-bound 가상화는 효율적이다. 하지만 동적 재배치 자체는 비효율적이다! 동적 재배치를 통해 할당된 영역은 내부 공간이 사용되지 않기 때문에 내부 단편화 (internal fragmentation) 가 발생하여 낭비되기 때문이다. 물리 메모리의 이용률을 높이고 내부 단편화를 방지하기 위해 더 정교한 기법이 필요하다. 그 기법으로 일반화된 베이스와 바운드 기법인 세그멘테이션 (segmentation) 이 등장한다.