[OSTEP-15] Address Translation

주소 변환의 원리

• 대부분의 경우 프로그램은 하드웨어에서 직접 실행되지만, 프로세스가 시스템 콜을 호출하거나 타이머 인터럽트가 발생할 때 운영체제가 개입함 (LED: 제한적 직접 실행)
• 운영체제는 약간의 하드웨어의 지원을 받아 효율적인 가상화를 제공하기 위해 최선을 다함
• 가상화를 제공하는 동시에 효율성 (efficiency) 와 제어 (control) 을 모두 추구함

핵심 질문. 어떻게 효율적이고 유연하게 메모리를 가상화 할까

하드웨어 기반 주소 변환

• 제한적 직접 실행 방식에 부가적으로 사용되는 기능
• 주소 변환을 통해 하드웨어는 명령어 반입, 탑재, 저장 등의 가상 주소를 물리 주소로 변환
• 하드웨어에 의해 제공되는 저수준(low level) 기능들은 변환을 가속화 시키는데 도움을 주지만, 하드웨어만으로는 메모리 가상화를 구현할 수 없음
  • 정확한 변환이 일어날 수 있도록 하드웨어를 셋업하기 위하여 운영체제가 개입해야 함

가정

• 사용자 주소 공간은 물리 메모리에 연속적으로 배치되어야 한다
• 각 주소 공간의 크기는 같고 공간의 크기가 너무 크지 않음

사례

// C언어
void func() {
  int x = 3000;
  x = x + 3;
}

