1. 스택 영역과 힙 영역

동적 할당을 하지 않는 메모리, 즉 스택 메모리에서는 데이터가 쌓이고 없어지는 방향이 정해져 있다. 스택은 반드시 높은 주소에서 낮은 주소 방향으로 자라고, 낮은 주소에서 높은 주소로 작아진다.

그러나, 동적 할당을 하는 힙 영역의 메모리는 그렇지 않다. 힙 메모리를 할당 할 때 낮은 주소부터 위로 할당해 주더라도, 할당된 메모리가 해제 되는데는 순서가 없다(마치 우리네 인생과 같다. 가는데는 순서 없는거다.). 할당된 힙 메모리에 구멍이 숭숭 날 수 있다는 것이다.

이 문제를 제대로 해결하지 않고 스택처럼 힙 메모리를 할당하게 된다면, 힙 메모리 공간의 크기를 다 할당하고 난 뒤에는 메모리가 해제되어도 메모리를 새로 받을 수 없을 것이다.

2-1. 대안 : 앞에서부터 차례대로 스캔하여 First-Fit 한 공간에 할당

이 방법은 필연적으로 External Fragmentation을 발생시킨다.

위 그림은 아래쪽에 있는 Fragment 영역의 메모리가 해제되면서 빈 공간이 생긴 모습이다.

새롭게 생긴 저 빈 공간의 크기보다 작은 메모리를 요청하는 경우엔 메모리 할당이 가능하지만, 그것보다 큰 메모리를 요청하면 저 공간은 메모리가 분명히 비어있음에도 불구하고 사용할 수 없게 된다.

위 예시 그림의 상황에서 사용자가 50KB의 메모리를 요청했다고 해 보자. 위 그림을 보면 분명 55KB의 여유 메모리가 있지만, 빈 메모리 공간이 파편화 되어서 50KB의 메모리를 할당해 줄 수 없는 모습이다.

저런 Fragment들은 보통 메모리 할당과 해제가 반복되면서 각 Fragment의 크기는 작아지고, 그 수는 많아지며 메모리 가용 용량에 악영향을 미친다.

2-2. 대안 : 메모리를 일정한 페이지로 나누기

메모리 전체를 일정한 크기의 페이지 단위로 나눈다. 그리고 메모리 요청이 들어올 때, 요청한 메모리 크기를 충족하는 가장 적은 개수의 페이지를 할당해 준다.

(ex : 페이지 크기가 20KB, 사용자가 요청한 메모리 크기가 50KB인 경우, 페이지 3개를 할당하여 총 60KB의 메모리 공간을 할당해 주는 것이다.)

우리가 First-Fit 방식에서 마주했던 외부 단편화(External Fragmentation) 문제를 돌아보자.

빈 메모리 공간 자체는 충분히 있었지만, 연속적으로 존재하는 빈 메모리의 용량이 충분하지 않아서 메모리를 할당해 줄 수 없었다.(총 빈 용량 : 55KB, 연속적으로 존재하는 최대 빈공간 : 30KB) 프로세스에 할당해 주는 메모리가 반드시 연속적이어야 했기 때문에 이러한 문제가 발생했던 것이다.

메모리 전체를 일정한 크기로 나누는 페이징(Paging) 기법의 가장 큰 장점은 메모리를 할당할 때, 굳이 연속적인 페이지들을 할당해 줄 필요가 없다는 것이다.

❓ 이게 말이 돼? 사실 배열은 불연속적인 메모리를 갖는 자료구조였던건가?

이 말은 반은 맞고 반은 틀리다. 이에 대한 설명은 아래 가상메모리 파트에서 다룬다.

빈 메모리는 항상 페이지 단위로 존재하기 때문에, 남아있는 총 메모리 용량이 요청받은 메모리 용량보다 크다면, 메모리는 항상 할당될 수 있는 것이다.

다만, 각 페이지의 사이즈를 크게 잡으면 페이지 내부에서 낭비되는 공간이 생긴다.

예를 들어, 페이지의 크기가 20KB인데, 사용자가 4바이트를 요청했다고 해 보자. 이런 경우에는 굉장히 많은 공간이 낭비될 것이다. 이런 현상을 내부 파편화(Internal Fragmentation)이라고 부른다.

그럼 페이지를 작게 잡으면 되지 않을까? 그게 또 그렇지만도 않다.

3. 가상 메모리

1) 개요

우리의 운영체제는 모든 프로세스에게 32비트 운영체제 기준 약 4GB의 메모리 공간을 할당해 준다.

엥? 당장 ctrl + alt + del을 눌러 작업 관리자를 보면 적어도 100개 이상의 프로세스가 돌아가고 있는데, 이들에게 정말 그렇게 큰 메모리를 할당해 주고 있을까?

당연히 거짓말이다. 프로세스에 할당되는 실제 D램의 공간은 그렇게 크지 않다.

하지만 프로세스들은 4GB 범위의 메모리 주소를 가지고 프로그램을 실행시킨다.

