[OSTEP] Virtualization) 15. Address Translation

[OSTEP] 15. Address Translation

이 포스팅은 $<$Operating Systems: Three Easy Pieces$>$, Remzi H. Arpaci-Dusseau & Andrea C. Arpaci-Dusseau을 읽고 개인 학습용으로 정리한 글입니다.

CH 15. 주소 변환의 원리

제한적 직접 실행 (LDE)

• 대부분의 경우 프로그램은 HW에서 직접 실행

• 그러나, 프로세스가 시스템 콜을 호출하거나, 타이머 인터럽트가 발생할 때 등의 특정 순간에는 운영체제가 개입

가상화에서 운영체제의 목표

• 효율성
• 제어: 응용 프로그램이 자기 자신의 메모리 이외 다른 메모리 접근 못하도록 운영체제가 보장
• 유연성: 프로그래머가 원하는 대로 주소 공간을 사용하고, 프로그래밍하기 쉬운 시스템을 만들어야

주소 변환(address translation)

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

• 제한적 직접 실행 방식에 부가적으로 사용되는 기능

• 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제 존재하는 물리 주소로 변환
  -> 프로그램의 모든 메모리 참조를 실제 메모리 위치로 재지정하기 위해 HW가 주소 변환

• 정확한 변환이 일어날 수 있도록 HW를 셋업하기 위해 운영체제가 관여해야
  -> 운영체제는 메모리의 빈 공간과 사용 중인 공간을 항상 알고 있어야

1. 가정

• 사용자 주소 공간은 물리 메모리에 연속적으로 배치되어야 한다고 가정

• 주소 공간의 크기가 너무 크지 않다고 가정
  (주소 공간은 물리 메모리 크기보다 작다)

• 각 주소 공간의 크기는 같다고 가정

2. 사례

• 주소 공간에 다음과 같은 프로세스가 있다고 가정

• 컴파일러는 이 코드를 어셈블리 코드로 변환한다

0. x의 주소는 레지스터 ebx에 저장되어있다고 가정한다
1. x의 주소에 저장되어 있는 값을 mov1 명령어를 사용하여 범용 레지스터 eax에 넣는다
2. eax에 3을 더한다
3. eax의 값을 x의 주소 위치의 메모리에 저장한다

• 세 개의 명령어 코드는 주소 128에 위치 (코드 섹션)
• 변수 x의 값은 주소 15KB에 위치 (스택)
  (그림에서 x의 초기 값은 3000이다)

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

• 메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소 0이 아닌 다른 곳에 재배치하고 싶다

• 이 프로세스의 주소 공간이 메모리에 배치되었을 때 가능한 물리 메모리 배치의 예.

• 물리 메모리의 첫 번째 슬롯은 운영체제 자신이 사용
• 프로세스는 물리 주소 32KB에서 시작하는 슬롯에 재배치되었다
• 다른 두 슬롯 (16KB ~ 32KB, 48KB ~ 64KB)은 비어있다

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

• 베이스와 바운드(base and bound) / 동적 재배치(dynamic relocation)

• 각 CPU마다 두 개의 HW 레지스터가 필요하다
  -> 베이스 (base) 레지스터
  -> 바운드(bound) 레지스터 / 한계(limit) 레지스터

1. 각 프로그램은 주소 0에 탑재되는 것처럼 작성되고 컴파일된다
2. 프로그램 시작 시, 운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고 베이스 레지스터를 그 주소로 지정한다
3. 프로세스가 실행되면서 프로세스에 의해 생성되는 모든 주소(가상 주소)가 다음과 같은 방법으로 변환(물리 주소)된다

• 예.

• 바운드 레지스터는 보호를 지원하기 위해 존재한다.
  -> 프로세서는 먼저 메모리 참조가 합법적인가를 확인하기 위해 가상 주소가 바운드 안에 있는지 확인한다

• 방식 1: 바운드 레지스터에 주소 공간의 크기 저장
  -> HW는 가상 주소에 베이스 레지스터를 더하기 전에 바운드 레지스터와 비교

• 방식 2: 바운드 레지스터에 주소 공간의 마지막 물리 주소를 저장
  -> HW는 먼저 가상 주소에 베이스 레지스터를 더하고 그 결과가 바운드 안에 있는지 검사

• 예. 주소 공간의 크기가 4KB인 프로세스가 물리 주소 16KB에 탑재되어있다고 가정
  -> 가상 주소가 너무 크거나 음수일 경우 폴트를 일으키고 예외가 발생하게 된다
  

• 베이스와 바운드 레지스터는 CPU 칩 상에 존재하는 HW 구조이다 (CPU당 한 쌍)
• 주소 변환에 도움을 주는 프로세서의 일부를 메모리 관리 장치(MMU, memory management unit)라고 부르기도 한다

4. 하드웨어 지원: 요약

특권 모드

• 두 가지 CPU 모드 필요
  -> 특정한 순간에 CPU는 모드를 전환한다

