Malloc-lab

메모리 구조

프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(load)되어야 한다.

또한, 프로그램에서 사용되는 변수들을 저장할 메모리도 필요하다.

1. 코드(code) 영역
   메모리의 코드(code) 영역은 실행할 프로그램의 코드가 저장되는 영역이다.
   CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리한다.

2. 데이터(data) 영역
   메모리의 데이터(data) 영역은 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역이다.
   데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸한다.

3. 스택(stack) 영역
   메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역이다.
   스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.
   스택 영역은 푸시(push) 동작으로 데이터를 저장하고, 팝(pop) 동작으로 데이터를 인출한다.
   스택은 후입선출(LIFO, Last-In First-Out) 방식에 따라 동작하므로, 가장 늦게 저장된 데이터가 가장 먼저 인출된다.
   스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당된다.

4. 힙(heap) 영역
   메모리의 힙(heap) 영역은 사용자가 직접 관리할 수 있는 메모리 영역이다.
   힙 영역은 사용자에 의해 메모리 공간이 동적으로 할당되고 해제된다.
   힙 영역은 메모리의 낮은 주소에서 높은 주소의 방향으로 할당된다.

+ (추가)프로그램 실행 후 스택 메모리의 변화

메모리의 동적 할당(dynamic allocation)

데이터 영역과 스택 영역에 할당되는 메모리의 크기는 컴파일 타임(compile time)에 미리 결정된다.

런 타임에 메모리를 할당받는 것을 메모리의 동적 할당(dynamic allocation)이라고 한다.

동적 할당 메모리는 힙 영역에 생성되게 되며 컴파일 타임에 메모리의 크기가 결정되는 데이터 영역이나 스택 영역의 정적 메모리 할당과는 대조적인 개념이다.

동적 메모리 할당의 필요성

프로그램이 동적 메모리 할당을 사용하는 가장 중요한 이유는 종종 이들이 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.

또한, 정적 메모리 할당을 하게 되면, 기억공간이 낭비될 경우가 많다. (배열)
메모리의 낭비를 최소화하기 위해서는 프로그램의 실행 중에 입력되는 데이터에 맞게 기억공간을 할당할 필요가 있다.

malloc 함수 사용법

#include <stdlib.h>

malloc 함수를 사용하기 위해서는 malloc 함수가 포함되어 있는 <stdlib.h> 헤더를 선언해야 한다.

#include <stdlib.h> //malloc 함수가 포함된 헤더 파일

malloc 함수 호출

함수 호출시 할당하고자 하는 메모리의 크기를 바이트 단위로 전달하면 그 크기만큼 메모리를 할당하게 된다.

할당한 메모리의 주소(첫 번째 바이트의 주소)를 리턴한다.

메모리 할당에 실패하면 NULL이 리턴된다.

int *i = (int*) malloc (sizeof(int));

리턴형 : void*(void 포인터)

malloc은 단순히 메모리만 할당하는 함수이기 때문에 개발자가 어떠한 데이터 형을 저장하는지 예측할 수 없다.

예를들어 4바이트를 할당하였을 경우 int형 데이터를 저장하기 위해서 사용하는지, float형 데이터를 사용하는지 예측할 수 없기 때문에 void포인터를 반환하여 개발자가 알맞은 용도로 변환하여 사용할 수 있도록 만든것이다.

malloc 함수 사용 예시

int형 데이터를 저장하기 위해서는 리턴되는 void을 int로 변환하는 경우

#include <stdio.h>
#include <stdlib.h>

void main()
{
    int* arr;
    arr = (int*)malloc(sizeof(int) * 4); // size 4 동적할당

    arr[0] = 100;
    arr[1] = 200;
    arr[2] = 300;
    arr[3] = 400;

    for (int i = 0; i < 4; i++) {
        printf("arr[%d] : %d\n", i, arr[i]);
    }

    free(arr); //동적할당 해제
}

free 함수의 필요성

동적 메모리를 할당하면 힙 메모리에 공간이 생성되는데, 이 공간은 프로그램이 종료될 때까지 존재한다.
메모리를 할당만 하고 해제를 해주지 않으면 사용하지는 않는데 메모리 사용량만 계속해서 증가하게 되며, 이러한 현상을 메모리 누수라고 한다.
때문에 메모리 누수를 막기 위해 free 함수를 사용한다.

