[운영체제]Memory Virtualization

Memory Virtualization, 메모리 가상화

1. Memory Virtualization

2. The Abstraction: Address Space

3. Interlude: Memory API

4. Mechanism: Addess Translation

5. Segmentation

6. Free-Space Management

---

1. Memory Virtualization

가상화에는 두 개의 중요한 축이 있다. CPU Virtualization과 Memory Virtualization이다. CPU Virtualization은 process와 thread의 개념으로 설명되었다.

Memory Virtualization를 이해하기 위해서 가장 중요한 것을 프로그램이 만드는 모든 Address는 Virtual Address임을 이해하는 것이다. 하지만 실제 시스템에서는 Physical Address로 DRAM(Memory)에 접근한다. 이 과정을 주소변환(Address Translation이라고 하며, OS와 하드웨어가 협력한다.

결론적으로, 사용자들은 Memory Virtualization를 통해 자신에게 굉장히 큰, 자신만이 사용할 수 있는 메모리가 있는 것처럼 추상화를 제공받는다.

 

2. The Abstraction: Address Space

Early system

초기 시스템에서는 물리 메모리를 그대로 사용하였다. Single-Program system으로 프로그램이 하나만 올라갔다. 프로그램이 하나만 올라가므로 프로그램 간의 보호 mechanism은 없거나 단순했다. Program-level에서는 protection이 없었다.

Overlay: 실제 사용가능한 공간보다 프로그램의 크기가 크면 Overlay를 사용했다. 큰 프로그램을 여러 개의 작은 부분으로 나누고, 필요한 부분만 올려서 수행하는 방식

 

Multiprogramming and Time sharing

Multiprogramming system: 여러 개의 프로그램들이 메모리에 존재하는 시스템

OS가 사용하지 않는 다른 부분에 일반 프로그램 여러 개를 올리는 방식이다.

Time sharing: CPU를 여러 프로세스에게 짧은 시간 번갈아 제공함으로써 마치 여러 개의 프로세스가 동시에 수행되는 것처럼 보이게 하는 것이다.

Issues

-Protection: 한 프로세스가 다른 프로세스의 주소 공간을 막을 때 segmentation fault가 발생할 수 있다. 어떻게 적절한 보호기법을 제공할 것인가?

-free space를 어떻게 효과적으로 관리할 것인가?

    Virtual memory의 개념을 도입하여, 하나의 프로세스가 자신이 독점적으로 모든 메모리를 사용하는 것과 같은 환상을 제공한다. 각각의 prcess들은 virtual memory를 가진다. 즉, 현재 시스템에 존재하는 process의 개수만큼 Virtual memory가 존재하게 된다. 또한 virtual memory의 일부를 physical memory에 담아 놓는다. 따라서 physical memory의 입장에서 살펴보면, 여러 프로세스의 정보를 함께 담고 있다.

 

Address space

Virtual memory는 address space라는 잘 정의된 layout를 가지고 있다.

Address space는 code, data, stack, heap이라는 4가지 부분으로 구분할 수 있다.

code	명령어, 가장 낮은 주소에는 code가 들어간다.
data	전역변수, 그 다음 영역에는 data가 들어간다.
heap	동적할당, heap은 낮은 주소에서 높은 주소로 자란다.
stack	지역변수

heap과 stack은 동적으로 자란다는 특징이 있다. stack과 heap 사이에는 free space가 존재한다.

 

Virtual memory의 목표

1.Transparency

물리 메모리의 복잡도를 몰라도 된다.

2.Efficiency

효율적으로 동작해야 한다.

3.Protection

보호 기법을 잘 제공해야 한다.

 

3. Interlude: Memory API

memory space는 2가지 영역으로 구분할 수 있다.

-static: code, data

-dynamic: heap, stack

 

heap vs stack

heap: 개발자에 의해서 명시적으로 할당 받아야 한다. 스택에 비해서 공간이 오래 유지된다. 명시적으로 free시켜줘야 해제된다.

stack: 변수를 선언하면 컴파일러가 자동으로 만들어준다.

 

Memory API

malloc()

인자로 size(요청 byte 수)를 받아서 할당에 성공하면 포인터의 주소를 return한다.

 

free()

할당받은 공간을 반납한다는 의미이다.

 

*메모리와 관련된 common errors

(1) 메모리 할당을 하지 않아서 발생하는 오류

(2) 충분한 메모리 공간을 할당하지 않아서 발생하는 오류

(3) 메모리 할당을 받았으나 초기화하지 않음

heap 공간은 깨끗하게 조정되어 있지 않다 그 공간의 초기값은 garbage 값이 들어가 있다.

(4) 메모리를 할당하고 free하지 않음

시스템에서 할당만 받고 free하지 않으면, 메모리가 부족해지거나 memory leak이 발생할 수 있다.

(5) Dangling pointer

포인터는 사라졌으나 메모리 객체가 여전히 살아있는 것처럼 되어 있을 때

garbage값이 읽히거나 segmentation fault가 발생할 수 있다.

(6) Freeing memory repeatedly

(7) Calling free incorrectly

 

Underlying OS Support/Other Calls

기반 OS의 지원

-malloc()/free()는 library로서 지원된다.

-malloc() library를 실행하면 sys_brk(), sys_mmap()등의 system call이 내부적으로 실행되어 page단위로 할당받는다.

malloc은 큰 메모리 공간을 할당받고(sys_brk(), sys_mmap()) 사용자가 요청한만큼 내어준다.

-malloc과 비슷한 library함수에는 calloc()과 realloc()이 있다.

 

4. Mechanism: Addess Translation

주소변환은 실제로 어떻게 구현되는가?

프로그램이 만들어 내는 것은 전부 가상 주소이지만, 실제로 수행될 때는 물리 주소에 직접 접근해야 한다. 따라서 가상 주소와 물리 주소 간 주소 변환을 필요로 한다.

-Efficiency를 위해서 하드웨어 기반 Address Translation을 사용한다.

-OS기반의 제어: free space 관리 등(free space를 list로 관리한다 등)

 

Address Translation

Memory Virtualization: 제한된 메모리를 독점적으로 사용할 수 있는 가상 메모리의 개념으로 제공하는 것

Virtual memory, Physical memory

Virtual memory: process들마다 주어진다. process는 배타적으로 virtual memory를 사용하다. virtual memory의 시작주소는 0이다.

Physical memory: 모든 process들이 공유한다. Physical memory 상의 주소는 각각의 process들마다 다르다.

 

 

*Virtual memory, Phyical memory 그리고 3가지 주요 components: Compiler, OS, and Hardware

-Compiler: compiler가 virtual memory를 정의한다.

-OS: 프로그램이 실행되기 위해서는 실제 메모리 상에 올라가야 한다.(loading) virtual memory가 실제 physical memory 상에 올라갈 때 임의의 위치에 올라갈 수 있는데 이를 relocatable하다라고 한다. OS가 physical memory를 결정하는 것이다.

-Hardware: hardwared based address translation

 

*Summary of address translation

Base register: Physical memory의 시작주소를 나타낸다.

• physical address = base register + virtual address(offset)

Limit register(Bound register): virtual memory의 크기를 제한하기 위한 용도로 사용되며, Physical memory의 끝나는 위치를 가리킨다. size의 값을 가진다.

→segmentation fault를 check한다.

Base/Limit register는 context switch마다 값이 바뀐다.

 

MMU(Memory management unit)

CPU의 일부분이다. CPU 내부에는 pipeline engine이 존재한다. 그 중에 하나가 MMU가 있다. Memory management unit이다. CPU 내부의 여러 부분들인데, 주소 변환을 도와주는 기능을 한다.

ex) Base/limit register, Segmentation related registers, Paging related registers, TLB(Translation Lookaside Buffer) +circuitry

 

