가비지 콜렉션에 해시 테이블을 사용하면 마크 및 스윕의 세계 문제를 해결할 수 있습니까? 객체를 재배치 할 때 세계를

mark-sweep-compact 가비지 수집 알고리즘에서는 참조 그래프가 일치하지 않고 객체를 가리키는 모든 참조의 값을 바꿔야하므로 객체를 재배치 할 때 세계를 멈춰야합니다.

그러나 객체 ID가 키이고 포인터가 값으로 해시 테이블이 있고 참조가 객체 주소 대신 해당 ID를 가리키는 경우 참조를 수정하면 하나의 값만 변경하고 객체가 필요한 경우에만 일시 중지해야합니다 복사하는 동안 작성하려고합니다 …

내 생각에 실수가 있습니까?



답변

참조를 업데이트하는 것은 하지 일시 중지를 요구하는 유일한 것. 일반적으로 “mark-sweep”아래에 그룹화 된 표준 알고리즘은 전체 객체 그래프가 표시되는 동안 변경되지 않은 상태로 유지된다고 가정합니다. 수정 (새 객체 생성, 참조 변경)을 올바르게 처리하려면 3 색 알고리즘과 같은 까다로운 대체 알고리즘이 필요합니다. 포괄적 인 용어는 “동시 가비지 수집”입니다.

그러나 예, 압축 후 참조를 업데이트하면 일시 중지가 필요합니다. 그리고 예, 간접적 인 객체 ID와 실제 포인터에 대한 해시 테이블을 통한 간접적 인 사용은 일시 중지를 크게 줄일 수 있습니다. 원하는 경우이 부분을 잠금 해제 할 수도 있습니다. 낮은 수준의 공유 메모리 동시성만큼 올바르게 처리하는 것은 여전히 ​​까다로울 수 있지만 작동하지 않는 근본적인 이유는 없습니다.

그러나 심각한 단점이 있습니다. 여분의 공간 ( 모든 객체에 대해 적어도 두 개의 여분의 단어)을 취하는 것 외에도 모든 역 참조가 훨씬 비쌉니다. 속성을 얻는 것만 큼 간단한 것조차 이제 전체 해시 테이블 검색이 필요합니다. 증분 추적보다 성능이 떨어질 것으로 예상합니다.


답변

컴퓨터 과학의 모든 문제는 간접적 인 수준의 간접적 인 수준으로 해결 될 수있다.

귀하의 접근 방식은 가비지 수집 문제를 즉시 해결하지는 않지만 한 수준 위로 이동시킵니다. 그리고 어떤 비용으로! 이제 모든 메모리 액세스는 다른 포인터 역 참조를 거칩니다. 결과 위치는 이전에 재배치되었을 수 있으므로 결과 위치를 캐시 할 수 없으며 항상 개체 ID를 거쳐야합니다. 대부분의 시스템에서이 간접적 인 지시는 용납 될 수 없으며 세계를 막는 것은 총 런타임 비용이 더 낮은 것으로 가정합니다.

나는 당신의 제안이 문제를 해결할뿐 아니라 해결하지 못한다고 말했습니다. 이 문제는 객체 ID 재사용과 관련이 있습니다. 객체 ID는 이제 우리의 포인터와 동일하며 유한 한 양의 주소 만 있습니다. 프로그램 수명 동안 INT_MAX 개 이상의 객체가 생성되었을 것입니다 (예 : 32 비트 시스템에서).

while (true) {
    Object garbage = new Object();
}

각 객체의 객체 ID를 늘리면 어느 시점에서 ID가 부족합니다. 따라서 아직 사용중인 ID와 회수 할 수있는 ID를 찾아야합니다. 익숙한 소리? 우리는 이제 광장으로 돌아 왔습니다.


답변

당신의 생각에는 오류가 없습니다. 당신은 방금 원래 Java 가비지 컬렉터가 작동하는 방식에 매우 가까운 것을 설명했습니다.

원래 Java 가상 머신 [6] 및 일부 스몰 토크 가상 머신은 [6]의 핸들이라고하는 간접 포인터를 사용하여 객체를 참조합니다. 핸들을 사용하면 각 객체에 대한 하나의 직접 포인터 (핸들에있는 하나) 만 있기 때문에 가비지 수집 중에 객체를 쉽게 재배치 할 수 있습니다. han-dle을 통해 간접적으로 객체에 대한 다른 모든 참조. 이러한 핸들 기반 메모리 시스템에서 오브젝트 주소는 오브젝트 수명 동안 변경되므로 해싱에 사용할 수 없지만 핸들 주소는 일정하게 유지됩니다.

쓰레기 수집 물체의 공간과 시간 효율적인 해싱

Sun의 현재 Java Virtual Machine 구현에서 클래스 인스턴스에 대한 참조는 그 자체가 포인터 쌍인 핸들에 대한 포인터입니다. 하나는 객체의 메소드를 포함하는 테이블에 대한 포인터이고 다른 하나는 오브젝트의 유형 및 오브젝트 데이터의 Java 힙에서 할당 된 메모리에 대한 다른 유형.

자바 가상 머신 사양 (1997)

따라서 작동하고 시도되었으며 비 효율성으로 인해 세대 별 마크 및 스윕 시스템이 개발되었습니다.