[OS] 메모리 가상화를 위한 주소 변환 (Address Translation) - OS 공부 9

안녕하세요 Pingu입니다!

 

지난 글에서 메모리를 사용하기 위한 Memory API들과 사용 시 주의점에 대해 알아보았는데요, 이번 글에서는 이제 본격적으로 메모리 가상화를 위한 메커니즘을 알아보려고 합니다. 이번 글에서 알아볼 메커니즘은 Address Translation(주소 변환)입니다. 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 15 - Address Translation 입니다!

Mechanism: Address Translation

CPU 가상화를 공부할 때 배운 Limited Direct Execution에 대해 기억하시나요? 간단히 짚고 넘어가자면 프로그램을 하드웨어에서 직접 실행하도록 하는데 특정 시점(프로세스가 system call 발생 시, 타이머 인터럽트 발생 시)에는 OS가 프로그램의 실행에 관여하는 방식이었죠. 즉 하드웨어의 지원과 OS의 관리로 CPU를 효율적으로 제어하는 가상화하는 방법이었습니다.

 

그렇다면 메모리를 가상화하는 방법은 어떻게 구현할 수 있을까요? CPU 가상화와 마찬가지로 메모리 가상화도 효율성을 위해서 하드웨어의 지원을 받으며 OS가 제어를 하는 방법으로 구현할 수 있습니다. 여기서 OS의 역할은 프로그램이 자신에게 할당된 메모리에만 접근하도록 제어하는 것입니다. 이를 통해 프로그램은 다른 프로그램으로부터 자신을 보호할 수 있게 됩니다!

 

Limited Direct Execution에 대한 일반적인 접근 방식에 메모리 가상화를 도입할 수 있는 방법은 Address Translation(주소 변환)이라는 기술입니다. 주소 변환을 통해 하드웨어는 virtual address(가상 주소)를 physical address(실제 주소)로 변환합니다. 따라서 모든 메모리 참조에서 프로그램 메모리 참조를 실제 주소로 변환하기 위해 하드웨어가 주소 변환을 수행하게 됩니다.

 

하지만 CPU 가상화 때와 마찬가지로 메모리 가상화를 하드웨어만 사용해서는 할 수 없습니다. OS가 적절히 개입하여 메모리를 관리하고 메모리의 어떤 부분이 사용 중인지 어떻게 사용할 것인지를 제어해줘야 합니다.

 

프로그램은 코드와 데이터가 있는 자체 메모리를 가지고 있습니다. 보통은 프로그램을 동시에 여러 개를 실행하게 되는데 CPU 가상화의 경우처럼 메모리도 하나의 메모리를 여러 개의 프로그램이 함께 사용하게 됩니다. 이런 상황에서 메모리 가상화를 통해 사용하기 쉽게 추상화하는 방법을 이번 글에서 알아보도록 하겠습니다!

 

Assumptions

메모리 가상화를 쉽게 이해하기 위해 몇 가지 가정을 세워보겠습니다. 우선 프로그램은 메모리 공간을 연속적으로 사용한다고 가정하겠습니다. 즉 메모리의 여기저기 흩어진 상태가 아니고 시작과 끝이 모두 연속적으로 사용한다는 말입니다. 다음 가정은 필요한 메모리가 실제 메모리보다 항상 작다고 가정하겠습니다. 마지막으로 모든 프로그램은 모두 같은 사이즈의 메모리를 사용한다는 가정을 세우겠습니다. 정리하면 아래와 같습니다!

1. 프로세스는 연속적인 메모리 공간을 사용한다.
2. 프로세스가 필요한 메모리는 항상 실제 메모리보다 작다
3. 모든 프로세스는 같은 크기의 메모리를 사용한다.

위의 가정은 실제와는 거리가 먼 가정들이며 메모리 가상화를 쉽게 이해하기 위해 잠시만 사용할 가정들입니다. 이 글에서 메모리 가상화에 대해 알아보면서 위의 세 가지 가정들을 없애며 실제 메모리 가상화 방법에 도달할 예정입니다!

