0913_explicit free list 에 대하여

🙊 명시적 가용 리스트

Implicit free list와의 비교

• 묵시적 가용리스트는 모든 블럭을 다 순회하면서 가용영역을 찾아야 하는 단점이 있었다. 그래서 블럭 크기가 커지면 순회하는데 많은 시간을 사용하게 된다. 즉 블록 할당 시간이 전체 블록 크기에 따라 비례하게 된다.
• 그러면 가용블럭 끼리만 연결해 놓으면 순회할 시간이 줄어들지 않을까?

Explicit free list

가용 리스트끼리 포인터로 연결되어있는 구조를 가진다.

• 힙블록 모양
  • 할당된 블록은 Implicit free list 와 동일하지만, 가용 블록은 아래와 같은 차이점이 있다. 가용 블록의 payload 부분에 이전 가용 블록(prev, predecessor)의 포인터와 다음 가용 블록(next, successor)의 포인터를 저장해둔다는 차이가 있다. 그래서 Implicit free list와 비교해서 2워드만큼 공간을 더 사용하게 된다.

Explicit Free List 의 메모리 할당 방식

• 회색 부분 만큼 메모리가 할당 되었을때, 첫번째 블록과 세번째 블록의 포인터는 두번째 블록에서 남은 가용 영역을 가리키게 된다.

Explicit Free List 의 메모리 해제 방식

새로 해제된 블럭을 어디에 넣느냐에 따라 2가지로 분류된다.

• LIFO(last in first out) 정책
  • 할당 해제된 블럭을 가용 리스트 맨 앞에 넣는 방법
  • 장점 : 간단하고, 가용리스트를 검색할때 소요되는 시간이 O(1) 이다
  • 단점 : address ordered 방법에 비해 메모리 단편화 더 심하다고 알려져있다.
• Address-ordered 정책
  • 가용 리스트를 아래와 같은 메모리 순서로 관리하는 방식이다. ◦ *addr(prev) < addr(curr) < addr(next)*
  • 장점 : LIFO 방법에 비해 단편화가 를 줄일 수 있다. 왜냐하면 인접한 가용블록을 병합하여 더 큰 블록을 만드는 것이 용이해지기 떄문
  • 단점 : 가용 블록을 검색하는데 선형시간O(N)이 소요된다.

Lifo 정책에서 메모리 해제시 case

1. case1

   

   새로 할당된 블럭의 포인터를 bp 라고 하고, 기존 가용리스트의 첫블록을 가리키는 포인터가 free_listp라고 한다면, 아래 절차를 거쳐야 반환된 블록의 삽입 절차가 완료 된다.

   GET_PREV(bp) = NULL;
   GET_NEXT(bp) = free_listp;
   GET_PREV(free_listp) = bp;
   

2. case2 반환하는 블록의 뒤에있는 블록이 새로 가용되는경우,

   어쨋든 새로 반환된 블록이 맨 앞에 와야 되기 때문에 아래와 절차를 거쳐야 반환된 블록의 삽입 절차가 완료 된다.
   
   ```c
   GET_PREV(bp) = NULL;
   GET_NEXT(bp) = free_listp;
   GET_PREV(free_listp) = bp;
   
   //그리고 pred블록과 succ사이에 있는 블록이 가용 리스트의 맨 앞으로 이동해버렸으므로, pred 블록과
   //succ블록은 서로 앞뒤 블록으로 가리키면 된다.
   ```
   

• note: spliting 이 되서 free가 되면, 삭제를 먼저 한다(free list에서 삭제) 삭제를 한 뒤에 사이즈를 늘려서 하나의 가용블록로 만들어주고, 가용리스트에 넣어주는것.

1. case3

   반환하는 블록의 앞에있는 블록이 새로 가용되는 경우, case2와 원리는 동일하다.

   

2. case4

   반환하는 블록의 앞뒤 블록이 가용 상태인 경우, 역시 prev 블록의 succ블록이 앞뒤 블록으로 서로 가리키게 한다는 점에서 case2와 동일하다.

   

공부하는 방법에 대하여

1. 모르는 개념을 공부하기 위해 책을 먼저 읽는다.
2. 책을 이해하기 위해선 먼저 목차를 읽고, 머리속에서 카테고리화를 잘 해야 한다.
3. 새로운 개념이 정의하고 있는 용어를 잘 알아야 정리가 쉽다 . ex) 묵시적 가용 리스트 = Implicit Free list
4. 책을 봐도 모르겠으면 정리해놓은 블로그나 유튜브가 있는지 찾아본다.
5. 정리해놓은 글이나 영상을 본 뒤에 다시 책으로 돌아온다.
6. 3번봐도 모르겠으면 그냥 넘어간다. 뒤에것을 이해하고 다시 돌아왔을때 이해가 될 수도 있다.
7. 시간을 정해놓고 혼자 공부하되, 정해놓은 시간 이후에도 모르는 부분은 다른사람에게 물어본다.
8. 남에게 물어보는걸 어렵게 생각하지마라. 진짜 부끄러운건 모르는걸 꽁꽁싸매서 시간을 낭비하는것이다. 다만 내 머리안에서 뭘 모르는지를 확실히 알고 다른사람에게 물어봐야 한다.