MS 님의 블로그

이전 게시글에서 Blocking과 Non-blocking의 차이와 Synchronous와 Asynchronous의 차이에 대해서 정리해봤다.

비동기와 동기 및 블럭킹과 논-블럭킹에 대한 최종 이야기 남아있다.

바로 위와 같이 2대2 Matrix로 정리된 표이다.

위의 표에 정리된 그림을 보고 이해가 된다면 해당 내용을 알고 있는 것이다.

해당 내용이 이해가 되지 않는다면 이 게시글을 보면서 이해해보도록 하자!

Sync Blocking과 Async Non-blocking

Sync Blocking

Sync-Blocking은 말그대로 Blocking이 이루어지는 동기 방식이다.

위의 그림을 보면 호출이 이루어짐에 따라 작업이 완료되기 전까지

제어권을 일시적으로 위임하는 Blocking의 특성이 보이며

작업이 완료되는 즉시 해당 작업에 대한 처리를 진행하는 Sync의 특성이 돋보이는 방식이다.

작업의 결과가 나오기 전까지 다른 작업을 진행할 수 없는만큼 전체 작업 수행 시간이 오래 걸린다.

간단한 예시로는 위와 같이 식당에서 웨이터가 주문을 받고 요리사에게 음식을 만들어달라고 요청했을 때

요리가 나오기 전까지 웨이터는 아무런 일도 하지 않고 음식이 나오기까지 기다리는 상황과 같다.

이렇게 식당에서 일을 하게 되면 주문 한건에 소요되는 시간이 큰 만큼 하루에 음식을 제공하는 양은 적어질 것 이다.

그렇게 된다면 당연히 매출이 떨어질 것 이기때문에 비효율적인 방식이라고 볼 수 있다.

Async Non-blocking

Async Non-blocking은 Sync Blocking과 정반대되는 방식이다.

필요에 따라 호출을 진행한 이후에도 제어권을 잃지 않기 때문에 Non-blocking 특성이 보이며

작업이 완료되었을 때 즉시 해당 결과에 대한 상황을 처리할지 안할 지는 불명확하다는 면에서

Async의 특성이 보인다.

작업의 결과를 기다리지 않고 다른 작업을 수행할 수 있는만큼 전체 작업 수행 시간이 단축된다.

Sync Blocking과 마찬가지로 비슷한 상황이라고 가정할 때

Async Non-blocking방식은 요리사가 요리를 하는 동안 청소를 한다던지 다른 손님의 주문을 받는다던지 등

음식을 기다리지 않고 다른 일을 할 수 있다.

또한 음식이 나오더라도 상황에 따라 즉시 서빙을 할지 안할지는 모른다.

위의 상황은 음식이 나왔더라도 다른 손님의 주문을 받고 있어 서빙이 나중에 이루어지는 모습이다.

Sync Blocking과는 다르게 주문 한건에 시간이 소요되는 동안 다른 주문도 받기때문에 하루에 음식을 제공하는 양이 앞선 방식보단 많아질 것 이다.당연히 매출은 증가할 것 이고 효율적인 방식이라고 볼 수 있다.

위의 두 방식은 우리가 프로그램을 만들 때 익숙하게 이용한 방식이다.

Sync Blocking의 예시를 들자면

C언어에서 사용자의 입력값에 따라 출력되는 프로그램이라고 볼 수 있다.

Async Non-blocking의 경우 

Unity C#에서 제공하는 Addressables API를 이용하여

번들을 로드한 이후 Completed 콜백을 통해 추가적인 작업을 처리할 때로 볼 수 있다.

Sync Non-blocking과 Async Blocking

Sync Non-blocking

Sync Non-blocking은 제어권을 잃지 않는 것이다.

호출을 통해 작업을 요청했어도 작업이 완료되는 동안 다른 작업을 수행할 수 있다.

다만 다른 일을 수행하면서도 작업이 완료되었는지 중간 중간 확인을 하며

확인 중 작업이 완료되었다는 회신을 통해 결과를 즉시 처리한다.

이번에는 주문에 대한 요리를 요청한 뒤 화장실 청소를 한다고 가정을 해보자.

