14장 메모리

14.1 메모리 관리

실제 컴퓨터에 어떤 자료 구조를 구현하기 위해서 컴퓨터 메모리를 사용할 필요가 있다. 

컴퓨터 메모리(computer memory): 단순히 메모리 단어(word)들의 시퀀스

각각은 (컴퓨터에 따라) 4바이트, 8바이트 또는 16바이트로 구성된다. 

이 메모리 단어들은 0부터 N-1까지 번호가 매겨진다. 

(N: 컴퓨터가 사용할 수 있는 메모리 워드의 수)

주소(address): 각 메모리 단어와 관련된 번호

따라서 컴퓨터의 메모리는 기본적으로 하나의 거대한 메모리 단어 배열로 볼 수 있다. 

이 메모리를 사용하여 자료 구조를 구성하려면 

변수, 노드, 포인터, 배열, 문자열 등 자료에 필요한 공간과 

컴퓨터가 실행할 프로그램을 제공하도록 

컴퓨터의 메모리를 관리(manage)해야 한다. 

이 절에서는 메모리 관리의 기본 사항에 대해 설명한다.

14.1.1 Java 가상 머신의 스택

자바 프로그램은 일반적으로

잘 정의된 모델인 자바 가상 머신(Java Virtual Machine, JVM)에 대한

"기계" 어로 정의되는 일련의 바이트 코드로 컴파일된다.

자바 언어 자체의 정의는 JVM의 정의의 핵심이다. 

자바 코드를 특정 CPU의 기계어가 아닌 JVM 바이트 코드로 컴파일함으로써 

자바 프로그램을 JVM을 모방할 수 있는 프로그램을 가진 

개인용 컴퓨터나 서버와 같은 컴퓨터에서 실행할 수 있다. 

흥미로운 점은 스택 자료 구조가 JVM의 정의에서 중심적인 역할을 한다는 것이다.

자바 메소드 스택

스택은 자바 프로그램의 런타임 환경에 중요한 응용 프로그램이다. 

자바 메소드 스택(Java method stack) 또는 자바 스택(Java stack):

실행 중인 자바 프로그램(더 정확하게는 실행 중인 자바 스레드)에 있는 개인 스택

실행 중에 호출되는 메소드에 대한 로컬 변수 및 기타 중요한 정보를 추적하는 데 사용된다(그림 14.1 참조)

좀 더 구체적으로, 자바 프로그램의 실행 중에, 

자바 가상 머신(JVM)은 요소들이 현재 활성(즉, 종료되지 않은) 메소드 호출의 디스크립터인 스택을 유지한다. 

프레임(frame): JVM에서 요소들이 현재 활성 메소드 호출된 스택

메소드 "fool"의 일부 호출을 위한 프레임은 

메소드 fool의 로컬 변수들 및 파라미터들의 현재 값뿐만 아니라 

fool을 호출한 메소드 "cool"에 대한 정보와 메소드 "cool"로 반환되어야 하는 것에 대한 정보를 저장한다.

그림 14.1 

자바 메소드 스택의 예: 

메소드 fool이 방금 메소드 cool에 의해 호출되었는데, 

이전에는 메소드 main에 의해 호출되었다. 

스택 프레임에 저장된 프로그램 카운터, 파라미터 및 로컬 변수 값에 주목한다. 

메소드 fool의 호출이 종료되면 메소드 cool의 호출은 명령어 217에서 실행을 재개할 것이며, 

이는 스택 프레임에 저장된 프로그램 카운터의 값을 증가시킴으로써 얻어진다.

프로그램 카운터 추적

JVM은 프로그램에서 JVM이 현재 실행하고 있는 문의 주소를 유지하기 위해 

프로그램 카운터(program counter)라는 특별한 변수를 유지한다. 

메소드 "cool"이 다른 메소드 "fool"을 호출하면 

프로그램 카운터의 현재 값이 현재 cool 호출의 프레임에 기록된다

(따라서 JVM은 메소드 fool이 완료되면 어디로 돌아가야 할지 알 것이다). 

 

자바 스택의 맨 위에는 실행 중인 메소드의 프레임이 있다.

실행 중인 메소드(running method): 현재 실행에 대한 제어권을 가지고 있는 메소드

스택의 나머지 요소는 중단된 메소드의 프레임이 있다.

중단된 메소드(suspended method): 다른 메소드를 호출하여 현재 종료 시 제어권을 반환하기를 기다리는 메소드

 

스택 내 요소의 순서는 현재 활성 메소드의 호출 체인에 대응한다. 

새로운 메소드가 호출되면 이 메소드에 대한 프레임이 스택 상으로 푸시된다. 

종료되면 해당 프레임이 스택으로부터 팝되고 JVM은 이전에 중단된 메소드의 처리를 다시 시작한다.

call-by-value 매개 변수 전달 이해

JVM은 메소드에 대한 파라미터 전달을 수행하기 위해 자바 스택을 사용한다. 

구체적으로 자바는 call-by-value 매개변수 전달 프로토콜을 사용한다. 

이는 변수(또는 수식)의 현재 값이 호출된 메소드에 인수로 전달되는 것임을 의미한다.

int나 float와 같은 원시 타입의 변수 x의 경우 현재 x의 값은 단순히 x와 연관된 숫자에 불과하다. 

그런 값을 호출된 메소드에 전달하면 호출된 메소드의 프레임 내의 로컬 변수에 할당된다. 

(이 간단한 할당은 그림 14.1에도 나타나 있다.) 

호출된 메소드가 이 로컬 변수의 값을 변경하더라도 

호출된 메소드의 변수의 값은 변경되지 않는다는 점에 유의한다.

그러나 물체를 가리키는 변수 x의 경우 현재 x의 값은 물체 x의 메모리 주소가 된다. 

(이 주소가 실제로 어디에 있는지에 대해서는 14.1.2절에서 자세히 설명하겠다.) 

따라서 어떤 방식으로 물체 x를 매개 변수로 전달하면 실제로 x의 주소가 전달된다. 

호출된 방식으로 어떤 로컬 변수 y에 이 주소가 할당되면 

y는 x가 가리키는 것과 같은 물체를 지칭할 것이다.

 

따라서 만약 호출된 메소드가 y가 가리키는 대상의 내부 상태를 바꾼다면, 

그것은 동시에 x가 가리키는 대상의 내부 상태를 바꾼 것이 될 것이다. 

그럼에도 불구하고 호출된 프로그램이 y를 어떤 다른 대상을 가리키도록 바꾼다면, 

x는 변하지 않을 것이고, 그것은 여전히 이전에 참조했던 동일한 대상을 가리킨다.

따라서 자바 메소드 스택은 JVM에 의해 메소드 호출과 매개변수 전달을 구현하는 데 사용된다. 

덧붙여서 메소드 스택은 자바의 특정한 특징이 아니다. 

C와 C++를 포함한 대부분의 현대 프로그래밍 언어의 런타임 환경에서 사용된다.

연산자 스택

흥미롭게도 실제로 JVM이 스택을 사용하는 또 다른 곳이 있다. 

(a + b) * (c + d)/e와 같은 산술 수식들은 JVM이

피연산자 스택(operand stack)을 사용하여 평가한다. 

a + b와 같은 간단한 이진 연산은 

스택에서 a를 누르고, 

스택에서 b를 누른 다음, 

