메모리 관리

최초의 단일 프로그래밍 일괄처리 환경에서는 오로지 하나의 프로세스만이 메모리에 적재될 수 있었으므로 특별한 메모리 관리 정책이 필요하지 않았다. 그러나 이후의 모든 운영체제 유형의 기본이 되는 다중 프로그래밍 환경 즉, 메모리에 여러 개의 프로세스가 동시에 적재되는 시스템 환경에서는 어느 프로세스를 어느 부분에 어떻게 적재할 것인가 하는 메모리 관리 전략이 필요하게 됐다.

• 프로그램 전체 적재
  • 연속 할당
  • 고정분할 할당
  • 가변분할 할당
  • 비연속 할당
  • 페이징
  • 세그먼테이션
  • 페이지화된 세그멘테이션
• 프로그램 일부 적재(가상 메모리)
  • 연속 할당
  • 오버레이
  • 비연속 할당
  • 페이징
  • 페이지화된 세그먼테이션

- 전체 적재와 일부 적재, 그리고 가상 메모리

사용자가 작성한 프로그램은 텍스트(기계 명령어)와 데이터(전역 변수)로 구성되고, 실행되기 위해 메모리에 적재될 때는 이들 외에 지역 변수 및 함수 호출제어를 위한 스택 영역이 추가로 확보된다.

이때 메모리 관리 기법에 따라 텍스트와 데이터 전체가 적재되어야 하는 경우도 있고, 우선 일부만 적재된 후 참조 요구에 의해 필요한 부분이 점차 적재되기도 한다.

프로그램 전체가 적재되어야 하는 환경에서는 동시에 적재되는 프로그램들의 크기가 메모리 용량보다 적어야 하므로 다중 프로그래밍 정도가 낮아질 수밖에 없고, 메모리 용량보다 큰 프로그램은 실행될 수 없다.

반면에 프로그램 일부만 적재되어도 실행이 가능한 환경에서는 적재되어 실행 중인 프로그램들의 크기 총합이 실제 메모리 용량보다 훨씬 클 수 있다. 즉, 사용자에게 실제보다 큰 용량의 메모리를 제공하는 효과를 주게 되는데 이를 가상 메모리(Virtual Memory)라고 한다.

- 연속(Contiguous) 할당과 비연속(Non-contiguous) 할당

프로그램의 텍스트와 데이터, 그리고 스택 영역 전체를 메모리의 연속된 공간에 적재하는 방법을 연속 할당이라 하고, 메모리의 이곳저곳에 조금씩 나누어 적재하는 방법을 비연속 할당이라고 한다.

연속 할당에서는 각 프로세스에 대한 위치 정보가 시작 주소와 크기 등 두 가지로 표시될 수 있지만, 비연속 할당에서는 프로그램이 분리된 파트별로 시작 주소와 크기가 관리되어야 한다.

| 프로세스 | 시작주소 | 크기 | | -------- | -------- | ----- | | P0 | 10,000 | 5,000 | | P1 | 15,000 | 300 | | P2 | 18,000 | 4,000 |

(a) 연속 할당

| 프로세스 | 파트 | 시작주소 | 크기 | | -------- | ---- | -------- | ----- | | P0 | 0 | 10,000 | 2,000 | | P0 | 1 | 16,000 | 1,000 | | P1 | 0 | 22,000 | 2,000 |

1. 논리 주소와 물리 주소 (Logical Address, Physical Address)

C 언어 등 고급 프로그래밍 언어로 작성된 프로그램은 컴파일러와 어셈블러, 그리고 링커에 의해 하나의 완성된 목적 프로그램(실행 파일)으로 완성되는데, 이때 목적프로그램에서 명시적 혹은 묵시적으로 사용되고 있는 주소를 논리 주소라고 한다. 기호로만 표시되었던 함수나 변수들이 목적 프로그램에서는 주소로 변환되는데 이 과정을 주소의 바인딩(Binding)이라 부르며, 이 주소가 곧 논리 주소가 된다.

논리 주소와 달리, 프로그램이 실행되기 위해 적재된 실제 메모리의 주소를 물리 주소라고 한다.

