01. 메모리 관리의 개요

1. 메모리 관리

(1) 메모리 관리의 복잡성

메모리는 메인 메모리를 가리킨다. 메모리의 구조는 1바이트의 크기로 나뉜다. 1바이트로 나뉜 각 영역은 메모리 주소로 구분하는데 일반적으로 0번지부터 시작한다. CPU는 메모리에 있는 내용을 가져오거나 작업 결과를 메모리에 저장하기 위해 메모리 주소 레지스터(MAR)를 사용한다. 메모리 주소 레지스터에 필요한 메모리 주소를 넣으면 데이터를 메모리에서 가져오거나 메모리에 데이터를 옮길 수 있다.
폰 노이만 구조의 컴퓨터에서 메모리는 유일한 작업 공간이며 모든 프로그램은 메모리에 올라와야 실행이 가능하다. 과거의 일괄 처리 시스템에서는 한 번에 한 가지 작업만 처리했기 때문에 메모리 관리가 어렵지 않았지만 오늘날의 시분할 시스템에서는 운영체제를 포함한 모든 응용 프로그램이 메모리에 올라와 실행되기 때문에 메모리 관리가 복잡하다. 운영체제도 프로그램이라서 메모리에 올라와야 실행할 수 있으므로 메모리에는 사용자 프로세스뿐 아니라 운영체제 프로세스도 공존하다.

(2) 메모리 관리의 이중성
메모리 관리의 이중성은 프로세스 입장에서 작업의 편리합과 관리자 입장에서 관리한 편리함이 충돌을 일으키는 것을 말한다. 현대의 메모리 관리 시스템은 프로세스와 메모리 관리자의 상충되는 요구 사항을 완벽하게 처리한다. 물론 이러한 요구 사항을 만족시키기 위해 메모리 관리자의 작업은 더욱 복잡해졌다.

(3) 소스 코드의 번역과 실행
컴파일러와 인터프리터의 동작
컴퓨터에서 작동하는 응용 프로그램은 프로그래밍 언어로 만들며, 보통 컴파일러를 사용하여 작성한 프로그램을 실행 가능한 코드로 변경한다. 물론 프로그램을 만들 때 처음부터 컴퓨터에서 바로 실행 가능한 코드로 만들 수 있다. 즉, 0과 1의 기계어로 만드는 것이지만 기계어는 배우기 어렵고 이해하기도 힘들다.
언어 번역 프로그램은 고급 언어로 작성한 소스 코드를 컴퓨터가 실행할 수 있는 기계어로 번역하는 프로그램이다.
컴파일러
소스 코드를 컴퓨터가 실행할 수 있는 기계어로 번역한 후 한꺼번에 실행한다. C언어, 자바 등이 이러한 방식으로 프로그램을 실행한다.
컴파일러를 사용하는 프로그래밍 언어는 사용할 변수를 먼저 선언한 후 코드를 작성한다. 변수 선언은 오류를 찾고 코드를 최적화하기 위해 반드시 필요한 작업이므로 반드시 변수는 미리 선언되어야 한다.
컴파일러는 실행 전에 소스 코드를 점검하여 오류를 수정하고 필요 없는 부분은 정리해서 최적화된 실행 파일을 만든다.
인터프리터
소스 코드를 한 행씩 번역하여 실행한다. 자바스크립트, 베이직 등이 이 방식으로 프로그램을 실행한다.
인터프리터는 한 줄씩 위에서부터 아랫방향으로 실행되기 때문에 같은 일을 반복하는경우나 필요 없는 변수를 확인할 수 없다. 따라서 크고 복잡한 프로그램에서는 컴파일러를 사용하고 간단한 프로그램에서는 인터프리터를 사용한다.

컴파일러의 목적
오류 발견
컴파일러의 첫 번째 목적은 소스 코드에서 오류를 발견하여 실행 시 문제가 없도록 하는 것이다. 컴파일러는 오류를 찾기 위해 심벌 테이블을 사용한다. 심벌 테이블은 변수 선언부에 명시한 각 변수의 이름과 종류를 모아 놓는 테이블로, 선언하지 않은 변수를 사용하지는 않았는지, 변수에 다른 종류의 데이터를 저장하지는 않았는지를 알 수 있다.
코드의 최적화
코드의 최적화는 불필요한 코드와 사용하지 않는 변수를 삭제해서 코드를 간결하게 하고, 실행 속도를 빠르게 하는 것이다. 결과적으로 컴파일러는 실행하기 전에 코드를 점검하여 오류를 수정하고 최적함으로써 크기가 작고 실행이 빠른 파일을 만든다.
컴파일 과정
컴파일은 사용자가 작성한 소스 코드를 목적 코드(object code)로 변환한 후 라이브러리를 연결하고 최종 실행 파일을 만들어 실행하는 과정이다.

소스 코드 작성과 컴파일
프로그래머가 C언어나 자바로 소스 코드를 작성하여 컴파일하면 목적 코드가 만들어진다. 컴퓨터는 0과1의 기계어만 인식할 수 있기 때문에 사용자가 작성한 소스 코드를 컴파일러로 일차로 번역하는데 이렇게 얻은 코드가 목적 코드이다.
컴파일 시간은 프로세스가 메모리에 적재될 위치를 컴파일 과정에서 알 수 있다면 컴파일러는 물리적 주소를 생성할 수 있다. 예를 들면, 사용자 프로세스가 임의의 위치로 시작해서 적재한다고 알려주면 생성된 컴파일러 코드는 그 위치에서 시작하여 확장해 나갈 것이다. 이후 시작 위치가 변하지 않으면 다시 컴파일할 필요가 없다.

