Address Translation (주소 변환)

Donghyeon Park·2025년 1월 2일

OS address translation 운영체제

Operating System

목록 보기

4/20

본 글의 내용은 Operating Systems: Three Easy Pieces의 Mechanism: Address Translation 챕터를 정리한 것입니다.

☑️ 개요

CPU 가상화에서는 Limited Direct Execution 메커니즘에 집중하였다.
LDE의 기본 아이디어는 HW가 프로그램을 직접 실행하되, 특정 시점에는 OS가 개입하여 작업을 올바르게 처리하자는 것이다.
중요한 시점에 개입하여 제어권을 유지하고, 실행 중인 프로그램을 최대한 방해하지 않으면서 효율적인 가상화를 제공한다.
메모리 가상화에서도 효율성과 올바른 제어를 모두 달성하는 것이 목표이다.
- 여기서 효율성이란 HW 지원을 활용한다는 의미이다.
- HW 지원은 매우 단순한 수준(레지스터 몇 개)에서 상당히 복잡한 수준(TLB, 페이지 테이블 등)으로 확장된다.
- 제어란 앱이 자신의 메모리 외에 어떤 메모리에도 접근할 수 없도록 OS가 보장하는 것이다. (여기에도 HW의 도움이 필요하다)
- 마지막으로 유연성을 달성하려면, 가상 메모리 시스템에 조금 더 많은 것이 필요하다.
그럼 효율적이고 유연하며, 제어 가능한 메모리 가상화는 어떻게 달성할 수 있을까?
일반적인 접근 방법은 HW based address translation, 줄여 말해 address translation(주소 변환)이다.
주소 변환을 통해 Instruction이 제공하는 가상 주소를 실제 주소로 변경한다.
이런 방식은 단순 HW만으로는 불가능하고, OS가 개입하여 메모리를 관리하고, 사용 중인 위치/사용 중이지 않은 위치를 추적하여 메모리 제어를 유지해야 한다.
결국 실제로는 다수의 프로그램이 동시에 메모리를 공유하고 있지만, OS의 가상화를 통해 자신만의 개인 메모리가 있다고 착각하게 된다.

☑️ 몇가지 가정

Address Translation을 알아보기 전에 (말도 안 되는) 가정을 해보자.

유저의 Address space가 물리 메모리에 연속적으로 배치된다.
Address space가 너무 크지 않고, 물리 메모리보다 작다.
모든 Address space의 크기가 정확히 같다.

☑️ 예시: 어셈블리 코드

다음 예시를 보자.

컴파일러는 위 코드를 아래와 같은 어셈블리로 변환한다.

이것을 Address space와 함께 확인해보자.

어셈블리 3줄은 Address spcae의 상위에 위치한다. (사진 상으로 128부터)

또한 x의 값 3000은 address space의 Stack에 위치하고 있다.

이 사실을 근거로 어셈블리 코드는 다음과 같은 과정을 거친다.

주소 128에서 명령어를 가져옴
명령어 실행 (주소 15KB에서 3000이라는 값을 로드)
주소 132에서 명령어를 가져옴
명령어 실행 (메모리 참조는 없음)
주소 135에서 명령어를 가져옴
명령어 실행 (주소 15KB에 값을 저장)

☑️ 프로세스의 실제 위치

프로세스의 관점에서 Address space는 0부터 16KB까지 존재한다.

하지만 이것은 메모리 가상화를 거친 결과물로, 실제로는 OS에 의해 주소 0이 아닌 다른 곳에 배치되어 있다.

위 그림을 예시로 든다면, 재배치된 프로세스는 32KB를 시작점으로 삼고 있다.

☑️ HW 기반 동적 재배치: Base & Bound

동적 재배치의 최초 기술은 base and bound라고 불리는 간단한 아이디어였다.
CPU 내에 두 개의 HW 레지스터가 필요한데, 하나는 base 레지스터, 하나는 bound(제한) 레지스터라고 불렸다.
이 두 레지스터로 프로세스가 자신의 메모리 영역에만 접근하고, 주소 공간을 원하는 물리 메모리의 위치에 배치할 수 있게 된다.
이 형태에서는, 각 프로그램이 주소 0에 로드되는 것처럼 컴파일된다.
그러나 OS는 프로그램이 실제 메모리에 로드될 위치를 결정하고, base 레지스터를 그 값으로 설정한다. (예시처럼 프로세스가 물리 주소 32KB에 로드되기로 결정되면 base 레지스터가 이 값을 저장한다.)
이제 프로세스에 의해 메모리를 참조하기 시작하면, 다음과 같은 방식으로 주소를 변환한다. HW를 기반으로 주소를 변환하는 것이다.
```
실제 주소 = base 레지스터 값 + 가상 주소
```
이전에 봤던 어셈블리 예제에 위 방식을 적용하면, 가상 주소 = 128, 실제 주소 = 32KB 이므로 32768+128=32896의 실제 주소를 얻을 수 있다.
위와 같은 기술(주소 변환, 주소 재배치)은 런타임에 이루어지며,
프로세스가 실행을 하고 나서도 주소 공간을 옮길 수 있기 때문에 동적 재배치(dynamic relocation)라고도 부른다.