CPU는 메모리 접근을 위해 주소 버스에 설정한 주소값을 가로채서 적절한 물리 주소로 변환하고, 변환하는 부분을 MMU(Memory Management Unit)라고 한다.

MMU에 의한 논리 주소와 물리 주소의 분리는 사용자 프로그래밍 과정에 매우 편리한 환경을 제공한다. 프로그래머는 자신의 프로그램이 메모리의 어느 곳에 적재될지에 걱정 없이 임의의 번지를 가정하고 목적 프로그램을 생산하면 된다.

2. 단일 프로그래밍 메모리 관리

초창기 단일 프로그래밍 일괄 처리 시스템은 메모리에 오직 하나의 프로세스만이 존재하므로 논리 주소와 물리 주소를 구분할 필요와 메모리의 이곳저곳에 나누어 분산 적재할 필요가 없다.

즉, 사용자 프로세스 영역으로 지정된 부분부터 연속적으로 할당하면 된다. 다만, 운영체제 영역을 보호하고, 메모리 용량을 초과하는 프로그램을 실행시킬 수 있는 다른 방안이 필요하다.

- 경계 레지스터(BR: Boundary Register)에 의한 운영체제 영역 보호

경계 레지스터에는 사용자 프로세스 영역과 운영체제 영역이 접하는 주소를 저장한다. 만약 사용자 프로세스가 경계 레지스터에 기록된 주소값을 벗어난 지점에 대한 참조를 시도하면 하드웨어 인터럽트가 발생하여 제어 흐름이 운영체제로 이동하고, 해당 프로세스는 운영체제에 의해 강제 종료된다.

- 오버레이(Overlay, 중첩)에 의한 메모리 용량 초과 프로그램의 실행

단일 프로그래밍 환경에서 프로그램의 크기가 메모리 영역을 초과하면 프로그램을 적절하게 분리하여, 필요할 때마다 분리된 부분을 같은 메모리 영역에 번갈아 적재해가면 실행하는 방법을 오버레이라고 한다.

오버레이는 운영체제에 의해 자동으로 이루어지는 것이 아니고, 프로그래머의 세심한 설계에 따라 실행 중 요구하는 시스템 콜에 의해 이루어지므로 일종의 동적 적재(Dynamic Loading)라 할 수 있다. 이를테면, 어셈블러 경우 전처리(Pre-process) 패스 1(Pass 1), 패스 2(Pass 2)로 구성되는데, 이들 세 부분을 차례차례 독립적으로 처리되므로 어셈블러 전체를 한꺼번에 적재하지 않아도 무방하다.

3. 고정 분할과 가변 분할(Fixed Partition, Varible Partition)

여러 개의 프로그램을 동시 적재하는 다중 프로그래밍을 위해서는 무엇보다 먼저 메모리의 분할이 필요하다.

고정 분할

고정 분할이란 메모리를 미리 고정적으로 분할시켜 놓고, 공간이 비워질 때마다 새로운 프로그램을 적재하는 방법이다.

- 운영체제 및 다른 프로세스 보호

각 분할의 위치는 시작 주소와 끝 주소로 명시되므로, 어느 분할에서 실행 중인 프로세스는 해당 분할의 범위를 벗어난 영역을 참조할 수 없다. 단일 프로그래밍의 경계 레지스터와 동일한 개념으로 분할의 상/하한. 경계 레지스터를 사용하여 운영체제 및 다른 프로세스를 보호할 수 있다.

- 분할의 크기

고정 분할의 가장 큰 단점은 사용자 프로그램의 크기에 꼭 맞는 메모리 공간을 제공할 수 없으므로 메모리 일부를 활용하지 못하는 데 있다. 이와 같은 현상을 내부 단편화(Internal Fragmentation)라고 부른다.

고정 분할의 또 다른 문제는, 가장 큰 분할에조차 적재될 수 없는 큰 프로그램은 실행될 수 없다는 점이다. 이를 해결하기 위해 인접한 여러 개의 분할을 일시적으로 통학하여 적재하는 방안이 있는데, 이는 어디까지나 인접한 분할들이 모두 비어있는 경우에만 가능하므로 큰 프로그램은 기아 상태가 초래된다.