즉, 프로세스가 사용하는 메모리 주소와 실제 D램간의 메모리 주소에는 차이가 있다. 그리고 그 간극에는 운영체제의 ‘가상 메모리’라는 마법이 작용한다.

운영체제는 이 가상 메모리 기술을 이용해 프로세스가 사용하는 메모리 공간에 맞추어 적당한 크기의 메모리를 할당시켜 준다.

마법이라고 하기는 했지만, 사실 프로세스가 사용하는 논리(가상)주소를 D램의 실제 물리적 주소로 변환시키는 것을 말한다. 그리고 여기서 앞서 언급한 ‘페이지’의 개념이 다시 등장한다.

2) 페이지 테이블

운영체제는 프로세스가 사용하는 논리(가상) 주소 공간과 실제 물리적 메모리 공간을 같은 크기의 단위(페이지)로 자른다. (보통 논리 주소 공간상의 페이지를 ‘페이지’, 실제 물리 메모리 상의 페이지를 ‘프레임’이라고 구분지어 부른다)

그리고 프로세스는 각자 저마다의 페이지 테이블을 가지고 있는데, 운영체제가 이를 관리한다.

페이지 테이블이 하는 일을 간단하다. 몇번째 페이지가 몇번째 프레임과 매핑되어 있는지를 기록하는 것이다. 더 자세히 말하자면, 페이지 테이블의 i번째 원소에는 i번째 페이지가 몇번째 프레임과 매핑되어 있는지 저장되어 있다.

3) 논리 주소가 물리 주소로 변환되는 과정

운영체제는 페이지의 크기를 알고 있기 때문에, 메모리에서 몇개의 프레임이 나올 수 있는지 알 수 있다. 보통 총 프레임 수는 2의 거듭제곱으로 정해지도록 페이지의 크기를 잡는데, 여기엔 그만한 이유가 있다.

그 이유은 주소 변환 과정에 있다. 일반적인 컴퓨터는 주소를 나타내는데 64비트, 적어도 32비트를 사용하는 경우가 많지만, 쉬운 이해를 위해 메모리 주소를 나타내는데 16비트만 사용해 보겠다.

만약 물리 메모리에 총 2^6 = 64개의 프레임이 존재한다고 하자. 운영체제는 프로세스가 요청한 논리 주소를 실제 물리 주소로 변환할 때 다음과 같은 과정을 거친다.

1. 16비트짜리 논리 주소의 상위 6비트의 값을 읽는다. 이 값은 페이지 테이블을 참조할 때 사용하는 인덱스의 역할을 한다.
2. 나머지 10비트의 값을 읽는다. 이 값은 프레임 내에서의 오프셋, 즉 프레임 시작 주소에서 얼마나 떨어져 있는지를 나타내는 역할을 한다.
3. 앞서 읽어온 6비트 값을 인덱스로 사용하여 페이지 테이블을 참조한다. 페이지 테이블에는 프레임 번호가 적혀있다.
4. 논리 주소의 상위 6비트를 페이지 테이블에서 읽어온 값으로 대체한다. 이것이 실제 D램상에서의 주소가 된다.

이렇듯 총 프레임수를 2의 n제곱개로 정해 놓으면, 논리 주소의 상위 n개 비트를 페이지 테이블의 인덱스로 사용하여 랜덤 액세스가 가능해진다. 바로 이것이 총 프레임 수를 2의 거듭제곱 개로 설정하는 이유이다.

이제 앞서 제시했던 의문점에 대한 답을 할 시간이 되었다. 배열은 분명 연속적인 메모리 공간을 갖는 자료구조로 알고 있었는데, 사실 불연속적이었던 것일까?

정확히 말하자면, 프로세스가 배열의 데이터에 접근할 때에는 논리 주소를 사용한다.(가상 주소)그리고 배열에 있는 모든 데이터는 ‘논리 주소’상으로는 모두 연속적이다. 하지만, 만약 배열의 크기가 페이지의 크기를 넘어설 경우, 운영체제에 의해 실제 메모리, D램 상에서는 불연속적인 공간에 데이터가 저장될 수 있다.

간단한 예시를 보자.

• 운영체제 상의 페이지 크기 : 4bytes
• 사용자가 할당을 요청한 배열의 크기 : 6bytes
• 각 원소의 크기 : 1byte

사용자가 6바이트 크기의 배열을 할당 요청했으므로, 운영체제는 2개의 페이지, 8바이트 크기의 메모리를 할당해 준다.

사용자가 할당받은 배열의 이름을 arr이라고 하자. 그러면 해당 배열의 논리 주소와 물리 주소는 다음과 같이 할당될 수 있다.

논리 주소

• &arr[0] = 0x0000
• &arr[1] = 0x0001
• &arr[2] = 0x0002
• &arr[3] = 0x0003
• &arr[4] = 0x0004
• &arr[5] = 0x0005

물리 주소

• &arr[0] = 0x0000
• &arr[1] = 0x0001
• &arr[2] = 0x0002
• &arr[3] = 0x0003
• &arr[4] = 0x0008
• &arr[5] = 0x0009

