[동적 메모리 할당, 가비지 컬렉션, 이중 연결 리스트]

0. 선행 지식

*정적 메모리 할당
- 동적 메모리 할당과 반대되는 개념
- 프로그램이 시작되기 전에 미리 정해진 크기의 메모리를 할당 받는 것을 말함
- 처음에 결정된 크기의 값 만을 처리함

---

1. 동적 메모리 (Dynamic Memory Allocation)

동적 메모리 할당이란 프로그램이 실행 도중에 동적으로 메모리를 할당 받는 것을 의미한다.
프로그램에서는 필요한 만큼의 메모리를 시스템으로부터 할당을 받아서 사용하고, 사용이 끝나면 메모리를 반납한다.

• 운영 체제의 힙 영역의 메모리를 할당 받아서 사용한다.
  • 힙 메모리 : 메모리를 프로그램이 실행되는 동안 동적으로 결정하는 경우 사용되는 공간
• 필요한 만큼만 할당 받고, 반납함으로써 메모리의 효율적 사용, 유연한 관리가 가능하다는 장점이 있다.
• 운영체제에 프로그램이 필요로 하는 메모리의 용량을 알려주어야하며, 할당된 메모리의 주소를 알아야 사용할 수 있다.
• 동적 메모리는 malloc() 계열의 라이브러리 함수를 사용하여 할당 받고, free() 함수를 통해 기어 공간을 해제한다.
  • 동적 메모리의 사용이 끝나면 해당 메모리 영역을 명시적으로 반납을 해줘야한다.

C언어에서 동적 메모리 할당 예시

• 간단하게 동적 메모리 할당을 비유하면, 수납 공간에서 물건을 꺼내는 것과 비슷하다고 할 수 있다.
• 수납 공간에서 물건을 꺼내서 사용하고, 사용이 끝나면 다시 수납 공간에 물건을 놓아야한다.

*MMU (Memory Management Unit) / 메모리 관리 장치
- CPU 코어 안에 탑재되어 가상 주소를 실제 메모리 주소로 변환해주는 장치

*Break
- MMU가 있는 시스템의 경우 필요할 때 break를 사용하여 프로그램이 사용하는 메모리를 늘리거나 줄일 수 있다.

*Heap Area
- 프로세스 실행 중에 malloc, new 등의 동적 메모리 할당 요구를 수용하는 데이터 영역 공간이다.
- break 값에 의해 그 끝을 나타내며 공간 부족 시에 주소가 커지는 방향으로 확장된다. 

 

• 좀 더 효율적인 메모리 할당을 위해 아래와 같이 노드와 문자열을 동시에 할당하는 방법을 사용할 수 있다.

---

2. 가비지 컬렉션 (Garbage Collection)

사용이 끝난 객체를 알아서 메모리 공간에서 지워주는 것

• C, C++은 사람이 직접 메모리 관리를 해야했다.
• 사람이 직접 해야하니 성능상의 이점은 있지만, 코드 작성 난이도가 높아지고 실수할 가능성이 존재한다는 약점이 존재했다.
• 이를 보완하기 위해 자바, 파이썬, 자바스크립트와 같은 언어들은, 사람을 대신하여 메모리 관리를 하여 필요없는 메모리를 정리 도구를 만들어낸다. 이것이 바로 카비지 컬렉터이다.
• 가비지 컬렉터의 기본적인 동작 방식은 다음과 같다. 
  • 여러 방식이 있지만 기본적으로 아래의 두 가지 방식에 근거한다.
  • 기본적으로 한 가지 방식만으로 가비지 컬렉터를 구현하지 않고, 둘 다 사용하여 상호 보완한다.

2.1  Reference Couting

• 선언하는 모든 객체들에게 레퍼런스 카운트라고 하는 숫자를 별도로 준다.
• 처음 선언할 때는 1이며, 참조되는 곳이 늘어날 때마다 +1 해준다.
• 레퍼런스 카운트 값이 0이 되는 순간 메모리에서 지워진다.

*레퍼런스 카운팅의 문제 :순환 참조를 만들면 계속 메모리에 남게 된다.

• 위와 같이 상호 참조, 순환 참조가 생기면 레퍼런스 카운팅의 문제가 생긴다.
• 이러한 문제가 생기면 프로그래머가 해당 객체에 접근할 방법이 사라지고, 사이클을 풀어낼 방법이 없게 된다.
• 이런 경우 프로그램이 동작하는 동안에는 계속 메모리가 남게 된다는 단점이 생기고, 이는 메모리 누수의 원인이 된다.

2.2 Mark & Sweep

• 레퍼런스 카운팅 방법을 보완하는 것이 바로 마크 앤 스윕 방식이다.
• 간단하게 말하면, 가비지 컬렉터가 객체를 돌아다니면서 마크를 하고, 마크가 안되어 있는 것은 지워버리는 방식이다.
• 이 방식은 매번 계산되는 것이 아니라, 의도적으로 가비지 컬렉터를 실행시켜야한다.
• 위의 그림에서 we are here 라는 위치에서 마크 앤 스윕을 실행시켰다고 가정하면, 다음과 같은 방식으로 진행된다.
  1. 우선 이 방식은 시작하는 노드가 필요하다. 위의 사진에서는 Root가 노드이다.
     • 상위 코드가 없는 경우 시작하는 노드와 연결된다.
     • a, b가 선언될 때 상위 코드가 없어서 노드와 연결되었고, 그 후에 a가 b블 참조하고 있다.
  2. we are here에서 마크를 시작하면, 루트와 연결된 그래프를 순회하면서 마킹을 한다.
     • a, b는 루트와 연결되어있으므로 마킹이 된다.
  3. 마킹이 끝나면 스윕이 시작된다.
     • 스윕은 그래프가 아닌 모든 스코프를 순회한다.
     • a,b는 마킹이 되어있으므로 삭제되지 않는다.
• 그러나 만약 스코프 안이 아니라, 바깥에서 마크 앤 스윕이 선언되었다고 가정한다면, a,b는 Root와 끊어진 상황일테니, 마킹이 안되고 전부 스윕되게된다.
• 이 방식은 순환 참조가 되어도 삭제가 가능하다는 장점을 가진다.

3. 이중 연결 리스트 (doubly linked list)

• 이중 연결 리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트이다.
• 위의 그림처럼 노드의 왼쪽 링크와 오른쪽 링크가, 각각 다른 노드의 링크들과 연결되어있고, 헤드도 노드로 이루어져 있다.

 

• 기존의 연결 리스트는 노드 중간에 삽입과 삭제가 어려웠다.
• 그러나 이중 연결 리스트는 리스트 전체를 방문하지 않아도 원하는 위치에 노드를 쉽게 추가하거나 삭제할 수 있다.

 

• 삽입 연산

 

• 삭제 연산

 

참고 및 출처

https://www.youtube.com/watch?v=4HHnXGIb9IM

https://www.youtube.com/watch?v=j9Vncn04GsE

https://yjg-lab.tistory.com/122