09. Address Translation¶

주소 변환의 원리¶

RECALL 03. Mechanism - Limited Direct Execution
프로그램은 하드웨어에서 대부분 직접 실행된다.
프로세스가 시스템 콜을 호출하거나 타이머 인터럽트가 발생할 때 등의 특정 순간에는 운영체제가 개입하여 문제가 발생하지 않도록 한다.
운영체제는 약간의 하드 웨어 지원을 받아 효율적인 가상화를 제공하기 위해 실행 프로그램에게 방해가 되지 않도록 최선을 다한다. 운영체제가 관여하여 하드웨어를 직접 제어한다.

CPU가 실행 중인 한 프로그램에서 다음 프로그램으로 전환 하는 것처럼, 많은 프로그램이 메모리를 공유한다.
→ 메모리 가상화도 비슷한 원리를 사용

메모리 가상화: 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다고 착각하게 함

폰 노이만 구조: 메모리는 유일한 작업 공간이며 모든 프로그램은 메모리에 올라와야 실행이 가능하다.

운영체제도 CPU를 사용하는 작업 중 하나이기 때문에 사용자 작업이 진행되는 동안에는 운영체제 작업이 잠시 중단된다.
운영체제 작업이 중단된 상태에서 사용자 작업으로부터 메모리를 보호하려면 하드웨어 도움이 필요하다.

• 하드웨어-기반 주소 변환(hardware-based address translation), 주소 변환(address translation)

하드웨어는 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제 존재하는 물리 주소로 변환
프로그램의 모든 메모리 참조를 실제 메모리 위치로 재지정하기 위하여 하드웨어가 주소를 변환한다.
운영체제는 하드웨어의 도움을 받아 메모리 주소를 관리한다.

• 응용 프로그램이 자기자신의 메모리 이외에는 다른 메모리에 접근하지 못하게 보장
  → 레지스터, TLB, 페이지 테이블 등 하드웨어 사용

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

가정¶

• 사용자 주소 공간은 물리 메모리에 연속적으로 배치되어야 한다.
• 논의를 단순화하기 위해 주소 공간의 크기가 너무 크지 않다고 가정한다.
• 주소 공간은 물리 메모리 크기보다 작다.
• 각 주소 공간의 크기는 같다고 가정한다.

주소 공간이 그림 18.1과 같은 프로세스가 있다고 가정하자.

