연속 메모리 할당

연속 메모리 할당 개념.
초기 컴퓨터 시스템에 적용한 메모리 관리 기법.
실행될 모든 프로그램은 필요한 영역만큼 연속적인 메모리 공간을 할당 받아 메모리에 적재.
한번에 적재 불가능하면 실행이 불가능하므로, 프로그램 수정 및 작은 모듈로 구성해야 함.

단일 사용자 연속 메모리 할당.
메모리 영역을 사용자를 위한 공간과 운영체제 상주를 위한 공간으로 구분.
운영체제를 메모리의 하위나 상위에 두는 것이 가능함.
메모리를 운영체제 루틴이 들어 있는 부분(모니터)과 사용자 프로그램이 들어있는 부분(사용자), 사용되지 않는 부분으로 구분(그림 7-8(a)).
사용자가 모든 메인 메모리에 대한 제어권을 가짐.
- 운영체제 파괴를 막기 위해 프로세서 내에 경계 레지스터를 둠(그림 7-8(b)).
- 사용자 프로그램이 메모리 주소를 참조할 때마다 경계 레지스터를 검사한 후 실행됨.

문제점.
사용자 프로그램의 적재.
- 컴퓨터 주소 공간이 0000부터 시작하더라도 사용자 프로그램의 처음 주소는 0000번지가 아니라 기준 레지스터 값 이후가 되므로, 기준 주소가 변하면 다시 적재해야 함.

해결 방법.
사용자 프로그램을 기준으로 상위 주소에 적재하지 않고 기준 레지스터로부터 내려가는 상위 메모리에 적재.
- 사용되지 않은 모든 공간이 중간에 있고, 운영체제나 사용자는 필요에 따라 사용되지 않은 공간으로 확장 가능.
수행할 때까지 주소 바인딩을 연기함.
- 동적 적재를 위한, 주소 바인딩을 연기하기 위한 기준 레지스터(재배치 레지스터)가 필요함.
- 기준 레지스터에 있는 값은 사용자 프로세스가 메모리로 보내질 때 생성되는 주소값에 더해짐.
ex: 기준값이 1400일 경우, 주소 0에 대한 사용자 프로세스는 동적으로 1400으로 재배치, 주소 346에 대한  접근은 17446으로 재배치됨.

※ 한 번에 한 프로그램만 사용 가능하며, 메모리의 효율성이 떨어지고 다중 프로그래밍이 불가능함.
※ 논리적 메모리가 물리적 메모리보다 작을 때만 프로그램을 수행할 수 있음.

교체 기법.
메인 메모리보다 더 큰 프로그램을 실행할 수 있으므로 제한된 메인 메모리를 확장시키는 방법으로 사용됨.
단일 사용자 연속 메모리 할당 시스템이 프로세서 중심 작업 일 경우.
- 프로세서를 집중적으로 사용 가능.
- 입출력 작업이 교대로 발생하는 경우에 프로세서의 유휴 상태가 자주 발생함.

※ 단순하고 사용자 공간이 확대되는 장점을 가짐.
- 운영체제 부분이 작아도 가능.
※ 자원의 낭비가 심하며, 프로세스 교체 비용이 크고 입출력 때 프로세스가 유휴 상태가 되며, 사용되지 않는 프로그램의 적재 발생.
- 프로그램이 차지하고 남은 부분에 대한 활용이 불가능함.

고정 분할 다중 프로그래밍
MFT(Multiprogramming with a Fixed number of Tasks) 메모리 할당 방법.
IBM OS/360에서 사용되었으나, 현재는 사용되지 않음.
고정된 크기의 분할 영역에 프로세스(작업)가 각각 할당됨.
물리 주소는 분할 기준 레지스터(PBR) 값에 논리 주소를 더하여 생성됨.
- 논리 주소가 분할 영역 크기보다 크면 오류 발생.
- 분할 영역보다 프로세스의 크기가 대부분 작으므로 내부 단편화가 발생함.

