Malloc

Malloc 함수 구현하기

• 동적 메모리 할당 방법을 직접 개발 하며, 메모리, 포인터 개념을 정확히 알고 사용하기.
  • malloc, realloc, free 함수 구현.
• implicit 방법으로 구현하기 (explicit, seglist, buddy system 방법도 여유되면 구현 해보기)

키워드

• 시스템 콜 (System Call)

  더보기
  System Call이란, 응용프로그램이 운영체제의 커널이 제공하는 서비스를 사용할 수 있게하는 방법이다. 예를 들어, 응용프로그램이 파일 시스템을 직접적으로 접근하는게 불가능하다. 그래서 응용프로그램은 커널에 접근하여 파일 시스템을 호출하는 방법을 사용한다.

• 데이터 세그먼트 (Data Segment)

  더보기

  

• 메모리 단편화 (Memory Fragmentation)

  더보기

  메모리 단편화

  • RAM에서 메모리의 공간이 작은 조각으로 나뉘어져 사용가능한 메모리가 충분히 존재하지만 할당(사용)이 불가능한 상태를 보고 메모리 단편화가 발생했다고 한다.

  • 메모리 단편화는 내부 단편화와 외부 단편화로 구분 가능하다.

    내부 단편화(Internal Fragmentation)

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

  • 예를 들어 메모장을 켰는데 OS가 4kb를 할당해줬다. 그런데 사실상 1kb만큼만 사용하고 있을 때 필요 이상으로 프로세스가 메모리를 할당받았으므로 내부 단편화가 3kb만큼 생긴 것임.

    외부 단편화(External Fragmentation)

    메모리가 할당되고 해제되는 작업이 반복될 때 작은 메모리가 중간중간 존재하게 된다. 이 때 중간중간에 생긴 사용하지 않는 메모리가 많이 존재해서 총 메모리 공간은 충분하지만 실제로 할당할 수 없는 상황

  • 예를 들어 메모리 처음 주소에 8mb짜리 프로세스가 할당되었고 바로 이어서 16mb짜리 프로세스가 할당되었다고 가정했을 때 8mb짜리 프로세스를 종료시키면 메모리 처음 주소부터 8mb만큼 공간이 생긴다

    ※ 출처: https://jeong-pro.tistory.com/91 [기본기를 쌓는 정아마추어 코딩블로그]

• sbrk(brk)/mmap(munmap)

  더보기
  sbrk, mmap

  동적 메모리 할당기 → malloc은 mmap과 munmap 함수를 사용해 힙 메모리를 할당하거나 반환 또는 sbrk 함수를 사용

  sbrk(), brk(): 메모리 할당시 호출 되는 시스템 콜, 데이터 세그멘트 크기를 변경, program break의 위치를 변경

  *program break

  프로세스의 데이터 세그먼트의 끝을 규정

  초기화되지않은 데이트 세그먼트 영역 후의 첫부분의 위치

  program break를 증가시키는 것은 프로세스에 메모리를 할당하는 효과를 가져옴. program break를 감소시키면 메모리 할당이 해제

  brk(): 시스템에 메모리가 충분할때 데이터 세그먼트의 끝을 brk의 인자인 addr에서 지정한 값으로 설정(program break 설정)

  sbrk(): 프로그램의 데이터 영역(data segment) - 힙 을 increment bytes 만큼 증가시킨다. increment 인자를 0으로 설정하여 sbrk()를 호출하는 것은 현재 program break의 위치를 찾을 때 씀(program break 증가)

  mmap(): 파일 디스크립터가 가리키는 객체를 파일에서 offset 바이트 지점을 기준으로 len 바이트 만큼 메모리에 맵핑하도록 커널에 요청 (커널에 새 가상 메모리 영역을 생성해줄 것을 요청하는 함수)

  munmap(): 메모리 맵을 사용하고 자원을 해제 할 때 사용, mmap()으로 만들어진 맵핑을 제거하기 위한 시스템 호출

  *파일 디스크립터(File Descripter -FD)

  유닉스 계열의 시스템에서 프로세스가 파일을 다룰 때 사용하는 개념, 프로세스에서 특정 파일에 접근할 때 사용하는 추상적인 값

  참조:https://aidencom.tistory.com/208

• 가상 메모리 (Virtual Memory)

  ※ 가상 메모리 출처: https://beeehappy.tistory.com/53

메모리 동적 할당의 필요성

정적 메모리는 코드대로 컴파일러에 의해 마련해둔 메모리 공간이다.

