단일 프로그래밍 환경에서 연속 할당
초기 컴퓨터 시스템은 사용자 한명만 컴퓨터를 사용할 수 있었고 컴퓨터 자원도 사용자 혼자만 마음대로 쓸 수 있었다. 그리고 프로그램은 메모리보다 클 수 없고 직접 배치 과정을 수행하여 항상 같은 메모리 위치에 적재되었다.
단일 프로그래밍 환경에서 연속 메모리 할당은 메모리를 사용자 영역과 OS 상주 영역으로 나눈다. OS 는 상위나 하위에 자유롭게 둘 수 있다.
- OS 가 상주한 영역인 모니터, 사용자 프로그램이 들어 있는 영역인 사용자, 사용하지 않는 영역인 미사용으로 나눌 수 있다.
- 메모리를 제어하는 모든 권한이 사용자에게 있기 때문에 사용자가 주소를 잘못 지정하면 OS가 손상될 수 있다.
- 그래서 (b) 와 같이 프로세서에 경계 레지스터를 두어 이를 방지한다.
- 사용자 프로그램이 메모리 주소를 참조할 때마나 경계 레지스터를 검사한 후 실행되도록 하는 것이다.
이런 메모리 할당 시스템의 문제는 사용자 프로그램의 적재이다. 컴퓨터 주소 공간이 0000부터 시작하더라도 사용자 프로그램의 시작 주소는 기준 레지스터 값 이후가 된다. 그러므로 기준 주소가 변하면 다시 적재해야 한다.
그래서 다음 두 가지 방법을 고려하여 이런 OS의 동적 변화에 대비할 수 있다.
- 사용자 프로그램을 기준 레지스터보다 상위 메모리에 적재하는 것이다. 이 방법은 사용하지 않은 모든 공간이 중간에 있어 OS나 사용자 프로그램의 공간을 확장할 수 있다는 장점이 있다.
- 주소 바인딩을 연기하는 것이다. 아래 그림과 같이 동적 적재를 하는, 즉 주소 바인딩을 연기하는 기준 레지스터가 필요하다.
- 기준 레지스터에 있는 값은 사용자 프로세스를 메모리로 보낼 때 생성하는 주소 값에 더해진다.
- 예를 들어, 기준 값이 1400이라면 주소 0에서 사용자 프로세스는 동적으로 1400으로 대체되고, 주소 346의 접근은 1746으로 대체된다.
기준 레지스터와 경계 레지스터
기준 레지스터는 가장 작은 물리적 주소를 저장하고, 경계 레지스터는 프로그램 영역이 저장되어 있는 크기를 저장한다. 즉, 기준 레지스터는 물리적 주소이고, 경계 레지스터는 논리적 주소이다.
단일 프로그래밍 환경에서 연속 메모리 할당은 단순하고 이해하기 쉬우나, 한 번에 프로그램 하나만 사용할 수 있고 메모리의 효율성이 떨어진다. 또 메모리보다 큰 프로그램은 수행할 수 없어 스와핑을 사용하여 제한된 메모리를 확장한다.
아래 그림과 같이 프로세서 중심의 작업이라면 프로세서를 집중적으로 사용할 수 있지만, 입출력 작업이 교대로 발생한다면 프로세서의 유휴 상태가 자주 일어난다. 그래서 자원 낭비가 심하고 프로세스 스와핑 비용이 많이 든다.
다중 프로그래밍 환경에서 연속 메모리 할당
다중 프로그래밍 환경에서 연속 메모리 할당을 지원하는 방법은 두 가지로 구분한다.
- 고정 분할 방법 : 메모리를 여러 개의 고정된 크기로 분할
- 가변 분할 방법 : 필요한 만큼만 메모리를 할당
고정 분할 방법
- 연속 메모리 할당에서는 메모리를 여러 개의 고정된 크기로 분할하고 분할된 각 메모리는 프로세스, 즉 작업(task) 하나를 실행할 수 있다.
- 이때 물리적 주소는 분할 기준 레지스터(PBR) 값에 논리적 주소를 더해서 생성한다.
내부 단편화의 개념
고정 분할 방법에서는 논리적 주소가 분할된 메모리보다 크면 오류가 발생하고, 작으면 내부 단편화가 발생한다.
사용 가능 공간이 18,464바이트이고 프로세스가 그중 18,462바이트를 요구한다고 가정하자.
요구된 블록을 정확히 할당하면 사용 가능 공간은 2바이트가 남는데, 이 공간을 활용하려고 처리하는 비용이 더 클것이다.
따라서 대부분 사용할 수 없는 공간이 되는데, 이를 보통 내부 단편화하고 한다.
스케줄링과 분할 크기에 따른 내부 단편화의 변화
(a) 와 같이 32KB 메모리를 10KB 운영체제 한 개, 10KB 사용자 공간 한 개, 4KB 사용자 공간 3개로 각각 나눈다고 하자.
- 대기 큐에 <7KB, 3KB, 6KB, 6KB> 작업이 있다면,
- 7KB 작업은 10KB 영역에( 3KB 내부 단편화 ),
- 3KB 작업은 4KB 영역 중 하나에 할당할 수 있으나( 1KB 내부 단편화 )
- 6KB 작업은 메모리를 할당할 수 없다.
- 반면 메모리를 (b) 와 같이 10KB, 8KB, 4KB 로 나누면,
- 7KB 작업은 8KB 영역에 (1KB 내부 단편화),
- 3KB 작업은 4KB 영역에 (1KB 내부 단편화),
- 6KB 작업은 10KB 영역에 (4KB 내부 단편화) 할당할 수 있다.
- 따라서 총 6KB 내부 단편화가 발생한다. (7KB 작업을 10KB 영역에 할당해도 된다.)
이처럼 내부 단편화는 스케줄링과 분할 크기에 따라 달라지며 메모리 낭비가 발생한다.
그리고 여러 프로세스가 메모리에 상주하므로 이 프로세스를 보호할 수 있는 메모리 보호 방법이 필요한데, 이는 기준 레지스터와 경계 레지스터를 사용하여 가능하다.
고정 분할 방법에서 메모리 보호 예
- (a) 에서 작업 2는 물리적 주소의 하한 값이 300040이고 크기가 120900이다.
- 따라서 기준 레지스터에는 가장 작은 물리적 주소인 300040을, 경계 레지스터에는 120900을 저장한다.
- 사용자 주소 범위는 0에서 120900으로 논리적 주소인 경계 레지스터보다 작아야 한다.
- 그리고 상한 값은 420940 ( = 기준 레지스터 + 경계 레지스터 = 300040 + 120900 ) 이 되므로, 사용자 주소는 하한 값과 상한 값 사이가 된다.
프로세서로 생성한 모든 주소가 이들 레지스터와 함께 (b) 과정을 거치면 다른 사용자의 프로그램과 데이터에서 보호할 수 있다.
각 영역별로 독립된 큐가 있는 고정 분할 시스템
고정 분할 방법에서는 프로그래밍의 성능이 분할 수에 제한을 받는다. 분할 영역이 비면 프로세서가 프로세스 큐에서 하나를 선택하여 비어 있는 분할 영역에 적재하고, 이 프로세스가 실행을 마치면 해당 분할 영역은 다른 프로세스가 사용할 수 있다.
- 크기가 2KB 인 큐 Q2, 6KB인 큐 Q6, 12KB인 큐 Q12가 있다고 하자.
- 크기가 2KB 미만인 프로세스는 Q2로, 크기가 6KB 미만인 프로세스는 Q6으로, 12KB 미만인 프로세스는 Q12 로 보내고 큐에는 최대 메모리 요구량을 표시한다.
- 큐별로 자신의 메모리 영역이 있으므로 큐 간에는 경쟁이 없다고 가정한다.
이 방법에서는 크기에 따라 담당하는 큐가 있어 큐 Q2가 차면 다른 큐 Q6과 Q12가 비어있어도 사용할 수 없다는 문제가 발생한다.
이 문제는 모든 작업을 하나의 통합된 대기 큐에 넣고 운영하는 방법으로 해결할 수 있다.
2KB, 6KB, 12KB로 분할된 메모리 영역과 선입선처리 작업 스케줄러, 대기 큐가 있다고 가정하자.
- 작업이 <5KB, 2KB, 3KB, 7KB> 로 도착했다.
- 우선 5KB 작업 1을 6KB영역에, 2KB 작업 2를 2KB영역에 할당한다.
- 다음 3KB 작업 3은 비어 있는 12KB 분할된 메모리 영역에 할당할 것이다.
- 이어서 7KB 작업 4는 작업 1과 작업 2를 종료했어도 분할 영역이 작아 기다리다가 작업 3이 끝난 후에야 12KB 영역에 할당할 것이다.
이처럼 통합 큐에서도 작업 5와 작업 6이 사용할 수 있는 2KB 영역과 6KB 영역이 비어 있더라도 7KB 작업 4 때문에 기다려야 한다는 문제가 발생한다. 이런 작업에서 메모리 할당(배치)을 하는 방법은 나중에 자세히 다룰 것이다.
다중 프로그래밍의 성능을 향상시키려면 메모리 분할, 작업 큐와 관련된 다음 사항을 결정해야 한다.
분할 영역의 크기
- 시스템 부하를 분석하여 분할 영역의 개수와 크기를 결정해야 한다. 이때 개수는 다중 프로그래밍의 정도가 될 수 있다.
- 예를 들어, 전체 용량이 32KB 이고 상주 모니터의 크기가 10KB라면 매우 작은 작업은 4K, 평균 작업은 6KB, 큰 작업은 12KB 로 영역을 배치할 수 있다.
- 이런 영역의 크기 결정은 시스템 전체의 효율을 나타낸다.
영역의 배치
- 프로그램 작업을 어느 영역에 배치하는지 결정해야 하는데, 작업 스케줄러가 필요하다.
가변 분할 방법
- 고정된 경계를 없애고 각 프로세스가 필요한 만큼 메모리를 할당하는 것을 가변 분할 방법이라고 한다.
- 가변 분할 방법에서는 기준 레지스터와 경계 레지스터를 사용하여 각 프로세스(분할 영역) 를 나타낸다.
예를 들어 분할 테이블에 있는 P3은 기준 레지스터(5034)와 경계 레지스터(250)에 매핑되어 물리적 주소를 생성한다.
이때 프로세서로 생성한 논리적 주소가 경계 레지스터 값보다 크면 오류가 발생한다.
가변 분할 방법 예
가변 분할 방법에서는 OS 가 메모리의 어느 부분을 사용하고 사용할 수 있는지 알 수 있는 테이블을 유지해야 한다.
- 메모리 256KB이고 운영체제가 40KB이며 작업큐에 (a) 와 같은 작업이 있다고 하자.
- 작업 1~작업 3 에 메모리를 할당하면 (b) 의 ① 과 같다.
- 5시간 후에 작업 2를 종료하여 사용한 메모리를 해제하면 ② 가 되고,
- 여기에 작업 4를 할당하면 ③ 이 된다.
- 그리고 작업 1을 10시간 후에 종료하여 메모리를 해제하면 ④가 되고,
- 작업 5에 메모리를 할당하면 ⑤ 가 된다.
위 예시로 사용 가능 공간이 메모리에 흩어져 있고 작업 큐에 대기 중인 프로세스를 실행하려면 프로세스에 충분한 크기의 메모리 영역을 찾아야 한다는 사실을 알 수 있다.
- 이때 인접한 공간 블록이 있다면, 블록 2개를 합쳐서 커다란 사용 가능 공간을 만들 수 있다.
- 물론 사용 가능 공간이 크다면 영역 2개로 나눠 공간 하나는 곧 도착하는 작업에 할당하고, 다른 공간은 다시 종료된 작업의 공간에 반환하여 또 다른 큰 공간을 만들수 있다.
이처럼 가변 분할(동적 메모리 할당)에는 요구된 크기 n을 사용 가능 공간에 어떻게 할당하느냐는 문제가 있다.
사용 가능 공간을 어느 작업에 할당하는 것이 가장 좋은지 결정하는 일반적인 메모리 배치 방법으로 최조 적합, 최적 적합, 최악 적합 등을 들 수 있다.
최초 적합(first-fit) 방법
- 프로세스를 사용 가능 공간 중 충분히 큰 첫 번째 공간에 할당한다.
- 검색을 사용 가능 공간의 리스트 맨 앞이나 이전의 최초 적합 검색이 끝났던 곳에서 시작하면 충분히 큰 사용 공간을 빨리 찾을 수 있다.
- 하지만 이 방법은 공간 활용률이 떨어질 수 있다는 단점이 있다.
최적 적합(best-fit) 방법
- 프로세스를 충분히 큰 사용 가능 공간 중에서 들어갈 수 있는 가장 작은 공간에 할당한다.
- 사용 가능 공간이 크기 순으로 정렬되어 있지 않으면 전체를 검색해야 한다.
- 따라서 사용 가능 공간을 계속 정렬하는 과정이 필요하므로 비효율적일 수 있다.
- 사용 가능 공간 이용률은 향상될 수 있으나 할당 과정에 많은 시간이 소요될 수 잇다.
- 물론 가장 작은 또 다른 사용 가능 공간을 만들 수도 있다.
최악 적합(worst-fit) 방법
- 프로세스를 가장 큰 사용 가능 공간에 할당한다.
- 공간이 크기 순으로 정렬되어 있지 않으면 전체를 검색해야 한다.
- 가장 큰 사용 가능 공간에 할당하기 때문에 가장 작은 또 다른 사용 가능 공간을 만드는 최적 적합보다 메모리 활용 면에서 더 유용하다.
위 그림들을 통해 최초 적합과 최적 적합 모두 최악 적합보다는 시간과 메모리 이용률을 감소시키기에 더 낫다는 것을 확인했다. 보통은 최초 적합이 최적 적합보다 메모리를 빨리 할당한다.
가변 분할에서 메모리를 보호하는 과정
가변 분할 방법도 고정 분할 방법처럼 상한 값과 하한 값이 있는 경계 레지스터 2개(기준 레지스터, 경계 레지스터)를 사용하여 메모리에 상주하는 프로세스들을 보호한다.
- 예를 들어, 물리적 주소의 하한 값이 100040이고 크기가 74600인 프로세사라면 상한 값은 174640 ( = 100040 + 74600 ) 이 되고, 사용자 주소 범위는 하한 값과 상한 값 사이가 된다.
기준 레지스터와 경계 레지스터는 수행 시간에 동적 대치(교체)를 허용한다.
- 기준 레지스터는 가장 작은 물리적 주소로 100040을 가지고 경계 레지스터가 논리적 주소 74600을 포함한다면, 사용자 주소 범위는 0~74600이다.
- 논리적 주소는 경계 레지스터보다 작아야 하며, 기준 레지스터에 추가하여 동적으로 대체된다.
- 따라서 100040~174639 범위에서 동적으로 대체하고, 대체한 주소는 메모리로 보낸다.
프로세서 스케줄러가 프로세스를 선택할 때 디스패터는 값이 정확한 기준 레지스터와 경계 레지스터를 적재한다. 프로세서가 생성한 모든 주소는 레지스터와 함께 검사하기 때문에 다른 사용자의 프로그램과 데이터를 보호할 수 있다.
외부 단편화 개념
가변 분할에서는 외부 단편화 문제가 발생한다.
- 프로세스들을 메모리에서 제거하고 새로운 프로세스를 적재할 때 사용 가능 공간을 작게 나눈다.
- 이것은 프로세스들이 연속된 메모리를 차지하는 과정에서 공백이 발생하기에 사용 가능 공간을 여러 개의 작은 공간으로 단편화할 수 있는 것이다.
이처럼 가변 분할에서는 프로세스가 요구한 크기로 공간을 만드므로 내부 단편화는 거의 없느나 외부 단편화는 있을 수 있다.
예시
- (b) 의 ① 에서는 26KB 외부 단편화가 발생했다. 이 공간은 너무 작아서 나머지 프로세스 작업 4와 작업 5를 만족시킬 수 없다.
- 마찬가지로 ③ 은 사용 가능 공간이 56KB ( = 30KB + 26KB ) 있으나 이 공간은 조각 2개로 나눠 있어 작업 5의 메모리 요구를 만족시킬 수 없다.
따라서 단편화 문제는 매우 심각할 수 있다. 물론 최조 적합, 최적 적합의 선택은 외부 단편화의 전체 양에 영향을 줄 수 있으나 해결책은 아니다.
이런 낭비를 해결하는 방안으로 메모리 통합(병합) 과 압축 방법을 생각할 수 있다.
외부 단편화 문제 해결 방안
메모리 통합 (coalescing) 방법
- 하나의 작업이 끝났을 때 다른 빈 공간과 인접해 있는지 점검하여 하나로 합치는 것이다.
- 그러나 메모리 전반에 흩어진 빈 공간을 모두 통합하기는 어렵다.
메모리 압축 (compaction) 방법
메모리의 내용을 적절히 움직여 사용 가능 공간을 큰 블록 하나로 만드는 것이다.
- 예를 들어 아래 그림처럼 외부 단편화된 빈 공간들을 하나의 공간인 66KB로 압축할 수 있다.
그러나 압축이 항상 가능한 것은 아니다.
- 여기서 작업 4와 작업 3을 이동했는데, 모든 내부 주소를 대체해야 이 프로세스들을 새로운 위치에서 수행할 수 있다.
- 주소 대체가 정적이고 컴파일이나 적재할 때 실행된다면 압축할 수 없다.
- 주소들을 동적으로 대체하면 프로세스들이 이동하고 기준 레지스터의 변화를 요구하여 새로운 기준 주소를 반영하므로 압축은 대체가 동적일 때만 가능하다.
- 또 실행 시간에 할 수 있다는 특징이 있다.
메모리 테이블을 유지해야 메모리 압축을 할 수 있으므로 오버헤드가 발생한다. 특히 작은 조각이 많을 때는 더 심하다.
- 그러므로 10,240 바이트의 빈 공간에 10,238 바이트의 작업을 배치할 때는 2 바이트의 조각을 관리하기보다는 10,240 바이트를 전부 배정하는 것이 낫다.
- 메모리 압축 비용이 더 많이 들기 때문이다.
다양한 메모리 압축 방법
- (a) 에서는 작업 3과 작업 4를 위해 (b)와 같이 총 600KB를 이동하거나 (d) 와 같이 작업 3을 작업 4 밑으로 옮겨 200KB 만 이동할 수도 있다. 특히 (d) 는 사용 가능한 큰 메모리 공간이 가운데 있다는 점이 특이하다.
- 또 큐가 450KB 를 요구하는 프로세스 하나만 가지고 있다면, 작업 2를 다른 위치로 이동할 수도 있을 것이다.
- 이런 해결책이 하나의 큰 공간을 생성하지는 않지만 다음 요구를 만족할 만큼 충분히 큰 공간을 만들어 낸다.
이렇게 다양한 방법으로 압축이 가능한데, 방법에 따라 비용에 차이가 있다. 하지만 최적의 압축 방법을 선택하는 것은 매우 어려운 일이다.
메모리 압축 방법의 단점
메모리 압축은 가변 메모리에서 발생하는 수많은 작은 공백을 하나의 큰 공백으로 변환하여 새로운 작업에 할당할 수 있다는 장점이 있지만, 다음과 같은 단점도 있다.
- 압축하는 동안 시스템은 모든 일을 중지해야 한다. 이때 대화형 사용자는 응답시간이 일정하지 않게 되고, 실시간 시스템은 심각한 문제가 될 수 있다.
- 메모리에 있는 작업들을 이동해야 하므로 프로그램을 적재할 때 제거되는 대치 관련 정보를 액세스 가능한 형태로 보관해야 한다.
- 압축 작업을 자주 요구하여 시스템 자원의 소모가 크다.
다중 프로그래밍 환경의 버디 시스템
고정 분할 방법이나 동적 분할 방법 모두 단편화 문제가 있었다.
- 이런 단편화 현상을 해결하는 방법으로 버디 시스템(buddy system) 을 제안했다.
- 버디 시스템은 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들며, 가능할 때마다 인접한 빈 버퍼(free buffer) 들을 합치는 과정을 반복한다.
- 버퍼를 나눌 때 각각을 서로의 버디라고 한다.
- 버디 시스템에서 사용할 수 있는 메모리 블록(K) 은 L <= K <= U 로 나타낼 수 있다.
- 여기서 L은 할당 가능한 가장 작은 블록이고, U는 가장 큰 블록으로 전체 메모리이다.
- 요청한 메모리의 크기가 작아 전체를 할당하지 않으면 블록은 2^U-1의 크기를 갖는 버디 2개로 나뉜다.
이런 과정을 반복하면 요청한 크기와 같거나 큰 블록을 생성하며, 요청을 할당할 때까지 계속 한다. 또 한 커널은 크기가 b 인 빈 버디 블록 쌍을 크기가 2b인 더 큰 블록 하나로 합한다.
64KB 의 초기 블록을 사용한 예이다.
- 먼저 첫 번째로 8KB를 요청하면 (a) 와 같이 블록을 32KB 버디 2개로 쪼개고,
- 여전히 요청한 크기보다 크므로 계속 또개 크기가 8KB가 되면 요청에 맞게 할당할 수 있다.(①~③)
- 이어서 두 번째도 8KB를 요청한다면 (b)와 같이 바로 할당할 수 있다. (④)
- 세 번째로 4KB를 요청한다면 (c) 와 같이 다시 블록을 버디 2개로 쪼개고 요청에 할당한다.(⑤~⑥)
- 다음 (d) 와 같이 두 번째로 요청한 8KB를 해제하고(⑦)
- (e) 와 같이 첫 번째 요청한 8KB를 해제하면서 합친다.(⑧)
버디 시스템으로 고정 분할 방법이나 가변 분할 방법의 단점을 해결할 수 있다.
하지만 최근 OS는 페이징이나 세그먼테이션을 활용한 가상 메모리를 선호하고, 버디 시스템은 유직스의 커널 메모리 할당이나 병렬 처리 시스템에서만 응용한다.
참고
- 운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미