분할의 수에 고정 분할 다중 프로그래밍의 성능이 제한 받음.
- 분할 영역이 비면 프로세스는 프로세스 큐에서 하나를 선택하여 빈 분할에 적재.
- 프로세스의 작업이 끝나면 그 분할은 다른 프로세스가 이용 가능.

[그림 7-12] 고정 분할 시스템 예.
프로세스 큐 하나의 크기가 2KB인 Q2, 6KB인 Q6, 12KB인 Q12가 있는 경우.
작업량이 2KB 미만은 Q2로, 6KB 미만은 Q6, 12KB 미만은 Q12로 보냄.
큐에 할당하는 과정은 자동적으로 처리되며, 최대 메모리 요구량을 큐에 표시함.
각 큐는 자신의 기억 영역을 가지므로 큐 사이에 경쟁은 없음.

문제점.
- 크기에 따라 각 분할 영역을 담당하는 큐가 있어 Q12 큐가 이미 다 차있는 경우, 다른 큐(Q2, Q6)가 비어있더라도  큐를 이용할 수 없음.

[그림 7-13] 통합 큐 운영 고정 분할 시스템.
모든 작업을 하나의 통합 큐에 넣고 운영.
문제점.
- 작업 스케줄러는 수행할 다른 작업을 선택, 그 크기의 메모리 공간을 이용할 수 있을 때까지 대기함.

통합 큐 운영 고정 분할 시스템 예.
- 2KB, 6KB, 12KB의 분할된 메모리 여역과 선입 선처리 작업 스케줄러, 작업 큐를 가진다 가정함.
- 작업이 5KB, 2KB, 3KB, 7KB 순으로 도착했다면,
① 작업 1(5KB)을 6KB 영역에, 작업 2(2KB)를 2KB 영역에 할당.
② 작업 1이 끝난 후 작업 3(3KB)이 6KB 영역에 할당됨.
③ 작업 4(7KB)는 작업 4를 위한 영역(12KB)이 비어 있다해도 작업 스케줄러가 선입 선처리 기법을 사용하므로,  작업 3이 할당될 때까지 대기해야 함.

다중 프로그래밍의 성능 향상을 위해 다음 사항을 결정해야 함.
분할 영역의 크기.
- 시스템 부하를 분석, 영역의 개수와 크기를 결정.
- 영역의 개수는 다중 프로그래밍의 정도가 될 수 있으며, 영역의 크기 결정은 시스템 전체의 효율을 나타냄.
영역의 배정.
- 프로그램 작업을 어느 영역에 배정하는 지에 대한 결정.
- 결정을 위해 작업 스케줄러가 필요함.

고정 분할 다중 프로그래밍에서의 단편화
메모리의 단편화(Fragmentation)는 메모리 구성과 관계없이 모든 컴퓨터 시스템에서 발생함.
고정 분할 다중 프로그래밍에서의 단편화.
- 사용자 작업의 크기가 지정된 분할에 정확히 맞지 않거나 분할이 너무 작아서 대기 중인 작업 중 하나도 맞는  것이 없는 상태.
- 분할된 공간은 사용되지 않고 남아 내부 단편화의 원인이 됨.
[그림 7-14] 다수의 영역을 할당한 메모리 영역.
18,464byte의 사용가능 공간이 있을 때 프로세스가 18,462byte를 요구한다 가정함.
요구된 블록을 정확히 할당하면 2byte의 사용가능 공간이 남음.
남은 2byte의 사용가능 공간을 활용하기 위한 처리비용은 사용가능 공간을 활용하는 비용보다 큼.
이러한 부분을 내부 단편화라 부르며, 대부분 사용할 수 없는 공간임.