목적 코드와 라이브러리 연결
목적 코드가 만들어지면 라이브러리에 있는 코드를 목적 코드에 삽입하여 최종 실행 파일을 만든다. 라이브러리는 자주 사용하는 함수를 시스템 내에 미리 만들어둔 것으로, 프로그래머가 직접 만들기 어렵거나 또는 만드는 데 시간이 많이 걸리는 함수를 파일 형태로 모아 놓은 것이다. 컴파일러는 라이브러리의 연결 단계에서 printf()문에 해당하는 기계어 코드를 <stdio.h> 라이브러리에서 가져와 목적 코드에 삽입한다. <stdio.h> 라이브러리는 입/출력 변수를 미리 만들어놓은 것으로, 사용자가 printf() 함수를 따로 정의하지 않고 소스 코드 맨 앞에 #include<stdio.h>라고 명시하면 자동으로 라이브러리가 연결된다.
적재 시간은 프로세스를 메모리의 어디에 적재해야 할지 컴파일 과정에 알려주지 않으면 컴파일러는 대체 가능한 상대 주소를 생성한다. 상대 주소는 프로그램의 시작 주소가 0으로 생성되므로 최종 연결을 적재 시간까지 연기한다. 시작 주소가 변하면 단지 변화된 값을 반영하려고 사용자 코드를 재적해한다. 이런 과정을 정적 대치라고 한다.
동적 라이브러리를 포함하여 최종 실행
동적(연결) 라이브러리(dll : dynamic linking library)는 프로그래머가 정의한 함수를 실행 파일과 분리해서 dll 파일 안에 넣어둘 수가 있다. 프로그램이 처음 로딩될 때 메모리에서 적재할 코드와 실행 시에 그때그때 필요한 코드를 구분해서 메모리를 효율적으로 사용할 수 있다. 또한 동시에 실행되는 여러 프로그램에서 같은 함수를 사용할 경우 각 프로그램에서 동일한 dll을 참조하면 되므로 같은 함수를 여러 번 로딩하는 비효율성을 없앨 수 있다. 즉, 로더(loader)는 재배치가 가능한 기계어 프로그램을 입력하여 절대 주소를 갖는 동등한 프로그램을 생성하는 연결 적재를 하고, 링크 전체가 실행 시점에 사용하는 동적 로드도 한다.
실행 시간은 한 프로그램(프로세스)이 동일한 장소에서 작동한다면 적재 시간 과정에서 연결할 수 있으나 프로세스를 실행하는 도중에 메모리의 한 세그먼트에서 다른 세그먼트로 이동한다면 연결은 수행 시간까지 연기(지연)된다. 이번 주소 체계는 기본 및 경계(한계) 레지스터 등 특수한 하드웨어의 지원이 필요하다. 현재 범용 운영체제 대부분은 실행 시간에 연결하는 이 방법을 사용한다.

컴파일러가 원시 코드를 컴파일하여 목적 파일을 생성하면 링터(연결기)가 이 목적 파일에 라이브러리 파일이나 다른 목적 파일을 결합한다. 그런 다음 로더(적재기)가 지정 위치에서 시작하여 메모리에 프로그램을 배치하는데, 하드웨어 구조에 따라 다음과 같은 방법으로 실행한다.
절대 적재 : 프로그램을 메모리의 지정 위치에 적재한다.
교체 적재 : 프로그램을 메모리의 여러 위치에 적재한다.

(4) 메모리 관리자의 역할
모든 프로그램은 우선 메모리에 적재되어야 실행이 가능하므로 메모리는 프로그램을 실행하는 중요한 작업 공간이다. 그리고 다중 프로그래밍 환경에서는 한정된 메모리를 여러 프로세스가 함께 사용하므로 이를 효율적으로 관리하는 방법이 필요하다.
메모리 관리는 프로세스들을 위해 메모리를 할당하고 제거하며 보호하는 활동이다. 더 단순하게는 프로세스의 요청에 따라 메모리의 일부를 할당하고, 필요가 없으면 자유로이 재사용할 수 있도록 하는 것이다. 또 디스크에 있는 프로그램을 실행하려면 먼저 메모리에 적재한 후 메모리 관리자가 예약된 메모리를 할당해 주어야 하는데, 이것도 메모리 관리에 해당한다. 다중 프로그래밍 시스템에서는 여러 프로세스가 메모리에 상주할 수 있도록 운영체제가 동적으로 메모리를 세분화하는데 이 과정도 메모리 관리에 해당한다.
메모리 관리는 메모리 관리자가 담당한다. 메모리 관리자는 메모리 관리 유닛(Memory Manage Unit)이라는 하드웨어로 일반적으로 메모리 관리자라고 말한다. 메모리 관리자의 작업은 가져오기(fetch), 배치(placement), 재배치(replacement)

적재 정책(fetch policy)
적재 작업
프로세스와 데이터를 메모리로 가져오는 작업이다. 메모리 관리자는 사용자가 요청하면 프로세스와 데이터를 모두 메모리로 가져온다. 그런데 어떤 상황에서는 데이터의 일부만 가져와 실행하기도 한다. 예를 들면, 용량이 큰 동영상을 실행해야 하는데 메모리가 충분하지 않다면 동영상 플레이어를 먼저 가져와 실행하고, 동영상 데이터는 필요할 때마다 수시로 가져와 실행하는 것이다. 메모리 관리자는 사용자의 요청이 없더라도 앞으로 필요할 것이라고 예상되는 데이터를 미리 가져오기도 한다.
적재 정책
적재 정책은 프로세스가 필요로 하는 데이터를 언제 메모리에 가져올지 결정하는 정책이다. 프로세스가 요청할 때 메모리로 가져오는 것이 일반적인 방법이지만, 필요하다고 예상되는 데이터를 미리 가져오는 방법(prefetch)도 있다.
요구 적재(demand fetch) : 운영체제나 시스템 프로그램, 사용자 프로그램 등 참조 요청에 따라 다음에 실행할 프로세스를 메모리에 적재하는 오래된 방법이다.
예상 적재(anticipatory fetch) : 시스템의 요청을 미리 예측하여 메모리에 적재하는 방법이다. 요청된 페이지 외의 다른 페이지도 함께 불러들여 탐색 시간과 회전 지연시간을 가지는 보조기억장치(디스크)의 특성을 참조한다.

배치 정책(placement policy)
배치 작업
가져온 프로세스와 데이터를 메모리의 어떤 부분에 올려놓을지 결정하는 작업이다. 배치 작업 전에 메모리를 어떤 크기로 자를 것인지가 매우 중요하다. 같은 크기로 자르느냐, 실행되는 프로세스의 크기에 맞게 자르느냐에 따라 메모리 관리의 복잡성이 달라지기 때문이다. 이렇게 나누어진 메모리의 구역에 따라 프로세스와 데이터를 어떤 위치에 놓을지 결정하는 것이 바로 배치 작업이다.
배치 정책
배치 정책은 디스크에 반입한 프로세스를 메모리 어느 위치에 저장할 것인지 결정한다. 사용 가능 공간 리스트에서 충분히 큰 첫 번째 공백 분할 공간에 적재하는 최초 적합, 사용 가능 공간 리스트에서 가장 작은 크기의 사용 공간을 작업에 적재하는 최적 적합, 가장 큰 사용 공간에 적재하는 최악 적합 등이 있다.