An Example

주소 변환을 하기 위해 할 일과 메커니즘의 필요성에 대해 알아보기 위해 간단한 예제를 보겠습니다!

주소 공간이 위의 그림과 같은 프로세스가 있다고 생각해보겠습니다. 그리고 이것은 프로그램이 자신이 갖고 있다고 착각하는 가상 주소 공간입니다. 0KB~2KB에 존재하는 Program Code 부분을 보면 어셈블리어로 뭔가 적혀있는데 이를 C언어로 표현으로 하면 아래와 같습니다.

void func() {
    int x = 3000;
    x = x + 3;
}

이를 컴파일러로 변환하여 어셈블리어로 나타낸 것이 위의 그림에 적힌 코드입니다. 잠깐 어셈블리어도 보고 가면 아래와 같습니다.

128: movl 0x0(%ebx), %eax // 0+ebx에 존재하는 데이터를 eax에 옮깁니다.
132: addl $0x03, %eax // eax의 값을 3만큼 증가시킵니다.
135: movl %eax, 0x0(%ebx) // 증가시킨 값을 다시 0+ebx에 옮깁니다.

즉 C언어에서 정수형 변수를 선언하고 3을 더하는 작업이 위와 같이 처리되는 것을 알 수 있습니다. 그렇다면 이를 메모리의 관점에서 보겠습니다. 위의 코드가 주소 공간에서 어떻게 처리되는지 보겠습니다. 지역변수들은 stack에 저장된다고 했었죠? 즉 x라는 변수가 stack에 저장되며 위의 그림에서도 확인할 수 있습니다. 그럼 stack에 있는 x의 값을 3 증가시키는 과정을 살펴보겠습니다.

• 주소 128에서 명령어를 가져옵니다.
• 주소 128 명령을 실행합니다. (x의 값을 stack공간에서 로드하는 것) 주소 132에서 명령어를 가져옵니다.
• 주소 132의 명령어를 실행합니다. (이 때는 메모리의 참조가 없습니다.)
• 주소 135의 명령어를 가져옵니다.
• 주소 135 명령을 실행합니다. (15KB 주소에 저장하는 것)

아까 그림에서 주소 공간의 크기는 16KB였습니다. 즉 프로그램은 저 공간에서만 메모리 참조를 해야 하는 것입니다. 그런데 아까 본 그림은 가상 주소 공간이었는데 이를 실제 메모리에서는 어떻게 처리해야 할까요? 다시 말하면 가상 주소 공간의 주소는 0KB~16KB였는데 실제 메모리에서는 이 주소를 사용하는 것이 아닌 적절히 변환을 해줘야 한다는 말이 됩니다! 그럼 실제 메모리를 한 번 살펴보겠습니다.

위의 그림을 보면 실제 메모리는 0KB~64KB의 크기를 가집니다. 그리고 아까 본 프로세스의 실제 위치는 32KB~48KB의 위치에 존재하는 것을 볼 수 있습니다. 즉 0KB~16KB의 가상 주소를 32KB~48KB의 실제 주소로 변환하는 작업이 필요하게 되는 것이죠! 또한 지금은 크게 상관없지만 16KB~32KB, 48KB~64KB 공간은 사용하고 있지 않습니다. 이를 관리하는 작업도 필요할 것 같네요!

 

이렇게 가상 주소 공간을 실제 메모리의 주소 공간으로 변환하는 것을 Relocation(재배치)라고 하며 이를 어떻게 하는지 알아보겠습니다.

Dynamic (Hardware-based) Relocation