[그림 7-15]내부 단편화.
시스템의 메모리(32KB)가 10KB의 운영체제 1개, 10KB의 사용자 공간 1개, 4KB의 사용자 공간 3개로 나뉜다고 가정함.
작업 큐에 7KB, 3KB, 6KB, 6KB를 요구하는 작업이 있다면,
- 7KB의 작업을 10KB 영역에(3KB 내부 단편화), 3KB 작업을 4KB 영역 중 하나에 할당(1KB 내부 단편화).
- 이때 6KB의 작업은 할당할 수 없음.
시스템 메모리 영역을 10KB, 8KB, 4KB로 나누면,
- 7KB 작업은 8KB 영역에서, 3KB 작업은 4KB 영역에서, 6KB 작업은 10KB 영역에서 수행되어 모두  6KB의 내부 단편화가 발생함.
- 할당하는 과정에서 7KB 작업을 10KB 영역에 할당 가능함.

단편화는 작업 스케줄러와 분할의 크기에 의해 좌우됨.
메모리의 낭비를 가져오므로 어떤 분할에서도 실행 가능한 재배치 가능 프로그램을 만들어야 함.
고정 분할은 효율적인 메모리 운영이 가능하나 기억 장소의 낭비가 있음.
메모리에 상주해야 하는 프로세스들이 있으므로 메모리 보호가 필요함.

[그림 7-16] 고정분할에서의 메모리 보호.
두 개의 레지스터(기준 레지스터와 한계 레지스터)를 사용하여 분할된 영역 보호.
- 기준 레지스터 : 가장 작은 합법적인 물리 메모리 주소(300040)를 저장.
- 한계 레지스터 : 프로그램 영역이 저장되어 있는 범위의 크기(120900)를 저장.

고정분할에서의 메모리 보호 예.
[그림 7-16]에서 작업 2는 가장 작은 물리적 주소의 하한값이 300040이고, 크기가 120900인 프로세스임.
- 기준 레지스터의 가장 작은 물리적 주소는 300040이며, 한계 레지스터는 논리 주소 120900임.
- 사용자 주소 범위는 0~120900으로, 논리 주소는 한계 레지스터 주소보다 작아야 함.
- 프로세스의 상한값은 420940(=기준 레지스터(300040)+한계 레지스터(120900))이 되므로,  사용자 주소 범위는 상한값과 하한값 사이가 됨.

프로세서에 의해 생성된 모든 주소는 레지스터와 함께 검사되므로 다른 사용자의 프로그램과 데이터를 보호할 수 있음.

가변 분할 다중 프로그래밍(MVT, Multiprogramming with a Variable number of Tasks)
고정된 경계를 없애고 각 작업이 필요한 만큼만 메모리를 할당.
각 프로세스(분할 영역)를 나타내기 위해 기준(재배치) 레지스터와 한계 레지스터를 사용.
한계 레지스터는 프로세스 크기만큼의 영역에 저장.
- 프로세서에 의해 생성된 논리 주소가 한계 레지스터 값보다 크면 오류 발생.
[그림 7-18] 가변분할 다중프로그래밍 예.
- 분할 테이블에 있는 P3의 경우 한계 레지스터(250), 기준 레지스터(5034)와 매핑, 물리 메모리 공간에 저장됨.

운영체제는 메모리의 사용 내역을 확인할 수 있는 테이블을 유지해야 함.
256KB의 이용할 수 있는 메모리와 40KB 크기의 운영체제 그리고 작업 큐에 [그림 7-19]와 같이 작업을 가진다 가정함.

- 작업 1(60KB), 작업 2(100KB), 작업 3(30KB)에 메모리를 할당하여 기억장소 작성(그림 7-20(a)).
- 5시간 후 작업 2가 종료되면서 사용했던 메모리 할당량을 해제(그림 7-20(b)).
- 작업 4가 스케줄되어 할당됨(그림 7-20(c)).
- 작업 1이 10시간 후에 종료되면 메모리가 해제됨(그림 7-20(d)).
- 작업 5에 메모리 할당(그림 7-20(e)).
가변 분할(동적 메모리 할당)는 요구된 크기 n을 사용가능 공간에 어떻게 할당하느냐의 문제임.
예 : 최초 적합(First-Fit), 최상 적합(Best-Fit), 최악 적합(Worst-Fit) 등.