재배치 정책(replacement policy)
재배치 작업
새로운 프로세스를 가져와야 하는데 메모리에 꽉 찼다면 메모리에 있는 프로세스를 하드디스크로 옮겨놓아야 새로운 프로세스를 가져오기 위해 오래된 프로세스를 내보내는 작업이다.
재배치 정책
재배치 정책(대치 정책, 교체 정책)은 메모리가 충분하지 않을 때 현재 메모리에 적재된 프로세스 중 제거할 프로세스를 결정하는 교체 방법이다. 시기 및 사용 빈도에 따라 선입선출(FIFO : First In First Out) 배치 알고리즘, 최근 최소 사용(LRU : Least Recently Used) 배치 알고리즘 등 다양한 방법이 가능하다.

(5) 메모리 적재(할당) 방법
메모리에 프로세스를 적재하는 방법은 크게 두 가지로 분류된다. 하나는 연속적으로 적재하는 연속 메모리 적재 방법이고, 다른 하나는 페이지나 세그먼트 단위로 나눠 여러 곳에 적재하는 비연속(분산) 메모리 적재 방법이다.
연속 메모리 할당
초기 컴퓨터 시스템은 각 프로그램이 연속된 하나의 블록을 차지하도록 연속 메모리 할당을 사용했다. 직접 배치, 중첩(오버레이), 고정 분할 방법이 이에 해당한다. 그런데 고정 분할 방법은 크기가 다른 프로세스에 모두 같은 크기의 메모리를 할당하여 메모리 낭비를 초래했다. 프로세스의 크기에 따라 메모리를 다르게 분할하는 가변 분할 메모리 할당을 제안하여 연속 메모리 할당의 문제를 해결하였고, 다중 프로그램 방법에 적용하면서 분산 메모리 할다잉 유용해졌다. 연속 메모리 할당에서는 고정 분할이나 가변 분할이 효과적인 메모리 활용 방법은 아니다. 또 내부 단편화나 외부 단편화 문제가 발생할 수 있다. 물론 제한된 압축을 활용하여 메모리 할당을 변화시켜서 외부 단편화를 해결하면 연속적인 공간을 만들 수 있지만, 실행 시간을 낭비하는 결과를 가져온다. 그래서 외부 단편화를 해결하고 내부 단편를 최소화하려는 새로운 방법이 바로 분산 메모리 할당이다.

불연속 메모리 할당
분산 메모리 할당은 불연속 메모리 할당이라고도 하는데, 프로그램 하나가 물리적 주소의 여러 공간에 분산해서 올라갈 수 있도록 하는 방법이다. 이 방법은 크게 고정 분할, 가변 분할로 분류할 수 있다. 먼저 고정 분할에 해당하는 페이징은 프로그램 하나를 분할하는 기준에 따라 동일한 크기로 나눠 메모리로 적재하는 방법이다. 이런 메모리 관리 기술은 계속 발전하여 가상 메모리를 지원할 수 있게 되었다.

02. 메모리 주소

메모리에 접근할 때는 주소를 사용한다. 따라서 메모리와 주소는 매우 밀접한 관계이다. 메모리 주소는 절대 주소와 상대 주소로 나뉜다.

(1) 32bit CPU와 64bit CPU의 차이
CPU의 비트는 한 번에 다룰 수 있는 데이터의 최대 크기를 의미한다. 32bit CPU는 한 번에 다룰 수 있는 데이터의 최대 크기가 32bit이고, 64bit CPU는 64bit이다. CPU 내부 부품은 모두 이 비트를 기준으로 제작된다. 32bit CPU 내의 레지스터 크기는 전부 32bit이고, 산술 논리 연산 장치도 32bit를 처리할 수 있도록 설계된다. 또한 데이터를 전송하는 각종 버스의 크기, 즉, 대역폭도 32bit이다. 32bit 대역폭의 버스를 통해 한 번에 옮겨지는 데이터의 크기는 당연히 32bit이다.
CPU의 비트는 메모리 주소 공간의 크기와도 연관이 있다. 32bit CPU의 경우 메모리 주소를 지정하는 레지스터인 메모리 주소 래지스터(MAR)의 크기가 32bit이므로 표현할 수 있는 메모리 주소 범위가 0~(2의 32승), 총 개수가 2의 32승개이다. 이를 16진수로 나타내면 000000000 ~ FFFFFFFFF이며 총 크기는 4Giga 바이트이다. 따라서 32bit CPU 컴퓨터는 메모리가 설치되며 각 메모리 주소 공간이 있다. 이렇게 설치된 메모리의 주소 공간을 물리 주소 공간(physical address space)이라고 한다. 물리 주소 공간은 하드웨어 입장에서 바라본 주소 공간을 컴퓨터마다 그 크기가 다르다. 이와 반대로 사용자 입장에서 바라본 주소 공간은 논리 주소 공간(logical address space)이라고 한다.

32bit CPU가 달린 컴퓨터에는 당연히 32bit용 운영체제를, 64bit CPU가 달린 컴퓨터에는 64bit 운영체제를 설치해야 한다.

(2) 절대 주소와 상대 주소
메모리 영역의 구분
단순 메모리 구조
단순 메모리 구조는 한 번에 한 가지 일만 처리하는 일괄 처리 시스템에서 볼 수 있다. 메모리 관리자는 이러한 메모리를 운영체제 영역과 사용자 영역으로 나누어 관리한다. 운영체제는 시스템을 관리하는 중요한 역할을 하기 때문에 사용자가 운영체제를 침범하지 못하도록 분리하여 관리한다. 운영체제가 0~359번지를 사용하고 사용자가 360~999번지를 사용한다.
상위 메모리부터 사용자 영역 할당
사용자 프로세스는 운영체제 영역을 피하여 메모리에 적재되어 (a)에서는 360부터 적재되는데, 만약 운영체제 영역을 399번지까지 사용한다면 사용자 프로세스가 400번지부터 적재되어야 한다. 그런데 이렇게 사용자 프로세스가 운영체제의 크기에 따라 매번 적재되는 주소가 달라지는 것은 번거로운 일이라 이를 개선하여 (b)와 같이 사용자 프로세스를 메모리의 최상위부터 사용하는 방법이 있다. 즉 메모리를 최상위에서 운영체제 방향으로 내려오면서 사용하는 것이다. 이 방법은 운영체제의 크기에 상관없이 사용자 영역의 시작접을 결정할 수 있으나 메모리를 거꾸로 사용하기 위해 주소를 변경하는 일이 복잡하기 때문에 쓰지 않는다.

