1장 소개 1.1 명시적 해제 1.2 자동 동적 메모리 관리 1.3 가비지 컬렉션 알고리즘 비교 __안전성 __처리량 __완전성과 신속성 __정지 시간 __공간 오버헤드 __특정 언어의 최적화 __확장성과 이식성 1.4 성능의 불이익? 1.5 실험적 방법론 1.6 용어와 표기 __힙 __뮤테이터와 컬렉터 __뮤테이터 루트 __참조와 필드, 주소 __생명성과 정확성, 접근성 __의사 코드 __할당자 __뮤테이터 읽기와 쓰기 연산 __원자적 연산 __집합과 멀티셋, 시퀀스, 튜플
2장 마크 스윕 가비지 컬렉션 2.1 마크 스윕 알고리즘 2.2 3색 추상화 2.3 마크 스윕 개선 2.4 비트맵 마킹 2.5 지연된 스위핑 2.6 마킹 루프에서 캐시 미스 2.7 고려할 사항 __뮤테이터 오버헤드 __처리량 __공간 사용량 __이동시킬 것인가 말 것인가?
3장 마크 컴팩트 가비지 컬렉션 3.1 두 손가락 압축 3.2 리스프 2 알고리즘 3.3 스레디드 압축 3.4 단일 패스 알고리즘 3.5 고려할 사항 __압축이 필요한가? __압축에 의한 처리량의 비용 __생명주기가 긴 데이터 __지역성 __마크 컴팩트 알고리즘의 한계
4장 복사 가비지 컬렉션 4.1 반공간 복사 컬렉션 __작업 리스트 구현 __예제 4.2 순회 순서와 지역성 4.3 고려할 사항 __할당 __공간과 지역성 __객체 이동
5장 일반화 선형 모형과 지수족 5.1 참조 카운팅의 장단점 5.2 효율성 개선 5.3 지연 참조 카운팅 5.4 병합 참조 카운팅 5.5 순환 참조 카운팅 5.6 제한된 필드 참조 카운팅 5.7 고려할 사항 __환경 __고급 해결책
6장 가비지 컬렉터 비교 6.1 처리량 6.2 정지 시간 6.3 공간 6.4 구현 6.5 적응 시스템 6.6 가비지 컬렉션의 통합 이론 __추상 가비지 컬렉션 __추적 가비지 컬렉션 __참조 카운팅 가비지 컬렉션
7장 할당 7.1 순차 할당 7.2 프리 리스트 할당 __최초 적합 할당 __차선 적합 할당 __최적 적합 할당 __프리 리스트 할당의 속도 개선 7.3 단편화 7.4 분리 적합 할당 __단편화 __크기 클래스 채우기 7.5 분리 적합과 최초, 최적, 차선 적합과의 조합 7.6 추가 고려 사항 __정렬 __크기 제한 __경계 태그 __힙 파싱 가능성 __지역성 __비사용 영역의 보존 __교차 맵 7.7 병행 시스템에서의 할당 7.8 고려할 사항
8장 힙 분할 8.1 용어 8.2 분할 이유 __이동성에 의한 분할 __크기에 의한 분할 __공간에 의한 분할 __종류에 의한 분할 __효율성을 위한 분할 __정지 시간 단축을 위한 분할 __지역성을 위한 분할 __스레드에 의한 분할 __사용 가능성에 의한 분할 __가변성에 의한 분할 8.3 분할 방법 8.4 분할 시점
9장 세대 가비지 컬렉션 9.1 예제 9.2 시간 측정 9.3 세대 가설 9.4 세대와 힙 배치 9.5 다중 세대 9.6 나이 기록 __집단적 승격 __반공간의 나이 기록 __생존자 공간과 유연성 9.7 프로그램 동작에 적응 __Appel식 가비지 컬렉션 __피드백 제어 승격 9.8 세대 간 포인터 __기억 세트 __포인터 방향 9.9 공간 관리 9.10 구세대 우선 가비지 컬렉션 9.11 벨트웨이 9.12 세대별 수집을 위한 분석 지원 9.13 고려할 사항 9.14 추상 세대별 가비지 컬렉션
10장 기타 분할 기법 10.1 큰 객체 공간 __트레드밀 가비지 컬렉터 __운영체제의 지원을 통한 객체의 이동 __포인터가 없는 객체 10.2 위상 컬렉터 __성숙 객체 공간 가비지 컬렉션 __연결 기반의 가비지 컬렉션 __스레드 로컬 가비지 컬렉션 __스택 할당 __영역 추론 10.3 하이브리드 마크 스윕, 복사 컬렉터 __가비지 우선 알고리즘 __혼합 기법과 기타 방법 __제한된 메모리 공간에서의 복사 컬렉션 10.4 북마킹 가비지 컬렉션 10.5 이면 참조 카운팅 10.6 고려할 사항
11장 런타임 인터페이스 11.1 할당 인터페이스 __할당 속도 높이기 __제로화 11.2 포인터 찾기 __보수적인 포인터 찾기 __태깅된 값을 이용한 정확한 포인터 찾기 __객체 내의 정확한 포인터 찾기 __전역 루트에서 정확한 포인터 찾기 __스택과 레지스터 내에서 정확한 포인터를 찾기 __코드 내의 정확한 포인터 찾기 __내부 포인터 다루기 __파생 포인터 다루기 11.3 객체 테이블 11.4 외부 코드로부터의 참조 11.5 스택 장벽 11.6 GC 안전한 지점과 뮤테이터 일시 정지 11.7 가비지를 수집하는 코드 11.8 읽기 장벽과 쓰기 장벽 __엔지니어링 __쓰기 장벽의 정확성 __해시 테이블 __순차 저장 버퍼 __오버플로우 동작 __카드 테이블 __교차 맵 __카드 요약 __하드웨어와 가상 메모리 기법 __쓰기 장벽 메커니즘: 요약 __청크 리스트 11.9 주소 공간 관리 11.10 가상 메모리 페이지 보호의 응용 __이중 매핑 __접근 금지 페이지의 응용 11.11 힙 크기 선택 11.12 고려할 사항
12장 언어 한정적인 사항 12.1 최종화 __파이널라이저를 실행하는 시점 __어떤 스레드가 파이널라이저를 실행하는가? __파이널라이저는 서로 병행적으로 실행할 수 있는가? __파이널라이저는 도달 불가능해진 객체에 접근할 수 있는가? __최종화가 진행된 객체는 언제 회수되는가? __파이널라이저에서 오류가 있다면 어떻게 되는가? __최종화에 대한 보장된 순서가 존재하는가? __최종화 경쟁 문제 __파이널라이저와 락 __특정 언어에서의 최종화 __추가 논의 12.2 약한 참조 __추가 동기 __다양한 포인터 강도 지원 __Phantom 객체를 사용한 최종화 순서 조정 __약한 포인터 정리 시의 경쟁 __약한 포인터 정리에 대한 통지 __여타 언어에서의 약한 포인터 12.3 고려할 사항
13장 병행성 입문 13.1 하드웨어 __프로세서와 스레드 __상호 연결 __메모리 __캐시 __일관성 __캐시 일관성 성능 예제: 스핀 락 13.2 하드웨어 메모리 일관성 __펜스와 선행 발생 __일관성 모델 13.3 하드웨어 기본 연산 __Compare-and-swap __Load-linked/store-conditionally __원자적 기본 산술 연산 __Test-then-test-and-set __좀 더 강력한 기본 연산 __원자적 기본 연산의 오버헤드 13.4 진행 보장 __진행 보장과 병행성 수집 13.5 병행성 알고리즘에서의 표기법 __명시적 펜스 지점 13.6 상호 배제 13.7 작업 공유와 종료 탐지 __랑데뷰 장벽 13.8 병행성 자료 구조 __병행성 스택 __단일 연결 리스트로 구현된 병행성 큐 __배열로 구현된 병행성 큐 __작업 가져오기 용도의 병행성 데큐 13.9 트랜잭션 메모리 __트랜잭션 메모리란 무엇인가? __수집 구현에 도움이 되는 트랜잭션 메모리 사용 __가비지 컬렉션에서의 트랜잭션 메모리 지원 13.10 고려할 사항
14장 병렬 가비지 컬렉션 14.1 병렬화할 만한 충분한 작업이 존재하는가? 14.2 부하 분산 14.3 동기화 14.4 분류 14.5 병렬 마킹 __프로세서 중심적 기법 14.6 병렬 복사 __프로세서 중심적 기법 __메모리 중심적 기법 14.7 병렬적 스위핑 14.8 병렬 압축 14.9 고려할 사항 __용어 __병렬 수집을 할 만한 가치가 있는가? __작업 분산 전략 __추적 관리 __저수준 동기화 __스윕과 압축 __종료
15장 병행성 가비지 컬렉션 15.1 병행성 수집의 정확성 __다시 살펴보는 삼색 추상화 __손실된 객체 문제 __강한 삼색 불변성과 약한 삼색 불변성 __정밀성 __뮤테이터 색상 __할당 색상 __점진적 갱신 해결책 __시작 시점에서 스냅샷을 이용한 해결책 15.2 병행성 수집에서의 장벽 기법 __그레이 뮤테이터 기법 __블랙 뮤테이터 기법 __장벽 기법의 완벽성 __병행성 쓰기 장벽 메커니즘 __1단계 카드 테이블 __2단계 카드 테이블 __작업 줄이기 15.3 고려할 사항
16장 병행적 마크 스윕 16.1 초기화 16.2 종료 16.3 할당 16.4 병행적 마킹과 스윕 16.5 온더플라이 마킹 __온더플라이 수집에서의 쓰기 장벽 __Doligez-Leroy-Gonthier __자바에서의 Doligez-Leroy-Gonthier __슬라이딩 뷰 16.6 추상적 병행성 수집 __컬렉터 파면 __원래 객체 추가 __뮤테이터 장벽 __정밀도 __컬렉터의 인스턴스화 16.7 고려할 사항
17장 병행성 복사와 압축 17.1 모스틀리 병행적 복사: 베이커 알고리즘 __모스틀리 병행적, 모스틀리 복사 수집 17.2 Brook의 간접 장벽 17.3 자가 삭제 읽기 장벽 17.4 복제 복사 17.5 다중 버전의 복사 __카피온라이트 방지를 위한 확장 17.6 사파이어 __컬렉터 단계 __병합 단계 __휘발성 필드 17.7 병행성 압축 __컴프레서 __무정지 17.8 고려할 사항
18장 병행성 참조 카운팅 18.1 단순한 참조 카운팅 다시 살펴보기 18.2 버퍼화된 참조 카운팅 18.3 병행적, 순환 참조 카운팅 18.4 힙 스냅샵 담기 18.5 슬라이딩 뷰 참조 카운팅 __연령 지향적인 수집 __알고리즘 __슬라이딩 뷰 순환 회수 __메모리 일관성 18.6 고려할 사항
19장 실시간 가비지 컬렉션 19.1 실시간 시스템 19.2 실시간 컬렉션 스케줄링 19.3 작업 기반의 실시간 수집 __병렬적, 병행적 복제 __작업 기반 스케줄링에서 불균형한 작업과 그 영향 19.4 슬랙 기반의 실시간 컬렉션 __컬렉터 작업 스케줄링 __실행 오버헤드 __프로그래머 입력 19.5 시간 기반의 실시간 수집: 메트로놈 __뮤테이터 사용량 __예측 가능성 지원 __분석 __견고성 19.6 스케줄링 접근법 통합: 증세 정책 __증세 정책 스케줄링 __증세 정책 선제 조건 19.7 단편화 제어 __메트로놈에서 점진적 압축 __단일 프로세서에서의 점진적 복제 __무정지: 락이 없는 가비지 컬렉션 __스타카토: 뮤테이터 대기 없음을 이용한 최선의 압축 __치킨: x86에서 뮤테이터 대기가 없는 최선의 압축 __클로버: 락이 없는 확률적 뮤테이터를 이용한 보장된 압축 __무정지 기법과 치킨, 클로버의 비교 __단편화된 할당 19.8 고려할 사항
★ 이 책에서 다루는 내용 ★
■ [Garbage Collection](1996)의 후속으로 완벽한 최신의 독보적인 개정판 ■ 병렬적, 병행적, 실시간 가비지 컬렉션 알고리즘을 철저히 분석 ■ 런타임 시스템 인터페이스를 비롯해 가비지 컬렉션의 까다로운 면을 설명 ■ 2,500 종류가 넘는 가비지 컬렉션 관련 문서가 담긴 포괄적인 온라인 데이터베이스에 의한 지원
★ 이 책의 대상 독자 ★
이 책에는 지난 50년간에 걸친 자동 메모리 관리 연구자와 개발자들이 축척한 다양한 경험을 함께 수록하려 노력했다. 문헌은 방대해 우리가 제시한 온라인 참고 문헌은 이 책의 집필 당시에 2,500 항목 정도였다. 가장 중요한 접근법과 최신 기술을 하나의 접근 가능한 프레임워크 내에서 논의하고 비교한다. 일관적인 스타일과 용어를 사용해 알고리즘과 개념을 제시함에 있어서 신중을 기했다. 이들 알고리즘과 개념은 종종 의사코드와 예시를 통해 자세하게 설명한다. 성능이 중요시되는 곳에서는 동기화를 위한 기본 연산의 선택과 캐시 같은 하드웨어 요소가 알고리즘 설계에 영향을 주는 것과 같은 저수준(Low level)의 세부 사항에 주의를 기울였다.
특히 지난 10여 년간에 걸쳐 하드웨어와 소프트웨어 향상으로 인해 가비지 컬렉션에 주어진 새로운 도전적 과제를 언급한다. 프로세서와 메모리 간의 성능 간극은 대체로 계속 커지고 있다. 프로세서 클럭 속도는 증가했고 더 많은 코어가 프로세서에 위치하며, 다수의 프로세서 모듈을 가진 구성이 일반화됐다. 고성능 가비지 컬렉터의 설계자와 구현가들을 위해 이런 변경의 결과에 대해 중점을 둔다. 이들의 알고리즘은 캐시 성능이 중요시되므로 지역성을 고려해야 한다. 늘어난 애플리케이션 프로그램들은 멀티코어 프로세서에서 멀티스레드화된 멀티코어 프로세서에서 실행된다. 순차적 병목현상을 회피하게끔 메모리 관리자를 설계해야 한다. 반면 새로운 하드웨어가 제공하는 병렬성을 이용할 수 있게 가비지 컬렉터를 설계해야 한다.
Jones[1996]는 당시에 여러 개의 컬렉터 스레드를 병렬로 실행할 수 있을지에 대해서는 전혀 고려하지 않았다. 집필 당시에는 생소하게 보였던 점진적 수집과 병행적 수집에 관해 한 단원을 할애한다.
현대 하드웨어가 제공하는 가능성과 제약은 이 책 전반에 걸쳐 민감한 부분이다. 이 책 전체에 걸쳐 지역성 문제를 다룬다. 시작 부분부터 애플리케이션 프로그램은 멀티스레드화될 수 있음을 가정한다. 좀 더 단순하고 전통적인 알고리즘을 많이 다루겠지만, 병렬성과 점진적, 병행성, 실시간 가비지 컬렉션 논의에 이 책의 절반을 할애한다. 이러한 내용들이 프로그래밍 언어 구현에 관심이 있는 대학원생과 연구자, 개발자에 도움이 될 것을 희망한다. 프로그래밍 언어와 컴파일러 구축, 소프트웨어 엔지니어링, 운영체제의 고급정을 수강하는 학부생에게도 이 책은 유용하다. 더욱이 여기서 제공하는 지식을 통해 전문적 프로그래머에게도 가비지 컬렉터가 직면한 문제와 상이한 컬렉터가 동작하는 방식에 좀 더 나은 통찰력을 제공해 여러 언어가 제공하는 가비지 컬렉터를 선택하고 구성하는데 있어서 좀 더 진보가 있기를 희망한다. 현대 프로그래밍 언어가 거의 채택하고 있는 가비지 컬렉션의 완전한 이해는 모든 프로그래머에게는 필수적이다.
★ 이 책의 구성 ★
2장에서는 자동 저장 공간 회수가 바람직한 이유를 설명하고, 상이한 가비지 컬렉션 전략을 비교할 수 있는 방법을 소개한다. 이 책 전반에 걸쳐 사용되는 추상화와 의사코드 표기법의 설명으로 끝을 맺는다.
3장에서 6장까지는 고전적인 가비지 컬렉션을 구성하는 부분들을 상세히 다룬다. 마크 스윕과 마크 컴팩트, 복사 가비지 컬렉션, 참조 카운팅을 살펴본다. 현대 하드웨어에서 이들 구현에 특히 초점을 맞춰 이들 전략을 좀 더 심도 있게 다룬다. 좀 더 일반적인 소개를 원하는 독자는 이전에 출판된 『Garbage Collection: Algorithms for Automatic Dynamic Memory Management』(Wiley, 1996)을 참고하기 바란다. 7장에서는 2장에서부터 5장에 걸쳐 다룬 전략과 알고리즘에 대해 이들의 장점과 약점, 다른 컨텍스트에서의 적용 가능성을 좀 더 심도 있게 비교한다.
저장 공간이 회수되는 방식은 저장 공간이 할당되는 방식에 좌우된다. 7장에서는 메모리 할당의 상이한 방법을 고려해보고, 자동 가비지 컬렉션이 할당자의 정책(명시적 malloc/free 메모리 관리와는 다른 정책)에 영향을 주는 정도를 검토해본다.
1장에서 7장까지는 힙 내의 모든 객체는 동일한 방식으로 관리된다는 암묵적인 가정을 한다. 하지만 이런 가정이 왜 취약한 설계인지에 대해서는 여러 이유가 있다. 8장부터 10장까지는 힙을 다른 공간으로 분할하는 이유와, 이들 분할된 공간을 관리하는 방법을 고려해본다. 객체 관리에 가장 성공적인 전략 중 하나인 세대별 가비지 컬렉션을 살펴보고 대규모 객체와 기타 여러 분할 기법을 다루는 방법을 알아본다.
런타임 시스템의 나머지 부분과의 인터페이스는 컬렉터 구축의 가장 까다로운 부분이다. 11장을 포인터 찾기와, 수집하기에 안전한 지점, 읽기 및 쓰기 장벽을 비롯한 런타임 인터페이스에 할애했고, 12장을 최종화와 약한 참조 같은 언어 특정적인 관심 사항에 할애했다.
이제 관심사를 병행성으로 돌려보자. 13장에서는 현대 하드웨어가 가비지 컬렉션 구현가에게 제공하는 것을 조사해보고, 동기화와 진행, 종료, 의견 수렴에 대한 알고리즘을 살펴본다. 14장에서는 모든 애플리케이션 스레드가 중지된 동안에 병렬적으로 다중 컬렉터 스레드를 실행하는 방법을 알아본다. 15장에서부터 18장까지는 광범위한 병행적 컬렉터를 고려해보고, 사용자 프로그램에 가장 짧은 간섭을 가지면서 수집이 일어날 수 있도록 스레드 중지 방식의 요건을 완화한다. 마지막으로 19장에서는 이런 요건을 가장 도전적인 극한 상황인 경성 실시간 시스템용의 가비지 컬렉션으로 확장해본다.
각 장의 마지막 부분에 고려할 사항을 요약해뒀다. 이는 독자들로 하여금 자신들의 시스템이 갖는 요건이 무엇이며, 이들 요건을 어떻게 충족시킬지에 대한 질문을 불러일으키기 위해 의도한 것이다. 클라이언트 프로그램의 동작과 이들의 운영체제, 하부의 하드웨어에 관한 질문에 대해 해답을 주지는 않았다. 이들 요약 사항은 해당 장을 읽는 것을 대신하지는 못한다. 요약 사항은 압축한 해결책을 의도한 것이 아니며, 추가적인 분석에 논의의 초점을 두고자 함이다.
마지막으로, 빠진 부분은 무엇일까? 런타임 시스템에 장착된 메모리 관리의 자동 기법만 을 고려했다. 따라서 언어 명세에 가비지 컬렉션이 적시돼 있는 경우라도 이들 언어가 지원할 수도 있는 메모리 관리에 관한 다른 메커니즘을 심도 있게 논의하지 못했다. 가장 분명한 예는 '영역'의 사용인데, 이는 자바의 실시간 명세에서 가장 두드러지게 사용됐다. 영역 추론 문제나 스택 할당 문제에 잠시 관심을 기울였지만, 가비지 컬렉션을 대체하거나 최소한 이를 보조할 의도의 여타 컴파일 시점의 분석은 전혀 하지 못했다. 클라이언트 프로그램에서 참조 카운팅 같은 기법을 최적으로 사용하는 방법이 C++ 같은 언어에서 인기가 많을지라도 이를 언급하지 하지 않았다. 마지막으로, 지난 10년 동안에는 분산 가비지 컬렉션에서 새로운 연구가 거의 없었다. 다방면으로 이는 안타까운 일이다. 그 분야에서 배울 내용들이 매우 비일관적인 메모리 아키텍처에서 이질적인 수집을 하는 차세대 머신을 위한 컬렉터 개발에 유용할 수도 있었기 때문이다. 그럼에도 불구하고 분산 가비지 컬렉션을 언급하지 않았다.
총 
바보 빅터