• 운영체제는 특권 모드(커널 모드)에서 실행
  -> 컴퓨터 전체에 대한 접근 권한을 가짐

• 응용 프로그램은 사용자 모드에서 실행
  -> 할 수 있는 일에 제한이 있다

• 프로세서 상태 워드(process status word) 레지스터의 한 비트가 CPU의 현재 실행 모드를 나타낸다

베이스/바운드 레지스터

• CPU는 메모리 관리 장치(MMU)의 일부인 추가 레지스터 쌍을 가짐

가상 주소를 변환하고 범위 안에 있는지 검사하는 능력

• 프로그램이 실행 중인 경우, HW는 프로그램이 생성한 가상 주소에 베이스 값을 더하여 주소 변환
• HW는 바운드 레지스터와 CPU내의 일부 회로를 이용하여 주소가 유효한지 검사

베이스.바운드를 갱신하기 위한 특권 명령어

• 다른 프로세스를 실행시킬 때 베이스와 바운드 레지스터 값을 변경하는 특권 명령어 제공해야

예외 발생 기능

• CPU는 사용자 프로그램이 바운드를 벗어난 주소로 불법적인 메모리 접근을 시도하려는 상황에서 예외를 발생시킬 수 있어야 함
  -> 이 경우 CPU는 예외를 발생시킴 & 운영체제의 “바운드 벗어남” 예외 핸들러를 실행시켜야

• CPU는 사용자 프로그램이 특권이 필요한 베이스와 바운드 레지스터 값의 변경을 시도하면 예외를 발생기킬 수 있어야 함
  -> 이 경우 CPU는 예외를 발생시킴 & “사용자 모드에서의 특권 연산 발생” 핸들러를 실행시켜야
  

예외 핸들러 등록을 위한 특권 명령어

• CPU는 위의 핸들러들의 주소를 파악하기 위한 방법을 제공해야

5. 운영체제 이슈

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

첫째

• 프로세스가 생성될 때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야 한다

• 각 주소 공간은 물리 메모리의 크기보다 작고, 크기가 일정하다는 가정 하에서 쉽게 처리 가능

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

• 새로운 프로세스가 생성되면 운영체제는 새로운 주소 공간 할당에 필요한 영역을 찾기 위해 자료구조(흔히 빈 공간 리스트(free list))를 검색
  -> 검색을 통해 선택된 공간을 사용 중이라고 표시

둘째

• 프로세스가 종료할 때, 즉 정상적으로 종료될 때 또는 잘못된 행동을 하여 강제적으로 죽게 될 때 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있게 해야 한다

• 프로세스가 종료되면, 운영체제는 종료한 프로세스의 메모리를 다시 빈 공간 리스트에 넣고 연관된 자료구조를 모두 정리한다

셋째

• 운영체제는 문맥 교환이 일어날 때에도 몇 가지 추가 조치를 취해야 한다
  -> 운영체제는 프로세스 전환 시 베이스와 바운드 쌍을 저장하고 복원해야 한다

• 운영체제가 실행 중인 프로세스를 중단시키기로 결정하면, 운영체제는 메모리에 존재하는 프로세스별 자료구조(프로세스 구조체(process structure) 또는 프로세스 제어 블록(process control block)) 안에 베이스와 바운드 레지스터의 값을 저장해야

• 운영체제는 실행 중인 프로세스를 다시 시작할 때/처음 실행시킬 때, 이 프로세스에 맞는 값으로 CPU의 베이스와 바운드 레지스터를 설정해야

• 프로세스가 중단되면 (즉, 실행 상태가 아닐 때) 운영체제가 메모리의 현 위치에서 다른 위치로 주소 공간을 비교적 쉽게 옮길 수 있다.

넷째

• 운영체제는 예외 핸들러 또는 호출될 함수를 제공해야 한다
  -> 운영체제는 부팅할 때 특권 명령어를 사용하여 이 핸들러를 설치한다

하드웨어/OS의 상호 작용 타임라인

• 메모리 변환은 운영체제의 개입 없이 HW가 처리하는 것에 주목

• 제한적 직접 실행의 기본적인 접근 방식을 따르고 있다
  -> 대부분의 경우, 운영체제는 HW를 적절하게 설정하고 프로세스가 CPU에서 직접 실행할 수 있게 함
  -> 타임 인터럽트 발생 / 프로세스가 잘못된 행동을 했을 때에만 운영체제가 개입한다

6. 요약

• 동적 재배치는 비효울적이다

• 재배치된 프로세스에서 스택과 힙 사이의 공간이 단순히 낭비되고 있다

• 이러한 할당된 내부 공간이 사용되지 않아 발생하는 낭비
  = 내부 단편화(internal fragmentation)

• 비록 더 많은 프로세스를 탑재할 수 있는 충분한 물리 메모리가 있더라도, 고정 크기의 슬롯에 주소 공간을 배치해야 하기 때문에 내부 단편화가 발생한다