시스템 메모리에서의 스택과 큐

4월 13일 오후 5시 최초 작성본

동일 날짜 오후 11시 Heap & Stack 내용 업데이트

2025.04.13 - [TIL] - [C] 동적 메모리 할당

[C] 동적 메모리 할당

여기에서 메모리에서의 힙은 일반 자료구조의 힙과 다르다는 내용에 너무 충격받아서 별도의 문서를 쓰게 된다.

무슨 프로그램을 실행하든 일정하게 만들어지는 것

┌───────────────┐ // 높은 주소
│   커널 영역    │ ← (사용자 공간 밖)
├───────────────┤
│    스택 (Stack)│ ← 함수 호출, 지역 변수
├───────────────┤
│   공유 라이브러리│ ← 동적 링크된 `.so`/`.dll`
├───────────────┤
│     힙 (Heap)   │ ← 동적 할당: malloc, new 등
├───────────────┤
│  BSS 영역       │ ← 초기화되지 않은 전역/정적 변수
├───────────────┤
│  Data 영역      │ ← 초기값 있는 전역/정적 변수
├───────────────┤
│  Text/Code 영역 │ ← 실행 코드 (기계어)
└───────────────┘ // 낮은 주소

내가 뭘 실행해도 이런 레이아웃이 만들어진다. C의 main() 처럼, 필연적으로 생긴다.
각기 영역은 반드시 필요한 이유가 있다. 여기선 스택과 큐 위주로 다룰 것이니 우선은 간단하게만 짚겠다.

척척박사들이 가능한 한정된 상황에 많은걸 만들려다 보니 결과적으로 만들어진 현 실태를 보시라.

• 실행 코드를 위한 공간 활용 하는데 있어 Text/Code 영역이 필요하다.
• Data와 BSS가 존재해야 전역/정적 변수 관리를 진행 할 수 있다.
• heap이 있기에 malloc, new를 통한 동적 구조 지원이 가능하다.
• stack이 없다면 지역변수, 매개변수, 리턴주소의 개념을 구현 할 수 없다.
• 공유 라이브러리에 시스템 라이브러리를 로딩해서 사용한다.

여기서 굵은 줄을 친 세 영역에 대해 다뤄보겠다.

BSS & Data

• 아니,초기화 여부에 따라 이거 하나가 다르다고요? 그러면 아래에서 선언된 a, b는 완전 다른 영역에 저장된다는거죠?

int a = 10;

int b;
b = 10;

• 네. 소스 코드 상 하는건 같겠지만, 컴파일러는 이들을 처리하는 방식, 또 저장되는 메모리 위치도 다르다.

시스템 메모리 관점에서의 int a = 10; 과 int b; | b = 10; 이 어떻게 다를까?

• int a = 10;
  • .data에 a라는 이름으로 10을 기록하게 된다. 실행 파일 내 10이라는 값이 바이트 단위로 이미 존재한다.
  • 프로그램이 실행되며 data 영역을 준비 시킬 때 바로 메모리에 10이라는 값이 준비 되는 것이다.
• int b; b = 10;
  • .bss에 b라는 공간만 확보된다. 초기 값이 없으니 운영체제는 이것을 0으로 초기화한다.
    • 더 많은 디테일을 볼 수 있지만 일단은 그런가보다를 해주길 바란다. 
    • 전역변수에 초기값을 주지 않아도 0 또는 쓰레기 값이 아닌 값으로 초기화 되는 이유가 이것이다.
    • 즉, 운영체제가 직접 하는 것도 있고, 실행 파일 포맷의 관례도 있고.
    • 그럼 왜 굳이 전역변수에 대해서만 이러는걸까?
      • 지금껏 그래왔기 때문 + 실용성도 한 몫 한다.
        • 초기화 되지 않은 전역변수라고 해도, 예측이 가능해야 했다. 쓰레기 값이면 대부분 문제가 생겨버리니까.
        • 초기값을 주겠다고 바이너리에 넣으면 그 효과에 비해 사이즈에 대한 부담이 커진다.
          • BSS 영역은 디스크에 들어가지 않고, 크기만 보고 자동 초기화를 실시하게 된다.
