[SW 정글 45일차] segregated list 구현과 demand-zero memory

오늘은 지난 번에 계속해왔던 explicit dynamic allocator구현에서 free block list를 구현할 때 implicit list, explicit list를 사용하여 구현했었고 이번에는 segregated list를 사용해서 구현해보려고 한다.

 

 

 

1. segregated list는 무엇인가?

아래의 강의 영상과 컴퓨터 시스템을 보며 정리한 내용이다.

https://www.youtube.com/watch?v=ru_2lvPNeQM&list=PLbY-cFJNzq7z_tQGq-rxtq_n2QQDf5vnM&index=20 

 

segregated list와 implicit, explicit list의 가장 큰 차이점은 free block의 크기에 따라 size class를 나눠서 리스트에 모아두는 것이다.

이렇게 된다면 우리가 implicit, explicit list를 사용했을 때에는 first-fit, next-fit, best-fit 방식 중 하나를 택하여 일단은 탐색 중 만나는 free block의 size를 비교했는데 그 전에 size class로 나누어 놓는다면 탐색 시 조금 더 효율적이라고 생각한다.

 

size class를 나눌 때, size는 자신이 원하는대로 정하면 된다.

2의 제곱으로 나눌 수도 있고 크기가 작은 블록들은 자신의 size class에 할당하고 큰 블록들은 2의 제곱으로 분리하는 방법을 택할 수도 있다.

 

동적 저장장치 할당과 관련된 논문들에서는 어떻게 size class를 정의하는지, 언제 coalesce를 수행하는지, 언제 추가적인 heap을 요청하는지, 분할을 허용하는지 등에 따라 10여가지 변형된 분리 저장장치가 존재한다.

 

 

내가 구현한 것은 segregated list의 size class를 2의 제곱으로 분류했고 list의 크기는 20으로 설정했다.

그리고 coalesce는 free block이 생성될 떄마다 수행하게 해주었고 분할도 수행되게 해주었다.

segregated list에 새로운 free block을 insert시키거나 delete시킬 때, case는 총 4개 존재한다.

(그리고 size class별로 나눈 뒤, 각 block들은 double linked list로 관리된다.)

 

case1. insert혹은 delete 하고자하는 block이 head부분일 떄

case2.  insert혹은 delete 하고자하는 block이 tail부분일 떄

case3.  insert할 때 list가 빈 상태이거나 delete하면 list가 빈 상태가 될 때

case4. list의 중간에 insert하거나 중간을 delete할 때

 

이렇게 case를 4가지로 나누어 segregated list를 관리하는 것외에는 explicit와 크게 달라지는 점은 없다고 생각한다.

 

코드는 아래 깃헙에 있다. (mm_segregated.c 파일)

https://github.com/JJong-Min/malloclab-jungle

 

구현하면서 의문이 든 점은 한 가지이다.

할당받을 block이 선정된 후에 내가 원하는 size보다 크다면 분할을 하여 남은 remainder는 free block으로 만들어 준다.

이 때, free block이 내가(혹은 엔지니어) 생각하는 기준에서 작다면 remainder(free block)을 앞에 두고 뒷부분을 할당받고 free block이 크다면 앞부분을 할당받고 뒤에 remainder(free block)을 둔다는 것이다.

 

 

 

 

2. demand-zero memory는 무엇인가?

컴퓨터 시스템 책을 읽으면서 9.9 도입부에 아래와 같은 말이 있었다.

"we will assume that the heap is an area of demand-zero memory that begins immediately after the uninitialized data area and grows upward."

 

위에서 demand-zero memory라는 말이 이해가 되지 않아 slack 질문방에서 도움을 주시는 조교님께 답변을 얻었다.

 

demand-zero memory라는 것은 말그대로 필요할 때(demand) 할당하고 0으로 초기화해주는(zero) 메모리를 말한다.

리눅스의 메모리 시스템은 매우, 최대한 게으른 방식(lazy)으로 작동하도록 되어있다.

게으르단 뜻은 어떤 자원을 요청하거나 동작을 요청했을 때, 그것이 정말 필요해질 때까지 실제 자원을 할당하거나 동작을 실행하지 않는 것을 의미한다.
즉, 우리(user program)가 kernel에게 메모리를 할당해달라고 요청하면(sbrk) kernel은 거의 아무것도 하지 않고(특정한 VM 영역이 할당되었다는 최소한의 표시만 해두고) 우리에게 할당이 끝났다고 알려준다.

즉, 특정 VM 영역이 할당되었다는 사실만 표시해두고, 실제 메모리는 할당되지 않은 상태로 남아있게 된다.

이렇게 되면 유저는 메모리가 할당된줄알고 해당 주소에 뭔가를 쓰거나 읽을텐데, 처음 읽거나 쓰려고 하는 순간 실제 메모리(페이지)가 할당되어있지 않기 때문에 page fault가 발생할 것이고, 그제서야 kernel은

1. 사용하지 않는 메모리(페이지)를 할당하고
2. 그 페이지를 0으로 채운뒤에
3. 유저가 원래 하려고했던 명령어를 다시 실행하게 된다.

 

알아봐야 할 키워드

demand paging, lazy loading

 

 

---

[오늘의 나는 어땠을까?]

오늘은 malloc lab 주 마지막 날이여서 코드를 조금 더 보고 복습하는 시간을 가졌다.

복습을 해보니 정말 공부할 것이 많고 왜?라는 질문을 계속 던지게 됐다.

이러한 시간을 가지니까 이번 주에 내가 너무 여유롭게 공부했나?라는 생각이 들었다.

그렇다고 이미 지난 날을 후회하지는 않고 그래도 이 전까지 얻은 지식이 꽤 되기 때문에 오늘 남은 시간에 궁금한 키워드 2가지, 메모리 영역(코드, 데이터, 힙, 스택)에 대해 알아보고 garbage collection에 대해 공부하려고 한다.

 

퇴근시간은 미정이다.

일단은 2가지 키워드를 이해하고 기숙사에 갈 생각이다.