Memory Virtualization

What is memory virtualization?

 

- OS virtualizes its physical memory.

- OS provides an illusion memory space per each process.

- It seems to be seen like each process uses the whole memory.

 

 각 프로세스들마다 전체 메모리를 가지고 있는 것처럼 환각을 제공한다.

 

 

 

Address space 는 process마다 갖고 있는 것이다.

Disk 에서 목적 파일 a.out이 들어가고 실행하면 text로 이동한다.

여기서 0x00000000 ~ 0xFFFFFFFF <= virtual address 이다. (물리적 주소 x)

 

위에서 오른쪽 사진은 Linux 기반으로 User mode, Kernel mode가 절반씩 나뉜 모습이다.

User mode : 0x00000000 ~ 0x7FFFFFFF, Kernel mode : 0x80000000 ~ 0xFFFFFFFF

 

그런데 pintos 에서 코드를 보면 알다싶이 PHYS_BASE = 0XC0000000 을 기준으로 Kernel space와 User space로 나뉜다. 

User mode : 0x00000000 ~ 0xBFFFFFFF, Kernel mode : 0xC0000000 ~ 0xFFFFFFFF

 

 

 

pintos/src/threads/thread.h 에 존재하는 thread structure를 살펴보도록 하자.

 

 

 

 

thread 구조체에서 status는 총 4가지로 Running, Ready, Blocked, 그리고 Dying 가 존재한다.

 

그리고 uint32_t *pagedir; 는 굉장히 중요한 역할을 하는데 virtual address를 physical address로 변경하도록 해준다. 

이를 pointer를 통해 해당 table을 찾아가도록 한다. (project 4에서 구현하게 될 것...?!)

uint8_t *stack; 도 볼 수 있듯이 stack 영역을 pointer를 통해 찾아갈 수 있을 것 같다.

 

virtual address는?

=> 한 process가 전체 process address space 를 정의하는 방법이 아니라 virtual memory라 해서

추상화함으로써 뭔가 컨트롤 되어있는 방식으로 접근할 수 있는것을 의미한다.

 

 

Executing in User Mode => user stack

Excuting in the Kernel Mode => kernel stack

 

System call을 하면 kernel 영역으로 들어간다. (이때 eip 변경)

이때 2가지 순서를 거치게 된다.

 

(1) switch from user stack to kernel stack

(2) raise privilege level (kernel mode)

 

Project 1을 구현했던것을 기반으로 system call의 흐름을 다시 생각해보면...

 

모든 세팅이 끝난 다음에 user code가 실행되는 과정속에서 특정 kernel API를 호출할 때

syscall을 호출함으로써 user stack에 argument와 syscall number 등을 push 하고 int 0x30 를 

실행 시킨다.

 

그리고 interrupt vector table에 존재하는 syscall_handler()를 호출함으로써 user stack 에서 쌓았던 argument 들을 stack pointer (esp) 를 이용하여 kernel API 를 사용할 수 있도록 해줬다.

 

여기서 system call을 하면서 kernel 영역으로 들어간다 했으므로 user stack이 kernel stack로 변경되고 kernel mode로 이동하는 순서로 알아둬야 겠다.

 

그리고 user mode에 text를 가르키는 eip 가 kernel mode 에 text and data를 가르키도록 변경하는 것 또한 알아두자.

 

 

 

Motivation for Virtualization

 

 

Uniprogramming : One process runs at a time.

 

 

Uniprogramming 의 단점은 다음과 같다.

 

1. Only one process runs at a time.

2. Process can destroy OS.

 

여러 프로세스를 실행하지 못함과 동시에 OS 를 destroy 하는 문제점이 존재한다.

 

프로세스가 OS 에 접근할 수 있어서 고치는 문제점이 있다.

 

 

 

Motivation for Dynamic Memory

 

 

Why do processes need dynamic allocation of memory?

 

- Do not know amount of memory needed at compile time.

- Must be pessimistic when allocate memory statically.

- Allocate enough for worst possible case; Stoarge is used inefficiently.

 

Recursive procedures

 

- Do not know how many times procedure will be nested.

 

동적 메모리 영역에서 메모리를 한번에 잡는것을 허용하지 않는다.

그 이유는 실제로 쓸 양만 할당해야하는 부분에서 얼마나 일지를 모르기 때문이다. (run time 때 알 수 있음)

그리고 recursive 또한 parameter value에 따라 결정된다고 할 때 이 또한 언제 끝날지도 모른다.

 

그래서 Dynamic allocation 에서 필요한 두가지 type 이 바로 Stack, Heap 이다.

 

Address space has static and dynamic components

 

- Static : Code and some global variables

- Dynamic : Stack and Heap

 

 

 

Multiprogramming Goals

 

 

Transparency

- processes are not aware that memory is shared

- Works regardless of number and/or location of processes

 

Protection

- Cannot corrupt OS or other processes

- Privacy : Cannot read data of other processes

 

Efficiency