ex) int array[100]을 선언하면, 컴퓨터는 100 integer 공간을 마련해둔다. 그래서 array[사용자 입력 변수]로 해놓으면 컴파일러는 array의 크기를 모르기 때문에 변수 선언을 할 수 없다.

(※ 실제로 컴파일 가능, C99부터 가변 길이 지원.)

그러면 동적 메모리를 사용하는 주된 이유는 무엇일까? 아마도 런타임에 변수 공간을 할당하고 메모리 공간을 반환하는 장점 때문일것이다. 한정된 메모리로 프로그램을 운영하는 입장에선 쓸모없이 남아있는 전역변수들이 고깝게 느껴질 것이다. 이쯤이면 동적 메모리를 사용해야하는 충분한 이유가 된다.

동적 메모리 활용

프로세스가 메모리에 load되면 메모리 영역은 Code(text), data, stack, heap 영역으로 나눠진다. 동적 메모리는 가상메모리 영역 힙(heap)이라는 영역에 저장된다. 힙이라는 영역은 maximum size에서 사용자가 원하는 size만큼 할당받아서 사용할 수 있다. 하지만, 할당받을 수 있는 size를 넘겨버리면 process가 사용할 수 있는 free영역은 더이상 사용할 수 없다. 그래서 필요없는 부분에 대해선 시간이 날때마다 해제시키거나 해줘야한다. 보통 이걸 자동으로 해주는게 garbage collection인데, C에는 그런 기능이 없다고 한다. 수동으로 해제시키는 방법을 취해야한다.

application이 생성되고 나서부터는 프로그램을 자체적으로 heap 영역이 얼마나 필요한지는 모른다. 따라서 각 application마다 사용자 입력을 받아서 heap 영역을 지정해주는게 동적 메모리 할당기 (Dynamic memory allocation)이고, 보통 malloc (in C)을 사용한다. 할당기는 heap영역을 관리하는데, 이 때 관리하는 개념이 allocated/free이다.

보통 Allocator 종류는 Explicit과 Implicit을 나누는데 Explicit의 경우에는 필요없는 경우에는 수동으로 해제를 해줘야하는 것이다. 반대로 자동으로 해주는 것을 implicit은 이런 free함수와 같은 동작을 자동으로 해주기때문에 프로그래머가 덜 신경써도 된다는 장점이 있다고 한다.

• malloc(sizeof(int) * 5): 할당된 공간이 모두 기존 값
• calloc(5, sizeof(int)): 할당된 공간을 모두 0으로 바꾼다.
• realloc(array, sizeof(int) * 10): array의 메모리를 40바이트로 재할당
• free(*p): 포인터에 있는 메모리 해제

구현 이슈 (implicit 방식)

• 가용 블록 구성: How 가용 블록을 지속적으로 추적하는가? => 헤더에 블록 크기/가용 상태 인코딩

• 배치: 가용 블록을 어떻게 선택하는가? => 헤더의 가용상태 확인. 검색 알고리즘 (First fit, Next fit, Best fit).

• 분할: 가용 블록을 원하는 사이즈 블록을 만든 후, 나머지 블록은 어떻게 할 것인가? => 새로운 가용블록으로 만듬

• 연결: 방금 반환된 블록은 무엇을 할 것인가? => 세그먼트된 가용블록들을 연결해준다.

  

이 외 방법

• Implicit 방법 (+first fit/next-fit): Header 정보로 가용상태 확인하여, 모든 가용/비가용 블록을 탐색 -> 블록 수에 비례

  ■ First fit (코드 바로가기)

  가용 블록 탐색시 항상 처음 위치에서 시작하는 방식으로, 처리량(Thru) 점수가 낮게 나온거같다.
  내부 단편화와 외부 단편화가 많이 생길 수 있는 가능성이 있다.

  

• Explicit 방법: 비가용 블록을 이중연결 리스트 활용하여 연결하여 가용 블록만 탐색 -> 가용 블록 수에 비례

  ■ LIFO (Last Input First Output)

  탐색시 가용블록만 확인하기 때문에 속도는 가용 블록수에 비례

  ■ address order

• Seglist 방법: Explicit방식에서 추가적으로 블록의 크기 size별로 정렬을 해준다. -> explicit 보다 적은 시간

  ■ seglist (코드 바로가기)

  Free-list를 size class로 나눠 이중연결 리스트를 만들어 Best fit의 장점와 Explicit 장점가 있을 것 같다.