[정글] WEEK 06 | 그니까 Malloc Lab이 뭔데

어제까지만 해도 있는 거 가져다 쓰던 malloc을 이제는 직접 만들어 써야 한다?!

 

WEEK 06 키워드
시스템 콜, 데이터 세그먼트, 메모리 단편화, sbrk/mmap

🚘 하나씩 차근차근 알아가보자

시스템 콜
C언어의 파일 입출력에는 System Call과 Library Function이 있음

System Call

• 커널에 직접 서비스를 요청하는 것
• 커널 (Kernel) - OS의 한 부분, 하드웨어와 응용 프로그램 사이를 연결하는 인터페이스
• 시스템에 직접 접근하기 때문에 Low Level까지 제어할 수 있지만, 커널에 직접 접근하는 만큼 남용하면 성능 손실이 일어남
• 대표적인 시스템 콜 함수 - open, read, write
• open은 File descriptor을 반환함

Library Call

• 라이브러리 함수는 시스템 콜 함수를 감싼 것
• 함수 내부에서 메모리 할당과 해제가 있어나기 때문에 입력을 모았다가 한번에 커널에 요청하기도 함
• 즉, 잦은 함수 호출 상황에는 시스템 함수보다 빠름
• 대표적인 라이브러리 함수 - fopen, fscanf, fprintf
• fopen은 File pointer를 반환함

데이터 세그먼트
모든 변수는 데이터 세그먼트 (Data segment) 라고 불리는 영역에 저장됨

1) 코드 (code) 영역

• 실행할 프로그램의 코드가 저장되는 영역, 텍스트 영역이라고도 불림
• CPU는 코드 영역에 저장된 명령어를 하나씩 처리함

2) 데이터 (data) 영역

• 프로그램의 전역 변수와 정적 변수가 저장되는 영역
• 프로그램의 시작과 함께 할당되며 프로그램 종료 시 소멸됨

3) 스택 (stack) 영역

• 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역
• 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임 (stack frame) 이라고 함

4) 힙 (heap) 영역

• 사용자에 의해 메모리 공간이 동적으로 할당되고 해제됨
• 메모리의 낮은 주소에서 높은 주소의 방향으로 할당됨

🚨 메모리 단편화 발생

메모리 단편화 (Memory Fragmentation)
RAM에서 메모리 공간이 작은 조각으로 나뉘어져 있어, 사용 가능한 메모리가 있지만 할당이 불가능한 상태

1) 내부 단편화 (Internal Fragmentation)
프로세스가 필요로 하는 양보다 더 큰 메모리가 할당되어서 프로세스에서 사용하는 메모리 공간이 낭비되는 상황

 

2) 외부 단편화 (External Fragmentation)
중간 중간에 생긴 작은 크기의 사용하지 않는 메모리가 존재하게 되어, 총 메모리 공간은 충분하지만 실제로 할당할 수 없는 상황

 

⏳ 문제를 해결해보자

Word	Discription
페이지	가상 메모리에서 사용되는 메모리 영역을 일정한 크기로 나눈 블록
프레임	물리 메모리에서 사용되는 메모리 영역을 일정한 크기로 나눈 블록
세그먼트	프로그램을 논리적인 크기로 나눈 단위
Program Break	프로세스의 데이터 세그먼트의 끝을 규정
File Discripter	유닉스에서 프로세스가 파일이나 입출력 리소스에 접근하는 데 사용하는 개념

 

페이징 (Paging) 기법

• 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 주기억장치의 영역에 적재시켜 실행
• 연속적이지 않은 공간도 활용할 수 있기 때문에 외부 단편화 발생 X, 내부 단편화 발생 가능
• 페이지와 프레임을 대응시킬 page mapping 과정이 필요하여 paging table을 만듦
• 페이징 테이블 사용으로 인해 비용이 증가하고, 처리 속도가 감소됨
• 따라서 페이지 단위를 작게 하면 page mapping 과정이 많아지므로 오히려 효율 떨어짐

세그먼테이션 (Segmentation) 기법

• 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행
• 가상 메모리를 서로 크기가 다른 논리적 단위인 세그먼트로 분할하여 메모리를 할당함
• 각 세그먼트는 연속적인 공간에 저장되어 있음
• 주소 변환을 위한 mapping이 필요하여 segment table을 만들어 세그먼트 위치 정보 저장
• 프로세스가 필요한 만큼 할당해주기 때문에 내부 단편화 X, 하지만 메모리 해제시 외부 단편화 문제 발생

메모리 풀 (Memory Pool)

