Memory Management

운영체제에서 중요한 부분인 메모리 관리 기능에 대해 알아보자.

메모리는 CPU 자원만큼 컴퓨터를 사용하는데 매우 중요한 자원 중 하나이다. 이전에는 운영체제에서 CPU 자원을 관리하는 프로세스 관리에 대해 살펴보았고, 지금부터는 메인 메모리를 관리하는 기능에 대해 살펴볼 것이다. 특히, 과거에는 메모리가 매우 비싼 자원이었고 크기 또한 작았기 때문에, 운영체제에서 메모리에 대한 관리가 지금보다 더 중요하였다.

현재에는 과거보다 훨씬 큰 메모리를 저렴하게 사용하지만, 지금도 메모리는 부족하다. 메모리가 커져온 만큼 프로그램의 크기와 처리하는 데이터의 크기는 그보다 더욱 빠른 속도로 커져왔다. 그러므로 현재에도 여전히 메모리를 최대한 효율적으로 사용하기 위해 여러 방법들이 연구되고 있고, 운영체제 기능에서도 매우 중요한 위치를 차지하고 있다.

1. 메모리에 프로그램 할당하기

메모리는 기본적으로 **주소(Address)**와 **데이터(Data)**로 구성되어 있다.

CPU와 메모리는 양방향으로 위 그림과 같이 주고 받는다. CPU는 주소를 가지고 메인 메모리에 요청을하거나 해당 주소에 계산 결과를 저장하고, 메모리는 요구하는 주소에 저장되어 있는 데이터를 CPU에게 전달한다.

1.1 프로그램을 빌드하는 과정

프로그램을 빌드하는 과정은 소스파일, 목적파일, 실행파일 순서로 생성된다.

1. 소스파일(Source file)
   • 고수준언어 또는 어셈블리어
2. 목적파일(Object file)
   • 컴파일 또는 어셈블 결과
3. 실행파일(Executable file)
   • 링크 결과

위 그림은 프로그램이 만들어지는 과정을 그림으로 표현한 것이다.

1. 소스파일은 컴파일러(compiler)에 의해 컴파일 수행 결과로 목적 파일을 생성한다.
   • 어셈블리어는 어셈블러가 어셈블을 수행하여 기계어로 변환한다. 프로그래밍을 하면서 외부의 라이브러리를 사용할 때가 빈번한데, 컴파일 단계에서는 이를 추가하지 않기 때문에 목적파일에는 이에 대한 정보가 없다.
2. 링크 단계에서 하드디스크에서 프로그래머가 추가한 라이브러리를 찾아 정보를 추가하여, 실행 파일을 만든다.
   • 링크 단계는 링커(linker)가 수행한다. 이 프로그램을 실행하면 로더(loader)에 의해 메인 메모리에 할당된다.

그리고 생성된 프로그램은 code, data, stack 영역으로 나뉘어져 있다. 단순히 생성된 프로그램에는 code와 data영역만 존재한다. 실제로 실행을 하는 과정에서는 함수를 실행하기 때문에, 돌아올 return address 등을 저장하는 stack도 필요하다.

1.2 MMU(Memory Management Unit)

메모리 관리를 효율적으로 해주는 OS 서비스

그렇다면, 프로그램을 실제로 메모리에 올리기 위해서는 좀 더 복잡한 과정이 필요하다. 먼저, 이 프로그램은 메모리에 몇 번지에 할당될까? 만약 운영체제가 없다면, 프로그래머가 직접 이를 처리해주어야 할 것이다. 하지만 운영체제가 존재하므로 실제 프로그래머는 이를 신경쓸 필요가 없다. 그러므로 프로그래밍을 할 때 주소를 사용하는 경우가 있는데, 프로그램이 메모리에 올라가는 주소를 고려하지 않고 프로그래밍이 가능한 것이다.(고수준언어에서는 직접 주소를 다루지 않는 경우가 많다.)

또한, 다중 프로그래밍 환경에서는 여러 프로그램이 메모리에 올라가고 내려가고를 반복하기 때문에, 한 프로그램은 고정적인 공간을 사용할 수 없다. 이러한 여러 고려 사항을 해결해주는 것이 전에도 살펴봤던 **MMU(Memory Management Unit)**이다. 그리고 MMU에는 프로그램이 메모리에 할당될 때마다 다른 주소공간을 사용하기 때문에 재배치 레지스터(Relocation register)가 별도로 존재한다.

