운영체제 8 - Mechanism: Address Translation [Memory Virtualization]

 CPU Virtualization 부분에서, LDE(Limited direct execution) 기법에 대해 집중적으로 다룬다.
CPU 가상화의 아이디어는 간단하다. → 대부분 프로그램은 하드웨어에서 직접 실행된다.
But 프로세스가 System Call을 호출하러가나 Timer Interrupt 발생할 때 특정 순간에는 OS가 개입하여 Process issue가 발생하지 않도록 한다.
OS는 약간의 hardware지원을 받아 efficient Virtualization을 제공하기 위해 실행 프로그램의 방해가 안 되도록한다. 중요한 순간에는 OS가 관여하여 하드웨어를 직접 제어한다.
현대 OS의 목표: efficiency, Control

---

Virtualizing memory

Virtualization을 제공하는 동시에 efficiency and control을 모두 추구한다.
Efficiency → Hardware 지원 활용할 수 밖에 없다.
처음에 몇개의 Register만 사용 점점 TLB → page table 등으로 사용하는 것이 늘어난다. 점점 복잡해진다.
Control → 응용 프로그램이 자기 자신의 메모리 이외에는 다른 메모리에 접근하지 못한다는 것을 OS가 보장한다는 것을 의미한다. → 쉽게 말해서 OS가 메모리 침범을 막아준다.
↑ 하드웨어의 도움이 필요하다.

flexibility 측면에서→ VM system이 필요한 상황이 있다.

• 원하는 대로 주소공간을 사용하기
• 프로그래밍하기 쉬운 시스템을 만들기를 원한다.

핵심 문제는 아래 참고 ↓

---

Quecstions

How can we build efficient virtualization of memory?
How do we provide the flexibility needed by applications?
How do we maintain control over which memory locations an application can access,
and thus ensure that application memory accesses are properly restricted?
How do we do all of this efficiently?

---

Hardware-based address translation →(짧게) address translation

address translation은 Limited Direct Execution에서 부가적으로 사용되는 기능이라고 생각할 수 있다.

• the hardware transforms each memory access (e.g., an instruction fetch, load, or store), changing the virtual address provided by the instruction to a physical address where the desired information is actually located.
• Hardware만으로 Memory Virtualzation을 구현할 수 없다. low level 기능들을 제공하여 translation을 가속화시키는 도움을 주지만 혼자서는 안된다.
  OS는 정확한 변환이 일어날 수 있도록 하드웨어를 셋업하기 위하여 관여한다. OS는 메모리의 빈 공간과 사용중인 공간을 알고 있어야하고, 메모리 사용을 제어하고 관리한다.

The program has its own private memory, where its own code and data reside.
↑ illusion을 만들어야한다.
Reality(현실) → Many programs are actually sharing memory at the same time.

Assumptions

---

Simple memory virtualization

1. The user's address space must be placed continuously in physical memory.
2. The size of the address space is not too big → it is less than the size of physical memory.
3. Each address space is exactly the same size.

차차 가정을 완화하면서 실제적인 Memory Virtualzation을 이끌어낸다.

Example

---

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

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

• 컴파일러는 이 코드를 어셈블리 코드로 변환하고 그결과 x86 어셈블리로 위 코드처럼 표기된다.

The three-instruction code sequence is located at address 128.
The value of the variable x at address 15KB. The initial value of x is 3000.
The sequence of memory accesses.

• Fetch instruction at address 128
• Execute this instruction (load from address 15 KB)
• Fetch instruction at address 132
• Execute this instruction (no memory reference)
• Fetch the instruction at address 135
• Execute this instruction (store to address 15 KB)

 

 

실제로는 0~16KB는 OS가 사용한다.

프로그램 관점에서 address space은 주소 0부터 시작하여 최대 16KB까지이다.
→ 프로그램이 생성하는 모든 메모리 참조는 이 범위 내에 있어야한다.
To virtualize memory, the OS wants to place the process somewhere else in physical memory, not necessarily at address 0.

프로세스 주소

공간이 실제로는 다른 물리 주소에 배치되어 있을 때, 주소 0번지부터 시작하는 가상 주소 공간의 환상을 어떻게 제공할 수 있을까?

Dynamic(Hardware-based) Relocation = base and bound

---

1950년 후반의 첫번째 time-sharing machines에게 base and bound 아이디어가 채택되었다.
base and bound을 dynamic relocation라고도 함.

각 CPU마다 2개의 hardware register가 필요하다. 바로 base, bound(limit) register이다.

base와 bound

• 우리가 원하는 위치에 주소 공간을 배치할 수 있게 한다.
• 배치와 동시에 프로세스가 오직 자신의 주소 공간에만 접근한다는 것을 보장한다.

Each program is written and compiled as if it is loaded at address zero.

When a program starts running, the OS decides where in physical memory it should be loaded and sets the base register to that value.

When any memory reference is generated by the process, it is translated.

---

위의 예제를 분석하며 이해하기

128: movl 0x0 (%EBX), % eax
PC(Program counter)는 128로 설정된다. hardware가 이 instruction을 fech할 때, 먼저 PC값을 base register의 값 32KB(32768)에 더해 32896의 물리주소를 얻는다.

그런 후 hardware는 물리주소에서 명령어를 가져온다. 그리고 프로세서는 명령어의 실행을 시작한다. 얼마후 프로세스는 15KB의 값을 load하라는 명령어를 내린다. 이 주소를 프로세서가 받아 다시 base register(32KB)를 더하고 물리주소 47KB에 원하는 내용을 탑재한다.

↑ address translation: Transforming a virtual address into a physical address.
그리고 이 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 주소 공간을 이동할 수 있기 때문에, dynamic relocation 이라고도 불린다.

