동적 메모리 할당 - 배치: first-fit, next-fit, best-fit

서론새롭게 할당된 블록을 배치하기 위한 가용 블록을 선택하는 방법에는 first-fit, next-fit, best-fit 등이 있습니다. GeeksforGeeks>☝🏻 first-fit: 처음부터 탐색하고 크기가 맞는 첫 가용 블록을 선택한다.static void *first_fit(size_t asize){ void *bp; for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { if (GET_SIZE(HDRP(bp)) >= asize && (!GET_ALLOC(HDRP(bp)))) { return bp; } } return NULL;}힙의 시작부터,..

• format_list_bulleted 운영체제
• · 2024. 7. 16.
• textsms

동적 메모리 할당: 명시적(explicit) 가용 리스트

서론동적 메모리 할당을 할 때 가용 리스트를 구성하는 방법에는 묵시적 가용 리스트(implicit), 명시적 가용 리스트(explicit), 분리 가용 리스트(segregated), 버디 시스템(buddy system) 등이 있습니다. 본문에서는 이 중 명시적 가용 리스트(explicit)를 사용한 동적 메모리 할당을 설명합니다.implicit에서 수정한 코드이기 때문에 수정되지 않은 코드는 설명을 적지 않습니다. 이전 게시글에 자세한 설명이 있습니다.explicit에서 블록의 구성implicit에서 사용한 블록과 달리 explicit에서는 가용 블록에 가용리스트의 다음 블록을 가리키는 Next와 이전 블록을 가리키는 Prev 포인터가 추가되어 있다.정의 & 선언#define GET_NEXT(bp) (*..

• format_list_bulleted 운영체제
• · 2024. 7. 16.
• textsms

동적 메모리 할당: 묵시적(implicit) 가용 리스트

서론동적 메모리 할당을 할 때 가용 리스트를 구성하는 방법에는 묵시적 가용 리스트(implicit), 명시적 가용 리스트(explicit), 분리 가용 리스트(segregated), 버디 시스템(buddy system) 등이 있습니다. 본문에서는 이 중 묵시적 가용 리스트(implicit)를 사용한 동적 메모리 할당을 설명합니다.implicit에서 블록의 구성블록엔 데이터(+패딩) 앞 뒤에 헤더와 푸터가 있다. 헤더와 푸터는 같은 값으로 안에는 블록의 크기(헤더와 푸터를 포함한)와 할당 정보가 들어있다.🤔 푸터(footer)는 왜 있어야 할까?푸터는 경계 태그(boundary tag)로 이전의 헤더 블록을 찾기 위해서 존재한다. 푸터가 없다면 헤더를 통해 할당 정보를 확인해야 하는데, 거꾸로 훑고 가면..

• format_list_bulleted 운영체제
• · 2024. 7. 16.
• textsms

동적 메모리 할당(Dynamic Allocation)이란?

서론C언어를 공부하다보면 malloc(), calloc(), realloc()이라는 함수를 사용하여 동적 메모리 할당을 합니다. 그럼 동적 메모리 할당은 무엇이며 어떻게 이루어지는 걸까요? '동적 메모리 할당'이란 프로그램 실행 중에 필요한 메모리를 힙(heap, 보통은)에 할당하는 것입니다.📝 그렇다면 힙이란 무엇인가?힙은 가상 주소 공간(virtual address space)에서 데이터 영역(data segment)과 코드 영역(code segment) 사이의 영역으로 동적으로 할당된 데이터를 저장하는 영역입니다.* 힙의 꼭대기를 brk ptr라고 합니다.🤔 그럼 동적 메모리 할당이 왜 필요한 것인가?가장 중요한 이유는 종종 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우..

• format_list_bulleted 운영체제
• · 2024. 7. 16.
• textsms

레드 블랙트리(The red black tree): 규칙, 회전, 삽입

루트 노드에서 leaf 노드로 가는 경로를 보았을 때 red black 트리는 한 경로가 다른 경로보다 2배 이상 길지 않다. 그래서 대체적으로 균형잡혀 있다.각각의 노드는 color, key, left, right, p 속성을 가지고 있다.red black 트리는 아래 규칙을 만족하는 이진 탐색 트리이다.규칙모든 노드는 색을 가진다. (red 또는 black)루트 노드는 black모든 leaf 노드는 NIL, blackred 노드는 red 자식 노드를 가질 수 없다.(2개의 black 자식을 가져야 한다.)각 노드에서 leaf 노드로 가는 경로들은 같은 수의 black 노드를 가지고 있어야 한다.회전Left-Rotate 왼쪽 회전y의 왼쪽 서브트리는 x의 오른쪽 서브 트리가 된다.(바꾼다라는 표현이 헷..

• format_list_bulleted 자료구조
• · 2024. 7. 15.
• textsms

[자료구조] C로 연결 리스트 Linked List 구현하기

서론포인터를 적용해보고자 연결 리스트를 구현해보았습니다. 구현하면서 흐릿했던 포인터의 개념이 약간은 명확해졌습니다. 코드는 사람마다 다르기 때문에 흐름만 이해하고 직접 구현해보는 것을 추천합니다. (포인터, 구조체, 동적할당 개념 필요)🔗 연결 리스트데이터를 순서대로 저장하는 자료구조 중 하나입니다. 연결 리스트는 각각의 노드가 데이터와 다음 노드의 주소를 가지고 있는 방식으로 구현됩니다. 연결 리스트는 배열과 달리, 데이터가 메모리 상에서 연속적으로 위치하지 않기 때문에 삽입, 삭제가 용이하고 데이터 크기를 동적으로 조절할 수 있습니다.삽입int insertion(nval) { struct node *newNodeptr = (struct node *)malloc(sizeof(struct node))..

• format_list_bulleted 자료구조
• · 2024. 7. 15.
• textsms