메모리 오버레이
프로그램의 크기가 실제 물리 메모리 크기보다 클 때, 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오는 기법을 메모리 오버레이라고 한다. 전체 프로그램을 몇개의 모듈들로 나누어 컴파일하고 수행시점에 필요한 모듈만을 메모리로 적재하여 사용하는 방법이다. 오버레이 기술은 별도의 운영체제 지원이 없으므로 프로그래머가 오버레이 기술을 적용할 프로그램의 모든 구조를 완전히 알고 있어야만 한다. 그래야만 프로세스가 실행되는 각 과정별 필요한 코드 및 데이터만을 가진 모듈들을 만들 수 있기 때문이다. 메모리 관리 장치 (Memory Management Unit, MMU)가 없는 임베디드 시스템과 같은 분야에 주로 사용하는 기술이다.
스왑
사용자가 컴퓨터를 사용할 때 동시에 여러 프로그램을 실행하는 것처럼 느끼게 되는데, 이는 CPU가 각 프로세스를 순차적으로 완료하며 처리하는 것이 아닌 일정 시간동안 번갈아가며 작업을 수행하기때문에 사용자의 눈에는 동시에 여러 프로세스가 처리되는 것처럼 보여진다. 이렇게 여러개의 프로세스가 CPU를 할당 받고 반환하는 작업을 반복하며 작업을 수행하는 때 필요한 것이 스와핑 기술이다. 프로세스 하나가 메모리를 점유하고 있다가 해당 프로세스가 CPU를 반환하고 다른 프로세스가 할당받으려 할 때, CPU를 반환하려는 프로세스는 모든 코드 및 데이터를 2차 보조기억장치(disk)의 특정 영역(swap partition) 혹은 파일(swap file) 형태로 저장한다. 이를 통해 해당 프로세스가 다음번에 cpu를 할당받으면 해당 영역 또는 파일을 사용하여 프로세스를 메모리에 적재시키고, 이전에 처리된 작업 시점 부터 이어서 작업할 수 있게된다.
하지만 프로세스가 스왑되는 과정에서 CPU 유휴 시간이 길어져 시스템의 성능에 매우 좋지 않다. 이를 해결하기 위해 페이징 paging 기법이 도입되었다.
메모리 분할 방식 (가변 분할, 고정 분할)
실제 물리적 메모리는 크게 연속 할당과 불연속 할당 방식으로 나뉘고, 연속 할당 방식은 또다시 고정 분할 방식과 가변 분할 방식으로 나뉜다.
연속할당 기법은 프로세스를 메모리에 올릴 때 주소 공간을 메모리의 한 곳에 연속적으로 적재하는 방식을 말한다. 연속 할당 방식에서는 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스가 적재되도록 한다.
고정 분할, fixed partitioning
물리적 메모리를 주어진 개수 만큼의 영구적인 분할로 미리 나누어 두고 각 분할에 하나의 프로그램(프로세스)을 적재하는 방식이다. 이 분할의 크기는 모두 동일하거나 다르게 할 수 있으며, 하나의 분할에는 하나의 프로그램만 적재 가능하므로 외부 단편화 (external fragmentation)과 내부 단편화 (internal fragmentation)이 발생한다.
메모리에 올릴 수 있는 프로그램의 수가 고정되어 있으며 수행 가능한 플그램의 최대 크기 또한 제한된다는 점에서 가변 분할 방식에 비해 융통성이 떨어진다.
외부 단편화
- 프로그램의 크기 > 분할의 크기인 경우에 발생
- 프로그램을 적재하지 못하는 빈 메모리 공간으로 사용될 수 없는 작은 분할을 의미
내부 단편화
- 프로그램의 크기 < 분할의 크기인 경우 발생
- 프로그램이 분할에 적재되고 나서 분할 내부에 사용될 수 없는 메모리 조각을 의미
가변 분할, dynamic partitioning
메모리에 적재되는 프로세스 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식이다.
가변 분할 방식은 프로세스에 딱 맞게 메모리 공간을 사용하기에 내부단편화 (internal fragmentation) 문제는 발생하지 않는다. 하지만 이미 메모리에 존재하는 프로그램이 종료되고 메모리 크기보다 더 작은 크기의 새로운 프로세스가 할당될 때 외부 단편화가 발생할 수 있다.
외부 단편화 문제를 해결하기 위한 방법으로 컴팩션 (compaction, 압축) 방법이 있다. 물리적 메모리 중에서 사용중인 메모리 공간을 한쪽으로 몰고 가용 공간을 확보하는 방법이다. 메모리를 효율적으로 사용할 수 있다는 측면에서 좋은 선택이나, 수행중인 프로세스의 메모리 주소공간을 이동시켜야 하므로 비용이 매우 많이 든다는 문제점이 있다.
또한, 프로세스를 어떤 위치에 올릴지 결정하기 위한 동적 메모리 할당 문제가 있다.
최초 적합, first-fit
가장 먼저 나오는 가용 가능한 메모리 공간에 프로세스를 올리는 방법
최적 적합, best-fit
가장 딱 맞는 메모리 공간을 찾아 프로세스를 올리는 방법
최악 적합, worst-fit
가장 큰 메모리 공간에 프로세스를 올리는 방법
버디 시스템
서로 다른 크기의 연속적인 페이지들을 빈번하게 할당 및 해제하는 경우 외부 단편화가 생기는 단점이 있다. 외부 단편화란 남은 공간으로만 봤을 땐 충분해보여도 실제 커널이 요청한 사이즈를 처리할 수 있는 연속된 페이지가 없을 때를 말한다.
버디 시스템은 이러한 외부 단편화를 줄이기 위해 탄생하였는데, 이를통해 연속적인 페이지 단위로 관리가 가능하다.
1. 메인 메모리는 항상 2^N 사이즈로 할당한다.
2. 사용할 수 있는 가장 큰 메모리부터 시작해서 binary로 절반씩 쪼개나가면서 아래 조건을 만족시키는 공간을 찾는다.
3. 만약 프로세스 메모리 크기가 K라고 한다면, 2^(U-1) < K <= 2^U 를 만족시키는 U를 찾고, 2^U 만큼의 공간에 프로세스를 할당한다. 예를 들어, 프로세스 크기가 1000B이면 512B < 1000B < 1024B 이기 때문에 1024B 사이즈의 메모리에 할당하는 것이다.
4. 프로세스가 종료되고, 만약 같은 parent를 갖는 buddy공간이 비어있다면 merge 한다.연속된 페이지 프레임 256개로 구성된 그룹, 즉 1024KB를 요청한 상황을 가정해보자.
우선 버디 시스템은 사용하지 않는 모든 페이지 프레임을 그룹별로 묶어서 블록리스트 10개에 넣는다. 각 리스트는 연속된 페이지 프레임 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024로 구성된 그룹을 담는다. 블록의 첫번째 페이지 프레임의 물리적인 주소는 그룹 크기의 배수이다.
여기서 요청을 수행하기위해 먼저 256 페이지 프레임 리스트에 여유블록이 있는지 검사한다. 여유블록이 없다면 다음으로 큰 블록, 512 페이지 프레임 리스트에서 여유블록을 찾는다.
여기서 여유블록을 발견하면 페이지 프레임 512개 중 256개를 요청한 쪽으로 할당하고, 나머지 페이지 프레임 256개를 여유 256 페이지 프레임 블록 리스트에 추가한다.
버디 시스템은 가변분할 dynamic partitioning 에 비해 외부 단편화 external fragmentation이 적으며, 하위 메모리부터 공간을 사용하기 대문에 자동적으로 compaction에 대한 오버헤드가 적다. 하지만 2^N 크기의 메모리를 무조건 할당해야해서 내부단편화 internal fragmentation이 필연적으로 존재할 수 밖에 없다.
