Address Translation

CPU 가상화를 구현하기 위해 우리는 LDE(limited direct executuon) 라는 방법을 살펴보았다. 그렇다면 메모리 가상화를 구현하는 방법은 뭘까?

LDE라는 접근 방식에 메모리 가상화를 도입할 수 있는 방법은 주소 변환 Address Translation 이라는 방법이다. CPU 가상화 때 처럼, OS와 하드웨어는 메모리 가상화를 위해 협력한다. 효율적인 메모리 가상화를 위한 방법들을 알아보자

Assumptions 가정

운영체제 스케줄링 정책을 살펴보기 위해 비현실적인 가정을 했던 것 처럼, 메모리 가상화 방법을 알아보기위해 비현실적인 가정을 해보겠다.

• 사용자의 주소 공간이 물리적 메모리에 연속적으로 배치되어야 한다.
• 주소 공간의 크기가 너무 크지 않다.(물리적 메모리보다 작다.)
• 각 주소공간의 크기가 같다.

An Example 예시

void func() {
    int x = 3000; // thanks, Perry.
    x = x + 3; // 우리가 관심을 가지는 코드 라인
    ...
}

컴파일러가 위의 c 코드를 어셈블리로 변환한다면 아래와 같다.

128: movl 0x0(%ebx), %eax ; 0+ebx를 eax에 로드합니다.
132: addl $0x03, %eax ; eax 레지스터에 3을 더합니다.
135: movl %eax, 0x0(%ebx) ; eax 값을 메모리(0+ebx)에 다시 저장합니다.

이 프로세스는 아래 사진과 같은 메모리 구조를 가진다.
명령 코드는 주소 128에 위치하고, 변수 x의 값은 주소 15KB에 위치하고 초기 값은 스택에 표시된것 처럼 3000이다.

이 명령이 실행되면, 프로세스의 관점에서 다음과 같은 메모리 엑세스가 발생한다.

• 주소 128에서 명령어를 가져온다.
• 이 명령을 실행한다. (x의 값을 스택에서 로드load)
• 주소 132에서 명령어를 가져온다.
• 이 명령을 실행한다. (메모리 참조 없음)
• 주소 135에서 명령어를 가져온다.
• 이 명령을 실행한다. (x의 값을 스택에 스토어store)

방금과 같은 상황에서는 프로세스의 주소 공간이 0에서 부터 시작한다. 하지만 아래 사진처럼 0에서 부터 시작하지 않는 경우도 있다. 이럴때 메모리 참조는 어떻게 해야할까?

Dynamic (Hardware-based) Relocation 동적 재배치

가상 주소를 실제 주소로 변환하는 것을 재배치(Relocation)라고 한다. 하드웨어 기반 주소 변환을 이해하기 위해 1950년대 후반 시분할 머신의 base and bounds 라고 불리는 아이디어를 살펴보겠다. 이 기법은 동적 재배치(dynamic relocation)라고도 불린다.

CPU 내에 두 개의 레지스터가 필요하다. 하나는 베이스(base) 레지스터이고, 하나는 바운드(bound) 레지스터이다. 각 프로그램은 0번 주소에 로드된 것처럼 행동한다. 이때 OS는 base 레지스터를 기준으로 물리적 메모리의 어디에 로드할지 결정한다. 물리적 주소 = 가상 주소 + 베이스

더 잘 이해하기 위해 이전의 예시를 살펴보겠다.
128: movl 0x0(%ebx), %eax 에서 PC가 128로 설정되었다. 먼저 32KB(32768)의 base 레지스터 값에 128을 더하여 물리적 주소 32896을 얻는다. 하드웨어는 이 주소에서 명령을 가져오고 프로세서는 명령을 실행한다.

이때 bound 레지스터는 보호를 돕는다. 위의 예시에서 bound 레지스터는 항상 16KB이다. 프로세스가 생성한 가상 주소가 음수이거나 bound 레지스터 값보다 크면 CPU는 예외를 발생시키고 프로세스는 종료된다. 따라서 bound 레지스터는 주소가 경계(bound)에 있도록 보호한다.

