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

By 01/10/2018OS Concept

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

 

메인 메모리는 운영체제 뿐만 아니라 여러 사용자 프로세스도 수용해야 한다. 일반적으로 사용되는 연속 메모리 할당에 대해서 알아 보자.

 

메모리는 일반 적으로 두 개의 부분으로 나누어 진다.

  • 메모리에 상주하는 운영체제를 위한 것
  • 사용자 프로세스를 위한 것.

 

운영체제는 메모리의 어느쪽 끝에도 위치할 수 있으며 이 결정에 영향을 미치는 요인은 인터럽트 벡터 이다. 인터럽트 벡터는 흔히 0번지에 위치하기 때문에 운영체제는 하위 메모리에 위치시키는 것이 보통이다.

 

 

 

일반 적으로 여러 프로세스가 동시에 메모리에 올라와 있는 것이 바람직하기 때문에 메모리에 올라오고자 입력 큐에서 기다리는 중인 프로세스들에게 메모리를 얼만큼씩 어떻게 할당하는 것이 좋은가를 생각할 필요가 있다. 이러한 연속 메모리 할당 시스템에서는 각 프로세스는 연속된 메모리 공간을 차지하게 된다.

 

[메모리 매핑과 보호(Memory Mapping and Protection)]

재배치 레지스터는 가장 작은 물리주소의 값을 저장하고 상한 레지스터는 논리 주소의 범위 값을 결정 한다.

 

 

CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때 디스패처(dispatcher)는 문맥교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재 한다. CPU에 의해서 생성되는 모든 주소들은 이 레지스터들의 값을 참조해서 확인 작업을 하기 때문에 운영체제와 다른 사용자 프로그램의 접근으로부터 보호 할 수 있다.

 

재배치 레지스터를 사용함으로써 운영체제의 크기는 실행 중이라도 얼마든지 변경될 수 있다. 메모리에는 더 이상 사용하지 않는(작업이 끝난) 운영체제 코드가 존재 할 수 있다. 이러한 부분을 [일시적 운영 체제 코드(transient OS code)]라 부르며 이 기능을 잘 활용하면 전체 운영체제의 크기는 매우 작아 질 수 있다.

 

 

[메모리 할당(Memory Allocation)]

간단한 메모리 할당 방법은 메모리를 똑같은 고정된 크기로 분할(partition)하는 것이다. MTF라 불리우며 각 분할을 정확히 하나의 프로세스를 가질 수 있으며 이때 분할의 개수를 다중 프로그래밍 정도(multi programming degree)라 부른다. 다중 분할 방법은 한 분할이 비게 되면 한 프로세스가 입력 큐에서 선택되어 그 분할에 들어 오며 프로세스가 끝나면 다른 프로세스에 사용 될 수 있다.(현재는 거의 사용하지 않음)

 

MVT라 불리는 방법은 일괄 처리 환경에서 고정된 크기의 분할 영역을 사용하는 것이다. 또한 순수 세그멘테이션(pure segmentation)을 사용하는 시분할 환경에서 적용될 수 있는 메모리 기법들도 있다.

 

변수분할 기법에서 운용체제는 메모리의 어떤 부분이 사용되고 있고 어떤 부분이 사용되지 않고 있는가를 파악 할 수 있는 테이블을 유지 한다. 초기에 모든 메모리 공간은 한 개의 큰 사용 가능한 블록으로 간주되며(hole) 프로세스가 생성되고 기억 장소가 필요해지면 운영체제는 이 프로세스에게 충분한 크기의 공간을 찾아 주게 된다.

 

운영체제는 항상 가용 블록의 크기들과 입력 큐를 유지해야 한다. 운영체제는 공간을 차례로 할당해 주다가 메모리가 부족하면 다른 공간이 생길 때까지 프로세스를 입력 큐로 되돌려 보낸다.

 

일반적으로 메모리는 여러 크기의 공간이 산재하게 된다.(시간이 지날수록 조각화는 더 커진다.) 프로세스가 공간을 필요할 때 운영체제는 이 공간들의 집합에서 적절한 것을 찾아내는데 요청한 공간보다 큰 경우 두 부분으로 나누어서 프로세스에게 할당하고 나머지 부분을 공간(hole)로 소속 시킨다.

 

