Smalltalk80LanguageImplementationKor:Chapter 30
- 제 30 장 객체 메모리의 형식적 명세
객체 메모리의 형식적 명세
TSmalltalk-80 구현의 두 가지 중요한 구성요소는 바이트코드 인터프리터와 객체 메모리이다. 제 28장과 29장에서는 바이트코드 인터프리터의 구현을 설명하였다. 이번 장에서는 객체 메모리의 구현을 설명하고자 한다. 객체 메모리는 객체를 생성, 저장, 파괴하고 그 필드로 접근성을 제공하는 기능을 한다.
메모리 관리 시스템은 두 가지 주요 범주, "real-memory"(실제 메모리) 구현과 "virtual-memory"(가상 메모리) 구현으로 나뉜다. 실제 메모리 구현에서는 환경 내 모든 객체가 일차 메모리에 거주하여 프로그램에서 직접 주소를 지정할 수 있다. 가상 메모리 구현에서는 객체가 메모리 계층구조의 하나 이상의 수준에 거주하고 실행 도중에 다양한 수준으로 움직일 수 있다. 이번 장에서는 실제 메모리 Smalltalk-80에 대한 객체 메모리, RealObjectMemory의 디자인을 설명한다.
Smalltalk는 어떤 워드 크기의 컴퓨터에서든 구현할 수 있지만 이 표현은 표준 알고리즘 내에서 몇 가지 가정으로 단순화될 것이다. RealObjectMemory의 루틴에서는 다음을 가정한다.
- 바이트에 8 비트가 있고,
- 워드에 2 바이트가 있고,
- 워드의 상위 바이트가 하위 바이트보다 우선하고,
- 목표 컴퓨터는 워드로 주소가 지정되고(word addressed) 워드로 색인된다(word indexed).
또한 루틴은 주소 공간이 각각 64K(65,536) 워드로 된 16개 이하의 "segments"(세그먼트)로 분할되어 있다고 가정한다. 표준 알고리즘을 시스템적으로 변경하여 여러 속성으로 된 하드웨어에 조정할 수 있다. RealObjectMemory의 루틴은 기계어 구현과 마찬가지로 거의 16-bit 정수만 처리한다.
기계어 구현은 호스트 머신의 주소 공간에 있는 위치로 접근하기 위해 명령을 로딩하고 저장한다. RealObjectMemory에서 로드 및 저장 명령어는 wordMemory라는 이름을 가진 RealWordMemory의 인스턴스로 전송되는 메시지로 상징된다. RealWordMemory의 프로토콜은 아래 표시하겠다.
| RealWordMemory 인스턴스 프로토콜 | |
| segment: s word: w | 세그먼트 s의 워드 w를 리턴한다. |
| segment: s word : put: value | 세그먼트 s의 워드 w로 value를 저장하고 value를 리턴한다. |
| segment: s word: w byte: byteNumber | 세그먼트 s의 워드 w의 바이트 byteNumber를 리턴한다. |
| segment: s word: w byte: byteNumber put: value | 세그먼트 s의 워드 w의 바이트 byteNumber에 value를 저장하고 value를 리턴한다. |
| segment: s word: w bits: firstBitIndex to: lastBitIndex | 세그먼트 s의 워드 w의 비트 firstBitIndex부터 lastBitIndex까지 리턴한다. |
| segment: s word: w bits: firstBitIndex to: lastBitIndex put: value | value를 세그먼트 s의 워드 w의 비트 firstBitIndex부터 lastBitIndex까지 저장하고 value를 리턴한다. |
워드의 두 바이트를 구별하기가 불가피해지면 좌측 (상위) 바이트는 색인 0으로 참조되고 우측 (하위) 바이트는 색인 1로 참조될 것이다. 워드에서 최상위 비트는 색인 0으로 참조되고 최하위 비트는 색인 15로 참조될 것이다. self는 본 장의 모든 루틴에서 RealObjectMemory 클래스의 인스턴스에 해당함을 주목한다.
객체 메모리의 어떠한 구현이든 제 27장에 제공된 객체 메모리 인터페이스의 기능적 명세를 준수하는 것이 가장 중요하다. 이번 장에서는 그러한 인터페이스의 다양한 구현을 설명하겠다. 특히 일부 루틴의 간단한 버전을 앞부분에 소개하고 좀 더 정교한 버전은 그러한 세부적인 부분을 더 분명하게 할 필요가 있을 때 후에 소개하겠다. 이러한 예비 버전은 루틴의 첫 번째 줄에 "**Preliminary Version**"이란 주석을 달아 표기할 것이다.
힙 저장공간(Heap Storage)
Smalltalk의 실제 메모리 구현에서 모든 객체는 "heap"(힙)이라 불리는 영역에 저장된다. 힙의 연속된 워드에 필드를 저장할 공간을 얻으면 새로운 객체가 생성된다. 객체가 차지하는 힙 공간을 해제하면 객체가 소멸된다. 힙에서 할당된 객체의 포맷은 그림 30.1에 표시되어 있다. 객체의 실제 데이터 앞에는 2 워드로 된 "header"(헤더)가 따라온다. 헤더의 크기 필드는 헤더를 포함해 객체가 차지하는 힙의 워드 개수를 나타낸다. 이는 부호가 없는 16 비트 숫자로, 2부터 65,536까지 범위가 가능하다.
메모리가 단편화되면 Smalltalk-80 구현은 주로 힙을 "heap segments"(힙 세그먼트)로, 각각 다른 메모리 세그먼트로 나누는 편이 효율적이다. 앞서 언급하였듯 이번 장에 실린 루틴에서는 목표 컴퓨터가 65,536 워드의 주소 공간으로 단편화된 것으로 간주한다.
| HeapSegmentCount | 구현에 사용된 힙 세그먼트의 개수. |
| FirstHeapSegment | 힙을 저장하는 데 사용된 첫 번째 메모리 세그먼트의 색인. |
| LastHeapSegment | 힙을 저장하는 데 사용된 마지막 메모리 세그먼트의 색인 (FirstHeapSegment + HeapSegmentCount - 1). |
| HeapSpaceStop | 각 힙 세그먼트에 사용된 마지막 위치의 주소. |
| HeaderSize | 객체 헤더(2) 내 워드의 개수. |
| 힙과 연관된 상수 | |
집약(Compaction)
힙에서 한 번 할당된 객체는 그 위치를 절대 변경하지 않는다고 가정해보자. 새로운 객체를 할당하기 위해서는 기존의 객체들 간 공간이 새로운 객체를 수용할만큼 충분히 큰지 확인해야 한다. 잠시 후 메모리는 "fragment"(단편화)되거나 "checkerboard"(체커보드)된다. 즉, 총 이용 가능한 메모리보다는 작지만 각 분리된 조각보다는 큰 공간에 할당 요청이 도착하도록 되어 있다 (그림 30.2a). 이용 가능한 공간이 크고 할당 요청이 상대적으로 작은 경우에도 발생할 수 있다.
재초기화 없이 수 백시간 이상 동적인 환경을 유지할 것으로 기대되는 대화형 시스템에서는 단편화를 허용할 수 없다. 따라서 메모리를 단편화하려면 "compacted"(집약)되어야 한다. 메모리는 사용 중인 모든 객체를 힙의 한쪽 끝을 향해 이동시키고 그 사이에 있는 모든 빈 공간을 짜내어 다른 끝에 할당되지 않은 하나의 큰 블록을 남겨둠으로써 집약된다 (그림 30.2b 참고).
각각의 힙 세그먼트는 구분되어 집약된다. 선형적으로 주소가 지정된 머신에서조차 각 집약 기간을 줄이기 위해 큰 힙을 단편화하는 방법이 선호된다.
객체 테이블(The Object Table)
집약 중에 객체가 이동하면 그 힙 메모리에 대한 모든 포인터는 업데이트되어야 한다. 그 외 다수의 객체가 기존의 위치를 직접적으로 가리키는 포인터를 포함할 경우, 순차 처리 컴퓨터에서 새로운 위치를 가리키는 참조를 찾고 업데이트하는 데에는 엄청난 시간이 소요된다. 따라서 포인터를 업데이트하는 수고를 덜기 위해 객체의 힙 메모리에 대해 하나의 포인터만 허용한다. 그 포인터는 "object table"(객체 테이블)이라 불리는 테이블에 저장된다. 객체에 대한 모든 참조는 객체 테이블을 통해 우회(indirect)해야 한다. 따라서 Smalltalk 객체에서 발견되는 객체 포인터는 객체 테이블 내의 실제 색인으로, 힙으로 들어가는 포인터가 발견된다 (그림 30.3).
객체 테이블을 통해 우회(indirection)할 경우 또 다른 장점이 있다. n-bit 포인터가 주소를 지정할 수 있는 평균 Z 크기의 객체 개수는 2n/Z가 아니라 대략적으로 2n 에 해당한다. 경험상 객체는 평균 크기가 10 워드이므로 (Z~10) 주소 공간이 크기 증가하면 우회를 통해 실현할 수 있다.
객체 테이블에서는 힙의 어떠한 공간과도 연관되지 않은 버려진(abandoned) 엔트리가 발생할 수 있다. 이러한 엔트리를 "free entries"(빈 엔트리)라고 부르고, 그 객체 포인터를 "free pointers"(빈 포인터)라고 부른다. 모든 객체 테이블 엔트리는 크기가 동일하므로 빈 엔트리를 재활용하기가 쉽다. 객체 테이블의 집약은 까다로우면서 일반적으로 불필요하므로 지원되지 않는다.
힙이 단편화된다 하더라도 객체 테이블은 단일 세그먼트에 저장되어 객체 포인터는 16 bits가 될 수 있고 그에 따라 1 워드에 일치할 수 있다. 따라서 실제 메모리에 주소 지정이 가능한 객체의 개수는 하나의 세그먼트에 맞는 객체 테이블 엔트리 개수로 제한된다. 각 객체 테이블 엔트리가 2 워드를 차지하고 전체 테이블이 64K 워드 이하를 차지하여 최대 32K 객체를 수용하도록 하는 것이 공통된 배열이다.
객체 포인터(Object Pointers)
객체 포인터는 16 비트를 차지하고 그림 30.4와 같이 배분된다.
객체 포인터의 최하위 비트가 0이면 첫 15 비트는 객체 테이블로 들어가는 색인이다. 215(32K) 객체까지는 주소지정이 가능하다. 객체 포인터의 최하위 비트가 1일 경우 첫 15 비트는 근접한 부호가 있는 정수이고, 객체 테이블이나 힙에 추가 공간을 사용하지 않는다. ±214 범위의 정수를 특별히 취급할 경우 산술이나 다른 많은 연산 시 높은 빈도수로 왔다 갔다 한다는 장점이 있다. 이러한 효율적인 표현 대신에 인터프리터가 작은 정수의 객체 포인터를 다른 객체의 객체 포인터로부터 구별하기 위해 실행해야 하는 수많은 검사는 감수해야만 한다.
isIntegerObject: 루틴은 아머지 포인터가 객체 테이블 색인보다는 근접한 정수 값인지 결정하기 위해 objectPointer의 하위 비트를 검사한다.
isIntegerObject: objectPointer
↑(objectPointer bitAnd: 1) = 1
그 외 다른 모든 객체-접근 루틴은 그 객체 포인터 인자가 사실상 객체 테이블 색인이 되도록 요구한다. cantBeIntegerObject: 루틴은 오류가 있는 호출을 가두는 데 사용된다. 하드웨어, 바이트코드 인터프리터, 객체 메모리 관리자에 버그가 없을 경우 오류 상태는 절대 접하지 않는다.
cantBeIntegerObject: objectPointer
(self isIntegerObject: objectPointer)
ifTrue: [Sensor notify: 'A small integer has no object table entry']
객체 테이블 엔트리(Object Table Entries)
객체 테이블 엔트리의 포맷은 그림 30.5에 표시되어 있다. 빈 엔트리 비트가 켜져 있으면 엔트리는 비어 있다(free). 빈 엔트리 비트가 꺼지면 세그먼트 4 비트는 힙 세그먼트를 선택하고 16의 위치 비트는 객체 테이블 엔트리가 소유한 해당 세그먼트에서 공간의 시작을 위치시킨다. 계수 필드, 홀수 길이 비트(O), 포인터 필드 비트는 이번 장의 뒷부분에서 설명하겠다.
| ObjectTableSegment | 객체 테이블을 포함하는 메모리 세그먼트의 개수. |
| ObjectTableStart | objectTableSegment에서 객체 테이블의 base의 위치. |
| ObjectTableSize | 객체 테이블에서 워드의 개수 (짝수 ≤ 64K). |
| HugeSize | 8-bit 계수 필드에 표현하기엔 너무 큰 숫자 중에서 최소수, 즉 256. |
| NilPointer | 객체 nil의 객체 테이블 색인. |
| Object Table Related Constants | |
다음의 루틴 집합은 각기 다른 방식으로, 즉 전체 워드를 로딩하거나, 전체 워드를 저장하거나, 비트 필드를 로딩하거나, 비트 필드를 저장하는 방식으로 객체 테이블 엔트리의 첫 번째 워드로 접근한다. 그리고 이러한 루틴들은 RealWordMemory의 인스턴스인 wordMemory의 루틴을 활용한다. 이는 objectPointer가 세그먼트 objectTableSegment 내 객체 테이블의 base인 objectTableStart를 기준으로 한 짝수 워드 오프셋으로 표현된다고 가정한다. ot는 "object table"의 줄임말이다.
ot: objectPointer
self cantBeIntegerObject: objectPointer.
↑wordMemory segment: ObjectTableSegment
word: ObjectTableStart + objectPointer
ot: objectPointer put: value
self cantBeIntegerObject: objectPointer
↑wordMemory segment: ObjectTableSegment
word: ObjectTableStart + objectPointer
bits: firstBitIndex
to: lastBitIndex
ot: objectPointer bits: firstBitIndex to: lastBitIndex put: value
self cantBeIntegerObject: objectPointer.
↑wordMemory segment: ObjectTableSegment
word: ObjectTableStart + objectPointer
bits: firstBitIndex
to: lastBitIndex
put: value
다음 12개의 객체-접근 하위루틴은 objectPointer의 객체 테이블 엔트리의 다양한 필드를 로딩하거나 저장한다.
countBitsOf: objectPointer
↑self ot: objectPointer bits: 0 to: 7
countBitsOf: objectPointer put: value
↑self ot: objectPointer bits: 0 to: 7 put: value
oddBitOf: objectPointer
↑self ot: objectPointer bits: 8 to: 8
oddBitOf: objectPointer put: value
↑self ot: objectPointer bits: 8 to: 8 put: value
pointerBitOf: objectPointer
↑self ot: objectPointer bits: 9 to: 9
pointerBitOf: objectPointer put: value
↑self ot: objectPointer bits: 9 to: 9 put: value
freeBitOf: objectPointer
↑self ot: objectPointer bits: 10 to: 10
freeBitOf: objectPointer put: value
↑self ot: objectPointer bits: 10 to: 10 put: value
segmentBitsOf: objectPointer
↑self ot: objectPointer bits: 12 to: 15
segmentBitsOf: objectPointer put: value
↑self ot: objectPointer bits: 12 to: 15 put: value
locationBitsOf: objectPointer
self cantBeIntegerObject: objectPointer.
↑twordMemory segment: ObjectTableSegment
word: ObjectTableStart + objectPointer + 1
locationBitsOf: objectPointer put: value
self cantBeIntegerObject: objectPointer.
↑wordMemory segment: ObjectTableSegment
word: ObjectTableStart + objectPointer + 1
put: value
힙 저장공간의 청크를 차지하는 객체의 경우 (빈 비트가 0인) 다음 4개의 객체-접근 하위루틴은 그 청크로부터 워드나 바이트를 로딩 또는 저장한다.
heapChunkOf: objectPointer word: offet
↑wordMemory segment: (self segmentBitsOf: objectPointer)
word: ((self locationBitsOf: objectPointer) + offset)
heapChunkOf: objectPointer word: offset put: value
↑wordMemory segment: (self segmentBitsOf: objectPointer)
word: ((self locationBitsOf: objectPointer) + offset)
put: value
heapChunkOf: objectPointer byte: offset
↑wordMemory segment: (self segmentBitsOf: objectPointer)
word: ((self locationBitsOf: objectPointer) + (offset // 2))
byte: (offset \\ 2)
heapChunkOf: objectPointer byte: offset put: value
↑wordMemory segment: (self segmentBitsOf: objectPointer)
word: ((self locationBitsOf: objectPointer) + (offset // 2))
byte: (offset \\ 2) put: value
아래 4개의 객체-접근 하위루틴은 객체 헤더의 워드를 로딩하거나 저장하는 경우에 대해서 보다 특수화되어 있다.
sizeBitsOf: objectPointer
↑self heapChunkOf: objectPointer word: 0
sizeBitsOf: objectPointer put: value
↑self heapChunkOf: objectPointer word: 0 put: value
classBitsOf: objectPointer
↑self heapChunkOf: objectPointer word: 1
classBitsOf: objectPointer put: value
↑self heapChunkOf: objectPointer word: 1 put: value
나머지 두 개의 객체-접근 하위루틴은 기능적으로 아래 표시된 sizeBitsOf: 와 동일하다. 본 장 뒷부분에서 객체-메모리 관리자를 개선하여 이 두 개의 하위루틴의 새로운 버전을 필요로 하는데, 그 버전들은 특정 상황에서 객체 크기와 다른 무언가를 리턴할 것이다. 이러한 이유로 "preliminary(예비)"라고 표기한다.
lastPointerOf: objectPointer "**Preliminary Version**"
↑self sizeBitsOf: objectPointer
spaceOccupiedBy: objectPointer "**Preliminary Version**"
↑self sizeBitsOf: objectPointer
할당되지 않은 공간(Unallocated Space)
객체 테이블의 모든 빈 엔트리는 freePointerList로 명명된 위치를 향하는 연결 리스트에 보관된다. 하나의 빈 엔트리에서 다른 빈 엔트리까지 링크는 그 위치 필드에 있는 객체 포인터에 해당한다 (그림 30.6 참고).
힙에서 할당되지 않은 공간은 크기가 정렬된 "free chunks"(빈 청크; 연속 블록)로 그룹화되고 각각의 빈 청크에는 객체 테이블 엔트리가 할당된다. 빈 청크는 리스트에서 서로 연결되어 있고, 각각은 크기가 동일한 청크를 포함한다. 하나의 빈 청크에서 그 다음 빈 청크까지 링크는 해당하는 클래스 필드에 위치한다 (그림 30.7). 리스트 헤드의 테이블을 작게 유지하기 위해 20 워드가 넘는 프리 청크는 모두 하나의 리스트로 연결된다.
| FreePointerList | 빈 객체 테이블 엔트리의 연결 리스트 헤드의 위치. |
| BigSize | 청크 크기가 동일한 리스트에 저장되지 않은 청크의 최소 크기. (마지막 빈 청크 리스트의 색인.) |
| FirstFreeChunkList | 크기가 0인 빈 청크의 연결 리스트 헤드 위치. 크기가 큰 청크의 리스트는 FirstFreeChunkList 다음 연속된 위치에 저장된다. 모든 청크의 길이는 최소 2 워드이므로 FirstFreeChunkList와 FirstFreeChunkList+1에 있는 리스트는 항상 비어 있을 것이다. |
| LastFreeChunkList | BigSize 또는 그 이상의 크기로 된 빈 청크의 연결 리스트 헤드 위치. |
| NonPointer | 객체 테이블 색인이 될 수 없는 16-bit 값. 예: 216-1 |
| 빈 공간과 연관된 상수 | |
빈 청크 리스트의 집합은 각 힙 세그먼트마다 따로 유지되지만 객체 테이블에는 하나의 빈 포인터 리스트만 유지된다. "빈 청크"와 연관된 객체 테이블 엔트리는 "빈 엔트리"가 아니라는 사실을 주목한다. 이는 빈 포인터 리스트에 위치하지 않으며, 그것의 빈 엔트리 비트는 설정되어 있지 않다. 빈 청크를 할당된 청크로부터 구별하는 방법은, 빈 청크의 경우 객체 테이블 엔트리의 계수 필드를 0으로, 할당된 청크에는 0이 아닌 수로 설정하면 된다.
다음 4개의 루틴은 objectTableSegment 세그먼트 내 freePointerList를 향하는 빈 포인터 리스트를 관리한다. 처음 두 개의 루틴은 리스트 헤드를 단순히 로드하고 저장한다.
headOfFreePointerList
↑wordMemory segment: ObjectTableSegment
word: FreePointerList
headOfFreePointerListPut: objectPointer
↑wordMemory segment: ObjectTableSegment
word: FreePointerList
put: objectPointer
toFreePointerListAdd: 루틴은 리스트의 헤드에 빈 엔트리를 추가한다.
toFreePointerListAdd: objectPointer
self locationBitsOf: objectPointer
put: (self headOfFreePointerList)
self headOfFreePointerListPut: objectPointer
removeFromFreePointerList 루틴은 리스트로부터 첫 번째 엔트리를 제거하여 리턴하는데, 리스트가 비어 있었다면 nil을 리턴한다. 구별된 값 NonPointer는 연결 리스트의 끝을 나타낸다. NonPointer에 올바른 값은 216-1 으로, 이 값은 대부분의 컴퓨터에서 쉽게 감지되고 홀수기 때문에 실제 객체 테이블 엔트리 어드레스와 혼동되지 않는다.
removeFromFreePointerList
| objectPointer |
objectPointer ← self headOfFreePointerList.
objectPointer = NonPointer ifTrue: [↑nil].
self headOfFreePointerListPut: (self locationBitsOf: objectPointer).
↑objectPointer
다음 루틴들은 각 힙 세그먼트의 LastFreeChunkList를 거쳐 FirstFreeChunkList+2를 향하는 빈 청크 리스트를 관리한다. 이 루틴들의 행위는 위의 루틴들의 행위와 정확히 동일하다. 첫 세 개의 루틴은 두 번째 매개변수가 암시하거나 명시한 세그먼트에서 작동한다. 네 번째 루틴은 레지스터 currentSegment가 명시한 세그먼트에서 작동한다.
headOfFreeChunkList: size inSegment: segment
↑wordMemory segment: segment
word: FirstFreeChunkList + size
headOfFreeChunkList: size inSegment: segment put: objectPointer
↑wordMemory segment: segment
word: FirstFreeChunkList + size
put: objectPointer
toFreeChunkList: size add: objectPointer
| segment |
segment ← self segmentBitsOf: objectPointer.
self classBitsOf: objectPointer
put: (self headOfFreeChunkList: size inSegment: segment).
self headOfFreeChunkList: size
inSegment: segment
put: objectPointer
removeFromFreeChunkList: size
| objectPointer secondChunk |
objectPointer ← self headOfFreeChunkList: size
inSegment: currentSegment.
objectPointer = NonPointer ifTrue: [↑nil].
secondChunk ← self classBitsOf: objectPointer.
self headOfFreeChunkList: size
inSegment: currentSegment
put: secondChunk.
↑objectPointer
resetFreeChunkList:inSegment: 루틴은 명시된 빈 청크 리스트를 빈 리스트로 리셋한다.
resetFreeChunkList: size inSegment: segment
self headOfFreeChunkList: size
inSegment: segment
put: NonPointer
할당과 회수(Allocation and Deallocation)
객체를 할당하기 위해 객체 테이블로부터 엔트리를 얻고 일부 힙 세그먼트로부터 헤더와 데이터에 충분한 공간을 얻는다. 공간이 발견되는 힙 세그먼트는 "current segment"(현재 세그먼트)라고 부른다. 이는 다음 객체를 할당하기 위한 공간을 찾는 첫 번째 세그먼트가 된다. 객체 메모리가 필요로 하는 유일한 레지스터가 현재 세그먼트의 색인을 보유한다.
| currentSegment | 현재 할당에 사용 중인 힙 세그먼트의 색인. |
| 객체 메모리의 레지스터 | |
힙 공간의 n개 워드를 필요로 하는 "큰" 객체를 할당하기 위해서는(n>=BigSize), 현재 세그먼트 내 LastFreeChunkList에서 시작하는 리스트에서 크기가 n개 워드이거나 적어도 n+headerSize 워드인 빈 청크를 검색한다. 발견된 빈 청크가 n 워드보다 클 경우 "분할"되어 할당 요청을 충족하도록 n개의 워드만 사용된다.
힙 공간의 n개 워드를 필요로 하는 "작은" 객체를 할당하기 위해서는 (headerSize<=n<BigSize) freeChunkLists+n에서 시작되는 리스트가 검색된다. 리스트가 비어 있지 않으면 첫 번째 빈 청크가 제거되어 새 객체에 사용된다. 리스트가 비어 있다면 "큰" 객체에 대한 위의 알고리즘이 사용된다.
현재 세그먼트에서 크기가 충분한 청크가 발견되지 않으면 다음 세그먼트가 현재 세그먼트로 만들어져 검색이 계속된다. 새로운 현재 세그먼트가 먼저 집약되어 충분한 공간을 찾을 수 있는 기회를 향상시킨다. 집약된 세그먼트에서는 할당된 객체가 모두 한쪽 끝에 위치하고 다른 끝에 위치한 (예상컨대 큰) 공간에는 하나의 큰 청크, 즉 LastFreeChunkList 리스트의 유일한 멤버가 위치한다. 어느 세그먼트에서도 충분한 공간이 발견되지 않으면 실행이 중지된다.
객체가 회수되면 그 공간은 적절한 크기의 빈 청크 리스트에서 재활용된다. 하지만 표현의 단순화를 위해 본장에 실린 표준 알고리즘은 크기가 큰 빈 청크의 리스트에서 사용되지 않은 분할된 청크는 그 크기가 작더라도 그대로 남겨두었다.
할당 알고리즘(An Allocation Algorithm)
allocate:class: 루틴은 아래에 단순한 할당 루틴의 예로 제시되어 있다. 이 루틴은 바람직한 청크 크기와 (헤더까지 포함해 워드로) 그 청크가 표현하게 될 객체의 클래스를 매개변수로 취한다. 실제 할당 루틴은 몇 가지 다른 매개변수를 취하므로 allocate:class: 루틴은 예비(preliminary)로 표기될 것이다. 좀 더 완전한 루틴으로는 allocate:extra:class:이 있는데 이는 뒷부분에서 표현할 것이며, allocate:odd:pointer:extra:class: 구현에서 사용되는 실제 루틴을 그 다음에 제시하겠다.
allocate: size class: classPointer "**Preliminary Version**"
| object Pointer |
objectPointer ← self allocateChunk: size. "actually allocate"
self classBitsOf: objectPointer put: classPointer. "fill in class"
"initialize all fields to the object table index of the object nil"
(headerSize to: size - 1) do:
[ :i | self heapChunkOf: objectPointer word: i put: NilPointer].
self sizeBitsOf: objectPointer put: size.
"return the new object's pointer"
↑objectPointer
allocateChunk: 루틴은 할당 작업을 성공적으로 실행할 수 있고, 실패할 경우 회복할 수 없는 오류를 보고한다. 이는 하위루틴 attemptToAllocateChunk:을 이용해 작업을 완료하고, 공간이 발견되지 않으면 nil을 리턴한다.
allocateChunk: size "**Preliminary Version**"
| objectPointer |
objectPointer ← self attemptToAllocateChunk: size.
objectPointer isNil ifFalse: [↑objectPointer].
↑self error: 'Out of memory'
attemptToAllocateChunk: 루틴은 먼저 현재 할당을 목표로 한 세그먼트인 currentSegment에 할당을 시도한다. 이 때는 attemptToAllocateChunkInCurrentSegment: 하위루틴을 이용하여 이를 시도한다. 하위루틴이 실패하면 (nil을 리턴), 루틴은 다음 세그먼트를 집약하고 그곳에서 할당을 재시도한다. 이러한 절차는 원본 세그먼트가 집약되어 검색될 때까지 계속된다. 어디에서도 공간이 발견되지 않으면 루틴은 nil을 리턴한다. 이는 구현 의존적 상수 HeapSegmentCount, FirstHeapSegment, LastHeapSegment를 사용함을 주목한다.
attemptToAllocateChunk: size
| objectPointer |
objectPointer ← self attemptToAllocateChunkInCurrentSegment: size.
objectPointer isNil ifFalse: [↑objectPointer].
1 to: HeapSegmentCount do:
[ :i |
currentSegment ← currentSegment + 1.
currentSegment > LastHeapSegment
ifTrue: [currentSegment ← FirstHeapSegment].
self compactCurrentSegment.
objectPointer
← self attemptToAllocateChunkInCurrentSegment: size.
objectPointer isNil ifFalse: [↑objectPointer]].
↑nil
attemptToAllocateChunkInCurrentSegment: 루틴은 올바른 크기 또는 올바른 크기의 청크를 만들기 위해 분할 가능한 첫 번째 청크에 대한 현재 힙 세그먼트의 빈 청크 리스트를 검색한다. 대부분의 객체는 BigSize보다 크기가 작고, 대부분의 할당 요청은 원하는 크기로 회수된 객체를 재활용하여 충족시킬 수 있으므로 대부분의 할당은 루틴의 첫 네 줄만 실행한다.
attemptToAllocateChunkInCurrentSegment: size
| objectPointer predecessor next availableSize excessSize newPointer |
size < BigSize
ifTrue: [objectPointer ← self removeFromFreeChunkList: size].
objectPointer notNil
ifTrue: [↑objectPointer]. "small chunk of exact size handy so use it"
predecessor ← NonPointer.
"remember predecessor of chunk under consideration"
objectPointer ← self headOfFreeChunkList: LastFreeChunkList
inSegment: currentSegment.
"the search loop stops when the end of the linked list is encountered"
[objectPointer = NonPointer] whileFalse:
[availableSize ← self sizeBitsOf: objectPointer.
availableSize = size
ifTrue: "exact fit --remove from free chunk list and return"
[next ← self classBitsOf: objectPointer.
"the link to the next chunk"
predecessor = Non Pointer
ifTrue: "it was the head of the list; make the next item the head "
[self headOfFreeChunkList: LastFreeChunkList
inSegment: currentSegment put: next]
ifFalse: "it was between two chunks; link them together"
[self classBitsOf: predecessor
put: next].
↑objectPointer].
"this chunk was either too big or too small; inspect the amount of variance "
excessSize ← availableSize-size.
excessSize > = HeaderSize
ifTrue: "can be broken into two usable parts: return the second part"
["obtain an object table entry for the second part"
newPointer ← self obtainPointer: size
location: (self locationBitsOf: objectPointer)
+ excessSize.
newPointer isNil ifTrue: [↑nii].
"correct the size of the first part (which remains on the free list)"
self sizeBitsOf: objectPointer put: excessSize.
↑newPointer]
ifFalse: "not big enough to use; try the next chunk on the list"
[predecessor ← objectPointer.
objectPointer ← self classBitsOf: objectPointer]].
↑nil "the end of the linked list was reached and no fit was found"
위의 루틴이 사용한 obtainPointer:location: 하위루틴은 빈 객체 테이블 엔트리를 얻고, 엔트리의 첫 번째 워드에서 나머지를 비롯해 빈 엔트리 비트를 0으로 만들고(zeroes), 명시된 위치에서 엔트리를 가리키며, 헤더의 크기 필드를 명시된 크기로 설정한다.
obtainPointer: size location: location
| objectPointer |
objectPointer ← self removeFromFreePointerList.
objectPointer isNil ifTrue: [↑nil].
self ot: objectPointer put: 0.
self segmentBitsOf: objectPointer put: currentSegment.
self locationBitsOf: objectPointer put: location.
self sizeBitsOf: objectPointer put: size.
↑objectPointer
회수 알고리즘(A Deallocation Algorithm)
객체의 할당에 비하면 회수는 매우 간단하다. 청크는 빈 청크 리스트에서 재활용된다. 다음 루틴은 상위 루틴이 계수 필드를 0으로 리셋할 것이라고 예상한다.
deallocate: objectPointer "**Preliminary Version**"
| space |
space ← self spaceOccupiedBy: objectPointer.
self toFreeChunkList: (space min: BigSize)
add: objectPointer
이 루틴은 sizeBitsOf: 대신 spaceOccupiedBy:을 이용해 객체가 차지한 공간을 계산한다는 사실을 주목하자. 이유는 본장 뒷부분에서 spaceOccupiedBy:을 개선 시 분명해질 것이다.
집약 알고리즘(A Compaction Algorithm)
위에서 attemptToAllocateChunk:이 호출한 compactCurrentSegment 루틴은 힙 세그먼트를 휩쓸고 지나가면서 할당된 객체를 모두 모아 그들의 객체 테이블 엔트리를 업데이트한다. 그 다음 할당을 위해 빈 청크로부터 회수한 객체 테이블 엔트리를 빈 포인터 리스트에서 연결하기도 하고 힙 세그먼트에서 사용되지 않은 부분으로부터 하나의 빈 청크를 생성하기도 한다. compactCurrentSegment에 대한 알고리즘은 준비 작업을 몇 가지 논한 다음에 간략히 소개하도록 하겠다.
힙 세그먼트가 여러 번 집약되고 나면 상대적으로 영구적인 객체가 세그먼트의 바닥까지 면밀히 조사하고 대부분의 할당 및 회수 활동이 상단 가까이에서 발생한다. 세그먼트는 할당된 청크가 빽빽이 들어찬 부분 다음에 할당되거나 빈 청크로 이루어진 부분으로 구성된다. 집약 중에 빽빽이 들어찬 부분에 위치한 청크는 절대 이동하지 않는데, 그 아래에 더 이상 제거할 공간이 남아있지 않기 때문이다. 따라서 컴팩터(compactor)는 첫 번째 빈 청크 위에서 위치가 lowWaterMark로 참조되는 청크에만 노력을 쏟는다.
abandonFreeChunksInSegment: 루틴은 lowWaterMark를 계산한다. 또한 회수된 청크를 모두 찾아 releasePointer: 하위루틴을 이용해 빈 포인터의 리스트에서 그들의 객체 테이블 엔트리를 재활용하고, 그들의 클래스 필드를 구분된 nonPointer 값으로 변경한다. 잇따른 sweep 중에 컴팩터가 그렇게 마킹된 객체를 마주칠 경우 회수된 청크로 인식할 수 있다.
abandonFreeChunksInSegment: segment
| lowWaterMark objectPointer nextPointer |
lowWaterMark ← HeapSpaceStop. "first assume that no chunk is free"
HeaderSize to: BigSize do: "for each free-chunk list"
[ :size |
objectPointer ← self headOfFreeChunkList: size
inSegment: segment.
[objectPointer = NonPointer] whileFalse:
[lowWaterMark ← lowWaterMark
min: (self locationBitsOf: objectPointer).
nextPointer ← self classBitsOf: objectPointer.
"link to next free chunk"
self classBitsOf: objectPointer put: NonPointer
"distinguish for sweep"
self releasePointer: objectPointer.
"add entry no free-pointer list"
objectPointer ← nextPointer].
self resetFreeChunkList: size inSegment: segment].
↑lowWaterMark
releasePointer: objectPointer
self freeBitOf: objectPointer put: 1.
self toFreePointerListAdd: objectPointer
힙 세그먼트는 상단에서 하단까지 sweep through를 통해 집약된다. 각 할당된 객체는 세그먼트 내에서 다른 할당된 객체를 덮어쓰지 않고 가능한 아랫방향으로 이동된다. 이동된 각 객체마다 해당하는 객체 테이블 엔트리가 발견되고 그 위치 필드는 객체의 새로운 위치를 가리키도록 업데이트된다.
힙 세그먼트의 sweep 도중에 마주치는 객체의 객체 테이블 엔트리를 찾는 일은 결코 사소한 일이 아니다. 힙 내에서 객체의 표현은 객체 테이블 엔트리로 돌아가는 포인터를 포함하지 않는다. 모든 객체에 대해 그러한 백포인터(backpointer)가 생기는 것을 피하거나 모든 객체가 이동한 후에 컴팩터가 객체 테이블을 찾도록 만들기 위해, 객체 테이블 엔트리가 힙 내의 헤더를 가리키는 일반적인 배열 대신 헤더가 임시로 객체 테이블 엔트리를 가리킨다.
포인터는 힙 세그먼트의 sweep through를 시작하기 전에 반전된다. 객체 테이블을 스캐닝하여 집약되는 세그먼트를 참조하는 세그먼트 필드를 갖고 있는 동시 위치 필드가 lowWaterMark 위에 있는 사용 중(in-use) 엔트리를 모두 찾는다. 그러한 엔트리는 각각 이동하게 될 객체의 헤더를 가리킨다 (그림 30.8a). 이후 포인터가 반전되는데, 즉 객체 고유의 객체 포인터가 그 헤더의 첫 번째 워드에 저장된다는 뜻이다. 이는 헤더가 객체 테이블 엔트리를 가리키도록 만든다. 이를 통해 헤더의 크기 필드가 덮어 쓰여진다. 크기의 손실을 피하기 위해 객체 테이블 엔트리의 두 번째 워드에 저장된다 (그림 30.8b). 이를 통해 위치 필드가 덮어 쓰여지지만 이동 후 컴팩터가 객체의 힙 위치를 재계산하기 때문에 그러한 결과는 발생하지 않는다.
reverseHeapPointersAbove: lowWaterMark
|size|
0 to: ObjectTableSize-2 by: 2 do:
[ :objectPointer |
(self freeBitOf: objectPointer) = 0
ifTrue: "the Object Table entry is in use"
[(self segmentBitsOf: objectPointer) = currentSegment
ifTrue: "the object is in this segment"
[(self locationBitsOf: objectPointer) < lowWaterMark
ifFalse: "the object will be swept"
[size ← self sizeBitsOf: objectPointer.
"rescue the size"
self sizeBitsOf: objectPointer
put: objectPointer. "reverse the pointer"
self locationBitsOf: objectPointer
put: size "save the size"]]]]
집약의 모든 준비가 완료되면 현재 힙 세그먼트가 sweepCurrentSegmentFrom: 루틴을 이용해 sweep된다. 이는 세그먼트에 두 개의 포인터를 유지하는데, 바로 si(소스 색인)와 di(목적지 색인)이다. 포인터 si는 현재 유지나 제거를 고려 중인 객체의 헤더를 가리킨다. 포인터 di는 객체가 유지될 경우 그 객체가 이동하게 될 위치를 가리킨다.
sweepCurrentSegmentFrom: lowWaterMark
| si di objectPointer size space |
si ← di ← lowWaterMark.
[si < HeapSpaceStop]
whileTrue: "for each object, si"
[(wordMemory segment: currentSegment word: si + 1) = NonPointer
ifTrue: "unallocated, so skip it"
[size ← wordMemory segment: currentSegment word: si.
si ← si + size]
ifFalse: "allocated, so keep it, but move it to compact storage"
[objectPointer
← wordMemory
segment: currentSegment word: si.
size ← self locationBitsOf: objectPointer.
"the reversed sie"
self locationBitsOf: objectPointer
put: di. "point object table at new location"
self sizeBitsOf: objectPointer
put: size. "restore the size to its proper place"
si ← si + 1. "skip the size"
di ← di + 1. "skip the size"
2 to: (self spaceOccupiedBy: objectPointer) do:
"move the rest of the object"
[ :i |
wordMemory segment: currentSegment
word: di
put: (wordMemory segment:
currentSegment
word: si).
si ← si + 1.
di ← di + 1]]].
↑di
포인터가 반전되는 동안에는 객체 테이블 엔트리로부터 객체의 힙 메모리로 접근하는 것이 불가능하다는 사실을 주목한다. 따라서 집약 도중에는 Smalltalk 인터프리터가 실행될 수 없다.
compactCurrentSegment 루틴은 위의 루틴을 적절한 순서로 호출한 후 힙 세그먼트의 상단에 하나의 빈 청크를 생성한다.
compactCurrentSegment
| lowWaterMark bigSpace |
lowWaterMark ← self abandonFreeChunksInSegment: currentSegment.
lowWaterMark < HeapSpaceStop
ifTrue:
[self reverseHeapPointersAbove: lowWaterMark.
bigSpace ← self sweepCurrentSegmentFrom: lowWaterMark.
self deallocate: (self obtainPointer:
(HeapSpaceStop + 1 - bigSpace)
location: bigSpace)]
이 루틴이 호출될 때 세그먼트 내에 빈 청크가 없다면 어떠한 객체도 이동시키기 않는다.
쓰레기 수집(Garbage Collection)
Smalltalk에서는 새로운 객체가 명시적으로 할당되지만 (예: 클래스로 new 메시지가 전송되어) 객체의 회수를 야기하는 명시적인 언어 구조체는 존재하지 않는다. 그러한 구조체는 객체를 회수하는 데 사용할 수 있지만 그에 대한 "dangling" 참조가 여전히 다른 객체에 존재할 수 있기 때문에 안전하지 않을 것이다. Dangling 참조를 포함하는 환경은 일관성이 없을 것이고 의도하지 않은 행위를 표출하거나 회복할 수 없는 오류가 야기될 가능성이 크다.
대부분의 비대화형 프로그래밍 시스템은 명시적 회수를 요구한다. Dangling 참조를 피하는 일은 프로그래머의 몫이다. Dangling 참조가 발생하면 프로그래머가 그것을 생성한 버그를 찾고 버그를 수정한 후 프로그램을 재시작할 것으로 기대한다. Smalltalk와 같은 대화형 환경에서는 (대부분의 LISP와 APL 시스템도 포함) 공통된 버그 때문에 재시작을 요구하는 일은 허용되지 않는데, 사용자가 엄청난 양의 작업을 다시 해야하기 때문이다.
Smalltalk에는 명시적 회수가 없기 때문에 메모리 관리자는 "inaccessible"(접근할 수 없는) 상태가 된 객체를 식별하고 자동으로 회수해야 한다. 이러한 작업은 "garbage collection"(쓰레기 수집)이라 알려진다. 명시적 회수와 비교할 때 쓰레기 수집은 성능이 크게 저하되는 결과가 발생한다. 이러한 불이익은 프로그래머가 코딩 시 회수를 관리하도록 의존하는 대신 실행 시 컴퓨터가 회수를 관리해야 하기 때문에 발생한다. 하지만 대화형 시스템에 증가하는 신뢰성을 생각하면 감수할 만하다.
객체 메모리 내에서 접근 불가한 객체를 식별하는 전통적인 방법이 두 가지 있는데 "marking"(마킹)과 "reference counting"(참조 계수)가 그것이다. 마킹 쓰레기 수집기는 접근 불가한 객체에 대한 메모리의 완전 탐색을 실행하여 모두 마킹(mark)한다. 이후 마킹되지 않은, 따라서 접근 불가한 객체를 메모리에서 스캐닝하여 회수한다. 참조 계수 쓰레기 수집기는 각 객체에 대한 다른 객체들로부터의 참조 계수를 유지한다. 어떤 객체에 대한 참조 계수가 0에 도달하면 그 객체는 접근 불가한 것으로 알려지고, 그 객체가 차지하는 공간이 회수된다.
참조 계수 시스템은 "cyclic structures"(순환 구조)라고 불리는 것을 적절하게 처리하지 않는다. 그러한 구조는 객체가 직접적으로 스스로를 참조하거나 그것을 참조하는 다른 객체를 통해 스스로를 간접적으로 참조할 때 발생하는 것으로 알려진다. 참조 계수 시스템에서 순환 구조가 프로그램에 접근 불가하게 되면 구조(intrastructure) 참조로 인해 0이 아닌 참조 계수를 갖게 될 것이다. 따라서 메모리 관리자는 구조가 회수되어야 함을 인식하지 않고, 구조를 구성하는 객체는 회수되지 않는다. 이러한 접근 불가한 객체는 공간을 낭비하지만 dangling 참조와 달리 환경에서 비일관성을 야기하지 않는다.
참조 계수와 마킹 모두 일반적인 컴퓨터에서 성능의 저하를 수반한다. 참조 계수 시스템에서 객체에 대한 참조를 저장하는 데에 자주 실행되는 연산은 참조 계수 관리에 대한 오버헤드를 수반하므로 프로그램이 상당히 느리게 실행된다. 마킹 쓰레기 수집기에서는 공간이 전체적으로 줄어들 때마다 광범위한 메모리 검색이 실행되어야 한다. 따라서 프로그램 실행에 인터럽트가 상대적으로 길어지기 십상이어서 대화형 시스템에서는 귀찮아진다. 두 접근법 모두 공간 오버헤드를 발생시킨다. 참조 계수 시스템에서는 참조 계수를 저장하기 위한 공간이 제공되어야 한다. 마킹 시스템에서는 컬렉션 사이에 쓰레기가 수집되도록 힙에 추가 공간이 할당되어야 한다.
Smalltalk의 특정 구현에 사용되어야 하는 쓰레기 수집 접근법은 부분적으로 하드웨어의 용량에 따라 좌우된다. 상대적으로 이용 가능한 양의 메모리가 적을 (예: 100 KB) 경우 참조 계수 시스템은 사용하기가 힘든데, 접근 불가한 순환 구조를 할당된 채로 남겨두어 소중한 공간을 낭비할 수 있기 때문이다. 반면 마킹 수집기는 이러한 상황에서 사용하기가 꽤 괜찮고, 메모리가 적어서 호출 시 인터럽트가 발생할 수 있지만 그 기간이 짧아 감지할 수 없을 정도이다. 메모리가 충분히 제공되면 (예: 2MB) 접근 가능한 객체를 모두 마킹하는 데 소요되는 시간이 너무 오래 소요되기도 한다. 반면 접근 불가한 객체를 적절한 수만큼 수용할 공간이 충분하다는 장점이 있다.
두 접근법의 차이는 큰 가상 메모리 시스템에서 두드러진다. 마킹은 이차 메모리로 무작위 접근에 너무 많은 시간이 소요되기 때문에 비용이 더 많이 들지도 모른다. 참조 계수는 회수되지 않은 순환 구조가 단순히 낭비되는 공간이 덜 성가신 이차 메모리로 이동하기 때문에 수고가 덜 든다. 메모리가 충분할 경우 참조 계수 쓰레기 수집기가 적합하다. 하지만 Smalltalk 프로그래머는 접근 불가한 순환 구조가 과도하게 누적되는 일을 피하도록 주의를 기울여야 하는데, 그렇지 않으면 큰 메모리까지 소모되기 때문이다. 프로그램은 순환 구조가 접근 불가해지기 전에 구조를 깨기 위해 주기에 참여하는 어떤 포인터든 nil로 변경할 수 있다.
쓰레기 수집에 대한 두 접근법을 결합할 수도 있다. 참조 계수는 일반적인 연산 중에 계수될 수 있고 마킹 컬렉션은 접근 불가한 순환 구조를 회수하기 위해 주기적으로 실행할 수 있다. 결합된 접근법은 실제 메모리가 최소에 해당하는 구현만 제외하고 어디든 적합하다. 작은 크기에서 중간 크기까지 메모리가 이용 가능하다면 집약이 충분한 공간을 회복하지 못할 때마다 마킹 컬렉션을 실행할 수 있다. 충분한 메모리를 이용할 수 있다면 매일 밤 또는 편리한 시간 간격을 두고 컬렉션 마킹을 실행할 수 있다.
단순 참조계수 수집기(A Simple Reference-counting Collector)
이번 장에 설명된 참조계수 수집기에서 객체의 참조 계수는 객체 테이블 엔트리의 계수 필드에 기록된다. 객체 포인터가 근접한 정수일 경우 고유의 유일한 참조에 있으므로 그 참조 계수는 명시적으로 기록되지 않는다. 참조 계수는 저장 연산 중에 업데이트된다. 객체 P를 참조하는 객체 포인터가 객체 Q를 참조하는 객체 포인터를 이전에 포함하였던 위치로 저장되면 P의 계수 필드는 증가하고 Q의 계수 필드는 감소한다. 객체 테이블 엔트리의 계수 필드에는 8 비트만 있기 때문에 증가한 계수가 오버플로할 가능성이 있다. 대부분의 컴퓨터에서 오버플로 감지를 촉진하기 위해서는 계수 필드의 상위 비트가 오버플로 비트의 역할을 한다. 계수 필드가 128에 도달하면 그 값에서 유지되고 증가되거나 감소되지 않는다. 참조 계수를 증가시키기 위한 알고리즘은 다음과 같다.
countUp: objectPointer
| count |
(self isIntegerObject: objectPointer)
ifFalse:
[count ← (self countBitsOf: objectPointer) + 1.
count < 129 ifTrue: [self countBitsOf: objectPointer put: count]].
↑objectPointer
객체의 감소된 참조 계수가 0에 도달하면 해당 객체는 회수된다. 객체를 회수하기 전에 해당 객체로부터 참조된 모든 객체의 참조 필드가 감소하는데, 객체가 회수되고 나면 더 이상 다른 객체를 참조하지 않을 것이기 때문이다. 다른 객체들 중 하나라도 0에 도달하면 이러한 절차가 재발생함을 주목한다. 원본 객체와 그것이 참조하는 모든 객체를 순회할 수 있는 재귀적 절차는 아래에 forAllObjectsAccessibleFrom:suchThat:do: 루틴과 같이 표현된다. 해당 루틴은 블록이 표현한 두 개의 절차 인자를 취하는데, predicate는 계수를 감소시키고 0과 객체를 회수한 action을 검사한다. action와 predicate의 평가 사이에 forAllObjectsAccessibleFrom:suchThat:do:이라는 절차의 하위루틴은 객체 내 모든 포인터를 재귀적으로 처리한다. 절차는 계수를 부가적 효과로 수정하도록 허용되므로 action 인자는 회수를 준비하면서 계수를 0으로 복구시켜야 한다.
countDown: rootObjectPointer
| count |
(self isIntegerObject: rootObjectPointer)
ifTrue: [↑rootObjectPointer]
ifFalse: "this is a pointer, so decrement its reference count"
[↑self forAllObjectsAccessibleFrom: rootObjectPointer
suchThat:
"the predicate decrements the count and tests for zero"
[ :objectPointer |
count ← (self countBitsOf: objectPointer) - 1.
count < 127
ifTrue: [self countBitsOf: objectPointer
put: count].
count = 0]
do: "the action zeroes the count and deallocates the object"
[ :objectPointer |
self countBitsOf: objectPointer put: 0.
self deallocate: objectPointer]]
아래에 표시된 순회 루틴은 먼저 제공된 객체에서 조건자(predicate)를 검사한다. 이후 predicate를 충족시키는 공급된 객체 내에서 참조된 객체를 모두 (1) 재귀적으로 처리하고, 제공된 객체에서 (2) action을 실행한다.
forAllObjectsAccessibleFrom: objectPointer suchThat: predicate do: action
(predicate value: objectPointer)
ifTrue:
[↑self forAllOtherObjectsAccessibleFrom: objectPointer
suchTaht: predicate
do: action]
forAllOtherObjectsAccessibleFrom: objectPointer suchThat: predicate do:action
| next|
1 to: (self lastPointerOf: objectPointer) - 1 do:
[ :offset |
next ← self heapChunkOf: objectPointer word: offset.
((self isIntegerObject: next) = = false and: [predicate value: next])
ifTrue: "it's a non-immediate object and it should be processed"
[self forAllOtherObjectsAccessibleFrom: next
suchThat: predicate
do: action]].
"all pointers have been followed; now perform the action"
action value: objectPointer.
↑objectPointer
공간효율적 참조계수 수집기(A Space-efficient Reference-counting Collector)
위에 설명된 순회 알고리즘은 재귀적이므로 실행에 스택을 사용해야 한다. 스택 오버플로가 생기지 않도록 주의하기 위해 스택의 깊이는 메모리에서 가장 긴 포인터 사슬보다 커야한다. 메모리 공간이 제한되면 이러한 요구조건을 충족시키기가 어렵다. 충분한 공간을 이용할 수 있도록 보장하기 위해서는 포인터 사슬 자체를 스택으로 이용할 수 있다. 객체 A가 A의 i번째 필드로부터 객체 B를 참조하고, 객체 B가 B의 j번째 필드로부터 객체 C를 참조하고, 객체 C는 C의 k번째 필드로부터 다른 객체를 참조하는 식으로 나아갈 경우 포인터 사슬은 A.i➛B.j➛C.k➛...로 표현할 수 있다 (그림 30.9a). 포인터 사슬을 순회 알고리즘의 재귀에 대한 스택으로 사용하기 위해서는 사슬이 ...➛C.k➛B.j➛A.i 식으로 임시적으로 역전되어 사슬 내 각 필드가 그 다음에 오는 것 대신 앞에 오는 것을 가리키도록 한다 (그림 30.9b).
순회 알고리즘의 재귀에서 각 단계는 "스택을 꺼냄"으로써 완료되어야 한다. 사슬 내 어떤 객체든 (예: C) 처리한 다음에 그 이전에 오는 객체는 (예: B) 역전된 포인터 사슬을 따름으로써 발견된다. 알고리즘은 이전에 오는 것의 어떤 필드가 작업 중인지 알 필요가 있다. 이러한 정보를 유지하기 위해 알고리즘은 B가 C를 처리하도록 둔 이전 단계에서 변경되어야 한다. 그 단계에서 필드 j의 색인이 B의 객체 테이블 엔트리의 계수 필드로 복사된다. 객체가 회수되는 중이므로 계수는 덮어쓸 수 있다. 하지만 B의 크기가 255 워드를 초과하면 계수 필드는 모든 필드 색인을 저장하기에 충분히 크지 않을 것이다. 대신 HugeSize(255) 워드 또는 그 이상에 해당하는 객체보다 1 워드씩 과할당하고 순회 알고리즘이 오프셋을 저장하는 데 사용하도록 그 추가 워드를 역전하도록 할당기(allocator)가 수정된다.
과할당을 제공하기 위해서는 할당 루틴이 0 또는 1에 해당하는 추가 인자 extraWord를 수용하도록 수정된다. 할당기가 새로운 객체의 헤더로 클래스를 저장하기 전에 새 객체의 클래스의 참조 계수를 증가시키도록 두는 것도 필요하다. (사실 이는 하위루틴의 부작용으로 우연히 클래스가 회수되지 않도록 보장하기 위해 allocateChunk:을 호출하기 전에 실행되어야 한다.)
allocate: size extra: extraWord class: classPointer
"**Preliminary Version**"
| objectPointer |
self countUp: classPointer.
"increment the reference count of the class"
objectPointer ← self allocateChunk: size + extraWord.
"allocate enough"
self classBitsOf: objectPointer put: classPointer.
HeaderSize to: size - 1 do:
[ :i | self heapChunkOf: objectPointer word: i put: NilPointer].
"the next statement to correct the SIZE need only be executed if extraWord > 0"
self sizeBitsOf: objectPointer put: size.
↑objectPointer
최소 HugeSize 필드와 함께 객체가 차지하는 실제 힙 공간은 할당된 초과 워드 때문에 그 크기 필드에 명시된 것보다 1이 크다. 따라서 spaceOccupiedBy: 루틴은 그러한 차이를 설명하도록 변경되어야 한다.
spaceOccupiedBy: objectPointer "**Preliminary Version**"
| size |
size ← self sizeBitsOf: objectPointer.
size < HugeSize
ifTrue: [↑size]
ifFalse: [↑size + 1]
회수된 객체는 크기 필드에서 계수되지 않은 추가 워드에 대한 공급을 갖고 있지 않기 때문에 회수 알고리즘은 수정되어야만 한다.
deallocate: objectPointer
| space |
space ← self spaceOccupiedBy: objectPointer.
self sizeBitsOf: objectPointer put: space.
self toFreeChunkList: (space min: BigSize) add: objectPointer
다음 루틴은 prior, current, next 변수가 표현하는 위의 예제의 A, B, C와 함께 공간 효율적인 순회 알고리즘을 구현한다. 루프 검사를 단순화하기 위해 메서드는 각 청크의 필드를 역순으로 스캐닝한다. 따라서 클래스 필드는 마지막으로 처리된다.
메서드의 마지막 문은 A 대신 C를 다시 가리키는 B.j를 얻기 위해 포인터 사슬을 복구시킨다. 처리하는 C로부터 B로 리턴 시에 수월한데, C의 객체 포인터는 B의 j번째 필드에 단순히 저장될 수 있기 때문이다. B가 회수되고 있기 때문에 그러한 단계가 불필요하다고 생각할 수도 있을 것이다. 하지만 B가 회수되지 않는 마킹 수집기도 동일한 순회 알고리즘을 사용할 수 있다.
forAllOtherObjectsAccessibleFrom: objectPointer suchThat: predicate do: action
| prior current offset size next |
"compute prior, current, offset, and size to begin processing objectPointer"
prior ← NonPointer.
current ← objectPointer.
offset ← size ← self lastPointerOf: objectPointer.
[true] whileTrue: "for all pointers in all objects traversed"
[(offset ← offset - 1) > 0 "decrement the field index"
ifTrue: "the class field hasn't been passed yet"
[next ← self heapChunkOf: current word: offset.
"one of the pointers"
((self isIntegerObject: next) = = false
and: [predicate value: next])
ifTrue: "it's a non-immediate object and it should be processed"
["reverse the pointer chain"
self heapChunkOf: current word: offset put: prior.
"save the offset either in the count field or in the extra word"
size < HugeSize
ifTrue: [self countBitsOf: current put: offset]
ifFalse: [self heapChunkOf: current
word: size + 1 put: offset].
"compute prior, current, offset, and size to begin processing next"
prior ← current. current ← next.
offset ← size ← self lastPointerOf: current]]
ifFalse:
["all pointers have been followed, now perform the action"
action value: current.
"did we get here from another object?"
prior = NonPointer
ifTrue: "this was the root object, so we are done"
[↑objectPointer].
"restore next, current, and size to resume processing prior"
next ← current. current ← prior.
size ← self lastPointerOf: current.
"restore offset either from the count field or from the extra word"
size < HugeSize
ifTrue: [offset ← self countBitsOf: current]
ifFalse: [offset ← self heapChunkOf: current word: size + 1].
"restore prior from the reversed pointer chain"
prior ← self heapChunkOf: current word: offset.
"restore (unreverse) the pointer chain"
self heapChunkOf: current word: offset put: next]]
기계어 구현은 간접적으로 호출될 하위루틴 주소 쌍을 전달하거나 일렬로 하위루틴을 확장시킴으로써 절차적 인자를 처리할 수 있다. 하드웨어가 충분한 레지스터를 갖고 있다면 추가 실행 속도를 위해 레지스터에 next, current, prior, size, offset 변수를 유지하는 것이 가능하다.
마킹 수집기(A Marking Collector)
마킹 쓰레기 수집기의 임무는 접근 가능한 객체를 모두 마킹하여 나머지 접근 불가한 객체를 식별하고 빈 청크 리스트로 추가하는 것이다. 접근 가능한 객체는 "세계의 루트", 즉 인터프리터의 스택과 전역 변수 테이블로부터 재귀적 검색으로 가장 쉽게 찾을 수 있다 (Smalltalk라는 이름의 Dictionary).
다음 알고리즘은 각 루트 객체에서 실행된다. 객체의 객체 테이블 엔트리에서 계수 필드를 1로 설정하면 "marked"(마킹되었음)을 의미한다. 객체가 참조하는 언마킹(unmarked)된 객체마다 이 단락의 알고리즘을 적용하도록 한다.
위의 "marking algorithm"(마킹 알고리즘)은 본질상 재귀적임을 주목한다. 그 구현에서는 참조 계수에 사용된 것과 동일한 순회 루틴을 단순 버전 또는 공간효율적 버전으로 이용할 수 있다. 마킹을 다시 시작하기 전에 모든 객체의 계수 필드는 "unmarked"(마킹되지 않음)을 나타내기 위해 0으로 리셋된다. 마킹이 끝나면 마킹되지 않은 객체는 모두 회수되고, 마킹된 모든 객체의 참조 계수가 계산된다. 필요한 단계를 모두 실행하는 루틴을 reclaimInaccessibleObjects라고 부른다.
reclaimInaccessibleObjects
self zeroReferenceCounts.
self markAccessibleObjects.
self rectifyCountsAndDeallocateGarbage
모든 객체의 계수 필드를 0으로 설정하는 하위루틴을 zeroReferenceCounts라고 부른다. 빈 엔트리나 빈 청크의 계수 필드를 0으로 만드는 것은 더 이상 불필요하다. 그럼에도 불구하고 아래의 버전은 모든 엔트리의 계수 필드를 0으로 만드는데, 대부분의 컴퓨터에서는 엔트리의 상태를 검사하는 데 소요되는 시간보다 엔트리의 첫 번째 바이트를 0으로 만드는 데 소요되는 시간이 적기 때문이다.
zeroReferenceCounts
0 to: ObjectTableSize - 2 by: 2 do:
[ :objectPointer |
self countBitsOf: objectPointer put: 0]
하위루틴 markAccessibleObjects는 rootObjectPointers 리스트의 객체마다 markObjectsAccessibleFrom: 마킹 알고리즘을 호출한다. 일반적으로 rootObjectPointers 리스트는 현재 프로세스의 객체 포인터와 전역 변수 사전의 객체 포인터를 포함하는데, 이로부터 접근 가능한 다른 모든 객체는 직접적으로 또는 간접적으로 참조된다.
markAccessibleObjects
rootObjectPointers do:
[ :rootObjectPointer |
self markObjectsAccessibleFrom: rootObjectPointer]
마킹 알고리즘 markObjectsAccessibleFrom:은 참조 계수 수집기가 한 것과 동일한 순회 루틴을 호출한다. predicate는 마킹되지 않은 객체에 성공하고 그러한 객체에 1의 계수를 마킹하는 효과도 가진다. 그 action은 참조 계수를 1로 복구하는데, 부가적 효과로 순회 루틴의 공간효율적 버전이 해당 필드를 0이 아닌 값으로 변경하였을 수도 있기 때문이다.
markObjectsAccessibleFrom: rootObjectPointer
| unmarked |
↑self forAllObjectsAccessibleFrom: rootObjectPointer
suchThat: "the predicate tests for an unmarked object and marks it"
[ :objectPointer |
unmarked ← (self countBitsOf: objectPointer) = 0.
unmarked ifTrue: [self countBitsOf: objectPointer put: 1].
unmarked]
do: "the action restores the mark to count = 1"
[ :objectPointer |
self countBitsOf: objectPointer put: 1]
마킹 알고리즘을 실행하고 나면 rectifyCountsAndDeallocateGarbage 하위루틴을 이용해 비어 있지 않은 객체 테이블 엔트리가 검사된다. 엔트리가 마킹되어 있지 않으면 엔트리와 그 힙 청크가 적절한 빈 리스트로 추가된다. 엔트리가 마킹되어 있으면 계수는 1씩 감소하여 언마킹을 시도하고, 그것이 직접 참조하는 모든 객체의 계수가 증가한다. 마킹된 객체를 처리할 때는 그 계수가 1을 초과할지도 모르는데, 이전에 처리된 객체들이 그것을 참조했을 수도 있기 때문이다. 그 때문에 계수를 0으로 설정하는 대신 뺄셈(substraction)으로 언마킹하는 것이다.
객체 테이블 엔트리를 검사할 때에는 마킹 컬렉션이 시작되기 전에 이미 비어 있었던 청크에 마주칠 것이다. 이미 비어 있는 청크의 계수 필드는 마킹되지 않은 객체와 마찬가지로 0이므로 빈 청크 리스트에 추가될 것이다. 그러면 청크가 이미 빈 청크 리스트에 있을 경우 문제를 야기할 것이다. 따라서 스캐닝이 시작되기 전에 빈 청크 리스트의 모든 헤드가 리셋된다.
마지막 단계는 각 루트 객체의 참조 계수가 증가하여 실수로 회수되지 않도록 확보하는 것이다.
rectifyCountsAndDeallocateGarbage
| count |
"reset heads of free-chunk lists"
FirstHeapSegment to: LastHeapSegment do: "for every segment"
[ :segment |
HeaderSize to: BigSize do: "for every free chunk list"
[ :size | "reset the list head"
self resetFreeChunkList: size inSegment: segment]].
"rectify counts, and deallocate garbage"
0 to: ObjectTableSize - 2 by: 2 do: "for every object table entry"
[ :objectPointer |
(self freeBitOf: objectPointer) = 0
ifTrue: "if it is not a free entry"
[(count ← self countBitsOf: objectPointer) = 0
ifTrue: "it is unmarked, so deallocate it"
[self deallocate: objectPointer]
ifFalse: "it is marked, so rectify reference counts"
[count < 128 ifTrue: "subtract 1 to compensate for the mark"
[self countBitsOf: objectPointer put: count - 1].
1 to: (self lastPointerOf: objectPointer) - 1 do:
[ :offset | "increment the reference count of each
pointer"
self countUp: (self heapChunkOf: objectPointer
word: offset)]]]].
"be sure the root objects don't disappear"
rootObjectPointers do:
[ :rootObjectPointer | self countUp: rootObjectPointer].
self countBitsOf: NilPointer put: 128
모든 세그먼트의 집약이 할당 요청을 충족하기에 충분한 공간을 만들어내지 못할 경우 이제 allocateChunk: 루틴이 마킹 수집을 시도하도록 수정할 수 있다.
allocateChunk: size
| objectPointer |
objectPointer ← self attemptToAllocateChunk: size.
objectPointer isNil ifFalse: [↑objectPointer].
self reclaimInaccessibleObjects. "garbage collect and try again"
objectPointer ← self attemptToAllocateChunk: size.
objectPointer isNil ifFalse: [↑objectPointer].
self outOfMemoryError "give up"
비포인터 객체(Nonpointer Objects)
이번 장에 제시된 객체 포맷은 특별히 공간 효율적이라 할 순 없지만 획일성을 확보한다면 시스템 소프트웨어를 작고 간단하게 만들면서 비효율성을 어느 정도 상쇄할 수 있다. 단, 비효율성을 허용할 수 없는 객체의 클래스가 두 개 있는데, 바로 문자열(character strings)과 bytecoded 메서드이다. 메모리에는 주로 수많은 문자열과 메서드가 존재하는데, 워드마다 하나의 문자나 하나의 바이트코드를 저장한다면 공간이 많이 낭비된다.
그러한 객체를 좀 더 효율적으로 저장하기 위해 객체의 데이터 부분이 객체 포인터가 아니라 부호가 없는 정수로 해석되는 8-bit 또는 16-bit 값을 포함하는 대안적인 메모리 포맷이 사용된다. 그러한 객체는 객체 테이블 엔트리의 포인터-필드 비트의 설정으로 구분되는데, 그러한 비트가 1이면 데이터는 객체 포인터로 구성되고 비트가 0이면 데이터는 양의 8- 또는 16-bit 정수로 구성된다. 비포인터 객체에 홀수로 된 데이터의 바이트가 있을 경우 마지막 워드의 마지막 바이트는 0이고 (약간의 공간 낭비), 주로 0에 해당하는 객체 테이블 엔트리에 대한 홀수 길이의 비트는 1로 설정된다. 비포인터 객체를 지원하기 위해 할당기는 두 개의 추가 매개변수, pointerBit와 oddBit를 필요로 한다. 비포인터 객체(pointerBit=0)의 경우 요소의 기본 초기값은 nil 대신 0이 된다. 할당 루틴의 마지막 버전은 아래에 표시하겠다.
allocate: size odd: oddBit pointer: pointerBit extra: extraWord class: classPointer
| objectPointer default |
self countUp: classPointer.
objectPointer ← self allocateChunk: size + extraWord.
self oddBitOf: objectPointer put: oddBit.
self pointerBitOf: objectPointer put: pointerBit.
self classBitsOf: objectPointer put: classPointer.
default ← pointerBit = 0 ifTrue: [0] ifFalse: [NilPointer].
HeaderSize to: size - 1 do:
[ :i | self heapChunkOf: objectPointer word: i put: default].
self sizeBitsOf: objectPointer put:size.
↑objectPointer
데이터는 포인터를 포함하지 않기 때문에 쓰레기 수집 순회 루틴은 각 비포인터 객체의 클래스 필드만 처리하면 된다. 이를 가능하게 만들기 위해서는 lastPointerOf: 루틴이 아래와 같이 변경된다.
lastPointerOf: objectPointer "**Preliminary Version**"
(self pointerBitOf: objectPointer) = 0
ifTrue:
[↑HeaderSize]
ifFalse:
[↑self sizeBitsOf: objectPointer]
lastPointerOf: 의 값은 비포인터 객체의 경우 절대 256만큼 크지 않으므로 비포인터 객체는 절대 과할당될 필요가 없다. 따라서 spaceOccupiedBy:은 다음과 같이 다시 수정된다.
spaceOccupiedBy: objectPointer
| size |
size ← self sizeBitsOf: objectPointer.
(size < HugeSize or: [(self pointerBitOf: objectPointer) = 0])
ifTrue: [↑size]
ifFalse: [↑size + 1]
CompiledMethods
CompiledMethod는 메모리 관리자에 대해서는 예외를 적용하는데, 그 데이터가 16-bit 포인터와 8-bit 부호 없는 정수로 섞여 있기 때문이다. CompiledMethods를 지원 시 유일하게 변경해야 할 사항은 바이트코드 인터프리터의 루틴 bytecodeIndexOf:의 것과 비슷한 계산인 lastPointerOf:로 추가하는 것 밖에 없다.
lastPointerOf: objectPointer
| methodHeader |
(self pointerBitOf: objectPointer) = 0
ifTrue:
[↑HeaderSize]
ifFalse:
[(self classBitsOf: objectPointer) = MethodClass
ifTrue: [methodHeader ← self heapChunkOf: objectPointer
word: HeaderSize.
↑HeaderSize + 1 + ((methodHeader bitAnd: 126)
bitShift: -1)]
ifFalse: [↑self sizeBitsOf: objectPointer]]
바이트코드 인터프리터에 대한 인터페이스(Interface to the Bytecode Interpreter)
객체 메모리의 구현에서 마지막 단계는 인터프리터가 필요로 하는 인터페이스 루틴을 제공하는 일이다. fetchClassOf: objectPointer는 그 인자가 근접한 정수일 경우 IntegerClass를 (SmallInteger의 객체 테이블 색인) 리턴한다.
object pointer access
fetchPointer: fieldIndex ofObject: objectPointer
↑self heapChunkOf: objectPointer word: HeaderSize + fieldIndex
storePointer: fieldIndex ofObject: objectPointer withValue: valuePointer
| chunkIndex |
chunkIndex ← HeaderSize + fieldIndex.
self countUp: valuePointer.
self countDown: (self heapChunkOf: objectPointer word: chunkIndex).
↑self heapChunkOf: objectPointer word: chunkIndex put: valuePointer
word access
fetchWord: wordIndex ofObject: objectPointer
↑self heapChunkOf: objectPointer word: HeaderSize + wordIndex
storeWord: wordIndex ofObject: objectPointer withValue: valueWord
↑self heapChunkOf: objectPointer word: HeaderSize + wordIndex
put: valueWord
byte access
fetchByte: byteIndex ofObject: objectPointer
↑self heapChunkOf: objectPointer byte: (HeaderSize * 2 + byteIndex)
storeByte: byteIndex ofObject: objectPointer withValue: valueByte
↑self heapChunkOf: objectPointer
byte: (HeaderSize * 2 + byteIndex)
put: valueByte
regerence counting
increaseReferencesTo: objectPointer
self countUp: objectPointer
decreaseReferencesTo: objectPointer
self countDown: objectPointer
class pointer access
fetchClassOf: objectPointer
(self isInteger Object: objectPointer)
ifTrue: [↑IntegerClass]
ifFalse: [↑self classBitsOf: objectPointer]
length access
fetchWordLengthOf: objectPointer
↑(self sizeBitsOf: objectPointer) - HeaderSize
fetchByteLengthOf: objectPointer
↑(self loadWordLengthOf: objectPointer) * 2 - (self oddBitOf: objectPointer)
object creation
instantiateClass: classPointer withPointers: length
| size extra |
size ← HeaderSize + length.
extra ← size < HugeSize ifTrue: [0] ifFalse: [1].
↑self allocate: size odd: 0 pointer: 1 extra: extra class: classPointer
instantiateClass: classPointer withWords: length
| size |
size ← HeaderSize + length.
↑self allocate: size odd: 0 pointer: 0 extra: 0 class: classPointer
instantiateClass: classPointer withBytes: length
| size |
size ← HeaderSize + ((length + 1)/2).
↑self allocate: size odd: length \\ 2 pointer: 0 extra: 0 class: classPointer
instance enumeration
initialInstanceOf: classPointer
0 to: ObjectTableSize - 2 by: 2 do:
[ :pointer |
(self freeBitOf: pointer) = 0
ifTrue: [(self fetchClassOf: pointer) = classPointer
ifTrue: [↑pointer]]].
↑NilPointer
instanceAfter: objectPointer
| classPointer |
objectPointer to: ObjectTableSize - 2 by: 2 do:
[ :pointer |
(self freeBitOf: pointer) = 0
ifTrue: [(self fetchClassOf: pointer) = classPointer
ifTrue: [↑pointer]]].
↑NilPointer
pointer swapping
swapPointersOf: firstPointer and: secondPointer
| firstSegment firstLocation firstPointer firstOdd |
firstSegment ← self segmentBitsOf: firstPointer.
firstLocation ← self locationBitsOf: firstPointer.
firstPointer ← self pointerBitOf: firstPointer.
firstOdd ← self oddBitOf: firstPointer.
self segmentBitsOf: firstPointer put: (self segmentBitsOf: secondPointer).
self locationBitsOf: firstPointer put: (self locationBitsOf: secondPointer).
self pointerBitOf: firstPointer put: (self pointerBitOf: secondPointer).
self oddBitOf: firstPointer put: (self oddBitOf: secondPointer).
self segmentBitsOf: secondPointer put: firstSegment.
self locationBitsOf: secondPointer put: firstLocation.
self pointerBitOf: secondPointer put: firstPointer.
self oddBitOf: secondPointer put: firstOdd
integer access
integerValueOf: objectPointer
↑objectPointer / 2
integerObjectOf: value
↑(value bitShift: 1) + 1
isIntegerObject: objectPointer
↑(objectPointer bitAnd: 1) = 1
isIntegerValue: valueWord
↑valueWord < = -16384 and: [valueWord > 16384]