---

그럼 bound(limit) register는 어디다 쓸까?

bound register는 보호를 지원하기 위해 존재한다. 앞에서 다룬 간단한 예에서 bound register는 항상 16KB로 설정된다. Process가 bound보다 큰 가상 주소 또는 음수인 가상 주소를 참조하면 CPU는 예외를 발생시키고 Process는 종료될 것이다. → bound의 요점은 프로세스가 생성한 모든 주소가 합법적이고 프로세스의 범위에 있다는 것을 확인하는 것이다.
The bounds register is there to help with protection. Specifically, the processor will first check that the memory reference is within bounds to make sure it is legal.

---

Memory Management unit→ MMU

base와 bound register는 cpu 칩 상에 존재하는 hardware structer이다. CPU당 1쌍.
Address translation에 도움을 주는 Processer의 일부를 MMU라고 부르기도 한다.

bound register 두가지 방식으로 정의

1. 주소 공간의 크기를 저장하는 방식

하드웨어는 가상 주소를 base 레지스터에 더 하기전에 먼저 bound 레지스터와 비교한다.

1. 주소 공간의 마지막 물리주소를 저장하는 방식

하드웨어는 먼저 base 레지스터를 더하고 그 값이 bound 앞에 있는지 검사한다.

 

두가지 모두 논리적으로 같다.

---

Example Translations

A process with an address space of size 4KB(비현실적) has been loaded at the physical address of 16KB.
예에서 볼수 있는 것처럼 Physcial address를 얻기 위해서는 간단하게 Virtual address에 base address를 더해주면 된다.
! virtual address가 너무 크거나 음수 일경우에 Fault를 일으키고 예외가 발생하게 된다.

---

Hardware Support

Two different CPU modes(Kernel, user mode)

• The OS runs in privileged mode(or kernel mode), where it has access to the entire machine.
• Applications run in user mode, where they are limited in what they can do.

Processor status word의 A single bit → indicates which mode the CPU is currently running in.

특정한 순간(system call, 다른 종류의 예외나 interrupt 발생) CPU는 모드를 전환한다.
The hardware must also provide the base and bounds registers themselves, as part of MMU of the CPU.
The hardware should provide special instructions to modify the base and bounds registers.

↑ CPU가 하나라고 가정했을 때, 프로세스가 변경되니 base, bound 값도 변경되어야한다.
The CPU must be able to generate exceptions in situations where a user program tries to access memory illegally.

• The CPU should stop executing the user program and arrange for the OS “out-of-bounds” exception handler to run.

---

• 번역

따로 교수님 설명 녹음 추가할 예정

Virtual address는 Program Counter에 존재한다.

뜬금포 지식 → Free list

---

운영체제는 프로세스에게 메모리를 할당할 수 있도록 사용되지 않는 메모리 공간의 리스트를 유지한다. 다양한 자료구조가 사용될 수있으나, 가장 간단한 자료구조는 free list다.
이 리스트는 현재 사용 중이지 않은 물리 메모리 영역의 리스트다.

Operating System Issues

---

하드웨어 지원과 OS 관리가 결합되면 간단한 Virtual Memory를 구현할 수있다. →base and boud 방식의 virtual memory구현을 위해서 OS가 반드시 개입해야하는 세개의 시점이 존재한다.

First, the OS must take action when a process is created, finding space for its address space in memory.
↑ Fortunately, given our assumptions that each address space is (a) smaller than the size of physical memory and (b) the same size, this is quite easy for the OS

• When a new process is created, the OS will have to search a data structure (often called a free list) to find room for the new address space and then mark it used.

Second, the OS must do some work when a process is terminated (i.e., when it exits gracefully, or is forcefully killed because it misbehaved), reclaiming all of its memory for use in other processes or the OS. 프로세스가 종료하면, 운영체제는 종료한 프로세스의 메모리를 다시 free list에 넣고 연관된 자료구조를 모두 정리한다.

Third, the OS must also perform a few additional steps when a context switch occurs.
-There is only one base and bounds register pair on each CPU, after all, and their values differ for each running program
-The OS must save and restore the base-and-bounds pair when it switches between processes.
-When the OS decides to stop running a process, it must save the values of the base and bounds registers to memory, in some per-process structure such as the process structure or process control block (PCB).

The OS must provide exception handlers

• 정리
• 사용자가 특정 프로그램 실행을 지시하는 순간 프로세스 생성 → 프로세스가 사용할 address space할당
  할당을 위해서 시스템 메모리에서 빈 공간을 찾아 프로세스가 사용할 공간 마련
  빈 공간과 사용중인 공간 중에 어느 프로세스가 어느 공간을 사용하고 있는지, 어떤 공간이 비어있는지 기록할 free list가 존재
  프로세스의 동작이 종료되었을 때(동작을 완료해서/강제종료)OS가 이 프로세스가 사용하던 주소 공간을 회수함.
  회수하고 이 프로세스의 주소 공간에 있던 모든 정보를 삭제하고 free list에 정보처리
  정보처리 방법 1. 메모리에 존재하고 잇는 정보를 안 지우고 free list에 비어있다 기록 2. 메모리에 있는 정보 초기화도 하고 free list에 기록도 함.

---

1. 실행 중인 프로세스를 중단시킨다.
2. 현재 위치에서 새 위치로 주소 공간을 복사한다.
3. 프로세스 구조체에 저장된 base 레지스터를 새 위치를 가리키도록 갱신한다.
4. 예외 핸들러 혹은 호출된 함수를 제공한다.

• 부팅할 때 커널 명령어를 사용하여 핸들러를 설치한다.