위 그림은 MMU의 모습이다. 프로그램은 메인 메모리에 해당 주소를 사용할 수 있는지 여부를 생각하지 않고 주소를 사용한다. 만약 해당 프로그램이 사용하는 시작주소가 0번지라고 할 때, 실제 메인 메모리에서는 할당되는 주소가 유동적이기 때문에 0번지이라는 주소를 실제 할당된 주소로 변경해주어야 한다. 이때 재배치 레지스터를 이용한다.

만약, 프로그램이 메인 메모리 500번지에 할당되어 재배치 레지스터값이 500으로 설정되었다면, CPU에서 프로그램의 0번지를 사용할 때 MMU를 통과하면 재배치 레지스터에 의해 500번지로 변경된다. 그 결과 CPU는 0번지를 사용하는 것으로 알고 있지만, 실제 메모리에서는 MMU에 의해 500번지를 사용하고 있는 것이다. CPU를 속인다.

MMU(Memory Management Unit)의 기능을 살펴보면, 이전에 메모리 보호를 위해 base와 limit 레지스터가 있었다. 이는 CPU에서 주소를 사용하는데 이 주소가 해당 프로그램의 base나 limit 범위를 벗어나면 인터럽트가 발생하여 그 프로그램을 강제로 종료시킨다.

MMU는 이 기능 이외에도 재배치 레지스터를 사용해서 프로그램이 어느 주소를 사용하더라도 실제 메인 메모리에 할당된 주소를 찾아갈 수 있도록 address translation 동작을 수행한다. 즉, CPU는 프로그램에 설정된 주소를 계속 사용하고 메모리에 명령을 보내지만, MMU에 의해 실제로 프로그램이 할당된 메모리 주소로 변환해서 사용할 수 있는 것이다. 그 결과, 프로그램의 실제 메모리 주소 공간의 위치는 CPU에 전혀 영향을 미치지 않고 정상적으로 사용할 수 있는 것이다.

MMU에 의해 위 그림과 같이 주소는 두 가지로 구분된다. **CPU에서 사용하는 주소는 논리 주소(logical address)**라고 하고, **메모리가 사용하는 주소는 물리 주소(physical address)**라고 한다.

2. 메모리 낭비 방지

운영체제는 메모리를 효율적으로 사용하기 위해 메모리 공간을 낭비하지 않는 것이 중요하다.

2.1. 동적 적재(Dynamic Loading)

프로그램이 실행하는데 반드시 필요한 루틴/데이터만 적재(load)하는 것

프로그램의 전체 코드에서 모든 루틴이 다 사용되는 것은 아니다. 대표적으로 오류 처리 구문이다. 오류 처리 구문은 if문과 같이 오류가 발생할 때만 해당 내부 코드가 실행되는 것을 말한다. 그러므로 동적 적재를 수행하면 프로그램의 실제 메모리에는 이러한 오류 구문을 제외하고 적재한다. 이러한 상태에서 실행하다가 오류가 발생하면 그 때 해당 오류 구문을 찾아 메모리에 올린다.

데이터도 마찬가지다. 모든 데이터가 반드시 사용되는 것이 아니기 때문에, 특히 배열과 클래스의 경우는 필요한 부분만 메모리에 올려두고, 실행 도중 필요할 때마다 해당 부분을 찾아 메모리에 올려준다.

반대로, 모든 루틴과 데이터를 적재하는 것을 정적 적재(static loading)이라고 한다. 현대 운영체제는 대부분 동적 적재를 사용한다.

2.2. 동적 연결(Dynamic Linking)

공통으로 사용하는 라이브러리는 하나만 올리자.

동적 연결은 여러 프로그램에 공통으로 사용되는 라이브러리를 중복으로 메모리에 올리는 것이 아니라 하나만 올리도록 하는 것이다.

예를 들어, 아래와 같은 코드의 P1, P2 프로세스가 있다고 하자.