상위 두 항목을 스택에서 터뜨려 이진 연산을 수행하고, 

결과를 스택으로 다시 푸시하는 명령어를 호출함으로써 계산된다. 

 

메모리로 요소를 쓰고 읽는 명령어들도 피연산자 스택에 대한 pop과 push 메소드를 사용한다. 

따라서 JVM은 자바로 된 산술 수식들을 평가하기 위해 스택을 사용한다.

7.3.6절에서는 JVM이 사용하는 알고리즘인 

후위 순회를 사용하여 산술식을 계산하는 방법을 설명했다. 

그러나 그 알고리즘을 피연산자 스택을 명시적으로 사용하는 방식이 아니라 재귀적 방식으로 설명했다. 

그럼에도 불구하고 이 재귀적 설명 = 피연산자 스택을 사용하는 방식의 비재귀적 버전

재귀 구현

메소드 호출을 구현하기 위해 스택을 사용하는 것의 장점 중 하나는 

프로그램이 재귀(recursion)를 사용할 수 있게 해준다는 점이다. 

즉 3.5절에서 설명한 바와 같이 메소드가 자신을 호출할 수 있게 해준다. 

흥미롭게도 코볼이나 포트란 같은 초기 프로그래밍 언어는 

원래 런타임 스택을 사용하여 메소드 및 프로시저 호출을 구현하지 않았다. 

하지만 코볼이나 포트란 같은 현대 버전의 고전 언어를 포함한 

모든 현대 프로그래밍 언어는 재귀가 허용하는 우아함과 효율성 때문에 

메소드 및 프로시저 호출을 위해 런타임 스택을 사용한다.

재귀 메소드의 실행에 있어서, 

재귀 추적의 각 박스 - 자바 메소드 스택의 프레임

자바 메소드 스택의 내용 - 초기 메소드 호출부터 현재 메소드 호출까지의 박스의 체인

런타임 스택이 재귀적 방법을 어떻게 허용하는지 더 잘 설명하기 위해 

코드 조각 14.1에 표시된 것처럼

factorial 함수의 고전적인 재귀적 정의의 자바 구현을 고려해 보자,
n! = n(n − 1)(n − 2) ... 1,

코드 조각 14.1: 재귀적 방법 factorial.

public static long factorial(long n) {
  if (n <= 1)
    return 1;
  else
    return n * factorial(n-1);
}

1. 메소드 factorial를 처음 호출할 때, 그것의 스택 프레임은 n값을 저장하는 로컬 변수를 포함한다. 

2. 메소드 "factorial()"는 (n - 1)!을 계산하기 위해 자신을 재귀적으로 호출하는데,

    자바 런타임 스택에서 새로운 프레임을 푸시한다.

3. 다시, 이 재귀적 호출은 (n - 2)! 등을 계산하기 위해 스스로를 호출한다. 

 

n. 재귀적 호출들의 연쇄, 즉 런타임 스택은 크기 n까지만 증가하는데, 

    이는 factorial(1)을 호출하는 것이 자신을 재귀적으로 호출하지 않고 즉시 1을 반환하기 때문이다. 

    런타임 스택은 메소드 factorial()이 여러 개의 활성 프레임에서 동시에 존재하도록 허용한다. 

    각 프레임은 반환될 값뿐만 아니라 매개 변수 n의 값을 저장한다. 

 

결국 첫 번째 재귀적 호출이 종료되면 (n - 1)!을 반환하고

n을 곱하여 factorial 메소드의 원래 호출에 대해 n!을 계산한다.

14.1.2 메모리 힙의 공간 할당

이미 (14.1.1절에서) 자바 가상 머신이 

방법의 로컬 변수를 자바 런타임 스택 상에서 

그 방법의 프레임에 할당하는 방법에 대해 설명했다. 

그러나 자바 스택은 자바에서 프로그램 자료에 사용할 수 있는 유일한 종류의 메모리는 아니다.

동적 메모리 할당

어떤 메소드를 실행하는 동안 자바에 내장된 특수한 new 연산자를 활용함으로써 

객체에 대한 메모리를 동적으로 할당할 수도 있다. 

예를 들어, 자바 문은 크기가 변수 k로 주어진 정수들의 배열을 만든다:
int[] items = new int[k];

상기 배열의 크기는 오직 런타임(runtime)에서만 알려져 있다. 

더욱이, 배열은 그것을 생성한 메소드가 종료된 후에도 계속 존재할 수 있다. 

따라서, 이 배열에 대한 메모리는 자바 스택 상에 할당될 수 없다.

메모리 힙

자바는 이 객체의 메모리에 자바 스택을 사용하는 대신에 

다른 스토리지 영역인 메모리 힙의 메모리를 사용한다. 

이 메모리 영역은 다른 메모리 영역과 함께 그림 14.2의 자바 가상 머신에서 설명한다. 

 

메모리 힙에서 이용 가능한 스토리지는 블록들로 나뉘는데, 

블록(block): 가변적이거나 고정된 크기일 수 있는 메모리의 연속적인 배열와 같은 "덩어리"

 

논의를 간단히 하기 위해, 메모리 힙의 블록들은 고정된 크기(ex. 1,024바이트)이며, 

하나의 블록은 우리가 만들고자 하는 어떤 물체에도 충분히 큰 크기라고 가정하자. 

(더 일반적인 경우를 효율적으로 다루는 것은 사실 흥미로운 연구 문제이다.)

그림 14.2: Java Virtual Machine의 메모리 주소 레이아웃의 개략도

메모리 할당 알고리즘

자바 가상 머신의 정의는 메모리 힙이 새로운 개체에 대해 메모리를 빠르게 할당할 수 있어야 하는데, 

이를 수행하기 위해 사용해야 할 자료 구조를 명시하지는 않았다. 

한 가지 인기 있는 방법은 

사용 가능한 빈 메모리의 연속적인 "구멍"들을 

자유 리스트(free list)라고 불리는 이중 링크 리스트에 보관하는 것이다. 

이 구멍들을 연결하는 링크들은 메모리가 사용되고 있지 않으므로 구멍 자체의 내부에 저장된다.

메모리가 할당되고 할당이 해제됨에 따라 자유 리스트에 있는 구멍들의 집합이 변하며, 

사용되지 않은 메모리는 사용된 메모리의 블록들에 의해 분할된 서로소인 구멍들로 분리된다. 

단편화(fragmentation): 사용되지 않은 메모리를 별도의 구멍들로 분리하는 것

물론 단편화를 가능한 한 최소화하고자 한다.

발생할 수 있는 단편화에는 두 가지 종류가 있다. 

1) 내부 단편화(Internal fragmentation): 

   할당된 메모리 블록의 일부분이 실제로 사용되지 않을 때 발생한다. 

   ex) 프로그램은 크기가 1000인 배열을 요청할 수 있지만 이 배열의 처음 100개의 셀만 사용한다. 

   런타임 환경이 내부 플래그멘테이션을 줄이기 위해 할 수 있는 일은 많지 않다. 

2) 외부 단편화(External fragmentation):

     할당된 메모리의 여러 연속된 블록 사이에 사용되지 않은 메모리가 상당히 많을 때 발생한다. 

     런타임 환경은 메모리가 요청될 때 어디에 할당할지에 대한 제어권을 가진다.

     ex) 자바에서 새로운 키워드를 사용할 때

     런타임 환경은 외부 플래그멘테이션을 최대한 합리적으로 줄이려는 방식으로 메모리를 할당해야 한다.