• b = 10; 은, 실제로 실행되는 명령어가 존재해야 한다. 즉, Code 영역에  mov b, 10 같은 어셈블리어가 삽입되어있다.
• 즉 런타임 중에 10이 대입 된다는 것.
  • 어떻게 보면 런타임에서 할당하고 쓴다는 부분에서 만큼은 Heap과 BSS가 유사 할수는 있다 (사실 이거만 같고 다 다르다)
• 스택과 힙과 다르게 BSS & Data는 특정한 자료구조의 형태로 관리되는 것은 아니다. 다만 연속적으로 배치된다는 면에 있어서 배열과 유사 할 수는 있으나, 인덱싱도 불가하고, int 다음에 똑같은 데이터 타입 int가 온다는 보장도 할 수 없다. 

Heap

힙은 자료구조의 힙과 다르며, 실제로 자료구조도 여러 형태를 사용한다고 알려져있다.
malloc, new와 같은 코드는 이 heap에서 필요로 하는 용량 만큼 slice 하여 필요로 하는 곳에 할당을 하게 된다.
스택에서 논하겠지만 스택은 일정한 크기에서 더 늘어나지 않는다. 그래서 런타임에서의 선언과 할당이 이루어지는 곳이 Heap이 된 것.

Heap도 용량 제한이 있지만 Stack만큼 빡빡하진 않다. 하지만 파편화를 포함한 다양한 문제를 신경써야 하기에 나름의 고충이 있다. 

자료구조의 힙은 트리 형태로 구성되어있지만 얘는 그냥 운영체제가 알아서 최적화된 자료구조를 채택한다고 한다. 쌓아두었다라는 의미에서 Heap을 사용하기에 이런 이름이 붙은건데, 메모리 여유분을 쌓아두고 할당하고 돌려받는데에 있어서는 그런 단어가 적합 할 수는 있겠다.

여기서 할당과 반환을 하는데에 있어 목록으로 정리되어 제공되는 Free list가 있다. 정확하게 이야기하면 할당 할 수 있는 메모리의 양이다. malloc이나 new를 통해 free list에서의 내용을 필요한 만큼 할당하고, 또 돌려받고. 프로그램 생애에서 이게 왠 종일 이루어지는 것이다.

• 이것은 엄연히 list이기 때문에 어느정도 크기의 할당 가능한게 목록으로 정리되어있다. [1K, 10M, 5M] 등. 딱히 정렬되어있진 않다.
• 그리고 이 list에서 내가 필요로 하는 공간을 찾아보는데, 여기서 무엇을 줄까?에 관한걸 논하는것이 바로 할당 전략이다.
  • 할당 전략!!!!
    • 메모리를 달라고 냅다 주면 Heap은 땅파서 장사하는 것도 아니다.. 이왕 줄 수 있을때 좀 덤으로 주고 이런건 가능하다면 자제해야 한다. 그래서 할당을 할 수 있는 전략으로 대표적으로 세 가지를 논 할 수 있다.
    • First Fit은 Free List를 순회하다가 조건에 맞는 용량을 제공 할 수 있는 즉시 해당 용량을 분할하여 제공한다.
      • 장점은 아래에서 논할 다른 전략들과 달리 전체 순회를 끝나고 선택이 아닌 도중 선택이라서 배정 자체는 무척 빠르게 이루어진다.
      • 단점은 여기서 파편화의 비중이 제일 크다고 할 수 있다.
    • Best Fit은 Free List 전체의 순회를 끝낸 다음 제일 적합한 용량을 제공한다.
      • 장점으로는 어차피 발생 할 파편화를 최소화 시킬 수 있다는 점이다.
      • 단점으로는 전체의 순회를 끝내야한다 한다는 점에서 시간 복잡도를 논해야 한다.
    • Worst Fit은 Free List 전체의 순회를 끝낸 다음 제일 큰 용량을 제공한다.
      • 장점으로는 큰 조각을 잘게 나눌 기회를 제공한다. 즉 First Fit과 Best Fit에서 비 선호되는 영역에 대한 접근 기회를 갖는 것이다.
      • 단점은 오히려 남발된다면 그에 대한 파편화도 염두 해야 한다는 것이다.
  • 오 네. 그럼 할당 전략의 선택 주체는 어떨때마다 이걸 고르게 되나요?
    • 운영체제, 라이브러리 구현체, 런타임에 따라 좀 다르긴 한데.. 일단 공통적으로 할당기 allocator 에서 선택이 된다.
      • malloc, new 또는 커널 내부의 할당하는 시스템 콜이 결정한다.
      • 이들이 가지고 있는 기준은 2개가 있다.
        • 요청 크기 : 크기에 따라 아예 다른 방식으로
          • 512Byte 미만의 작은 크기는 그냥 때린다. 내부 단편화? 신경쓰지 않아.
          • 128KB 미만정도의 적당 크기는 Best fit을 보통 선택하려고 한다.
          •  MB 단위로 넘어가면 Fit 전략 없이 일반 배정 콜인 mmap() 같은걸 그냥 쓴다.
            • fit 전략과 mmap()은 상호보완적이며, 언급했듯이 크기 기준으로 선택 경로가 다르다.
        • Free list의 상태와 힙 압력 : 파편화 상태나 할당 패턴을 자체적으로 감지한다.
          • 내부 전략은 감지에 기반해 동적으로 전환되기도 한다.