화장실과 주방에 거리는 멀기 때문에 음식이 나오는 것을 직접 가서 확인해야한다.

확인할 때마다 요리가 나오지 않았다면 다시 청소를 하러 돌아갈 것 이고

요리가 나왔다면 즉시 서빙을 할 것 이다.

Async Blocking

Async Blocking은 제어권을 다른 작업에게 위임하는 것 이다.

호출을 통해 작업을 요청했을 경우 제어권을 위임하기 때문에  제어권을 다시 얻기 전까진

다른 작업을 수행하지 못하고 대기해야한다.

마찬가지로 비동기식이므로 완료된 작업에 대해 즉시 처리 여부는 불명확하다.

이번엔 가게에서 정해진 break time으로 인해 잠시 가게를 닫은 다음

이 시간을 활용해 웨이터는 요리사에게 점심 식사를 요구한 상태라고 가정하자.

요리사가 점심 식사를 준비할 때까지 심심한 나머지 웨이터에게 말동무가 되어달라고 한다.

요리사는 본인의 옆에서 이야기를 하는 걸 좋아하기때문에 웨이터는 다른 일을 하지 못하게 된다.

점심 식사 준비를 완료가 된 이후 자유가 된 웨이터는 점심 식사를 바로 할지

화장실에서 손을 씻고 밥을 먹을지는 알 수가 없다.

위의 두 방식은 Sync Blocking 및 Async Non-blocking과 다르게 우리가 흔히 이용하는 방식은 아니다.

그렇기 때문에 예시를 통해 이해가 되었더라도 이 방식들이 어떻게 실제로 적용된 사례가 있을지는 감이 오지 않을 수도 있다.

Sync Non-blocking의 경우 게임의 로딩 progress를 예시로 들 수 있다.

로딩이 진행되는 동안 수시로 어느 정도 진행이 되었는지 확인을 하며 UI를 업데이트하기 때문이다.

Async Blocking의 경우는 

비효율적인 면이 크게 나타나므로 보통은 해당 의도를 가지고 구현하는 경우는 거의 없다.

보통 의도를 Async Non-blocking으로 하려다 개발자의 실수 혹은 기타 이유로 인해 일어난다.

마무리

이전부터 정말 헷갈려 하는 개념을 제대로 이해하고 정리하게 되면서 마음이 많이 홀가분해졌다.

Sync 및 Async와 Blocking과 Non-blocking은 명확히 다른 개념이며

이 두 부류는 공존 할 수 있다는 것을 알 수 있다.

참고 영상 : https://www.youtube.com/watch?v=oEIoqGd-Sns&list=LL&index=1&t=528s

Synchronous와 Asynchronous, Blocking과 Non-blocking이라는 말은 운영체제(OS)를 공부하면서 듣게 된 개념이다.

프로그래밍을 함에 있어 중요한 개념인 만큼 이번 기회에 정리를 해보고자 한다.

Synchronous와 Asynchronous

Synchronous

Synchronous의 의미는 동기식이라는 의미로,

작업을 동시에 수행하거나, 동시에 끝나거나, 끝나는 동시에 시작함을 의미한다.

위 그림을 보면 Process A가 작업을 하는 도중 필요로 인해 Process B에게 작업을 요청한 상태이다.

이때 Process A는 Process B의 작업이 완료되는 즉시 결과에 대한 작업을 진행할 것 이다.

동기 방식은 요청한 작업의 결과를 즉시 처리하는 특징이 있다.

그렇기 때문에 위의 예시를 보았듯이 동기식의 흐름 방식은 직관적이기 때문에 이해하기가 쉽다.

Asynchronous

Asynchronous는 비동기식이라는 의미로,

시작, 종료가 일치하지 않으며, 끝나는 동시에 시작을 하지 않음을 의미한다.

위 그림 역시 동기식의 상황과는 똑같은 상태이다.

비동기식에서는 Process A는 Process B가 작업을 완료되어 돌아온 결과에 대한 작업을 진행할 수도 있고 안할 수 있다.

비동기 방식은 동기 방식과 다르게 요청한 작업의 결과를 즉시 처리하지 않는다는 특징이 있다.