그럼 bound 레지스터는 무슨 역할을 할까? 메모리를 보호하기 위해 존재한다.
프로세서가 특정 메모리 참조가 합법적인지 확인하기 위해 해당 메모리 참조가 bound를 넘어서지 않는지 확인한다.
두가지 방식을 사용할 수 있는데, base부터 가능한 용량 한계를 저장하거나 실제로 주소의 끝이 되는 값을 저장한다.
base & bound 레지스터는 칩에 유지되는 HW 구조라는 것을 유의해야 한다.
주소 변환을 돕는 프로세서의 일부를 MMU(Memory management unit, 메모리 관리 장치)라고 부르기도 한다.

☑️ HW가 지원하는 기능 정리

결국 HW가 지원하는 기능은 다음과 같다.

HW 지원 사항	이유
User / Kernel Mode	privileaged operation이 악용되지 않기 위해
Base & Bound 레지스터	address translation(메모리 가상화)에 사용하기 위해
Base & Bound 레지스터를 업데이트 할 명령어	프로그램이 실행되기 전에 이 값들을 설정할 수 있어야 함
Exception handler를 등록할 privileaged operation	OS는 예외가 발생했을 때 어떤 코드를 실행할 것인지 HW에게 알려야 함
Exception을 발생시킬 능력	프로세스가 잘못된 주소에 접근하려 하거나 privileged operation을 실행하려고 할 때 예외를 발생시켜야 함

☑️ OS가 풀어야 할 문제

OS 이슈	이유
메모리 관리	새 프로세스를 위한 메모리 할당과 종료되는 프로세스에게서 메모리 회수. 일반적으로 free list로 관리한다.
Base/bound 관리	Context switching시에 base/bound 레지스터 값을 바꿔주어야 함
예외 처리	올바르게 작동하지 않는 프로세스를 제어해야 함

메모리 가상화를 구현하기 위해, 프로세스가 생성될 때 OS는 해당 프로세스가 차지할 메모리의 실제 공간을 찾아야 한다.
앞서 세웠던 가정에 따른다고 쳐보자. 각 주소 공간이 물리 메모리보다 작고, 각각 같은 크기라면?
- 여유 공간을 하나의 배열로 보고, 배열의 빈 자리를 추적하기만 하면 된다.
- 이 빈 자리는 free list라고 불리는 데이터 구조에서 검색하며,
  사용할 공간은 사용 중이라고 표시하면 된다. (물론 가변 크기의 주소 공간을 사용하면 더 복잡하다)

결국 free list, 프로세스가 종료될 때 메모리 회수,
Context switching 시에 base & bound 레지스터 저장 및 복원,
예외 처리 능력이 OS에게 요구 된다.
(이 base & bound 레지스터 값은 PCB 혹은 process structure에 저장된다.)
(실행 중이지 않은) 프로세스의 주소 공간은 OS에 의해서 굉장히 쉽게 수정될 수 있다.
OS가 주소 공간을 수정할 때, 해당 주소 공간을 새 위치로 복사하고 base 레지스터를 갱신한다.
프로세스가 다시 시작되면 새 base 레지스터 값을 통해 주소 변환이 진행된다.
예외 처리기(exception handler)는 OS가 부팅 시에 설치된다. 일반적인 처리 방식은 프로세스를 종료하는 것이다.

✅ 요약

주소 변환(address translation)은 Limited Direct Execution의 확장된 개념이다.
주소 변환을 통해 OS가 프로세스의 모든 메모리 접근을 제어하고, address space 내에 머물도록 강제할 수 있다.
이 기술의 핵심은 가장 주소가 물리 주소로 HW 지원을 통해 신속하게 수행된다는 것이고, 매우 효율적이다. bound 레지스터 덕분에 메모리 영역을 보호할 수도 있다.
하지만 이 간단한 동적 재배치 방식에는 비효율성도 있는데, 프로세스가 똑같은 주소 공간 크기를 차지하기 때문에, 스택과 힙 사이에 빈 공간이 생기는 내부 단편화가 발생한다.
이것을 해결하기 위해 segmentation이 등장하게 된다.

Donghyeon Park

Android 4 Life

이전 포스트

Multi-level Feedback Queue (Scheduling: Multi-level Feedback Queue)

다음 포스트