운영체제의 기초 - 14. Dynamic Storage Allocation

Why Dynamic Allocation?

execution 전이냐? 후냐?에 따라 나눠짐

Static: execution 전, pre-runtime, offline

Dynamin: runtime에 이루어지는 여러가지 행위들

Static analysis: 프로그램이 수행하기 전에 무언가가 코드를 분석하는 것

 - ex) 컴파일러: 소스코드를 분석해서 기계어 코드로 만들어냄

Static Allocation: 프로그램이 수행되기 전에 미리 메모리를 할당하는 것

 - ex) Code(Text) Segment, Data Segment, 전역변수, array[]

Static Allocation의 특징

변수의 Lifecycle이 프로그램의 시작과 종료와 일치

Dynamic Allocation

 - ex) Stack Segment, (Heap Segment)

왜 Dynamic Allocation이 필요한가?

 - 프로그램 안에서 함수를 호출 했을 때 그 함수가 필요로 하는 local 변수들을 담아주는 공간

 - 수행중에 어떤 함수가 어떤 시퀀스로 불리게 될지 모르기 때문에 (예측불가능성)

 - 예측불가능한 상황에서 on demand(요구만 있으면) 필요한 양만큼만 메모리를 할당할 필요가 있기 때문에

 - Dynamic storage Allocation 을 하게 되는 것이다.

Activation Records (Stack Frames 또는 Activation Frames)

Procedure가 수행되기 위해 필요한 정보들을 저장하고 관리하기 위해 Stack에 저장되는 데이터 구조

 - 그 함수가 불려져서 그 함수의 수행이 끝날 때까지만 자기의 의미있는 값을 유지할 수 있음

수행중의 예측불가능성 언제 나타나는가?

- calling 시퀀스 

- Data structure가 있는데 몇 개 쓰일지 모를 때 (PCB)

PCB(Process Control Block)

프로세스의 관리를 위해 운영체제가 유지해야 하는 정보들을 저장하는 데이터 구조

Heap Managemen

Free List: Heap의 사용 가능한 공간들을 연결한 리스트

Free 함수의 역할: Free List로 반환되는 공간이 기존 가용한 공간과 병합 가능한 경우 하나의 큰 공간으로 병합하고 아닌 경우 새로운 포인터를 추가

Fragmentation(단편화): 프로세스에 대한 기억 영역의 할당과 해방을 반복함으로써 작은 기억 영역의 hole이 많이 생성된 상태

 - 단점: 사용할 수 있는 기억 공간이 프로세스가 요구하는 크기보다 작기 때문에 어떤 요구도 만족할 수 없고, 사용하지 않은 상태로 남아있는 상태

 - 이것은  Deadlock 상황과 비슷함

 - 이미 30K를 받아 놓은 상태에서 추가 20K를 요구했으나 받아 들여지지 않아 Sleep 됨 (다른 프로세스도 마찬가지)

 - 다들 조금씩 메모리를 갖고 있으면서 전부 sleep을 하게 됨 (아무도 추가적으로 메모리를 내놓지 않음)

 - 그런데 새로운 request는 계속 들어옴. 조금 있는 메모리 공간마져도 다 쓰게 되고 

 - 궁극적으로 Daadlock 상황이 됨

내용 정리

- Dynamic Allocation은 꼭 필요함

- 특히 Heap은 굉장히 중요한 역할을 한다.

- Heap은 Fragmentation이라고 하는 치명적인 문제를 갖고 있다.

- OS에서 특히 memory Allocation 관련된 사람들은 Fragmentation이 발생하지 않도록 최대한 노력을 해야 한다.

Fragmentation을 피하기 위핸 대표적인 알고리즘 Buddy allocator

현재 리눅스에서는 buddy allocator, slab allocator를 사용

paging이라는 기법 역시 memory Fragmentation를 피할 수 있는 기법임

Buddy allocator = Heap

memory chunk size가 2의 k지수승 만큼 되어 있음

- malloc Request가 들어왔을 때 Free공간을 계속 쪼갠다.

- 쪼갤 때 친구를 맺도록 쪼갠다 ex) 2^8을 2개의 2^7로 나누고 그 중 한개를 또 2개의 2^6으로 쪼개는 것

- 64(2^6)은 malloc(33)을 만족시킬 수 있는 가장 작은 chunk size다

- 다음 사람이 malloc(45)를 요청했다고 했을 때

- 이 요청은 2번째 buddy로 가게 됨 

- 낭비는 있지만 장점이 있음

- 첫번째 요청을 Free()했다고 하면 그 자리가 Hole생김

- 두번째 요청도 Free()했음

- 첫번째 buddy와 두번째 buddy를 하나로 합치면 큰 buddy가 생김 

Buddy Allocator의 Free

인접한 Buddy들이 가용 상태인 경우 이들을 병합함으로써 쉽게 큰 크기의 가용한 메모리 공간을 확보할 수 있다.

Free List를 관리하는 통상적인 방법은 Linked list를 구성하는 것

- Free List가 주어지면 runtime에 어떤 프로세스가 새로운 메모리 allocation request를 했을 때 얘를 어떤 정책에 의해서 들어주느냐를 고민했음

Best-fit: Free list를 살펴보면서 여분이 가장 작은 것을 찾아 Allocation해주는 것

- Best-fit을 오래하게 되면 hole의 사이즈가 굉장히 작아짐 (작은 홀들이 많아질 것임)

First-fit: Best-fit보다는 hole의 사이즈가 크겠지만 average size의 hole들이 생길 것임

Best-fit으로 Allocation하는 것이 항상 좋은 결과를 가져오지 못하는 이유

시간이 지남에 따라 First-fit, Worst-fit에 비해 작은 크기의 hole들이 생성되기 때문에 Fragmentation 문제가 더 심각해질 수 있다.

메모리 Fragmentation 문제는 Scheduling의 문제와는 달리 Policy를 가지고 해결되기는 굉장히 어렵다.

여기서 Heap Implementation이란 주로 Free list Implementation을 의미함

메모리 단편화를 줄이기 위한 상식적인 방법이 memory pool을 사용하는 것임

- memory Fragmentation이라는 문제가 왜 발생하는 거죠? 원인이 뭔가?

- Hole(Free block)과 memory request size가 딱 맞지 않아 발생하는 문제임

- 원인을 찾으면 100% 해결할 수 있음

- 그것이 Paging 기법임

- 그러나 Paging을 사용할 수 있는 한계(제한)가 있음

- 다른 방법으로는

- memory request size를 딱 맞게 만들면 됨

- memory request를 요청할 때 unit 사이즈로만 요청할 수 있겠끔 하는 것!!

- ex) 1KB만 메모리 할당하겠다고 한다면 1KB보다 작은 것은 전부 1KB로 요구하도록 하는 것

- 이것이 memory pool 기법임

memory pool: unit사이즈로 메모리 request를 하도록 함. 그대신 다양한 사이즈를 허용함

 - 메모리 노드를 동일한 사이즈 별로 묶어서 할당하는 것

 - 이럴 경우 Fragmentation이 발생하지 않음

 - 다른 문제: 1K짜리 요구만 들어온다고 했을 때 1K짜리 pool은 비지만 2K, 4K Pool은 남아있는 불균형의 문제가 생길 수 있음

Heap 은 Fragmentation문제를 유발시킬 수 있고

Fragmentation은 시스템의 안전성이나 성능 등에 굉장히 나쁜 영향을 미칠 수 있다

Fragmentation과 함께 memory leak에 관한 문제가 굉장히 중요한 문제다.

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=665

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=666