경계 레지스터
사용자 영역이 운영체제 영역으로 침범하는 것을 막으려면 하드웨어의 도움이 필요한데 이는 CPU 내에 있는 경계 레지스터가 담당한다. 경계 레지스터는 운영체제 영역과 사용자 영역 경계 지점의 주소를 가진 레지스터이다. 메모리 관리자는 사용자가 작업을 요청할 때마다 경계 레지스터의 값을 넣어 벗어나는지 검사하고 만약 경계 레지스터를 벗어나는 작업을 요청하는 프로세스가 있으면 그 프로세스를 그 프로세스를 종료한다.

절대 주소와 상대 주소의 개념
절대 주소
사용자 프로세스가 메모리의 사용자 영역 400번지에 올라왔다고 가정하자. 컴파일 방식을 사용하는 프로그램의 경우 컴파일 시 변수의 주소를 0번지부터 배정한다. 컴파일할 당시에는 변수가 메모리의 어느 위치에 올라가는지 알 수 없기 때문에 0번지부터 배정하고 실제로 실핼할 때 주소를 조정한다. 만약 사용자 프로세스가 메모리의 400번지에 올라간다면 프로세스 내 변수의 주소에 400을 더하는데, 이때 400번지는 절대 주소(absolute address)이다. 실제 물리 주소(physical address)를 가리키는 절대 주소는 메모리 관리자 입장에서 바라본 주소이다. 즉, 메모리 주소 레지스터가 사용하는 주소로 컴퓨터에 꽂힌 램 메모리의 실제 주소를 말한다.
메모리 관리자는 절대 주소를 사용하지만 사용자 입장에서 절대 주소는 불편하고 위험하다. 절대 주소를 사용하면 운영체제 영역을 확인해야 한다. 현재 359번지까지 사용하더라도 운영체제가 업그레이드되면 그 이상의 주소 범위를 사용할 수도 있다. 또한 운영체제 영역의 주소가 사용자에게 노출되면 실수나 고의적인 조작으로 운영체제 영역을 침범할 수도 있다.
상대 주소
사용자 프로세스 입장에서 운영체제 영역은 어차피 사용할 수 없는 공간이다. 또한 운영체제의 절대 주소(물리 주소)를 알 필요도 없다. 상대 주소(relative address)는 사용자 영역이 시작되는 번지를 0번지로 변경하여 사용하는 주소 지정 방식이다. 예를 들면 그림에서는 360번지가 0번지로, 400번지가 40번지로 바뀌는데, 이때 360번지와 400번지는 절대 주소이고 0번지와 40번지는 상대 주소이다. 상대 주소는 사용자 프로세스 입장에서 운영체제가 어디서 끝나는지, 자신의 데이터가 어디에 존재하는지 알 필요 없이 주소 공간이 항상 0번지부터 시작하는데, 이러한 주소 공간을 논리 주소 공간이라고 부른다. 앞서 설명했듯이 논리 주소 공간은 물리 주소 공간의 상대적인 개념이다. 즉, 논리 주소 공간은 상대 주소를 사용하는 주소 공간이다. 물리 주소 공간은 절대 주소를 사용하는 주소 공간이다.

상대 주소를 절대 주소를 변환하는 과정
메모리 접근 시 절대 주소를 사용하면 특별한 변환 과정 없이 작업을 할 수 있다. 그러나 상대 주소를 사용하면 상대 주소를 실제 메모리 내의 물리 주소, 즉 절대 주소로 변환해야 한다. 이러한 변환 작업은 프로세스가 실행되는 동안 메모리 관리자가 매우 빠르게 처리한다. 메모리 관리자가 상대 주소를 절대 주소로 변환하는 과정은 그림과 같다.

사용자 프로세스가 상대 주소 40번지에 있는 데이터를 요청한다.
CPU는 메모리 관리자에게 40번지에 있는 내용을 가져오라고 명령한다.
메모리 관리자는 재배치 레지스터를 사용하여 상대 주소 40번지를 절대 주소 400번지로 변환하고 메모리 400번지에 저장된 데이터를 가져온다.
메모리 관리자는 사용자 프로세스가 상대 주소를 사용하여 메모리에 접근할 때마다 상대 주소 값에 재배치 래지스터 값을 더하여 절대 주소를 구한다. 재배치 레지스터는 주소 변환의 기본이 되는 주소 값을 가진 래지스터로, 메모리에 사용자 영역의 시작 주소 값이 저장된다. 그림에서는 360번지가 재배치 레지스터에 저장된다. 사용자 프로세스 입장에서는 메모리 관리자가 재배치 레지스터를 사용하여 상대 주소를 절대 주소로 변환하기 때문에 메모리가 상항 0번지부터 시작하는 연속된 작업 공간으로 보인다. 만약 운영체제 영역이 바뀌어 사용자 영역이 500번지부터 시작한다면 재배치 레지스터에 500을 넣으면 된다.

02. 단일 프로그래밍 호나경에서의 메모리 할당

1. 메모리 오버레이

과거에는 개인용 컴퓨터에 큰 메모리를 사용할 수 없었다. 한 예로 마이크로소프트 윈도우 운영체제의 전신인 MS-DOS는 기본 메모리가 640KB로 한정되었다. MS-DOS를 개발할 당시에는 640KB보다 큰 사용자 프로그램이 없을 것이라고 생각하여 한정한 것이다.
지금은 메모리의 가격이 부담스럽지 않고 용량도 넉넉하여 문제가 없지만 과거에는 작은 메모리로 큰 프로그램을 어떻게 작동할 것인가가 문제였다. 1MB 메모리의 컴퓨터에서 100MB의 프로그램을 실행시킬 수는 없을 것이다. 프로그램의 크기가 실제 메모리(물리 메모리)보다 클 때 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오는 기법을 메모리 오버레이(memory overlay)라고 한다. 'overlay'는 '겹겹이 쌓다', '중첩시킨다'라는 뜻으로, 메모리 오버레이는 하나의 메모리에 여러 프로그램을 겹겹이 쌓아놓고 실행하는 것을 말한다. 메모리 오버레이의 경우 프로그램을 몇 개의 모듈로 나누고 필요할 때마다 모뷸을 메모리에 가져와 사용한다. 전체 프로그램을 메모리에 올려놓고 실행하기에는 메모리의 크기가 작기 때문에 실행하는데 필요한 중요한 모듈만 올려놓고 나머지는 필요할 때마다 메모리에 가져와 사용하는 것이다.