외부 단편화를 최소화하기 위해 힙에서 메모리를 할당하는 여러 휴리스틱이 제안되었다. 

1) best-fit algorithm:

    프리 리스트 전체를 탐색하여 요청되는 메모리의 양에 가장 가까운 크기의 홀을 찾는다. 

2) first-fit algorithm:

    프리 리스트의 처음부터 충분히 큰 첫 번째 홀을 탐색한다. 

3) next-fit algorithm:

    충분히 큰 첫 번째 홀을 탐색하지만 

    이전에 중단했던 부분부터 탐색을 시작하여 

    프리 리스트를 원형 연결 리스트로 본다는 점에서 유사하다. 

4) worst-fit algorithm:

    프리 리스트를 탐색하여 사용 가능한 메모리의 가장 큰 홀을 탐색하는데, 

    이 홀이 우선순위 큐로 유지된다면 

    전체 프리 리스트를 탐색하는 것보다 더 빨리 수행될 수도 있다(8장). 

     각 알고리즘은 선택한 메모리 홀에서 요청된 메모리 양을 뺀 후 남은 홀 부분을 프리 리스트로 돌려보낸다.

각 알고리즘의 장단점

1) best-fit algorithm:

    선택한 구멍의 남은 부분이 작기 때문에

    최악의 외부 조각화를 발생시키는 경향이 있다. 

2) first-fit algorithm:

     빠르지만 자유 리스트의 맨 앞에 많은 외부 조각화를 발생시키는 경향이 있기 때문에 

     향후 검색 속도가 느려진다. 

3) next-fit algorithm:

     메모리 더미 전체에 조각화를 더 균일하게 퍼뜨리기 때문에 

     검색 시간을 낮게 유지한다. 

    그러나 이러한 확산은 큰 블록을 할당하는 것을 더 어렵게 한다. 

4) worst-fit algorithm:

    빈 메모리의 연속적인 부분을 가능한 한 크게 유지함으로써 

    이러한 문제를 방지하려고 한다. 

 

14.1.3 쓰레기 수거

C와 C++와 같은 일부 언어에서는 

객체에 대한 메모리 공간을 프로그래머가 명시적으로 할당 해제해야 하는데, 

이는 초보 프로그래머들이 간과하는 의무이며 

숙련된 프로그래머들도 답답한 프로그래밍 오류의 원인이 된다. 

대신 자바의 설계자들은 메모리 관리의 부담을 전적으로 런타임 환경에 두었다.

위에서 언급한 바와 같이 객체에 대한 메모리는 메모리 힙으로부터 할당되고 

실행 중인 자바 프로그램의 인스턴스 변수에 대한 공간은 

실행 중인 스레드마다 하나씩 메소드 스택에 배치된다. 

루트 객체(root object): 실행 중인 스레드의 메소드 스택의 모든 변수와 객체

메소드 스택의 인스턴스 변수는 메모리 힙의 객체를 참조할 수 있기 때문이다.

라이브 객체(live object): 루트 객체에서 시작하는 객체 참조를 후속하여 도달할 수 있는 모든 객체

라이브 객체는 실행 중인 프로그램에 의해 현재 사용되고 있는 활성 객체이므로 

이 객체들은 할당 해제되어서는 안 된다. 

 

예시)

실행 중인 자바 프로그램은 이중 연결 리스트를 사용하여 구현된 시퀀스 S에 대한 참조를 변수에 저장할 수 있다. 

S에 대한 참조 변수는 루트 객체이지만 S에 대한 객체는 라이브 객체이며, 

이 객체에서 참조되는 모든 노드 객체와 이러한 노드 객체에서 참조되는 모든 요소가 마찬가지이다.

 

가비지 컬렉션(garbage collection):
때때로, 자바 가상 머신(JVM)은 메모리 힙 내의 이용 가능한 공간이 부족해지고 있다는 것을 알아차릴 수 있다. 

그러한 때에, JVM은 더 이상 살아있지 않은 객체들을 위해 사용되고 있는 공간을 회수하고, 

회수된 메모리를 프리 리스트로 되돌리도록 선택할 수 있다. 

 

가비지 컬렉션에 대한 여러 상이한 알고리즘들이 있지만, 

가장 많이 사용되는 것 중 하나는 마크-스윕(mark-sweep) 알고리즘이다.

마크-스위프 가비지 컬렉션 알고리즘에서 

1) 그 객체가 라이브인지 아닌지를 식별하는 각각의 객체에 "마크" 비트를 연결한다. 

2) 어느 시점에서 가비지 컬렉션이 필요하다고 판단되면, 

    실행 중인 다른 모든 스레드를 일시 중단하고 

    메모리 힙에 현재 할당된 모든 객체의 마크 비트를 지운다. 

3) 현재 실행 중인 스레드의 자바 스택을 추적하여 

     이 스택들에 있는 모든 (루트) 객체를 "라이브"로 표시한다. 

4) 루트 객체에서 도달 가능한 다른 모든 라이브 객체를 결정해야 한다. 

 

이를 효율적으로 수행하기 위해서

깊이 우선 탐색 순회의 방향 그래프 버전 사용 가능(섹션 13.3.1). 

메모리 힙의 각 객체 - 방향 그래프의 정점

한 객체에서 다른 객체로의 참조 - 방향 간선

 

1. "마크" 단계:

    각 루트 객체에서 지시 DFS를 수행함으로써, 각 라이브 객체를 정확하게 식별하고 표시할 수 있다. 

 

2. "스윕"단계:

     메모리 힙을 스캔하여 표시되지 않은 개체에 사용되고 있는 공간을 모두 회수한다. 

     이 때 메모리 힙에 할당된 모든 공간을 하나의 블록으로 통합하여 

      당분간 외부 조각화를 제거할 수도 있다. 

 

3. 앞의 단계를 완료되면 중단된 스레드를 다시 실행한다. 

 

따라서 마크 스윕 가비지 컬렉션 알고리즘은 

살아있는 개체 수와 참조 수에 메모리 힙의 크기를 더한 값으로 

사용되지 않는 공간을 시간적으로 회수한다.

DFS 제자리 수행

마크-스위프 알고리즘 중 마크 단계에서 문제점

사용 가능한 메모리가 부족한 상황에서 메모리 공간을 재확보하기 때문에 

가비지 컬렉션 자체에서 여분의 공간을 사용하지 않도록 주의해야 한다. 

문제는 DFS 알고리즘이 13.3.1절에서 설명한 재귀적인 방식으로 

그래프의 정점 수에 비례하는 공간을 사용할 수 있다는 것이다. 

가비지 컬렉션의 경우 그래프의 정점은 메모리 힙의 객체이므로 사용할 메모리가 이렇게 많지 않을 것이다. 

 

위의 문제점에 대한 유일한 대안책

제자리에서 수행하는 방법을 찾는 것

즉 일정한 양의 추가 저장소만을 사용하여 DFS를 수행해야 한다.

DFS를 제자리에서 수행하는 주된 아이디어

(가비지 컬렉션의 경우 객체 참조에 해당하는) 

그래프의 간선을 사용하여 재귀 스택을 모의실험하는 것

방문한 정점 v에서 새로운 정점 w로 한 간선을 횡단할 때, 