동기 방식과는 다르게 작업 완료에 대한 결과를 예측하기 어렵기 때문에 직관적이지 못한면이 있다.

위의 설명만으로는 동기와 비동기에 대한 이해가 어려울 수 있기 때문에 식당의 예시를 살펴보자.

웨이터는 주문을 받고 해당 주문을 요리사에게 요청을 한 이후 음식을 제공하는 일을 한다.

웨이터가 동기 방식으로 일을 수행하게 된다면 요리사에게 제공할 음식을 만들어달라고 요청한 이후

기다리거나 다른 일을 하고 있을 것이다.

그 이후 따뜻한 요리를 곧장 제공하기 위해 요리가 나오는 즉시 손님에게 제공을 해줄 것 이다.

요리사는 요리를 한 이후 서빙을 하라고 지시할 것이다. 이때 요리사는 기다리거나 다른 일을 하고 있을 것이다.

만약 식사가 끝난 손님의 빈 접시를 웨이터가 전해주게 된다면

요리사는 들어오는 주문에 맞는 요리를 하느라 빈 접시들이 들어오는 즉시 설거지를 하지 않을 것이다.

즉 동기와 비동기는 결과를 돌려주었을 때 순서와 결과에 관심이 있는지 없는지로 판단할 수 있다.

Blocking과 Non-blocking

Blocking

Blocking이란 자신의 작업을 진행하다가 다른 주체의 작업이 시작되면

해당 작업이 완료될 때까지 기다렸다가 자신의 작업을 재개하는 것을 의미한다.

위의 그림을 보면 Process A가 작업을 하는 도중 Process B의 작업이 시작됨에 따라

Process A의 작업이 일시 중지 되는 것을 볼 수 있다.

Process B의 작업이 끝난 이후 Process A의 작업이 재개되는 것을 확인할 수 있다.

즉, 작업을 진행하는 제어권을 일시적으로 위임했다고 볼 수 있다.

Non-blocking

Non-blocking이란 Blocking과 달리 다른 주체의 작업이 시작된다고 해서

해당 작업이 완료될 때까지 기다리지 않고 자신의 작업을 하는 것을 의미한다.

Non-blocking은 Blocking과 달리 Process B의 작업이 시작되어도 작업이 중단되지 않고

계속해서 작업을 진행하는 것을 볼 수 있다.

즉, 작업을 진행하다 다른 작업이 시작되어도 제어권을 잃지 않는다는 것을 알 수 있다.

이렇듯 Blocking과 Non-blocking은 작업을 진행할 때 본인의 제어권이 있느냐 없느냐로 판단할 수 있다.

마무리

지금까지 Synchronous와 Asynchronous의 차이 및 Blocking과 Non-blocking의 차이에 대해서 알아보았다.

위의 두 부류는 명확하게 다른 개념이므로 헷갈려선 안된다.

또한 더 나아가 다음 게시글에서는

Sync blocking, Sync non-blocking과 Async blocking, Async non-blocking에 대해서도 다뤄볼려고 한다.

참고 영상 : https://www.youtube.com/watch?v=oEIoqGd-Sns 

해시 테이블(HashTable)이란?

Key와 Value로 데이터를 저장하는 방법 중 하나로 데이터를 빠르게 검색할 수 있는 자료구조이다.

해시 테이블은  Key 값을 '해시값'으로 생성한 이후 실제 데이터가 저장되는 장소인 '버킷(Buckets)'에 저장하는 방식이다.

이때 해시값은 '해시 함수'를 통해 연산이 되어 생성이 되는데해시 함수는 해당 키 값에 대해서는 항상 고정적인 Index를 반환한다.이러한 과정을 통해 Key로 한번에 필요한 데이터를 찾는 게 가능하기 때문에평균적으로 O(1) 시간복잡도를 가진다.

해시 함수(Hash Function)

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값, 해시 코드, 해시섬(sum), 체크섬 등으로 부른다.

해시 함수는 결정론적 알고리즘(Deterministic Algorithm)으로 작동해야 한다.그렇기 때문에 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터가 달라야 한다.(역은 성립하지 않는다.)