- Do not waste memory resources (minimize fragmentation)

 

Sharing 

- Cooperating processes can share portions of address space

   (예를들어서 pipe를 통해서 sharing을 할 수 있음)

 

 

 

 

Stack Organization

 

Memory is freed in opposite order from allocation.

 

So, simple and efficient implementation

=> Pointer separates allocated and freed space

    - Allocate : Increment pointer

    - Free : Decrement pointer

 

No fragmentation!

 

Physical Address에서의 Allocate, Free를 생각하면 된다. 

다음과 같은 그림을 통해서 이해하도록 하자.

 

 

Heap Organization

 

 

Definition : Allocate from any random location : malloc(), new()

- Heap memory consists of allocated areas and free areas (holes)

- Order of allocation and free is unpredictable

 

Advandage => Works for all data structures

 

Disadvantages 

- Allocation can be slow

- End up with small chunks of free space - fragmentation

- Where to allocate 12 bytes? 16 bytes? 24 bytes?

 

위 사진을 보면 Free한 영역, Alloc 한 영역이 랜덤하게 나뉜것으로 보이는 것을 알 수 있다.

 

What is OS's role in managing heap?=> OS gives big chunk of free memory to process; library manages individual allocations

 

Heap 이라는 것은 random 한 주소에다가 할당할 수 있다.즉, 메모리 공간중에 이용 가능한 곳에 필요한 만큼 할당할 수 있다.메모리가 어디에 할당할 것인지에 대한 trace 또한 할 수 있어야 한다.

 

근데 allocate를 어디에다 할지를 모르므로 이를 해결하기 위해 어디가 최적으로 할당하기에 좋은지에 대한 알고리즘을 구현해야 한다.

 

즉, OS가 free한 space 빈공간이 어디에 있는지 계속해서 관리를 해줘야 한다는 단점이 있다.반면에 Stack은 그냥 포인터 하나만으로 해결이 가능하다는 점에서 편리함이 있다.

 

 

How to virtualize Memory?

 

 

How to run multiple processes simultaneously?

=> Addresses are "hardcoded" into process binaries 

 

hard coding 뜻은 데이터를 코드 내부에 직접 입력하는 것. 기술적으로는 데이터가 실행 바이너리(exe 파일 등)에 합쳐져 있는 상태를 말한다.

 

Possible Solutions for Mechanisms

 

1. Time sharing

2. Static relocation

3. Base

4. Base + Bounds

5. Segmentation

6. Paging

...

 

 

Time Sharing of Memory

 

 

이전에 배웠던 time sharing을 떠올려보면 process scheduling, time quantum 등 배웠는데 

time sharing of memory 란 memory 를 독점해버리는 것을 말한다. (CPU가 아닌 Memory를)

 

OS gives illusion of many virtual CPUs by saving CPU registers to memory when a process isn't running.

 

Colud give illusion of many virtual memories by saving memory to disk when process isn't running.

 

 

 

위 그림의 flow를 이해해보도록 하자

 

Disk에 program이 존재할 때, Memory에 process create 한다.

다른 프로그램이 올라간다고 할 때 process 1 를 내려버리는데 이러한 과정을 time sharing 이라고 한다.

그리고 나서 또 Memory에 process create 한다.

fork() 를 통해 process 2가 만들어지는데 이를 또 내려버리고 다시 process 1을 올리는 과정 또한 time sharing 이라고 한다.

 

이런식으로 Memory virtualization 을 한다면 정말로 비효율적이다.

 

Better Alternative => space sharingAt same time, space of memory is divided across processes.

 

 

Static Relocation

 

 

idea : OS rewrites each program before loading it as a process in memory

Each rewrite for different process uses different addresses and pointers.

 

Static : Layout in Memory

 

time sharing 같은 경우에 컴파일러가 생성한 코드 (ex : echo.o) 영역이 loader가 Memory 에 올릴 때의 그곳이 바로 물리적인 주소이다.

 

그렇다면 다시 creation 하는 경우 program을 내릴 수 밖에 없다.

 

동일한 코드를 올리기 때문에 한 녀석을 내리다가 time sharing 을 하게 된다.

 

OS가 프로그램을 fork() 띄워서 memory에 올릴 때 물리적인 주소를 바꿔준다.

(rewrite 되어서 주소 0x1010, 0x3010 와 같이)

 

오른쪽 사진을 보면 process 1, process 2는 4 KB 으로 물리적 주소가 바로 mapping 됨을 볼 수 있다.

 

 

Static Relocation 의 단점은 ?

=> process가 다른 process에 접근할 수 있는 여지가 충분히 존재한다.

또한 kernel 영역도 destroy 할 수 있으며 즉 privacy 문제를 일으킬 수 있다.

그리고 한번 메모리에 적재되면 그 다음에 고정되기 때문에 다른 곳으로 이동할 수 없는 문제점도 존재한다.

 

No protection : Process can destroy OS or other processes, No Privacy

 

Cannot move address space after it has been placed.