[CS Study] OS - Memory allocation

메모리(Memory)

주로 RAM 혹은 메모리로 불리는 Random Access Memory는 컴퓨터의 주기억장치로서 현대 컴퓨터에서 작업의 중심이 되는 부품 중 하나이다. 휘발성 메모리로서 컴퓨터의 전원이 꺼지면 모두 사라지며, CPU와 보조기억장치(HDD, SSD 등) 사이에서 서로를 연결함으로써 CPU가 프로세스를 빠르게 처리할 수 있도록 돕는다. 응용 프로그램의 일시적 로딩, 데이터의 일시적인 저장 등이 RAM의 주요 역할의 예시가 될 것이다.

메모리 할당(Memory allocation)

앞서 주소 바인딩에 대해 설명하면서 프로그램이 실행되면 메모리에 적재되고, 그 과정에서 물리적 주소와 논리적 주소를 서로 연결하는 작업이 이루어진다고 하였다. 이때 메모리의 사용자 공간에서 일정 부분(물리적)을 분리하여 프로그램을 적재하는 작접을 메모리 할당이라고 한다.

메모리 할당 방법은 할당되는 메모리의 공간에 따라 크게 둘로 나눌 수 있다.

연속적 메모리 할당(Contigous memory allocation)

연속적 메모리 할당은 물리 메모리를 다수의 공간으로 분할하고, 하나의 프로세스가 하나의 공간에 적재되도록 하는 것이다. 즉, 하나의 프로세스가 메모리의 한 공간에 연속적으로 적재되는 방식이다.
연속적 메모리 할당 방식은 다시 고정 분할 방식과 가변 분할 방식으로 나뉜다.

1. 고정 분할 방식(Fixed partition allocation)
   물리적 메모리를 정해진 개수만큼의 영구적인 분할로 나누어 두고 하나의 분할에 하나의 프로세스를 적재하는 방식이다. 이때 각 분할의 크기는 서로 같을 수도, 다를 수도 있다.
   이 방식은 메모리의 관리가 수월하다는 장점이 있으나, 메모리에 적재할 수 있는 프로세스의 수가 한정적이며 수행 가능한 프로그램의 최대 크기 또한 제한되므로 가변 분할 방식에 비해 효율성이 떨어지는 방식이다.
   또한 외부 단편화 및 내부 단편화 문제가 발생할 수 있다(자세한 것은 뒤에서 다룬다).
   

2. 가변 분할 방식(Variable partition allocation)
   이는 메모리에 적재되는 프로세스의 크기에 따라 매번 분할의 크기와 개수가 동적으로 변하는 방식이다. 따라서 프로그램의 크기를 고려해 메모리를 할당하고 이를 관리하는 기술적인 기법이 필요하다.
   이 방식은 프로세스의 크기에 맞추어 메모리 공간을 사용하므로 내부 단편화는 발생하지 않는다. 다만 프로세스를 적재할 충분한 공간이 없다면 외부 단편화 문제가 발생할 수 있다.
   

가변 분할 방식에서는 프로세스들이 메모리를 할당받은 뒤 작업이 종료되어 메모리를 되돌려주는 과정에서 빈 공간, 즉 홀(Hole, 프로세스가 할당되지 않은 메모리 공간)들이 여기저기 발생하게 된다. OS는 이 홀을 다른 프로세스에 할당해주게 되는데, 이때 '어떻게' 다른 프로세스에 홀을 할당해줄지 결정해야 하며, 이 알고리즘은 일반적으로 세 가지로 분류된다.

메모리의 총 영역이 200MB, 현재 적재하고자 하는 프로세스가 2MB라고 가정하고 세 가지 방식의 차이를 확인해 보자.

1. 최초 적합(First fit)
   최초 적합은 메모리의 최초 주소부터 검색을 시작해 프로세스가 할당받을 수 있는 공간(즉 홀)을 확인하면 해당 공간에 프로세스를 할당하는 방식이다. 이 방식은 적합한 공간을 발견하는 즉시 프로세스를 할당하므로 불필요한 검색이 최소화되며, 따라서 메모리 할당 속도가 빠르다는 장점이 있다.
   

2. 최적 적합(Best fit)
   최적 적합은 사용 가능한 홀 중 프로세스와 크기가 가장 유사한 홀을 택하여 프로세스를 할당하는 방식이다. 이 방식은 메모리의 내부 단편화 문제를 최소화하기 위한 방식이다.
   

