[컴파일러] 10. 실행 시간 환경 - 스택, 힙, 가비지 컬렉션

높은 주소
+------------------+
|      스택 (Stack) |  <- 함수 호출 정보, 지역 변수
|        |         |
|        v         |
|                  |
|        ^         |
|        |         |
|      힙 (Heap)   |  <- 동적 할당 데이터
+------------------+
| 정적 데이터       |  <- 전역 변수, 상수
+------------------+
| 코드 (Code)      |  <- 프로그램 명령어
+------------------+
낮은 주소

높은 주소
+---------------------------+
|  실제 매개변수 (arguments) |
+---------------------------+
|  반환값                    |
+---------------------------+
|  제어 링크 (control link)  |  <- 호출자의 프레임 포인터
+---------------------------+
|  접근 링크 (access link)   |  <- 정적 스코프 지원
+---------------------------+
|  저장된 레지스터            |
+---------------------------+
|  지역 변수                 |
+---------------------------+
|  임시 변수                 |
+---------------------------+
낮은 주소

1. 실제 매개변수를 평가하여 스택에 push
2. 반환 주소를 저장
3. 피호출자로 제어를 이동 (call 명령)

1. 저장해야 할 레지스터를 스택에 push
2. 이전 프레임 포인터(FP)를 저장 (제어 링크)
3. 새로운 프레임 포인터(FP)를 설정
4. 지역 변수를 위한 공간 할당 (SP 이동)

1. 반환값을 지정된 위치에 저장
2. SP를 FP로 복원
3. 저장된 레지스터를 복원
4. 이전 FP를 복원
5. 반환 주소로 점프

void main() {             void foo(int x) {
    foo(10);                  int y = x + 1;
    // ...                    bar(y);
}                         }

                          void bar(int a) {
                              int b = a * 2;
                          }

스택 변화:

[1] main 호출 시        [2] foo(10) 호출 시      [3] bar(11) 호출 시

+-------+              +-------+              +-------+
| main  |              | main  |              | main  |
+-------+              +-------+              +-------+
                       | foo   |              | foo   |
                       | x=10  |              | x=10  |
                       | y=11  |              | y=11  |
                       +-------+              +-------+
                                              | bar   |
                                              | a=11  |
                                              | b=22  |
                                              +-------+

// Pascal-like 코드
procedure A;
    var x: integer;

    procedure B;
        var y: integer;

        procedure C;
        begin
            x := y + 1;  // A의 x와 B의 y에 접근
        end;

    begin
        C;
    end;

begin
    B;
end;

스택 (호출: A -> B -> C):

+-------+
| A     |  <- 접근 링크: 없음 (최외곽)
| x     |
+-------+
| B     |  <- 접근 링크: A의 레코드를 가리킴
| y     |
+-------+
| C     |  <- 접근 링크: B의 레코드를 가리킴
|       |
+-------+

C에서 x에 접근: 접근 링크를 2번 따라감 (C -> B -> A)
C에서 y에 접근: 접근 링크를 1번 따라감 (C -> B)

디스플레이 배열:
  display[1] = A의 활성 레코드 포인터
  display[2] = B의 활성 레코드 포인터
  display[3] = C의 활성 레코드 포인터

C에서 x에 접근: display[1]로 바로 접근 (O(1))
C에서 y에 접근: display[2]로 바로 접근 (O(1))

1. 퍼스트 핏(First Fit):
   충분히 큰 첫 번째 빈 블록을 사용

   [사용중][  빈 블록  ][사용중][ 빈 블록 ]
                ^
            여기에 할당

2. 베스트 핏(Best Fit):
   요청 크기에 가장 가까운 빈 블록을 사용
   -> 외부 단편화 가능성이 높음

3. 버디 시스템(Buddy System):
   2의 거듭제곱 크기의 블록으로 분할/합병
   -> 내부 단편화 가능성이 있지만 합병이 빠름

외부 단편화 (External Fragmentation):
  빈 공간의 총합은 충분하지만, 연속 블록이 부족

  [사용][빈][사용][빈][사용][빈]
        ^^^       ^^^       ^^^
    각각 100B이지만 200B 요청 불가

내부 단편화 (Internal Fragmentation):
  할당된 블록 내에 사용되지 않는 공간

  요청: 100B, 할당: 128B -> 28B 낭비

루트 집합: 스택 변수, 전역 변수, 레지스터

    [루트] --> [객체A] --> [객체B]
                 |
                 v
              [객체C]

              [객체D] --> [객체E]   <- 도달 불가 = 가비지!

a = new Object();   // Object의 refcount = 1
b = a;              // Object의 refcount = 2
a = null;           // Object의 refcount = 1
b = null;           // Object의 refcount = 0 -> 회수!

