임베디드 레시피

Egloos | Log-in





STACK, HEAP에 관한 소고.


- STACK은 history기능을 가지고 있고, Heap은 메모리를 꿔줄 수 있습니다. stack이나 heap은 모두 전역변수 배열로 선언되어 있으며, 어떤 전략으로 사용할 것인가에 따라 stack이나 heap으로 나뉘게 되지요.  -


STACK과 HEAP에 관한 작은 생각들을 늘어놓도록 하겠습니다. STACK은 무엇인가? - 시작부터 Stack이 무엇인지 늘어놓으려고 하니, 참으로 쑥스럽습니다. 저에게 Stack이라는 것은 참으로 미지의 무엇이었기 도 했는데, 조금 알았다 싶어 다시 잘 생각해 보면, 여전히 미지의 것이기는 마찬가지 입니다. 참으로 곤란하기 짝이 없습니다. 그저 Data를 건초더미 쌓듯이 쌓아 올리면 되리라는 근본적인 Idea에는 변함이 없습니다만, 막상 함수가 호출될 때, 어떻게 Stack을 이용한다던가 하는 문제를 자세히 들여다볼 기회가 없었을 뿐이라고 생각하고 있습니다. 그러니까, Stack이라는 것은 뭔가를 쌓는 구조의 Memory 영역이라니까요.
 
일단은 Stack이라는 것의 정의부터 살펴봐야 할 것 같습니다. 어떻게 이용되는지는 "함수의 호출과정"편에서 확실하게 짚고 넘어가기로 - 구렁이 담 넘어가 듯이 - 하고. 일단, Stack이라는 것은 LIFO (Last In, First Out)이라고 불리는 자료 구조인데요, 마지막에 집어넣은 Data가 가장 처음으로 나오는 Data라는 의미 입니다. 쉽게 말해서 책을 순서대로 쌓는다고 했을 때, 웬만큼 쌓고 난 후, 책을 무너트리지 않고, 하나의 책을 다시 꺼내 오려면 맨 위의 책을 꺼내오는 것이 가장 현명한 방법이라고나 할까요?
 
여기서 Stack에 관련된 용어 두 개를 정의 하자면, push와 pop이 있습니다. Push는 Stack에 자료를 집어 넣는 용어이고, Pop은 Stack에서 자료를 빼는 것을 말합니다. 자, 이제 예제 하나를 들겠습니다. - 예제 말고는 쉬운 방법이 없겠는데요. 한계인가요 - A를 push, B를 push, C를 push, D를 push, E를 push했을 때는 어떤 일이 벌어질 까요? (A → B → C → D → E 순서) 결국 그림의 가장 왼쪽 경우처럼 되겠습니다. 


 
가장 밑바닥에서부터 A,B,C,D,E를 채워 넣었습니다. 이 stack에 대해서 Pop을 5회 연속 시도 하면 어떤 일이 벌어질지 대충은 아시겠죠? Pop을 한번 하면 E가 Stack에서 튀어 나오고, DCBA만 남게 되고요, 또 Pop을 시도하면 D가 튀어나오고, CBA만 남게 되고 그런 구조입니다.
 
가장 최근에 push한 data부터 순서대로 가장 오래 전에 push 한 data까지 pop하게 되는 원리인데, 예를 들어 DOS, UNIX, LINUX cmd 창에서 쓸 수 있는 history기능 등이 바로 그 기능입니다. ↑ 위쪽 화살표 키를 계속 누르면 가장 최근에 입력했던 command에서부터 다시 보여주죠. 또는 우리가 Window Application 등에서 ctrl - z (취소) 버튼을 계속 누르면 가장 최근에 작업했던 것부터 점점 차례대로 취소해 줍니다. 이 모두 Stack이라고 할 수 있습니다. Stack이라는 건 history기능을 포함하고 있어서, Stack을 이용하면 시간 순서 중 가장 최근에 작업했던 data를 다시 꺼내 볼 수 있다는 거죠.
 
구현이야 어쨌거나, 이런 식인 거죠.
 
push (0x1);
push (0x2);
push (0x3);
 
pop (); /* 0x3이 나옵니다. */
pop (); /* 0x2가 나옵니다. */
pop (); /* 0x1이 나옵니다. */
 
이런 Data구조를 어떻게 구현할 거냐는 건 다른 C Algorithm에 관련된 서적들에게 그 책임을 떠 넘겨야 하겠습니다. 이 책에서는 Data구조로서의 의미 보다는 이런 식으로 동작하는 Memory 영역에 관한 이야기 입니다. 대신 실 제 tcc를 통해 compile을 하게 되면 함수 호출 시 어떤 식으로 구현되는지, stack이 Memory에 어떻게 자리 잡는지. option은 어디에 있는지, 실제로 stack이 어떤 식으로 이용되는지. 하는 류의 내용은 "함수의 구조와 함수가 불렸을 때 일어나는 일"편에서 자세히 레츠고!
 
Stack이 어떤 건지 훑어 보았으니까, 이제 Heap에 대해서도 구경해 볼 차례가 도래하였습니다. Heap도 역시나 Stack 처럼 쌓아 올린 더미라는 뜻을 가지고 있는데, 약간은 의미가 다릅니다. Heap의 경우에는 동적 할당에 사용되는데, Linked List, Tree구조 등에 많이 사용됩니다. 역시나, 조금은 뜬 구름 잡는 식이 되어 버렸는데, Heap이라는 것을 알려면 동적 할당이라는 말을 다시 한번 곱씹어볼 필요가 있겠군요.
 