*주소변환은 하드웨어적인 도움을 필요로 한다.

(1)특권모드

User mode와 Kernel mode를 구분한다.

(2)Base/bounds register

Base/bounds register Hardware에서 제공한다.

(3)Virtual address

Virtual address가 CPU로 나오면 Physical memory 바꾸는 작업을 Hardware적으로 진행된다.

(4)Base/bound register를 update

context switch가 이루어지면 Base/bounds register를 update할 필요가 있다.

(5)예외 발생시

예외 발생시 Base/bound register를 update해야 한다.

예: segmentation fault 발생시

(6)예외를 야기할 수 있는 Hardware의 지원도 필요하다.

 

*OS는 메모리를 관리하기 위해서 다음과 같은 역할을 제공해야 한다.

1.메모리 관리: 새로운 프로세스가 만들어지면, 그 프로세스를 위해서 메모리를 할당할 수 있어야 한다. 마찬가지로 회수할 수 있어야 한다. free한 공간을 관리할 수 있어야 하다.

2.base/bound register: 문맥 교환 발생 시 base/bound register를 바꿔줘야한다.

3.Exception handling(예외 처리): segmentation fault 등의 예외 발생시 예외를 처리할 수 있어야 한다.

 

*OS, Hardware, Program의 연관

실제 Application이 하는 일은 단순한다. Fetch와 Execute의 반복이다.

