동적 메모리 할당, 더 효율적인 메모리 할당, 가비지 컬렉션, 이중 연결 리스트

1. 동적 메모리 할당.

• 배열이 사용하는 메모리는 정적이다. 즉, 한번 정해진 메모리 크기에서 변화가 존재하지 않는다.
• 반면에 연결리스트의 노드들은 동적입니다. 즉, 이들은 필요에 따라서 자유롭게 생기기도 하고 사라지기도 합니다.
• 이러한 동적 메모리 할당은 메모리 영역중에서 힙공간을 사용합니다.
• MMU(메모리 관리 유닛)이 있는 시스템이라면 런타임 라이브러리가 프로그램에게 필요한 메모리 용량을 판단해 운영체제에게 요청한다.
• C언어에서는 대표적인 동적 메모리 할당 방법으로 malloc과 free함수가 있다.
• malloc의 작동 원리는 단일 연결 리스트 데이터 구조를 사용합니다.

 

• 전체 힙 공간은 처음에 한 블록으로 존재합니다.
• 이후 필요할때마다 필요한 크기만큼 블록을 만들어 할당한다.
• 프로그램이 free로 메모리를 해제하면 그 공간은 빈 공간이 된다.
• 앞에서부터 순차적으로 메모리 공간 크기를 탐색하면서 할당을 반복해나갑니다.
• malloc은 종종 가용 블록 리스트를 스캔하면서 두 가용 블록이 서로 인접한 경우 둘을 합쳐서 더 큰 블록으로 만듭니다.
• 위와 같은 과정들이 반복되면서 메모리 공간이 파편화가 됩니다. 파편화로 인해 계속 사용하지 않는 애매한 크기의 메모리들이 남아있어서 낭비를 초래합니다.
• 또한 각각의 메모리 블록에는 next(다음 블록의 주소)와 size 표시로 인해 블록당 16바이트를 소모해야합니다.
• 이런 단점들이 존재하기 때문에 오늘날 충분히 큰 RAM을 제공하는 환경에서 모든 메모리를 정적으로 할당해 사용하는 편이 더 낫다고 합니다.

2. 더 효율적인 메모리 할당

• 텍스트 문자열이 들어있는 연결 리스트를 만든다고 할 때 왼쪽의 방식처럼 노드에 문자열을 가리키는 포인터가 들어있는 방식은 노드에 사용할 메모리 뿐만 아니라 문자열에 사용할 메모리도 할당해야 하기 때문에 메모리 공간 낭비가 심하다.
• 반면에 오른쪽 방식처럼 하나의 노드에 바로 문자열을 집어 넣고 메모리 경계를 지키기 위해 패딩을 끝에 추가해주는 방식은 부가비용을 절반으로 줄여준다. 오른쪽 방식이 더 효율적이다.
• free 함수도 오른쪽은 한번만 호출해도 된다.

3.가비지 컬렉션

• C언어에서는 malloc이나 free를 통해서 직접 동적 메모리 할당을 하고 해제하였다. 이 과정에서 포인터를 사용해 존재하지 않는 메모리에 접근하는 예외가 발생할 수 있고 이로 인해 프로그램이 중단된다는 문제가 발생할 수 있다.
• 그래서 자바나 자바스크립트 같은 언어에서는 사용자가 직접 동적 메모리 할당을 할 수 없게 만들었다. 즉, 자바의 경우 malloc과 free 대신에 가비지 컬렉션을 통해서 알아서 동적 메모리 할당을 해제한다. 또한 포인터 대신에 참조라는 것을 만들어 실제 메모리 주소를 노출하지 않게 하였다.
• 자바에서 동적 메모리 할당을 하고 싶다면 new연산자를 사용하면 된다.
• 또한 가비지 컬렉션은 JVM에서 자동으로 제공하는 기능으로 사용자가 직접 메모리를 해제할 필요 없이 런타임 환경에서 변수 사용을 추적하여 더 이상 사용하지 않는 메모리를 자동으로 해제합니다.
• 메모리 자동 해제에는 여러가지 방법이 있지만 대표적으로 참조 카운팅 방식이 있습니다.
• 참조 카운팅 방식은 각 메모리를 변수가 참조하는 횟수를 추적해서 더 이상 메모리를 참조하는 변수가 없다면 메모리를 해제하는 방법입니다.
• 가비지 컬렉션을 통해서 사용자의 잘못된 포인터의 사용으로 인한 프로그램 중단 현상은 없어졌지만 가비지 컬렉션이 늦어진다면 프로그램이 늦어진다는 단점이 있다.
• 또한 가비지 컬렉션은 사용자가 제어할 수 없기 때문에 원하지 않는 타이밍에 가비지 컬렉션이 시행되는 경우가 존재할 수 있다.
• 만약 가비지 컬렉션에서 에러가 발생할 경우 사용자가 직접 제어할 수 없기 때문에 디버깅이 더 어렵다는 단점도 존재합니다.

4. 이중 연결 리스트

• 단일 연결 리스트에서 특정 위치의 노드를 삭제하려면 바로 앞 노드를 찾아야만 했다.
• 이 말은 바로 앞 노드를 찾기 위해서 제일 처음 노드부터 순차적으로 찾아가야한다는 것을 의미하여 상당히 작업이 느려질 수 있다.
• 그래서 등장하게 된 개념이 이중 연결 리스트 구조이다.
• 이중 연결 리스트는 다음 노드에 대한 포인터 뿐만 아니라 이전 원소에 대한 포인터도 들어있는 리스트이다.

• 이는 노드당 부가 비용은 2배가 되지만 삭제시 또는 새로운 노드를 추가시 노드를 앞에서부터 방문할 필요가 없어진다.

• 이런식으로 바로 직전 노드가 무엇인지 알 수 있기 때문에 기존 포인터 연결을 끊기만 하면 쉽게 삭제하거나 추가할 수 있다.

 

참조: https://hijuworld.tistory.com/28