[OS] Mechanism: Address Translation

 

CPU를 가상화할 때 LDE(Limited Direct Execution) 매커니즘을 활용했었던게 기억나시나요??

CPU를 user mode와 kernel mode의 2가지 모드와, system call, trap, interrupt등이 발생했을 때는 운영체제가 개입하여 알맞은 일을 처리해주었었습니다. 이 때 운영체제는 하드웨어의 지원을 받아 효율적인 가상화를 제공함과 동시에, 프로세스에게 통제권을 온전히 주는 것이 아닌 time interrupt같은 것을 통해서 통제권을 유지했습니다.

 

CPU 가상화에서 효율성(Efficiency)과 통제(Control) 그리고 보호(Protection)가 운영체제에게 중요했던 만큼 메모리 가상화에서도 여전합니다. 또한, 프로그램들이 자신의 address space를 원하는 방식으로 사용할 수 있도록 하여 시스템을 더 쉽게 프로그래밍할 수 있게끔 유연성(flexibiliy) 또한 중요하게 요구됩니다.

 

어떻게 하면 요구사항들을 충족시키면서 효율적이고! 유연한! 메모리 가상화를 구축할 수 있을까요?
애플리케이션에 필요한 유연성을 어떻게 제공할 수 있을까요??
어떻게 특정 메모리 위치에 대한 접근을 통제하여 메모리 접근이 적절히 제한되도록 할 수 있을까요?
그리고 이 모든 것들을 어떻게 효율적으로 수행할 수 있을까요???!!

 

LDE(Limited Direct Execution)에 추가된 개념으로, 하드웨어 기반 주소 변환(Hardware-based address translation), 또는 간단히 주소 변환이라는 방법을 활용하게 됩니다.

 

주소 변환이 하는 것은 간단합니다.

가상 주소(virtual address)를 실제 물리 메모리 주소(Physical address)로 변환하는 것입니다.

이 때 성능 측면에서의 효율성을 위해 하드웨어를 사용하는 것입니다. 하지만 하드웨어만으로는 이런 일이 일어나지는 않죠.

운영체제가 필요합니다. 운영 체제가 주소 변환이 올바르게 이루어질 수 있도록 도움을 줘야합니다. 또한, 메모리를 관리해서 어떤 위치가 비어있는지, 어떤 위치가 사용 중인지를 추적하고, 메모리 사용 방식을 통제해야합니다. 운영체제가 할 일이 많습니다!

 

다시 리마인드하자면, 이런 모든 작업의 궁극적인 목표는 프로그램이 자신의 코드와 데이터가 위치한 자신만의 독립적인 메모리를 가지고 있다는 아름다운 환상(beautiful illusion)을 만드는 것입니다. 사실은 여러 프로그램이 동시에 메모리를 공유하고 있고, CPU가 time sharing을 통해 프로그램 간에 전환을 통해 이를 실행하고 있다는 복잡한 현실은 모른채 말이죠. 

운영체제가 하드웨어의 도움과 함께 이러한 복잡한 현실을 가린채 사용하기 쉬운 추상화로 바꾸어줍니다.(투명성)

이런 투명성의 혜택은 앞선 글에서도 언급했듯이 다른 프로그램을 신경쓸 필요없이 자신만의 프로그램만 신경쓰며 개발할 수 있게끔 하여 우리와 같은 개발자들에게 온전히 혜택으로 다가오게 되는 것 입니다!

 

이제 본격적으로 메모리 가상화에 대해서 더 알아봅시다 !

 

---

 

우선 몇가지 가정들을 하고 넘어갑니다.

- 사용자의 address space가 physical memory에서 연속적으로 배치되어야 한다.
- address space의 크기가 크지 않다. 즉, address space 크기가 physical memory의 크기보다 작다.
- 프로세스 각각의 address space의 크기가 모두 동일하다.

 

이런 가정을 하고, 점차 이런 가정들을 수정해나가면서 현실적인 메모리 가상화에 가까워집니다.

예제와 함께 더욱 살펴봅시다.

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

 

 

하나의 프로세스가 존재하고, 해당 프로세스의 address space를 그림으로 표현한 것입니다. 지역변수 x는 stack에 할당된 것을 볼 수 있습니다.

 

 

위 코드가 기계어로 변역된 것을 표현해보면 아래와 같습니다.