void func() {  
    int x = 3000;  
    ...  
    x = x + 3; // This is the line of code we are interested in  

코드 내용은 다음과 같다.

1. 메모리에 값을 로드한다.
2. 3씩 증가시킨다.
3. 값을 다시 메모리에 저장한다.

컴파일러는 이 코드를 어셈블리 코드로 변환하고 그 결과는 x86 어셈블리로 다음과 같을 것이다.
Linux 상에서는 objdump 도구 또는 Mac OS X 상에서는 otool을 사용하여 디스어셈블한다.

사례¶

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

1. x의 주소는 레지스터 ebx에 저장되어 있다고 가정하고 이 주소에 저장되어 있는 값을 movl 명령어 (longword를 이동하는 명령어) 를 사용하여 범용 레지스터 eax에 넣는다.
2. eax에 3을 더한다
3. 마지막 명령은 eax의 값을 같은 위치의 메모리에 저장한다.

위 그림에서 코드와 데이터가 프로세스 주소 공간에 어떻게 배치되어 있는지 볼 수 있다.

세 개 명령어의 코드는 (코드) 주소 128에 위치하고 , 변수 x의 값은 (스택) 주소 15 KB에 위치한다.
그림에서 x의 초기 값은 3000이다 (스택 영역 참조).

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

이 명령어가 실행되면 프로세스의 관점에서 다음과 같은 메모리 접근이 일어난다.

• 주소 128의 명령어 fetch
• 이 명령어 실행 (주소 15 KB에서 탑재)
• 주소 132의 명령어를 반입
• 이 명령어 실행 (메모리 참조 없음)
• 주소 135의 명령어를 반입
• 이 명령어 실행 (15 KB에 저장)

프로그램 관점에서 주소 공간은 주소 0부터 시작하여 최대 16 KB까지이다. (상대 주소)
프로그램이 생성하는 모든 메모리 참조는 이 범위 내에 있어야 한다.

동적 (하드웨어-기반) 재배치¶

• 실제 메모리
  1. 운영체제: 물리 주소 0Kb 부터 16KB 차지
  2. 프로세스: 물리 주소 32 KB ~ 48KB 차지
  → 프로세스에게 메모리 주소 0부터 시작한다고 착각하게 해야함
  3. 다른 두 슬롯 (16 KB ~32 KB와 48 KB ~64 KB)은 비어 있다.

베이스와 바운드 (base-and-bound)¶

하드웨어 기반 주소 변환 ¹

이 설정에서 각 프로그램은 주소 0에 탑재되는 것처럼 작성되고 컴파일된다.

각 CPU마다 2개의 하드웨어 레지스터가 필요하다.
베이스와 바운드 레지스터는 CPU 칩 상에 존재하는 하드웨어 구조(CPU당 1쌍).

• 베이스(base) 레지스터 : CPU는 현재 진행 중인 작업의 메모리 시작 주소를 경계 레지스터 (bound register)에 저장한 후 작업을 한다.
• 바운드(bound) 레지스터 or 한계(limit) 레지스터 : 현재 진행 중인 작업이 차지하고 있는 메모리의 크기, 즉 마지막 주소까지의 차이를 한계 레지스터 (limit register)에 저장한다. 프로세스가 생성한 모든 가상 주소가 올바른 범위 안에 있는지 확인한다.

바운드 레지스터는 두 가지 방식 중 하나로 정의될 수 있다.

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

사용자의 작업이 진행되는 동안 이 두 레지스터의 주소 범위를 벗어나는지 하드웨어적으로 점검함으로써 메모리를 보호한다.

만약 두 레지스터 값을 벗어난다면 메모리 오류와 관련된 인터럽트가 발생한다.
인터럽트가 발생하면 모든 작업이 중단되고 CPU는 운영체제를 깨워서 인터럽트를 처리하도록 시킨다.
메모리 영역을 벗어나서 발생한 인터럽트의 경우 운영체제가 해당 프로그램을 강제 종료한다.

프로그램 시작 시, 운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고 베이스 레지스터를 그 주소로 지정한다.
위의 예에서 운영체제는 프로세스를 물리 주소 32 KB에 저장하기로 결정하고 베이스 레지스터를 이 값으로 설정한다.

하드웨어는 프로세스가 참조하는 가상 주소를 받아들여 데이터가 실제로 존재하는 물리 주소로 변환한다.

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

프로세스가 명령어 반입이나 데이터를 읽고 쓰기 위해 메모리를 참조하면,

1. CPU 하드웨어는 자동으로 프로세스가 참조하려는 메모리 주소에 base 레지스터 값을 더한다.
2. 또한 프로세스가 참조하려는 주소가 limit 레지스터의 값과 동일한지 혹은 큰지를 확인한다.
   → 만약 범위를 벗어난다면 메모리 참조는 중단되고 Fault가 발생한다.
   → 정상적인 범위 내라면 더한 값을 참조하려는 메모리 주소 값을 메모리 버스에 보낸다.

이 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 주소 공간을 이동할 수 있기 때문에, 동적 재배치(dynamic relocation) 라고 도 불린다.

메모리 관리 장치(memory management unit, MMU): 주소 변환에 도움을 주는 프로세서
CPU는 메모리 관리 장치(MMU) 의 일부인 추가의 레지스터 쌍을 가진다.
하드웨어는 베이스와 바운드 레지스터를 자체적으로 제공한다.

예제¶

베이스와 바운드를 이용한 주소 변환을 상세하게 이해하기 위해 하나의 예를 살펴보자.
주소 공간의 크기가 4 KB 인 프로세스가 물리 주소 16 KB에 탑재되어 있다고 가정하자. 주소 변환의 결과는 다음과 같다.

예에서 볼 수있는 것처럼 물리 주소를 얻기 위해서는 간단히 가상 주소에 베이스 주소를 더하기만 하면 된다

(가상 주소를 주소 공간 내에서의 오프셋을 나타낸다고 생각할 수 있음). 가상 주소가 너무 크거나 음수일 경우에 폴트를 일으키고 예외가 발생하게 된다.

하드웨어 요구 사항¶

03. Mechanism - Limited Direct Execution 에서 설명했듯이 두 가지 CPU 모드가 필요하다.

실행 모드:

• 특권 모드(또는 커널 모드)에서 실행하며 컴퓨터 전체에 대한 접근 권한을 가진다.
• 사용자 모드: 응용 프로그램 실행

프로세서 상태 워드(processor status word) 레지스터: CPU의 현재 실행 모드를 나타냄

하드웨어가 하는 일:

• 프로세스가 이해하는 메모리인 가상 주소를 실제 메모리 모습인 물리 주소로 변환한다.
• 하드웨어는 주소가 유효한지 검사할 수 있어야 한다.
  • 이 검사는 바운드 레지스터와 CPU 내의 일부 회로를 사용하여 이루어진다.
• 하드웨어는 베이스와 바운드 레지스터 값을 변경하는 명령어를 제공해야 한다.
  • 다른 프로세스를 실행시킬 때 운영체제가 이 명령어를 사용하여 베이스와 바운드 레지스터 값을 변경할 수 있다.
• 커널 모드 (또는 특권 모드)에서만 레지스터를 변경할 수 있다.

예외 발생 (CPU의 실행 모드 전환 기능):

• CPU는 사용자 프로그램이 바운드를 벗어난 주소로 불법적인 메모리 접근을 시도하려는 경우
  • CPU는 사용 자 프로그램의 실행을 중지하고 운영체제의 “바운드 벗어남” 예외 핸들러(exception handler) 실행시키고 프로세스를 종료시킨다.

• 사용자 프로그램이 베이스와 바운드 레지스터 값의 변경을 시도하는 경우

  • CPU는 예외를 발생시키고 “사용자 모드에서의 특권 연산 발생” 핸들러를 실행하고 프로세스 종료

• 베이스 레지스터와 바운드 레지스터:

  • 메모리 주소의 유효성을 검사할 회로
  • 베이스와 바운드 레지스터 값을 변경하는 특권(커널) 모드 명령어

운영체제 요구 사항¶

• 베이스와 바운드 방식의 가상 메모리 구현을 위한 운영체제가 반드시 개입되어야 하는 중요한 세 개의 시점

1. 프로세스가 생성될 때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야 한다.
   
   a. 물리 메모리의 크기보다 작고
   b. 크기가 일정하다

라는 가정하에서는 운영체제가 쉽게 처리할 수 있다. (가변 크기는 더 복잡함)

운영체제는 물리 메모리를 슬롯의 배열로 보고 각 슬롯의 사용여부를 관리한다.

cf ) 빈 공간 리스트(free list): 새로운 프로세스가 생성되면 운영체제는 새로운 주소 공간 할당에 필요한 영역을 찾기 위한 자료 구조.

