3.3 가비지 컬렉션 알고리즘

• 가상 머신 또는 플랫폼따라 가컬 알고리즘 차이가 큼
• 이번 절에서 소개하는 알고리즘은 주류 가상 머신이 쓰는 추적 GC들
  • 참조 카운팅 GC는 주류에서 안써서 패스

3.3.1 세대 단위 컬렉션 이론

• 현재 상용 가상 머신들이 택한것은 대부분 세대 단위 컬렉션 이론에 기초해 설계됨
  • 이 이론 본질은 대다수 프로그램에서 관측된 실제 상황들에서 얻은 경험 법칙을 구현한 것
  • 기본적으로 다음 두가지 가정이 뿌리
    • 1. 약한 세대 가설(weak generational hypothesis): 대다수 객체는 일찍 죽는다.
    • 2. 강한 세대 가설(strong generational hypothesis): 가비지 컬렉션 과정에서 살아남은 횟수가 늘어날 수록 더 오래 살 가능성 커진다
• 위 2가지 가정 합쳐져서 널리 알려진 가컬들에 일관된 설계 원칙을 제공
  • 자바 힙을 몇 개의 영역으로 나누고 객체들이 나이에 따라 각기 다른 영역에 할당 하는 것
  • 나이: 가비지 컬렉션에서 살아남은 횟수!
• 영역 안의 객체 대부분이 곧바로 죽을 운명이라면, 그 객체들을 한데 몰아넣고(곧 회수될 다수의 객체에 표시하는 대신-) 살아남는 소수의 객체를 유지하는 방법에 집중하는 편이 유리
  • 확실히 적은 비용으로 대량의 메모리 확보 가능
  • 한 번 살아남은 객체는 통계적으로 잘 안죽으니 다른 영역에 따로 모으고, 가상 머신이 그 영역을 회수하는 빈도를 줄이는 것
  • 이러면 가컬에 드는 전체 시간도 줄고 메목리 공강도 효율적 이용가능
• 힙을 여러 영역으로 나누면 가컬은 한번에 하나 또는 다수의 영억만 선택해 회수 가능한데 이를 기준으로 마이너 GC, 메이저 GC, 전체 GC, 식으로 부르곤 함
  • 각 영역에 담긴 객체들의 생존 특성에 따라
    • 마크-스윕(mark sweep: 표시 후 쓸기)
    • 마크-카피(mark copy: 표시 후 복사)
    • 마크-컴팩트(mark compact: 표시 후 모으기)
  • 로 구분
• 세대 단위 컬렉션 이론을 가상 머신에 적용한 설계자 들은 자바 힙을 최수 2 개 영역으로 나눔
  • 신세대, 구세대
  • 신세대: 가비지 컬렉션 때마다 다수의 객체가 죽고 살아남은 소수만 구세대로 승격 됨
• 생각해 보면 시 세대 단위 컬렉션이 단순히 메모리 영역을 나누는것뿐이 아님을 알 수 있음
  • 예를들어 객체들은 단독 존재하는 게 아니기에 다른 세대에 존재하는 객체들을 참조하는 상황이 자연스럽게 나타남
• 신세대에서만 가컬을 하고싶더라도(마이너 GC), 신세대에 속하지만 구세대에서 참조 중인 객체도 있을 수 있음
  • 따라서 살아남을 객체를 찾으려면 도달 가능성을 분석할 때 고정된 GC 루트들 뿐만 아니라 구세대 객체 까지 모두 탐색해야 결과를 신뢰가능
  • 반대도 마찬가지
  • 구세대 전체의 객체까지 탐색하는게 이론적으론 가능한데 실제로는 성능면에서 부담이 큼
  • 이 문제 풀려면 세대 단위 컬렉션 이론에 세 번째 경험 법칙을 추가해야함!
• 3. 세대 간 참조 가설(intergenerational reference hypothesis): 세대 간 참조의 개수는 같은 세대 안에서의 참조보다 훨씬 적다.
• 세번째 가설은 사실 처음 두가지 가설로 부터 논리적으로 유추 가능한 암묵적 추론
  • 상호 참조 관계의 두 객체는 삶과 죽음을 함께하는 경향 있음
  • 예) 신새대 객ㄱ체가 세대 간 참조를 가지고 있다고 해보자구. 구세대는 잘 안죽음. 따라서 가비지 컬렉션 거쳐도 신세대 객체는 세대 간 참조 덕에 구세대로 승격 될 것. 그러면 같은 세대가 되었으니 세대 간 참조는 자연스럽게 없어짐
• 이 가설 따르면 세대 간 참조 수는 아주 적기에 구세대 전체 훓는건 낭비
  • 또한 어떤 객체들이 존재하고 어떤 세대 간 참조 있는지 기록하느라 공간 낭비할 필요도 없음
  • 그저 신세대에 기억 집합 이라는 전역 데이터 구조 하나 두면 됨
  • 이 구조 통해 구세대를 작은 조각 몇 개로 나누고 그 중 어느 조각에 세대간 참조 있는지 기록해 관리하는 것
  • 그리고 마이너 GC가 수행되면 세대 간 참조 포함하는 작은 메모리 블록 안의 객체들만 GC 루트에 추가된다
  • 이 방식에서 객체 사이에서의 참조 관계 변화를 정확히 관리해야함
  • 그래서 런타임에 할 일 늘어나지만 구세대 전체 훓는 비용보다는 쌈