3. 최악 적합(Worst fit)
   최악 적합은 메모리의 빈 공간을 모두 확인한 후 적재 가능한 홀 중 가장 큰 공간에 프로세스를 배치하는 방법이다(프로세스의 크기와 상관없이). 이런 다소 이상한 방식이 나타난 것은 크기가 큰 프로세스를 적재할 수 있도록 큰 메모리 블록을 최대한 유지하려는 목표를 달성하기 위해서이다.
   

비연속적 메모리 할당(Noncontigous memory allocation)

비연속적 할당 방법은 말 그대로 메모리에 프로세스가 불연속적으로 할당되는 방식이다. 하나의 프로세스가 물리 메모리상의 여러 위치에 분산되어 적재되는 방식으로, 이는 다시 페이징과 세그멘테이션으로 나뉜다.

이때 몇 가지 용어를 이해하고 가면 편리하다.

• 페이지(Page) : 프로세스를 고정된 크기의 작은 블록들로 나누었을 때 그 블록을 의미
• 프레임(Frame) : 페이지 크기와 동일한 주기억장치의 메모리 블록
• 세그먼트(Segment) : 서로 다른 크기의 논리적 단위

1. 페이징(Paging)
   프로세스의 주소 공간을 고정된 크기의 페이지 단위로 나누어 메모리의 프레임에 불연속적으로 할당하는 방법이다. 페이지와 프레임을 대응시키는 페이지 매핑(Page mapping)을 위한 페이지 테이블(Page table)이 필요하며, 여기에는 각 페이지의 번호와 해당 페이지가 할당된 프레임의 시작 물리 주소가 저장된다.
   연속적이지 않은 공간도 활용할 수 있어 외부 단편화 문제가 해결된다. 그러나 프로세스의 크기가 페이지 크기의 배수가 아닌 경우 마지막 페이지에 대한 내부 단편화가 발생하며, 페이지 크기를 작게 하면 이를 일부 해결할 수 있지만 그만큼 페이지 매핑 과정이 많아져 효율성이 떨어지게 된다.
   

2. 세그멘테이션(Segmentation)
   프로세스를 가변 크기의 세그먼트로 나누어 메모리에 불연속적으로 할당하는 방식이며, 이때 세그먼트의 단위는 함수 단위일 수도 있고 논리적 단위(code, data, heap, stack 등)가 될 수도 있다. 페이징과 마찬가지로 세그먼트 매핑(Segment mapping) 과정을 위한 세그먼트 테이블(Segment table)이 필요하며, 여기에는 시작 주소와 함께 limit 정보가 주어진다(세그먼트의 크기는 각각 다르므로).
   이 방식은 프로세스가 필요로 하는 메모리 공간만큼을 각각 할당하기 때문에 내부 단편화 문제가 해결되나, 매모리 해제 시 외부 단편화 문제가 발생할 수 있다.
   

단편화(Fragmentation)

위와 같이 다양한 메모리 할당 방식을 사용하는 것은 결국 메모리를 효율적으로 사용하기 위해서이며, 조금 더 세부적으로는 메모리 단편화(Memory fragmentation) 문제를 해결하기 위해서라고 할 수 있다. 여기서 단편화(Fragmentation)란 연속된 메모리상에서 메모리가 할당될 때 프로세스가 할당되지 못하는 낭비되는 메모리 공간을 말한다. 메모리 단편화는 크게 외부 단편화와 내부 단편화로 구분할 수 있다.

외부 단편화(External fragmentation)

앞서 설명했던 연속적 메모리 할당 방식 중 가변 분할 방식으로 메모리를 할당할 경우, 혹은 세그멘테이션 방식을 이용할 경우 등에 발생 가능한 단편화 문제이다. 프로세스가 할당된 메모리 공간들 사이에 프로세스 할당이 불가능한 공간이 발생하는 경우를 말한다. 다음 예시를 보면 이해하기 쉬울 것이다.

