[OS] 메인 메모리(1) - 물리, 논리주소 및 연속 메모리 할당

 

배경

---

메인 메모리는 현대 컴퓨터 시스템의 운영에 중심적인 역할을 합니다. 메모리는 각각 주소가 할당된 일련의 바이트들로 구성됩니다. CPU는 PC(program counter)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져오는데 그 명령어는 필요한 경우 추가적인 데이터를 더 가져올 수 있으며 반대로 데이터를 메모리로 내보낼 수도 있습니다. 이번 게시글에서는 메모리를 관리하는 다양한 방법에 관해 정리해 보겠습니다.

이 장의 목표

1. 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU(메모리 관리 장치)의 역할을 정리해 본다. (현재 게시글)
2. 메모리를 연속적으로 할당하기 위해 최초, 최적, 및 최악 접합 전략을 적용해 본다. (현재 게시글)
3. 단편화에 대해 알아보고 단편화의 두 가지 종류 내부 및 외부 단편화의 차이점을 정리해 본다. (현재 게시글)
4. 외부 단편화 문제를 해결하기 위한 페이징 기법을 살펴본다. (다음 게시글)
5. TLB(translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다. (다음 게시글)
6. 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다. (다음 게시글)

 

논리 주소와 물리 주소(Ligical, Physical-Address Space)

---

우리는 주소 공간을 아래와 같이 크게 두 가지로 나눌 수 있습니다.

논리 주소(logical address)	CPU가 생성하는 주소입니다. 가상 주소(virtual address)라고도 하며, 논리 주소나 가상 주소나 같은 뜻으로 사용합니다.
물리 주소(physical address)	메모리가 취급하게 되는 주소[즉, 메모리 주소 레지스터(MAR)에 주어지는 주소]입니다.

 

프로그램에 의해 생성된 모든 논리 주소 집합을 논리 주소 공간(logical address space)이라 하며 이 논리 주소와 일치하는 모든 물리 주소 집합을 물리 주소 공간(physical address space)이라 합니다. 

 프로그램의 실행 중에는 이와 같은 아래 이미지와 같이 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 관리(memory management unit, MMU)에 의해 실행됩니다.

메모리 관리 장치(MMU)

아래 이미지와 같이 MMU안에는 재배치(relocation) 레지스터가 있습니다.

재배치 레지스터를 이용한 동적 재배치

재배치 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 그 모든 주소에 더해집니다. 예를 들어, 재배치 레지스터 값이 14000이라면 프로세스가 346번지에 액세스 할 때, 실은 메인 메모리의 14346번지에 액세스 하게 됩니다.

 사용자 프로그램은 결코 실제적인 물리 주소에 접근하지 않는다는 것을 주의해야 합니다. 사용자 프로그램은 346번지에 대한 포인터를 생성해서 그것에 대해 저장, 연산, 다른 주소들과 비교하는 등 온갖 일을 할 수가 있습니다. 사용자 프로그램은 논리 주소를 사용한 것이고, 메모리 하드웨어는 논리 주소를 실제 주소로 바꾼 것입니다. 따라서 참조된 메모리 주소의 실제 위치는 이 참조가 실제 실행된 시간에 결정됩니다.

 

연속 메모리 할당

---

일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원합니다. 따라서 메모리에 적재되기를 기다리는 프로세스에 사용 가능한 메모리를 할당하는 방법을 고려해야 합니다. 연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에서 적재됩니다. 

메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션에 할당하는 것입니다. 각 파티션에는 정확히 하나의 프로세스만 적재될 수 있습니다. 이 가변 파티션 기법에서 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블을 유지합니다. 처음에는 모든 메모리가 사용자 프로세스에 사용 가능하며, 하나의 큰 사용 가능한 메모리 블록인 hole로 간주합니다. 앞으로 보겠지만 결국에는 메모리에는 다양한 크기의 hole이 생기게 됩니다.

 아래 이미지는 이 기법을 보여줍니다.

가변 파티션

1. 처음에는 프로세스 5, 8 및 2가 적재되어 있고 메모리가 완전히 활용 중입니다.
2. 프로세스 8이 종료된 후 하나의 연속된 hole이 생깁니다.
3. 나중에 프로세스 9가 도착하고 메모리가 할당됩니다.
4. 그런다음 프로세스 5가 종료되면 두 개의 연속되지 않은 hole이 생깁니다.

 프로세스가 시스템에 들어오면, 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당합니다. 프로세스가 공간을 할당받게 되면, 이후로는 CPU를 할당받기 위해 경쟁합니다. 프로세스가 끝내면 메모리를 반납하고, 운영체제는 다른 프로세스에 이 공간을 할당할 수 있습니다.

 도착 프로세스의 요구를 충족시키기에 메모리가 충분하지 않으면 어떻게 될까요? 

1. 단순히 프로세스를 거부하고 적절한 오류 메시지를 제공한다.
2. 이러한 프로세스를 대기 큐에 넣는다.
3. 메모리가 나중에 해제되면 운영체제는 대기 큐를 검사하여 대기 프로세스의 메모리 요구를 충족시킬지 여부를 결정한다.

 언급한 것처럼 일반적으로 메모리에는 다양한 크기의 hole이 여기저기 산재하게 됩니다. 프로세스에 공간이 필요할 프로세스에 공간이 필요할 때 운영체제는 이 hole의 집합에서 적절한 것을 찾아내야 합니다. 만약 hole을 찾았는데 그것이 요청한 것보다 약간 크면 두 개로 나누어 한 조각은 프로세스에 할당하고, 나머지 하나는 hole 집합으로 되돌아갑니다. 그 프로세스가 끝나면 그 공간은 hole의 집합으로 되돌아갑니다. 이 새로운 hole이 다른 hole과 인접해 있다면, 이 두 개의 블록을 합쳐서 한 개의 큰 hole로 만듭니다.

 이러한 기법은 동적 메모리 할당 문제(dynamic storage allocation problem)의 특별한 한 예입니다. 이것은 일련의 가용 공간-리스트로부터 크기 n-바이트 블록을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정하는 문제입니다. 이러한 문제에 대한 해결책은 여러 개가 제시되어 있는데 대표적으로 아래와 같은 기법들이 있습니다.

최초 적합(first-fit)	첫 번째 사용 가능한 가용 공간을 할당한다.  검색은 집합의 시작에서부터 하거나 지난번 검색이 끝났던 곳에서 시작될 수 있다.  충분히 큰 가용 공간을 찾았을 때 검색을 끝낼 수 있다.
최적 적합(best-fit)	사용 가능한 공간 중에서 가장 작은 것을 택한다. 리스트가 크기 순으로 되어 있지 않다면 전 리스트를 검색해야만 한다. 이 방법은 아주 작은 가용 공간을 만들어 낸다.
최악 적합(worst-fit)	가장 큰 가용 공간을 택한다. 이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있다. 이때 가용 공간 들이 크기 순으로 정렬되어 있지 않으면 전 리스트를 다 검색해야만 한다.

 모의실험(simulation)을 통해서 연구해 보면 최초 적합과 최적 적합 모두가 시간과 메모리 이용 효율 측면에서 최악 적합보다 좋다는 것이 입증되었습니다. 최초 적합이나 최적 적합이나 공간 효율성 측면에서는 어느 것이 항상 더 좋다고 말할 수 없지만 최초 적합이 일반적으로 속도가 더 빠릅니다.

 

단편화(Fragmentation)

---

(1) 외부 단편화(external fragmentation)

위에서 살펴본 세 가지 기법(최초 적합, 최적 적합, 최악 적합) 모두 외부 단편화(external fragmentation) 문제를 가지고 있습니다. 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 가용 공간은 너무 작은 조각이 되어 버립니다. 외부 단편화는 이처럼 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각들로 여러 곳에 분산되어 있을 때 발생하는 문제입니다. 즉, 메모리는 너무 많은 수의 매우 작은 조각들로 단편화되어 있는 것입니다. 이 단편화 문제는 매우 심각해질 수 있는데, 최악의 경우에는 모든 프로세스 사이마다 못 쓰게 된 가용 공간을 가질 수 있습니다. 이 모든 가용 공간들을 합쳐 하나의 큰 가용 공간을 만들면 여기에 여러 개의 프로세스를 실행시킬 수 있을 것입니다.

 세 가지 적합중 어느 것을 사용할 것인지에 대한 결정은 단편화의 크기에 영향을 받습니다. 어떤 시스템에서는 최초 적합이 우수하고, 다른 시스템에서는 최적 적합이 우수할 수 있기 때문입니다. 메모리의 위쪽 혹은 아래쪽 어느 부분부터 가용 공간을 할당할 것인가도 고려해야 할 요소 중의 하나입니다. 세 가지 중 어떤 전략을 선택 할더라도 외부 단편화 문제는 항상 문제로 남아있습니다.

(2) 내부 단편화(internal fragmemtation)

메모리 공간을 낭비하는 현상인 단편화는 내부적으로도 발생할 수 있습니다. 18,464B 크기의 가용 공간이 있고, 어느 한 프로세스가 18,462B를 요구한다고 가정해 봅시다. 요구된 블록을 정확히 할당하면 2B의 가용 공간(hole)이 남습니다. 일반적으로 메모리는 프로세스가 요청하면 할당을 항상 2의 지수 배 형태로 해주는 것이 보통입니다. 그렇기에 할당된 공간은 요구된 공간보다 약간 더 클 수 있습니다. 때문에 이들 두 크기 사이의 남는 부분이 바로 내부 단편화(internal fragmentation)이고, 이 내부 단편화 역시 사용이 못 되는 부분입니다.

외부 단편화를 해결할 수 있는 방법은 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법입니다. 이것은 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법입니다. 이러한 기법을 페이징 기법이라고 하는데 다음 게시글에서 이 페이징 기법에 대해 살펴보겠습니다.

[OS] 메인 메모리(2) - 페이징 기법