4번째, 5번째 인덱스 원소의 논리 주소와 물리 주소를 보면, 논리 주소 상으로는 연속적이지만, 물리주소 상에서 3번째 인덱스 원소와 4번째 인덱스 원소는 서로 4바이트 떨어져 있다. 즉, 페이지가 불연속적으로 할당된 것이다.

당연한 얘기지만, 논리 주소를 사용하는 프로세스의 입장에서는 데이터가 D램 상에 어떻게 저장되어 있는지 신경 쓸 필요가 없다. 논리 주소를 물리 주소로 바꿔주는 것은 운영체제가 할 일이기 때문이다. 따라서 프로세스 입장에서 배열은 연속적인 메모리 공간을 갖는 자료구조인 것이다.

4) 페이지 테이블의 관리

32비트 운영체제를 생각해보자. 보통 운영체제에서 페이지의 크기는 4KB로 잡는 것이 일반적이다.(보통 보조 저장장치로부터 Block I/O를 할 때 4KB씩 데이터를 뽑아오기 때문) 이때 페이지 테이블의 크기는 어떻게 될까?

• (총 페이지 개수) = (주소 범위) / (페이지 크기) = 2^(32 - 12) = 2^20 개
• (페이지 테이블의 크기) = 2^22 바이트 = 4MB

뭔가 이상하다. 페이지 테이블의 크기가 생각보다 크다. 페이지 테이블의 크기가 하나의 페이지 크기를 넘어선다. 이 페이지 테이블도 결국 프로세스가 생성될 때마다 1개씩 할당되고 해제되기 때문에, 기본적으로 동적할당된다. 그렇다는 건, 페이지 테이블 역시 페이지 단위로 찢어져서 메모리에 저장되야 한다는 것인데, 그러면 페이지 테이블이 저장되어 있는 주소는 어떻게 물리 주소로 전환시킬까?

이 문제를 해결하기 위해 페이지 테이블을 쪼갠 후, 쪼개놓은 페이지 테이블 데이터가 저장된 프레임과 논리 주소를 연결해 주는 상위 페이지 테이블을 만든다.

위 예시에서, 페이지 테이블은 1024개로 쪼개지게 될 것이다. 따라서 새로 만들어지는 상위 페이지 테이블의 크기는 4 * 1024 = 4KB가 되며 쪼개진 페이지 테이블의 크기 역시 4KB가 된다. 딱 페이지 하나에 들어갈 수 있는 크기가 된다.

이 상황에서 프로세스가 제시한 논리 주소는 어떻게 변환될까?

간단하다. 본래 주소값의 상위 20비트를 페이지 테이블의 인덱스 값으로 사용했는데, 이제는 다음과 같이 해석한다.

• 논리주소의 상위 10비트를 상위 페이지 테이블의 인덱스로 사용하여 하위 페이지 테이블을 참조한다.
• 그 밑의 10비트는 하위 페이지 테이블의 인덱스로 사용하여 물리 메모리 상의 프레임의 주소를 찾는다.
• 나머지 비트는 프레임 내에서의 오프셋으로 사용한다.

즉, 결과적으로 페이지 테이블을 2번 참조하면 되는 것이다. 다만, 페이지 테이블 참조 횟수가 늘어났으므로 그만큼 성능에서 손해를 보게 된다.

앞서 언급했던 페이지 크기를 무작정 줄일 수 없는 이유가 여기에 있다.

1. 페이지 크기가 작아지면 그만큼 페이지 수가 늘어나야 한다.
2. 페이지 수가 늘어나면 그만큼 많은 페이지의 매핑 관계를 저장해야 하므로, 페이지 테이블 역시 커진다.
3. 그러면 위에서 본 것 처럼 페이지 테이블을 2중, 3중, 4중으로 나눠야 할 수 있다.
4. 그러면 그만큼 메모리 참조시 페이지 테이블 참조 횟수가 늘어나고, 이는 성능에 직접적인 영향을 미친다.

메모리의 참조, 할당과 해제는 프로세스가 동작하며 수도 없이 많이 일어나는 작업이다. 이 작업이 2배, 3배 느려지면 프로세스의 전체 속도가 2배, 3배 느려진다고 봐도 될 정도로 성능에 큰 영향을 줄 것이다.

이 문제를 피하고 싶다면 페이지 크기를 크게 늘려서 페이지 테이블의 크기를 줄이면 된다. 페이지의 수가 작아지면, 그만큼 필요한 페이지 테이블의 원소 수도 작아지기 때문이다. 하지만 그렇게 하면 적은 크기의 메모리 요청에도 큰 메모리가 할당되므로, 내부 단편화(Internal Fragmentation)이 심각하게 발생하여 메모리가 낭비될 것이다.

즉, 페이징 기법을 사용하게 되면 낭비되는 메모리 공간과 프로세스의 성능이 Trade-Off 관계에 놓이게 된다. 따라서 적절한 크기의 페이지를 잡아 주는 것이 중요하다.