[OS] Memory Allocation Strategies

우리가 사용하는 프로그램은 virtual address로 동작하기 때문에 이를 physical memory에 allocation 해주는 것이 중요하다. 특히 memory에 단일 process가 올라오는게 아니라 multi process들이 올라오기 때문에 이들을 관리해주는 것은 중요하다. Memory allocation 방식은 크게 두 가지로 나뉜다.

1. Contiguous memory allocation
2. Non-contiguous memory allocation

1. Contiguous Memory Allocation

Greedy하게 연속적으로 memory 할당을 해주는 방식이다.

Contiguous memory allocation의 방식으로는 크게 네 가지가 존재한다.

1. First fit: 특정 address를 기준으로 순차적으로 검색하여 적합한 memory 영역에 할당해주는 방식이다. 시작은 lower address 또는 지난번 allocation이 끝난 address 기준으로 한다.
2. Best fit: Allocation이 가능한 공간 중 가장 작은 것을 선택한다.
3. Worst fit: Allocation이 가능한 공간 중 가장 큰 것을 선택한다. Latency 측면에선 best fit보다 좋을 수 있지만, memory utilization 측면에선 안 좋을 수 있다.
4. Next fit: 마지막 allocation에서 다음 address부터 찾아서 allocation 가능한 영역에 memory 할당을 한다.

Memory allocation을 이야기하면 fragmentation 개념이 중요한데, fragmentation은 크게 두 종류로 나뉜다.

1.1 External fragmentation

External fragmentation은 조각난 memory 영역에 대해 새로운 process에 대해 allocation 해줄 수 있는 크기임에도 불구하고 조각이 나있기 때문에 발생되는 문제다. 해결 방법으론 memory compaction 또는 paging 기법을 통해 해결 가능하다.

1.2 Internal fragmentation

Internal fragmentation은 process에 할당해주는 memory보다 실제 process가 요구하는 memory size가 큰 경우에 발생한다. 위 그림에서 보면 실제 사용하는 space에 비해 allocation space가 크기 때문에 발생한다. 이를 위한 해결 방안으론 best-fit scheme으로 allocation 해주면 된다.

2. Non-Contiguous Memory Allocation

Contiguous memory allocation의 가장 큰 단점으로 internal fragmentation & external fragmentation이 모두 발생할 수 있다. 그리고 memory utilization이 떨어지는 문제가 있기 때문에 non-contiguous memory allocation 방식을 채택한다.

2.1 Segmentation

Segmentation은 하나의 process를 다수의 segmentation으로 나눠서 관리한다. 각 segmentation은 base address와 limit 값으로 segment table에서 관리된다.

Process의 대표적인 구조인 code, data, stack, heap section이 이런 segmentation의 종류 중 각각이다. 각각의 segment들은 독립적으로 자라거나 감소한다.

Segment scheme의 장점

1. Growing 또는 shrink하는 데이터 구조체를 핸들링이 쉬움
2. Easy to protect each segment
3. Easy to share segment by using segment table
   1. 대표적인 예가 shared library

Segment scheme의 단점

1. External fragmentation issue
2. Memory overhead for segment table
3. Cross-Segment address: process간 공유를 위해 같은 segment number를 가질 필요가 있음

2.2 Paging

Paging은 segmentation과 마찬가지로 physical address space를 non-contiguous하게 만들 수 있는 scheme이다. Page라는 고정적인 크기를 가지는 block으로 나누어 각 process의 Virtual Page Number (VPN) 를 Physical Frame Number (PFN)으로 바꾸어 page table에서 관리해준다. (자세한 내용은 아래 post에서 참고 바란다.)

[Computer Arch.] TLB / Page Table

Paging scheme의 장점

1. Physical memory allocation을 free list를 통해 관리하기 용이
2. External fragmentation이 없음
3. Easy to share page by using page table
4. Easy to protect pages

Paging scheme의 단점

1. Internal fragmentation 발생
2. 2번의 memory access (page table access and memory access)
3. Memory overhead for page table

결론적으로 contiguous memory allocation과 non-contiguous memory allocation의 특징을 비교하면 다음과 같다.

S.NO.	Contiguous Memory Allocation	Non-Contiguous Memory Allocation
1.	Contiguous memory allocation allocates consecutive blocks of memory to a file/process.	Non-Contiguous memory allocation allocates separate blocks of memory to a file/process.
2.	Faster in Execution.	Slower in Execution.
3.	It is easier for the OS to control.	It is difficult for the OS to control.
4.	Overhead is minimum as not much address translations are there while executing a process.	More Overheads are there as there are more address translations.
5.	Both Internal fragmentation and external fragmentation occurs in Contiguous memory allocation method.	External fragmentation occurs in Non-Contiguous memory allocation method.
6.	It includes single partition allocation and multi-partition allocation.	It includes paging and segmentation.
7.	Wastage of memory is there.	No memory wastage is there.
8.	In contiguous memory allocation, swapped-in processes are arranged in the originally allocated space.	In non-contiguous memory allocation, swapped-in processes can be arranged in any place in the memory.

Reference

1. https://www.geeksforgeeks.org/difference-between-contiguous-and-noncontiguous-memory-allocation/
2. https://www.geeksforgeeks.org/difference-between-internal-and-external-fragmentation/
3. https://www.geeksforgeeks.org/paging-in-operating-system/?ref=lbp