Stack 과 heap (메모리구조)

1. stack memory(스택메모리)

stack 이란 단어를 컴퓨터 사전에서 찾아보면 이렇게 정의되어 있습니다.

“후입선출(LIFO, Last-In, First Out)방식에 의하여 정보를 관리하는 자료구조. 스택에서는 톱(Top)이라고 불리우는 스택의 끝부분에서 자료의 삽입과 삭제가 발생한다. 즉, 스택에 자료를 삽입하게 되면 톱 위치에 삽입된 정보가 위치하게 된다. 그리고 스택에서 정보를 읽어오려 하면 스택의 톱 위치에 있는 정보가 반환된다. 따라서 스택에서는 가장 나중에 삽입된 정보가 가장 먼저 읽혀지는 특징을 가지고 있다.”

그림으로 설명하자면 밑의 그림과 같습니다. A→B→C→D 라는 순서대로 자료가 쌓이게 됩니다. 그리고 빠져 나올 때는 위에서부터 차례대로 D→C→B→A 빠져나오게 됩니다. 이러한 구조를 stack 구조라고 합니다.

 

  |  |     |  |     |  |     |  |     |  |     |  |      

  |__|     |__|     |__|     |__|     |  |     |  |    

  |  |     |  |     |  |     |D |     |  |     |  |        

  |__|     |__|     |__|     |__|     |__|     |  |        

  |  |     |  |     |C |     |C |     |C |     |  |        

  |__|     |__|     |__|     |__|     |__|     |__|      

  |  |     |B |     |B |     |B |     |B |     |B |        

  |__|     |__|     |__|     |__|     |__|     |__|      

  |A |     |A |     |A |     |A |     |A |     |A |      

  |__|     |__|     |__|     |__|     |__|     |__|

    

이러한 스택구조가 실생활에서 쓰이는 예로는 택시에서 볼 수 있는 동전을 넣는 원형통입니다. 동전은 원통형의 공간에 들어가고, 원통 아래쪽엔 스프링이 달려서 동전을 밀어 내줍니다. 손님에게 동전을 거슬러 줄 때 위에서부터 동전이 하나씩 나오게 되죠. 그럼 버스에서 보게 되는 동전교환기도 스택일까요? 이것은 스택이 아니라 큐라는 구조 입니다. 원통에 동전이 차곡차곡 쌓여있고, 아래쪽 동전부터 빠져나오게 됩니다.

즉 여기서 동전을 처음에 넣는 것을 push 라는 단어를 사용하게 됩니다.

    push : 하나의 데이터를 스택에 추가한다.

그리고 동전을 꺼내는 것을 pop 이라고 합니다

    pop : 하나의 데이터를 스택에서 꺼낸다.

보통 스택구조를 LIFO 라고 합니다. 즉 Last In First Out 입니다. 말 그대로 마지막에 저장한 데이터는 처음 얻어진다는 뜻입니다. 처음 집어넣은 데이터는 제일 마지막에 얻어지게 되겠지요. 이러한 방식이 컴퓨터에서는 메모리 영역 한 부분이 이런 식으로 동작하고 그 메모리 영역을 스택이라고 부르는 것입니다. 스택을 생각해 내지 못했다면 많은 변수의 사용이나, 함수 호출은 할 수가 없었을 것입니다. 그리고 스택은 프로세스가 생성될 때 필요한 만큼이 할당되어 집니다. 즉 고정사이즈 입니다. 스택 오버플로우라던가, 스택 언더플로우는 스택이 고정사이즈이기 때문에 발생하는 에러입니다.

위에서 프로세스 생성시에 스택은 정적으로 프로세스 공간에 할당 된다고 하였습니다. 그리고 스택은 내부에서도 할당과 반환이 이루어 집니다. 예를들어 스택공간이 1000byte라고 한다면 이 스택의 상대적인 주소값은 0~999까지 갖을 수 있습니다. 이 비어있는 스택에 1바이트 값을 하나 넣어주면 1바이트가 할당되는 것이라고 할 수 있습니다. 1바이트 값을 하나 스택에서 빼오는 것은 스택에서 1바이트를 반환하는 것으로 생각 할 수 있습니다. 이런 스택의 할당과 반환을 처리하기 위해서 CPU에서는 “스택 포인터”라는 레지스터가 있습니다. 이 스택포인터란 것으로 스택이 작동하며 위에서는 1byte 넣고 빼고 하는 예를 들었는데 스택 포인터를 조작하여 스택 내부에 가변적인 크기를 할당해 놓을 수도 있습니다.