128: movl 0x0(%ebx), %eax // load 0+ebx into eax
132: addl $0x03, %eax // add 3 to eax register
135: movl %eax, 0x0(%ebx) // store eax back to memory

 

이 명령어들을 살펴보면 virtual address들이 쓰이는 것을 볼 수 있습니다.

• 주소 128에서 명령어를 fetch해온다.
• 해당 명령어 실행 (주소 15KB에서 값을 LOAD)
• 주소 132에서 명령어를 fetch해온다.
• 해당 명령어 실행 (메모리 참조X)
• 주소 135에서 명령어를 fetch해온다.
• 해당 명령어 실행 (주소 15KB에 값을 STORE)

프로그램의 관점에서 address space는 주소 0~최대 16KB이고, 모든 메모리 참조는 이 범위 내에 있어야 합니다. 하지만 메모리를 가상화하기 위해, 운영체제는 이 프로세스를 물리 메모리의 어딘가 다른 위치에 배치하고자 합니다.

즉, 실제 해당 프로세스가 올라가는 주소는 0이 아닌 다른 위치입니다.

 

어떻게 하면 프로세스는 이 사실을 모른채 투명하게 재배치(relocation)를 시킬 수 있을까요?

 

relocation 이후의 모습

 

Dynamic (Hardware-based) Relocation: Base and bounds

하드웨어 기반 주소변환을 이해하기 위해 초기 형태인 'Base and bounds' 기법을 먼저 알아보도록 하겠습니다!

이 기법은 dynamic relocation이라고도 불리며, 두 용어를 서로 바꿔 사용하기도 한다고 합니다.

 

여기에는 각 프로세스 당 2개의 레지스터가 필요합니다.

1. Base register
2. Bounds register (limit register)

프로그램이 실행될 때 운영체제가 physical memory에서 load할 위치를 결정하고, 해당 값을 base register로 설정합니다.

바로 위 예시 그림을 보면 32KB로 로드하기로 결정한 것이고, 운영체제는 base register에 32KB를 설정합니다.

 

그리고 프로세스가 실행되고, 즉 런타임에!!(dynamic이라는 네이밍이 붙은 이유) 메모리 주소를 참조하고자 할 때 아래와 같은 계산이 실행됩니다.

physical address = virtual address(offset) + base

 

이렇게 계산을 통해 얻어진 실제 물리 메모리 주소로 접근하게 되는 것 입니다.

 

구체적인 예시로 한번 더 알아보겠습니다.

 

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

 

PC(Program Counter)가 128를 가르키고 있어 해당 주소에서 명령어를 fetch 해오고자 할 때 주소 128에 접근하게 됩니다. 

이 때 PC값, 128 + base register 값 32KB(32 * 1024 = 32,768)를 더합니다. 따라서 32,768 + 128 = 32,896의 실제 물리 주소에서 해당 명령어를 가져오게 됩니다.

 

명령어를 실행할 때에도 메모리 참조가 존재합니다. 이 명령어는 virtual address 15KB에서 값을 로드하고자 합니다.

15KB + base register, 32KB를 더하면 47KB의 실제 physical address를 얻게 되고, 해당 위치에서 원하는 값을 가져옵니다.

 

이러한 virtual address를 physical address로 변환하는 것을 '주소 변환(Address translation)'이라고 부르고, 이 작업은 런타임에 이루어집니다. 프로세스가 실행 중인 상태에서도 주소 공간을 이동시킬 수 있는 특성 때문에 dynamic relocation이라고 부릅니다.

 

이제 지금까지 base register를 활용해서 실제 물리 주소를 구하는 것까지 살펴보았습니다. 그럼 이제 bounds register는 어디에 사용되는 걸까요???

 

bounds register는 '보호(Protection)'의 목표를 이루기 위해 사용됩니다. 즉, 메모리를 참조하고자 하는 해당 주소가 올바른 주소인지를 확인하여 정상적인 접근인지 체크하기 위해 존재합니다. 올바른 접근인지 아닌지의 기준이 뭘까요??

 

위의 예시를 한번 다시 살펴봅시다.

relocation 이후의 모습

위의 그림 예시에서 bounds register는 16KB로 설정됩니다(48 - 32 = 16).

