GC(Garbage Collection)란 무엇인가?
흔히 메모리 관리 방식은 2가지로 나뉜다
Manual 과 GC이다.
수동 메모리 관리(Manual Memory Management) 와 자동 메모리 관리(Garbage Collection,GC)이다.
수동 메모리 관리는?
개발자가 직접 메모리 할당과 해제를 관리하는 방식이다.
대표적인 언어로 C,C++ malloc/free,new/delete 등등 개발자가 직접 메모리를 할당 해제한다.
장점으로는 정밀한 제어를 통한 메모리 할당 해제 시점을 프로그래머가 완전히 통제 가능하며
예측 가능한 성능이기때문에 GC의 불필요한 오버헤드가 존재하지 않는다.
또한 필요 없는 메모리를 즉시 해제해 리소스를 절약할 수 있다.
다만, 단점은 *메모리 누수(Memory Leak)가 존재하며, *댕글링 포인터(Dangling Pointer)가 존재하며 개발이 복잡해진다는 것이다.
*메모리 누수: 할당된 메모리를 해제 않아서 프로그램이 종료될때까지 누적되는 현상, 시스템 메모리 고갈로 크래시를 발생시킬 수 있다.
**댕글링 포인터:이미 해제된 메모리를 참조할 경우 예측 불가능한 동작이 발생함
최근에는 Rust는 수동 메모리의 관리의 대안으로 소유권 시스템(OwnerShip System)을 통해 메모리를 안전하게 관리하는데, 이는 완전한 수동 메모리 관리라기보다는
수동 메모리 관리의 새로운 대안이라고 여겨진다.
GC는 프로그래밍 언어에서 더 이상 사용되지 않는 메모리를 자동 해체하는 기능인데, 이제 이 글에서 설명할 것이다.
자유 저장소 목록 (Free-Storage List)
어느 시점에서든지, 리스트 구조를 저장하기 위해 예약된 메모리의 일부만이 실제로 S-표현식(S-expressions)을 저장하는 데 사용됩니다.
나머지 레지스터들(우리 시스템에서는 초기에 약 15,000개 정도)은 **자유 저장소 목록(free-storage list)**이라는 단일 목록으로 구성됩니다.
프로그램 내의 특정 레지스터인 FREE는 이 목록의 첫 번째 레지스터 위치를 포함합니다.
추가적인 리스트 구조를 구성하기 위해 단어(word)가 필요할 때, 자유 저장소 목록의 첫 번째 단어가 사용되고, 레지스터 FREE의 값은 자유 저장소 목록의 두 번째 단어 위치로 변경됩니다.
사용자가 레지스터를 자유 저장소 목록으로 반환하는 것을 프로그래밍할 필요는 없습니다.
-Recursive Functions of Symbolic Expressions Their Computation by Machine, Part I John McCarthy
자유 저장소 목록(Free-Storage List)은 초기 LISP 시스템에서 자동 메모리 관리를 구현하는 기초적인 개념이었다.
당시 LISP는 동적으로 리스트 구조를 생성하는 방식이었고, 프로그래머가 명시적으로 메모리를 해제하는 것이 어려웠다
.
이를 해결하기 위해, 사용되지 않는 메모리 블록을 추적하는 Free-Storage List 개념이 자동 메모리 관리 개념으로 발전했다.
특정 레지스터(FREE)에 가용 메모리 리스트의 시작 위치를 저장하고, 필요할 때 가져오고, 더 이상 사용되지 않는 경우 다시 반환하는 방식이었다.
이 아이디어는 이후 Mark-and-Sweep 방식의 GC의 기반이 되었다.
(GC의 구현방식 및 아이디어 상세설명은 다음섹션에서 이야기하겠다)
컴퓨터에 리스트를 저장하기 위한 뉴얼-쇼-사이먼(Newell-Shaw-Simon) 방식의 중요한 특징은
동일 데이터가 여러 번 발생하더라도 컴퓨터 내 한 곳에만 저장될 수 있다는 점입니다. 즉, 리스트들이 "중첩(overlapped)"될 수 있습니다.
그러나 이러한 중첩은 이후 삭제(erasure) 과정에서 문제를 일으킵니다. 더 이상 필요 없는 리스트가 주어졌을 때,
다른 리스트와 중첩되지 않은 부분만을 선택적으로 삭제해야 합니다. LISP에서는 매카시(McCarthy)가 이 문제에 대해 우아하지만 비효율적인 해결책을 제시했습니다.
본 논문은 효율적인 삭제를 가능하게 하는 일반적인 방법을 설명합니다. -"A Method for Overlapping and Erasure of Lists" (1963) George E. Collins
존 맥카시의 논문이 mark-and-Sweep 방식의 기반이 되었지만, GC실행시 프로그램이 멈추는 Stop - the - World 현상이 발생했다.
이는 실시간 GC를 구현하기 어렵게 만들었고, 콜린스는 Reference Counting(참조 카운팅) 개념을 GC방식으로 제안
각 객체에 참조 횟수(Reference Count)를 저장하여 참조가 0이 되면 즉시 메모리를 회수 하는 방식을 제안한다.
Collins(1960)는 Reference Counting GC를 제안하여 즉시 메모리 회수를 가능하게 했지만, 순환 참조 문제로 인해 완벽한 해결책은 아니었다.
Python, Swift 등 현대 언어에서도 여전히 사용되지만, 보완 기법이 추가되었다
(여담이지만 '우아하지만 비효율적'이다라니 엣날부터 생각하지만 전반적으로 프로그래머의 직업적 특징인지 모르겠으나
프로그래머들은 주로 상대방을 '우아하게' 비꼬는 재주가 있다. 아무래도 실체가 없는 추상적 개념에 대한 이야기를 하니까
실체적 폭력에 대한 존재가 옅어져서 그런게 아닐까 싶기도하다. 한국에서는 이러면 보통 물리적 실체인 주먹으로 응징을 당할텐데 말이지.)
본 논문에서는 매우 큰 가상 메모리 환경에서 동작하는 리스트 처리 시스템을 위한 가비지 컬렉션 알고리즘을 제안합니다.
이 알고리즘의 주요 목적은 "여유 메모리 확보"보다는 **활성 메모리의 압축(compaction)**에 있습니다.
가상 메모리 시스템에서는 여유 메모리가 실제로 고갈되지 않기 때문에, 가비지 컬렉션 실행 시점을 결정하기가 쉽지 않습니다.
따라서 본 논문에서는 가비지 컬렉션 트리거 조건에 대한 다양한 기준을 논의합니다. -"A LISP Garbage Collector for Virtual-Memory Computer Systems" (Fenichel & Yochelson, 1969)
(가상메모리(Virtual Memory):물리적 메모리 크기를 넘어서는 대용량 메모리를 논리적으로 관리하는 기술)
이 논문은 Minsky의 복사방식 GC(Copying GC)를 개선하여, 가상 메모리(Virtual Memory)에서 효율적으로 동작하는 방법을 기술한 논문이다.
본 논문은 Misnky의 가비지 컬렉터, 깊이 우선 탐색 (DFS, depth-first-serach)을 이용해 도달가능한 데이터를 보조 저장소에 복사하고, 이를 새로운 연속된 주소에 할당한 후 다시 메모리로 로드 하는 방식을 실제적으로 구현한 논문인데, 완성도가 떨어진다는 이야기가 있지만
이 논문은 Minsky의 방법을 기반으로 "Copying GC"를 현대적인 가상메모리 환경에 적용한 첫 논문이고, 이 논문이 없었다면
자바와 C#의 Generational GC 개념이 등장하지 못했을 것이다.
"간단한 비재귀적(nonrecursive) 리스트 구조 압축 기법 또는 가비지 컬렉터가 제시됩니다.
이 알고리즘은 컴팩트(compact)한 구조와 LISP 스타일의 리스트 구조 모두에 적용 가능합니다.
재귀(recursion)를 사용하지 않고, 복사된 리스트를 추적하기 위해 부분 구조(partial structure)를 점진적으로 활용함으로써 재귀 의존성을 제거했습니다."- (C. J. Cheney, 1970)
이후 깊이 우선 탐색(DFS) 에서 너비 우선 탐색(BFS,Breadth-Frist Search)를 사용한 '비재귀(Nonrecursive)' GC를 제안하는데, 이는 스택 없이도 GC가 가능하도록 설계된다
이 연구의 의의는 오늘날 Jav,C#,Python의 Copying GC 방식에 큰 영향을 주고 BFS, 기반이라 스택 오버플로우 문제를 방지하고, 캐시친화적 구조를 가진다.
BFS가 DFS랑 다르게 비재귀적인 방식으로 구현 된 이유
우선 독자 제언들 대부분 알겠지만 스택은 LIFO(Last in, First Out, 후입선출) 구조를 따르는 구조이다. 가장 마지막에 추가된 요소가 가장 먼저 제거된다.
큐는 FIFO(First in, First Out, 선입선출) 구조를 따르는 자료구조다. 즉 가장 먼저 추가된 요소가 가장 먼저 제거된다.
DFS는 한쪽 방향으로 끝까지 탐색한 후, 돌아오는 방식(백트래킹)을 사용하는데, 이를 위해 스택(Statc)이나 재귀함수(Recursive Call)을 사용해야한다.
DFS의 Stack 기반 원리는 다음과 같다.
1. 현재 노드를 방문 스택(or재귀 호출)으로 저장
2. 다음 방문할 노드가 있으면 스택 호출(or 재귀호출) 하여 계속 진행
3. 더 이상 진행할 곳이 없으면 백트래킹(되돌아가기) 실행
BFS는 Queue 기반이 원리
1. 탐색을 시작할 노드를 큐에 추가(Enqueue)
2. 큐에서 하나씩 꺼내(Dequeue) 방문 처리 후, 인접 노드들을 다시 큐에 추가
3. 모든 노드를 탐색할까지 반복.
큐를 사용하기때문에 별도의 재귀 호출이 존재하지 않는 것이다.
동굴 탐험을 예시로 들어보자
DFS는
동굴을 탐험할 때, 한 길을 따라 끝까지 들어간 후에, 길이 막히면 되돌아가서 새로운 길을 탐색하는 방식이다.
길이 막혔을 때 되돌아갈 경로를 기억(저장)해야 돌아갈 수 있지 않겠는가?
BFS는
동굴 입구에 팀을 배치하여 모든 갈림길을 동시에 탐색하고, 1층의 모든 길을 먼저 확인한 후, 다음 층으로 내려간다.
적절한 팀 배치를 위해서는 먼저 도착한 갈림길부터 인원을 우선 배치해야 하지 않겠는가?
자 그럼 현대적 연표를 요약해보자
| 연도 | 연구자 | GC 알고리즘 | 개선된 점 | 문제점 |
|---|---|---|---|---|
| 1960 | John McCarthy | Mark-and-Sweep | 최초의 GC 개념 도입 | Stop-the-World, 단편화 문제 |
| 1963 | Marvin L. Minsky | Copying GC (DFS 기반) | 메모리 단편화 해결, 캐시 최적화 | 순환 참조 문제, 디스크 사용 |
| 1969 | Fenichel & Yochelson | Copying GC (Virtual Memory 적용) | 두 개의 반공간(Semispaces) 사용 | 메모리가 부족하면 프로그램이 느려짐 |
| 1970 | C. J. Cheney | Nonrecursive Copying GC (BFS 기반) | 스택 사용 없이 GC 가능 | BFS 기반이라 메모리 재배치 최적화가 덜 됨 |
이 GC 알고리즘 발전의 의미는 무엇일까? Stop-the-World 문제를 줄이고, 실시간 (Concurrent)GC로 발전하는 과정을 우리는 이제 확인해보았다.
(코드내에서 C++의 RAII을 따라 shared_ptr을 사용할 경우 실제로 GC 동작 관측이 어렵기때문에 원시 포인터를 사용해야한다)
(이미지 출처 : https://deepu.tech/memory-management-in-v8/)
2. Reference Counting(참조 횟수)
(전역 참조 테이블 unordered_map을 사용하여, 객체 생성시 참조 카운트를 1로 초기화하고, addRef와 releaseRef 를 통해 참조횟수 조절하고, 참조 카운트가 0일 경우 delete 호출)
| 구분 | Tracing GC (Mark & Sweep) | Reference Counting GC |
|---|---|---|
| 기본 개념 | 루트에서 추적하여 객체를 검사 후 정리 | 객체의 참조 카운트를 기준으로 메모리 해제 |
| 메모리 누수 가능성 | 순환 참조(Strong Reference) 가능 (GC가 자동 해결) | 순환 참조 시 메모리 누수 발생 |
| GC 실행 비용 | 객체 수와 참조 그래프 크기에 비례 | 객체가 많아질수록 계산 부담 증가 |
| 성능 | 객체 수가 많을수록 성능 저하 가능 | 참조가 즉시 0이 되면 빠르게 해제 가능 |
| Stop-the-World(STW) | GC 실행 시 멈춤 발생 | 즉시 해제 가능하므로 멈춤 없음 |
| 대표적인 사용 사례 | C#, Java, Python | Objective-C (ARC), Swift |
일반적으로 가장 유명한 것은
1. STOP-the-World(STW)
GC 실행시 프로그램이 완전히 멈춘다.
전통적인 방식의 GC로써 GC 구현이 상대적으로 단순하며, 정확한 메모리 회수가 가능하다.
하지만 역시 응답시간의 증가로 사용자 경험 저하가 있다.
2.Incremental GC(점진적 GC)
이미지출처(https://databases.systems/posts/visualizing-the-go-gc)
GC를 여러 작은 단계(Small Steps)로 나누어 실행, Dijkstra의 Tri-Color Marking Algorithm을 기반으로 구현되었다.
이 알고리즘을 요약하면 3색을 어떻게 효율적으로 칠하느냐의 문제인데
이것이 GC와 어떻게 연결되는지 설명하겠다.
객체를 처리되지 않음(unprocessed) , 처리중(processing), 처리됨(processed) 3가지로 나누고
흰색 : 처리되지 않음 unprocessed
회색: 처리 중 processing
검은색: 처리 됨 processed
로 나눈 후, 노드를 색칠하는 알고리즘이다.
1. 모든 노드는 흰색으로 시작
2. 객체에 방문하면 회색
3. 방문이 끝났으면 검은색
이렇게 3가지 개체 집합이 생기고, 객체는 흰색->회색->검은색으로 이동하는데, 여기서 알 수 있는 사실은 흰색과 검은색이 직접 연결되지 않는 것이다.
3. Concurrent GC(병렬 GC)
GC와 애플리케이션 실행이 동시에 수행되고 STOP-the-World 시간을 최소화한다.
GC 스레드가 별도로 동작하고, 애플레케이션의 다른 스레드와 동시에 메모리 탐색(mark)나 복사 같은 작업을 수행한다.
이로 인해 GC 수행중에도 애플리케이션이 동작하고,다중 코어를 활용하지만, 메모리 관리가 더욱 복잡해진다.
조기 최적화는 모든 악의 근원이다- 도널드 커누스(Donald Knuth)
이 글에서는 GC의 역사와 현재 쓰이는 GC 알고리즘, 최적화 전략과 실행 방법을 썼다. 이후에 GC를 피하는 ZoC(Zero Allocation) 등도 있지만
이 글은 초보자를 대상으로 하기때문에, 초보자가 파악하기 어려워서 아쉽게도 생략하고, 일부 최적화 전략등을 생략했다.
직접 메모리를 다루는 것을 좋아하는 사람들은 GC를 악으로 여기며, 프로그래밍의 불확실성을 늘려준다고 말할지도 모르지만,
도널드 커누스가 말했듯 메모리 관리와 같은 '조기 최적화'에 매몰되기 보단, GC는 개발자로 하여금 '문제 해결'에 집중할 수 있게 해준다.
프로그래머의 역할은 단순히 기술을 숙지하는 것이 아니라, 당면한 문제를 해결하는 것이다.
GC는 많은 프로그래머들에게 '메모리 관리'라는 부담을 덜어주는 중요한 도구이다.
중요한 것은 'GC가 좋은가 나쁜가'가 아니라, '어떤 도구가 나의 문제를 해결하는 데 가장 적합한가'를 고민하는 것이라고 나는 생각한다.
너무 길다.
118.235로 의미없는 디시콘 달아서 념글컷 채우는 ㅆㅇㅆ https://archive.md/e52ei
118.235로 다중이질 하다가 닉변 까먹은 ㅆㅇㅆ https://archive.md/Yg4q9