1.Initialization 작업: OS에서 trap handler를 초기화해야한다. Hardware에게 어떤 예외를 발생시켜야 하는지 등록해야 한다.

2.OS involved: 프로세스를 위한 테이블 할당, 메모리공간 할당

→어떤 프로그램을 수행하기 위해서 Hardware적으로 Virtual memory를 Physical memory로 바꾸는 작업을 수행하고, OS에서는 프로세스를 위해서 메모리 공간을 할당하고 예외가 발생하면 예외를 처리하는 등의 작업을 한다.

 

Mechanism

주소변환(Address Translation)은 크게 3가지 방법이 있다.

연속 할당

-Base and limit registers

• 장점: 간단하고 protection을 제공할 수 있다.
• 단점: Internal fragmentation
• base and limit relocation의 한계: code부터 stack까지 연속적으로 할당되어야 하므로 실제 사용하지 않음에도 물리 메모리를 차지하는 문제가 발생한다.

불연속 할당 기법

-Segmentation, 가변 크기 불연속 할당 기법

segmentation단위로 불연속 할당이 이루어진다. 하나의 프로그램은 여러 개의 segment로 나누어지며, segment별로 불연속적으로 할당된다.

-Paging, 고정 크기 불연속 할당 기법

page단위의 고정크기로 불연속 할당이 이루어진다. 하나의 프로그램이 여러개의 page로 나눠지며, page별로 불연속적으로 할당된다.

 

5. Segmentation

key idea

-불연속 할당

-프로그램을 여러 개의 segment들로 나눈다.(예: code segment, data segment, stack segment, heap segment)

-segment 별로 base/limit register를 지원한다.

 

Address Translation

virtual address는 segment number+offset이다.

-code

virtual address 100이면->physical address: 32KB+100이다.

base register의 값에 100을 더해준 것이다.

-heap

virtual address 4200이면->physical address: 34KB+104(offset)

4200=4096(4KB)+104

-free한 공간, 할당된 공간이 아님

virtual address 3000이면 할당된 공간이 아니다.

마찬가지로 virtual address 7000이면, 7000=4096+1024+1024=856으로 할당된 공간이 아니다.

segmentation fault가 발생한다.

 

virtual address가 bit로 표현되는 방법

상위 2개의 비트는 segment number로 표현되고 하위 12개의 비트는 offset을 표현하는데 사용된다.

virtual address 4200은 예를 들어 아래와 같이 표현된다.

 

stack issue

segmentation이란 주소공간을 여러 개의 segment로 나누는 것이다. stack은 기존 segment와는 다른 특징을 가지고 있다. 기존의 segment들은 낮은 주소에서 높은 주소로 자라지만, 스택은 높은 주소에서 낮은 주소로 자라난다. 예를 들어, heap은 낮은 주소에서 높은 주소로 자라지만, 스택은 높은 주소에서 낮은 주소로 자란다.

각각의 segment마다 register를 갖고 있다. 이를 segment register라고 한다. Segment register은 segment들마다 관리한다. Segment register은 base, size, grow positive 등의 정보를 다룬다.

상위 2bit는 segment number로 사용되고, 나머지 12bit는 offset 정보 등을 다룬다.

 

offset+(virtual address-total address)

offeset+(offset in stack-maximum stack size)

주소가 자라는 방향이 positive일 때는 기존의 방법대로 주소변환을 하면 된다. 하지만 negative일때는 base register에서 offset-segment의 크기를 빼주면 된다.

 

case1.

Virtual address가 15KB = 11 1100 0000 0000

-segment number: 11->stack

-offset: 1100 0000 0000->3KB

->Physical address: 28KB+(15KB-16KB) or 28KB+(3KB-4KB)

case2.

16KB-4B = 16380 = b 11 1111 1111 1100

-segment number: 11->stack

-offset: 1111 1111 1100

->Physical address: 28KB+(4092B-4096B)=28KB-4B

 

segment의 크기

coarse-grained: segment의 크기를 크게 한다.→관리 가능한 segment의 개수가 작아진다.(장점)

fine-grained: segment의 크기를 작게 한다→좀 더 유연하게 관리가 가능하다.(장점), 하지만 segment의 개수가 많아진다.→segment table로 관리를 한다.

 

segment을 위한 OS의 지원

-context switch 지원: segment와 관련된 register들을 save/restore해줘야 한다.