하지만 이러한 해시값은 '고유의 값(Unique Value)'을 갖지 않기 때문에서로 다른 입력값에도 동일한 값이 출력되는 경우도 존재한다.이러한 경우를 '해시 충돌(Hash Collision)'이라고 한다.

해시 충돌(Hash Collision)

해시 테이블에선 동일한 해시값에 의한 충돌을 크게 2가지 방식으로 해결하고 있다.

분리 연결법(Separate Chaining)

각 Index에 데이터를 Linked List에 대한 포인터를 가지는 충돌 처리 방식이다.

동일한 Index로 인해 충돌이 발생한다면

해당 Index가 가리키고 있는 Linked List에 노드를 추가하여 값을 추가한다.

데이터를 추출할 때는 Key에 대한 Index를 통해

해당 Index가 가리키고 있는 Linked List를 선형 검색하여 데이터를 가져오게 된다.

삭제 역시 Index가 가리키고 있는 Linked List에서 해당 데이터를 삭제하면 된다.

새로운 데이터를 추가할 때 테이블이 가득 차도 각 버킷에 있는 Linked List에 추가할 수 있기 때문에

추가하는 데이터 수의 제약이 적다.

시간 복잡도 

중복된 해시값이 많아질수록 List에서 선형으로 검색이 이루어지기 때문에

데이터 삽입, 삭제, 검색에 있어 시간복잡도는 평균적으로 O(1)을 가진다.

하지만 최악의 경우 최대 O(n) 시간 복잡도까지 증가하게 되어 그만큼 캐시의 효율성이 떨어진다.

개방 주소법(Open Addressing)

빈 버킷을 찾아 데이터를 저장하는 충돌 처리 방식이며,

찾는 방식은 세 가지로 나뉜다.

1. 선형 탐사(Linear Probing)

충돌 발생 시 Index에 해당하는 버킷의 다음 버킷들을 순차적으로 탐색하며

빈 버킷 발견 시 해당 버킷에 데이터를 저장하는 방식으로 구현이 간단하다.

위와 같이 Key % 9 해시 함수를 사용하는 해시 테이블이 있을 때

Key값이 1, 12인 경우는 충돌이 없어 데이터가 저장된 모습이다.

하지만 Key값이 10인 경우엔 1과 충돌이 나기 때문에

그 이후 존재하는 빈 버킷에 바로 데이터를 저장하고 있다.

하지만 충돌이 빈번해지면 특정 구간에 연속된 데이터가 몰리는 클러스터링(clustering) 문제가 발생하게 된다. 

이는 탐색 시간을 오래걸리게 하여 검색 효율이 떨어지게 된다.

2. 이차 탐사(Quadratic Probing)

선형 탐사와 비슷하지만 간격이 이차 함수 꼴로 증가하면서 빈 버킷을 찾는 방식이다.

예를 들어 Index가 3에서 충돌이 난다면 다음과 같은 형태로 Index가 증가한다.

3 → 3 + 1^2 → 3 + 2^2 → 3 + 3^3 → ... 

선형 탐색에 비해 클러스터링이 적게 일어나지만

만약 두 Key의 해시값이 동일하다면 빈 버킷을 찾는 과정이 동일하므로 같은 버킷을 탐색하게 된다.

즉 처음 충돌한 위치가 같다면 다음 충돌할 위치에서도 반복적으로 충돌이 나게 되는 것이다.

2차 클러스터링 문제가 발생하게 된다.

3. 이중 해싱(Double Hashing)

이중 해싱은 클러스터링 문제를 방지하기 위한 기법으로

두 개의 해시 함수를 사용해 빈 버킷을 찾는 방식이다.

첫 해시 함수를 통해 해시값을 얻었을 때 충돌이 날 경우

두 번째 해시 함수를 통해 새로운 해시값을 받아 빈 버킷을 찾는다.

만약 이후에도 충돌이 난다면 두 번째 해시 함수를 통해 계속해서 빈 버킷을 탐색한다.

이러한 방식은 충돌이 발생했을 때 무작위로 빈 버킷을 찾게 되어 클러스터링 문제를 피할 수 있다.

