[malloc] 동적 메모리 할당

📌동적 메모리 할당

• 컴퓨터 프로그래밍에서 실행 중에 사용할 메모리 공간을 할당하는 것을 의미
• 정적 할당 : 컴파일시점에 소스 코드를 읽고 메모리 공간을 확보하는 것
• 동적 할당 : 컴파일 시점이 아닌 프로그램이 실행되는 중인 런타임에 필요한 만큼의 메모리 공간을 확보하는 것을 의미한다.

💡동적할당을 하는 이유?

• char name [100];
• name 배열은 최대 100개 까지 저장이 가능할 것이다. 그런데 막상 프로그램을 실행 시켜서 10글자만 입력했다. 그렇다면 90바이트는 어떻게 될? 그냥 낭비가 되는것이다. 반대로 100글자를 저장할 수 있는데 110글자를 입력하려고 한다. 이것 또한 문제이다.
• 위와 같은 문제를 해결해주는 것이 바로 동적 메모리 할당이다. 동적으로 할당한다는 말은, 프로그램이 시작된 후에 필요에 따라서 그떄 그떄 메모리를 할당하고 저장하겠다는 의미이다. 위와 같은 예에서 사용자가 입력할 공간을 미리 설정해 놓지 않고 그떄 그떄 프로그램이 실행 되는 시간에 10글자면 10바이트 , 110글자이면 110바이트의 메모리를 정확하게 할당하여 사용하자는 의도이다.

 

📌malloc()

• c에서 동적 메모리 할당을 위해서는 보통 malloc 계열의 함수들을 사용한다.
• void* malloc(size_t size)//malloc함수의 원형
• 말록은 void* 를 리턴한다 따라서 내가 원하는 타입으로 형변환이 가능하다. size_t는 unsignde int를 typedef 해놓은 것이다. 할당할 메모리가 음수값이 될리는 없기에 unsigned로 정해놓은 것이다. size에는 우리가 원하는 메모리 공간의 바이트 수를 써주면 된다.
• malloc 함수는 size만큼 바이트를 메모리 공간에서 할 당한 후 그 첫번쨰 주소값을 리턴해주며 그 타입은 void*이다
• 왜 void* 을 리턴하는 이유는 동적으로 메모리 할당을 하는데 정수를 저장할지, 배열을 저장할지, 구조체를 저장할지 실직적으로 모르기 때문이다.

• char* pi =(char* p) malloc (sizeof(int)*10);
• //char 10개를 저장할 수 있는 메모리공간을 할당하고 그 첫번쨰 주소를 char형으로 형변환하여 pi에 저장

 

📌calloc()

• void* colloc(size_t n , size_t size)
• malloc과 달리 함수의 매개변수가 2개이다. 앞에 n은 할당할 메모리의 단위 갯수이며, 뒤에 size는 하나당 크기를 이야기 한다. 한마디로 4개x4바이트, 10개 1바이트와 같은것이다.
• malloc과 다른점은 malloc은 할당된 메모리를 초기화하지 않아서 쓰레기 값이 그대로  들어깄지만, calloc함수는 할당된 메모리 공간을 모두 0 으로 초기화 시켜준다. 

---

📌시스템 콜

• 운영체제(OS)는 '커널 모드'와 '유저 모드'로 구성된다. 우리가 개발하는 프로그램은 일반적으로 유저 모드에서 실행된다. 시스템 콜은 OS가 제공하는 기능으로 커널 영역의 기능을 사용자 모드에서 사용하게 해주는 기능이다. 프로그램 실행 중에 인터럽트가 발생하거나 시스템 콜을 호출하게 되면 커널모드로 전환된다. 커널 모드는 프로그램의 현재 CPU상태를 저장하고 CPU에서 커널 코드가 실행된다. 처리가 완료되면, 중단됐던 프로그램의 CPU 상태를 복원하고 통제권을 유저 모드로 넘겨준다.커널모드는 시스템을 보호하기 위해 존재한다. 우리가 개발한 프로그램이 함부로 하드웨어를 점유하면, 문제가 발생할 수 있다.

 

📌 sbrk / mmap 함수

• brk, sbrk 시스템콜은 malloc 함수와 같은 메모리 할당을 요청할 때 사용되는 시스템콜이다. malloc 함수 실행 후 실제 메로리를 할당 받기 위해선 brk, sbrk, 또는  mmap 시스템 콜을 수행해야한다.

#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

 

📌데이터 세그먼트

• 프로세서는 cpu가 실행파일에 있는 명령들을 실행할 수 있도록 OS가 실행 파일의 명령들을 읽어서 메모리에 재구성한 것이다. 프로세스는 세그먼트의 집합으로 구성된다.

💡코드 세그먼트