분할의 크기는 동시에 적재할 수 있는 프로세스의 수에도 영향을 미친다. 다중 프로그래밍의 정도를 높이기 위해 분할을 여러 개 만들면 분할의 크기가 작아지고, 반대로 분할의 크기를 높이면 다중 프로그래밍 정도가 낮아질 수밖에 없다.

• 고정 분할은 관리가 간단하지만, 내부 단편화에 의한 메모리 낭비를 피할 수 없고, 실행 가능한 프로그램의 최대 크기가 제한된다.

가변 분할

고정 분할의 내부 단편화 문제를 해결하기 위해 비어있는 공간을 정확히 프로그램의 크기만큼만을 할당하는 방법이 있는데 이를 가변 분할이라고 한다.

가변 분할에서는 분할의 개수 및 시작과 끝이 고정되어 있지 않고, 프로세스의 종료 및 적재가 일어날 때마다 변한다.

그러나 할당과 반납이 진행되면서 크기가 아주 작은 빈 분할들이 늘어나 이들이 비어 있는데도 불구하고 활용되지 못하는 상황이 발생한다. 이처럼 빈 공간이 있지만 크기가 너무 작아서 할당되지 못하는 현상을 외부 단편화(External Fragmentation)이라 부르고, 이러한 작은 분할을 홀(Hole)이라 한다.

외부 단편화 문제를 완화하기 위해서는 적절한 할당 정책, 인접한 빈 공간의 병합(Coalescing), 빈 공간 전체의 통합(Compaction) 등의 조치가 필요하다.

- 가변 분할의 할당 정책

할당 정책은 다양한 크기의 비어있는 분할들이 있을 때 어느 분할에서 요구 메모리를 할당하는 것인가를 선택하는 문제다.

최적 적합(Best-fit) 할당:

분할의 크기가 할당 요구 크기에 가장 근접하는 분할을 선택하여 할당 방법이다. 할당하고 남은 부분이 아주 작은 분할이 되어, 결국 새로운 작은 빈 분할을 낳는다.

최악 적합(Worst-fit) 할당:

최적 적합과는 반대로 가장 큰 분할에서 할당하는 방법이다. 큰 분할부터 계속 작은 분할로 변해간다는 단점이 있다.

최초 적합(First-fit) 할당:

빈 분할의 크기와는 관계없이 무조건 할당 요구를 만족하는 최초의 분할에서 할당하는 전략으로, 랜덤 효과를 얻으면서도 검색 부담을 줄이는 장점이 있다.

순차 적합(Next-fit) 할당:

최초 적합 할당에서 검색은 매번 메모리 앞부분의 동일한 부분부터 이루어지므로 작은 분할들이 더 많이 발생할 가능성이 있다.

순차 적합은 랜덤 할당 성질을 더욱 강화하여 할당이 이루어진 분할을 기록해두었다가 다음번 검색은 바로 그다음 분할부터 이루어지도록 하는 방법이다.

- 인접한 빈 분할들의 병합(Coalescing)

할당되었던 분할이 반납되어 빈 할당이 되었을 때, 앞이나 뒤에 인접한 빈 분할이 존재한다면 이들 분할들을 병합하여 하나의 큰 빈 분할로 만들어 관리한다면 다음번 할당 시 외부 단편화 문제를 줄일 수 있다.

- 분산된 빈 분할들의 통합(Compaction)

인접한 빈 분할들을 모두 통합했는데도 불구하고 빈 분할들이 여러 곳에 분산되어 있으면 외부 단편화 문제로 메모리 활용률이 크게 저하된다. 이를 해결하기 위해서는 할당된 분할과 빈 분할들의 위치를 바꾸어 빈 분할들을 큰 분할로 병합해야 하는데 이를 통합이라 부른다.

통합에 있어서 가장 큰 부담은 할당된 분할 즉, 프로세스의 적재 위치가 변경됨에 따라 재배치가 이루어져야 한다는 점인데 MMU에 의해 쉽게 해결된다.

4. 페이징(Paging)