하지만 그만큼 구현이 복잡하며 위의 두 방식에 비해 연산이 오래 걸린다는 단점이 있다.

삭제

삭제를 하기 위한 버킷을 찾고 해당 버킷을 삭제되었다고 표시한다.해당 버킷을 삭제되었다고 표시하지 않고 완전히 삭제하게 된다면탐색을 하지 못하는 경우가 발생할 수 있다.

위의 그림에서 모든 Key는 해시 함수를 통해 Index 1을 반환받게 된다.

Key 1의 경우 그대로 데이터가 적재되지만

나머지 10, 19의 경우 충돌로 인해 그 다음 Index에 연속적으로 적재된 것을 확인할 수 있다.

이때 Key 10을 완전히 삭제하게 될 경우 Key 19의 값을 찾을 수 없게 되는데

그 이유는 충돌을 해결하기 위해 사용된 연속적인 탐사 방식이 깨지기 때문이다.

Key 19의 값을 찾기 위해 Index 1부터 시작해 차례로 탐색을 하는 과정에서

빈 상태를 확인하게 되면 해당 자리에 값이 Key 19의 값이 없다고 판단하고 탐사를 중단해 버린다.

그렇기 때문에 완전히 삭제하지 않고 삭제되었다는 표시를 통해 유지한다.

해당 삭제 방식은 선형 탐사를 제외한 나머지 방식(이차 탐사, 이중 해시)에서도 똑같이 적용이 된다.

시간 복잡도

개방 주소형같은 경우도 충돌 시 찾아가는 횟수가 많아지므로

최상의 경우 O(1)에서 최악의 경우 O(n)으로 증가하게 된다.

리사이징(Resizing)

분리 연결법(Separate Chaining)의 경우 버킷이 일정 수준이상 차 버리면

각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에 성능 저하가 일어나고

주소 개방형(Open Addressing)의 경우 고정 크기 배열을 사용하기 때문에

일정 수준이상 차 버리면 성능 저하가 일어날 뿐더러 데이터를 적재할 공간이 남지 않게 된다.

즉 해시 테이블의 '부하율(Load Factor)'이 높아질수록 그만큼 충돌이 많아지고 성능이 저하되기 때문에

이러한 경우 리사이징이 일어난다.

리사이징 이후에는 테이블이 더 커지기 때문에 충돌이 줄어들어 검색 성능이 다시 O(1)에 가깝게 유지되게 된다.

하지만 리사이징을 통해 테이블의 크기가 늘어나면

모든 데이터를 새 해시 테이블로 재해싱하는 작업이 필요하므로 작업에 대한 큰 비용을 요구하게 된다.

참고 블로그

https://bcho.tistory.com/1072

https://yoongrammer.tistory.com/82

싱글톤 클래스와 정적 클래스는 공통된 속성이 있다.

대표적으로 다음과 같은 특징이 있다.

1. 단 하나의 객체만 존재한다.
2. 모든 객체에서 접근이 가능하다.

이러한 공통점으로 인해 싱글톤 클래스와 정적 클래스의 차이를 모르고 넘어가는 경우가 많다.

그렇기 때문에 오늘은 두 클래스의 차이점에 대해 알아보고자 한다.

인스턴스화

두 클래스의 차이점은 인스턴스화가 되느냐 안되느냐에서 명확히 드러난다.

정적 클래스는 new 키워드를 통해 인스턴스를 생성할 수 없으며,클래스의 모든 멤버는 정적으로 선언되어야 한다.

반면, 싱글톤 클래스의 경우 new 키워드를 통해 인스턴스를 생성할 수 있으며,정적이 아닌 멤버를 선언할 수 있다.

사실, 싱글톤 클래스를 두 개 이상으로 인스턴스화 하는 것은 그 클래스로 만드는 의미가 어긋나

실제론 단 하나의 인스턴스화만 하지만,

두 클래스의 명확한 차이점은 인스턴스화가 되는 여부에 따라 크게 차이난다는 것을 알려주기 위해 설명한 것 이다.