만약 CPU가 bounds보다 크거나 같은, 혹은 음수인 virtual address에 참조하고자 한다면 exception이 발생하고 해당 프로세스는 kill 될 것입니다. 즉, bounds register의 목적은 모든 메모리 참조가 프로세스의 "범위 내"에 있는지 확인하는 것 입니다.

 

이런 작업들은 효율성을 위해 하드웨어의 도움을 받게 되고, 이런 하드웨어를 MMU(Memory Management Unit)이라고 합니다.

base와 bounds register는 MMU에 존재하고, MMU에는 산술 연산(물리 주소 계산을 위해)과 비교 연산(범위 내에 있는지 판단을 위해)이 가능합니다.

 

주소 변환 다른 예제

 

address space 크기가 4KB인 프로세스가 물리 주소 16KB에 로드되었다고 가정해봅시다. bounds가 4KB(4,096)이고, base가 16KB라는 말이겠네요. 표에서 3000을 계산하는 것을 보면 base(16KB = 16,384)에 3000을 더해 19,384라는 실제 물리 주소를 계산하는 것을 볼 수 있습니다.

 

마지막 행에 4400을 보면 애초에 offset이 4400으로, offset값만으로 이미 bounds(4KB, 4 * 1024 = 4,096)를 넘습니다. 따라서 해당 주소는 fault (out of bounds) exception을 일으키게 됩니다. [Trap → OS kernel TrapHandler → fault 처리]

 

Hardware Support: A Summary

필요한 하드웨어가 해줘야하는 요구사항들을 한번 총망라해서 요약해봅시다.

 

1. 특권 모드(CPU의 kernel mode)
   1. user program이 MMU의 base나 bounds 레지스터를 바꾸면 안됨. (protection)
2. Base와 Bounds 값을 바꿀 수 있는 특권 명령어 (kernel만 수행할 수 있는)
3. Base / Bounds 레지스터들
4. 변환할 수 있는 능력
   1. ability to translate virtual addressess and check if within bounds
   2. “+” base 더하고, “>” bounds안에 들어가는지 체크하기
5. Exception handling을 위한 특권 명령어
6. Exception을 발생(raise)시킬 수 있어야함 (Bounds값 벗어나면 Fault)

 

Operating System Issues

하드웨어가 dynamic relocation을 지원하기 위해 새로운 기능을 제공하는 만큼, 운영체제도 새로운 문제들을 마주하게 됩니다.

 

1. 프로세스 생성 시의 작업

Figure 15.2 그림을 보면 운영체제는 물리 메모리의 첫번째 슬롯을 자신을 위해 사용하고, 32KB에서부터 프로세스를 재배치시켰습니다. 다른 빈 두 슬롯(16-32KB, 48-64KB)은 비어 있으므로, free list는 이 두 슬롯으로 구성됩니다.

 

2. 프로세스 종료 시의 작업

프로세스가 정상적이거나 비정상적으로 종료될 때, OS는 그 프로세스가 점유하고 있던 모든 메모리를 회수해서 free list에 넣어둠으로써 다른 프로세스나 운영체제가 사용할 수 있도록 합니다. 또한, 프로세스 리스트에서 해당 프로세스도 제거해줘야합니다.

 

3. Context Switching 시의 작업

이 때 가장 유의해야할 점은 PCB에 Base register값과 bounds register값도 함께 담아서 프로세스마다 save을 해줘야한다는 점입니다.

반대로 다시 실행할 때에는 이 값들을 CPU에 restore시켜줘야합니다.

 

한가지 더 유의해야할 점은 프로세스가 stopped됐을 때, OS는 프로세스의 address space를 메모리의 한 위치에서 다른 위치로 쉽게 이동할 수 있습니다. 이를 위해서, 먼저 프로세스를 스케줄링에서 제외하고, 주소 공간을 현재 위치에서 새로운 위치로 복사한 후, PCB에 저장된 base register를 새로운 위치로 업데이트합니다. 그러면 해당 프로세스가 다시 시작할 때 새로운 base register에서 복원되어, 자신이 새로운 위치에서 실행중이라는 사실을 전혀 인지 못하게 됩니다.

 

4. Exception handler 제공

운영체제는 exception handler를 booting 때 설정합니다. 만약 프로세스가 허용된 범위를 벗어난 메모리 주소에 접근하고자 하면 exception을 raise시키고, OS는 해당 프로세스를 kill합니다. 해당 프로세스는 Process table에서도 제거됩니다.

 