mmap과 malloc

mmap

메모리의 내용을 파일이나 디바이스에 대응(mapping)하기 위해서 사용하는 시스템 호출이다.

munmap

맵핑된 메모리를 해제하는데 사용한다. (mmap & munmap <--> malloc & free)

메모리관리와 mmap

가상 메모리 공간을 쓰는 이유는 프로세스간 (기본적으로) 메모리는 공유되지 않는 특성 때문이다.

보호를 위해 필요한 기능이지만 다른 프로세스와 특정 데이터를 공유하기 위해서는 불편한 기능이 된다.

mmap 은 메모리의 특정 영역을 파일로 대응시킬 수 있도록 도와준다. 파일은 시스템 전역적인 객체이므로 다른 프로세스에서 접근 가능하도록 할수 있으며, 이러한 mmap의 특징 때문에 IPC용도로 사용가능하다.

프로세스 간 통신(Inter-Process Communication, IPC)

• 프로세스들 사이에 서로 데이터를 주고받는 행위 또는 그에 대한 방법이나 경로

프로세스(process)

• 현재 실행 중인 프로그램(program)

malloc 과 mmap 의 차이

최소 할당 메모리 크기 차이

• malloc : 8byte
• mmap : 8KB, 4096byte

메모리 할당 장소

• malloc : heap
• mmap : Virtual Memory

System Call

• malloc : 파일 입출력 함수를 사용한다. (open() 함수를 써서 파일 디스크립터를 받고 파일 오프셋을 이동시킨 다음 read 함수를 호출해서 데이터를 버퍼로 읽어와서 작업한다.)
• mmap() : 메모리에 매핑 후 해당 mmap에서 반환하는 주소가 가리키는 메모리 영역의 데이터를 대상으로 작업하기 때문에 매번 read 함수로 읽어올 필요가 없다.

단편화

단편화(Fragmentation)는 기억 장치의 빈 공간 또는 자료가 여러 개의 조각으로 나뉘는 현상을 말한다. 단편화는 기억장치의 사용 가능한 공간을 줄이거나, 읽기와 쓰기의 수행속도를 늦추는 문제점을 야기한다.

내부 단편화

메모리를 할당할 때 프로세스가 필요한 양보다 더 큰 메모리가 할당되어,
프로세스에서 사용하는 메모리 공간이 낭비 되는 현상

외부 단편화

여유 공간이 여러 조각으로 나뉘는 현상

메모리가 할당 및 해제 작업의 반복으로 작은 메모리가 중간중간에 존재
총 메모리 공간은 충분하지만 실제로 할당할 수 없는 상황

단편화 문제 해결 방법

압축 (Compaction)

• 메모리에 존재하는 여러 흩어진 단편화 영역 혹은 빈 영역들을 한곳으로 모음

• 프로그램들의 재배치 필요

통합 (Coalescing)

• 인접한 단편화 영역 혹은 빈 영역들을 합침

• 프로그램 재배치 필요 X

페이징 (Paging) - 가상메모리사용, 외부 단편화 해결

가상 메모리(Virtual Memory)를 같은 크기의 블록으로 나눈 것을 페이지(Page)라고 한다.
주 기억장치(RAM)를 페이지와 같은 크기로 나눈 것을 프레임(Frame)이라고 한다.

페이징 기법이란 필요한 메모리를 페이지 단위로 프레임에 옮기고(swap-in), 사용하지 않는 프레임을 페이지에 옮기는(swap-out) 기법이다.

페이지와 프레임을 대응시키는 과정 중 paging table 을 만들어 이용한다.

연속적이지 않은 공간도 활용할 수 있기 때문에 외부 단편화 문제를 해결할 수 있다.
하지만 페이지 단위에 정확히 맞춰 할당하는 것이 아니므로 내부 단편화 문제는 여전히 있다.

페이지 단위를 작게하면 내부 단편화 문제도 해결할 수 있지만, page mapping 과정이 많아지므로 효율이 떨어질 수 있다.

세그멘테이션 (Segmentation) - 가상메모리사용, 내부 단편화 해결

가상메모리를 서로 크기가 다른 논리적 단위인 세그먼트로 분할한 후 메모리를 할당하여 실제 메모리 주소로 변환을 하게 된다.