(1) 메모리 오버레이의 작동 방식
일반적인 문서 편집기에는 기본 문서 편집 기능 이외에 맞춤법 검사, 출력, 그림판 등의 기능이 있다. 이러한 기능은 각각 모듈 형태로 분리되어 있다가 프로그램이 실행되면 필요한 모듈만 메모리에 올라와 실행된다. 기본 문서 편집기를 사용하다 그림판이 필요하면 메모리에 그림판을 가져오고, 맞춤법 검사기가 필요하면 그림판을 제외하고 그 자리에 맞춤법 검사기를 가져온다. 프로그램 전체를 메모리에 올려놓고 실행하는 것보다 속도가 느리지만, 메모리가 프로그램보다 작을 때도 실행할 수 있어 유용하다.
메모리 오버레이에서 어떤 모듈을 가져오거나 내보낼지는 CPU 레지스터 중 하나인 프로그램 카운터(PC)가 결정한다. PC는 앞으로 실행할 명령어의 위치를 가리키는 래지스터로, 해당 모듈이 메모리에 없으면 메모리 관리자에게 요청하여 메모리로 가져오게 한다.

(2) 메모리 오버레이의 중요한 의미
한정된 메모리에서 메모리보다 큰 프로그램의 실행이 가능하다. 이는 가상 메모리 시스템의 기본이 되는 개념으로 다음 장에서 설명한다.
프로그램 전체가 아니라 일부만 메모리에 올라와도 실행이 가능하다. 프로그램은 개념적으로 한 덩어리지만 일부분만 가지고도 실행할 수 있다. 이는 메모리를 여러 조각으로 나누어 여러 프로세스에 할당할 수 있다는 의미이기도 하다.

2. 스왑

메모리 오버레이를 이용하면 메모리보다 큰 프로그램을 실행할 수 있다. 그러나 처리해야 할 문제는 남아있다. 그림에서와 같이 메모리에 모듈 B를 가져올 때 먼저 메모리에 올라온 모듈 A를 어딘가에 보관해야 한다. 그림과 같이 모듈 A를 원래의 하드디스크 위치에 옮겨 놓으면 되겠지만 다시 사용할 지도 모르고 아직 작업이 끝나지 않았기 때문에 저장장치의 별도 공간에 보관해야 한다. 이처럼 메모리가 모자라서 쫓겨난 프로세스는 저장장치의 특별한 공간에 모아두는데 이러한 영역을 스왑 영역(swap area)이라고 부른다.
스왑 영역에서 메모리로 데이터를 가져오는 작업은 스왑-인(swap-in), 메모리에서 스왑 영역으로 데이터를 내보내는 작업은 스왑-아웃(swap out)이라고 한다.

스왑 영역은 메모리 관리자가 관리한다. 원래 하드디스크 같은 저장장치는 저장장치 관리자가 관리하지만, 스왑 영역은 메모리에서 쫓겨났다가 다시 돌아가는 데이터가 머무는 곳이기 때문에 저장장치는 장소만 빌려주고 메모리 관리자가 관리하는 것이다.
메모리 오버레이에서는 메모리보다 큰 프로그램을 실행할 대 프로그램을 메모리보다 작은 크기의 모듈로 나누어서 사용한다. 여기에 스왑을 이용하면 스왑 영역의 크기가 메모리의 크기로 인식된다. 다시 말해 사용자는 실제 메모리의 크기와 스왑 영역의 크기를 합쳐서 전체 메모리로 인식하고 사용할 수 있다. 예를 들면 실제 메모리의 크기가 1GB, 스왑의 크기가 3GB라면 사용자가 인식하는 메모리는 4GB이다. 이는 이제 메모리가 4GB인 컴퓨터보다 속도가 느리겠지만, 스왑을 사용하면 실제 메모리의 모자란 부분을 보충할 수 있다. 사용자 입장에서는 실제 메모리의 크기에 상관없이 큰 프로그램을 실행할 수 있는 것이다.

03. 다중 프로그래밍 환경에서의 메모리 할당

한 번에 여러 프로세스를 실행하는 경우 메모리 관리가 더욱 복잡해지는데, 프로세스들의 크기가 다를 때 메모리를 어떻게 나누어 사용할 것인지에 대해 알아본다.

1. 메모리 분할 방식

메모리를 어떤 크기로 나눌 것인가는 메모리 배치 정책에 해당된다. 메모리에 여러 개의 프로세스를 배치하는 방법은 가변 분할 방식(variable-size partitioning)과 고정 분할 방식(fixed-size partitioning)으로 나뉜다.
가변 분할 방식 : 프로세스의 크기에 따라 메모리를 나누는 것이다
고정 분할 방식 : 프로세스의 크기와 상관없이 메모리를 같은 크기로 나누는 것이다.

(1) 가변 분할 방식와 고정 분할 방식의 예
식당은 17개의 의자가 놓여 있는 상황이라고 가정한다. 가변 분할 방식의 경우는 어디에 앉든 상관없기 때문에 손님들이 알아서 편한 자리에 앉는다. 그러나 고정 분할 방식에서는 의자를 4개씩 파티션으로 나누고 손님들의 자리를 파티션 단위로 배정했다. 한 일행이 같은 파티션에 앉을 수 없다면 다른 파티션에 나누어 앉는다. 함께 온 손님은 의사 색깔로 구분했으며 격자무늬는 빈 의자로 나타낸다.
가변 분할 방식에서는 손님들이 앉고 싶는 자리에 앉을 수 있고, 파티션으로 구분되지 않았기 때문에 함께 온 일행이 나란히 앉을 수 있다. 그러나 식당 관리자 입장에서는 관리가 복잡하다. 그림의 (a)에서 손님 B팀의 3명이 식사를 마친 후, 새로운 손님 4명이 온 경우를 생각해 보면 4명이 나란히 앉을 수 있는 빈자리가 없기 때문에 손님 C팀이 옆으로 이동해서 4명이 나란히 앉을 수 있다. 이처럼 식사하는 도중에 자리를 옮기는 것은 매우 불편한 일이다.
이와 달리 고정 분할 방식은 관리가 용이하다. 의자를 4개씩 파티션으로 나누었기 때문에 손님들이 알아서 적당한 파티션에 앉으면 된다. 단 함께 온 일행이 분산해서 앉는 것을 감수해야 한다. 그림의 (b)에서는 A팀의 6명이 2개의 파티션에 나누어 앉았다. 고정 분할 방식은 함께 온 일행이 따로 앉는 문제를 신경 쓰지 않아도 되므로 가변 분할 방식처럼 식사 도중에 손님이 자리를 옯길 필요가 없다.