그럼 일반적으로 스택이 사용되는 예를 알아보도록 하겠습니다.

스택이라는 메모리 공간에는 우리가 변수로 잡아준 것들이 위에서 설명한 방식으로 할당되고 반환됩니다. 외부 정적 변수를 제외하고 보통 자동변수라고 함수 내에서 선언하는 변수들은 스택 내부에 확보됩니다. 그리고 고정되게 위치하는 것이 아니고 동적으로 스택에 확보가 됩니다.

int ABC;

위의 ABC 변수는 4바이트가 스택에 확보되고 그 스택메모리가 변수로 사용됩니다. 블록이 닫히는 지점에서 스택 포인터 값이 변경되며 확보되어있던 부분이 소멸되지요.

배열변수도 마찬가지 입니다.

void func(void)

{

   char DEF[10];

}

프로그램이 func() 로 실행될때 스택에 10바이트를 할당하고 그 할당된 스택 메모리가 변수를 담는 공간으로 이용됩니다. 물론 10바이트만 할당 되는 것은 아닙니다. 함수호출 자체가 스택을 사용하기 때문에 기본적으로 확보되어야 할 스택에다가 덤으로 10바이트를 할당합니다.

변수가 항상 스택에 할당 되는 것은 아닙니다. 하지만 대체로 스택에 할당 됩니다.

또한 포인터 변수에서도 사용이 됩니다. 포인터 변수라고 특별난 것은 없고 그냥 일반 변수처럼 포인터 변수 또한 스택이라는 공간에 잡힙니다. 단지 포인터 변수는 그 변수에 담겨있는 값이 메모리 주소값 이라는 것뿐입니다. 포인터 변수는 그냥 일반 변수와 똑같고, 사이즈는 언제나 32비트입니다. 안에 담겨있는 값이 단지 주소라는 것 뿐입니다. 변수 자체는 일반변수처럼 스택에 할당됩니다. 단지 C 라는 컴파일러에서 포인터 변수라는 의미를 부여하는 것입니다.

또한 함수 호출 후 복귀 할 때도 사용이 됩니다. 함수를 호출하기 직전에 프로그램 카운터 값을 스택에 한번 넣어주고 호출하게 됩니다. 그 호출된 함수고 종료되어 리턴되면 CPU는 스택에서 최근 넣어진 프로그램 카운터 값을 빼오고 현재의 프로그램 카운터를 빼온 값으로 변경하여 실행하게 됩니다. 그럼 프로그램은 함수 호출 후에 다시 원래대로 카운트 증가해 나가면서 실행되는 것입니다. 이것이 함수 호출의 원리이고, 스택메모리가 사용되는 예입니다.

여기서 주의할 점은 스택에 생성된 메모리는 선언된 함수나 블록문이 끝나면 자동해제됩니다.

 

2. heap memory(힙메모리)

heap memory 는 컴퓨터 사전을 찾아보면 이렇게 정의되어 있습니다.

“ 프로그램의 실행 도중에 요구되는 기억 장소를 할당하기 위하여 운영 체제에 예약되어 있는 기억 장소 영역. 프로그램에서 실행 도중에 자료를 저장하기 위하여 기억 장소를 요청하게 되면 운영 체제에서는 힙에 존재하는 기억 장소를 프로그램에 할당한다. 그리고 프로그램에서 기억 장치를 더 이상 필요로 하지 않는 경우에는 앞에서 할당 받았던 기억 장소를 운영체제에 반납하게 되는데, 이때 운영체제에서는 반납된 기억 장소를 다시 힙에 연결하게 된다. 힙에 대한 기억 장소는 포인터를 통해 동적으로 할당되거나 반환이 되는데 연결 리스트, 트리, 그래프 등과 같이 동적인 특성을 가지고 있는 자료구조에서 널리 사용된다.”