v의 인접 리스트에 저장된 간선 (v, w)를 DFS 트리에서 v의 부모로 다시 가리키도록 변경한다. 

(w에서 "재귀적" 호출로부터 돌아오는 것을 모의실험하여) 

v로 돌아오면, 이제 수정한 간선을 다시 w로 가리키도록 전환할 수 있다. 

물론, 어떤 간선을 다시 변경해야 하는지를 식별하는 방법이 필요하다. 

한 가지 가능한 방법은 v 밖으로 나가는 참조를 1, 2 등으로 번호를 매기고 저장하는 것인데, 

이는 수정한 간선을 알려주는 카운트 식별자이다.

카운트 식별자를 사용하려면 개체당 저장어가 추가로 필요하다. 

그러나 이 추가어는 일부 구현예에서는 피할 수 있다. 

예시) 자바 가상 머신의 많은 구현예들은 개체를 타입 식별자를 가진 참조의 컴포지션으로 표현하고

(이 개체가 정수형인지 또는 어떤 다른 타입인지를 나타낸다) 

이 개체에 대한 다른 개체들 또는 데이터 필드들에 대한 참조로 표현한다. 

그러한 구현예들에서 타입 참조는 항상 컴포지션의 첫 번째 요소가 되어야 하기 때문에, 

개체 v를 떠나 어떤 개체 w로 갈 때 변경한 에지를 "표시"하기 위해 이 참조를 사용할 수 있다.

단순히 v의 종류를 참조하는 v에서의 참조와 w를 참조하는 v에서의 참조를 교환한다. 

v로 돌아가면 변경한 간선 (v, w)는 v에 대한 구성에서 첫 번째 참조가 될 것이고, 

v의 종류를 참조하는 위치는 

v의 인접 리스트에서 이 간선이 속하는 위치를 알려줄 것이기 때문에 

빠르게 식별할 수 있다. 

따라서 간선 교환 트릭을 사용하든 카운트 식별자를 사용하든 

점근적 실행 시간에 영향을 주지 않고 

DFS를 제자리에 구현할 수 있다.

14.2 외장 메모리 및 캐싱

대용량의 자료를 처리해야 하는 컴퓨터 어플리케이션의 예

예) 과학적 데이터 세트의 분석, 금융거래의 처리, 데이터베이스(전화번호부 등)의 정리 및 유지보수

실제로 처리해야 하는 데이터의 양이 너무 많아 

컴퓨터의 내부 메모리에 온전히 들어갈 수 없는 경우가 많다.

14.2.1 메모리 계층

큰 데이터 세트를 수용하기 위해 컴퓨터는 서로 다른 종류의 메모리 계층(hierarchy)을 갖는데, 

메모리의 크기와 CPU로부터의 거리 면에서 다르다. 

1. CPU 자체가 사용하는 내부 레지스터

    그러한 위치에 액세스하는 것은 매우 빠르지만 그러한 위치는 상대적으로 적다. 

2. 캐시 메모리

    이 메모리는 CPU의 레지스터 세트보다 상당히 크지만 액세스하는 데에는 더 오랜 시간이 걸린다. 

    그리고 액세스 시간이 점점 더 느린 캐시도 여러 개 존재할 수 있다. 

3. 메인 메모리 또는 코어 메모리라고도 알려진 내부 메모리

    내부 메모리는 캐시 메모리보다 상당히 크지만 액세스하는 데에도 더 많은 시간이 필요하다. 

4. 외부 메모리

    ex) 디스크, CD 드라이브, DVD 드라이브 및/또는 테이프

    이 메모리는 매우 크지만 속도도 매우 느리다. 

따라서 컴퓨터에 대한 메모리 계층은 이전 레벨보다 크고 느린 4개의 레벨로 구성된다고 볼 수 있다

(그림 14.3 참조)

그러나 대부분의 응용 분야에서 실제로 중요한 것은 

모든 데이터 항목을 저장할 수 있는 수준과 그 바로 아래 수준 두 가지뿐이다. 

이 경우 일반적으로 모든 항목을 저장할 수 있는 데이터 항목을 

상위 메모리에 넣고 꺼내는 것이 계산상의 병목 현상이 될 것이다.

그림 14.3: 메모리 계층.

캐시 및 디스크

구체적으로, 가장 중요한 두 레벨은 우리가 해결하려고 하는 문제의 크기에 따라 달라진다. 

 

메인 메모리에 완전히 들어갈 수 있는 문제의 경우, 가장 중요한 두 레벨은 캐시 메모리와 내장 메모리이다. 

내장 메모리에 대한 액세스 시간 =

캐시 메모리에 대한 액세스 시간 * (10배에서 100배)

따라서, 캐시 메모리에서 대부분의 메모리 액세스를 수행할 수 있는 것이 바람직하다. 

 

메인 메모리에 완전히 들어가지 않는 문제의 경우, 반면에, 가장 중요한 두 레벨은 내장 메모리와 외장 메모리이다.

여기서 차이점은 훨씬 더 극적인데, 

범용 외장 메모리 장치인 디스크의 액세스 시간 =

내장 메모리의 액세스 시간 * (100,000배에서 1,000,000배)

 

ex)
이 후자의 수치를 원근법으로 표현하자면, 

볼티모어에 시카고에 부모님께 돈을 요청하는 메시지를 보내고자 하는 학생이 있다고 상상해보자. 

 

만약 학생이 부모님께 이메일을 보낸다면, 약 5초 안에 부모님의 컴퓨터에 도착할 수 있다. 

CPU가 내장 메모리에 접근하는 것에 해당하는 통신방식을 생각해 보자. 

 

외장 메모리 접근 속도가 50만 배 느린 통신방식은 

학생이 직접 시카고로 걸어가서 메시지를 전달하는 것인데, 

하루 평균 20마일을 갈 수 있다면 약 한 달이 걸릴 것이다. 

 

→ 외장 메모리에 가능한 한 적게 접근해야 한다.

14.2.2 캐싱 전략

수준에 따라 접근 시간의 편차가 크지만,

대부분의 알고리즘은 메모리 계층 구조를 염두에 두고 설계되지 않는다. 

실제로 지금까지 이 책에서 설명한 모든 알고리즘 분석은 모든 메모리 접근이 동일하다고 가정했다. 

이 가정은 처음에는 훌륭한 감독처럼 보일 수도 있지만, 

마지막 장에서 지금 다루고 있는 것은 사실 합리적인 가정인 이유도 충분하다.

이유 1)

메모리 크기에 관한 특정한 장치 의존적 정보를 얻기가 종종 어렵기 때문에 

모든 메모리 접근에 동일한 시간이 걸린다고 가정할 필요가 있다는 것이다. 

사실 메모리 크기에 관한 정보를 얻는 것이 불가능할 수도 있다. 

예를 들어 여러 다른 컴퓨터 플랫폼에서 실행되도록 설계된 자바 프로그램은 

특정한 컴퓨터 아키텍처 구성의 관점에서 정의될 수 없다. 

만일 아키텍처 특정한 정보를 가지고 있다면, 확실히 아키텍처 특정한 정보를 사용할 수 있다. 

그러나 일단 특정한 아키텍처 구성에 맞게 소프트웨어를 최적화하면, 

소프트웨어는 더 이상 장치 독립적이지 않을 것이다. 