메모리 재배치 기법
최초 적합 기법
프로세스는 사용가능공간 리스트에서 충분히 큰 첫 번째 공백 분할 공간에 할당됨.
검색은 사용가능공간 리스트의 맨 앞에서 시작하거나 이전의 최초 적합 검색이 끝났던 곳에서 시작됨.
검색은 빠르나 공간 활용률이 떨어짐.

최상 적합 기법
프로세스가 들어갈 수 있는 충분히 큰 사용가능공간 중에서 가장 작은 크기의 사용 공간에 작업을 할당함.
사용가능공간에 대한 지속적인 정렬과정이 필요하여 비효율적임.
- 공간 리스트가 크기 순서로 정렬되어 있지 않을 시 전 리스트를 검색해야 함.
사용가능공간 이용률은 향상되나 할당되는 과정에 많은 시간이 소요됨.
가장 작은 또 다른 사용가능공간 생성 가능.

최악 적합 기법
작업을 가장 큰 사용가능공간에 할당함.
공간이 크기 순서로 정렬되어 있지 않을 시 전 리스트를 검색해야 함.
최상 적합보다 메모리 활용면에서 더 유용함.

※ 시간과 메모리 이용률 감소 측면에서 최초 적합과 최상 적합이 유용함.
※ 일반적으로 최초 적합이 최상 적합보다 메모리 할당이 더 빠름.

가변 분할에서의 메모리 보호
프로세스 보호를 위해 두 개의 경계 레지스터 사용.
상한값과 하한값을 갖는 기준 레지스터와 한계 레지스터를 사용.
- 가장 작은 물리적 주소의 하한값이 100040 이고 크기가 74600인 프로세스인 경우
- 상한값은 174640(=100040+74600)이며, 사용자 주소 범위는 하한값과 상한값 사이임.
기준 레지스터 및 한계 레지스터는 수행시간에 동적 재배치를 허용함.
- 기준 레지스터가 가장 작은 물리적 주소로 100040이며, 한계 레지스터가 논리 주소 76400을 포함할 경우
- 사용자 주소 범위는 ‘0~76400’임.
논리 주소는 한계 레지스터보다 작아야 하며 기준 레지스터에 추가하여 동적 재배치됨.
- ‘100040~174639’범위 내에서 동적으로 재배치되며, 재배치된 주소는 메모리로 전송됨.
프로세서 스케줄러가 프로세스 선택 시, 디스패처는 정확한 값을 가진 두 경계 레지스터를 함께 적재함.
- 프로세서가 생성한 모든 주소는 레지스터와 함께 검사되므로 다른 사용자의 프로그램과 데이터 보호 가능.

외부 단편화
가변 분할 알고리즘은 외부 단편화 문제가 발생함.
프로세스들이 메모리에서 제거되고 새로운 프로세스가 적재될 때 사용가능공간은 작게 나뉘어짐.
프로세스들이 연속된 메모리를 차지하는 과정에서 공백이 발생, 사용가능공간은 많은 수의 작은 공간으로 단편화될 수 있음.
분할은 프로세스가 요구한 크기로 만들어지므로 내부 단편화는 거의 없으나 외부 단편화는 발생할 수 있음.

[그림 7-20] 외부 단편화 예.

그림 7-20의 (a)에서 26KB의 외부 단편화 발생.
- 이 공간은 너무 작아 나머지 프로세스 작업 4와 작업 5를 만족시킬 수 없음.
그림 7-20의 (c)에서 56KB(=30KB+26KB)의 외부단편화 발생.
- 이 공간은 두 개의 조각으로 나뉘어져 작업 5의 메모리 요구를 만족시킬 수 없음.