힙은 프로그램이 실행될 때까지 알 수 없는 가변적인 양만큼의 데이터를 저장하기 위해 프로그램의 프로세스가 사용할 수 있도록 미리 예약되어 있는 메인 메모리의 영역입니다. 예를들면 하나의 프로그램은 처리를 위해 한명 이상의 사용자로부터 서로 다른 양의 입력을 받을 수 있으며 즉시 모든 입력데이터에 대해 처리를 시작합니다. 운영체계로부터 이미 확보된 일정량의 힙 저장공간을 가지고 있으면 저장과 관련된 처리를 좀 더 쉽게 할 수 있으며 일반적으로 필요할 때마다 운영체계의 운영체계에게 매번 저장공간을 요청하는 것보다 빠르게 됩니다. 프로세스는 필요할 때 heap 블록을 요구하고 더 이상 필요 없을 때 반환하며 이따금씩 자투리 모으기를 수행함으로써 자신에게 할당된 heap을 관리하기도 합니다. 여기서 자투리 모으기란 더 이상 사용되지 않는 블록들을 사용 가능한 상태로 만들고 또한 heap 내의 사용 가능한 공간을 인지함으로써 사용되지 않은 작은 조각들이 낭비되지 않도록 하는 것을 말합니다.

힙이란 컴퓨터의 기억 장소에서 그 일부분이 프로그램들에 할당되었다가 회수되는 작용이 되풀이 되는 영역입니다. 스택영역은 엄격하게 후입선출(LIFO)방식으로 운영되는데 비해 힙은 프로그램들이 요구하는 블록의 크기나 요구/횟수 순서가 일정한 규칙이 없다는 점이 다릅니다. 대개 힙의 기억장소는 포인터변수를 통해 동적으로 할당받고 돌려줍니다. 이는 연결 목록이나 나무, 그래프 등의 동적인 자료 구조를 만드는데 꼭 필요한 것입니다.

그럼 힙 메모리를 프로그램을 사용할 수 있는 자유메모리라고 할 수 있습니다. 프로그램 실행 시에 함수로 내는 데이터 등을 일시적으로 보관해 두는 소량의 메모리와 필요시 언제나 사용할 수 있는 대량의 메모리가 있습니다. 이때, 소량의 메모리를 ‘스택’이라 하고 대량의 메모리를 ‘힙’ 이라고 합니다. 이 ‘힙’이 없어지면 메모리 부족으로 ‘이상종료’를 하게 됩니다.

프로세스에 exe 이미지가 로드되고, 할당되고, 이것저것 필요한 동적 라이브러리가 로드되고 사용되지 않는 미사용 구간이 있는 것은 분명한데 그 미사용 영역이 ‘힙’이라고 합니다. 프로그램을 짤 때 new나 malloc()함수를 이용한 동적 할당을 하게 되면 힙 영역이 사용 가능하도록 되는 것입니다. 님께서 물어보신 생성자, 소멸자 역시 힙 영역에 메모리를 할당하고 해제하는것입니다. 필요한 메모리 사이즈만큼 OS에게 할당해 달라고 부탁할 수도 있으며, 사용을 다 했으면 다시 OS에게 넘겨줘야 합니다.

예를들어 

   char *p = new char[1000];

위와 같은 코드가 런타임시 힙영역에 메모리를 1000바이트 할당하는 동작을 합니다. 물론 할당을 하였으면 반환도 해주어야 겠지요. 참고로 힙을 마구 할당하고 반환시키다가 보면 선형 메모리의 중간중간이 끊어지게 됩니다. 즉 다른말로 표현하자면 메모리 블록이 여러조각으로 나뉘게 되어 비효율적으로 되어버리기도 합니다.

힙 메모리는 프로그램이 종료 될 때까지 관리하고 유지 되는 메모리 영역이기 때문에 전역함수를 쓰지 않고 프로그램 내에서 지속적으로 메모리를 참조해야 할 경우 힙 영역에 메모리를 할당 받으면 됩니다.

출처 : http://blog.hanafos.com/blogView.asp?blogerid=lsh457457&cateNo=47970&serialno=1