용어 정리 Paging = swapping 디스크(ex 하드 디스크)와 메모리(ex RAM) 사이에 페이지를 전송하는 동작

가상 메모리 물리적인 메모리 공간 보다 더 많은 메모리를 사용하기 위해 메모리를 확장하는 기법

data segment 프로그램의 runtime 때 쓰이는 global variable, static variable, 그리고 그 외의 데이터가 저장되는 영역

break point Data block의 힙의 꼭대기. 절대 initialised와 uninitialised 데이터를 구분하는 것이 아니다!!

brk() break point를 결정해줌

sbrk() data segment를 increment byte 만큼 늘리고, 성공하면 현재 break point의 위치(이전 brk의 값)를 반환함

시스템 요청 (system call) 운영체제(OS, 컴퓨터를 관리하는 시스템)에게 CPU와 독립적으로 특정한 기능(서비스)를 사용할 수 있도록 요청하는 행위

DMA (직접 메모리 접근) 하드웨어 시스템(하드디스크, 그래픽 카드 등)이 메모리에 직접 접근해서 데이터를 읽거나 쓸 수 있도록 해주는 기능

이더넷 LAN(Local Area Network)으로 정의된 로컬 환경에서(가정, 건물 등) 컴퓨터와 다른 장치들을 네트워크에 연결하기 위해 개발된 통신 표준; 여러 장치를 연결해서 해당 위치의 다른 사람들과 정보를 작성하고 저장하고 공유할 수 있다.

메모리 단편화 메모리 공간이 작은 조각 공간으로 나눠지면서 사용할 수 있는 메모리가 충분함에도 불구하고 메모리 할당이 불가능한 상태

implicit free list Free block이 명시적으로 표시되어있지 않고, 할당기가 heap의 특정한 기능을 이용해서 free block을 찾아야 하는 리스트

explicit free list Free block이 명시적으로 공개되어있는 리스트

segregated list Free block들이 크기별로 각각의 리스트로 나눠짐. 각 리스트가 정해진 크기를 가진 free block으로 구성됨.

first fit 가용 리스트를 처음부터 검색해서 크기에 맞는 첫 번째 가용 블록을 선택하는 방법

next fit 이전 검색에서 종료된 주소에서 부터 검색하는 방법

best fit 모든 가용 블록을 검사하면서 크기가 맞는 가장 작은 블록을 선택하는 방법

demand-zero memory 필요할 때 할당하고 0으로 초기화 해서 사용할 수 있는 메모리

20230511 어제까지 완성한 RB tree 코드를 github에 올리고 테스트도 돌리고 나서 malloc-lab 주제로 들어갔다. malloc은 동적으로 메모리를 할당하는데 쓰는 것인데, 메모리 공간을 필요한 만큼만 이용해서 코드의 효율성을 높이려는 것이 목적이다. 이걸 우리 방식으로 만드는 것이 과제다. 어차피 컴퓨터 시스템 교제에 예제 코드가 나와있어서 따라서 입력하면 되지만, 관련 용어들을 먼저 익히는 것이 중요하여 오늘은 빨리 퇴근하더라도 몇 가지 용어만 찾았다. 카이스트 정글 수강생 한 분이 이에 관해 정리해놓은 블로그가 있지만, 아직은 그냥 봐서는 뭐가 뭔지 전혀 모르겠다..

20230512 어제에 이어서 이번주차의 용어 공부를 마저 하고, 코드 분석도 조금씩 시작했다. 용어의 정의를 공부하는데도, 그 정의 내에서 뜻을 잘 모르는 단어들도 섞여있고, 코드 내에서도 난생 처음 보는 것들도 있어 정말 당황스러웠다. 정의를 찾다가 결국 깊게 파고들어가야 했는데, 정말 피곤하다. RB 트리는 그래도 누가 만들어놓은 자료구조를 구축하는것이라 “비교적” 쉬웠지만, 이번 malloc-lab은 malloc 함수의 구성요소를 깊게 파고들어가는 듯 하는 느낌이 들고, 생소한 용어가 많아 더 힘들다.