• 실행할 프로그램의 코드가 저장되는 영역으로 text 영역이라고도 함
• cpu는 이 영역에서 명령어를 하나씩 가져와 처리함
• 코드 영역은 소스코드가 저장되는 영역으로, 컴퓨터가 실행해야할 명령어들이 순서대로 쌓이는 메모리 영역이다.
• 코딩한 것을 실행시키면 cpu가 알아서 코드 영역에 저장된 명령어들을 하나씩 가져가 처리하는 방식으로 컴퓨터가 알아서 처리하기 떄문에 따로 신경 쓸 필요가 없는 영역이다.

💡데이터 세그먼트

• 전역 변수와 정적 변수가 할당되는 영역
• 프로그램이 시작될 때 할당되어, 프로그램이 종료하면 소멸됨
  • 전역 변수 : 함수 외부에 선언되어 있으므로 프로그램이 시작할 때 생성되고, 프로그램이 끝날  때 소멸
  • 정적 변수  : 선언한 위치에서 메모리가 생성되고, 프로그램이 끝날 때 소멸

💡스택 세그먼트

• 사용자에 의해 메모리가 할당되고 해제되는 영역
• 필요에 의해 동적으로 메모리를 할당할 때 사용
• 가상 메모리 영역을 관리
• 프로그램 동작시에 크기가 결정됨
• 메모리 주소값에 의해서만 참조되고 사용되는 영역
  1. 힙 (heap)  : 메모리의 낮은 주소에서 높은 주소의 방향으로 할당됨
  2. 지역변수 ( stack ) : 메모리의 높은 주소에서 낮은 주소의 방향으로 할당

#include <stdio.h>

int x = 1;              // Data 영역
int y;                  // BSS 영역: 초기화 되지 않은 데이터(전역 변수)

int main(){
    int z;                  // Stack 영역: 지역 변수
    static int st_a;        // BSS 영역
    static int st_b = 1;    // Data 영역: static
    char* c;                // Stack 영역
    c = malloc(10);         // Heap 영역
    y = 2;                  // Code 영역
 
    return 0;
}

 

📌메모리 할당 malloc() , free()

• 위 그림은 18워드의 작은 힙을 malloc과 free을 통해 관리하는 것을 보여준다
• 그림 a : 4워드 블록을 요청하며, 이 블록의 첫 번째 워드를 가리키는 포인터를 리턴한다.
• 그림 b : 5워드 블록을 요청하며, 6워드 블록을 할당하는데 이유는 이 예제가 더블 워드 경계에 정렬되도록 하기 위해 1워드가 추가 패딩 된 것이다.

정렬 제한 조건
정렬 제한 조건이란 할당기에 블록을 할당 시 블록들이 가지는 byte의 수가 정렬 조건의 배수가 되게 하는 것이다.
책에서는 더블워드(8byte)의 데이터를 확보한다면 헤더(4byte) + 데이터(8byte)가 되어 12byte가 필요한데 더블 워드 정렬 조건으로 byte가 8의 배수가 되어야 한다. 이때 패딩 4byte 하나를 추가하여 8의 배수를 맞춰준다.

• 그림 c : 6워드 블록을 요청하며, malloc은 가용 블록에서 6워드 블록을 할당
• 그림 d : free로 호출이 리턴된 후에 포인터 p2는 여전히 malloc된 블록을 가리킨다.
• 그림 e : 2워드 블록을 요청하며, 이전 단계에서 반환된 블록의 부분을 할당하고, 새로운 블록의 포인터를 리턴한다.

📌묵시적 가용 리스트

• 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다.
• 한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성된다.
• 헤더 : 블록 크기와 할당 여부를 담는다.
• 데이터  : 담아야할 데이터를 담는 부분
• 패딩 : 외부 단편화를 극복하기 위한 전략의 일부분으로 사용될 수도 있고, 정렬 요구사항을 만족하기 위해 필요.

보통 하나의 블록은 4바이트나 8바이트로 구성하는데, 그걸 부르는 단위를 word라고 부른다, 따라서 1워드는 4바이트고, 더블 워드가 될 경우 8바이트가 된다. 블록 크기는 대개 4의 배수 혹슨 8의 배수로 구분된다.

• 첫 층은 블록의 헤더로서 블록 크기와 가용 여부를 나타낸다. 가용 여부는 3자리 비트로 이루어 진다. 마지막 비트의 0과 1로 할당과 가용을 구분한다. 앞 뒤 2자리가 왜 있냐면, 블록 크기는 16진수 비트로 이루어지는데 가용 여부 또한 16진수 비트로 구성해야 비트 연산을 통해 하나의 16진수로 구성할 수 있기 때문이다.
• 두번째 층은 데이터이다. 할당된 블록의 경우 특정한 자료가 담긴다.
• 세번째 층은 패딩이다. 패딩은 블록의 크기를 일괄적으로 정렬해야 하기 때문에 들어간다. 블록의 크기는 규격화 되어야 효율성이 증가한다. 하나의 블록 크기가 다 다르다면 컴퓨터는 블록을 다 따로따로 계산해야한다.

예를들어 크기가 2byte인 데이터를 넣어야 하면, 컴퓨터는 16byte 블록을 할당할 것이다. 왜냐하면 header와 footer는 무조건 들어가야하는데, 이들은 각각 4바이트씩이다.

 