다행히도, 이러한 최적화가 항상 필요한 것은 아닌데, 

그 이유는 주로 동일한 시간의 메모리 접근 가정을 위한 두 번째 이유 때문이다.

캐싱 및 차단

이유 2)

운영체제 설계자들이 대부분의 메모리 접근을 빠르게 할 수 있도록 하는 일반적인 메커니즘을 개발했다는 것이다. 

이러한 메커니즘은 대부분의 소프트웨어가 가지고 있는 두 가지 중요한 참조 지역 속성에 기초한다:

• 시간적 지역성(temporal locality): 

어떤 프로그램이 특정 메모리 위치에 접근한다면 가까운 미래에 이 위치에 다시 접근할 가능성이 높다. 

예) 카운터의 값을 증분하는 것을 포함하여 

여러 다른 표현에서 카운터 변수의 값을 사용하는 것은 꽤 흔하다.

사실, 컴퓨터 설계자들 사이에서 흔한 격언은 

"프로그램은 그것의 시간의 90%를 코드의 10%에 소비한다"는 것이다

• 공간적 지역성(spatial locality): 

어떤 프로그램이 특정 메모리 위치에 접근하면 이 위치 근처에 있는 다른 위치에 접근할 가능성이 높다.

예) 배열을 사용하는 프로그램은 

이 배열의 위치에 순차적 또는 거의 순차적으로 접근할 가능성이 있다.

컴퓨터 과학자들과 공학자들은 

대부분의 소프트웨어들이 이런 종류의 로컬리티를 모두 가지고 있다는 주장을 정당화하기 위해 

광범위한 소프트웨어 프로파일링 실험을 수행했다. 

예를 들어 배열을 스캔하는 데 사용되는 for문은 두 종류의 지역성을 모두 보여줄 것이다.

시간적 및 공간적 지역성은 차례로 2개의 레벨을 가진 컴퓨터 메모리 시스템에 대한

두 가지 기본적인 설계 선택을 야기한다.

 

(2개의 레벨을 가진 컴퓨터 메모리 시스템:

캐시 메모리와 내장 메모리 사이의 인터페이스에 존재하며 

내장 메모리와 외장 메모리 사이의 인터페이스에도 존재함)

1. 첫 번째 설계 선택을 가상 메모리(virtual memory)라고 한다. 

이 개념은 보조 기억장치의 용량만큼의 주소 공간을 제공하고 

보조 레벨에 위치한 데이터가 주소가 정해지면 기본 레벨로 전달하는 것으로 구성된다. 

가상 메모리는 프로그래머가 내부 메모리 크기의 제약에 한정하지 않는다. 

캐싱: 기본 메모리에 데이터를 가져오는 개념, 시간적 지역성에 의해 동기부여를 받는다. 

우선 기본 메모리에 데이터를 가져오면 곧 다시 접근할 수 있기를 바라고 

가까운 미래에 찾아올 이 데이터에 대한 모든 요청에 신속하게 대응할 수 있을 것이다.

2. 두 번째 설계 선택의 동기는 공간적 지역성이다. 

블록킹(blocking):

보조+레벨 메모리 위치 l에 저장된 데이터를 접근하면

그 위치 l을 포함하는 연속적인 위치들의 큰 블록인 기본+레벨 메모리로 들여온다(그림 14.4 참조).

l에 가까운 다른 보조+레벨 메모리 위치들도 곧 접근할 것이라는 예상에서 동기를 부여한 것이다. 

캐시 라인(cash line): 캐시 메모리와 내장 메모리 사이의 인터페이스에서 그런 블록들

페이지(page): 내장 메모리와 외장 메모리 사이의 인터페이스에서 그런 블록들

그림 14.4: 외장 메모리의 블록.

캐싱과 블로킹으로 구현할 때, 

가상 메모리는 종종 보조 기억장치를 실제보다 더 빠르다고 인식하게 한다. 

 

문제점

1) 주 기억장치는 보조 기억장치보다 훨씬 작다. 

2) 게다가 메모리 시스템은 블로킹을 사용하기 때문에 

   어떤 실체 프로그램이든 보조 기억장치에 데이터를 요청하는 시점에 도달할 가능성이 높지만 

   주 기억장치는 이미 블록으로 가득 차 있다. 

 

해결책

이러한 요청을 충족하고 캐싱과 블로킹의 사용을 유지하기 위해서는 

주 기억장치에서 일부 블록을 제거하여 

이 경우 보조 기억장치에서 새로운 블록을 위한 공간을 만들어야 한다.

이 퇴거를 수행하는 방법을 결정하는 것은 

여러 가지 흥미로운 자료 구조와 알고리즘 설계 문제를 야기한다.

캐싱 알고리즘

웹 페이지에 제시된 재방문 정보를 처리해야 하는 여러 웹 애플리케이션이 있다. 

이러한 재방문은 시간적으로나 공간적으로 모두 참조 지역성을 나타내는 것으로 나타났다. 

이러한 참조 지역성을 이용하기 위해서는 

웹 페이지의 복사본을 캐시 메모리에 저장하는 것이 종종 유리하므로, 

이러한 페이지는 다시 요청될 때 신속하게 검색될 수 있다. 

 

완전한 연관 캐시(fully associated cache):

웹 페이지를 포함할 수 있는 m개의 "슬롯"을 갖는 캐시 메모리

웹 페이지가 캐시의 임의의 슬롯에 배치될 수 있다.

 

완전한 연관 캐시가 있다고 가정하자.

1. 브라우저가 실행되면서 서로 다른 웹 페이지를 요청한다. 

2. 브라우저는 이러한 웹 페이지 l을 요청할 때마다 l이 변경되지 않고 

   현재 캐시에 포함되어 있는지 여부를 (퀵 테스트를 사용하여) 결정한다. 

   1) 만약 l이 캐시에 포함되어 있다면 브라우저는 캐시된 복사본을 사용하여 요청을 만족시킨다. 

   2) 그러나 l이 캐시에 없는 경우 l에 대한 페이지는 인터넷을 통해 요청되고 캐시에 전송된다. 

3. 캐시에 있는 m개의 슬롯 중 하나가 사용 가능하면 브라우저는 빈 슬롯 중 하나에 l을 할당한다. 

4. 그러나 캐시의 m개의 셀이 모두 사용되고 있다면 

    컴퓨터는 l을 가져오기 전에 이전에 어떤 웹 페이지를 제거할지 결정해야 한다. 

    물론 제거할 페이지를 결정하는 데 사용될 수 있는 많은 다른 정책들이 있다.

페이지 교체 알고리즘

더 잘 알려진 페이지 교체 정책 중 일부는 다음과 같다(그림 14.5 참조):

• First+in, first+out(FIFO):

캐시에 가장 오래 있었던 페이지, 즉 과거에 캐시에 가장 멀리 전송되었던 페이지를 제거한다.

• 가장 최근에 사용(Least rercently used, LRU):

가장 최근에 마지막 요청이 발생한 페이지를 삭제한다.

또한 단순하고 순수하게 무작위적인 전략을 고려할 수 있다:

• 랜덤(Random): 캐시에서 삭제할 페이지를 랜덤으로 선택한다. 

그림 14.5: 랜덤, FIFO 및 LRU 페이지 교체 정책.

랜덤 전략의 특징

랜덤 또는 의사+랜덤 생성기만을 요구하기 때문에, 구현하기에 가장 쉬운 정책들 중 하나이다. 