장점:
  - 즉시 회수: 참조가 0이 되면 바로 메모리 반환
  - 일시 정지 없음: GC 정지(stop-the-world) 없음
  - 구현이 간단

단점:
  - 순환 참조 처리 불가:
    [A] --> [B]
     ^       |
     +-------+
    A.refcount = 1, B.refcount = 1 (영원히 0이 안 됨)

  - 카운트 갱신 오버헤드: 대입마다 카운트 갱신
  - 캐시 효율 저하: 참조 갱신 시 원격 메모리 접근

마크 단계 (Mark Phase):
  1. 루트 집합에서 시작
  2. 도달 가능한 모든 객체에 "마크" 표시
  3. DFS 또는 BFS로 객체 그래프 순회

스윕 단계 (Sweep Phase):
  1. 힙의 모든 객체를 순회
  2. 마크되지 않은 객체를 회수
  3. 마크된 객체의 마크를 제거

마크 전:
  [A*] -> [B*] -> [C*]
                    |
                    v
  [D ] -> [E ]    [F*]

  * = 루트에서 도달 가능

스윕 후:
  [A] -> [B] -> [C]
                  |
                  v
  [빈] -> [빈]  [F]

  D, E는 회수됨

장점:
  - 순환 참조도 정확히 회수
  - 오버헤드가 쓰레기의 양에 비례

단점:
  - Stop-the-World: GC 실행 중 프로그램 일시 정지
  - 단편화: 회수 후 메모리가 조각남

[From 공간]              [To 공간]
+---------+              +---------+
| A  B  C |  복사 -->    | A  C    |
| (빈) D  |              | (빈)    |
+---------+              +---------+

살아있는 객체만 To 공간으로 복사
-> 단편화 없음, 연속 메모리

1. To 공간의 시작 위치에 scan과 free 포인터 설정
2. 루트에서 참조하는 객체를 To 공간으로 복사
3. scan 포인터가 가리키는 객체의 참조를 처리:
   - 참조하는 객체가 From에 있으면 To로 복사
   - 참조를 새 위치로 갱신
4. scan이 free를 만나면 완료

장점:
  - 단편화 없음 (압축 효과)
  - 할당이 매우 빠름 (포인터 증가만)
  - 살아있는 객체에만 비용 발생

단점:
  - 메모리의 절반만 사용 가능
  - 살아있는 객체가 많으면 복사 비용이 큼
  - 포인터 갱신 필요

+------------------+
|  Old Generation  |  (오래 살아남은 객체)
|  (Major GC 대상) |  <- GC 빈도 낮음
+------------------+
|                  |
| Young Generation |  (새로 생성된 객체)
|  (Minor GC 대상) |  <- GC 빈도 높음
|  +----+ +------+ |
|  |Eden| |Survivor||
|  +----+ +------+ |
+------------------+

1. 새 객체는 Young 세대에 할당
2. Young 세대가 가득 차면 Minor GC 실행:
   - 살아있는 객체를 Survivor 영역으로 복사
   - 여러 번 살아남은 객체는 Old 세대로 승격(promotion)
3. Old 세대가 가득 차면 Major GC 실행:
   - 전체 힙을 대상으로 GC (비용이 큼)

Old 세대의 객체 A가 Young 세대의 객체 B를 참조하면:
  -> 기억 집합에 A를 추가
  -> Minor GC 시 기억 집합의 객체도 루트로 취급

이를 통해 Minor GC가 Old 세대 전체를 스캔하지 않아도 됩니다.

Java HotSpot JVM:
  Young: Eden + Survivor0 + Survivor1 (복사 수집)
  Old: Mark-Compact 또는 CMS/G1/ZGC

Go:
  세대 없이 동시(concurrent) 마크 앤 스윕
  삼색 표시 (tri-color marking) 사용

Python:
  참조 카운팅 + 세대별 GC (순환 참조 처리용)

[프로그램 스레드]  -------실행-------실행-------실행------->
[GC 스레드]       --마크--|-스윕---|---------|-마크--|-->

-> Stop-the-World 시간을 최소화

[프로그램] [GC] [프로그램] [GC] [프로그램] [GC] [프로그램]
   10ms   2ms    10ms    2ms    10ms    2ms    10ms

-> 긴 일시 정지 대신 짧은 일시 정지 여러 번

Java G1 (Garbage First):
  - 힙을 동일 크기의 리전(region)으로 분할
  - 가비지가 많은 리전을 우선 수집
  - 일시 정지 목표 시간 설정 가능

Java ZGC / Shenandoah:
  - 매우 짧은 일시 정지 (수 밀리초 이내)
  - 대용량 힙 (수 테라바이트) 지원
  - 동시 압축(concurrent compaction)