통합.
하나의 작업이 끝났을 때 기억 장소가 비어 있는 다른 기억 장소(공백)와 인접되어 있는지를 점검, 하나의 공백으로 합하는 과정.
통합 과정을 수행하더라도 메모리 전반에 흩어져 있는 비어있는 공간을 모두 사용가능공간으로 통합하기 어려움.

압축(Compaction).
메모리 내용들을 적절히 움직여 모든 사용가능메모리를 하나의 큰 블록으로 만듬.
[그림 7-26] 압축 과정.
- [그림 7-20(e)]의 메모리 맵 중 10KB, 30KB, 26KB의 사용가능공간을 66KB의  하나의 공간으로 통합 확장.

압축은 항상 가능하지 않음.
- [그림 7-26]에서 작업 3과 작업 4를 이동함.
- 이동한 작업 프로세스들이 새로운 위치에서 수행되기 위해 모든 내부  주소들이 재배치되어야 함.
- 재배치가 정적이면서 어셈블리나 적재할 때 실행될 경우 불가능함.
※ 압축은 재배치가 동적인 경우만 가능하며 수행시간에 이루어짐.

주소의 동적 재배치 후 프로세스들이 이동함.
- 새로운 기준 주소 반영을 위해 기준 레지스터의 변화가 필요함.
메모리 테이블을 관리하고 유지해야 함.
- 과부하를 발생, 작은 단위의 조각이 많을 경우 더 심함.

압축 방법에 따라 비용이 많이 듬.
- [그림 7-27]에서 작업 3과 작업 4를 위해 총 600KB를 이동, 또는 작업 3을 작업 4 밑으로 이동해 200KB를 이동시킬 수 있음.
- (d)에서 사용 가능한 하나의 큰 메모리 공간이 가운데에 있으며, 큐가 450kB를 요구하는 한 프로세스 만을 가진 경우, 작업 2를 다른 위치로 이동시켜 요구 만족시킴.

장점.
- 가변 메모리에서 발생하는 수 많은 작은 공간을 하나의 큰 공백으로 변환, 새로운 작업에 할당 가능.
단점.
- 압축할 동안 시스템은 모든 일을 멈추어야 함.
- 메모리에 있는 작업들을 이동시켜야 하므로 프로그램 적재 시 제거되는 재배치 관련 정보를 액세스 가능한  형태로 보관해야 함.
- 압축 작업이 자주 요구되어 시스템 자원 소모가 큼.

버디 시스템(Buddy System)
자원 할당 과정에서 발생하는 단편화 문제를 해결하기 위해 제안됨.
큰 버퍼들을 반복적으로 이등분하여 작은 버퍼 생성.
가능할 때마다 인접한 자유로운 버퍼들(Free Buffers)을 합치는 과정을 반복.
버퍼가 나뉘어질 때, 각각을 서로의 버디(Buddy)라 부름.
사용할 수 있는 메모리 블록(K)은 ‘L ≤ K ≤ U’로 나타냄.
- L : 할당 가능한 가장 작은 블록.
- U : 가장 큰 블록으로 전체 메모리를 말함.
요청된 메모리의 크기가 작아 전체를 할당하지 않을 경우, 블록은 2U-1의 크기를 갖는 2개의 버디로 나뉘어 짐.
이 과정을 반복하여 요청된 크기와 같거나 큰 블록 생성, 요청이 할당될 때까지 계속됨.
한 커널은 크기가 b인 빈 버디 블록 쌍을 크기가 2b인 더 큰 블록 하나로 합침.

※ 버디 시스템은 고정 분할이나 동적 분할의 단점을 해결하는 적절한 방법으로, 유닉스의 커널 메모리 할당 또는 병렬 처리 시스템에서 활용됨.
※ 최근 운영체제는 페이징이나 세그먼테이션을 활용한 가상 메모리 기법을 선호함.

[그림 7-28] 크기가 64KB의 초기 블록을 사용한 예.
8KB, 8KB, 4KB의 크기로 세 작업이 요청된다 가정함.