Lazy Initialization (게으른 초기화)

Lazy Initialization이란?

객체나 변수가 실제로 필요할 때까지 초기화를 지연시켜 성능을 최적화하는 방식이다.

싱글톤 클래스는 일반적으로 게으른 초기화를 바탕으로 객체가 생성된다.

즉, 객체가 필요한 시점에 초기화를 진행하고 참조할 수 있는 것이다.

"정적 클래스도 처음 호출 하는시점에 초기화가 되니깐,

필요한 시점에 호출해주면 Lazy Initialization(게으른 초기화)가 아닌가요?"

그렇게 생각할 수 있지만 답은 틀렸다.

정적 클래스는 기본적으로 처음 호출이후 모든 정적 멤버를 초기화하기 때문에 개별 객체나 변수가 처음 사용될 때 초기화하는 방식인 Lazy Initialization과의 개념과는 다르다고 볼 수 있다.

상속 (inheritance)

정적 클래스는 어떠한 클래스나 인터페이스에 상속할 수 없다.

즉, 상위 클래스로 정의하거나 정의된 인터페이스를 구현할 수 없어 캡슐화가 되지 않아 그 부분에서의 확장성이 떨어지며,

오로지 하나의 클래스 자체로만 사용된다.

반면 싱글톤 클래스의 경우 엄밀히 말하면 비정적 클래스이므로 캡슐화를 통한 정의가 가능하다.

마무리

두 클래스는 공통적인 부분도 있지만 그만큼의 차이점도 명확하다는 것을 알고 쓰임새에 맞게 사용해야한다.

일반적으로 정적 클래스의 경우 상태를 가지지 않아 유틸리티 클래스로 사용된다.

그외의 상태를 가져 사용할 경우 싱글톤 클래스로 정의하는 것이 좋다.

참고 :

https://bldev2473.github.io/programming/static-and-singleton

https://learn.microsoft.com/ko-kr/dotnet/csharp/programming-guide/classes-and-structs/static-classes-and-static-class-members

오늘은 가비지 컬렉터(Garbage Collector, GC)에 관한 게시글을 작성하려한다.

우리가 프로그래밍을 할 때, 때에 따라 동적으로 메모리를 할당해야하는 상황이 주어진다.

이때 할당된 메모리는 힙 영역에 저장이 되고, 주소값을 통해 힙 영역에 저장된 데이터에 접근하게 된다.

하지만 이러한 메모리 공간은 유한하기 때문에, 메모리 공간의 관리를 잘 해주어야 한다.

C, C++과 같은 언어에서는 프로그래머가 동적으로 메모리를 할당하였다면(malloc, new) 수동으로 그 메모리를 해제(free, delete)해주어야 하는 빈번한 과정을 거쳐야 했다.

꼼꼼한 검수과정을 통해 수동으로 메모리를 해제해주는 작업을 잘 거친다면 메모리 누수 현상은 발생하지 않을 것이다.

하지만 그런 꼼꼼한 검수 과정을 거치더라도 메모리 누수 현상을 완벽하게 방지할 수는 없다...(사람은 누구나 실수를 하기 때문)

이러한 문제를 해결하기 위해 가비지 컬렉터가 나오게 된 것 이다.

가비지 컬렉터 작동 방식

가비지 콜렉터의 작동 방식은 크게 2가지 방식이 있다.

1. 추적 기반 가비지 컬렉터(Tracing Garbage Collection)

프로그램을 실행하는 도중 특정한 시점이 되었을 때 현재 할당된 모든 메모리를 조사하는 방식이다.

이때 할당된 메모리들은 현재 접근 가능한지 불가능한지 분류한 뒤, 접근이 불가능할 경우 가비지로 간주하여 해제시키는 방식이다.

여기서 접근 가능한 메모리를 root라고 한다. 

Mark-and-Sweep

Mark-and-Sweep은 위에 있는 설명을 그대로 구현한 방식이다.

GC를 실행하여 접근이 가능한 메모리를 대상으로 마킹(Marking)을 한 이후, 마킹이 되지 않은 메모리를 할당 해제(Sweep) 하는 방식이다.

