🐢 chap5. 스택과 힙

⭐ 5.1 스택

• 프로세스는 힙 세그먼트 없이 계속 작동 가능, but 스택 세그먼트가 없다면 불가능

• 스택

  • 프로세스의 수명에서 주요 부분에 해당 ⇒ 함수 호출에 대한 메커니즘 때문! (스택 세그먼트 이용해야 함수 호출 가능)
  • 스택의 내용 건드리면 프로세스의 실행 방해 및 중단 발생
  • 스택 세그먼트에서 이뤄지는 할당은 빠르며, 어떤 특별한 함수 호출도 필요하지 않음
  • 메모리 해제 및 모든 메모리 관리도 가능!

  • 🚨 하지만 스택을 남용할 수 있으므로 주의

    • 스택은 아주 크지 않으므로 큰 객체를 저장할 수 없음

    • 스택의 내용을 잘못 사용하면 실행이 중지되고 충돌이 발생

      • 버퍼 오버플로 상황 : 스택의 내용을 덮어 쓰는 strcpy 함수

        #include <string.h>
        
        int main(int argc, char ** argv) {
        	char str[10];
        	strcpy(str,
        			"akafjaskfjasfjaskfj132131431fasf");
        	return 0;
        }
        

        • 프로그램 충돌 발생 !!
          • strcpy가 스택의 내용을 덮어 쓴다 ⇒ 스택 스매싱 (smashing)
          • 배열 str 에는 10개의 문자열!
          • strcpy 는 배열 str에 10개 넘는 문자를 덮어 쓰고 있음!! ⇒ 이전에 푸시한 변수와 스택 프레임에 덮어 쓴다 ⇒ main 에서 잘못된 명령으로 건너뜀

5.1.1 스택 검사하기

• 스택 세그먼트
  • 소유자 프로세스만이 읽고 수정할 권한을 갖는 전용 메모리