세그먼트들의 크기가 다르기 때문에 미리 분할해 둘 수 없고 메모리에 적재될 때 빈 공간을 찾아 할당하는 기법이다.

mapping을 위해 세그먼트 테이블이 필요하다.
(세그먼트 테이블 항목 : 각 세그먼트 항목별 세그먼트 시작주소, 세그먼트의 길이 정보)

s 는 세그먼트의 번호를 의미하며 세그먼트 테이블에 대한 색인으로 사용된다. d 는 변위(offset)를 의미한다. 그림을 보면 d 는 논리 주소와 물리 주소가 동일하다. (왼쪽이 논리 주소, 오른쪽이 물리 주소)

• 논리주소는 v = (s,d) 로 표현된다.
• 논리주소 (2, 100) -> 물리주소 4400번지
• 논리주소 (1, 500) -> 인터럽트로 인해 프로세스 강제 종료(범위를 벗어남)
• 물리주소 a 는 base[s] + d 로 계산된다.

프로세스가 필요한 메모리 만큼 할당해주기 때문에 내부단편화는 일어나지 않으나,
중간에 프로세스가 메모리를 해제하면 생기는 외부 단편화 문제는 여전히 존재한다.

메모리 풀 (Memory Pool)

필요한 메모리 공간을 필요한 크기, 개수 만큼 사용자가 직접 지정하여 미리 할당받아 놓고 필요할 때마다 사용하고 반납하는 기법

필요한 크기만큼 할당을 해놓기 때문에 내부 단편화가 생기지 않는다.

메모리의 할당, 해제가 잦은 경우에 메모리 풀을 쓰면 효과적이다.

미리 할당해놓고 사용하지 않는 순간에도 계속 할당해놓으므로 메모리 누수가 있는 방식이다.

추가 설명

제목

내용

할당기 요구사항과 목표

명시적(explicit) 할당기 : malloc(), free()

• 개발자가 직접 free, delete 해줘야함
• C: malloc-free

묵시적(implicit) 할당기 : garbage collector(Java, List, ML 등 하위수준 언어)

• 개발자가 free할 필요X
• high level language :Java, C++

요구사항

할당된 블록만 Free시킬 수 있다.
요청에 즉시 응답하기 : 효율성을 위해 먼저 들어온 free/malloc요청을 미루고 다른 명령을 받을 수 없다.
힙만 사용하기 : Stack 및 다른 타입의 가상메모리에 저장할 수 없다. 프로그램 실행 중에 확장 가능한 것은 heap 뿐이기 때문이다.
메모리주소는 32bit 모드 기준 8의 배수이고, 64bit 모드 기준 16의 배수이다.
할당된 블록을 수정하지 않기. 일단 한 번 할당된 데이터를 메모리관리의 효율성을 위해 자리를 이동시키지 않는다.
=> 왜 이동시키지 않을까?

목표

처리량 극대화 : 시간효율을 높인다.
최대이용도 : 메모리 이용도를 최대화 (처리량과 이용도사이의 균형)

고려사항

가용 블럭 구성 : 어떻게 가용 블록을 지속적으로 추적하는가?
배치 : 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
분할 : 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?
연결 : 방금 반환된 블록으로 무엇을 할 것인가?

9.9.5 구현 이슈
9.9.6 묵시적 가용 리스트
9.9.7 할당한 블록의 배치

메모리 배치 알고리즘

First - fit : 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 free 블록을 택한다. 리스트의 앞에 작은 블록이 남고 뒤에 큰 블록이 남는다.(큰 블록을 찾는 경우에 검색시간이 늘어남)

Next - fit : 이전 검색이 종료된 시점부터 검색을 재시작한다. first fit에 비해 검색 시간이 빠르지만 메모리 이용도가 나쁘다.

Best - fit : 할당 가능한 모든 free블록 중 크기가 가장 작은 블록을 택한다. 메모리 이용도는 first, next fit에 비해 좋지만, implicit free list를 이용할 경우엔 힙 전체를 검색해야하기 때문에 검색 시간이 늘어난다.

worst - fit : 남은 메모리 중 가장 큰 메모리에 할당한다.

9.9.8 가용 블럭의 분할
9.9.9 추가적인 힙 메모리 획득하기
9.9.10 가용 블록 연결하기
9.9.11 경계 태그로 연결하기
9.9.12 종합설계 : 할당기 구현