위와 같이 힙 영역에 할당된 메모리 obj1, obj2, obj3, obj4가 있다고 가정하자.

GC가 실행되어 할당된 메모리 중 접근이 불가능한 메모리를 마킹한다.

여기선 obj1, obj3가 접근이 불가능한 메모리로 가정한다.

마킹된 메모리는 더 이상 필요하지 않는 메모리이므로 할당을 해제해준다.

하지만 지속적으로 메모리 할당과 해제를 반복하게 될 경우 중간 중간 빈 공간이 생기게 되는 메모리 단편화가 생기게 되어,연속적으로 메모리를 할당해야할 경우 남은 메모리가 충분함에도 불구하고 할당하지 못하는 상황이 발생한다.

Compact

이러한 문제점을 보완하기 위해 Mark, Sweep 과정을 거친 이후 Compact 과정을 한번 더 거치는 방법을 채택하였다.

Compact 과정은 간단하다.불필요한 메모리를 해제한 이후 남은 메모리들을 앞에서 부터 차례차례 빈공간을 채워나가는 과정이다.

추적 기반의 방식은 중간에 메모리가 변경되면 마킹을 다시해야하는 상황이 발생하므로 프로그램 전체를 정지(Stop-The-World) 시켜야 한다.

그렇기 때문에 중간 중간 끊기는 현상이 발생하여 사용자의 경험에 좋지않다는 문제가 발생한다.

1.1 점진적 가비지 컬렉터(Incremental Garbage Collection)

이 방식은 기존 방식에서 중간 중간 끊기는 현상이 발생하는 부분에 대해 어느정도 보완을 하기위해 만들어졌다.

기존 한 번에 마킹과 해제를 하는 방식과는 다르게 여러 번에 걸쳐서 수행하는 방식이다.

여러 번 걸쳐서 수행하는 만큼 마킹과 해제를 하는 한 사이클이 오래 걸리지만 프로그램이 정지하는 시간은 줄일 수 있다.

삼색 표시 기법(Tri-Color Marking)

점진적 가비지 컬렉터는 메모리를 세 가지로 마킹하는 방식인 삼색 표시 기법을 사용한다.기본적으로 흰색, 회색, 검은색으로 표현되며 각 색깔 별 의미는 다음과 같다.

• 흰색 - 더 이상 접근 불가능한 객체
• 회색 - 접근이 가능한 객체이지만, 이 객체에서 가리키는 객체들이 아직 검사되지 않은 객체
• 검은색 - 접근이 가능한 객체

그리고 이 기법은 다음과 같은 순서로 이루어진다.

먼저 모든 객체를 흰색으로 표시한다.

그 이후 루트 집합(전역 변수, 스택 변수 등)에 도달 가능한 객체를 찾아 회색으로 표시해준다.

회색으로 표시된 객체가 참조하는 모든 객체를 회색으로 표시하고 자기 자신을 검은색으로 표시한다.

모든 회색 객체가 없어질 때까지 위와 같은 과정(1~3번)을 반복한다.

그 이후 남은 흰색 객체는 접근 불가능한 객체이므로 모두 해제한다.

(이 방식은 BFS(Breadth-First Search) 알고리즘과 유사하다.)

1.2 세대별 가비지 컬렉터(Generational Garbage Collection)

마찬가지로 이 방식도 기존 방식에 문제점을 보완하기 위해 만들어졌다.

위의 방식들을 토대로 지켜보았을 때 대부분의 객체들은 만들어진 이후 잠깐 쓰이고 금세 버려지며, 오래 살아남아서 쓰이는 경우는 그렇게 많지 않다는 경향을 발견하여 이 방식을 만들게 되었다.

Generation

위 경향을 토대로 크게 두 가지 영역(세대)으로 나누어 수집 대상을 정했다.

• Young 혹은 New - 새로 할당된 객체 혹은 일정 수준 이하 동안 살아남은 객체들
• Old - 새로 할당된 이후 일정 수준 이상 동안 살아남은 객체들

여기서 살아남았다는 말은 가비지 컬렉터가 호출된 이후 수집이 안된 횟수를 뜻한다.

