2019년 10월 31일 목요일

가비지 콜렉션(Garbage Collection) - 할당(Allocation), 단편화(Fragmentation), 힙분할(Partitioning the heap)

가지지 콜렉션(Garbage Collection)

메모리 관리 시스템에서 살펴 볼 세 가지 측면

  1. 최초의 메모리 할당
  2. 라이브 데이터의 식별
  3. 이전에 할당 되었지만, 현재는 죽은 객체가 점유한 메모리의 회수

자동해제와 명시적 해제의 중요한 차이점

  1. 한꺼번에 모든 공간을 해제
  2. 할당할 때, 가비지 컬렉팅에 이용해야 하는 정보를 좀 더 추가해서 할당 한다.
  3. 프로그램 작성 스타일이 달라진다. 좀 더 잦은 힙 할당을 사용한다.

할당(Allocation)

할당전략

  • 순차 할당
    • 한쪽 끝에서 부터 할당하는 전략
  • 프리리스트 할당
    • 할당 가능한 공간에 대한 자료구조를 별도로 관리하는 전략
  • 자바에서 둘 사이의 성능 차이는 전체 실행 시간의 1% 정도
  • 캐시 지역성에서는 순차할당이 우세(이동식 컬렉터)
  • 단편화가 발생한 경우는 프리리스트 우세(비이동식 컬렉터)

순차할당

sequentialAllocation(n) :
    result <- free
    newFree <- result + n
    if newFree > limit
        return null
    free <- newFree
    return result

프리리스트 할당

firstFitAllocate(n):
    prev <- addressOf(head)
    loop
        curr <- next(prev)
        if curr = null
            return null
        else if size(curr) < n
            prev <- curr
        else
            return listAllocate(prev,curr,n)

헤드 포인터(head pointer)에서 부터 셀을 탐색, null 이면 메모리 고갈, 현재 포인터의 셀의 크기가 n 보다 작은 경우는 다음 포인터로 listAllocate에서 실제로 할당 해줌

할당하고자 하는 셀의 크기가 n보다 큰 경우에는 셀을 분할해서 할당 할 수 있게 해주고, 분할된 셀의 남은 공간은 다시 프리리스트로 반환한다.

listAllocate(prev,curr,n):
    result <- curr
    if shouldSplit(size(curr),n)
        remainder <- result+n
        next(remainder) <- next(curr)
        size(remainder) <- size(curr) - n
        next(prev) <- remainder
    else
        next(prev) <- next(curr)
    return result

프리리스트 할당 종류

  • 최초적합할당
    • 루프 돌면서 공간할당요청을 충족할 수 있는 발견된 최초의 셀에 할당
    • 셀 분할 후 남게 되는 작은 셀은 리스트의 앞쪽에 쌓이게 된다.
    • 점점 할당을 느리게 하는 요인
  • 차선적합할당
    • 리스트에서 마지막 탐색이 성공한 지점부터 적당한 크기의 셀을 찾기 시작
    • 리스트 끝에 도달하면 처음 부터 다시 시작
    • 리스트의 앞부분에 존재하는 작은 크기의 셀을 반복적으로 탐색하지 않아도 된다.
  • 최적적합할당
    • 요청 크기와 가장 일치하는 세을 찾는다.
    • 공간 낭비는 적지만, 할당으로 인한 성능이 떨어진다.

단편화(Fragmentation)

  • 프로그램을 실행하고, 할당과 해제가 반복됨에 따라 많은 수의 프리 셀을 양산
  • 부정적 영향
    • 실제로 요청을 만족시킬 만한 충분한 양의 프리메모리가 존재하지만 프리 셀 중에 이 요청을 만족시킬 만큼의 크기를 가진 셀이 존재 하지 않을 수 있음
    • 명시적 해제 프로그램은 보통 강제 종료
    • 자동 해제 프로그램은 GC발생
  • 이상적인 최적의 할당
    • 할당과 해제 요청이 성공적으로 이뤄질 수 있는 전체 순서를 정하고 이에 필요한 가장 작은 공간을 사용한다.
    • NP-hard 문제이다.

단편화의 Worst case



힙분할(Partitioning the heap)

  • 모든 객체가 동일한 컬렉션 알고리즘에 의해 관리될 필요는 없다.
  • 컬렉터가 상이한 범주의 객체들을 이동시키기를 원하는지, 원한다면 어떻게 이동시킬 것인지에 따라 다르게 관리할 수 있음

분할이유

  • 이동성에 의한 분할
    • 이동 가능한 객체와 그렇지 않은 객체를 구분(예를들어 커널로 전달되어 I/O가 수행되는..)
  • 크기에 의한 분할
    • 큰 객체는 옮기지 않는 것이 바람직
  • 공간에 의한 분할
    • 빠른 할당과 우수한 공간지역성을 보유한 전략으로 관리하는 공간에 객체를 생성하는 것이 바람직
    • 수명이 길고 단편화가 급하지 않으면 비이동식 컬렉터가 주로 관리
    • 할당비율이 상대적으로 높고 수명이 얼마남지 않은 객체는 빠른 할당과 저렴한 수집비용을 위해 복사컬렉터의 관리하에 있는 공간
  • 효율성을 위한 분할
    • 대부분의 객체는 젊어서 죽는다.

정지시간 단축을 위한 분할

  • 복사 컬렉터의 수집 비용은 라이브 객체의 양에만 좌우
  • 마크 스윕의 경우에는 수집 비용이 주로 스윕 비용
  • 컬렉터가 추적하는 수집 예정 공간의 크기를 제한함으로써 수집 또는 마킹된 객체의 양을 제한해 결과적으로 가비지 컬렉션에 필요한 시간을 제한

지역성을 위한 분할

  • 메모리 계층이 갈수록 복잡해짐에 따라 지역성의 중요성이 커짐
  • 예)부모 객체와 자식 객체를 함께 배치
  • 여유공간을 반환할 가능성이 높은 힙의 부분집합에 노력을 집중

스레드에 의한 분할

  • 자신의 스레드에서 할당 했지만, 다른 스레드가 접근할 수 없게 된 객체만을 수집한다면 스레드간 동기화 비용을 줄일 수 있음

가변성에 의한 분할

  • 최근에 생성된 객체는 예전에 생성된 오래된 객체보다 더 자주 변경되는 경향이 있음.
  • 참조 카운팅 기반 메모리 관리자는 갱신 때 마다 높은 오버헤드를 유발하는 경향이 있어서, 변경 빈도가 많은 객체에는 부적합
  • 매우 큰 힙에서는 비교적 적은 비율의 객체만이 특정 기간 내에 변경되지만, 추적 컬렉터는 GC대상이 되는 항상 모든 객체를 방문

가장 유명한 분할 기법

  • 객체를 나이에 따라 구분하고 좀 더 젊은 객체를 우선적으로 수집하는 세대 컬렉션(Generational collection)
게시:
라벨: ,