지금으로썬 내가 궁금해하고 정리하는건 여기까지이나, 분명 한 키워드에 대해 또 유의미하게 딥하게 파고 드는시간을 가지겠다.

Stack

스택은 후입 선출 구조라는 점에 있어 자료구조의 스택과 동일하게 떠올리면 된다. 함수 호출 시 지역 변수, 매개 변수, 리턴 주소 등이 자동으로 스택 프레임에 적재된다. 함수가 끝나면 해당 프레임이 제거 된다.

2025.04.09 - [컴퓨터 이론] - week 4 CSAPP #3-7 ~ -9

week 4 CSAPP #3-7 ~ -9

안그래도 내 책 정리에서 Stack Frame에 관한 내용을 담고 있다. 

메모리 할당과 해제는 자동으로 이루어진다. 속도는 매우 빠르고, 짧은 생명 주기를 갖는 데이터 저장에 주로 이용된다.

스택은 동적으로 크기를 조절 할 수 없는 탓에 프로그램이 실행되면서 전개되는 형태라면 런타임에서 동적 할당이 이루어 질 수 있게끔 malloc, new를 고려한 힙 구역 사용을 고려 해야한다.

• stack이 없다면 지역변수, 매개변수, 리턴주소의 개념을 구현 할 수 없다. 라고 앞에서 이야기했었다.
  • 왜 하필 스택이었을까?
    • 함수의 재귀호출까지는 아니라도 함수가 다른 함수를 부르고, 그 함수도 다음 함수로 무언가를 부를 수 있다.

main() -> funcA() -> funcB() -> funcC()

funcC가 끝나면 funcB로 되돌아가서 funcB의 할 일을 마저 해야한다!..
즉, footstep을 기록할게 필요했다. 되돌아 갈 곳이 어딘지는 알아야 다시 돌아가서 할 일을 하지?

• 그럼 이걸 뭘로 만들죠? 에 대해 논한다면 이게 Stack이 정말 적합하다라는 결론이 나온 것이다.
  • 큐와 힙 같은 다른 자료구조는 이것을 구현하는 것이 구조적으로 어렵다. 큐는 부분적으로는 순차 처리는 가능하긴 하겠다.
• 이건 함수 호출에 대한 이야기뿐인데, 언급한 지역 변수, 매개 변수, 리턴 주소에 대한건요?
  • 그것들이 사실 함수 호출이라는 이벤트의 부산물이다. 그래서, 함수끼리의 매개에 당연히 필요 한 것들이니 어찌 다른 공간에 담을 수 있을까. 그래서 함수 호출이 일어나고 footstep이 저장되는 이 저장소에 함수와 연관된 변수와 주소도 저장하는 것이다.

논외로, Stack은 수학적 계산의 중간 저장소 개념에서 시작되었지만, 함수 호출과 호출 타이밍으로의 복귀가 필요한 상황에서 이 스택은 간단하고 강력한 툴이 되었다.