전체 글 74

[week06] Malloc Lab 6주차 회고

📷 회고 정글에 들어오고 처음으로 현타가 좀 왔다. 할당기를 구현하는데 내가 직접 코드를 짠 것도 아니고(도저히 짤 수 없을 정도로 어려웠다) 심지어 코드를 보고 이해하는것도 어려웠다. 따라친 코드가 잘 돌아가지 않으면 눈이 빠져라 틀린그림 찾기를 하는 느낌으로 오타를 고치면서 내가 지금 맞는 방향으로 가고 있는건지 확신할 수가 없었다. 알고리즘 주차에서는 내가 맞고 틀린것을 명확하게 볼 수 있으니까 피드백이 빨리 오는데, 이건 그런게 없기 때문에 과연 잘 가고 있는 것인가 의구심이 들었다. 주차가 다 끝나고 동기들과 이야기 해본 결과 우리가 지금 매우 빠르게 개발자가 되어야 해서 기본적인 것들을 많이 건너뛰면서 가고 있어. 마치 걸음마도 못하는 아가한테 뛰라고 하는 느낌이 들지않아?? 그래도 한 주가 ..

[week06] 명시적 할당기 구현 - segregated free list 방식

segregated free list의 구조와 방식 일단 겁먹지 말자. segregated free list는 explict free list에서 사용한 pred, succ의 로직을 그대로 사용한다. 앞서 살펴본 두 개의 방식(implicit free list, explicit free list)을 사용하는 할당기는 한 개의 블록을 할당할 때 free block의 수에 비례하는 시간이 필요하다. 이걸 획기적으로 줄이는 방법이 segregated free list방식이다. 어떻게 시간을 줄이냐? 다수의 가용 리스트를 유지해서 각 리스트에 비슷한 크기의 블록들을 저장하는 방식을 취한다. 할당기는 free list의 배열을 관리하고(위 그림에서 segregated list) 크기 클래스마다 크기가 증가하는 오..

[week06] 명시적 할당기 구현 - explicit free list 방식

명시적 가용 리스트(Explicit Free lists)의 구조 저번 시간에 살펴보았듯이 묵시적 가용 리스트는 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 범용 할당기로는 적합하지 않다. 더 좋은 방법은 가용 블록들을 일종의 명시적(Explicit) 자료구조로 구성하는 것이다. 명시적 가용 리스트가 묵시적 가용 리스트와 가장 큰 차이점은 가용 블록만을 위한 리스트를 연결시킨다는 점이다. 묵시적 가용 리스트에서는 allocated block과 free block이 모두 연결되어 있어서 free block을 찾을 때 시간이 오래걸렸던 것을 기억해내자. allocated block은 안에 payload가 들어 있기 때문에 할당기가 건드려서도 안되고, 건드릴 수도 없지만 free block들은 안이 비어있..

[week06] 명시적 할당기 구현 - implicit free list 방식

묵시적 가용 리스트(implicit free list) 방식 묵시적 가용 리스트(implicit free list)의 장점은 단순성이다. 그러나 아주 큰 단점을 가지고 있는데, 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록수에 비례한다는 단점이다. 따라서 실제로는 사용되지 않는다. 그러나 할당기에 꼭 필요한 개념들을 가지고 있고, explicit free list, segregated list를 이용하는 발전된 방식들의 뿌리가 implicit free list를 이용하는 방법이므로 처음 할당기를 구현해 본다면 implicit 방식을 구현해 보는것을 추천한다고 한다.(카네기 멜런 대학교 교수님왈) 묵시적 가용 리스트 구조 묵시적 가용 리스트는 다음과 같은 구조들이 연..

[week06] 동적 메모리 할당

메모리 구조 메모리의 구조는 다음과 같다. 동적 메모리 할당을 할 때 heap영역을 사용할 것인데 일단 stack 메모리와 heap 메모리의 차이를 살펴보고 왜 heap 영역을 사용하는지 이해해 보자. stack메모리 vs heap메모리 스택 메모리 스택 메모리는 우리가 배워왔던 자료구조와 마찬가지로 프레임 단위로 쌓여간다. 컴퓨터는 변수를 찾기 위해 top 위치에서 n번째 메모리공간에 엑세스를 진행한다. stack의 큰 특징은 메모리가 쌓일 때는 올리기만 하면 되고, 해제시킬 때는 맨 위를 없애주면 되기 때문에 매우 간단한 data structure를 가지고 있다. 힙 메모리 heap의 영단어 뜻은 '더미'이다. 스택처럼 쌓여가는 느낌이 아니라 순서가 없이 더미로 존재한다는 뜻이다. 참고로, 자료구조 ..

[week06] 가상 메모리란? Virtual Memory

가상 메모리(Virtual Memory) 우리는 main memory(RAM)를 가지고 있다. 그런데 main memory의 크기가 작아서 모든 정보를 담기에는 부족한 경우가 있다. 이 때 하드디스크까지 main memory(RAM)를 확장해서 사용하는 것을 큰 틀에서의 Virtual Memory 기법 이라고 한다. 물리 주소와 가상 주소 물리주소는 main memory(RAM)에만 존재하는 것이다. 가상주소는 하드디스크까지 메모리를 확장했을 때 얻을 수 있는 값들을 이야기한다. 물리주소와 가상주소가 어떻게 동작하는지 살펴보자. 일단 main memory가 16KB 크기를 가진다고 가정하자. CPU가 가상메모리에서 어떤 주소를 할당해달라고 요청하면, MMU(memory management unit)가 요..

[week06] 헤더 파일을 사용하는 이유 feat(Private global, static)

malloc 과제를 진행하다가.. /* Private global variables */ static void *extend_heap(size_t words); 라는 주석과 코드를 만났는데, Private이 무슨 뜻인지 궁금해서 구글링 해봤더니 다음과 같은 설명을 찾을 수 있었다. 키워드: 접근 제한, 접근 제어 public: 내부, 외부 접근 모두 허용 private: 내부접근만 허용 그런데 global은 전역변수로서 모든 함수에서 접근가능하고, private은 내부접근만 허용하는데 그럼 이 두개의 의미가 충돌하는 것이 아닐까? 하는 생각이 들었다. 결론부터 말하자면 그렇지 않다! 왜냐하면 뜻하는 범위가 다르기 때문이다. 이것을 이해하기 위해서는 header file을 사용하는 이유에 대해서 알아야 한..