운영체제 - Dynamic Storage Allocation(Stack, Heap)
static allocation?
- 프로그램이 수행되기 전(컴파일 타임)에 미리 메모리를 할당하는 것,
static allocation
- Text(Code) segment, Data segment
dynamic allocation
- Stack segment, Heap segment
Static Allocation의 특징
- 변수의 life cycle이 프로그램의 시작과 종료와 일치
Q. 왜 dynamic allocation이 필요할까?
- 얼마만큼의 메모리 크기가 필요할 지 예측할 수 없기 때문
# Activation Record(= stack frames, activation frames)
- procedure가 수행되기 위해 필요한 정보들을 저장하고 관리하기 위해 stack에 저장되는 데이터 구조
# PCB(Process Control Block)
- 프로세스의 관리를 위해 운영체제가 유지해야 하는 정보들을 저장하는 데이터 구조
- PCB를 Array(static allocation), linked-list(dynamic allocation)으로 관리하느냐 차이에 따라 성격이 달라진다.
# free list
- heap의 사용가능한 공간들을 연결한 리스트
# free()함수의 역할
- free list로 반환되는 공간이 기존 가용한 공간과 병합 가능한 경우 하나의 큰 공간으로 병합하고 아닌 경우 새로운 포인터를 추가한다.
힙 메모리 공간은 alloc()과 free()을 반복하다보면 각기 다른 메모리 청크(chunk)로 분할됨. => memory fragmentation
memory fragmentation을 해결하는 방법?
- Buddy allocation(2^k)
+ 장점 : 인접한 Buddy들이 가용 상태인 경우 이들을 병합함으로써 쉽게 큰 크기의 가용한 메모리 공간을 확보할 수 있다.
- paging
# free list policy
- cpu scheduling에서는 policy 정책에 따라 컴퓨터 시스템 성능이 크게 달라졌지만 free list policy는 무엇을 선택해도 그닥 영향이 없다.
① Best fit
- free list를 찾으며 제일 fitable한 block할당
- 단점 : 시간이 지남에 따라 first-fit, worst-fit에 비해 작은 크기의 hole들이 생성되기 때문에 fragmentation 문제가 더 심각해질 수 있다.
② First-fit
- free list에서 가장 첫 번째로 fit되는 block할당
③ Worst-fit
- 가장 큰 block 할당
# Heap implementation(= free list implementation)
1. bitmap
2. memory pool
- 힙 메모리 공간을 유저 요청에 따라 다양하게 메모리를 할당해주지 말고 단위 크기(unit size)로만 메모리를 할당해 주는 방식이다.
- 예를 들어, 전체 메모리 공간을 1K 할당만을 위한 공간, 2K 할당만을 위한 공간, 4K 할당만을 위한 공간으로 나누면 메모리 단편화 문제가
발생하지 않는다. 그러나, 사용자가 1K공간만을 지속해서 요구한다면 불필요하게 메모리 낭비가 발생할 수 있다.