base bound 레지스터는 CPU에 존재하는 하드웨어이다. 이렇게 프로세서에서 주소 변환을 돕는 부분을 메모리 관리 장치(MMU)라고 부른다.

정적 재배치 static relocation
초기 하드웨어 지원이 없던 시기에 일부 시스템은 소프트웨어 방법으로 재배치를 수행했다.
그 방법은 실행 파일의 주소를 물리적 메모리에서 원하는 offset으로 재작성 하는 것이다.
예를 들어 명령어가 주소 1000에서 레지스터로 로드되는 경우(예: movl 1000, %eax)
그리고 프로그램의 주소 공간이 주소 3000에서 시작 된다면,
로더는 각 주소를 3000만큼의 offset으로 재작성한다.(예: movl 4000, %eax)
여기에는 문제가 있는데, 
첫 번째는 보호를 제공하지 않는다는 것, 
두 번째는 주소 공간의 재 배치가 어렵다는 것이다.

Hardware Support: A Summary 하드웨어 지원 요약

메모리 가상화를 위해 하드웨어가 제공해야하는 지원을 요약해보겠다.

• user , kernel 모드로 구분되어야한다.
  OS는 커널 모드에서 실행되고, 응용 프로그램은 사용자 모드에서 실행된다.

• base , bound 레지스터를 제공해야한다.
  CPU에는 MMU의 일부인 레지스터 쌍이 있다.

• 가상주소를 변환하는 능력 , 잘못된 가상 주소 공간을 체크하는 능력을 제공해야한다.

• base, bound 레지스터를 업데이트 할 수 있어야한다.

• 오류 발생시 처리 능력이 있어야한다.
  OS는 예외가 발생할 경우에 실행할 코드를 하드웨어에 알려줄 수 있어야 한다.

• 오류가 발생했을때, 오류를 발생시킬 수 있어야한다.
  메모리에 잘못 엑세스하려고 할 때(out of bound) 예외를 일으킬 수 있어야한다.

  사용하지 않는 메모리를 추적하기 위해 free list를 사용할 수 있다.
  free list 는 할당되지 않은 메모리를 연결리스트로 연결한다.

Operating System Issues 운영체제의 문제

동적 재배치(Dynamic Relocation)를 위해 하드웨어가 base, bound 레지스터를 지원한 것처럼 OS도 해야하는 일이 있다.

첫 번째, 프로세스가 생성될 때 OS는 해당 프로세스의 주소 공간(address space)에 메모리를 할당해야한다. 우리의 가정-각 주소 공간이 물리적 메모리 보다 작고 서로 동일한 크기라는-덕분에 이 작업은 OS에게 쉽다. OS는 물리적 메모리를 슬롯 배열로 보고, 각 슬롯의 사용 여부를 추적할 수 있다. 새로운 프로세스가 생성될 때, OS는 free list를 검색하고, 그것을 사용 중으로 표시해야한다.

두 번째, 프로세스가 종료될 때 OS는 해당 메모리를 회수해야한다. 메모리를 free list로 되돌리고 관련 데이터 구조를 정리해야한다.

세 번째, 문맥 전환(context switching)시 base, bound 레지스터 값을 저장,복원헤야한다. 프로세스를 실행,중지 결정시 base, bound 레지스터 값을 프로세스 구조나 PCB에 저장하여 각 프로세스에 맞는 값으로 업데이트 해야 한다.
프로세스가 중지되어 있는 경우, OS는 메모리에서 주소 공간을 다른 위치로 이동할 수 있다. 그러기 위해서 OS는 해당 프로세스를 스케줄링 하지 않고, 주소공간을 새위치로 복사, base 레지스터 값을 업데이트한다.

네 번째, OS는 예외를 처리할 수 있는 기능을 제공해야한다. OS는 부팅 시 이러한 처리기를 설치한다. 만약, 프로세스가 잘못된 메모리에 엑세스 하려 한다면 CPU가 예외를 일으킨다. 이 때 OS는 조치를 취해야하며 대부분은 종료시킨다.

아래 사진은 OS와 하드웨어가 부팅 시 준비를 하는 모습,
실제 프로세스를 실행시키고, context switching, B가 잘못된 접근을 하여 OS가 종료시키는 모습이다.