// P1
int a = 1;
int b = 2;
printf("%d\n", a + b);

// P2
int a = 1;
int b = 2;
printf("%d\n", a * b);

이 두 소스파일을 컴파일하면 목적파일이 생성되고, 여기서 사용된 라이브러리를 링크하여 실행파일을 만든 다음 메모리에 적재한다. 두 프로세스가 적재되었을 때, printf() 를 사용하는 라이브러리는 메모리에 중복되어서 적재되어있다.

이와 같이, 똑같은 라이브러리를 사용하는 프로그램은 흔히 볼 수 있다. 이러한 같은 라이브러리를 하나만 메모리에 올린 후, 이를 사용하는 프로그램이 하나의 메모리에 접근하도록 하면 메모리 낭비를 줄일 수 있다.

동적 연결은 같은 라이브러리가 중복으로 메모리에 올라가는 것을 방지하기 위해 프로그램이 메모리에 적재된 후에 링크(link) 작업을 수행한다. 기존에는 실행 파일이 만들어지기 전에 링크 과정을 수행하였는데, 이를 정적 연결이라고 한다.

위 그림은 예제에서 살펴 본 P1, P2 프로세스가 동적 연결을 통해 공통 라이브러리(printf() 라이브러리)를 연결한 모습을 볼 수 있다. 이러한 라이브러리를 Linux에서는 공유 라이브러리(Shared Library), Windows에서는 **동적 연결 라이브러리(Dynamic Linking Library, DLL)**라고 부른다.

2.3 Swapping

Swapping은 메모리에 적재되어 있는 프로세스 중에서 오랫동안 사용하지 않은 프로세스를 프로세스 이미지 형태로 만든 후 하드디스크(Backing store)에 내려보낸다. 메모리에서 Backing store로 가는 것을 swap-out, 다시 Backing store에서 메모리로 가는 것을 swap-in이라고 한다.

여기서, 프로세스 이미지는 해당 프로그램이 메모리에 적재된 후 실행되면서 데이터를 추가하거나 변경하는 등의 과정을 거치는데, 현재 데이터의 상태를 프로세스 이미지라고 부른다. 그러므로 이는 단순히, 하드디스크에 존재하는 프로그램(exe파일)과는 전혀 다른 데이터이므로, 따로 저장해야한다. 이와 같은 swapping 과정으로 인한 프로세스 이미지를 저장하기 위해 하드디스크의 일부분을 분리하여 사용하는데, 이를 backing store 또는 swap device라고 부른다.

Backing store의 크기는 대략 메인 메모리 크기 정도로 예상할 수 있다. 메모리의 모든 프로세스가 쫓겨난다고 해도 메인 메모리 크기를 넘지 않기 때문이다. 메인 메모리 크기가 크지 않는 PC나 스마트폰은 하드디스크의 일부를 backing store로 사용하지만, 메모리 크기가 크다면 따로 하드디스크 자체를 backing store로 사용하는 경우도 있다.

Swap-out된 프로세스는 다시 swap-in을 할 때, 이전의 메모리 주소 공간이 아닌 새로운 주소 공간으로 갈 수도 있다. 이는 해당 프로세스가 backing store에 있는 동안 다른 프로세스가 해당 주소 공간을 사용할 수 있기 때문에다. 하지만 이는 MMU의 재배치 레지스터로 인해 어디에 적재되는지 상관없이 정상적으로 수행할 수 있다.

현재는 프로세스의 크기가 커지고, 하드디스크는 메인 메모리보다 속도면에서 매우 느리므로 swapping 동작의 오버헤드는 크다고 볼 수 있다. 하지만 이로 인해 얻는 이득이 더 많으므로 대부분 운영체제는 이를 사용하고 있고, 속도가 중요한 서버 컴퓨터나 슈퍼 컴퓨터는 backing store를 하드디스크가 아닌 좀 더 빠른 저장 장치를 사용하기도 한다.

3. 연속 메모리 할당(Contiguous Memory Allocation)

과거에는 메모리에 프로세스가 하나만 올라가는 형태였다. 하지만 현재에는 메모리에 여러 프로세스가 할당되는 다중 프로그래밍 환경이 되었다.

