쓰레기 수집 ( 컴퓨터 과학 ) - 위키백과 , 우리 모두 의 백과사전 
 쓰레기 수집 ( 컴퓨터 과학 ) 
 ( 가비지 콜렉션 에서 넘 어 옴 ) 
 쓰레기 수집 ( garbage collection 가비지 컬렉션 [ *], GC ) 은 메모리 관리 기법 중 의 하나 로 , 프로그램 이 동적 으로 할당 했 던 메모리 영역 중 에서 필요 없 게 된 영역 을 해제 하 는 기능 이 다 . 영어 를 그대로 읽 어 가비지 컬렉션 이 라 부르 기 도 한다 . 1959 년 무렵 리스프 의 문제 를 해결 하 기 위해 존 매카시 가 개발 하 였 다 . [ 1 ] 
 3 포인터 추적 방식 
 3 . 1 접근 가능 한 객체 
 3 . 2 여러 가지 포인터 추적 기법 
 3 . 2 . 1 표시 하 고 쓸 기 ( mark and sweep ) 
 3 . 2 . 2 삼 색 표시 기법 
 3 . 2 . 3 객체 이동 기법 
 3 . 2 . 4 세대 단위 쓰레기 수집 
 4 참조 횟수 계산 방식 
 5 쓰레기 수집 기법 을 사용 하 는 언어 
 쓰레기 수집 은 동적 할당 된 메모리 영역 가운데 더 이상 사용 할 수 없 게 된 영역 을 탐지 하 여 자동 으로 해제 하 는 기법 이 다 . 더 이상 사용 할 수 없 게 된 영역 이란 , 어떤 변수 도 가리키 지 않 게 된 영역 을 의미 한다 . 
 자바 , C #, 그리고 일부 스크립트 언어 들 은 처음 부터 쓰레기 수집 기법 을 염두 에 두 고 설계 되 어 , 언어 정의 에 쓰레기 수집 이 포함 되 어 있 다 . C , C ++ 등 의 프로그래밍 언어 는 수동 메모리 관리 를 가정 하 고 설계 되 었 으나 , 쓰레기 수집 을 지원 하 는 구현 도 존재 한다 . D 와 같 은 어떤 언어 들 은 쓰레기 수집 을 지원 하 지만 , 필요 에 따라 쓰레기 수집 을 하 지 않 고 수동 으로 메모리 를 관리 할 수 있 다 . 
 쓰레기 수집 이 지원 되 는 환경 에서 는 프로그래머 가 동적 으로 할당 한 메모리 영역 의 전체 를 완벽 하 게 관리 할 필요 가 없 어 진다 . 쓰레기 수집 은 다음 과 같 은 버그 를 줄이 거나 완전히 막 을 수 있 다 . 
 유효 하 지 않 은 포인터 접근 : 이미 해제 된 메모리 에 접근 하 는 버그 를 가리킨다 . 만약 이 포인터 가 해제 되 고 새로운 값 이 할당 되 었 다면 , 잘 못 된 값 을 읽 어 오 게 된다 . 
 이중 해제 : 이미 해제 된 메모리 를 또 다시 해제 하 는 버그 를 가리킨다 . 일부 메모리 할당 알고리즘 에서 는 , 해제 된 메모리 를 다시 해제 하 려고 시도 하 는 것 은 오류 를 일으킬 수 있 다 . 
 메모리 누수 : 더 이상 필요 하 지 않 은 메모리 가 해제 되 지 않 고 남 아 있 는 버그 를 가리킨다 . 메모리 누수 가 반복 되 면 메모리 고갈 로 프로그램 이 중단 될 수 있 다 . ( 접근 가능 한 메모리 가 증가 하 여 메모리 가 고갈 되 는 문제 는 쓰레기 수집 으로 도 막 을 수 없 다 ) 
 반면 , 쓰레기 수집 기법 은 다음 과 같 은 단점 을 갖 고 있 다 . 
 어떤 메모리 를 해제 할지 결정 하 는 데 비용 이 든다 . 객체 가 필요 없 어 지 는 시점 을 프로그래머 가 미리 알 고 있 는 경우 에 도 쓰레기 수집 알고리즘 이 메모리 해제 시점 을 추적 해야 하 므로 , 이 작업 은 오버헤드 가 된다 . 
 쓰레기 수집 이 일어나 는 타이밍 이나 점유 시간 을 미리 예측 하 기 어렵 다 . 때문 에 프로그램 이 예측 불 가능 하 게 일시 적 으로 정지 할 수 있 다 . 이런 특성 은 특히 실시간 시스템 에 는 적합 하 지 않 다 . 
 할당 된 메모리 가 해제 되 는 시점 을 알 수 없 다 . 자원 할당 과 변수 초기 화 를 일치 하 는 RAII ( Resource Acquisition is Initialization ) 스타일 의 프로그래밍 에서 는 , 이것 은 자원 해제 시점 을 알 수 없 다는 것 을 의미 한다 . 
 포인터 추적 방식 편집 
 대부분 의 쓰레기 수집 기법 은 포인터 추적 방식 을 사용 한다 . 포인터 추적 방식 은 한 개 이상 의 변수 가 접근 가능 한 메모리 는 앞 으로 사용 할 수 있 는 메모리 로 간주 하 고 , 그 밖 의 메모리 를 해제 하 는 방식 을 가리킨다 . 
 접근 가능 한 객체 편집 
 접근 가능 한 객체 는 어떤 변수 가 직접 가리키 는 메모리 , 또는 간접 적 으로 가리키 는 메모리 를 의미 한다 . 접근 가능 한 메모리 는 다음 과 같이 재귀 적 으로 정의 할 수 있 다 . 
 변수 가 가리키 는 객체 . 여기 서 변수 는 콜 스택 에서 정의 된 지역 변수 와 전역 변수 를 모두 포함 한다 . 
 접근 가능 한 객체 가 가리키 는 모든 객체 는 마찬가지 로 접근 가능 하 다 . 
 여러 가지 포인터 추적 기법 편집 
 포인터 추적 기법 에 는 여러 가지 변종 이 존재 한다 . 어떤 언어 들 은 다음 기법 들 가운데 여러 가지 전략 을 함께 사용 하 기 도 한다 . 
 표시 하 고 쓸 기 ( mark and sweep ) 편집 
 표시 하 고 쓸 기 기법 은 포인터 추적 기법 가운데 가장 단순 한 기법 이 다 . 먼저 각 메모리 할당 영역 에 표시 를 위해 1 비트 의 메모리 를 남겨 둔다 . 표시 단계 에서 , 모든 변수 가 가리키 는 영역 을 " 사용 중 " 으로 표시 하 고 , 그 영역 에서 가리키 는 또 다른 영역 또한 " 사용 중 " 으로 표시 한다 . 이 와 같이 모든 메모리 영역 을 표시 하 고 나 면 , 표시 되 지 않 은 영역 을 접근 불 가능 한 메모리 영역 이 된다 . 접근 불 가능 한 메모리 영역 들 을 쓸 기 단계 에서 모두 해제 한다 . 
 이 기법 의 단점 은 , 표시 단계 에서 메모리 내용 이 변경 되 지 않 아야 하 기 때문 에 전체 시스템 의 실행 이 정지 된다는 것 이 다 . 또한 전체 메모리 영역 을 검사 해야 하 므로 메모리 페이징 을 사용 하 는 운영 체제 에서 프로그램 의 성능 이 저하 될 수 있 다 . 
 삼색 표시 기법 편집 
 표시 하 고 쓸 기 기법 의 단점 을 보완 하 기 위해 , 많 은 언어 들 은 삼색 표시 기법 을 사용 한다 . 삼색 표시 기법 은 기본 적 으로 표시 하 고 쓸 기 와 같 은 기법 이 지만 , 표시 단계 에서 2 가지 가 아닌 3 가지 ( 흰색 , 회색 , 검 은 색 ) 정보 중 하나 로 메모리 를 표시 한다 . 이 기법 은 다음 과 같 은 순서 로 이루어진다 . 
 각각 의 객체 를 흰색 , 회색 , 검은색 으로 분류 한다 . 
 흰색 은 더 이상 접근 불 가능 한 객체 를 가리킨다 . 
 회색 은 접근 가능 한 객체 이 지만 , 이 객체 에서 가리키 는 객체 들 은 아직 검사 되 지 않 았 음 을 의미 한다 . 
 검 은 색 은 이 영역 에서 가리키 는 객체 들 이 흰색 객체 를 가리키 지 않 음 을 의미 한다 . 
 알고리즘 이 시작 할 때 는 변수 가 가리키 는 객체 들 이 회색 으로 표시 되 며 , 그 외 의 모든 객체 는 흰색 으로 표시 된다 . 
 회색 으로 표시 된 객체 가운데 하나 를 선택 하 여 검은색 으로 표시 하 고 , 이 객체 가 가리키 는 모든 객체 를 회색 으로 표시 한다 . 
 회색 객체 가 하나 도 남 지 않 을 때 까지 위 과정 을 반복 한다 . 
 남 은 흰색 객체 는 접근 불 가능 한 객체 이 므로 , 모두 해제 한다 . 
 이 알고리즘 은 단순 한 표시 하 고 쓸 기 알고리즘 과 달리 , 프로그램 이 실행 중 에 도 병행 하 여 수행 할 수 있 다 . 또한 , 메모리 가 고갈 되 었 을 때 쓰레기 수집 을 실행 하 는 것 이 아니 라 주기 적 으로 수집 하 는 것 도 가능 하 다 . 
 객체 이동 기법 편집 
 객체 이동 기법 은 , 해제 할 객체 표시 가 완료 된 후 해제 되 지 않 은 객체 를 그대로 두 는 것 이 아니 라 , 다른 영역 으로 복사 하 는 기법 을 가리킨다 . 원래 대로 유지 해도 무방 한 객체 를 복사 하 는 것 은 언뜻 비 효율 적 으로 여겨질 수 도 있 으나 , 다음 과 같 은 실용 적 인 장점 을 가지 고 있 다 . 
 해제 된 후 재 사용 가능 한 영역 과 사용 중 인 영역 을 표시 하 기 위해 추가 적 인 작업 을 할 필요 가 없 다 . 따라서 해제 된 영역 을 포인터 로 관리 하 는 방식 에 비해 할당 과 해제 가 빠르 게 이루어진다 . 
 할당 된 메모리 들 이 단편 화 되 는 것 을 막 을 수 있 다 . 
 연결 리스트 와 같 은 연결 형 자료 구조 에서 , 서로 연결 된 객체 들 이 메모리 상 에서 가까운 위치 에 할당 될 확률 이 높 아 진다 . 이 는 캐시 와 관련 하 여 성능 향상 에 도움 이 된다 . 
 반면 , 메모리 이동 기법 은 주기 적 으로 포인터 의 내용 이 바뀌 므로 포인터 연산 을 사용 할 수 없 게 된다는 단점 이 있 다 . 
 세대 단위 쓰레기 수집 편집 
 많 은 연구자 들 은 프로그램 에서 새롭 게 할당 된 영역 일수록 금방 해제 될 확률 이 높 다는 관찰 을 보 고 하 였 다 . 세대 단위 쓰레기 수집 기법 은 이런 특성 을 이용 하 여 , 각각 의 객체 를 할당 된 시간 에 따라 세대 별 로 구분 하 여 , 각 세대 별 로 서로 다른 메모리 영역 에 객체 를 할당 한다 . 만약 한 세대 의 메모리 영역 이 꽉 차 면 , 이 메모리 영역 에서 살아남 은 객체 를 더 오래 된 메모리 영역 으로 옮긴다 . 새로 할당 된 영역 에서 는 대부분 의 객체 들 이 빠르 게 해제 되 고 오래 된 영역 에서 는 객체 들 이 변하 지 않 을 확률 이 높 으므로 , 이 기법 은 메모리 의 일부 영역 만 을 주기 적 으로 수집 하 게 되 는 장점 이 있 다 . 자바 , 닷넷 프레임워크 등 현대 적 언어 들 은 대부분 이 기법 을 사용 한다 . 
 참조 횟수 계산 방식 편집 
 이 부분 의 본문 은 참조 횟수 계산 방식 입니다 . 
 일부 쓰레기 수집 기법 은 참조 횟수 계산 방식 을 사용 한다 . 참조 횟수 계산 방식 은 각 객체 에서 참조 횟수 를 기억 하 여 , 참조 횟수 가 0 이 되 면 해당 객체 를 해제 하 는 방식 을 가리킨다 . 파이썬 표준 구현 인 CPython 에서 이 방식 을 사용 한다 . C ++ 에서 는 스마트 포인터 라는 특수 한 객체 를 이용 해 이 기법 을 구현 할 수 있 다 . 
 참조 횟수 계산 방식 은 다음 과 같 은 장점 을 가지 고 있 다 . 
 객체 가 접근 불 가능 해 지 는 즉시 메모리 가 해제 되 므로 , 프로그래머 가 객체 의 해제 시점 을 어느 정도 예측 할 수 있 다 . 
 객체 가 사용 된 직후 에 메모리 를 해제 하 므로 , 메모리 해제 시점 에 해당 객체 는 캐시 에 저장 되 어 있 을 확률 이 높 다 . 따라서 메모리 해제 가 빠르 게 이루어진다 . 
 위 와 같 은 장점 때문 에 , 참조 횟수 계산 방식 은 메모리 관리 뿐 아니 라 다른 자원 할당 기법 에 도 종종 사용 된다 . 예 를 들 어 하드 디스크 블록 의 할당 과 해제 를 담당 하 는 파일 시스템 의 경우 , 포인터 추적 방식 의 쓰레기 수집 은 디스크 라는 매체 의 특성 상 오랜 시간 을 소모 하 게 된다 . 그러나 참조 횟수 계산 방식 은 할당 된 블록 을 해제 하 는 시점 에 해당 블록 을 가리키 는 포인터 가 운영 체제 의 버퍼 에 로딩 되 어 있 으므로 , 빠르 게 블록 을 해제 할 수 있 다 . 
 반면 참조 횟수 계산 방식 에 는 다음 과 같 은 단점 이 있 다 . 
 두 개 이상 의 객체 가 서로 를 가리키 고 있 을 경우 , 참조 횟수 가 0 이 되 지 않 게 된다 . 이 를 순환 참조 라고 하 며 , 메모리 누수 의 원인 이 된다 . CPython 은 이 문제 를 해결 하 기 위해 순환 참조 를 감지 하 는 알고리즘 을 사용 한다 . 또한 자료 구조 에서 약한 참조 ( 참조 횟수 를 증가 시키 지 않 는 포인터 ) 를 사용 하 여 이 문제 를 해결 할 수 도 있 다 . 
 멀티 스레드 환경 에서 는 , 스레드 간 에 공유 하 는 객체 의 참조 횟수 계산 을 위해 원자 적 명령 을 사용 하 거나 락 을 걸어야 한다 . 이 문제 를 회피 하 기 위해 스레드 단위 지역 변수 로 참조 횟수 를 따로 관리 하 면서 , 스레드 의 참조 횟수 가 0 이 될 때 만 전역 참조 횟수 를 확인 하 는 방식 을 사용 할 수 있 다 . 리눅스 커널 에서 이 방식 을 사용 한다 . 
 참조 횟수 가 0 이 될 때 , 해당 객체 가 가리키 는 다른 객체 들 또한 동시 에 0 으로 만드 는 작업 이 일어난다 . 이 과정 은 경우 에 따라 많 은 시간 이 걸릴 수 도 있 기 때문 에 실시간 시스템 에 는 적합 하 지 않 을 수 있 다 . 
 쓰레기 수집 기법 을 사용 하 는 언어 편집 
 많 은 현대 언어 들 이 쓰레기 수집 기법 을 사용 한다 . C 와 C ++ 는 쓰레기 수집 기법 을 사용 하 지 않 지만 , 라이브러리 를 통해 쓰레기 수집 기법 을 사용 할 수 있 다 . 
 ML , 하스켈 , 얼랭 등 대부분 의 함수 형 프로그래밍 언어 는 쓰레기 수집 기법 을 지원 한다 . 특히 리스프 는 쓰레기 수집 기법 을 최초 로 사용 한 언어 이 다 . 
 자바 , 스몰토크 , 자바 스크립트 등 의 객체 지향 언어 들 은 대부분 쓰레기 수집 이 내장 되 어 있 다 . 그러나 델파이 와 C ++ 는 쓰레기 수집 을 사용 하 지 않 는다 . 오브젝티브 - C 는 쓰레기 수집 을 사용 하 지 않 았 으나 , OS X 에서 구현 된 ObjC 2 . 0 에서 는 애플 에서 내부 적 으로 개발 한 쓰레기 수집 기 가 사용 된다 . 루비 등 의 일부 동적 타입 언어 또한 쓰레기 수집 을 지원 하 며 , 파이썬 , PHP 등 의 언어 는 참조 횟수 계산 방식 을 사용 한다 . 
 프로그래밍 초보 자 를 위해 설계 된 베이직 등 의 언어 또한 까다로운 메모리 관리 를 자동 으로 지원 하 기 위해 쓰레기 수집 기법 을 사용 한다 . 초창기 마이크로컴퓨터 에서 구현 된 베이직 의 경우 쓰레기 수집 이 이뤄지는 동안 프로그램 이 오랫동안 정지 하 는 등 의 동작 을 보였 다 . 
 ↑ “ Recursive functions of symbolic expressions and their computation by machine , Part I ” . 2013 년 10 월 4 일 에 원본 문서 에서 보존 된 문서 . 2012 년 11 월 13 일 에 확인 함 . 
 2020 년 6 월 22 일 ( 월 ) 16 : 59 에 마지막 으로 편집 됨 
 이 문서 는 2020 년 6 월 22 일 ( 월 ) 16 : 59 에 마지막 으로 편집 되 었 습니다 .