• 디버거

  • 디버그 하려는 다른 프로세스에 붙여서 사용하는 프로그램

  • 디버거가 프로세스를 디버깅하면서 하는 작업 중에는 다양한 메모리 세그먼트를 관찰함

    • 프로세스를 디버깅할 때만 전용 메모리 블록을 읽고 수정 가능
    • 프로그램 명령어의 실행 순서를 제어함

    • 스택의 가장 위에 할당된 배열을 선언한 후 배열의 원소에 문자열 덧붙이기

      // File name: ExtremeC_examples_chapter5_1.c
      // Description: Example 5.1
      
      #include <stdio.h>
      
      int main(int argc, char** argv) {
        char arr[4];
        arr[0] = 'A';
        arr[1] = 'B';
        arr[2] = 'C';
        arr[3] = 'D';
        return 0;
      }
      

      • 힙에 메모리를 할당하는 malloc 함수를 사용하지 않음
      • 배열 arr에 필요한 메모리는 스택에 할당
        • 🚨 스택 메모리는 변수와 배열이 할당되는 기본 장소!
        • 스택의 최상단에 할당됨

  • 디버깅 하려면…

    • 디버깅 용도의 이진 파일이 반드시 빌드 되어야 함

    • 컴파일러로 디버그 심벌을 포함하는 이진 파일이 필요하다고 전달해야 함

      • 디버그 심벌 : 실행되는 코드 또는 충돌을 야기하는 코드 찾아냄

      • 디버그 심벌을 포함하는 실행 가능한 목적 파일을 만들어보자!

        ```bash
        gcc -g ExtremeC_examples_chapter5_1.c -o ex5_1_dbg.out
        ```
        
        - -g : 최종 실행 가능한 목적 파일에 디버깅 정보가 삽입된다
          - 컴파일 할 때 소스에 디버그 옵션이 있는지에 따라 이진 파일의 크기도 다르다
          - -g 옵션이 없을 때 vs -g 옵션이 있을 때
            ```bash
            gcc ExtremeC_examples_chapter5_1.c -o ex5_1_dbg.out
            gcc -g ExtremeC_examples_chapter5_1.c -o ex5_1_dbg.out
            ```
            ```bash
            ls -al ex5_1_dbg.out
            ls -al ex5_1.out
            ```
            - -g 옵션 없는 ex5_1.out (이진 파일)크기가 더 작음
        - **gdb** 를 통해 디버그를 시작해보자
        
          ```bash
          gdb ex5_1_dbg.out
          ```
        
          - 우리는 방금! gdb 명령어는 리눅스 머신에서 실행함
            - gdb 는 디버깅 명령어를 전달하는 **커맨드 라인 인터페이스** 가짐
            - 🚨 So, 디버거에 입력값으로 지정된 실행 가능한 목적 파일을 실행하려면 명령어 (**r** 아니면 **run**) 입력해야함!!!!!
            ```bash
            (gdb) run
            ```
            ![17.png](/assets/img/gani0325/17.png){: width="150" }
          - run 명령어를 전달하니 셸 박스에 gdb는 프로세스를 시작하고, 프로세스에 추가된 뒤, 프로세스가 명령어를 실행하고 종료함
            - gdb는 프로그램을 방해하지 않음
              - **중단점 (breakpoint)** 를 설정하지 않았기 때문
              - 중단점 : gdb가 프로그램의 실행을 멈추고 나중의 명령어를 기다리도록 하는 표시 (원하는 대로 얼마든 쓸 수 있음)
          - main 함수에 b 아니면 break 명령어를 사용해 중단점을 설정하자 - 중단점 설정하면 gdb는 프로그램이 main 함수에 진입할 때 실행을 중단시킨다
            `bash
        

        (gdb) break main ` - ex5_1.c (main 이 몇 번째 줄인지 확인)

        // File name: ExtremeC_examples_chapter5_1.c
        // Description: Example 5.1
        
                      #include <stdio.h>
        
                      int main(int argc, char** argv) {
                        char arr[4];
                        arr[0] = 'A';
                        arr[1] = 'B';
                        arr[2] = 'C';
                        arr[3] = 'D';
                        return 0;
                      }
                      ```
                    - **break로** main 함수 전 (6번 행)에 진입을 중지함
                    - 다시 ********\*\*********run********\*\********* 하니까 main 함수 (6번 행) 진입
        
                > **r or run** : gdb 실행
                >
                > **break main** : main 함수에서 중단점 설정
                >
                > **n or next** : 코드의 다음 행 실행
                >
                > **print arr** : 배열 내용이 문자열로 나타남
        

    • 디버거는 다음 명령어를 기다리며, 프로그램을 하나하나 한줄한줄 실행함

    • 메모리 내부의 변수와 변수가 갖는 값을 살펴보고 검사할 수 있음

      • 스택, 힙 세그먼트 검사할 때 사용함

      • 배열에 할당된 메모리 프린트 해보기

        • ex5_1.c (arr 확인)

          // File name: ExtremeC_examples_chapter5_1.c
          // Description: Example 5.1
          
          #include <stdio.h>
          
          int main(int argc, char** argv) {
            char arr[4];
            arr[0] = 'A';
            arr[1] = 'B';
            arr[2] = 'C';
            arr[3] = 'D';
            return 0;
          }
          

        (gdb) x/4b arr
        (gdb) x/8b arr
        

        x/4b 는 10진수, x/4bx 는 16진수

        • x/4b : arr 이 가리키는 지역에서 4바이트를 나타낸다
          • arr 은 배열의 첫 번째 원소를 가리키는 포인터
        • x/8b : arr 이 가리키는 지역에서 8바이트를 나타낸다
          • A, B, C, D 값은 배열 arr 에 저장된다
          • 배열에는 실제 문자열이 아니라 아스키값이 저장된다
            • A 의 아스키 값은 10진법으로 65, 16진수로 0x41
            • B 의 아스키 값은 10진법으로 66, 16진수로 0x42
          • ❓ 나머지 4바이트는 무엇?
            • 스택에 속한 것으로, main 함수를 호출하는 동안 스택 맨 위에 놓인 최근의 스택 프레임의 데이터를 포함한다
        • 다른 메모리 지역은 작은 주소부터 시작해서 주솟값이 더 커진다
        • 🚨 But, 스택 세그먼트는 큰 주소부터 채워지고 주솟값이 작아진다

    • 🚨 But, 스택 세그먼트는 큰 주소부터 채워지고 주솟값이 작아진다

      • 이해가 안가서 자료 찾아봄

        // File name: ExtremeC_examples_chapter2_5_main.c
        // Description: This file contains the 'main' function and a definition for another function 'add'.
        
        void add(int a, int b) {
          int c;
          c = a + b;
        }
        
        int main(void) {
          add(5, 6);
          return 0;
        }
        

        • 현재 main 함수의 주소가 func 함수의 주소보다 높은 주소에 위치

          

      • 주소가 커지는 방향으로 스택 세그먼트를 읽는다? → 스택 세그먼트에 이미 푸시된 내용을 just 읽는 것..
      • 또한 바이트 변경은 스택을 변경하는것, 좋은 방식 아님!
      • ❓ 왜 배열 arr 의 크기보다 더 큰 값이 보이는건가?
        • gdb는 우리가 요청한 메모리의 바이트 수를 검사
        • 명령어 x는 배열의 경계를 신경쓰지 않음!!!!
          • 범위를 출력하려면 오직 시작 주소와 바이트 수만 필요함
      • set 명령어로 배열의 개별 바이트 변경하기 (스택 내부의 값 변경)
        • set : 스택 내부의 값 변경하기 + 배열의 경계 바깥에 있는 개별 바이트 변경하기
          • 기존 메모리 셀을 수정함
          • 메모리 셀은 배열 arr에 있는 개별 바이트 참조함

            (gdb) x/4bx arr
            (gdb) set arr[1] = 'F'
            (gdb) x/4bx arr
            (gdb) print arr
            

      • set 명령어로 배열의 경계 바깥에 있는 개별 바이트 변경하기
        • set : 스택 내부의 값 변경하기 + 배열의 경계 바깥에 있는 개별 바이트 변경하기
          • 기존 배열 arr 보다 훨씬 더 큰 주소에 위치한 바이트 수정하기
          • 스택에 이미 푸시된 내용을 변경하기
          • 🚨 스택 메모리는 다른 세그먼트와 정반대로 채워진다는 것 유의

            (gdb) x/20bx arr
            (gdb) set *(0x7fffffffdc71) = 0xff
            (gdb) x/20bx arr
            

          • 배열의 경계 바깥에 있는 0x7fffffffdc71 주소에 0xff 값을 썼다
            • main 함수에 진입하기 전에 푸시된 스택 프레임 안에 존재하는 바이트
        • ❓ 실행을 계속 한다면 어떻게 될까?
          • 스택의 중요 바이트를 수정했다면 충돌 발생
            • 스택의 중요 바이트 변경하면 프로세스가 종료됨
              • 스택의 내용을 덮어 쓴다 ⇒ 스택 스매싱 (smashing)
              • 할당하지 않은 주소에 스택 내용을 수정한다면 충돌!
              • 🚨 So, 변수나 배열에 정의된 경계 바깥의 어떠한 값도 쓰지 않아야 하며! 스택 변수를 작성할 때 매우 주의 하셈
              • 스택 메모리에서 주소는 점점 작아지기 때문이다
              • 그래서 이미 작성된 바이트에 덮어쓰기 쉬움~
          • 어떤 메커니즘에 따라 수정이 감지되어 프로그램의 실행 중단
          • 명령어 (c or continue) 는 gdb 에서 프로세스를 계속 실행함
        • 디버그 마치고 gdb 에서 나갈 때 명령어
          • g 또는 quit

            (gdb) q
            

    • 🚨 추가 참고할 점, 스택의 가장 위에 할당된 버퍼 (바이트 또는 문자열 배열의 다른 이름) 에 할당되지 않은 값을 작성하는 일은 취약점으로 간주
      • 공격자가 이를 이용해 배열을 프로그램에 주입해서 통제함! ⇒ 버퍼 오버플로우 = 익스플로잇
      • 버퍼 오버플로 취약성을 나타내는 프로그램

        int main(int argc, char** argv) {
        	char str[10];
        	strcpy(str, argv[1])'
        	printf("Hello %s! \n", str);
        }
        

        • argv[1] 입력값의 내용과 크기를 검사하지 않고 배열 str 에 곧바로 복제함
        • 이 값은 스택의 맨 위에 할당됨
        • 흔치 않지만, 익스플로잇 야기함

5.1.2 스택 메모리 사용 시 주의점

• 스코프 (scope)
  • 각 스택 변수는 고유의 스코프를 갖고, 스코프는 변수의 수명을 결정함
  • 스택 변수가 한 스코프 내에서 수명을 시작해서 해당 스코프를 떠나면 죽는 것! ⇒ 스코프는 스택 변수의 수명을 결정함
• 스택 변수는 메모리에서 자동으로 할당하고 해제할 수 있지만 오직 스택 변수에만 해당!!!!
  • 스택 변수 선언할 때마다 스택 세그먼트의 가장 윗부분에 할당됨
  • 할당은 자동으로 이뤄지며 이는 변수 수명의 시작으로 기록됨
  • 이후 더 많은 변수와 스택 프레임이 스택의 맨 위에 놓임
  • 변수가 스택에 존재하고, 다른 변수가 그 위에 놓이는 한 그 변수는 계속 살아있음

• 🚨 But, 변수는 스택에서 팝 아웃 pop 됨

  • 미래의 언젠간,, 프로그램은 종료될 것이고 스택은 그 순간 비워져야 함
  • 해제 또는 팝아웃은 자동으로 이뤄지고, 이는 변수 수명의 끝으로 표시 ⇒ 개발자가 제어하지 않는 스택 변수의 메모리 관리가 자동으로 이뤄진다

  • 스택의 맨 위에 변수 하나 선언하기

    int main(int argc, char ** argv) {
    	int a;
    	...
    	return 0;
    }
    

    • 변수는 main 함수가 반환되기 전까지 스택에 남아 있음
      • 변수는 스코프 (main 함수) 가 유효할 때까지 존재함
        • main 함수는 모든 프로그램이 실행하는 변수이므로, 프로그램이 실행되는 내내 선언되는 전역 변수와 거의 같음

    • 🚨 하지만 전역변수는 아님 ^^

      • 변수는 스택에서 팝아웃 되는 때가 있음
        • 스택 세그먼트에 할당됨
      • 전역 변수는 main 함수가 종료되고 프로그램이 완료될 때도 메모리 갖는다
        • 데이터나, BSS 세그먼트에 할당됨

      • 스택의 가장 윗부분에서 변수를 선언하기

        // File name: ExtremeC_examples_chapter5_2.c
        // Description: Example 5.2
        
        int* get_integer() {
          int var = 10;
          return &var;
        }
        
        int main(int argc, char** argv) {
          int* ptr = get_integer();
          *ptr = 5;
          return 0;
        }
        

        • get_integer 함수는 지역변수 var 의 주소를 반환하지만 get_integer 함수의 스코프에서 선언된 것
          • get_integer 함수는 지역 변수의 주소를 반환함
        • main 함수는 받은 포인터를 역참조해 주소가 가리키는 메모리 지역에 접근하려고 함
          • 함수 내에서 지역 변수에 주소를 반환하는 흔한 실수!!!
          • 🚨 경고: 함수가 지역 변수의 주소를 반환합니다
        • 프로그램을 실행하면 발생하는 세그멘테이션 오류
          • 충돌이라고 할 수 있음
          • 일반적으로 이전에는 할당되었으나, 현재는 메모리 영역에 유효하지 않은 접근을 했기 때문!
• gdb 로 프로그램 실행하면 충돌에 관한 더 자세한 내용 나타남!
  • 컴파일 시 디버그 정보 삽입하는 -g 옵션을 사용해야 함!!!
  • gdb 또는 valgrind 같은 디버그 도구 사용하여 프로그램 디버그 가능
    • 이때도 -g 옵션 추가해서 소스 파일 컴파일 하기
  • 컴파일 시 -g 옵션 주고 디버거 실행하기
    • main 함수 내 11 번 행에 충돌 원인이 있음
    • 프로그램이 반환된 포인터를 역참조해서 반환된 주소를 작성하려는 곳
    • 변수 var 은 get_integer 함수의 지역 변수로, 더 이상 존재하지 않음
    • 반환된 포인터는 허상 포인터
  • 현재 스코프에 있는 변수의 주소를 가리키는 포인터를 다른 함수로 전달하는 것이 일반적.. - 현재 스코프가 유효한 이상, 변수는 현재의 스코프에 있기 때문! - 그런데 동시에 다른 작업이 현재 스코프 내에 있는 변수의 주소를 나타내는 포인터를 받아서 사용하려고 할 때는 전달되지 않음 (동시 프로그램에서는 좋은 방식이 XXX) - 현재 스코프는 이미 사라졌으니까!!

    💡 스택 세그먼트
    - 스택 메모리는 **크기가 제한적** (큰 객체 저장하기에 좋은 장소 X)
    - 스택 세그먼트의 **주소는 작아진다** (스택 메모리는 오름차순으로 읽으면, 이미 푸시된 바이트를 읽는 것임)
    - 스택은 **자동으로 메모리가 관리**됨 (할당 및 해제 모두)
    - **모든 스택 변수는 스코프**를 가지며 스코프는 변수의 수명을 결정함
    - **포인터는 계속 스코프 내에 존재하는 스택 변수만**을 가리켜야 함
    - 스택 변수의 **메모리 해제는 자동**으로 수행됨
      - 스코프가 종료되어 더이상 개발자가 통제할 수 없을 때 자동으로 해제
    - **현재 스코프에 존재하는 변수에 대한 포인터는 다른 함수의 인자로 전달** 될 수 있음 - 단, 호출된 함수에 있는 코드가 포인터를 사용하려고 할 때 현재 스코프가 여전히 그장소에 있다고 확인한 경우에만 가능! (동시성 로직 있을 땐 안됨)
    

⭐ 4.2 메모리 구조 알아보기

☑️ 힙을 왜 사용하는가?

• 스택은 컴파일시 크기가 결정될까? 런타임시 크기가 결정될까? 컴파일시 크기가 결정된다고 얘기하는 사람의 주장: int arr[a] 가 컴파일 오류이므로 컴파일시 크기가 결정된다. 런타임시 크기가 결정된다는 사람의 주장: 스택 오버플로우가 런타임시 발생하므로 런타임에 크기가 결정된다.
• 힙은 자동으로 할당되는 메모리 블록을 갖지 않습니다. 개발자가 malloc 또는 그와 유사한 함수를 사용해서 힙 메모리 블록을 하나씩 얻어야 합니다. 자동 할당이 되지 않습니다. 대신 스택 메모리가 이 약점을 보완해 줍니다.
• 힙은 메모리 크기가 큽니다. 힙 크기가 커질수록 할당자는 운영체제에서 힙 페이지를 더 많이 요청해야 합니다. 힙메모리 블록은 이 페이지를 따라 더 전파 됩니다. 스택 세그먼트와 달리, 힙 메모리에서 할당되는 주솟값은 점차 더 커집니다.
• 힙 메모리 내에서 메모리의 할당과 해제는 개발자가 관리합니다. 개발자가 할당과 해제를 맡습니다. 가비지 컬렉터가 없는 C와 C++은 수동으로 비워야 합니다. 이에 실패하면 메모리 누수가 발생합니다.
• 스택의 변수와는 달리 힙에 할당된 변수는 스코프를 전혀 갖지 않습니다.
• 변수를 언제 해제해야 할지도 모르며, 효율적으로 메모리를 관리하려면 메모리 블록의 스코프와 소유자를 위한 새로운 정의를 생각해야 합니다.
• 힙 메모리 블록의 주소를 지정하려면 포인터만 사용할 수 있습니다. 힙 변수와 같은 개념은 존재하지 않고 힙 지역은 포인터를 통해 주소가 지정됩니다.
• 힙 세그먼트는 소유자 프로세스의 전용이므로 검사하려면 디버거를 사용해야 합니다.

5.2.1 힙 메모리의 할당과 해제

☑️ 힙 메모리

수동으로 얻고 비워야 합니다.

개발자가 일련의 함수나 API를 사용해야 한다는 뜻입니다.

stdlib.h 에 정의됩니다. malloc, calloc, realloc입니다. 힙 메모리 블록을 해제하는데 사용되는 유일한 함수는 free입니다.

gcc ExtremeC_examples_chapter5_3.c -o ex5_3.out
./ex5_3.out

• calloc은 청소 및 할당 malloc은 메모리 할당입니다.

  realloc 함수는 이전의 블록에 있는 데이터를 변경하지 않으며 이미 할당된 블록을 새로운 블록으로 확장합니다.

• 단편화

  (단편화란, 힙 영역에 메모리가 남아있으나 블록을 할당하기 어려운 상황, 즉 공간이 파편화되는 현상)

  단편화 때문에 현재 할당된 블록을 확장할 수 없을 때는 다른 충분히 큰 블록을 찾은 뒤 이전 블록에서 새 블록으로 데이터를 복제합니다.

• 메모리 누수 감지 도구 valgrind

  디버그 -g옵션과 valgrind도구

  gcc -g ExtremeC_examples_chapter5_4.c -o ex5_4.out
  valgrind ./ex5_4.out
  

• free(ptr) 코드 수정이후 valgrind로 메모리 누수 확인

  메모리 누수는 설계까 올바르지 않아서 누수를 야기하는 경우 기술부채로 간주되며, 무슨일이 발생할지 알지 못하는 경우에는 또한 위험요인이라고 봅니다.

  valgrind외에도 다른 메모리 프로파일러로 MemProf도 있습니다.

5.2.2 힙 메모리 원칙

스택 메모리와 몇몇 방식에서 차이가 있습니다.

힙 메모리는 메모리관리에 관한 자체 가이드 라인이 있습니다.

스택의 모든 메모리 블록은 스코프를 갖습니다. 따라서 이 스코프에 따라 메모리 블록의 수명을 정의하기는 쉬운 일입니다.

힙 메모리 블록은 아무 스코프도 갖지 않습니다. 자바 같은 현대 언어는 세대별 가비지 컬렉션을 사용합니다. 힙의 수명은 프로그램 자체에서 정의되거나 사용된 C라이브러리로는 정의될 수 없습니다. 개발자만이 힙 메모리 블록의 수명을 결정할 수 있는 유일한 존재입니다. 힙의 수명은 개발자가 정하므로 상호 절충안, 트레이드 오프가 됩니다.

• 이중 해제

  블록을 소유하지 않는다면 어느 것도 힙 메모리 블록을 해제해서는 안 됩니다. 이중 해제(더블 프리)가 메모리 손상 문제에 해당합니다.

  • C언어용 가비지 컬렉터 Boehm-Demers-Weiser Conservative Garbage Collector입니다.

  • RAII객체

    RAII는 리소스 획득은 초기화. 메모리 블록에 할당된 힙과 같은 리소스의 수명을 어떤 객체의 수명과 연결할 수 있다는 뜻입니다. 어떤 객체를 사용하는 상황에서 객체를 생성하면 리소스를 초기화하고, 파괴하면 리소스가 해제된다는 뜻입니다.

    C에서는 이 기술을 사용할 수 없습니다. 객체가 파괴되었다는 정보를 전달받을 수 없기 때문입니다. 하지만 C++에서는 소멸자를 이용해 이 기술을 효과적으로 사용합니다.

  • 힙 메모리 가이드라인
    • 힙 메모리할당에는 치러야 할 나름의 비용이 있습니다. 모든 메모리 할당 함수가 같은 비용을 치르는 것은 아니지만 malloc은 대체로 그 비용이 가장 덜 드는 함수입니다.
    • 힙 공간에 할당된 모든 메모리 블록은 더 이상 필요하지 않을 때나 프로그램을 종료하기 직전에 반드시 해제되어야 합니다.
    • 각각의 힙 메모리 블록에 대한 메모리 관리 전략을 고수해야 합니다.
    • 선택한 전략과 전략에 관한 가정은 블록에 접근할 때마다 코드에 기록되어야 합니다.
    • C++ 같은 특정 프로그래밍 언어에서는 RAII객체를 사용해 힙 메모리 블록과 같은 리소스를 관리할 수 있습니다.

  힙 메모리는 큰 객체를 저장하기에도 충분하고 어떤 프로그램을 실행하기에도 충분한 메모리를 가졌다고 가정했습니다.

  다음 절에서는 사용 가능한 메모리에 제한을 둘 것이며, 메모리가 부족하거나 메모리 저장소를 추가하는데 드는 비용(메모리, 시간, 성능 등) 이 큰 환경에 관해 다루겠습니다. 이럴 때는 가장 효율적인 방식으로 가용 메모리를 써야 합니다.

⭐ 5.3 제한된 환경에서의 메모리 관리

☑️ 메모리가 제한적인 환경에서

메모리가 제한적인 이유 : 메모리 사용에 대한 하드 리밋, 저용량의 메모리를 제공하는 하드웨어, 더 큰 메모리를 지원하지 않는 운영체제

메모리 사용은 프로젝트에서 중요한 비기능 요구 사항의 하나이다.

메모리가 적은 환경에서 극복하는 기술과 실행 프로그램의 성능을 향상하기 위한 환경을 사용하는 메모리 기법을 설명합니다.

5.3.1 메모리가 제한된 환경

시간 복잡도가 높은데 낮은 메모리 사용과 타협해야 하는 관계.

시간 복잡도와 메모리 복잡도는 Big-O 함수로 나타냅니다.

1. 메모리가 충분하지만 메모리가 제한 적인 환경에 있다고 생각하고 코드를 작성하는 방법.

   • 패킹된 구조체 패딩을 포기하고 구조체를 패킹시킵으로서 더 작은 메모리 레이아웃을 갖습니다. 메모리 정렬을 폐기하기 때문에 메모리를 덜 사용하지만 변수를 로드하는 동안 워드 단위로 읽기 때문에 메모리를 읽는 시간이 더 듭니다.
   • 압축 텍스트 데이터가 이진 파일 데이터에 비해 압축률이 높습니다. 하지만 압축과 압축해제를 하기위한 작업이 필요해지고, 압축 알고리즘을 CPU바운드 이자 계산 집약적이므로, 프로그램 성능은 떨어집니다.
   • 외부 데이터 저장소 네트워크 서비스, 클라우드 인프라, 또는 단순히 하드디스크 드라이브의 형태로 외부 데이터 저장소를 사용하여 메모리 부족 문제를 해결합니다. 메모리가 메인 저장소가 아닌 캐시 메모리의 역할을 한다고 가정하고 언제든 데이터의 일부나 페이지만 메모리에 로드할 수 있다고 가정합니다. PostgreSQL이나 오라클 같은 모든 데이터 베이스 서비스가 이 기술을 사용합니다.

5.3.2 성능이 더 나은 환경

성능을 향상시키기 위한 방법입니다.

캐시를 적절히 사용한다.

• 캐싱 캐싱이란 두 데이터 저장소가 서로 읽기/쓰기 속도가 다를 때 컴퓨터 시스템의 많은 부분에서 사용되는 모든 비슷한 기법을 가리키는 일반적인 용어입니다. 예를 들어 CPU가 연산하기위해 메모리로부터 데이터를 가져와야하는데(fetch) 이 작업은 레지스터보다 훨씬 더 느립니다. 이때 캐싱 메커니즘을 사용합니다. 트레이드오프할 수있는점 : 많은 항목을 포함하는 느린 저장소 vs 더 빠르지만 제한 된 수의 항목만 가질 수 있는 저장소 더 빠르지만 더 작은 저장소는 캐시라고 할 수 있습니다. 많은 항목을 부른다면 캐시저장소가 아닌 더 많은 항목의 느린 저장소를 가져와야할 때도 있을 겁니다.

• 캐시 친화적 코드

  • CPU 가 명령어를 실행할 때는 우선 필요한 데이터를 모두 가져옴
    • 데이터는 메인 메모리의 특정 주소에 저장되며 이 주소는 명령어에 의해 결정됨
  • 연산하기 전에 데이터는 CPU 레지스터로 전송되어야 함
    • 보통 CPU 는 가져와야 (fetch) 하는 것보다 더 많은 블록을 가져와 캐시에 넣음
  • 어떤 값에서 이전의 주소에 대한 근접성이 필요하다면, 이 값은 캐시 내에 존재해야만 하고, CPU는 메인 메모리 대신 캐시를 사용할 수 있음
    • 메인 메모리로부터 값을 읽는 것보다 훨씬 빠름 ⇒ 캐시 적중 (cache hit)
  • CPU 캐시에서 주소를 찾을 수 없다면 캐시 실패 (cache miss)
  • CPU 는 대상 주소를 읽고자 메인 메모리에 접근해서 필요한 데이터를 가져와야 하며, 이 방식은 상당히 느리다
    • 캐시 적중률이 높으면 실행이 더 빠름

  • ❓ CPU는 왜 이웃 주소 (근접성) 가져와야 할까? ⇒ 지역성의 원리

    • 컴퓨터 시스템에서는 보통 같은 이웃에 위치한 데이터가 더 자주 접근된다고 관찰됨
    • CPU 는 이 원리에 따라 지역 참조로부터 데이터를 더 많이 가져옴
    • So, CPU 가 알고리즘을 더 빨리 실행할 수 있음 ⇒ 캐시 친화적 알고리즘

    • 캐시 친화적 코드 vs 비 캐시 친화적 코드 성능 나타내기

      • ⬇️ 행렬의 모든 원소의 합을 계산하고 출력

        // File name: ExtremeC_examples_chapter5_6.c
        // Description: Example 5.6
        
        #include <stdio.h>  // For printf function
        #include <stdlib.h> // For heap memory functions
        #include <string.h> // For strcmp function
        
        void fill(int* matrix, int rows, int columns) {
          int counter = 1;
          for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
              *(matrix + i * columns + j) = counter;
            }
            counter++;
          }
        }
        
        void print_matrix(int* matrix, int rows, int columns) {
          int counter = 1;
          printf("Matrix:\n");
          for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
              printf("%d ", *(matrix + i * columns + j));
            }
            printf("\n");
          }
        }
        
        void print_flat(int* matrix, int rows, int columns) {
          printf("Flat matrix: ");
          for (int i = 0; i < (rows * columns); i++) {
            printf("%d ", *(matrix + i));
          }
          printf("\n");
        }
        
        int friendly_sum(int* matrix, int rows, int columns) {
          int sum = 0;
          for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
              sum += *(matrix + i * columns + j);
            }
          }
          return sum;
        }
        
        int not_friendly_sum(int* matrix, int rows, int columns) {
          int sum = 0;
          for (int j = 0; j < columns; j++) {
            for (int i = 0; i < rows; i++) {
              sum += *(matrix + i * columns + j);
            }
          }
          return sum;
        }
        
        int main(int argc, char** argv) {
        
          if (argc < 4) {
            printf("Usage: %s [print|friendly-sum|not-friendly-sum] ", argv[0]);
            printf("[number-of-rows] [number-of-columns]\n");
            exit(1);
          }
          char* operation = argv[1];
          int rows = atol(argv[2]);
          int columns = atol(argv[3]);
        
          int* matrix = (int*)malloc(rows * columns * sizeof(int));
          fill(matrix, rows, columns);
        
          if (strcmp(operation, "print") == 0) {
            print_matrix(matrix, rows, columns);
            print_flat(matrix, rows, columns);
          }
          else if (strcmp(operation, "friendly-sum") == 0) {
            int sum = friendly_sum(matrix, rows, columns);
            printf("Friendly sum: %d\n", sum);
          }
          else if (strcmp(operation, "not-friendly-sum") == 0) {
            int sum = not_friendly_sum(matrix, rows, columns);
            printf("Not friendly sum: %d\n", sum);
          }
          else {
            printf("FATAL: Not supported operation!\n");
            exit(1);
          }
        
          free(matrix);
          return 0;
        }
        

        • 사용자는 프로그램에 옵션에 전달해 행동 변경 가능
          • fill 함수에 쓰인 알고리즘으로 초기화된 2행 3열 행렬 출력해보자
            • 필요한 행과 열 숫자와 print 옵션 입력해야 함
            • ./ex5_6.out print 2 3 을 통해 print 옵션 전달
        • 출력 결과
          1. 행렬을 2차원으로 표현
          2. 같은 행렬을 1차원으로 표햔
        • 행렬은 메모리에 행-우선 순위로 저장되었음
          • 행렬이 한 행씩 저장된다는 의미
        • CPU 가 어떤 행에서 뭔가를 가져오려고 한다면, 그 행의 모든 원소 또한 가져와야 함
          • 열-우선이 아니라 행-우선순위에서 이 코드의 합계 연산이 잘 수행됨
        • friendly_sum 함수
          • 행-우선으로 합계가 수행됨
        • not friendly_sum 함수
          • 열-우선으로 합계가 수행됨
        • 20,000 개의 열과 행의 행렬 합계 수행 시간 비교하기
          • 같은 로직과 같은 양의 메모리를 사용하더라도, 행렬의 원소에 접근하는 순서를 다르게 선택하면 시간이 훨씬 오래 걸릴 수 있음
          • time
            • 특정 프로그램의 실행 시간을 측정하기 위한 명령어
              • real : 총 실행 시간 (실제 커맨드 실행하는데 걸린 시간)
              • user : user 영역에서 실행된 시간
              • sys : 커널 영역에서 실행된 시간
• 할당 및 해제 비용
  • 힙 메모리 해제와 할당 작업은 시간과 메모리를 소비하여 비용이 더 필요함
  • 상대적으로 더 빠르며 할당 자체에 메모리가 더 필요하지 않은 스택 할당과 달리,
    • 힙 할당은 충분한 크기의 비어 있는 메모리 블록을 찾아야 함
  • 메모리 할당과 해제를 위해 설계된 많은 알고리즘 多
    • 할당과 해제 작업 사이에서 언제나 타협 (trade off) 필수
    • 메모리를 빠르게 할당하고 싶다면 메모리를 더 많이 사용
    • 메모리를 덜 사용하고 싶다면 시간이 더 드는 느린 할당 받기
  • 기본 C 표준 라이브러리
    • malloc
    • free
    • ptmalloc
    • tcmalloc
    • Haord
    • dlmalloc
  • ❓ 치명적일 수도 있는 이 문제의 해결책은?
    • 할당과 해제를 최소화 하는 것
    • 대체로 힙 메모리의 큰 블록을 할당하며 관리하려고 함
    • 마치 커다란 힙 메모리 블록 위해 놓은 할당과 해제의 로직에 대한 추가 레이어를 갖는 것과도 같음
    • 그밖에도 + 메모리 풀 이용
• 메모리 풀
  • 메모리 할당과 해제는 비용이 듦
    • 미리 할당되어 고정된 크기의 힙 메모리 블록의 풀을 사용하는 방법은 할당의 횟수를 줄이고 성능을 약간 향상함
  • 풀의 각 블록
    • 일반적으로 식별자를 가지며, 식별자는 풀 관리를 위해 설계된 API 를 통해 얻을 수 있음
    • 필요 없어지면 이 블록은 나중에 해제됨
    • 할당된 메모리 양이 고정된 채 남으므로, 메모리가 제한적인 환경에서 알고리즘이 결정론적인 행위를 하려고 할 때 탁월한 선택임

⭐ 5.4 마무리

스택과 힙 세그먼트를 다뤘으며 이들 세그먼트가 사용되는 방식을 살펴봤습니다.

• 스택 및 힙 세그먼트 모두를 검사할 때 사용되는 도구와 기법을 설명했습니다.
• 디버거를 소개했으며 메모리와 관련된 문제를 고치는 메인 디버거로 dgb를 사용했습니다.
• 메모리 프로파일러를 설명했고, 실행할 때 발생하는 누수나 허상 포인터와 같은 문제를 발견하기 위해 valgrind를 사용했습니다.
• 스택 변수와 힙 블록의 수명을 비교했으며 그러한 메모리 블록의 수명을 판단하는 법을 설명했습니다.
• 스택 변수의 경우 메모리 관리가 자동이지만 힙 블록에서는 전적으로 수동이라는 점을 알아봤습니다.
• 스택 변수를 다룰 때 저지르는 흔한 실수를 살펴봤습니다.
• 제한된 환경을 논의 했으며 이러한 환경에서 메모리를 어떻게 튜닝할 수 있는지 알아봤습니다.
• 성능이 더 나은 환경과 성능을 얻고자 할 때 사용할 수 있는 기법은 무엇이 있는지 설명했습니다.