우선 하드웨어 기반 주소 변환에 대해서 알아보겠습니다. Dynamic Relocation(동적 재배치)라는 기술은 base, bounds라는 아이디어를 사용한 단순한 기술입니다. 이는 주소 변환, 주소 재배치와 같은 말이니 헷갈리지 않으셔도 됩니다! 이 기술을 위해서는 CPU에 2개의 하드웨어 레지스터가 필요합니다. 하나는 base 레지스터, 하나는 limit 레지스터(bounds 레지스터라고도 합니다.)입니다. 이 2개의 레지스터를 사용하면 실제 메모리의 원하는 위치에 가상 주소 공간을 배치할 수 있고 프로세스가 자신의 주소 공간에만 접근할 수 있도록 해줍니다.

 

위의 그림과 같이 base 레지스터와 limit 레지스터를 사용하여 가상 주소 공간을 실제 메모리에 재배치할 수 있습니다. 위의 그림을 설명하자면 base 레지스터는 가상 주소 공간이 실제 메모리에 재배치되었을 때 주소 공간의 시작 부분을 가리킵니다. 위의 예에서는 32KB가 되겠네요! 그리고 limit 레지스터는 가상 주소 공간의 크기를 나타냅니다. 위의 예에서는 16KB가 되겠죠? 그럼 이 두 개의 레지스터를 사용해서 주소변환을 하는 과정을 살펴보겠습니다.

 

우선 base 레지스터로 실제 메모리의 주소를 나타내는 식은 아래와 같습니다.

실제 메모리 주소 = 가상 주소 + base 레지스터

이 말이 무엇인가는 예를 보며 이해해보겠습니다. 우선 아까 본 가상 주소 128에 위치하던 어셈블리 명령어를 가져와보겠습니다.

128: movl 0x0(%ebx), %eax

우선 program counter (PC)는 128로 설정됩니다. 위의 명령어의 주소인 128은 가상 주소였죠? 이를 실제 주소로 바꾸는 것은 아까 위에서 본 식을 사용하면 됩니다.

실제 메모리 주소 = 가상 주소 + base 레지스터
// 주소 128을 변환
실제 메모리 주소 = 128 + 32KB

어떤가요? 이렇게 쉽게 변환할 수 있습니다! 그럼 이제 하나의 의문이 생기지 않나요? 분명 하드웨어 기반 주소 변환에는 base, limit 레지스터가 필요하다고 했는데 limit 레지스터는 사용하지도 않고 주소변환이 성공했습니다. 이는 변환하려는 가상 주소의 값이 128이었기 때문인데요, 위의 예에서 limit 레지스터는 16KB였습니다. 이 보다 작은 값을 변환할 땐 제한을 주지 않고 변환을 하는 것입니다. 그렇다면 만약 가상 주소 17KB를 변환하려고 한다면 어떻게 될까요? Limit 레지스터의 값보다 큰 값이므로 이는 오류를 발생합니다. 이렇게 프로세스가 다른 프로세스의 메모리에 접근을 하지 않도록 보호해주는 역할이 limit 레지스터의 역할입니다.

 

그럼 limit 레지스터의 역할을 예제를 통해 살펴보겠습니다. 가상 주소 공간의 크기가 4KB인 프로세스가 실제 메모리의 16KB에 로드되었다고 가정하겠습니다. 그렇다면 limit 레지스터의 값은 4KB가 되겠죠? 이를 기억하며 아래 예를 살펴보겠습니다.

다른 변환들은 모두 잘 됐는데, 가상 주소 4400을 변환할 때 오류가 발생했습니다. 이유는 limit 레지스터의 값이 4KB 즉 4096인데 이것보다 큰 값을 변환하려고 했기 때문입니다. 물론 limit 레지스터의 값보다 큰 값도 오류를 발생하지만 음수도 오류를 발생합니다!

 

Base, limit 레지스터는 CPU에 존재하는 하드웨어라는 점을 기억하셔야 합니다. 이렇게 주소변환을 돕는 프로세서 부분을 MMU(메모리 관리 장치)라고 부릅니다. 

Hardware Support: A Summary

이제 주소 변환을 위해 하드웨어가 지원하는 것이 어떤 것인지 알았습니다. 이를 요약해보면 아래와 같습니다.