프로세스가 끝나면 할당 된 메모리를 회수하는데 이때 회수된 공간이 다른 공간 블록과 인접 하다면 이 두 개의 블록을 합쳐서 하나의 큰 공간 블록을 만들며 이 큰 공간이 필요한 프로세스에게 할당 한다. (물론 큰 공간이 없다면 다시 분할해서 할당 한다.)

 

이러한 것을 동적 공간 할당 문제(dynamic storage allocation problem)라 하며 이것은 일련의 공간집합 리스트로부터 크기 n바이트 블록을 요구하는 것을 어떻게 만족 시킬까 하는 것으로 최초 적합(first fit), 최적 적합(best-fit), 최악 적합(Worst-fit) 기법이 있다.

 

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

 

최초 적합, 최적 적합을 사용할 것인지에 대한 결정은 메모리 단편화(memory fragmentation)의 크기에 영향을 받는다.

 

 

[메모리 단편화 (Memory Fragmentation)]

위에서 기술한 알고리즘에는 메모리의 외부 단편화가 발생한다. 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면 자유 공간들이 너무 작은 조각화가 되어 버린다. 외부 단편화는 모든 조각들을 합치면 충분한 공간이 만들 수 있지만 여러 곳에 분산되어 있어 발생 한다.

 

단편화 문제는 매우 심각한 문제를 일으킬 수 있다. 최악의 경우 모든 공간들이 작은 조각으로 세분화 되어 있어 프로세스들이 사용 할 수 없는 것이다.

 

어떤 적합 모델(최초, 최적, 최악 적합)을 사용하더라도 단편화 문제는 발생 한다. 최초 적합의 경우 통계적 분석결과 N개의 블록을 할당되었을 때 0.5N 개의 블록이 단편화 때문에 손실 될 수 있다. 즉 메모리의 1/3이 쓸 수 없게 될 수 있다는 것이다. 이 현상은 50%(50 percent rule) 규칙으로 알려져 있다.

 

메모리 공간을 낭비하는 현상은 외부 단편화 뿐만 아니라 내부 단편화도 발생 할 수 있다. 내부 단편화의 예를 들면 공간이 100byte로 할당 되어 있고 어떤 프로세스가 98byte 크기의 공간을 요구한다면 98byte를 할당하고 2byte 공간을 관리하는데 더 큰 부담이 될 수 있다. 이때는 두 개의 공간으로 나누지 않고(98byte, 2byte) 요구한 공간보다 조금 더 할당(100byte) 한다. 이때 할당 받고 남은 공간이 내부 단편화(internal fragmentation) 이다.

 

외부 단편화를 해결하는 방법은 압축(compaction)과 동떨어진 곳의 공간 배정이다.

  • 압축은 은 메모리의 모든 내용은 한곳으로 이동하여 모든 자유 공간들을 모아서 한 블록의 큰 공간으로 만드는 것이다. 하지만 이렇게 하기 위해서는 실행되는 프로세스 내의 모든 주소들이 동적으로 재배치되어야 한다. 따라서 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어 지는 경우에만 가능하며 압축이 가능하더라도 비용을 검토해 보아야 한다. (대부분 비용이 많이 든다.)
  • 동떨어진 곳의 공간을 배정하는 대표적인 시스템으로는 페이징과 세그멘테이션이 있다. 세그멘테이션은 사용자의 메모리 관점과 물리적인 메모리 관점을 분리한다. 페이징과 세그멘테이션은 서로 합쳐 사용하기도 하지만 세그멘테이션 결함으로 인하여 대부분 페이징으로 사용한다.

 

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사

 

 

operation system, 운영체제, 운영체제 구조, 컴퓨터 구조, OS Concept, 메인 메모리, 주 메모리, 메모리 할당, memoryallocation, 메모리 단편화, sqlmvp, SQL Angeles

 

Leave a Reply