세대 단위 컬렉션에서 다양한 GC 방식

• 부분 GC: 자바 힙의 일부만 회수하는 GC 말하며 다음과 같이 세분화
  • 마이너 GC(신세대 GC): 신세대 대상 GC
  • 메이저 GC(구세대 GC): 구세대 대상 GC. 책 집필 시점 기준 오직 CMS 컬렉터만 구세대를 따로 회수함. 메이저란 단어가 혼동 줄 수 있는데 문헌 따라 다를수 있음. 전체 회수인지 구세대 회수인지 맥락으로 구분잘하기
  • 혼합 GC: 신세대 전체와 구세대 일부를 대상 GC. 집필 시점 기준 G1 컬렉터만 이렇게 동작
• 전체 GC: 자바 힙 전체와 메서드 영역까지 모두를 대상으로 하는 GC

3.3.2 마크-스윕 알고리즘

• 마크 스윕은 리프스의 아버지 존 맥카시가 1960에 제안한 최초이자 기본적인 카컬 알고리즘
  • 이름처럼 이 알고리즘은 작업을 mark와 쓸기(sweep)이라는 두 단계로 나누어 진행
    • 먼저 회수할 객체에 모두 표시
    • 이후 표시된 객체 쓸어 담기
  • 표시 단계는 객체가 쓰레기인지 판단하는 과정
• 이게 가장 기본적인 알고리즘인 이유는 이어 나온것들이 이 알고리즘을 기초리 단점을 보완하는 식으로 발전했기 때문.
• 단점은 2가지
  • 첫째, 실행 효율이 일정하지 않다. 힙이 다량의 객체로 가득 차 있고 그 대부분이 회수 대상이라면 표시하는 일, 회수하는 일 모두 커짐. 즉, 객체 많을수록 효율 떨어짐
  • 둘째, 메모리 파편화 심함. GC가 쓸고간 자리에는 불연속적인 메모리 파편 만들어짐. 파편화 너무 심하면 프로그램이 큰 객체 만들려 할때 충분한 크기의 연속 메모리 찾기 점점 여려워지고, 그 결과 또 GC 유발

3.3.3 마크 카피 알고리즘

• 카피 알고리즘 이라고도 함
  • 회수할 객체 많아질수록 효율 떨어지는 마크 스윕 개선위해 등장
  • 69년 로버트 페니첼이 세미스페이스복사 라는 가컬 알고리즘 제안
  • 이 알고리즘은
    • 가용 메모리를 똑같은 크기의 두 블록으로 나눠 한 번에 한 블록만 사용
    • 한쪽 블록이 다 차면 살아남은 객체들만 다른 블록에 복사하고 기존 블록을 한 번에 청소
• 대다수 객체가 살아남는다면 메모리 복사에 시간 허비하는 반면, 대다수가 회수 된다면 생존한 소수의 객체만 복사혀면됨
  • 또한, 복사 과정에서 객체들이 메모리의 한쪽 끝에서부터 차곡차곡 쌓이기에 골치 아픈 메모리 파편화문제로 부터 해방됨
• 이 알고리즘은 구현 쉽고 실행 효율도 좋음
  • 하지만 단점이 바로 가용 메모리를 절반으로 줄여 낭비가 꽤 심한것
• 오늘날 상용 자바 가상 머신들 대부분은 이 알고리즘 활용
• IBM은 ‘객체들의 생존 기간이 짧다’는 신세대 특성을 더 정량적으로 해석하고자 특별한 연구 수행.
  • 그 결과, 신세대 객체중 98%가 첫 번째 가컬때 살아남지 못함.
  • 즉, 신세대용 메모리 영역을 1:1로 나눌 필요 없다는 결론
• 89년 앤드류 아펠은 이 특성 반영해 더 최적화된 전략 제안
  • 요즘은 아펠 스타일 컬렉션이라 부름
  • 시리얼, 파뉴 같은 핫스팟 가상 머신의 신세대 컬렉터는 모두 신세대 메모리의 레이아웃을 이 전략에 부합하게 구성
• 아펠 스타일 컬렉션 방식
  • 먼저 신세대를 하나의 큰 에덴 공간과 두 개의 작은 생존자 공간으로 나눈다.
  • 그리고 메모리 할당 시에는 생존자 공간 중 하나와 에덴만 사용!
  • 가컬이 시작되면 에댄과 생존자 공간에서 살아남은 객체들은 나머지 생존자 공간으로 하나씩 복사 후 에덴과 이전 생존자 공간 곧바로 비움
• 핫스팟 에서 에덴과 생존자 공간의 비율은 기본적으로 8:1
  • 즉, 신세대에 할당 된 전체 메모리중 90%를 활용(에덴 80% + 생존자 공간 중 하나 10%)
  • 낭비되는 공간은 10% 뿐