부팅 직후에 메모리 상태를 살펴보면, 운영체제만 할당되어 있고 비어있는 상태일 것이다. 이러한 비어있는 공간을 hole 이라 부른다. 즉, 부팅 직후에는 운영체제와 big single hole이 있는 상태이다. 시간이 지나면서 프로세스가 생성되고 종료하고를 반복하면, 여러 곳에 서로 다른 크기의 홀(hole)이 존재할 것이다. 이러한 상태를 scattered holes라고 한다.

위 그림은 부팅 직후 상태에서 시간이 경과하면서 프로세스들이 생성, 종료를 반복한 후의 상태이다. 이와 같이 hole들이 불연속하게 흩어져 있는 상태를 메모리 단편화(Memory fragmentation) 라고 한다.

메모리 단편화로 인해서 여러 곳에 hole이 흩어져 있는 상태에서 하나의 프로세스가 메모리에 할당되려하면 문제가 발생할 수 있다. 예를 들어, hole이 3개가 있고 각 크기는 50byte, 50byte, 80byte이다. 그런데 할당하려는 프로세스의 크기는 150byte이다. 각 hole들을 하나로 합치면 230byte로 이 프로세스를 할당할 수 있는데 실재로는 나누어져 있으므로 할당되지 못한다. 이러한 현상을 외부 단편화(External fragmentation) 라고 한다. 외부 단편화를 줄이기 위해서는 어떤 해결 방법이 있을까?

3.1. 연속 메모리 할당 방식

외부 단편화의 해결방법을 살펴보기 전에 연속 메모리 할당 방식을 먼저 살펴보자. 연속 메모리 할당 방식에는 3가지가 있다. First-fit, Best-fit, Worst-fit 이 있다.

1. First-fit(최초 적합)
   • 최초 적합은 할당할 프로세스 크기보다 크거나 같은 hole을 탐색하는 순서 중에서 가장 먼저 찾은 hole에 프로세스를 할당하는 것이다.
2. Best-fit(최적 적합)
   • 최적 적합은 할당할 프로세스 크기와 hole 크기의 차이가 가장 작은 hole에 프로세스를 할당하는 것이다.(hole크기는 프로세스 크기보다 반드시 커야 한다.)
3. Worst-fit(최악 적합)
   • 최적 적합과 반대로, 할당할 프로세스 크기와 hole 크기의 차이가 가장 큰 hole에 프로세스를 할당하는 것이다.

예제

Hole id	HoleSize	Process Name	Size
1	100kb	P1	212kb
2	500kb	P2	417kb
3	600kb	P3	112kb
4	300kb	P4	426kb
5	200kb

First-fit

Best-fit

Worst-fit

각 3가지 방식대로 프로세스를 할당한 모습을 볼 수 있다. 예제의 결과를 보면 Best-fit은 4개의 프로세스를 모두 할당할 수 있었고, 나머지 2개는 마지막 P4를 할당하지 못했다. 모든 hole을 합치면 P4를 할당할 수 있지만, hole들은 각각 나눠져 있기 때문에 할당할 수 없다.(외부 단편화)

각 할당 방식의 일반적인 성능을 비교해보면, 속도면에서는 first-fit이 가장 빠르다. 메모리 이용률면에서는 first-fit, best-fit이 비슷한 성능을 낸다고 알려져있다. 하지만 여러 실험을 통해 best-fit을 사용하더라도 외부 단편화로 인해 전체 메모리의 1/3 정도를 낭비한다고 한다. 이는 거의 사용이 불가능한 수준이다.

이를 해결하는 방법 중 하나는 Compaction 이다. compaction은 여러 곳에 흩어져있는 hole들을 강제로 하나로 합치는 것이다. 하지만 hole을 옮기는 오버헤드가 너무 크고, hole과 process 두개를 하기 때문에 어떻게 옮겨야 빠르게 합칠 수 있는지에 대한 최적 알고리즘이 존재하지 않는 큰 단점이 존재한다.

Reference

• KOCW 양희재 교수님 - 운영체제
• 양희재 교수님 블로그(시험 기출 문제)
• codemcd 님의 정리글
• Operating System Concepts, 9th Edition - Abraham Silberschatz