-free space 관리(가용 공간 관리): coalescing and compaction을 사용한다.

→coalescing: 인접한 free한 영역을 합치는 것

→compaction: 조각난 free한 영역을 모아주는 것

disk의 compaction과 segment에서의 compaction은 목적이 다르다. disk에서는 성능을 향상시키기 위해서, memory에서는 연속적인 큰 메모리 공간을 만들기 위해서 그런다.

-allocation 정책: Best-fit, Worst-fit, buddy algorithm 등의 할당 정책을 사용한다.

 

segmentation의 장점

1.base register을 사용할 때에 비해서 base/limit register을 사용하는 경우에 비해서 물리 메모리를 실제로 할당할 필요가 없다.

-heap과 stack 사이에 실제로 사용하지 않는 비어 있는 공간을 할당할 필요가 없다.

2. 여러 process들 간에 sharing이(공유가) 더 쉬워진다.

-똑같은 code부분이고 p1과 p2가 공유하고 있는 것을 확인할 수 있다. 서로 동일한 부분이라면 굳이 물리 메모리에 따로따로 만들 필요가 없다.

3.segmentation 단위로 protection을 지원한다.

-각각 segment별로 접근권한을 다르게 준다.

segmentation의 단점(문제)

segmentation은 여전히 문제가 있는데, segmentation은 가변크기를 사용한다. 불연속 할당은 다시 2가지로 나뉘는데, Segmentation과 Paging이 있다. Segmentation과 Paging의 가장 큰 차이는 사이즈이다.

→가변 크기를 사용하면 외부 단편화가 발생하고, free space를 관리하기 쉽지 않다.

→가변크기는 하드웨어로 주소 변환을 구현하기가 쉽지 않다.

※참고: Paging→고정크기 단위(Page)를 사용한다.

 

6. Free-Space Management

Free space 관리

-가변 크기를 지원할 때, free space를 어떻게 지원할 것인가? 외부 단편화를 다뤄야 한다.

• External fragmentation: 가변 크기 할당에서 발생한다. → free한 공간들이 흩어져 있는 것
• Internal fragmentation: 고정 크기 할당에서 발생한다.

-재배치(relocatable) 가능하다. 수행하는 도중에 swap out(suspend)되고, 다시 올라오면(resume) 재배치(relocate) 된다.(위치가 바뀐다.)

→고정크기인 경우, free space를 관리하는 것이 어렵지 않다. Bitmap 등을 사용하면 된다.

 

Splitting and Coalescing

process가 메모리로 올라가야하는데, 연속된 free space가 부족하면 어떻게 해야할까? process를 나눠 여러개로 나눠 할당시킬 수도 있다. 하지만 free한 공간을 하나로 모을 수도 있다.

 

free한 공간들이 어떻게 관리가 되는가?

-free space들은 list로 관리가 된다.

*Request

-현재 물리 메모리에 30-byte짜리 heap이 존재한다.

-10B→free한 공간을 할당한다.

-10B보다 크다→실패하거나 compaction이 발생해야 한다.(free한 공간을 합쳐야 한다.)

-10B보다 작다→need splitting(10B를 다 할당해주기는 아깝다.)

 

compaction과 coalescing의 차이

-compaction: free한 것과 used를 구분하기 위해, 메모리 전체 범위를 대상으로 한다. free한 공간을 합치는 것이다.

-coalescing: 반납한 후, 앞 뒤 간에 합치는게 가능한지 확인하여 가능하다면 합치는 것

 

Free-space allocation policy

1.Best-fit: 남는 공간이 제일 적은 영역을 할당해 준다.→17

→free 공간을 최소화하기 위함

2.Worst-fit: 남는 공간이 제일 큰 영역을 할당해 준다.→36

→free 공간이 또 다시 할당에 사용될 수 있다.

3.First-fit: 처음 만나는 곳에 할당한다.

→할당시간을 줄일 수 있다.

4.Next-fit: 마지막으로 할당된 공간을 기억한다. 그 다음부터 검사를 하여 First-fit에 비해 좀 더 빨리 available한 공간을 찾을 수 있도록 한다.

 

Buddy allocation

2^n의 단위로 할당을 해준다.

2의 정수승으로 나눈다. 그 중에 하나를 할당을 해준다.

→내가 반납이 되면 나의 buddy가 free한지 확인한 후, free하면 합친다. 실제로는 약간 낭비되는 공간이 있긴 하지만, split allocation을 굉장히 효율적으로 할 수 있다.