프로그램을 원래 모양 그대로 메모리에 적재하는 환경에 적합한 고정 분할이나 가변 분할과는 달리, 프로그램을 여러 개의 조각으로 분리하여 메모리에 분산하여 적재하는 페이징과 세그먼테이션이 있다.

이 방법들은 프로그램을 분리하여 분산 적재하므로 비연속 할당 방법이고, 페이징과 세그먼테이션의 차이점은 프로그램을 조각으로 분리하는 방법에 있다.

페이징은 프로그램 전체를 일정한 크기의 작은 조각으로 분리하여 메모리에 적재한다. 이때 각각의 조각을 페이지(Page)라 하고, 페이지는 시스템에 따라 보통 512~8K 바이트 크기를 가진다.

페이징에서는 프로그램을 페이지 단위로 분리하여 적재하므로 메모리 할당 단위 또한 페이지 단위로 이루어져야 한다. 즉, 메모리가 페이지 크기와 동일한 조각으로 분할되어야 하는데 그 각각을 페이지 프레임(Page Frame)이라 부른다.

페이지들로 분리된 프로그램은 메모리 이곳저곳에 산재하는 빈 페이지 프레임들에 적재되므로, 특정 프로그램이 적재된 메모리 정보는 페이지들과 페이지 프레임들의 대응 관계가 표로 관리되어야 하는데 그 표를 페이지 테이블(Page Table)이라 부른다.

논리 주소의 물리 주소 변환

프로그램의 시작 주소가 0이라면 프로그램이 적재된 직후 운영체제는 이 프로세스에게 CPU의 PC를 0으로 설정하여 CPU를 할당한다. CPU는 첫 명령어를 인출하기 위해 논리 주소 0을 주소 버스에 올리고 메모리 접근을 시도할 것인데, 이때 MMU가 페이지 테이블을 이용하여 대응되는 물리 주소로 변환한다.

성능 개선을 위한 페이징 MMU 구조

페이징 MMU의 가장 큰 문제점은 메모리 접근을 하기 전에 물리 주소를 얻기 위해 반드시 페이지 테이블을 참조한다는 것이다. 즉, 페이지 테이블 또한 메모리에 존재하므로 결국 메모리에 접근할 때마다 두 번의 메모리 참조가 이루어져 성능이 1/2로 반감된다는 것이다.

이를 해결하기 위해 물리 주소 변환 과정에 고속의 캐시 메모리 소자로 구성된 하드웨어 연관 메모리(associative memroy) 구조를 사용한다. 연관 메모리란 저장된 내용을 주소에 의해 읽는 것이 아니라, 저장된 내용 일부와 일치하는 내용을 병렬 검색 회로에 의해 읽어 낸다. (캐싱)

페이징 시스템 분석

프로그램의 크기가 정확하게 페이지 크기의 배수가 된다는 보장이 없으므로 마지막 페이지에서 약간의 내부 단편화가 발생한다. 이는 페이지의 크기가 클수록 심화된다. 반대로 이를 해결하기 위해 페이지 크기를 줄이면 페이지 테이블을 위한 메모리가 더 많이 사용된다는 단점이 있다.

페이징 시스템에서의 보호와 공유

페이징 시스템 구조 자체의 특성상 어느 프로세스도 자신의 메모리 영역을 벗어나 운영체제네 다른 프로세스의 메모리 영역을 침범할 수 없다. 즉, 페이지 테이블에 연결된 페이지 프레임 외에는 주소 변환이 결코 일어나지 않는다는 것이다.

페이지 테이블을 적절하게 잘 구성하면 내부 페이지들에 대한 세밀한 보호 모드를 설정하여 운영할 수 있다. 예를 들어 읽기(r), 쓰기(w), 실행(x) 등의 보호 비트 3개를 추가하여 페이지에 가능 여부를 표시하면 허용되지 않은 참조 접근을 차단할 수 있다.

일반적으로 프로그램의 기계 명령어 부분(텍스트)에는 읽기와 실행만 허용하고, 변수(데이터)나 스택 부분은 읽기와 쓰기만 허용함으로써 해킹 행위등을 예방한다.

