[Malloc_Lab] 명시적 가용 리스트를 이용한 동적 메모리 할당기 (1)

묵시적 가용리스트를 구현하고, 이번엔 명시적 가용 리스트 만들기를 시작했다.

하나하나 다 구현해보고 마지막에 좋은 생각이 있다면 구현을 해보는 것이 말록랩에서 뭔하는 것 같아서 이번엔 명시적인 가용 리스트로 오게 되었다. 구현하고 점수가 나오는게 재밌어서 하나하나 다 해보는 것 같다. 그럼 일단 레츠고...

일단 명시적 가용 리스트가 뭔지 알아보자.

명시적 가용 리스트가 뭔데 ?

사진을 보면 위에 있는 것이 묵시적 가용리스트이고, 아래 있는 것이 명시적 가용 리스트이다.

이전 묵시적을 사용하면, 뭔가 선형적으로 탐색해야해서 시간 복잡도가 높았는데, 이거는 가용 상태인 친구들만 하나하나 이어버려 주는 것이다 !

그럼 저건 알겠는데... 카네기 멜론 교수님은 구조체나 배열을 절대 쓰지 말라고 하셨다... 그래서 강의 자료를 계속 보고 있었는데...

진짜 겁나 똑똑한 아저씨들이 이런 생각을 해놨다.

만약 블록이 가용 상태라면 해당 블록의 payload는 뭘 하든 상관없으니까, 이곳에 이전과 이후의 정보를 담은 후에 관리해주는 것이다... 이러면 진짜 Linked-list 처럼 사용할 수 있을 것 같다 !

라고 생각했는데....ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

완전 지맘대로 이어져 있는거 같지만,.. 규칙을 유지한다는 걸로 받아드렸다... 어쨋든 가용블럭들 끼리는 이어져 있다. 아마 계속해서 링크되고 링크되다보니 저런 상황이 생긴 것 같다.

핵심 로직

Place 함수에서 바뀌는 점...

만약 place함수를 통해 분할을 하게 되면 가용을 저런 식으로 이어주어야 한다고 한다.

아마 footer에 double word를 더한 후에 이전 값을 넣어주면 되지 않을까 싶다.

말은 간단한데 앞, 뒤 애들 다 바꿔줘야 하니까 벌써부터 재밌다 !!!

CASE 1 (루트 ?)

위 사진에서는 case 1에 대한 것을 얘기하고 있다.

루트를 이용해야 하는데, 이전 묵시적 가용 리스트 next_fit 함수에서 사용했던 전역 변수를 이용하여 구현하면 될 것 같다.

헤딩 자료에서는 제일 최근에 가용상태로 변한 친구가 root가 된다고 한다.

명시적 가용 리스트에서 전역 변수를 생성하면 되겠지 했지만, 이 다음에 어떻게 해야할지 전혀 감도 잡히지 않았었다...

해당 강의를 통해 머릿속에 정신병이 하나 줄었다...

CASE 2

걱정은 했었다... 항상 합쳐지는 애들이 문제일 꺼 같았다.
이미 next_fit 구현에서 엄청 쓴 맛을 봐서 문제였는데, 여기서는 해당 방식을 이런 식으로 해결한다.

1. 가용된 리스트를 헤드로 만들어준다.
2. case2일 경우 합쳐지는 블록의 이전 블록 과 이후 블록을 서로 이어 준 후에 병합한다.

CASE 3

case 3 또한 비슷하지만, 합쳐진 블록의 payload에 root를 이어준다.

CASE 4

case 4는 case 2,case 3 에서 했던 것을 둘다 해주면 된다. 아마 함수화를 하면 간단하지 않을까 ..?

멜론 교수님이 명시적 가용 리스트가 빠르다고 막 말하던데,

한번 믿어봐야겠다... 저번에 best fit에 데인게 너무 마음이 아파서 신뢰가 안가지만,
지식이 늘었으니 만족한다.

이번에도 이론 정리가 끝났으니 구현으로...