1. Kernel, User 모드가 구분되어야 합니다.
2. Base, limit 레지스터를 제공해야 합니다.
3. Base, limit 레지스터로 가상 주소를 변환하는 능력, 잘못된 가상 주소 공간을 체크하는 능력을 제공해야 합니다.
4. 오류가 발생했을 때 처리할 수 있는 능력이 있어야 합니다.
5. 오류가 발생했을 때 오류를 발생할 수 있어야 합니다.

이렇게 쓰고 보니 당연한 말들을 나열해 둔 것 같네요. 첫 번째 것만 다시 보자면 Base, limit 레지스터의 값을 수정할 때, 오류를 발생시킬 때, 오류 핸들러의 위치를 찾을 때는 Kernel 모드에서 진행해야 한다는 말입니다. 즉 2,3,4,5를 위해서는 kernel 모드에서 진행해야 한다는 것이죠.

Operating System Issues

그럼 이제 하드웨어가 주소 변환에서 어떤 역할을 하는지 알았으니 OS의 역할을 살펴보겠습니다. 가상 메모리의 base, limit를 구현하기 위해서 OS가 개입해야 하는 시점들이 존재하는데 이를 알아보겠습니다.

 

첫 번째는 프로세스가 생성될 때 프로세스의 주소 공간을 위해 실제 메모리에서 공간을 찾아야 합니다. 아까 글의 도입부에서 정의한 가정들을 기억하시나요? 그중에 항상 주소 공간이 실제 메모리보다 작고 모든 프로세스는 같은 크기를 갖는다는 가정이 있었는데, 이 가정이 있을 때는 OS에게 빈 공간을 찾는 것이 아주 쉬운 일입니다. 하지만 처음 가정을 세울 때도 말했듯 이는 비현실적인 상황이며 후에 이를 없앨 것이라 했었죠? 이 가정들을 없앤다면 OS는 새로운 주소 공간을 찾고 이를 사용 중이라고 표시해줘야 하며 프로세스의 주소 공간의 크기들이 다르다면 이를 처리할 방법도 생각해야 합니다. 따라서 이를 없앴을 때의 방법을 알아봐야 합니다.

 

두 번째는 프로세스가 종료되면 종료된 프로세스가 사용하던 메모리 공간을 다른 프로세스나 OS가 사용하기 위해서 반환해야 합니다. OS는 이렇게 반환된 메모리를 사용 가능한 목록에 넣고 정리해야 합니다.

 

세 번째는 OS는 context switch가 발생할 때 몇 가지 단계를 추가적으로 수행해야 합니다. 각 CPU에는 하나의 base, limit 레지스터만 존재하는데, 모든 프로세스는 각각의 base, limit 레지스터의 정보를 가지고 있어야 합니다. 따라서 OS는 context switch가 발생할 때 이러한 정보를 저장하고 복원하는 작업을 해줘야 합니다. 이러한 정보를 프로세스 구조나 프로세스 제어 블록(PCB)에 저장해야 context switch가 원활하게 작동할 수 있습니다. 프로세스가 중지되면 OS가 메모리의 어떠한 위치에서 다른 위치로 쉽게 이동할 수 있다는 점에 유의해야 합니다.  프로세스의 주소 공간으로 이동하기 위해서 OS는 먼저 프로세스의 스케줄링을 취소하고 현재 위치에서 새 위치로 주소 공간을 복사합니다. 마지막으로 OS는 저장해둔 base 레지스터 정보로 base 레지스터를 업데이트하여 새로운 위치를 가리키게 됩니다. 

 

네 번째는 OS가 위에 설명한 대로 예외가 발생했을 때 호출할 핸들러나 함수를 제공해야 합니다. OS는 이러한 것들을 부팅 시 설치하게 됩니다. 예외를 처리하는 예를 보며 이해해보겠습니다. 예를 들어 프로세스가 limit 레지스터의 값보다 큰 값에 접근하려고 하려는 상황이라고 하겠습니다. 이때 CPU는 예외를 발생시키게 되고 OS는 이 예외를 처리할 준비가 되어있어야 합니다. 보통 이러한 상황에서 OS는 프로세스를 종료해버립니다.