• 필요한 메모리 공간을 필요한 크기, 개수만큼 직접 지정하여 할당 받고 반납하는 방법
• 실제로는 알고리즘에 의한 할당과 해제가 반복되는데 이는 미리 공간을 할당해놓고 사용하기 때문에 외부 단편화 발생하지 않음
• 또한 필요한 크기만큼 할당하기 때문에 내부 단편화 발생하지 않음
• 메모리의 할당과 해제가 잦은 경우 적절한 방법
• 하지만 미리 할당해놓기 때문에 사용하지 않는 순간에는 메모리 누수가 발생함

sbrk/mmap

• 동적 메모리 할당 시 malloc을 사용하는데 내부에서는 실제로 메모리를 할당 받기 위해 brk와 mmap 시스템 콜을 사용함
• Program Break를 증가시킨다는 것은 프로세스에 메모리를 할당한다는 것, 감소시킨다는 것은 메모리 할당을 해제한다는 것

System Call	Desscription
brk()	데이터 세그먼트의 끝을 파라미터 값으로 설정함
sbrk()	데이터 영역을 파라미터 값만큼 증가시킴 파라미터가 0이라면 현재 위치를 찾는 것이라고 보면 됨
mmap()	FD가 가리키는 객체를 파일에서 파라미터 값만큼 메모리에 맵핑하도록 커널에 요청함
munmap()	mmap로 인해 만들어진 맵핑과 자원을 해제할 때 사용함

 

🛴 Malloc Lab

동적 메모리 할당이 필요한 이유

• 동적 메모리 할당으로 자료구조의 크기를 모르는 상황에서도 필요한 만큼의 메모리만 할당할 수 있음
  
• 즉, 메모리 낭비가 없고 관리도 쉬움

 

동작 원리를 알아야 하는 이유

• 프로그래머가 동적 메모리 할당 기능을 효율적으로 사용하기 위해, 어떻게 동작하는지 이해할 필요가 있음

 

Heap 영역

• 힙 영역: 동적으로 할당된 메모리를 관리함
• 힙은 낮은 위로 자람 (낮은 메모리 주소 → 높은 메모리 주소)
• 스택의 top 주소 값이 감소했다는 건, 스택에 새로운 값이 추가되었다는 의미
• malloc, free 동적할당 함수: 힙 영역에 메모리 공간을 할당 및 해제

  

 

블록 검사 방법

1) Implicit

• 순차적으로 모든 블록을 검사하는 선형적 방법
• 처음부터 차례대로 검사하는 first-fit 방식보다 next-fit 방식을 사용하면 성능이 매우 향상됨

 

2) Implicit + next-fit 구현

• 이전 검색(가용 검색이든, 할당이든)이 종료된 지점부터 검색 시작
• 즉, bp가 갱신되는 모든 부분에 last_bp도 갱신 해주면 됨
• 프로그램 상에 return bp 전에 last_bp = bp 코드를 넣어준다 생각하면 됨
• find_fit (검색 함수)에서는 last_bp 지점부터 검색, 없으면 처음부터 last_bp 범위 검색
  
  • last_bp ~ 에필로그
  • heap_listp ~ last_bp

 

3) Explicit

• 할당 해제된 블록들을 연결 리스트로 관리, 이 연결 리스트만 검사
• Implict에서 개선된 방법, Implicit의 next-fit과 유사함

 

4) Seglist

• 할당 해제된 블록들을 사이즈별로 모아 여러 개의 연결 리스트로 관리
• 이 연결 리스트들의 포인터들만 힙에 저장하여 관리함
• Explicit에서 개선된 방법으로, 빠른 속도로 찾을 수 있어 가장 성능이 좋음

• 삽입/삭제
  
  • 분리 가용 리스트의 가운데로
  • 분리 가용 리스트의 맨 처음으로
  • 분리 가용 리스트의 맨 마지막으로
  • 분리 가용 리스트에 원소가 없을 때

 

가용 리스트
1) 묵시적 가용 리스트

• 힙을 연속된 할당 및 가용 블록의 배열로 구성한 것
• 장점 : 단순함
• 단점 : 탐색에 필요한 연산 비용이 힙에 있는 전체 블록 수와 가용 블록 수에 비례함

 

2) 명시적 가용 리스트

• 가용 블록들을 일종의 명시적 자료구조로 구성한 것
• 단점 : 일반적으로 가용 블록들이 충분히 크기 때문에 포인터, 헤더, 푸터까지 포함하고 있어야 함

 

3) 분리 가용 리스트

• 분리 저장장치는 다수의 가용 리스트를 유지하며 각 리스트는 거의 동일한 크기의 블록을 저장
• 장점 : 할당과 반환의 시간이 빠름, 블록당 오버헤드 없음
• 단점 : 내부/외부 단편화에 취약

프로젝트 바로가기