---

 

HW, OS가 이제 어떤 요구사항들을 갖춰야하는지를 정리해보았습니다. 이제 한번 동작되는 흐름 또한 살펴봅시다.

 

1. OS: trap table 초기화
2. HW: HW적으로 trap handler의 주소 기억하기. CPU가 어디서 처리할지 기억해야함.
   1. system call handler 주소
   2. timer handler(time-out됐을 때) 주소
   3. 메모리 주소가 잘못되었을 때 (illegal mem-access handler 주소)
   4. 잘못된 명령어. 예를 들어 Data를 명령어로 실행시키는 잘못된 프로그램 (illegal instruction handler 주소)
3. OS: Interrupt Timer 구동 시작 !
4. HW: x ms마다 interrupt거는 건 HW역할 !
5. OS: 프로세스가 여러개 있기 때문에 그것을 Table로 관리하는데 그 Table 초기화 및 비어있는 공간 free space를 free list로 관리. (나중에는 segmentation, paging을 쓰겠지만 free list로 이런식으로도 할 수 있다)

 

프로세스 실행 시의 흐름

 

1. OS:
   1. process table에 프로세스 A등록
   2. A를 위해 메모리를 찾아서 배치해주기
   3. base and bounds 레지스터 설정 (주소변환정보)
   4. kernel stack에 A의 초기값들을 넣어주는데, 그 때의 A의 시작주소(main함수) main의 주소를 kernel stack에 넣어주고
   5. return from trap
2. HW:
   1. A의 레지스터들을 restore
   2. move to user mode
   3. jump to A’s initial PC
3. Program
   1. 프로세스 A Run !
   2. Fetch instruction
4. HW:
   1. VA(Virtual Address) 등장했네? translate virtual address (with MMU)
   2. perform fetch !
5. Program:
   1. 오 메모리주소에서 가져와졌네 Execute Instruction
6. HW:
   1. Instruction안에 또 VA가 있네(ex: LD, ST)
   2. Bounds안에 들어오는지 확인 (ensure address is legal)
   3. translate VA (MMU) → PA (Physical Address)
   4. perform LD/ST
   5. Timer interrupt (time-out !) : Trap발생 ! (이 때 자동으로 register값들을 kernel stack에 저장)
   6. move to kernel mode
   7. jump to handler
7. OS(Handle timer):
   1. 프로세스A를 중단시키고 프로세스B를 실행시키자 !
   2. call switch() routine
      1. save regs(A) including base and bounds: 주소변환정보 Reg → A의 PCB.context (base, bounds 포함)
      2. restore regs(B) including base and bounds: 주소변환정보 Reg ← B의 PCB.context (base, bounds 포함)
   3. return-from-trap
8. HW:
   1. restore registers of B
   2. move to user mode
   3. jump to B’s PC
9. Program:
   1. 프로세스B 실행
   2. load 명령 실행
10. HW:
    1. MMU가 VA 변환하는 과정에서 fault: Out of bounds 발생 !
    2. move to kernel mode
    3. jump to trap handler (Exception)
11. OS:
    1. handle the trap !
    2. kill process B !
    3. B의 메모리 deallocate
    4. process table에서 B 제거(free): free list에 해당 공간 추가 될 것.

Dynamic relocation(Base and bounds)의 비효율성: Internal fragmentation(내부 단편화)

이렇게 base and bounds register를 활용한 메모리의 가상화를 알아보았습니다. 하지만 여기서 끝일리가 없겠죠..?

위 그림에서 표시된 영역처럼 heap과 stack이 늘어나는 것을 고려해보아도 많은 공간이 낭비되고 있습니다.

이렇게 둘 사이의 공간이 낭비되는 것을 '내부 단편화(Internal fragmentation)'이라고 합니다.

현재 방식에서는 처음 가정했던 고정된 크기의 슬롯에 주소 공간을 배치해야 하기 때문에 이런 단편화 발생할 수 밖에 없습니다.

 

그렇다면 이제 이런 단점을 해결하기 위한 노력이 있겠죠?

 

다음글은 physical memory를 보다 더 효율적으로 활용하고 내부 단편화를 줄이기 위한 Segmentation이라는 방법을 살펴보도록 하겠습니다!