이 네 가지를 정리하면 위와 같이 정리할 수 있습니다.

 

그럼 이제 하드웨어와 OS에서 주소 변환을 할 때 어떤 역할을 하는지 알았으니 이를 전체적으로 보며 이해해보겠습니다. 먼저 OS가 부팅할 때 주소변환을 위해 오류처리 핸들러, 함수들을 설치한다고 했는데 그 부분을 보겠습니다.

부팅할 때 OS는 trap table, process table, free list를 초기화하고 타이머 인터럽트를 시작하는 것을 볼 수 있습니다. 하드웨어는 system call 핸들러, 타이머 핸들러, 잘못된 메모리 접근 시 사용할 핸들러, 잘못된 명령에 대한 핸들러의 위치를 기억합니다. 이렇게 준비를 했으니 이제 실제 프로그램을 실행시켜서 주소 변환이 일어나는 과정을 살펴보겠습니다.

위의 예에서는 A, B 두 개의 프로세스를 수행합니다. 제가 구분이 쉽게 색을 다르게 하여 표시했는데 괜찮으신가요? 우선 주황색 부분을 살펴보겠습니다. 주황색 부분은 A 프로세스의 수행 과정입니다.  OS에서 A 프로세스를 위한 메모리를 할당해주고 base, limit 레지스터를 A 프로세스에 맞게 설정합니다. 그런 뒤 하드웨어에서 주소 변환을 하여 A 프로세스를 수행합니다. 그러다 타이머 인터럽트가 발생하게 되고 B 프로세스로 context switch를 하려고 합니다. Context switch를 처리하는 부분이 빨간색 부분입니다. A, B 프로세스의 base, limit 레지스터의 정보를 처리하는 부분이죠! 그런 뒤 B 프로세스를 수행합니다. 이 부분은 초록색 부분입니다. 그런데 B 프로세스가 잘못된 메모리에 접근하려고 해서 오류가 발생하게 되고 결국 OS는 B 프로세스를 kill 합니다.

 

위의 과정에서도 볼 수 있듯 프로세스는 CPU에서 직접 실행되는 Direct Execution 방법을 사용합니다. 그리고 특정 상황에서만 OS가 관여하는 Limited Direct Execution 방법인 것을 볼 수 있습니다!

Summary

이번 글에서는 Address Translation(주소 변환)이라고 하는 가상 메모리에서 사용되는 메커니즘을 사용해서 Limited Direct Execution의 개념을 확장했습니다. 주소 변환의 효율성의 핵심은 가상 주소를 실제 메모리의 주소로 변환하는 하드웨어의 지원이었습니다. 이를 통해 프로세스는 자신의 가상 주소가 실제 메모리의 주소인 것으로 착각하게 만드는 가상화를 수행하게 된 것입니다!

 

또한 base, limit 레지스터를 사용한 동적 재배치 기술로 가상화를 하는 방법에 대해 알아봤습니다. 이를 사용하면 주소변환도 쉽게 처리되며 프로세스를 보호할 수 도 있었습니다. 그리고 OS의 개입으로 문제들을 처리할 수 있었습니다.

 

하지만 이번 글에서 알아본 동적 재배치 기술은 비효율적입니다. 이유는 잠깐 아까 본 그림을 다시 보자면..

위의 그림에서 32KB~48KB의 부분이 프로세스에게 할당된 메모리였습니다. 그런데 stack, heap의 사이에 사용되지 않는 공간이 엄청 큰 것을 볼 수 있습니다. 이는 곧 메모리 낭비이며 이번 글의 도입부에서 정의한 가정 때문에 일어난 일입니다. 따라서 이러한 점을 개선한 방법이 필요하며 이는 segmentation이라고 알려진 base, limit을 일반화하는 방법입니다. 이는 다음 글에서 알아보도록 하겠습니다!

 

감사합니다.