이 정책을 구현하는데 수반되는 오버헤드: 페이지 교체 당 O(1)개의 추가적인 양의 연산

각각의 페이지 요청에 대한 추가적인 오버헤드가 없다. 

사용자의 브라우징이 나타내는 임의의 시간적 또는 공간적 지역성을 이용하려는 어떠한 시도도 없다.

FIFO 전략

-구현-

페이지들에 대한 참조들을 캐시에 저장하기 위해 

큐 Q 만을 필요로 하기 때문에 구현하기가 매우 간단하다. 

페이지들은 브라우저에 의해 참조될 때 Q로 큐잉되고, 그 다음 캐시에 불러온다. 

페이지가 퇴출되어야 할 필요가 있을 때, 

컴퓨터는 단순히 Q에 대해 디큐 동작을 수행하여 퇴출시킬 페이지를 결정한다. 

-특징-

페이지 당 O(1)개의 추가 연산을 요구한다.

페이지 요청에 대한 추가적인 오버헤드를 발생시키지 않는다. 

더욱이 시간적 지역성을 어느 정도 활용하려고 한다.

LRU 전략

-특징-

FIFO 전략보다 한 단계 더 나아가, 

LRU 전략은 가장 적게+최근에 사용된 페이지를 항상 제거함으로써 

시간적 로컬리티를 최대한 활용한다. 

정책적 관점에서는 이는 훌륭한 접근법이지만, 

구현의 관점에서는 비용이 많이 든다. 

즉, 시간적 및 공간적 로컬리티를 최적화하는 방법은 상당히 비용이 많이 든다. 

-구현-

예를 들어 특수 포인터 또는 "로케이터"를 사용하여 

기존 페이지 검색을 지원하는 우선순위 큐 Q를 사용해야 한다. 

Q가 연결 리스트을 기반으로 정렬된 시퀀스로 구현되면 

각 페이지 요청 및 페이지 교체에 대한 오버헤드: O(1)

Q에 페이지를 삽입하거나 키를 업데이트할 때 

페이지는 Q에서 가장 높은 키가 할당되고 리스트의 끝에 배치되며, 

이는 O(1) 시간에도 수행될 수 있다. 

LRU 전략에 일정한 시간 오버헤드가 있음에도 불구하고 위와 같은 구현을 사용하면 

추가 시간 오버헤드와 우선순위 큐 Q에 대한 추가 공간 측면에서 

관련된 일정한 요인이 정책의 매력을 떨어뜨린다.

페이지 교체 정책 간의 비교

구현 난이도와 지역성을 이용하는 것처럼 보이는 정도 사이에 

상이한 트레이드오프(trade-off)를 가지고 있기 때문에, 

어떤 것이 최선인지를 보기 위해서는 이러한 방법들에 대한 일종의 비교 분석을 요청하는 것이 당연하다.

최악의 경우에는

FIFO와 LRU 전략이 상당히 매력적이지 않은 경쟁 행위를 한다. 

예시) m개의 페이지를 포함하는 캐시가 있다고 가정하고, 

순환 순서로 m+1개의 페이지를 반복적으로 요청하는 루프를 갖는 프로그램에 대해 

페이지 교체를 수행하는 FIFO와 LRU 방법을 생각해 보자. 

FIFO와 LRU 정책은 그러한 일련의 페이지 요청에 대해 모두 좋지 않은 성능을 보이는데, 

그 이유는 모든 페이지 요청에 대해 페이지 교체를 수행하기 때문이다. 

따라서 최악의 경우에는 이러한 정책이 우리가 상상할 수 있는 최악의 경우가 대부분인데, 

모든 페이지 요청에 대해 페이지 교체를 필요로 하기 때문이다.

그러나 이 최악의 경우 분석은 

페이지 요청의 하나의 잘못된 시퀀스에 대한 각 프로토콜의 동작에 초점을 맞추기 때문에 다소 비관적이다. 

이상적인 분석은 가능한 모든 페이지 요청 시퀀스에 대해 이들 방법을 비교하는 것이다. 

물론 이를 완전히 수행하는 것은 불가능하지만 

실제 프로그램에서 파생된 페이지 요청 시퀀스에 대해 많은 실험 시뮬레이션이 수행되었다. 

이러한 실험적 비교를 바탕으로 LRU 전략은 대개 FIFO 전략보다 우수한 것으로 나타났다.

14.3 외부 탐색 및 B-트리

메인 메모리에 맞지 않는 많은 양의 항목에 대한 딕셔너리를 구현하는 문제를 고려해 보자.

큰 딕셔너리의 주된 용도 중 하나가 데이터베이스에 있으므로 

디스크 블록: 보조 기억장치 블록

디스크 전송: 보조 기억장치와 주 기억장치 사이에 블록이 전송되는 것

 

주 메모리 접근과 디스크 접근 사이에 존재하는 큰 시간 차이를 상기시키면서 

외부 메모리에서 딕셔너리를 유지하는 주된 목표 

쿼리나 업데이트를 수행하는 데 필요한 디스크 전송 수를 최소화하기

사실 디스크와 내장 메모리 사이의 속도 차이가 너무 커서 디스크 전송을 몇 번 피할 수 있다면 

상당한 수의 내장 메모리 접근을 기꺼이 수행해야 한다. 

 

알고리즘의 입출력 복잡도:

표준 딕셔너리 검색 및 업데이트 연산을 수행하는 데 

각각 필요한 디스크 전송 수를 세어 딕셔너리 구현의 성능을 분석

일부 비효율적인 외장 메모리 딕셔너리

n개의 원소를 저장하기 위해 리스트를 사용하는 간단한 딕셔너리 구현

 

리스트가 정렬되지 않은 이중 연결 리스트로 구현된 경우 

삽입과 제거는 각각 O(1)개의 전송으로 수행할 수 있지만,

제거 및 검색은 수행하는 각 링크 홉이 다른 블록에 접근할 수 있기 때문에 최악의 경우 전송을 필요로 한다.

이 검색 시간을 O(n/B) 전송으로 개선할 수 있는데, 여전히 성능이 떨어진다.

(B: 리스트에서 블록에 들어갈 수 있는 노드의 수)

 

정렬된 배열을 사용하여 시퀀스를 교대로 구현된 경우

검색은 이진 검색을 통해 O(log2n) 전송을 수행한다.

그러나 이 솔루션은 삽입 또는 제거 연산을 수행하기 위해 <cr>(n/B) 전송이 필요한데, 

최악의 경우 요소를 위 또는 아래로 이동하기 위해 모든 블록에 접근해야 할 수도 있다. 

 

따라서 리스트 기반 딕셔너리 구현은 외부 메모리에서 효율적이지 못하다.

 

로그 시간 내부 메모리 전략
이러한 간단한 구현들은 I/O 비효율적이기 때문에, 

균형 잡힌 이진 트리(ex. AVL 트리 또는 레드-블랙 트리) 또는 

로그 평균 케이스 쿼리 및 업데이트 시간(ex. 스킵 리스트 또는 스플레이 트리)을 갖는 

다른 검색 구조를 사용하는 로그 시간 내부 메모리 전략을 고려해야 한다. 

이러한 메소드들은 딕셔너리 항목들을 이진 트리의 노드 또는 그래프의 노드에 저장한다. 

