[자료구조] 스택(Stack)과 힙(Heap)

💡 tl;dr

---

1. 스택(Stack)
2. 힙(Heap)
3. 메모리 구조
4. Java에서의 스택과 힙

스택(Stack)

---

• 스택은 제한적으로 접근할 수 있는 나열 구조를 띈 자료구조이다.
• 접근 방법은 언제나 목록의 한 쪽 끝에서만 이루어지는 선형 구조(LIFO - Last In First Out)로 되어있다.
  • 최근에 추가한 항목이 가장 먼저 저게된다.
• 자료를 넣는 행위는 Push, 빼는 것을 Pop이라 한다.
• 이와는 반대로 처음 추가한 항목이 가장 먼저 제거되는 Queue 자료구조가 있다(FIFO - First In First Out)

힙(Heap)

---

• 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조다.
  • 완전이진트리란 2개씩 노드가 분리되는 트리 자료구조에 왼쪽부터 차례대로 노드를 추가하여 구현할 수 있는 형태를 뜻한다.
• 부모의 키값이 자식보다 항상 큰 힙을 최대 힙, 항상 작은 힙을 최소 힙이라 한다.

메모리 구조

---

• 프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(load) 되어야 한다.
• 프로그램에서 사용되는 변수들을 저장할 메모리도 필요하다.
• 따라서 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공한다.
• 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간은 4가지가 있다.
  1. 코드(code) 영역
  2. 데이터(data) 영역
  3. 스택(stack) 영역
  4. 힙(heap) 역

코드 영역

• 메모리의 코드 영역은 실행할 프로그램의 코드(텍스트)가 저장되는 영역이다.
• CPU는 코드 영역에 저장된 명령어를 하나씩 가져와서 처리한다.
• 프로그램 = 명령어들의 집합

데이터 영역

• 메모리의 데이터 영역은 프로그램의 전역(global) 변수와 정적(static) 변수가 저장되는 영역이다.
• 데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸한다.

스택 영역

• 컴퓨터에서 포인터라고 하는 자료의 위치 표시자와 넣고 빼는 명령어를 사용해서 스택을 이용한다.
• 메모리의 스택 영역은 함수의 호출과 관계되는 지역변수(local variable)와 매개변수(parameter)가 저장되는 영역이다.
• 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.
• 주로 함수를 호출할 때 인수의 전달 등에 이용된다.
• 스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당된다.
• 매우 빠르게 액세스 된다.
• 변수를 명시적으로 할당 해체 할 필요가 없다.
  • scope가 해체(pop)될 때 일괄적으로 해체 된다.
• 공간은 CPU에 의해 효율적으로 관리 된다.
• OS에 따라 스택 크기에 제한이 있을 수 있다.
• 변수의 크기를 조정할 수 없다.

자바에서의 스택 영역

• 원시타입의 데이터가 값과 함께 할당된다.
• Heap 영역에 생성된 Object 타입의 데이터의 참조값이 할당된다
• 각 쓰레드(Thread)는 자신만의 stack을 가진다.

힙 영역

• 사용자가 직접 관리할 수 있는 메모리 영역이다.
• 사용자에 의해 메모리 공간이 동적으로 할당되고 해제된다.
• 메모리의 낮은 주소에서 높은 주소의 방향으로 할당된다.
• 메모리 크기에 제한이 없다.
• (상대적으로) 액세스가 느리다.
• 효율적으로 공간 사용을 보장하지 못하면 메모리 블록이 할당 된 후 시간이 지남에 따라 메모리가 조각화되어 해제 될 수 있다.
• 메모리를 관리해야 한다(변수의 할당과 해제에 책임이 있다).

자바에서의 힙 영역

• 모든 Object 타입(Integer, String, ArrayList, …)은 heap 영역에 생성된다.
• 몇개의 스레드가 존재하든 상관없이 단 하나의 heap 영역만 존재한다.
• heap 영역에 있는 오브젝트들을 가리키는 레퍼런스 변수가 stack에 올라가게 된다.

Java 에서의 스택과 힙

---

Java Virtual Machine (JVM)

• C나 C++ 에서는 OS 레벨의 메모리에 직접 접근한다.
  • 따라서 free()라는 메소드를 호출하여 할당받았던 메모리를 명시적으로 해제해주어야 한다.
  • 그렇지 않으면 memory leak가 발생하고, 다른 프로그램에도 영향을 줄 수 있다.
• 자바는 OS의 메모리 영역에 JVM 이라는 가상머신을 이용해 간접적으로 접근한다.
• JVM은 오브젝트가 필요해지지 않은 시점에 알아서 free()를 수행하여 메모리를 확보한다.
• 프로그램 실행시 옵션을 통해 OS에 요청한 사이즈 만큼의 메모리를 할당 받아 실행한다.
  • 이 이상의 메모리를 사용하면 에러가 나며 자동으로 프로그램이 종료된다.
• 따라서 현재 프로그램에서 메모리 누수가 발생해도 다른 것에 영향을 주지 않는다.
• OS 레벨에서의 메모리누수가 불가능하게 된다는 장점이 있다.

Garbage Collection

• 자바가 메모리 누수현상을 방지하는 또 다른 방법이다.
• 프로그래머는 힙을 사용할 수 있는 만큼 자유롭게 사용한다.
• 더 이상 사용되지 않는 오브젝트들은 가비지 컬렉션을 담당하는 프로세스가 자동으로 메모리에서 제거한다.
• Heap 영역의 오브젝트 중 stack 에서 도달 불가능한 오브젝트들은 가비지 컬렉션의 대상이 된다.
• 즉, stack에 있는 레퍼런스 변수의 참조가 소실된 Object를 자동으로 제거한다.

참조

---

스택(Stack) - wiki
힙(Heap) - wiki
힙-스택 차이점 JungHyun-Baek blog
자바 메모리 관리 - yaboong blog
Java Garbage Collection - yaboong blog