// 어셈블리 코드
0000000100003f90	sub	sp, sp, #0x10
0000000100003f94	mov	w0, #0x0
0000000100003f98	str	wzr, [sp, #0xc]
0000000100003f9c	mov	w8, #0xbb8
0000000100003fa0	str	w8, [sp, #0x8]
0000000100003fa4	ldr	w8, [sp, #0x8]
0000000100003fa8	add	w8, w8, #0x3
0000000100003fac	str	w8, [sp, #0x8]
0000000100003fb0	add	sp, sp, #0x10
0000000100003fb4	ret

• x 의 주소 => 레지스터에 저장
• 주소에 저장되어 있는 값을 범용 레지스터에 적재
• 레지스터 값에 3을 더하고 같은 위치의 메모리에 저장

부가설명

• 프로그램 관점에서 주소공간은 0 부터 최대 16KB 까지 (코드, 힙, 스택) 영역
  • 프로그램이 생성하는 모든 메모리참조는 해당 범위 내에 있어야함
• 어떻게 하면 메모리를 다른 위치에 재배치 하느냐가 해결해야할 문제

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

• 1950년대 시분할 컴퓨터에서 사용되는 개념 베이스와 바운드 (base and bound) or 동적 재배치 (dynamic relocation)
  • 각 CPU 마다 2개의 하드웨어 레지스터가 필요
    • 하나는 base, 하나는 bound 레지스터 혹은 limit 레지스터
• 베이스와 바운드 쌍은 원하는 위치에 공간을 배치할 수 있게 보장함.

재배치 과정

 

• 프로그램 실행 시 운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고, 베이스 레지스터를 그 주소로 결정함
• 위의 예시에서는 물리 주소를 32KB 에 저장하기로 결정하고 베이스 레지스터를 저 값으로 설정
• 프로세스가 실행되며 생성되는 모든 주소가 다음과 같은 방법으로 프로세서(CPU) 에 의해 변환됨
  • physical address = virtual address + base
• 프로세스가 생성하는 메모리 참조는 가상 주소
• 주소의 재배치는 실행 시에 일어나고, 이후에도 주소 공간을 이동할 수 있기 때문에 동적 재배치라고함
• 바운드 값은 프로세스가 생성한 모든 주소가 합법적이고 프로세스의 “범위“ 에 있다는 것을 확인하는 용도
• 베이스와 바운드 레지스터는 CPU 칩 상에 존재하는 하드웨어 구조
  • CPU 당 1쌍 존재
  • 주소 변환에 도움을 주는 프로세서 유닛을 MMU 라고 함 (Memory Management Unit)
• 바운드 레지스터는 아래와 같이 두 가지 방식 중 하나로 정의 될 수 있음
  • 1. 주소 공간의 크기를 저장하는 방식으로 가상 주소를 베이스 레지스터에 더하기 전에 먼저 바운드 레지스터와 비교
  • 2. 주소 공간의 마지막 물리 주소를 저장하는 방식 하드웨어는 먼저 베이스 레지스터를 더하고 그 결과가 바운드안에 있는지를 검사함

예시

어셈블리 코드: 128: mov1 0x0(%EBX), %eax

• 프로그램 카운터 (PC) 는 128로 설정되고, 하드웨어가 해당 명령어를 반입할때 PC값을 베이스 레지스터의값(32768) 에 더해 32896 의 물리주소를 얻음
• 하드웨어는 프로세스가 참조하는 가상 주소를 받아들여 데이터가 실제로 존재하는 물리 주소로 변환함

 

소프트웨어 기반 재배치

• 초창기 하드웨이 지원이 제공되기 전, 일부 시스템은 소프트웨어만으로 엉성하게 재배치를 수행함
• 이 기술은 정적 재배치 (static relocation) 이라 불리고, 로더(loader) 라 불리는 소프트웨어가 실행하고자 하는 실행 파일의 모든 주소를 원하는 물리 메모리 오프셋으로 변경함
• 예를 들어, 명령어가 주소 1000번지로 부터 레지스터로 탑재하는 경우 (mov1 1000, %eax) 그리고 프로그램 주소 공간이 주소 3000부터 탑재 되었다면, 로더는 모든 명령어의 주소를 3000 씩 이동한 주소로 재 작성함 (mov1 4000, %eax)

문제점

• 보호 기능이 없음
  • 잘못된 주소를 생성하여, 다른 프로세스나 운영체제의 메모리를 불법적으로 접근할 수 있음
  • 제대로 보호하기 위해서는 하드웨어 자원이 필요함
• 한번 배치되면 추후 주소 공간을 재배치하는 것이 매우 어려움

하드웨이 지원: 요약

• 두가지 CPU 모드
  • 운영 체제는 특권모드 (혹은 커널 모드) 에서 실행하며 컴퓨터 전체에 대한 접근 권한을 가짐
  • 응용 프로그램은 사용자 모드에서 실행되며, 할 수 있는 일에 제한이 있음
  • 프로세서 상태 워드 (processor status word) 레지스터의 한 비트가 CPU의 현재 실행 모드를 나타내고, 특정 순간에 시스템 콜 또는 다른 종류의 예외나 인터럽트 발생시) CPU는 모드를 전환함
• 베이스와 바운드 레지스터를 자체적으로 제공
  • CPU 는 메모리 관리 장치 (MMU) 의 일부인 추가의 레지스터쌍을 가짐
  • 프로그램이 실행중인경우 하드웨어는 프로그램이 생성한 가상 주소에 베이스 값을 더하여 주소를 변환함
  • 하드웨어는 주소가 유효한지 검사할 수 있어야 함
  • 베이스와 바운드 레지스터 값을 변경하는 명령어를 제공 해야함, 다른 프로세스를 실행시킬때 이 명령어를 사용하여 베이스와 바운드 레지스터 값을 변경할 수 있음 (특권 명령어)

운영체제는 프로세스에게 메모리를 할당할 수 있도록, 사용되지 않는 메모리 공간의 리스트를 유지함.

다양한 자료구조가 사용될 수 있지만, 가장 간단한 자료구조는 빈 공간 리스트임 이 리스트는 현재 사용중이지 않은 물리 메모리 영역의 리스트임

 

운영체제 이슈

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

1. 프로세스가 생성될때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야함
   1. 각 주소 공간이 물리 메모리의 크기보다 작고, 메모리 크기가 일정할 경우 쉽게 처리할 수 있음
      1. 가변 크기의 주소 공간인 경우는 어떻게 해야하나?
   2. 운영체제는 물리 메모리를 슬롯의 배열로 보고 각 슬롯의 사용여부를 관리함
   3. 새로운 프로세스가 생성되면 운영체제는 새로운 주소 공간 할당에 필요한 영역을 찾기 위해 free list 라고 불리는 자료구조를 검색해야함
2. 정상적으로 종료, 혹은 예기치 못하게 종료 되었을때 프로세스가 사용하던 메모리를 회수하여, 다른 프로세스나 운영체제가 사용할 수 있게 해야 함
   1. 프로세스가 종료하면, 운영체제는 종료한 프로세스의 메모리를 다시 빈 공간 리스트에 넣고 연관된 자료구조를 모두 정리해아함
3. Context Switching 이 발생할 경우 몇가지 추가 조취를 취해야 함
   1. CPU 마다 한쌍의 베이스-바운드 레지스터만 존재하기 때문에 프로세스 전환시 베이스와 바운드 쌍을 저장하고 복원해야함
   2. 프로세스 별 자료구조안에 베이스와 바운드 레지스터의 값을 저장해야함 프로세스 구조체 혹은 프로세스 제어 블록 (PCB)
4. 예외 핸들러 또는 호출될 함수를 제공해줘야함

 

단점

• 동적 재배치를 사용할 경우 할당된 영역의 내부 공간이 사용되지 않으면, 단편화가 발생되어 메모리 공간이 낭비 될 수 있음 (internal fragmentation)
  • 물리 메모리의 이용률을 높이고, 내부 단편화를 방지하기 위해 더 정교한 기법이 필요함
• 따라서 base-and-bound를 일반화하기 위한 기법이 필요한데 이를 Segmentation 이라 부름