일반적으로, 이러한 구조들 중 하나에서 쿼리 또는 업데이트를 위해 

엑세스되는 각각의 노드는 다른 블록에 있을 것이다. 

따라서, 이러한 메소드들은 모두 쿼리 또는 업데이트 연산을 수행하기 위해 

최악의 경우 O(log2n) 전송을 필요로 한다. 

특히, O(logB n) = O(logn/logB) 전송만을 사용하여 딕셔너리 쿼리 및 업데이트를 수행할 수 있다.

14.3.1 (a,b) 트리

검색을 위한 내부-메모리 접근과 외부-메모리 접근 간의 성능 차이의 중요성을 줄이기 위해, 

다원 탐색 트리를 사용하여 딕셔너리를 나타낼 수 있다(섹션 10.4.1).

이 방법은 (a,b) 트리로 알려진 (2,4) 트리 자료 구조의 일반화를 야기한다.

(a, b) 트리는 각 노드가 a와 b 자식 사이에 있고 

a - 1과 b - 1 엔트리 사이에 저장되는 다원 탐색 트리이다. 

(a, b) 트리에서 엔트리를 검색, 삽입 및 제거하는 알고리즘은 (2,4) 트리에 대해 해당하는 간단한 일반화이다. 

 

(2,4) 트리를 (a,b) 트리로 일반화하는 것의 장점 

- 일반화된 클래스의 트리가 유연한 검색 구조를 제공한다.

  (노드의 크기와 다양한 딕셔너리 연산의 실행 시간은 매개변수 a와 b에 따라 달라진다.) 

- 매개변수 a와 b를 디스크 블록의 크기에 대해 적절하게 설정함으로써 

  우수한 외부 메모리 성능을 달성하는 데이터 구조를 도출할 수 있다.

(a,b) 트리의 정의

(a,b) 트리는

(2 ≤ a ≤ (b + 1)/2를 만족하는 정수 a, b)
다음과 같은 추가 제한이 있는 다원 탐색 트리 T이다:

크기 속성: 각 내부 노드는 루트가 아닌 한 적어도 자식을 가지며, 최대 b개의 자식을 가진다.

깊이 속성: 모든 외부 노드의 깊이가 동일하다.

명제 14.1: n개의 엔트리를 저장하는 (a, b) 트리의 높이: (log n/log b)와 O(log n/log a)

정당화: 

T: n개의 원소를 저장하는 (a, b) 트리

h: T의 높이

h에 대하여 다음과 같은 경계를 설정함으로써 명제를 정당화한다:

크기 및 깊이 특성에 의해, T의 외부 노드의 수 n''은 적어도 2a^(h-1)이고, 최대 b^h이다. 

명제 10.7에 의해, n'' = n + 1. 따라서 2a^(h-1) ≤ n+1 ≤ b^h.

각 항의 밑 2에 로그를 취하면 (h - 1)log a + 1 ≤ log (n + 1) ≤ hlog b를 얻는다.

탐색 및 업데이트 연산

다원 탐색 트리 T에서, 

T의 각 노드 v는 그 자체로 딕셔너리인 2차 구조 D(v)를 가지고 있음을 기억한다(10.4.1절). 

만약 T가 (a, b) 트리라면, D(v)는 최대 b개의 엔트리를 저장한다. 

f(b): D(v) 딕셔너리에서 검색을 수행하는 시간

(a, b) 트리의 검색 알고리즘은 10.4.1절의 다원 탐색 트리의 검색 알고리즘과 정확히 같다. 

따라서 (a, b) 트리 T에서 n개의 엔트리를 가진 탐색 시간: O(f(b)/logogn)

만약 b가 상수이면(따라서 a도 마찬가지임), 탐색 시간: O(logn)

(a, b) 트리의 주된 응용

- 외부 메모리에 저장된 딕셔너리

- 즉, 디스크 접근을 최소화하기 위해 매개변수 a와 b를 선택하여 

  각 트리 노드가 하나의 디스크 블록을 차지하도록 한다

  (단순히 블록 전송을 세고 싶다면 f(b) = 1이 되도록 한다). 

- 여기서 올바른 a와 b 값을 제공하면 B-트리라고 불리는 자료 구조가 생성되며, 

   이 구조는 간단히 설명할 것이다. 

그러나 이 구조를 설명하기 전에 (a, b) 트리에서 삽입과 제거가 어떻게 처리되는지 논의해 보자.

(a, b) 트리의 삽입 알고리즘은 (2, 4) 트리의 삽입 알고리즘과 유사하다. 

b-노드 v에 엔트리가 삽입되면 오버플로우가 발생하며, 이는 불법 (b + 1)-노드가 된다. 

(다방향 트리의 한 노드가 d개의 자식을 가진 경우 d-노드임을 상기한다.) 

오버플로우를 해결하기 위해 v의 중위 엔트리를 v의 부모로 이동시키고 

v를 (b + l)/2 노드 v' 및 (b + 1)/2노드 v'로 대체하여 노드 v를 분할하였다. 

이제 (a, b) 트리의 정의에서 a ≤ (b + 1)/2 를 요구하는 이유를 알 수 있다. 

분할의 결과로, 2차 구조 D(v')와 D(v'')를 구축해야 한다.

(a, b) 트리에서 항목을 제거하는 것은 (2,4) 트리에 대해 수행된 것과 유사하다. 

언더플로우는 루트와 구별되는 a-노드 v에서 키를 제거할 때 발생하며, 이로 인해 v는 불법 (a - 1)-노드가 된다. 

언더플로우를 해결하기 위해, a-노드가 아닌 v의 형제와 전송을 수행하거나 a-노드인 형제와 v의 융합을 수행한다. 

융합으로 인한 새로운 노드 w는 (2a - 1)-노드이므로 a≤(b + 1)/2가 필요한 또 다른 이유이다.

표 14.1은 (a, b) 트리로 구현된 딕셔너리의 성능을 보여준다.
표 14.1: (a,b) 트리 T에 의해 실현되는 n-엔트리 딕셔너리의 시간 한계. 

T의 노드들의 2차 구조의 검색 시간: f(b)

일부 함수에 대해서는 g(b) 시간으로 분할 및 융합 연산을 지원한다고 가정하는데, 

디스크 전송만을 세고 있을 때 O(1)이 될 수 있다.

14.3.2 B-트리

B-트리: 외부 메모리에 딕셔너리를 유지하는 가장 잘 알려진 방법인 (a, b) 트리 자료 구조의 버전

(그림 14.6 참조)

순서 d의 B-트리: a=d/2이고 b=d인 (a,b) 트리

위의 (a,b) 트리에 대한 표준 딕셔너리 쿼리와 업데이트 메소드에 대해 논의했으므로 

여기서는 B-트리의 I/O 복잡도로 논의를 제한한다.

그림 14.6: 순서 6의 B-트리.

 

B-트리의 중요한 특성

d개의 자식 참조와 노드에 저장된 d-1개의 키가 모두 하나의 디스크 블록에 들어갈 수 있도록 선택할 수 있다

= d가 B에 비례한다

이 선택을 통해 (a, b) 트리에 대한 검색과 업데이트 연산을 분석할 때 

a와 b도 B에 비례한다고 가정할 수 있다. 

→ f(b)와 g(b)는 모두 O(1)이므로, 

검색이나 업데이트 연산을 수행하기 위해 노드에 접근할 때마다 디스크 전송을 한 번만 수행하면 된다.

위에서 이미 관찰한 바와 같이, 

각 검색이나 업데이트는 트리의 각 레벨에 대해 최대 O(1)개의 노드를 검사할 것을 요구한다. 

→ B-트리에 대한 모든 딕셔너리 검색이나 업데이트 연산은 O(log (d/2) n), 

    즉 O(log n / log B) 디스크 전송만을 요구한다. 

예) 삽입 연산은 B-트리 아래로 진행하여 새로운 엔트리를 삽입할 노드를 찾는다. 

 

