Virtualization - Virtual Memory

연속 메모리 할당

한 프로세스가 연속적인 메모리 공간에 전부 적재되는 기법.

*가장 단순하지만 이 기법으로는 메모리보다 큰 프로세스는 실행이 불가능하다.

 

Address Translation

가상 메모리는 32비트 운영체제에서는 2^32 byte만큼의 크기이다.

하지만 이건 프로세스가 생각하는 메모리이며 실제 물리 메모리는 다르다.

그래서 프로세스가 요청한 가상 메모리 주소를 운영체제는 물리 주소로 변환해서 사용하는 과정이 필요하다.

 

프로세스의 Address Space의 주소를 진짜 물리적인 메모리의 어느 주소인지를 결정하는 과정을 Address Translation이라고 한다. *Virtual Address를 Physical Address로 변환하는 과정이다.

 

CPU 코어당 하나씩 MMU (Memory Management Unit)이라는 하드웨어가 장착되어있고 이 하드웨어가 빠른 주소 변환을 도와준다.

*연속 메모리 할당 기법이라면 MMU에는 어떤 정보만 들고 있으면 될까?

Base와 Bound 정도만 있으면 된다.

해당 코어를 점유하고 있는 프로세스의 메모리 시

작 주소를 Base, 크기를 Bound로 저장한다.

근데 생각해보면 프로세스의 메모리를 통째로 메모리에 적재하는건 낭비가 심하다.

스택과 힙은 서로를 향해 자라나고 그 사이 공간은 엄청 비어있지않은가.

2^32바이트 가상 메모리를 가능하게 해준 기법이 페이징과 세그멘테이션이다.

 

먼저 16KB를 Virtual Address로 인식하는 운영체제는 몇비트 운영체제일까?

1KB = 2^10 

1MB = 2^20

1GB = 2^30

 

정답은 2^14 (14비트 운영체제) 이다.

 

Segmentation (세그멘테이션)

그래서 프로세스마다 Base, Bound를 갖는것이 아니라, 프로세스의 Stack, Heap, Code 마다 Base, Bound 값을 갖게 하면 어떨까.

그러다가 어느 세그멘테이션도 아닌 영역의 주소를 접근하려고 하면 C 프로그램에서 자주만나는 Segmentation Fault가 발생한다. *해당 오류의 Segmentation은 이 세그멘테이션에서 비롯한 단어이다.

 

특정 가상 메모리 주소가 어떤 세그먼트인지는 어떻게 알까?

이렇게 앞에 2비트를 세그먼트로 사용하는 방법도 있고 (Explicit Approach)

 

Stack pointer에서 나온건 Stack 세그먼트 Program Counter에서 나온건 Code 세그먼트

다른 주소들은 Heap 세그먼트로 판단하는 방법도 있다. (Implicit Approach)

 

스택같이 반대로 자라는 세그먼트도 있다. 그래서 자라는 방향도 저장할 수 도 있다.

그리고 Code 세그먼트는 변경되면 안된다. 그래서 Protection에 관한 정보도 포함될수 있다.

 

External Fragmentation (외부 단편화)

차례로 가지런히 적재되었다고 하더라도 그 이후에 프로세스의 메모리가 스와핑되거나 프로세스가 끝나서 unload되면 External Fragmentation(단편화) 이 발생할 수 있다.

*위 처럼 남은 공간의 총합은 Process 7을 충분히 담을 수 있지만 남은 공간들이 작게 남아서 Process 7가 들어갈 수가 없다.

 

Free-Space Management

Segmentation 기법도 External Fragmentation의 문제가 있었다.

예를 들어 위와같은 메모리 상황에서 15만큼의 메모리 할당 요청이 들어오면 20만큼의 사용가능한 메모리가 있음에도 실패한다.

 

Splitting and Coalescing 

이런 Linked List로 사용가능한 메모리를 관리한다고 하자. 앞으로 Free List라고 부르자

위의 예시에서 10보다 큰 요청은 실패하고 정확히 10메모리를 요청하는 것은 하나의 Node를 주면 될 것이다.

 

그럼 1만큼의 요청은 어떻게 될까.

하나의 노드를 선택해서 거기에서 1만큼을 Split해서 주면된다. 그럼 다음과 같이 될것이다.

그러다가 저 두개의 노드 사이의 메모리가 다시 회수되었다고 하자.

그럼 이 세개의 노드는 서로 연속되고 있으므로 그냥 하나의 노드로 Coalesce(합치다) 할 수 있다.

 

Tracking The Size Of Allocated Regions

 