즉, 일정 호출 횟수 이후까지 살아남아 있다면 그 객체는 Old세대가 되는 것이다.

또한 Young세대는 Old세대보다 비교적 더 작은 크기를 가지게 되는데,

그 이유는 전체의 일부분을 지속적으로 빠른 시간내에 GC가 수집하면서 메모리 공간을 확보하기 위해서이다.

Minor-GC와 Major-GC(Full-GC)

세대별로 나누어 수집하는 방식은 크게 두가지 방식으로 나뉜다.

1. Minor-GC

특정 조건에 만족하여 Minor-GC가 호출될 땐 Young세대에 있는 객체들을 대상으로 수집이 이루어진다.

빨간 색으로 표시된 객체들은 GC가 호출이 되었을 때 수집되는 대상이다.

Minor-GC로 호출되었기 때문에 Young세대에 있는 수집 대상만 마킹되고 수집하는 것을 확인할 수 있다.이때 수집된 곳은 빈 공간(Empty)이 된다.

2. Major-GC

특정 조건에 만족하여 Major-GC가 호출될 땐 전체 객체를 대상으로 수집이 이루어진다.

위의 Young세대 수집이 있은 이후의 객체들은 특정 횟수 이상을 만족하며 Old세대로 옮겨지고,

Young세대에는 새로운 객체들이 할당된 상태이다.

Major-GC로 호출되었기 때문에 전 세대에 있는 수집 대상들을 마킹하고 수집하는 것을 확인할 수 있다.

전체 대상으로 수집하기 때문에 Full-GC라고 부르기도 한다.

2.  참조 횟수 카운팅 기반 가비지 컬렉터(Reference Counting based Garbage Collection)

다른 메모리가 어떤 메모리를 얼마나 많이 참조하는지 횟수를 세어서 접근 가능과 불가능을 나누는 방식이다.

Reference Counting

한 메모리가 다른 메모리를 참조하면 그 다른 메모리는 참조 횟수에 1을 더하고 참조를 중단하면 참조 횟수에 1을 뺀다.

이때 1을 뺀 이후 참조 횟수가 0이 되면 해당 메모리에 접근이 불가능하므로 그 메모리를 해제하는 것이다.

단지 참조 횟수를 카운팅 해주고 0이 되었을 때 해제해주기 때문에 구현이 간단하다는 장점이 있다.

OverHead

하지만 매번 대입를 할 때마다 참조 횟수를 카운팅 해주고 참조 횟수가 감소될 때 조건문을 통해 해제가 가능한지 판별하는 것은 적지 않은 오버헤드를 발생시킬 수 있다 또한 참조 횟수를 저장해야하기 때문에 캐시효율 또한 낮아질 수도 있다.

Cyclic Reference

이러한 문제점 말고 한 가지 더 문제점이 있는데 그것은 바로 순환 참조이다.

예를 들어 A가 B를 가리키고 B에서 A를 가리키면 둘 다 참조 횟수가 1이 될 것 이다.

이때 A와 B 둘 중 어느 곳에도 접근할 수 없는데 참조 횟수가 0이 아니기 때문에 메모리를 해제할 수 없게 되며 메모리 누수가 발생하게 된다는 문제점이 있다.

현재는 위의 두 가지 방식중 대부분의 언어는 Tracing GC를 채택하고 있다.

마무리

가비지 컬렉터가 동적으로 할당하는 메모리를 어떤 식으로 관리하는지에 대해 알아보았다.

기존 수동으로 관리하는 방식에 비해 매우 편해졌지만 아직까지 가비지 컬렉터에게 모든 관리를 도 맡기에는 한계가 있다.

가비지 컬렉터가 수집하는 조건은 더 이상 참조하지 않는 객체에 대해만 할당을 해제하기 때문에 메모리 누수의 가능성은 항상 열려있다.또한 실행 시간에 작업을 수행하는 이상 성능 저하는 피할 수는 없다.

그렇기 때문에 가비지 컬렉터를 너무 맹신하고 메모리에 대한 문제를 신경쓰지 않는다면 심각한 성능 저하를 일으킬 수 있는 것이다.