20230513 어제에 이어 용어 정리를 마저 하고 본격적으로 코드 분석에 들어가기로 했다. 완성 코드를 정리해놓은 블로그들이 있는데, 서로 다른 방식을 적용했기 때문에 서로 다르다. 어떻게 하느냐에 따라 점수가 달라지기 때문이다. 예를들어 implicit free list 혹은 explicit free list를 사용했는지, 아니면 first fit이나 next fit을 이용했는지에 따라서 말이다. 그래서 지금은 교제를 먼저 읽고 전체적인 흐름을 따라가기로 했다. 아무것도 모르고 그냥 따라치기만 하면 배우는 것이 없기 때문이다. 구현하는것이 중요하다고 해도 그냥 생각없이 하기만 하면 아무 의미 없다. Malloc을 할 때 heap을 쓰는 이유는 이렇다. 리스트를 만드려는데, 크기를 정하기가 곤란할 때 되게 유용한 리스트인데, heap은 비연속적으로 쌓여있는 데이터 블록의 더미이기 때문에 heap에서 가져다가 할당하기 더 쉽기 때문이다. 다만 데이터들은 linked list로 구성되어있는데, 단순히 아무 데이터 블록이나 무작위로 가져오는 것보다 원하는 블록을 찾아서 할당하는 것이 더 유용하기 때문이다. 그리고 나중에도 데이터를 할당할 수 있도록 그 heap에 다시 돌려주는 것이다. 이것을 free() 함수로 구현한다. 참고로 stack을 쓰지 않는 이유는 이건 연속적으로 쌓인 더미이기 때문에 마음대로 꺼내서 쓰기 쉽지 않기 때문이다. Heap에서 데이터를 요청하는 과정은 이렇다. 사용 가능한 데이터 블록들이 free list에 저장된다. Free list에 저장된 데이터 중 특정한 조건을 만족시키는 데이터만이 할당되어 리스트를 형성한다. 이 할당된 데이터 중 사용 완료된 데이터는 free list로 돌아간다. 모든 데이터가 사용 완려되어 모두 free list로 반환되면 다시 heap으로 반환된다.

20230515 어제까지는 푹 쉬다가 오늘 본격적으로 코드를 돌려보기로 했다. 우선 implicit free list로 시작해서 first-fit 방식으로 해보다가 코드를 수정해서 next-fit과 best-fit을 시도해보고, explicit free list와 segregated list를 이용해보면 된다. 교제에 나온대로 코드를 짜고나서 make 파일을 생성하고 돌려보니 53점이 나왔다. Next-fit 방식으로 하면 83점이 나온다. Explicit free list를 사용하면 87점이 나온다. 일단 이렇게 구현은 다 했다. 이제부터 목요일까지 남은 시간동안 알고리즘 공부하고, malloc-lab 코드 이해하는데 보내면 될 듯 하다.

20230516 Segregated list도 시도해보라 하여 예제를 찾아 테스트해봤더니 85점이 나왔다. 일단 이렇게 구현되는 것은 다 봐서 코드를 분석하기로 했지만, 생각보다 잘 되지 않았다. 하지만 막판에 조원들과 다같이 블로그 글을 천천히 읽으면서 서로 의논하다보니 머리에 좀 더 잘 들어왔다. 이번 주의 조는 생각보다 팀워크가 잦지 않은 듯 해서 우려가 있었는데, 이렇게 나중에라도 해서 다행이다. 하지만 그렇다고 나중에 혼자서 이 malloc-lab을 구현할 수 있지는 못할 것이다. 지난주 차의 red black tree도 구현할 수 없으니 말이다. Red black tree든 malloc-lab이든 다 복잡한 코드다. 이것들을 구현한 사람은 정말 천재 아닌가 라는 생각이 든다. 물론 그 분들도 시간이 굉장히 많이 들었을 것이다.

20230517 아침에 알고리즘 문제를 몇개 풀어봤는데, 드디어 스스로 풀린 문제가 있어서 기분이 좋았다. 계속 동적 프로그래밍 위주로 풀다가 잘 안되어서 막막했는데, 구현 문제를 풀다보니 내가 생각한 알고리즘이 통해서 좋았다. 하지만 다른 어려워했던 알고리즘도 결국은 익숙해져야 할 것이다. 나머지 시간은 malloc-lab 코드 이해에 집중했다. 점수를 90점 이상 목표로 하는 사람들도 있던데, 나는 아직 딱히 그럴 생각은 들지 않고, 우선 흐름 이해가 중요하다고 느낀다.