• 98% 객체가 회수 되는 데이터는 물론 ‘일반적 상황’에서 측정된 결과라서, 10% 넘게 살아남는 일이 절!대! 없다고는 말 못함
  • 그래서 아펠 스타일에서도 10%넘는 특이 케이스 대처하기 위한 설계하나가 추가되어 있음
  • ‘메모리 할당 보증’ 메커니즘. 마이너 GC 에서 살아남은 객체를 생존자 공간에서 다 수용 못할 경우 다른 메모리 영역(대부분 경우 구세대)을 활용해 메모리 할당을 보증하는 것(핸들 승격)
• 메모리 할당 보증은 돈을 빌리러 은행에 방문하는 일에 비유 가능
  • 고객 평판이 좋다면 은행은 고객이 돈을 제때 상환 가능하다 믿고, 보증인 한 명만 데려오면 위험하지 않다고 판단할 것.
  • 메모리 할당 보증도 같다.
  • 신세대 가컬에서 살아남은 객체들을 생존자 공간에 다 못담으면, 할당 보증 메커니즘 통해 객체들을 구세대에 바로 추가

3.3.4 마크 컴팩트 알고리즘

• 마크 카피는 객체 생존율 좊을수록 복사할 게 많아 비효율이 됨
  • 게다가 공간 50% 낭비 싫다면 할당 보증용 공간 따로 마련하여 대다수 객체 살아남는 상황도 대처해야함
  • 그래서 구세대에는 부적합
• 구세대 객체들의 생존 특성 감안하여 에드워드 루더스는 마크 컴팩트 알고리즘을 74년에 제안
  • 표시 단계는 마크 스윕과 같다. 하지만 다음 컴팩트 단계에서(회수 대상 객체들을 곧바로 쓸어 담는 대신) 생존한 모든 객체를 메모리 영역의 한쪽 끝으로 모은 다음, 나머지 공간을 한꺼번에 비운다
  • 마크 스윕과의 핵심적 차이는
    • 메모리 이동이 일어난다는 점
  • 그런데 가컬 후 살아남은 객체를 이동할지는 양날의 검 같은 결정
  • 특히 구세대에서는 회수 때마다 살아남는게 많을 것
    • 따라서, 생존한 객체를 이동시킨 후, 이동된 객체들을 가리키던 기존 참조들을 모두 갱신하기는 매우 부담될것
    • 더욱이 이런 식의 객체 이동은 사용자 애플리케이션을 모두 멈춘 상태에서 진행해야 하므로 신중히 고려해야 할 단점
    • 이런 정지 현상을 초기 가상 머신 설계자는 “스톱 더 월드”라는 말로 아주 잘 표현함
• 하지만, 마크 스윕 처럼 살아있는 객체 전혀 이동안시키면 힙이 파편화 됨
  • 결국은 메모리 할당과 접근 방식을 더 복잡하게 만들어야하는 것
  • 예컨데, 메모리 할당 문제는 파편화 없는 할당 연결 리스트(partition free allocation linked list)로 해결 가능
  • 메모리 읽기는 사용자 프로그램에서 단연 빈번히 일어나는 동작
  • 이동작 수행하는 부담 커지면 성능 느려질건 뻔함
• 이상의 두 관점에서 객체 이동시킬 때와 아닐 때 모두 단점 존재
  • 객체 이동 시, 회수 작업 복잡
  • 객체 그냥 두면, 할당 작업 복잡
  • 가컬 시의 ‘일시 정지 시간’ 기준으로 판단하면 이동안시키는 게 유리
    • 정시 시간 짧아지거나 정지 안시켜도 될것
  • 하지만, 전체 프로그램의 ‘처리량’이 기준이라면 객체를 이동시키는 편이 효율적
    • 지금 맥락에서 처리량은 사용자 프로그램와 가컬에서의 효율을 포괄하는 개념
  • 객체 이동 안시키면, 컬렉터 효율 높아짐.
  • 하지만, 메모리 할당하고 접근하는 빈도가 가컬 수행 빈도보다 훨씬 많으므로 할당과 접근 효율 떨어지면 전체적 처리량은 여전히 나빠짐
• 핫스팟에서 처리량에 중점 둔 ‘패러렐 올드 컬렉터’는 마크 컴팩트 알고리즘에 기초하고, 지연 시간에 중점을 둔 ‘CMS 컬랙터’는 마크 스윕 알고리즘에 기초한다는 점도 이런사실 간접적으로 확인해줌
• 메모리 할당과 접근에 부담 많이 안주는 축복받은 해법도 있음
  • 대부분의 경우에는 메모리 파편화 감내하면서 마크 스윕 쓰다가, 객체 할당에 영향 줄 만큼 파편화가 심해지면 마크 컴팩트를 돌여 연속된 공간을 확보하는 것
  • 앞서 CMS는 마크-스윕이 기본이라 했는데, 메모리 파편화 심해지면 이 전략 실행하여 단점을 보완함!!