# malloc lab

16개의 포스트

[SW사관학교 정글] Week05. 탐험 준비 - Malloc Lab

👀 Week05 요약 이번 주는 카네기 멜론 대학교의 malloc-lab 과제를 통해 malloc, realloc, free 함수를 직접 구현해보았다. 개념 공부할 때까지만 해도 포인터가 왜 c에서 악명 높은 존재인지 모르겠다 생각했는데, 막상 실제로 구현을 해보니 그 이유를 알 수 있었다. 포인터 때문에 참 많은 Segmentation fault를 마주했었다 🥲 힘들기는 했지만 내가 직접 힙 영역을 확장하고 메모리를 할당, 해제해보면서 컴퓨터의 본질에 한 발짝 더 다가선 듯 해서 뿌듯한 한 주였다. 📝 관련 개발 일지 [[컴퓨터 시스템] 동적 메모리 할당 - Implicit Free List 개념](https://velog.io/@youngeui_hong/%EC%BB%B4%ED%93%A8%ED%84%B0-%EC%8B%9C%EC%8A%A4%ED%85%9C-%EB%8F%99%EC%A0%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%9

2023년 9월 14일
·
0개의 댓글
·
post-thumbnail

Malloc Lab: Explicit Free List를 구현하며 만났던 문제들

개념은 쉽고, 구현은 어려워 🎵 나만의 동적 메모리 할당기의 성능을 더더욱 높이기 위해, Explicit Free List를 이용한 구현에 대해 공부했다. Implicit Free List를 사용한 할당기는 간단하게 구현할 수 있지만 블록의 할당에 소모되는 시간이 힙의 모든 블록 수에 비례한다는 단점이 있었다. 반면에 Explicit Free List를 이용한다면, 블록의 할당에 소모되는 시간을 힙의 가용 블록 수로 줄일 수 있다. Explicit Free List의 개념은 생각보다 간단했다. 가용 가능한 블록의 내부에 다음 가용 블록의 주소를 가리키는 포인터 Next와 이전 가용 블록의 주소를 가리키는 포인터 Prev 를 포함하는 것! 이렇게 해주

2023년 5월 16일
·
0개의 댓글
·
post-thumbnail

Malloc Lab: first-fit 을 next-fit 로 바꾸며 만났던 문제들

더 높은 점수를 향해 🪜 Malloc Lab을 Implicit List로 구현한 후 받은 첫 점수는 53점! 더 높은 점수를 위해서는 만든 동적 메모리 할당기의 성능을 다양한 방법으로 끌어올려야 했다. Malloc Lab에서의 동적 메모리 할당기의 성능은 두 가지로 평가된다. Space Utilization과 Throughput. 영어 의미대로 공간을 얼마나 잘 활용하는가'와 '할당 속도가 얼마나 빠른가'로 평가한다. 내가 선택한 더 높은 점수를 위한 첫 단추는 first-fit을 next-fit으로 바꿔 Throughput`을 개선하는 것! 뭐야? 별거 아닌데? 😄 first-fit: 매 할당마다 처음부터 메모리를 쭉

2023년 5월 15일
·
0개의 댓글
·
post-thumbnail

[동적할당] Dynamic Memory Allocation

동적 할당과 malloc-lab 번역된 CS:APP는 난해한 부분들이 꽤 있었는데 운 좋게 영어로 된 책과 저자의 강의를 봐 이해에 도움이 많이 되었다. 말록랩에서는 여러가지 정책들(placement, splitting, coalescing 에 관련된)과 가용 블럭 정리방법들을 통해 명시적 할당기를 구현 해 볼 수 있었다. Why Dynamic Memory Allocation? We often do not know the sizes of certain data structures until the program actually runs. Hard coded bounds such as can become a maintenance nightmare for large software products with millions of lines of code and tons of users. A better approach is to allocate memory d

2023년 4월 9일
·
0개의 댓글
·
post-thumbnail

[Malloc-Lab] My Study - Implicit Free List

Organization implicit이라는 의미대로 list 안에서 free block의 관계가 암묵적으로 나타남. 일반적으로 block의 header와 footer에 block의 size와 allocated 여부가 담긴다. 이러한 데이터를 바탕으로 포인터를 이동시켜서 다음 block의 size와 allocated의 여부를 확인하는 방식으로 진행된다. 즉 모든 블록을 선형적으로 탐색하는 방식이다. Find fit First-fit heap을 맨 처음부터 뒤지기 시작해서 처음으로 요청받는 메모리보다 size가 더 큰 free block을 할당한다. 만약 heap의 앞에 size가 작은 block들만 남아있으면 탐색시간이 길여지므로 throughput가 떨어진다. 또한 처음으로 발견하는 `blo

2022년 11월 3일
·
0개의 댓글
·
post-thumbnail

[Malloc Lab] Overline

📌 목적 📍 해당 실습을 통해 직접 동적 메모리 할당기(storage allocator)를 구현한다. 📍 Malloc, Free, Realloc을 구현한다. 📍 mdriver가 memory ultilization(메모리 이용도), throughout(처리량) 측면에서 품질을 평가한다. 📌 왜 동적 메모리 할당기를 사용하는가? 프로그램들이 동적 메모리 할당을 사용하는 가장 중요한 이유는 종종 이들이 프로그램을 실제로 실행시키기 전에는 자료구조의 크기를 알 수 없는 경우들이 있기 때문이다. 최대 배열 크기를 가진 정적 배열로 만들면 해결 될 수 있겠지만 과도하게 메모리를 낭비하는 방법으로 그렇게 좋은 방법은 아니다. 또 배열을 정해진 크기를 발생할 경우 문제가 발생한다. ![](https://velog.velcdn.com/images/daelkdev/post/400cf8b7-5ea4-474f-9d97-a2f52146eb

2022년 11월 3일
·
0개의 댓글
·
post-thumbnail

week06. malloc lab (implicit list)

malloc lab 프로젝트는 실제로 C언어에서 동적 할당을 해주는 malloc 함수를 구현하는 것이 아닌 할당이 어떤 방식으로 이루어지는지 보기 위한 동적 할당 모형. 단편화 : 가용 메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 발생. 내부 단편화와 외부 단편화로 나뉨. 내부 단편화 : 할당된 블록이 데이터 자체보다 클 경우 발생. 이 경우는 얼마나 메모리가 낭비되고 있는지 할당기에 따라 예측이 가능하다. 외부 단편화 : 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일 가용 블록은 없는 경우 발생. 외부 단편화의 경우 이전 할당 상태 뿐만 아니라 이후에 들어올 요청에 따라 달라지기 때문에 예측할 수 없다. 단편화를 최소화하면서 가능한 많은 블록을 할당하는 방법을 연구. implicit list with next fit ![](https://images.vel

2021년 12월 31일
·
0개의 댓글
·
post-thumbnail

Malloc lab - 명시적 할당기 구현(C언어)

C언어, 32bit 기준으로 작성. 동적 메모리 할당을 사용하는 이유 프로그램을 실행시키기 전에 자료구조의 크기를 알 수 없는 경우들이 있기 때문이다. > 배열에 미리 넉넉하게 할당하여 쓰면 되지 않나? 수백만 라인의 코드와 수많은 사용자가 있는 큰 규모의 소프트웨어 제품에서는 관리하는데 어려움이 될 수 있다. 목표 1 : 처리량 극대화 ----------------- 처리 속도 2 : 메모리 이용도 최대화 ----------- 메모리 활용도 단편화(Fragmentation) ![](https://images.velog.io/images/stthunderl/post/0d60a35e-3e81-45c3-98ac-2ed260e2cd90/im

2021년 12월 14일
·
0개의 댓글
·
post-thumbnail

Malloc lab (1) 탐험준비

키워드 시스템 콜 데이터 세그먼트 메모리 단편화 sbrk/mmap explicit allocator(malloc) 구현범위 implicit list : first-fit, next-fit explicit free list : LIFO 평가 요소 Space Utilization The peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via mm malloc or mm realloc but not yet freed via mm free) and the size of the heap used by your allocator. The optimal ratio e

2021년 12월 14일
·
0개의 댓글
·

[WEEK 06] C - MALLOC LAB

할당기 기본 설계 memlib.c 패키지에서 제공되는 메모리 시스템의 모델을 사용 mem_init 함수는 힙에 가용한 가상메모리를 큰 더블 워드로 정렬된 바이트의 배열로 모델 memheap과 membrk 사이의 바이트들은 할당된 가상메모리 mem_brk 다음에 오는 바이트들은 미할당 가상메모리 할당기는 mem_sbrk 함수를 호출해서 추가적인 힙 메모리를 요청 mm_init 함수는 할당기를 초기화, 성공이면 0을 아니면 -1을 리턴 mmmalloc과 mmfree 함수는 이들에 대응되는 시스템 함수들과 동일한 인터페이스와 의미 할당기는 최소 블록 크기는 16바이트이며 가용 리스트는 묵시적 가용 리스트로 구성 첫번째 워드는 더블 워드 경계로 정렬된 미사용 패딩 워드 패딩 다음에는 헤더와 풋터로만 구성된 8바이트 할당 블록인 프롤로그 블록 프롤로그 블록은 초기화 과정

2021년 9월 11일
·
0개의 댓글
·

[회고록] Malloc Lab 프로젝트

Malloc Lab 프로젝트 Github 링크 21.01.15 ~ 21.01.21 C언어를 이용하여 malloc함수를 구현하는 프로젝트였습니다. 동적할당에 대해 이해할 수 있는 시간이었고, 가상메모리의 주소에 직접 접근하여 할당하는 경험을 할 수 있는 기회가 되었습니다. 어려웠던 점 동적할당이 잘 수행되었는지 확인하는 heap checker를 구현하는 도중 설계단계에서 생각하지 못한 엣지케이스를 발견하였습니다. free한 블록들을 연결 리스트 형태로 구현하고 가장 처음 포인터만을 변수로 저장해 놨었는데, 엣지케이스 때문에 가장 마지막 블록에 접근해야 하는 일이 발생하였습니다. 문제점을 해결하기 위해 연결리스트를 head와 tail을 만드는 방법으로 수정하였습니다. 이후 더 설계를 수정하여 마지막에 들어오는 블록을 가장 처음에 연결하는 방법으로

2021년 1월 24일
·
0개의 댓글
·

[C] 분리 가용 리스트를 이용한 동적 메모리 할당기 구현(MALLOC-LAB) (4)

마지막으로 분리 가용 리스트를 이용한 할당기를 만들어 보자. 분리 가용 리스트 분리 가용 리스트는 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장한다. 기본적인 아이디어는 모든 가능한 블록 크기를 크기 클래스라고 하는 동일 클래스의 집합들로 분리하는 것이다. 이때 크기 클래스를 정의하는 많은 방법들이 존재한다. 예를 들어 블록 크기를 2의 제곱으로 나눌 수 있다. 그럼 아래와 같은 리스트들이 만들어진다. 또는 크기가 작은 블록들은 자신의 크기 클래스에 할당하고, 큰 블록들은 2의 제곱으로 분리할 수 있다. 할당기는 가용 리스트의 배열을 관리하고, 크기 클래스마다 크기가 증가하는 순서로 한 개의 가용 리스트를 가진다. 할당기가 크기 n의 블록이 필요하면 적당한 가용 리스트를 검색한다. 이때 리스트 내부에 가용 가능한 블록이 없다면, 다음 리스트를 검색한다. 나머지는 명시적 가용 리스

2021년 1월 21일
·
0개의 댓글
·

[C] 명시적 가용 리스트를 이용한 동적 메모리 할당기 구현하기(MALLOC-LAB) (3)

이번에는 명시적 가용 리스트(explicit free list)를 이용한 할당기를 구현해 보자. 명시적 가용 리스트 명시적 가용 리스트는 가용 블록을 일종의 명시적 자료구조로 구성해 가용 리스트들을 모두 연결한다. 가용 블록의 header와 footer를 제외한 영역은 할당되어 데이터가 들어가기 전까지 사용하지 않는 영역이다. 그래서 가용 블록의 내부에 사용하지 않는 영역에 내 이전 가용 블록과 다음 가용 블록을 가리키는 포인터 두 개를 넣는다. 이 가용 블록 내부의 두 개의 포인터로 인해 가용 리스트는 이중 연결 가용리스트로 구성될 수 있다. 묵시적 가용 리스트 대신 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는

2021년 1월 20일
·
0개의 댓글
·

[C] 묵시적 가용 리스트를 이용한 동적 메모리 할당기 구현하기(MALLOC-LAB) (2)

관련 내용에 대해서는 저번 포스팅에서 설명했기에 이번 포스팅에서는 묵시적 가용 리스트를 이용해 구현한 동적 메모리 할당기 코드를 보도록 하겠다. 코드 코드 내부에 unistd.h 등의 헤더는 유닉스에서 사용할 수 있는 헤더로 따로 설정을 하지 않는 이상 window 환경에서는 돌아가지 않습니다. 1. mm_init mm_init 함수는 초기 힙 영역을 할당하는 것과 같은 필요한 초기화들을 수행한다. 가용리스트는 아래와 같은 변하지 않는 형태를 유지한다. 더블 워드 경계 정렬방식으로 인한 미사용 패딩 워드 뒤에 헤더와 풋터로만 구성된 8바이트 할당 블록인 프롤로그 블록이 온다. 그 뒤로 malloc 또는 free를 통해 호출된 일반 블록들이 오고 힙은 항상 에필로그 블록으로 끝난다. 프롤로그와 에필로그 블록은 연결과정 동안 가장자리 조건을 없애주기 위해 임의로 설정한 블록이다. ![](https://images.velo

2021년 1월 19일
·
0개의 댓글
·

[C] 동적 메모리 할당을 직접 구현해보자 (MALLOC-LAB) (1)

아래 내용은 컴퓨터 시스템(computer systems: a programmer's perspective)의 '9.9장 - 동적 메모리 할당'의 내용을 재구성 하였습니다. 1. 동적 메모리 할당기 동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당되었거나 가용한 가상메모리의 연속적인 묶음이다. 할당기에는 명시적 할당기, 묵시적 할당기 두 개의 기본 유형이 있다. 명시적 할당기는 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. C에서 malloc 함수를 호출해 블록을 할당하고, free 함수를 호출해 블록을 반환하는 것이 이에 해당한다. 묵시적 할당기는 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는 지를 할당기가 검출할 수 있을 것을 요구한다. 묵시적 할당기는 가비지 컬렉터라고 알려져 있으며, 자동으로 사용하지 않은 할당

2021년 1월 17일
·
0개의 댓글
·

210115 개발일지(39일차) - 컴퓨터 시스템 9.9장 Malloc Lab 프로젝트(1) : Malloc Lab 과제 설명, implicit방법과 explicit방법, 단편화

Malloc Lab 과제란?! >- http://csapp.cs.cmu.edu/3e/malloclab.pdf 출처: CMU (카네기멜론) 말록랩은 '동적 메모리 할당' 방법을 직접 개발하면서 메모리, 포인터 개념에 익숙해질 수 있는 과제다. 랩 코드를 직접 수정하고, 채점 프로그램을 실행하면서 '내 점수'를 알 수 있다. 즉, malloc()함수와 free()함수를 직접 만드는 것이라고 생각하면 된다. 먼저, implicit 방법으로 구현해 볼 예정인데 이는 컴퓨터시스템 9.9장에 나와 있다. 그 후 explicit 방법과 segreagted free 방법에 대해서 고민해볼 예정이다. 동적 메모리 할당의 필요성 가장 큰 이유는, 프로그램을 실행시키기 전에 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다. 미리 어떤 배열의 크기의 값을 정적으로 정의하고 시작해도 되나, 실

2021년 1월 15일
·
1개의 댓글
·