[WEEK06] DAY39~46 & malloc lab 구현

https://velog.io/@yerimii11/WEEK06-malloc 2021년 12월 18일에 작성된 게시글 아카이브입니다.  (사유: 블로그이전)

[WEEK06] DAY39~46 & malloc lab 구현

---

2021.12.09 THU ~ 12. 16 THU

안들던 불안함이 드는 주간이었다.
감정을 다스려야한다. 불안함을 연료로 삼자.

16일 오후는 알고리즘 스터디에서 각자 한 주간 푼 문제를 가지고 랜덤으로 문제를 지정받아 발표연습하는 시간을 가졌었다.

---

Malloc lab 최종 완성 코드

• implicit (first fit 주석, next fit) : 주석 자세히 썼으니 잘 모르겠는 사람 읽기 추천
• explicit (next fit)
• segregated list

---

Git 가져올 때 bare, mirror 차이

bare 와 mirror의 차이는 아주 간단하게 보면 기존 저장소의 모든 이력을 가져오냐의 차이. bare의 경우 원본 저장소와 관련이 없어짐. mirror의 경우 원본 저장소의 정보를 가지고 있고 원본 저장소의 모든 이력을 가져옴.

---

<메모리 누수 에러 확인> (꿀팁)

1.

• vi 파일에 들어가서 바로 수정 가능
• 수정시 i 누르고, 저장시 :wq, 그냥 나갈땐 :q
  vi makefile
  -wall 옆에 -fsanitize=address 써주기
  그러면 ./mdriver 했을 때 에러, 몇번째 라인인지 뜸

2.

valgrind : 메모리 누수 탐지 명령어.
valgrind ./mdriver

---

malloc 공부 도움 받은 블로그

할당기

1.
2.
3.
4.

---

implicit, explicit, segregated 구분

• implicit
  array 선언. 포인터 연산으로 조각블럭을 넘어감.
  헤더의 사이즈로 다음 블록으로 넘어감
  할당된 블록, 프리블록도 다 보고 지나감
• explicit
  포인터를 사용해서 링크드리스트처럼 사용, free들만 모아서 링크드리스트처럼 만듦
  탐색 순서 LIFO (last in first out) : 프리블럭 리스트에서 새로 생긴 프리블럭이 있으면 맨 앞으로 넣고, 탐색시 걔부터 탐색.
  first fit으로 find.
• segregated List
  이중연결리스트들을 묶어놓은 것
  리스트에서 각각 크기별로 가용리스트를 가리켜줌
  segregated_free_lists : 정적 포인터. 정적 배열에 있다고 생각하면 되는지? yes. 배열이 주소값을 담을 배열인 것임.

---

Segregated list

크기가 같은 범위에 있는 가용리스트끼리 서로 연결시킨 것.
그 크기를 지수 간격으로 나눠서 저장을 한 것. (지수 간격 : 1-2, 4, 8, …)

---

Buddy system

Seg-> 최악의경우 끝까지 돌고 찾아야해서 O(logN)의 시간복잡도.
but Buddy system은 자식노드에서 못찾으면 부모노드 split여부 확인 후 합치고 버디(형제노드) 공간이 free이면 그쪽에 할당하기 때문에 시간복잡도가 절반으로 O(N)이 된다.

---

mem_sbrk 함수

98line

if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)

위의 코드에 대해 자세히 알고싶어졌다

heap_listp = 
mem_sbrk(4*WSIZE);
    if (heap_listp == (void *)-1) {
        return -1;
    }

풀어쓰면 이렇게 됨
일단 mem_sbrk로 힙에 메모리 요청을 해 그러면 mem_sbrk의 리턴값 나오고
그게 문제없이 주소가 나오면 조건문에 안걸리고 다음 작업으로 가는거고 그게 아니라 -1이 나왔으면
오류로 감지하고 멈추는거.

mem_sbrk 는 sbrk 함수의 단순 모델. 힙을 incr 바이트만큼 확장하고 새 영역의 시작 주소를 반환. 이 모델에서는 힙을 축소할 수 없다. incr가 입력값
mem_sbrk 함수 돌리면 내가 넣은 인풋값만큼의 영역이 있는지 찾아보고 있으면 그 포인터주소를 heap_listp에 반환하고 아니면 -1 리턴하는 함수.
정식으로 메모리 요청하는 건 extend_heap 함수에서 실행

오전 2:54 예림 mem_sbrk가
오전 2:54 예림 그러면
오전 2:55 예림 메모리요청값 <0 이거나
오전 2:55 예림 힙의 끝값+요청값 > 힙의 max주소값
오전 2:55 예림 이면 에러 ?
오전 2:56 예림 그니까 넣을 공간이 없으면 ?
-> 어 그렇지 주소값도 크기가 있는데 그 크기가 가장 큰 주소를 저장해놓은곳같아

---

void *

if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)

void니까 리턴값이 없을것같은데 리턴값을 주네? 하고 이상하게 생각할 수 있는데
얘는 모든 포인터 타입으로 바뀔 수 있어
void 로 선언된 변수 하나가 있을 때
int a = 10;
char str = "예림이"
float b = 3.5
이런거 주소값 넘겨주면
그 타입으로 변수 타입이 바뀌어
대표적으로 내장함수 malloc이 리턴 타입이 void 거든
malloc으로 어떤 값이든 동적할당을 할 수 있잖아?
이게 void 타입으로 인풋값을 받기 때문에 가능한거야
그래서 타입이 유동적으로 바뀔 수 있는 포인터변수는 void*로 선언해

그럼 -1은 왜? 그냥 오류라고 표시한거. 통념적으로 함수 리턴값이 -1이면 오류있다는 표현이니까