(2) 메모리 분할 방식의 구현
그림은 가변 분할 방식과 고정 분할 방식이 메모리에서 어떻게 구현되는지 보여준다.

가변 분할 방식
프로세스의 크기에 맞게 메모리가 분할되므로 메모리의 영역이 각각 다르다. 한 프로세스가 연속된 공간에 배치되기 때문에 연속 메모리 할당(contigious memory allocation)이라고 한다.
장점
가변 분할 방식에서는 프로세스를 한 덩어리로 처리하여 하나의 프로세스를 연속된 공간에 배치한다
단점
가변 분할 방식은 메모리 관리가 복잡하다. 그림의 (a)에서는 프로세스 B와 D가 작업을 마쳤다면 각각 18KB와 17KB의 빈 공간이 생긴다. 이때 19KB가 넘는 프로세스가 메모리에 올라오려고 한다면 어떻게 될까? 빈 공간이 떨어져 있기 때문에 올라올 수 없다. 19KB가 넘는 프로세스를 실행하려면 비어 있는 공간을 하나로 합쳐야 하며, 이 과정에서 프로세스 C의 자리도 옮겨야 한다. 이처럼 가변 분할 방식은 메모리 통합 등의 부가적인 작업이 필요하므로 메모리 관리가 복잡하다.

고정 분할 방식
프로세스의 크기에 상관없이 메모리가 같은 크기로 나뉘며, 큰 프로세스가 메모리에 올라오면 여러 조각으로 나뉘어 배치된다. 그림의 (b)에서는 프로세스 A가 프로세스 A1과 프로세스 A2로, 프로세스 C가 프로세스 C1과 프로세스 C2로 나눠 배치되었다. 한 프로세스가 분산되어 배치되기 때문에 비연속 메모리 할당(noncontigious memory allocation)이라고 한다.
장점
고정 분할 방식에서는 메모리를 일정한 크기로 나누어 관리하기 때문에 메모리 관리가 수월하다. 가변 분할 방식의 메모리 통합 같은 부가적인 작업을 할 필요가 없다.
단점
고정 분할 방식에서는 쓸모없는 공간으로 인해 메모리 낭비가 발생할 수 있다. 즉, 일정하게 나누어진 공간보다 작은 프로세스가 올라올 경우 메모리 낭비가 발생하다. 그림의 (b)에서는 프로세스 B는 18kB, 프로세스 D는 17kB이므로 메모리의 한 조각인 20kB에 배치하면 공간이 남는다. 이는 다른 프로세스가 사용할 수 없는 공간이라 메모리가 낭비되는 것이다. 이 남는 공간을 활용하려고 처리하는 비용이 더 클 것이고, 대부분 사용할 수 없는 공간이 되는데 이를 보통 내부 단편화라고 한다.
그림에서 32kB 메모리를 10kB, 4kB, 4kB, 4kB 사용자 공간으로 각각 나눈다고 가정하자. 작업 대기 큐에 <7kB, 3kB, 6kB, 6kB> 작업이 있다면, 7kB 작업은 10kB 영역에 3kB 내부 단편화가 발생하고, 3kB 작업은 4kB 영역 중 하나에 할당할 수 있으나 1kB 내부 단편화가 발생한다. 6kB 작업은 메모리를 할당할 수 없다.
또 다른 작업은 32kB 메모리를 10kB, 4kB, 4kB, 4kB 사용자 공간으로 각각 나눈다고 가정하자 작업 대기 큐에 <7kB, 3kB, 6kB, 6kB> 작업이 있다면, 7kB 작업은 10kB 영역에 3kB 내부 단편화가 발생하고, 3kB 작업은 4kB 영역 중 하나에 할당할 수 있으나 1kB 내부 단편화가 발행한다. 6kB 작업은 메모리를 할당할 수 없다.
또 다른 작업은 32kB 메모리를 10kB, 8kB, 4kB 사용자 공간으로 나눈다면, 7kB 작업은 10kB 영역에 3kB 내부 단편화가 발생하고, 3kB 작업은 4kB 영역에 1kB 내부 단편화, 6kB 작업은 8kB 영역에 2kB 내부 단편화가 발생한다. 따라서 총 5kB의 내부 단편화가 발행한다. 또는 7kB 작업을 8kB 영역에 할당하고, 6kB 작업을 10kB에 할당해도 된다. 총 6kB 내부 단편화가 생긴다.
현대 운영체제에서 메모리 관리는 기본적으로 고정 분할 방식을 사용하면서 일부분은 가변 분할 방식을 혼합하고 있다.

2. 가변 분할 방식의 메모리 관리
   가상 메모리 시스템에서는 가변 분할 방식을 세그먼트 기법이라고 한다. 여기서는 가변 분할 방식에서는 프로세스를 배치하는 방법과 이에 따른 문제점을 알아본다.

(1) 프로세스 배치와 외부 단편화
가변 분할 방식의 자리 배정 예 1
그림과 같이 총 16개의 의자가 놓인 식당이 있다고 가정한다. 식당의 의자에는 번호를 매기고 손님은 어디에 앉아도 상관없지만 일행은 나란히 붙어 앉도록 한다. 손님들의 도착 순서는 A팀(3명) -> B팀(2명) -> C팀(2명) -> D팀(1명) -> E팀(4명) -> F팀(1명) -> G팀(2명) -> H팀(4명) -> I팀(2명)이다. 16번호 의자는 빈 의자를 의미한다. 현재 A팀부터 G팀까지 앞에서부터 차례대로 의자에 앉았고, H팀 4명과 I팀 2명은 자리를 ㄹ배정하지 목하고 대기하는 인원으로 한다.