C++에서의 new는 heap에 메모리를 할당요청한다.

new 다음에 오는 타입의 크기만큼 메모리를 할당하면 되겠다.

하지만 delete은 그저 void*를 받는다.

그저 메모리 주소를 주면서 “해제해줘~”하는데 얼만큼의 크기를 해제해야하는지 어떻게 아는것일까?

그럼 어디에선가 할당된 메모리의 크기를 보관하고 있다고 봐야한다.

magic에는 메모리가 오염되었는지 체크하기위한 값이 들어있다.

 

Growing The Heap

Heap은 계속 늘어난다.

그럼 더이상 늘어날수없을때는…?

그냥 Fail 시켜버리거나 nullptr을 주면 마음편한 해결책이겠지만 이러면 누가 쓰나.

Heap에 할당할 메모리가 없으면 OS에 추가적인 메모리를 위한 page를 요청한다.

page는 디스크와 메모리를 왔다갔다하므로 모자랄일은 딱히 없다.

 

그럼 빈 공간들 중에 어느 곳에 다음 프로세스의 메모리를 적재할지에 대한 알고리즘이 필요하다.

 

최초 적합

빈 공간들을 순회하다가 첫번째로 나타나는 가능한 공간에 적재한다.

빈 공간을 전부 순회하지않아서 빠르다.

 

최적 적합

빈 공간을 전부 순회하여 제일 낭비가 없는 부분에 적재한다.

빈 공간을 전부 순회해야해서 느리고 External Fragmentation이 가속화된다.

 

최악 적합

빈 공간을 전부 순회하여 제일 낭비가 많은 부분에 적재한다.

빈 공간을 전부 순회해야해서 느리다.

 

Paging (페이징)

2^32바이트 가상 메모리를 가능하게 해준 기법이 페이징과 세그멘테이션이다.

이번엔 둘 중에 현대 운영체제에서 많이 사용하는 페이징 기법이다.!!

 

세그멘테이션은 세그먼트의 크기에 따라 가변의 크기메모리를 할당해줘야한다.

하지만 페이징는 Page라는 고정크기의 메모리단위로 할당이 이루어진다. (논리 주소)

물리 메모리는 Page Frame이라는 Page가 담길수있는 크기만큼으로 쪼개져있다. (물리 주소)

Page의 크기 == Page Frame의 크기

 

위 그림은 몇비트 운영체제 일까?

2^6 = 64

정답은 6비트 운영체제 이다.

 

특정 프로세스의 특정 페이지가 어느 페이지 프레임에 들어가 있는지를 찾기 위해 Page Table이라는 것이 필요하다.

 

위 그림처럼 가상 메모리를 4개의 페이지로 나눈다면 제일 위 2비트를 Virtual Page Number로 사용하면 된다.

 

VPN을 Physical Frame Number로 변환하여 사용하면 된다.

변환하는데에 Page Table에 적혀있는 내용을 사용하겠고 Page Table도 메모리에 적재되어있어야한다.

 

번외)

1. 64KB 크기의 가상 메모리 & 256KB 크기의 물리 메모리 & 8KB Page크기면 프로세스는 몇 Page를 갖고 있고 물리메모리는 몇 Page Frame으로 나뉘어야할까?

1KB = 2^10 = 10비트

2^11 = 2KB

2^12 = 4KB

2^13 = 8KB

 

64KB = 2^16 = 16비트운영체제 (가상)

256KB = 2^18 (물리)

8KB = 2^13 (Page)

8KB = 2^13 (Page Frame)

한 프로세스당 몇개의 Page? 64KB(2^16) / 8KB(2^13) = (2^3) 8개

메모리는 몇개의 Page Frame? 256KB / 8KB = 2^5개 = 32개

 

8개의 Page와 32개의 Page Frame.

 

그럼 VPN은 몇 비트이며 PFN는 몇 비트일까?

1bit = 2^1

2bit = 2^2

3bit = 2^3

위 그림의 가상메모리의 크기는 얼마인가.

    2^12 byte = 4KB

Page의 갯수는 몇개일까?

    16개 = 2^4

Page의 크기 얼마인가..

    2^8 bytes

 

5bits / 11bits

 

Page의 크기 얼마인가.

    2^11 bytes = 2KB

프로세스 하나의 Page의 갯수는 몇개인가.

    알수없다. 2KB ~ ?

 

32비트 운영체제에 4KB 크기의 페이지를 가지면 가상 메모리는 몇개의 페이지로 나뉠까?

    2^32 / 2^12 = 2^20 개의 페이지

 