만약 이 추가로 인해 노드가 오버플로우(d + 1개의 자식을 가지는) 경우, 

이 노드는 각각 (d + 1)/2와 (d + l)/2개의 자식을 가지는 두 노드로 분할된다. 

이 과정은 다음 레벨 업에서 반복되며, 대부분의 O(logB n) 레벨에서 계속된다.

 

마찬가지로 제거 연산으로 노드 언더플로우가 발생하면(d/2 – 1개의 자식이 있어야 함), 

적어도 d/2 + 1개의 자식이 있는 형제 노드에서 참조를 이동하거나 

형제 노드와 이 노드의 융합 연산을 수행해야 한다

(그리고 부모에서 이 계산을 반복해야 함). 

이 연산은 최대 O(logB n) 수준에서 B-트리를 계속 수행한다. 

 

각 내부 노드에 적어도 <en>d/2<bn> 자식이 있어야 한다는 요구 사항은 

B-트리를 지원하는 데 사용되는 각 디스크 블록이 적어도 절반 이상 채워짐을 의미한다. 

따라서 다음을 얻는다:

제안 14.2: n개의 엔트리를 가진 B-트리는

검색 또는 업데이트 연산을 위해 입출력 복잡도 O(logBn)를 가지며, O(n/B) 블록을 사용한다.

(B: 블록의 크기)

 

14.4 외부 메모리 정렬

외부 메모리에 구현해야 하는 자료 구조, 

예를 들어 딕셔너리와 같이

너무 커서 내부 메모리에 완전히 들어가지 못하는 입력 집합에서도 

동작해야 하는 알고리즘들이 많다. 

이 경우에는 가능한 한 적은 수의 블록 전송을 사용하여 알고리즘 문제를 해결하는 것이 목적이다. 

이러한 외부 메모리 알고리즘의 가장 고전적인 영역은 정렬 문제이다.

다중방향 병합-정렬

외부 메모리에서 n개의 객체로 이루어진 집합 S를 정렬하는 효율적인 방법

익숙한 병합 정렬 알고리즘에서 단순한 외부 메모리 변형에 해당한다. 

 

외부 메모리 변형의 주된 아이디어

한 번에 많은 재귀적으로 정렬된 리스트를 병합하여 재귀의 레벨 수를 줄이는 것이다. 

 

구체적인 다중 방식 병합 정렬 방법

1. S를 대략 동일한 크기의 d개의 부분집합 S1, S2, ..., Sd로 나눈다.

2. 각 부분집합 Si를 재귀적으로 정렬한다.

3. 모든 d개의 정렬된 리스트를 동시에 S의 정렬된 표현으로 병합하는 것이다. 

 

만약 O(n/B)개의 디스크 전송만을 사용하여 병합 과정을 수행할 수 있다면,

n의 값이 충분히 큰 경우, 이 알고리즘에 의해 수행된 총 전송 수는 다음과 같다:
어떤 상수 c ≥ 1에 대하여, t(n) = d · t(n/d) + cn/B이다. 

 

n ≤ B일 때, 모든 객체를 내부 메모리로 가져가서, 

효율적인 내부 메모리 알고리즘으로 집합을 정렬할 수 있으므로, 재귀를 중지할 수 있다. 

따라서 n/B ≤ 1이면 t(n)의 중지 기준은 t(n) = 1이다.
이는 t(n)이 O((n/B) logd (n/B)) = O(n/B) log (n/B) / log d)라는 폐쇄형 해를 의미한다.

따라서, 만약 d를 <cr>(M/B)로 선택할 수 있다면, 

이 다중방향 병합 정렬 알고리즘에 의해 수행되는 블록 전송의 최악의 경우 수는 상당히 적어질 것이다. 

 d = (1/2)M/B를 선택했다.

이 알고리즘의 유일한 측면은 O(n/B) 블록 전송만을 사용하여 d-way 병합을 수행하는 방법이다. 

14.4.1 다자간 병합

"토너먼트"를 실행함으로써 d-way 병합을 수행한다. 

T: d개의 외부 노드를 갖는 완전 이진 트리, 내부 메모리에 완전히 존재

 

1. T의 각 외부 노드 i를 다른 정렬된 리스트 Si와 연결시킨다.

    Si의 첫 번째 객체인 각 외부 노드 i로 읽음으로써 T를 초기화한다.

    이것은 정렬된 각 리스트 Si의 첫 번째 블록을 내부 메모리로 읽는 효과를 가진다. 

2. 두 외부 노드의 각 내부 노드 부모 v에 대하여, 

    v의 자식들에 저장된 객체들을 비교하고 둘 중 작은 것을 v와 연결한다. 

3. 이 비교 테스트를 T의 다음 레벨에서 반복하고, 다음 레벨에서 반복한다. 

4. T의 루트 r에 도달하면, 모든 리스트 중에서 가장 작은 객체를 r과 연결한다. 

5. 이것으로 d-way 병합을 위한 초기화가 완료된다. (그림 14.7 참조)

그림 14.7: d-way 병합. B = 4인 5-way 병합을 보여준다.

d-way 병합의 일반적인 단계

1. T의 루트 r과 연관된 객체 o를 병합된 리스트 S'를 위해 만들 배열로 이동시킨다. 

2. o가 나온 외부 노드 i의 경로를 따라 T를 추적한다. 

3. 리스트 Si의 다음 객체 i를 읽는다. 

    1) o가 블록의 마지막 요소가 아니라면, 이 다음 객체는 이미 내부 메모리에 있다. 

    2) 그렇지 않으면, 이 새로운 객체에 접근하기 위해 Si의 다음 블록에서 읽는다

       (Si가 지금 비어 있다면, 노드 i를 키 + ∞를 가진 의사 객체와 연결하라). 

4. i부터 T의 루트까지 각 내부 노드에 대한 최소 계산을 반복한다. 

    이것은 다시 완전한 트리 T를 제공한다. 

5. T의 루트에서 병합된 리스트 S'로 객체를 이동시키고 T를 재구축하는 이 과정을 

    T가 객체들이 비울 때까지 반복한다. 

 

병합의 각 단계:  O(log d) 시간 → d-way 병합의 내부 시간: O(nlogd)

각 리스트 Si를 한 번씩 순서대로 스캔하고, 병합된 리스트 S'를 한 번 쓰기 때문에, 

→ 병합에서 수행되는 전송 횟수: O(n/B)

따라서, 다음과 같다:

제안 14.3: 

외부 메모리에 저장된 n개 원소의 배열 기반 시퀀스 S가 주어지면 

O((n/B) log(n/B) / log(M/B)) 전송과 O(n log n) 내부 CPU 시간을 사용하여 S를 정렬할 수 있다.

(M: 내부 메모리의 크기, B: 블록의 크기)