(2) 가변 분할 방식의 자리 배정 예 2
그림은 A팀 3명과 D팀 1명이 식사를 마치고 퇴장해서 1번, 2번, 3번, 8번, 16번 의자가 비어 있는 상황이다. 의자가 5개 비어 있지만 4개가 나란히 비어 있는 상태가 아니기 때문에 H팀 4명에게 자리를 배정할 수 없다. 이때 B팀과 C팀에게 오른쪽으로 한자리씩 옮겨달라고 부탁하면 문제가 해결될 수 있으나. 식사 도중 자릴르 옮겨달라고 하기엔 어려운 일이고 복잡하다.

가변 분할 방식의 자리 배정 예 3
마지막 대기 중인 I팀 2명을 먼저 빈자리에 배정할 수도 있지만, H팀이 먼저 기다렸다면 양보하지 않을 가능성이 높다. 만약 양보하더라도 이러한 방법은 아사현상(기아상태)를 유발해서 바람직하지 않다. 인원이 많은 팀이 계속 자리를 배정받지 못하는 문제가 발생할 수 있으므로 의자가 비었다고 우선순위에 상관없이 아무 팀이나 앉히면 안된다.
그림은 그림에 이어 B팀 2명과 F팀 1명이 식사를 마치고 나간 상황으로 1~5번 의자가 비게 되어 H팀 4명이 자리를 배정받는다. 결과적으로 5번, 8번, 13번, 16번 의자가 비어 있지만 I팀 2명은 여전히 자리를 배정받지 못한다.

그림 ~ 그림에서 의자는 메모리에, A~I팀의 손님들은 프로세스에 비유할 수 있다. 위의 자리 배정과 같이 가변 분할 방식은 빈 영역이 있어도 서로 떨어져 있으면 프로세스를 배정하지 못하는 것이 문제이아. 이로 인해 작은 조각들이 발생하는 현상을 단편화(fragmentation) 또는 조각화라고 한다.

가변 분할 방식과 외부 단편화
그림과 같이 물리 메모리에 프로세스 A, B, C, D, E를 순서대로 배치했을 때 프로세스 B와 D가 종료되면 18kB와 17kB의 빈 공간이 생긴다. 이후 18kB보다 큰 프로세스가 들어오면 적당한 공간이 없어 메모리를 배정하지 못했는데, 가변 분할 방식에서 발생하는 이러한 작은 빈 공간을 외부 간편화(external Fragmentation)라고 한다. 프로세스의 바깥쪽에 조각이 발행하기 때문에 이렇게 불리는 것이다.
가변 분할 방식에서는 외부 단편화로 인한 문제를 해결하기 위해 메모리 배치 방식(memory placement strategy)이나 조각 모음(defragmentation)을 사용한다. 메모리 배치 방식은 작은 조각이 발생하지 않도록 프로세스를 배치하는 것이며, 조각 모음은 조각이 발생했을 때 작은 조각들을 모아서 하나의 큰 덩어리로 만드는 작업이다. 메모리 배치 방식은 가변 분할 방식에서 선처리에 해당하고 조각 모음은 후처리에 해당한다.

메모리 할당과 스케줄링 과정
가변 분할 방법에는 운영체제가 메모리의 어느 부분을 사용하고 또한 사용할 수 있는지를 알 수 있는 테이블을 유지해야 한다. 예를 들어 메모리가 256kB이고 운영체제가 40kB이며 작업 큐에 그림의 (a)와 같은 작업이 있다고 하자. 작업 1 ~ 작업 3에 메모리를 할당하면 (b)의 1와 같다. 5시간 후에 작업 2를 종료하여 사용한 메모리를 해제하고 2가 되고, 여기에 작업 4를 할당하면 3이 된다. 그리고 작업 1을 10시간 후에 종료하여 메모리를 해제하면 4가 되고, 작업 5에 메모리를 할당하면 5가 된다.

그림의 예로 사용 가능 공간이 메모리에 흩어져 있고 작업 큐에 대기 중인 프로세스를 실행하려면 프로세스에 할당할 충분한 크기의 메모리 영역을 찾아야 한다는 사실을 알 수 있다. 이때 인접한 공간 블록이 있다면, 블록 2개를 합쳐서 커다란 사용 가능 공간을 만들 수 있다. 물론 사용 가능 공간이 크다면 영역 2개로 나눠 공간 하나는 곧 도착하는 작업에 할당하고, 다른 공간은 다시 종료된 작업의 공간에 변환하여 또 다른 공간을 만들 수 있다. 이처럼 가변 분할(동적 메모리 할당)에 요구된 크기 n을 사용 가능 공간에 어떻게 할당하느냐는 문제로 남는다. 사용 가능 공간을 어느 작업에 할당하는 것이 가장 좋은지 결정하는 일반적인 메모리 배치 방법으로 최초 배치, 최적 배치, 최악 배치 방법이 있다.

(2) 메모리의 배치 방식
가변 분할 방식의 외부 단편화 문제를 해결하기 위한 대표적인 메모리 배치 방식으로는 최초 배치(first fit), 최적 배치(best fit), 최악 배치(worst fit)가 있다. 그 외에는 버디 시스템(buddy syste)이 있다.

최초 배치(first fit) 방법
최초 배치는 단편화를 고려하지 않는 것으로, 프로세스를 메모리의 빈 공간에 배치할 때 메모리에 적재 가능한 공간을 순서대로 찾다가 첫 번째로 발견한 공간에 프로세스를 배치하는 방법이다. 검색을 이용 가능 공간의 리스트 맨 앞이나 이전의 최초 적합 검색이 끝났던 곳에서 시작하면 충분히 큰 사용 공간을 빨리 찾을 수 있다. 그러나 이 방법은 공간 활용률이 떨어질 수 있다는 단점이 있다.

최적 배치(best fit) 방법
최적 배치는 메모리의 빈 공간을 모두 확인한 후 적당한 크기 가운데 가장 작은 공간에 프로세스를 배치하는 방법이다. 사용 가능 공간이 크기 순으로 정렬되어 있지 않으면 전체를 검색해야 한다. 사용 가능 공간을 계속 정렬하는 과정이 필요하므로 비효율적일 수 있다. 사용 가능 공간 이용률은 향상될 수 있으나 할당 과정에 많은 시간이 소요될 수 있다. 그리고 가장 작은 또는 다른 사용 가능 공간을 만들 수 있다.