Page Table

페이지 테이블은 엄청 커질수있다.

세그먼트의 Base, Bound를 저장하는 테이블보다 훨씬더..

32비트 운영체제에 4KB 크기의 페이지를 가지면 가상 메모리는 2^20개의 페이지이다.

그럼 프로세스마다 2^20개의 엔트리가 있는 페이지 테이블이 필요하다.

엔트리마다 4bytes가 필요하다고 한다면 프로세스마다 4MB 크기의 페이지 테이블이 생긴다.

100개의 프로세스가 돌고있다고하면 400MB의 메모리를 페이지테이블 저장으로만 쓰게 된다.

 

그리고 또 하나의 문제는 주소를 하나 변환하려고 페이지 테이블에 접근하기 위해 메모리에 접근하고, 변환한 주소를 접근하기위해 또 메모리에 접근한다. *메모리에 접근하기위해 두번이나 메모리를 왔다갔다해야한다.

 

TLB (Translation Lookaside Buffer)

가상주소를 물리주소로 변환하는 속도를 높이기 위해 사용 하는 캐시  <주소변환캐시>

그래서 페이지 테이블의 일정부분을 CPU와 가까운 MMU에 저장한다.

MMU의 해당 부분을 TLB라고 한다.

 

CPU에서 주소를 참조할때 메모리의 Page Table까지 가지않고 TLB를 먼저본다.

TLB에 해당 주소에 대한 변환정보가 있다면 그걸 사용한다. (TLB Hit)

없으면 Page Table까지 가서 해당 변환 정보를 TLB에도 저장한다. (TLB Miss)

 

가상주소 = 프로세스마다 독립적으로 가지고 있는 주소

물리주소 = 실제 메로리 하드웨어의 올라와있는 주소

이 두개가 나누어져 있는 이유는 일반적으로 논리적 메모리가 물리적 메모리보다 크기 때문입니다.물리적 메모리에는 그때 그때 필요한 메모리가 들어가게 되고, 만약 공간이 부족할 경우에는 Swap 영역으로 쫓겨나게 되는 것입니다.쫓겨났던 메모리가 다시 들어오게 될 때에는 Swap 영역에서 다시 물리 메모리 공간으로 들어온다고 생각하실 수 있습니다.

위의 예시를 들면

배열의 원소를 0부터 차례로 접근한다고 하면

miss, hit, hit, miss, hit, hit, hit, miss, hit, hit 이 된다.

“이곳을 접근하면 조만간 주변 부분은 또 접근하겠지~” 하는 것을 **공간지역성 (Spatial Locality)**라고 한다.

 

Context Switch

A 프로세스가 코어를 사용하면서 TLB를 마구 채워놨다가 컨텍스트 스위칭이 일어났다고 하자.

TLB에는 A 프로세스의 변환정보들만 가지고 있다.

그래서 컨텍스트 스위칭이 일어나면 TLB의 내용도 정리를 해줘야 이전 프로세스의 변환정보를 실수로 사용하는 일이 없어질것이다. 근데 TLB를 컨텍스트 스위칭이 일어날때마다 비워버리는 것(Flush)은 오버헤드가 크다.

그럼 어떤 방법이 있을까?

칼럼을 하나 더 추가하여 Address Space Identifier를 두는 것이다.

프로세스들마다 유니크한 이 값을 둬서 이 값도 비교해주면 될것이다.

 

TLB miss. What to replace?

TLB miss가 떴는데 TLB가 꽉차있어서 Entry하나를 비워줘야한다면? 어떤 것을 Replace해줘야할까?

최근에 가장 덜쓴 엔트리를 선택하는 방법이 있다.

이 방법은 공간지역성 (Spatial Locality)과도 잘 맞는다.

 

다른 방법은 그냥 랜덤 엔트리를 없애는 방법이 있다.

이 방법은 위 방법처럼 덜쓴 엔트리를 찾는 과정이 없어지므로 오버헤드가 적어질수 있겠다.

 

For Smaller Tables

페이지 테이블을 줄여보자. 어떤 방법이 있을까.

 

Bigger Pages

Page크기를 늘리는 방법이있다.

 

32비트 운영체제에 16KB 크기의 페이지를 가지면 가상 메모리는 2^18개의 페이지이다.

그럼 프로세스마다 2^18개의 엔트리가 있는 페이지 테이블이 필요하다.

엔트리마다 4bytes가 필요하다고 한다면 프로세스마다 1MB 크기의 페이지 테이블이 생긴다.