또한 페이징 시스템에서는 페이지의 공유가 매우 용이하다. 페이지의 공유란 두 프로세스가 동일한 페이지를 동시에 참조하는 것을 말한다. 예를 들어 인턴넷 브라우져등 동일한 프로그램을 여러 번 실행하여 적재하는 경우 기계 명령어는 모두 동일하고 실행 도중 내내 변경도 일어나지 않으므로, 각각 따로 적재하지 않고 한 벌만 적재하여 공유하면 메모리를 크게 절약할 수 있다.

5. 세그먼테이션 (Segmentation)

사용자 프로그램을 조각으로 분리하여 메모리에 분산해서 적재하고, MMU가 매핑 테이블을 이용해 논리 주소를 물리 주소를 변환한다는 개념에서 세그먼테이션과 페이지는 같다.

그러나 세그먼테이션은 사용자 프로그램을 균일한 작은 조각(페이지)으로 분리하는 것이 아니고, 프로그램 이미지를 구성 부위별 특성에 따라 분리한다는 점에서 다르다. 이때 같은 특성으로 구별되는 묶음들을 세그먼트라 부른다.

보통 프로그램 이미지는 텍스트(기계 명령어), 데이터(전역 변수), 스택(지역 변수 및 서브 루틴 호출 관리), 공유 라이브러리 등 최대 7~8개의 세그먼트로 구성된다. 세그먼트는 프로그램 이미지를 논리적인 특성을 기준으로 분리한 단위를 의미하므로 하나의 큰 덩어리라 말할 수 있고, 그들의 크기는 각각 다르고 비교적 크다.

세그먼트의 보호 및 공유

페이징에서와 마찬가지 방법으로 세그멘트 테이블을 이용하면 세그먼트의 보호와 공유를 쉽게 구현할 수 있다.

예를 들어, 유닉스의 vi 같은 편집기가 두 번 실행 되었을 때, 편집기 프로그램의 이미지는 텍스트, 데이터 , 스택 등 3개의 세그먼트로 구성되어 있다. 이 중 텍스트(기계 명령어)는 두 프로세스 모두 같고 변경이 없으므로 공유되고 있다. 반면에 데이터와 스택은 사용자가 편집을 진행하는 과정에서 각각 고유하게 변경되어 가므로 각각 독립적으로 할당되어야 한다.

세그먼테이션 분석

페이징에 대비되는 세그먼테이션의 가장 눈에 띄는 점은 프로그램의 이미지를 구성 부위별에 따라 크기가 제각각인 3~8개의 세그먼트로 분리하여 적재하므로 세그먼트 테이블에 할당 주소와 길이가 관리되어야 하고, 세그먼트 테이블 항목이 소수여서 테이블의 자체의 크기가 작다는 점이다.

또한, 세그멘테이션에서는 메모리를 정확히 세그먼트 크기에 맞추어 할당하므로 내부 단편화가 발생하지 않는다. 그러나, 세그먼트별 메모리 할당이 가변 할당 방식으로 이루어지므로 홀에 의한 외부 단편화 문제가 심각하게 나타날 수 있다.

5. 페이지화 된 세그먼테이션(Segmentation with Paging)

세그먼테이션의 가장 큰 문제점 중 하나는 각각의 세그먼테이션을 가변 분할 정책으로 연속적으로 할당함으로써 피할 수 없는 외부 단편화 문제이다. 반면에 페이징에서는 프로그램 이미지가 너무 작은 조각들로 분리되어 페이지별 보호 등의 관리를 위한 부담이 크다.

이와 같은 두 시스템의 단점을 보완하는 방법으로 논리적 특성에 따라 분리된 세그먼트를 다시 페이지 단위로 분리하여 적재하는 페이지화된 세그먼테이션 시스템이 도입되었다. 유닉스 등 현대 범용 운영체제는 거의 모두 이 방법을 쓴다.

페이지화된 세그먼테이션의 페이지 테이블은 로 구성되는데, 세그먼트 번호 s와 페이지 번호 p는 검색 키로, 그리고 페이지 프레임 번호 f는 출력값으로 사용된다.