최악 배치(worst fit) 방법
최적 배치와 정반대인 최악 배치는 빈 공간을 모두 확인한 후 가장 큰 공간에 프로세스를 배치하는 방법이다. 공간이 크기 순으로 정렬되어 있지 않으면 전체를 검색해야 한다. 가장 큰 사용 가능 공간에 할당하기 때문에 가장 작은 또 다른 사용 가능 공간을 만드는 최적 적합보다 메모리 활용 면에서 더 유용하다.

(3) 조각 모음
최초 배치, 최적 배치, 최악 배치 방식을 사용해도 단편화 현상이 발행한다. 원래 가변 분할 방식의 목적은 프로세스를 한 덩어리로 취급하여 메모리 관리의 효율성을 높이는 것인데, 메모리 배치 방식으로는 근본적으로 문제를 해결하지 못한다.
가변 분할 방식에서는 메모리에 올라오는 프로세스가 차례대로 배치되기 때문에 공간 사용에 큰 문제가 없다. 그러나 작은 프로세스가 작업을 마치고 메모리에서 나가면 그 공간이 조각으로 남아 쓸모없을 가능성이 높다. 이렇게 단편화가 발생하면 이미 배치된 프로세스를 인접한 빈 공간으로 옮겨 하나의 큰 덩어리로 만들어야 한다.

조각 모음 과정
조각 모음은 서로 떨어져 있는 여러 개의 빈 공간을 합치는 작업이다. 조각 모음은 다음과 같은 순서로 진행된다.

조각 모음을 하기 위해 이동할 프로세스의 동작을 멈춘다.
프로세스를 적당한 위치로 이동한다. 프로세스가 원래의 위치에서 이동하기 때문에 프로세스의 상대 주소 값을 바꾼다.
이러한 작업을 모두 마친 후 프로세스를 다시 시작한다.

조각 모음을 하려면 위와 같은 과정을 거치므로 많은 시간이 걸리며 가변 분할 방식은 외부 단편화로 인해 조각 모음과 같은 부가적인 작업이 필요하므로 메모리 관리가 복잡하다.

하드디스크 조각 모음
외부 단편화는 하드디스크와 같은 저장장치에서도 발생한다. 하드디스크에는 동영상 같은 큰 파일도 저장되고 문서와 같은 작은 파일도 저장된다. 빈 하드디스크에 데이터를 채운면 데이터가 쌓이다가 데이터의 삭제와 저장을 반복하면서 데이터가 여러 공간에 나눠 저장된다. 이러한 현상은 시간이 흐를수록 더욱 심해지고 결국 하드디스크의 데이터 입/출력 속도를 떨어뜨려 컴퓨터의 성능을 저하하는 원인이 된다. 따라서 하드디스크와 같은 저장장치도 성능을 유지하려면 주기적으로 조각 모음을 실행해야 한다.

이런 낭비를 해결하는 방안으로 메모리 병합(통합)과 압출 방법을 생각할 수 있다.

메모리 통합 방법
메모리 통합(coalescing) 방법은 하나의 작업이 끝났을 때 다른 빈 공간과 인접해 있는지 점검하여 하나로 합치는 것이지만 메모리 전반에 흩어진 빈 공간을 모두 통합하기는 어렵다.

메모리 압축 방법
메모리 압축(compactation) 방법은 메모리의 내용을 적절히 움직여 사용 가능 공간을 큰 불록 하나로 만드는 것으로 그림 (b)의 5는 그림과 같이 하나의 공간인 66kB로 압축할 수 있다.
압축은 항상 가능한 것은 아니고, 작업 4와 작업 3을 이동했을 때, 모든 내부 주소를 대체해야 이 프로세스들을 새로운 위치에서 수행할 수 있다. 주소 대체가 정적이고 컴파일이나 적재할 때 실행된다면 압축을 수행할 수 없다. 주소들을 동적으로 대체하면 프로세스들이 이동하고 기준 레지스터의 변화를 요구하면 새로운 기준 주소를 반영하므로 압축은 대체가 동적일 때만 가능하다. 또 실행 시간에 할 수 있다는 특징이 있다.

장점
메모리 압축은 가변 메모리에 발생하는 수많은 작은 공백을 하나의 큰 공백으로 변환하여 새로운 작업에 할당할 수 있다.
단점
압축하는 동안 시스템은 모든 일을 중지해야 한다. 이때 대화형 사용자는 응답시간이 일정하지 않게 되고, 실시간 시스템에서는 심각한 문제가 될 수 있다.
메모리에 있는 작업들은 이동해야 하므로 프로그램을 적재할 때 제거되는 대치 관련 정보를 액세스 가능한 형태로 보관해야 한다.
압축 작업을 자주 요구하며 시스템 자원의 소모가 크다.

(4) 다중 프로그래밍 환경의 버디 시스템
고정 분할 방법이나 동적 분할 방법은 모두 단편화 문제가 있다. 이런 단편화 현상을 해결하는 방법으로 버디 시스템(buddy system)을 제안했다. 버디 시스템은 가변 분할 방식이지만 고정 분할 방식과 유사한 점이 있다. 그러나 최근 운영체제는 페이징이나 세그먼테이션을 활용한 가상 메모리를 선호하고, 유닉스의 커널 메모리 할당이나 병렬 처리 시스템에만 응용된다.
버디 시스템은 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들며, 가증할 때마다 인접한 버퍼(free buffer)들을 합치는 과정을 반복한다. 버퍼를 나눌 때 각각을 서로의 버디라고 한다.

버디 시스템의 작동 방식
프로세스의 크기에 맞게 메모리를 이등분하고, 프로세스를 메모리에 배치한다.
나뉜 메모리의 각 구역에는 프로세스가 한 개만 들어간다.
프로세스가 종료되면 주변의 빈 조각과 합쳐서 하나의 큰 덩어리를 만든다.

버디 알고리즘의 예
그림은 64kB의 초기 블록을 사용한 예이다.
첫 번째 8kB를 요구하면 (a)와 같이 블록 32kB 버디 2ㅐ로 나누고, 여전히 요청한 크기보다 크므로 계속 나누고 크기가 8kB가 되면 요청에 맞게 할당할 수 있다.
두 번째 8kB를 요청한다면 (b)와 같이 바로 할당할 수 있다.
세 번째로 4kB를 요청한다면 (c)와 같이 다시 블록을 버디 2개로 나누고 요청에 할당한다.
네 번째로 (d)와 같이 두 번째로 요청한 8kB를 해체하고
(e)와 같이 첫 번째 요청한 8kB를 해제하면서 합친다.