1. 프로세스가 종료할 때 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있게 해야 한다.
   프로세스가 종료하면, 운영체제는 종료한 프로세스의 메모리를 다시 빈 공간 리스트에 넣고 연관된 자료 구조를 모두 정리한다.
   

2. 문맥 교환 시 베이스와 바운드 레지스터의 값의 쌍을 저장하고 복원한다.
   
   - 프로세스 구조체(process structure), 프로세스 제어 블럭(process control block, PCB)
   운영체제는 프로세스를 전환하거나 중단시키기로 결정하면 메모리에 존재하는 프로세스 별 자료 구조 안에 베이스와 바운드 레지스터의 값의 쌍을 저장하고 복원할 때 쓰이는 자료구조

운영체제가 메모리의 현 위치에서 다른 위치로 주소 공간을 비교적 쉽게 옮길 수 있다는 사실에 주목해야 한다.
프로세스의 주소 공간을 이동시키려면 운영체제는 먼저 프로세스의 실행을 중지시킨다.
그런 후 운영체제는 현재 위치에서 새 위치로 주소 공간을 복사한다.

• 운영체제는 프로세스 구조체에 저장된 베이스 레지스터를 갱신하여 새 위치를 가리키도록 한다.

프로세스가 실행을 재개하면 새로운 베이스 레지스터가 복원되고 다시 실행을 시작하고, 명령어와 데이터가 전혀 다른 새 위치에 존재한다는 사실을 인식하지 못한다.