2+4+4 = 10바이트로 생성 요건을 충족하였지만, 방금 말했듯이 규격화 해야하고 8의 배수 등으로 무조건 정렬 조건을 만족해야 하기 때문이다. 이미 들어가야 하는 자료가 8byte를 넘으니 6바이트를 더해 16바이트 블록을 할당한다.

이때 패딩을 사용해 6바이트가 들어가게 된다.

 

• 마지막 층은 블록의 푸터로서 헤더와 동일한 기능을 수행한다. 굳이 2개를 만들어야 하는 이유는
• 시간적으로 블록의 연결을 줄일 수 있기 떄문이다. donald knuth라는 사람이 경계 태그라는 기법을 개발했는데, 각 블록이 푸터를 포함하게 되면 할당기는 시작 위치와 이전 블록의 상태를 자신의 푸터만 조사해서 파악할 수 있다. 이전 블록은 항상 현재 블록의 시작 부분에서 1word 앞에 위치하기 때문이다.

푸터를 넣음으로써 이전 블록과 다음 블록의 상태를 쉽게 파악할 수 있다. 물론, 장점만 있는것은 아니다. 모든 블록이 헤더와 푸터를 유지해야 하므로 블로그이 개수가 많아지면 메모리 오버해드가 발생할 수 있다.

여기서 이 연속된 배열은 가용리스트다. 실제 malloc 구현할때 쓰이는 개념이다.

• 패딩 : 위에 설명한 용도의 패딩과 똑같다.
• 프롤로그 헤더, 푸터 : 메모리를 할당하거나 반환하다보면 블록을 연결해야 할 일이 생긴다. 그 연결 과정 동안에 가장자리 조건을 없애기 위한 트릭
• 에필로그 헤더 : 에필로그 헤더 또한 프롤로그와 같은 일종의 트릭이다.
• header, footer : 실제로 데이터가 들어가는 블럭의 헤더와 푸터이다. 위에 블록 그림에서 설명한 헤더와 푸터라고 이해하면 됨
• malloc프로그램은 전체 힙에서 이 가용 리스트를 할당한 다음, 가용 리스트 내부에 블록을 할당 & 반환하고, 가용 리스트가 넘치면 새로운 리스트를 추가하고 빼는 식의 프로그램이라고 생각하면된다.

📌할당할 블록 배치 방법

1. First fit
   리스트를 처음부터 탐색해서 크기가 맞는 첫 번째 가용 블록을 선택한다.
2. Next fit
   First fit과 유사하지만, 검색을 리스트의 처음에서 시작하는 대신에 검색이 종료된 지점에서 검색을 시작한다.
3. Best fit
   모든 가용 블록을 검사하여 크기가 맞는 블록 중 가장 작은 블록을 선택한다.

📌경계 태그로 연결하기

• 만약 반환하여 가용상태로 만드는 블록이 현재블록이라고 할때, 다음 가용 블록을 연결하는 것은 간단하다. 현재 블록의 헤더의 주소에서 헤더의 크기를 더해주면 다음 블록의 헤더를 찾을 수 있다. 하지만 이전 블록을 찾기 위해서는 앞에서부터 다시 탐색해야 가능하다.
• 위 가용 블록하는 과정을 쉽게 하기 위해 블록에 새로운 요소 푸터가 추가 된다.

💡연결하는 네가지 경우

 

1. case1: 이전과 다음 블록이 모두 할당되어 있는 상태
   • 현재 블록의 상태를 변경하면 된다.
2. case:2 이전 블록은 할당 상태, 다음 블록은 가용상태
   • 현재블록과 다음 블록이 통합된다.
3. case:3 이전 블록은 가용상태, 다음 블록은 할당 상태
   • 이전 블록의 헤더와 현재 블록의 풋터는 두 블록의 크기를 합한 것이다.
   • 이전 블록과 다음 블록 통합
4. case:4 이번 블록과 다음 블록 모두 가용 상태이전 블록의 헤드와 다음 블록의 푸터는 세 블록의 크기를 합한 것으로 갱신된다.
   • 세 블록 모두 하나의 가용 블록으로 통합

 

📌단편화

메모리 단편화
- 메모리 공간이 작은 조각으로 나눠져 사용 가능한
메모리가 충분히 존재하지만 할당(사용)이 불가능한 상태

💡내부 단편화

• 메모리를 할당할 때 프로세스가 보다 더 큰 메모리가 할당되어 사용하는 메모리 공간을 낭비할 때

💡외부 단편화

• 총 메모리 공간은 충분하지만 요청을 처리할 수 있는 단일한 가용 블록이 없을 때 발생

• 위 그림에서 파란 부분은 메모리 할당 상태 흰색은 가용 상태 블록을 나타낸다.
• 만약 위의 상태에서 8블록을 요청하면 가용 블록의 수(흰색)는 8개로 충분하지만 
• 단일 가용 블록은(6개 p2와 p3 사이)는 8개가 되지 않아 외부 단편화가 발생한다.