가변 분할 방식으로 각 프로세스에 메모리를 할당하여 프로세스를 처리하던 중(왼쪽 그림), 프로세스 B와 D의 실행이 완료되어 메모리를 반환하면 각 프로세스가 차지했던 크기만큼의 빈 공간이 발생한다(오른쪽 그림). 이를 외부 단편화라 하며, 해당 공간에 적재할 수 있는 프로세스가 존재하지 않는다면 이 공간들은 빈 상태로 낭비된다. 즉, 실제로는 34kb(16kb+18kb)의 빈 공간이 존재함에도 18kb를 초과하는 프로세스는 적재할 수 없는 상황이 된다.

내부 단편화(Internal fragmentation)

내부 단편화는 연속적 메모리 할당 방식 중 고정 분할 방식으로 메모리를 할당할 경우, 혹은 페이징 방식을 이용할 경우 등에 발생 가능한 단편화 문제이다. 고정된 크기로 분할된 메모리에 할당된 프로세스의 크기가 분할된 메모리의 크기보다 작을 경우 할당되고 남는 메모리 공간이 발생한다. 이를 내부 단편화라 한다.

메모리를 20kb 크기로 분할할 경우 20kb의 배수 크기인 프로세스가 적재된다면 단편화 문제가 발생하지 않는다(큰 프로세스를 분할하여 적재하는 것이 가능하므로). 그러나 프로세스 B, D처럼 프로세스 자체의 크기가 분할된 메모리 공간보다 작거나, 혹은 프로세스 C와 같이 20kb의 배수 크기가 아니라서 분할 적재 후 남는 공간이 생길 경우 해당 메모리는 사용되지 않고 낭비된다.

메모리 압축과 통합

사실 앞서 살펴본 페이징과 세그멘테이션 모두 이 단편화 문제를 해결하기 위한 방편으로서 많이 사용되는 방법이다. 다만 단편화를 해결하기 위한 일반적인 방법 몇 가지가 더 존재하여 간단하게 확인하려 한다.

1. 메모리 압축(Compaction)
   메모리 공간을 재배치하여 사용 중인 메모리 영역과 비어 있는 메모리의 영역을 각각 한쪽으로 모은 뒤 비어 있는 영역을 하나로 통합하는 기법이다. 디스크 조각 모음이 대표적인 메모리 압축의 예시이다.
   

2. 메모리 통합(Coalescing)
   단편화가 발생하여 비어 있는 메모리 공간 중 인접한 것이 있을 경우 이들을 통합하여 더 큰 메모리 공간으로 만드는 기법이다. 메모리 압축과 달리 메모리 공간의 재배치는 일어나지 않으며, 인접한 공간끼리만 합쳐진다는 차이가 있다.
   

3. 메모리 풀(Memory pool)
   메모리 풀은 동적 할당과 조금 비슷한 방식이지만, 메모리 공간이 필요할 때마다 메모리를 할당받고 반환하는 것이 아니라, 일정한 크기만큼 메모리를 미리 할당받아 놓고 필요에 따라 할당받은 메모리를 쪼개어 사용하는 방법이다.
   일반적으로 동적 할당을 통해 메모리의 할당과 반환을 반복하면 앞서 살펴본 알고리즘에 따라 메모리 공간을 차지하므로 내부 혹은 외부 단편화가 발생한다. 그러나 메모리 풀을 이용할 경우 미리 필요할 것으로 생각되는 공간을 할당받은 뒤 그 할당받은 공간을 가져다 쓰고 반납하는 방식이므로 단편화가 발생하지 않는다.
   다만 메모리 풀을 만들었지만 사용되지 않는 공간이 많을 경우 메모리의 낭비가 발생하므로 주의해야 하며, 잦은 할당과 해제가 일어나는 경우에 사용하는 것이 바람직하다.
   ※ 앞서 정리한 스레드 풀(Thread pool)과 유사한 원리이므로 함께 보면 이해하기 쉬울 것이다.

참고 자료

• [OS] 메모리 연속할당 - 고정분할 방식과 가변분할 방식
• [운영체제] 메모리 할당, 페이징(Paging)과 세그멘테이션(Segmentation)
• 스와핑(Swapping),메모리 할당(최초 적합, 최적 적합, 최악 적합) IN OS
• [OS] 메모리 단편화, 페이징, 세그멘테이션
• [OS] 페이징(Paging)과 세그멘테이션(Segmentation)
• 메모리 단편화(Memory Fragmentation)
• 메모리 단편화(Fragmentation)에 대한 해결방법