• 문맥 교환을 이용한 메모리 위치 변경

  중단하는 프로세스의 메모리 위치를 비교적 쉽게 변경 가능.

  1. 프로세스의 실행을 중지
  2. 현재 위치에서 새 위치로 주소 공간을 복사
  3. PCB에 저장된 베이스 레지스터의 값 갱신
  4. 프로세스 실행 재개 → 새 베이스 레지스터 값으로 복원

1. 운영체제는 예외 핸들러 또는 호출될 함수를 제공해야 한다.

운영체제는 부팅할 때 커널 명령어를 사용하여 이 핸들러를 설치한다.
프로세스가 바운드 밖의 메모리에 접근하려는 경우 CPU는 예외를 발생시키고 프로세스를 종료한다.

→ 부팅할 때 컴퓨터를 사용 가능한 상태로 만들기 위하여 제한적 직접 실행의 기본적인 접근 방식을 토대로 운영체제가 하드웨어/OS의 상호작용을 타임라인으로 정리한 자료

• 프로세스 (Process A)

  • 실행을 시작할 때 메모리 변환은 운영체제의 개입 없이 하드웨어에 처리

• 타이머 인터럽트가 발생

• 운영체제는 Process B로 전환한다.

  • Process B는 불법적인 주소에 잘못된 탑재를 실행한다.
  • 그 시점에 운영체제가 개입하여 프로세스를 끝낸 후 B의 메모리를 해제하고 프로세스 테이블에서 해당 항목을 제거하여 정리한다.

프로세스가 잘못된 행동을 했을 때에만 운영체제가 개입하여야 한다.

요약 및 정리¶

주소 변환이라고 알려진 가상 메모리 기법을 통해 제한적 직접 실행의 개념을 확장

하드웨어와 함께 운영체제는 프로세스의 모든 메모리 접근을 제어할 수 있고, 접근이 항상 주소 공간의 범위 내에서 이루어지도록 보장할 수 있다.

하드웨어 지원은 프로세스가 이해하는 메모리인 가상 주소를 실제 메모리 모습인 물리 주소로 변환하며 이 변환을 빠르게 수행한다.

베이스와 바운드 (base-and-bound) 또는 동적 재배치로 알려진 가상화의 한 형태를 살펴보았다.

장점

• base-and-bound 가상화는 매우 효율적이다.
  베이스 레지스터를 가상 주소에 더하고 생성된 주소가 바운드를 벗어나는지 검사하기 위한 간단한 하드웨어 회로만 추가하면 됨

• 보호 기능
  운영체제와 하드웨어는 협력하여 프로세스가 자신의 주소 공간 이외의 밖의 메모리는 참조를 할 수 없도록 한다.

• 해결해야 할 문제점: 내부 단편화

위 그림을 다시 보자면 프로세스는 32 KB에서 48 KB까지의 물리 메모리를 사용하는데 이때 내부 단편화가 발생함을 볼 수 있다.

내부 단편화(internal fragmentation)
현재 접근 방식에서 비록 더 많은 프로세스를 탑재할 수 있는 충분한 물리 메모리가 있더라도, 고정 크기의 슬롯에 주소 공간을 배치해야 하기 때문에 내부 단편화가 발생한다.
그러나 프로세스 스택과 힙이 아주 크지 않기 때문에, 둘 사이의 공간이 단순히 낭비되고 있다. 할당된 영역의 내부 공간이 사용되지 않기 때문에, 즉 단편화가 발생한다.

• 해결책
  1. 세그멘테이션(segmentation) 기법
  base-and-bound를 일반화한 기법

2. 고정 크기의 스택을 코드 바로 아래에 배치하고 힙을 그 아래에 배치하여 힙이 아래 쪽으로 확장하게 하는 방법
   → 재귀 호출과 함수 호출의 중첩이 긴 경우 그 구현을 어렵게 만들기 때문에 융통성에 제약을 주므로 사용하지 않는 해결책

추가 참고 자료 및 자료 출처¶

• 2-8장. 주소 변환의 원리
• OS는 할껀데 핵심만 합니다. 12편 Memory 개요, 메모리 관리, 정적 링킹과 동적 링킹, 절대 주소와 상대 주소
• 운영체제 - 물리 메모리 관리

이후 참고할 문서 (페이징 기법 관련)
[운영체제] 가상 메모리의 이해
Virtual Memory, 가상메모리 [운영체제]
수까락의 프로그래밍 이야기
운영체제 - 물리 메모리 관리