동적 할당이라는 것은 가변적인 양만큼의 Data를 처리하기 위해서 생겨난 셈인데, 그 가변적인 양만큼이라는 것이 참으로 난감한 것들이었습니다. 예를 들면 어떤 함수를 Design하는 와중에 Integer Array가 필요하다고 치면, 보통 우리는 필요한 양 만큼 Array를 선언하게 됩니다. 어떻게요? int array[100] 이런 식으로요. 그런데, 이런 상황에서 100개 만큼의 array가 꼭 필요하다고 한다면, 별로 상관없겠지만, 그 만큼이 다 필요 없다면, 또는 몇 개가 필요할지 모르는 상황이라면 그만한 낭비도 없죠. 그래서 나온 것이 바로 동적 할당입니다. 결국 모두다 공통으로 쓸만한 메모리 영역을 미리 확보해 놓은 다음에 필요한 녀석만 필요할 때마다 필요한 만큼씩만 공통으로 확보해 놓은 메모리 영역에서 잠시 빌려다 쓰는 것입니다. 
Heap도 나름대로 한가지 익숙해 져야 하는 용어가 두 개 있습니다. alloc과 free가 바로 그 친구들인데, malloc은 메모리를 빌려올 때 (할당 받을 때, allocation), free(해제 할 때)는 빌려온 메모리를 다시 돌려줄 때를 의미하지요. (C++에서는 new 라고 합니다.)
 
예를 들어, Size를 미리 알 수 없는 integer Array를 쓰고 싶을 때 그 크기를 입력 받아 Array를 선언하는 방법은 다음과 같이 구현할 수 있겠습니다요. (함수의 argument로 Array의 크기 n을 받는다고 치고, 주의 하실 사항은 사실은 Array이는 아닙니다요. 실망마시고)
 
void HEAP (int n)
{
    int *p;
 
    p = (int *)malloc((sizeof(int))*n);
 
    ........어쩌구 저쩌구..........
}
 
이런 식으로 할당을 하면 integer size를 n개 만큼 연속적인 Memory 영역을 heap으로 부터 가져 오는데, 그 녀석을 이제부터는 *p하면 array의 첫번째 *(p+1) 하면, array의 두 번째를 의미하게 됩니다. 결국 array처럼 쓰는 거지요 머.
 
Heap이라고 불리 우는 그 메모리 영역은 Run Time동안 가변적인 크기의 기억장소를 할당, 해제가 되풀이 되는 영역이지요. 이런 의미에서 Heap영역에서는 Stack과 달리 빌려가고 돌려주는 Memory의 양이나 회수는 일정한 규칙이 없습니다. Heap은 그런 의미에서 자투리 공간 - 사용하지 않는 구멍들 예를 들어 100 byte, 2 byte, 10 byte를 순서대로 heap 영역에서 빌려 갔는데 2 byte짜리를 먼저 갚게 되면 중간에 2byte 구멍이 생기게 되죠. 이런 것을 Fragmentation (조각화) 라고 하며, 약간 비효율적이 될 수도 있습니다. - 들이 생기게 되는데요, 이런 낭비요소는 자투리 모으기를 수행하는 것이 뜨거운 감자이기도 합니다. 한가지, 이런 구멍들을 잘 메우려면 heap 관리 입장에서 누가 빌려가고 누가 돌려 주었는지를 시시각각 monitoring하지 않는다면, 구멍을 메운 후, 누구의 것인지 구분이 되지 않아 구멍을 메우기는 커녕 heap영역을 엉망으로 만들어 버리는 결과를 초래합니다.
 
한가지 주의할 사항으로는 malloc을 한 후, free를 해주지 않으면, 계속 빌려온 녀석을 다른 친구들이 사용을 하지 못하여, 메모리 부족현상을 겪게 될 수도 있으니, 빌려오면 꼭 갚아야 하는 것이 세상이치니까 꼭 지키세요. 안 갚으면, Target이 Reset으로 응분의 조치를 취할 수도 있으니 조심. 특히나, heap의 경우에는 할당을 받을 pointer를 local로 선언한 다음, free를 해주지 않고, 그 함수가 끝나서 return되어 버린 경우에는 다시 돌려줄 방법도 없으니까, 다 쓰면 꼭 돌려주세요. 이런걸 유식한 말로 메모리 누수 현상 (Memory Leakage)라고도 한다죠 아마. 이런 게 자꾸 누적되면 언젠가는 메모리가 모자라 게 될 테니까요~
 
이 section은 말 그대로 小考 - 작은 생각 - 이니까, 일단은 Stack과 Heap에 대해서 작지만, 중요한 결론만 내리고 지나가야 하겠습니다.

by 히언 | 2009/07/25 23:43 | System비네팅 | 트랙백 | 핑백(1)

Linked at 임베디드 시스템 개발자 되기 .. at 2009/07/25 23:46

... 대와 원더걸스, 그리고 이중 포인터 ⓒ struct와 typedef, 그리고 PACKED ⓓ Stack과 Heap에 관한 소고 ⓔ Stack의 정체와 자세히 보기 - initialization 까지 ⓕ&nbsp ... more

◀ 이전 페이지          다음 페이지 ▶