100개의 프로세스가 돌고있다고하면 100MB의 메모리를 페이지테이블 저장으로만 쓰게 된다.

 

4KB 크기의 페이지일때보다 훨씬 줄어들게 된다.

대신 페이지가 커지면 16KB의 페이지안에서 Internal Fragmentation이 생길 수 있다.

 

Hybrid Approach: Paging and Segments

세그멘테이션과 페이징을 둘다 쓰는 방법도 있다.

일단 세그멘테이션처럼 용도별도 세그먼트를 나눈다.

 

그러고 세그먼트마다 테이블을 가진다.

 

세그멘테이션은 레지스터로 Base, Bound를 저장하고 관리하는데

여기서 Base와 Bound는 해당 세그먼트에 대한 페이지 테이블의 시작과 크기를 나타낸다.

그래서 페이지테이블 하나하나가 정해진 크기를 가지는게 아니라 가변크기를 가져서

Valid한 페이지가 적으면 작은 테이블로도 가능해진다.

 

Multi-level Page Tables

위의 방식처럼 작은 테이블로 나누고

그 작은 테이블을 관리하는 테이블을 따로 둔다.

그래서 아직 안써도 되는 작은 테이블은 할당하지않는다.

 

Swap Space

근데 메모리는 한계가 있다.

그럼 Ready상태이나 Block상태로 넘어간 프로세스는 메모리에 있을 필요없고 보조기억장치에 넣어놓으면 되지않을까.

보조기억장치의 해당 부분을 스왑영역이라고 부르고 해당 기법을 스와핑이라고 한다.

 

The Present Bit

그래서 페이지테이블에는 해당 페이지가 메모리에 있는지에 대한 정보가 Present Bit라는 이름으로 있다.

bit가 1이면 메모리에 올라와있는 페이지이고 0이면 스왑스페이스에 있는 페이지이다.

 

Page Fault

해당 페이지를 접근하러왔는데 Present Bit가 0이면 해당 페이지는 애초에 메모리에 없다는 뜻이다.

그러면 Page Fault라고 한다.

메모리에 해당 페이지가 없으니 스왑스페이스에서 해당 페이지를 메모리에 가져와야한다는 뜻이다.

그럼 스왑스페이스에서 페이지를 찾아서 메모리에 적재하고 페이지테이블을 업데이트한다. (오버헤드 발생)

 

Demand Paging

Swap Space가 있는 것처럼 프로세스들이 필요한 메모리를 한번에 전부 메모리에 적재하기에는 메모리가 한없이 작다.

그래서 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징 (Demand Paging)이라고 한다.

 

Page Replacement

그래서 Swap Space에 페이지를 놨다가 다시 들여올때 메모리가 꽉 차있으면 쫓아낼 페이지를 골라야한다.

쫓아낼 페이지를 고르는 로직을 페이지 교체 알고리즘이라고 한다.

 

- FIFO 페이지 교체 알고리즘

메모리에 들어온지 가장 오래된 페이지를 내쫓는 알고리즘

 

- 최적 페이지 교체 알고리즘

CPU에 의해 참조되는 횟수가 가장 적은 페이지를 내쫓는 알고리즘.

 

- LRU 페이지 교체 알고리즘

사용된지 가장 오래된 페이지를 내쫓는 알고리즘.

 

Thrashing & Frame Allocation

프로세스가 실제 실행되는 시간보다 페이지에에 더 많은 시간을 소요하여 성능이 저해되는 문제를 Thrashing (스래싱) 이라고 한다.

메모리가 너무 작아서 페이지 프레임의 수가 적으면 Page Fault가 자주 일어날 것이고 Page Fault를 핸들링하는 시간이 너무 길어져서 오버헤드가 커질 것이다.

혹은 프로세스마다 필요한 페이지 프레임의 수가 각기 다를 수 있다.

어느 프로세스는 페이지 프레임이 5개만 필요하지만 어떤 프로세스는 한번에 100개씩 필요할 수 있다.

 

그래서 프로세스마다 몇개씩의 페이지 프레임을 할당해줄지를 결정하는 것이 Frame Allocation (프레임 할당)이다.

 

첫번째는 **균등 할당 (Equal Allocation)**이다.

세개의 프로세스에게 300개의 페이지 프레임을 나눠줄 있다면 균등하게 100개씩 할당해주는 방법이다.

 

두번째는 **비례 할당 (Proportional Allocation)**이다.

프로세스의 크기에 비례해서 페이지 프레임을 할당해주는 방법이다.