[sw정글 6주차] 세계최초 Buddy System 메모리할당기 구현(+당신이 몰랐을 7가지 코드 최적화 방법)
카테고리: swjungle survive
원희형이 준 썸네일
📚SW정글 6.7주차
CMU의 유명한 과제중 하나인 Malloc_lab을 수행하게 되었다.
Malloc에 대해서 기초수준 이상 알고 있다는 가정하에 글을 작성해 나가도록 하겠다.
🚀Implicit
✍️Implicit 작성
일단 시작은 Implicit로 시작하였다
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.008844 644
1 yes 99% 5848 0.008258 708
2 yes 99% 6648 0.013705 485
3 yes 100% 5380 0.011248 478
4 yes 66% 14400 0.000162 88999
5 yes 92% 4800 0.009671 496
6 yes 92% 4800 0.008483 566
7 yes 55% 12000 0.224711 53
8 yes 51% 24000 0.382306 63
9 yes 27% 14401 0.117968 122
10 yes 34% 14401 0.003491 4125
Total 74% 112372 0.788847 142
Perf index = 44 (util) + 9 (thru) = 54/100
Implicit-free-list구현코드 깃에서 보기(클릭)
🧐Implicit 분석
🍯당신이 몰랐을 malloc-(1): 코드 최적화방법🍯
🍯꿀1
Footer의 정보를 업데이트시, 그 위치는 헤드를 기준으로 산정된다 따라서 본인이 생각하는 가독성을 높이는 방법으로 코딩하면 된다.
처음에는 CSAPP의 코드가 잘못된 줄알았다. coalescing을 할 때, Header의 정보는 새로운 사이즈로 업데이트 하지만 footer의 정보는 제대로 업데이트 하지 않기 때문이다. 하지만 킹갓 기운이형의 도움을 통해, Footer의 위치정의는 (malloc_lab과제에서는)헤더정보를 이용해서 정의되기 때문에 굳이 빡빡하게 업데이트해주지 않아도 된다는 사실을 알게 되었다. 매번 이런 일이 발생한다. CSAPP를 의심하다가 시간을 날리곤 한다. ❗️CSAPP를 의심하지 말자❗️
점수를 살펴보겠다. 일단 thru점수, 즉 속도가 굉장히 떨어지는 모습을 보였다. 첫술에 배가 부를까? CMU교수님도, 정글의 코치님도 일단 Implicit free list를 먼저 만들기를 추천하였다. Allocator(할당기)에는 두가지 종류가 있다. Implicit과 Explicit. 하지만 Implicit한 할당기에는 또다시 Implicit free list 방법도 있고, Explicit free list방법도 있는 것이다. 이 개념을 잘 몰랐어서, 첫날에는… “아니 뭘 만들라는거야??”라는 생각밖에 들지 않았다
개념의 hierachy는 아래와 같다.
- 할당기
- Implicit
- Garbage collection 등
- Explicit
- malloc(), free()와 같은 명시적 방법
- 구현
- Implicit free list
- Explicit free list
- Segregated list
- 기타 다양한 방법들…
- Implicit
다시 본론으로 돌아오겠다. Implicit을 먼저 완성하고 나면 코드가 조금 눈에 보이게 된다. 여기서의 개선점은 free block을 찾는 방법을 통해 속도를 올릴 수 있는 것이다. First-fit이 아닌, next-fit과 best-fit을 시도해 볼 수 있는 점이다.
메모리 유틸 점수(44)점이 그렇게 나쁜 점수는 아니다. 하지만 Explicit을 구현하게 된다면, 그리고 그 Explicit을 LIFO방법으로 free list를 관리해주게 된다면 next-fit과 같은 효과가 있으리라 생각이 들었고, 바로 explicit-free-list방법으로 넘어가도 되겠다는 판단을 하였다.
🚀Explicit
✍️Explicit 작성
Results for mm malloc:
trace valid util ops secs Kops
0 yes 89% 5694 0.000263 21675
1 yes 92% 5848 0.000189 31024
2 yes 94% 6648 0.000341 19518
3 yes 96% 5380 0.000293 18393
4 yes 66% 14400 0.000202 71429
5 yes 88% 4800 0.000572 8392
6 yes 85% 4800 0.000586 8190
7 yes 55% 12000 0.003547 3384
8 yes 51% 24000 0.003729 6436
9 yes 26% 14401 0.118755 121
10 yes 34% 14401 0.003510 4103
Total 71% 112372 0.131984 851
Perf index = 42 (util) + 40 (thru) = 82/100
👾Explicit-free-list구현코드 깃에서 보기(클릭)
🧐Explicit 분석
Explicit는 어떻게 구현할까? 일단 연결되어있는 리스트들을 끊고, free-list의 맨 앞에 삽입 해 주면 된다. 어려워보이지만 아니다. 사실 `coalescing`함수만 바꾸어 주면 된다 그게 95%이다.
- coalescing조건별 free-list연결 끊어주기&이어주기(95%완료)
find()함수에서 전체가 아닌, free_list에서만 탐색하도록 바꾸기place()함수에서 쪼개고 넣을 때, 새로이 쪼개진 녀석을 free list의 맨 앞으로 넣어주기init()에 연결리스트 정보 넣어주기
그리고 위의 1번과정을 편하게 하기위해 많은 사람들이 구글링에서 발견하였을 removeBlock(), putBlock()과 같은 함수를 만들어 쓰는 것이다.
🍯당신이 몰랐을 malloc-(2): 코드 최적화방법🍯
🍯꿀2
여기서 init()을 할 때, Null값으로 처리를 해주어야 한다. 이유는 블럭을 free-list에서 제거할 때, 다음 블럭이 없는 경우에 예외처리를 쉽게 할 수 있기 때문이다.
init을 null처리를 해주면 굳이 예외조건을 하나 더 만들지 않아도, 알아서 연결리스트들이 Null처리 된다.
점수를 살펴보겠다. 일단 점수가 상당히 많이 올랐다. Thru 점수가 눈에 띄게 늘어난 점을 볼 수 있다. 오히려 유틸 점수는 떨어졌다. 메모리를 순서대로 사용하지 않았기 때문에 점수가 조금 떨어진것일까? CSAPP 9.9.7 장을 보면 first-fit의 장점은 큰 블록들을 뒤쪽에 둠으로써 좋은 메모리 이용도를 가질 수 있으며, next-fit은 더 나쁜 메모리 이용도를 가진다는 연구결과가 있다고 한다.
그렇다면, Explicit(Explicit free list)을 LIFO로 구현하게 된다면, 결국 next-fit과 같은 효과를 가지게 되므로, 메모리 이용도가 떨어지게 되었으며, util점수에서의 하락이 생긴 것이다.
그렇다면 오히려 Explicit에 next-fit을 적용하면 어떻게 될까?
😇Explicit + nextfit
Results for mm malloc:
trace valid util ops secs Kops
0 yes 89% 5694 0.002198 2590
1 yes 91% 5848 0.001451 4029
2 yes 95% 6648 0.004619 1439
3 yes 97% 5380 0.004597 1170
4 yes 66% 14400 0.000221 65070
5 yes 92% 4800 0.006093 788
6 yes 90% 4800 0.005284 908
7 yes 55% 12000 0.022854 525
8 yes 51% 24000 0.012285 1954
9 yes 27% 14401 0.120021 120
10 yes 30% 14401 0.003819 3771
Total 71% 112372 0.183443 613
Perf index = 43 (util) + 40 (thru) = 83/100
👾Explicit-free-list + next-fit구현코드 깃에서 보기(클릭)
Explicit에 Next를 입히자, 43점으로 유틸점수가 올라왔다. last_bp라는 변수에 마지막으로 작업한 위치를 넣었다. 왜 1점이 올랐을까 고민하였지만 해답을 찾을 수 없었다. 하지만 한가지 알 수 있는 사실은 바보짓을 했다는 것이다. 위와같이 코드를 짜자, free_list를 통한 할당가능한 블록탐색이 전혀 이루어지지 않는다는 것이다. 결국 Implicit+next로 돌린것과 다를바가 없는 것이다. Explicit에 굳이 next-fit을 입히려는 바보짓을 하지 말자
🍯당신이 몰랐을 malloc-(3): mdriver, 그리고 점수측정🍯
🍯꿀3
trace내의 .rep파일들(테스트케이스들)을 돌리며 점수측정이 진행된다. 내부에서 테스트케이스를 생성하는 스크립트도 있다. 원하는 테스트케이스들을 .rep파일로 만들어 낼 수 있는 것이다.
그리고 디버깅할때, default trace배열에 있는 테스트케이스들이 돌아간다. 이 내용을 바꾸어 주면 특정 케이스들만을 쉽게 돌릴 수 있다. -f옵션으로 테스트케이스 1개씩 돌릴 수 있는데 이게 왜 필요하냐? 라고 생각할 수도 있다. 하지만 -V옵션으로 돌아가는 테스트는 테스트케이스를 여러번 돌리는 것으로 추측된다. -f옵션으로 돌때는 init이 한번 실행되지만, -V옵션에서는 하나의 테스트케이스에 대해서도 init이 여러번 실행된다.
(필자는 -f옵션에서(1번돌릴 때)는 잘 돌아갔지만, -v옵션(테스트를 반복해서 돌릴 떄)에서는 segfault 오류가 나는 경험을 했다)
🍯당신이 몰랐을 malloc-(4): 추가점수 얻기🍯
🍯꿀4(필살기)
참고로 extend_heap(4)를 사용하면 2~3점의 추가점수를 올릴 수 있다. (테스트케이스에 한해서) 자주사용되는 작은 블럭이 잘 처리되어 점수가 오르는 것으로 추측된다. 필자는 3점을 더 올림으로써, explicit-(first-fit)으로 최종 86점을 획득할 수 있었다
8도 아니고, 16도 아닌 4이다. A반에서는 magic-number라고 불리우고 있다
🚀Segregated
✍️Segregated 작성
Results for mm malloc:
trace valid util ops secs Kops
0 yes 96% 5694 0.000372 15302
1 yes 98% 5848 0.000359 16299
2 yes 98% 6648 0.000437 15213
3 yes 99% 5380 0.000356 15125
4 yes 99% 14400 0.000494 29150
5 yes 93% 4800 0.000524 9153
6 yes 90% 4800 0.000526 9132
7 yes 55% 12000 0.000517 23197
8 yes 51% 24000 0.001454 16505
9 yes 25% 14401 0.119575 120
10 yes 29% 14401 0.004133 3484
Total 76% 112372 0.128747 873
Perf index = 46 (util) + 40 (thru) = 86/100
👾Segregated-fit 코드 깃에서 보기(클릭)
🧐Segregated 코드 분석
Explicit(explicit-free-list)과 상당히 유사하다. 아주 상당히 유사하다. 일단 크기별 리스트를 통해 관리하니 유틸성이 확실히 높아진 모습이다.
🍯당신이 몰랐을 malloc-(5): address-ordered policy점수🍯
🍯꿀5
Address-ordered policy로 segregated free list를 만든 친구는 90점을 받았다고 한다.
라고 한줄만 적기는 뭐해서 내용을 추가하였다.
디버거 사용에 익숙하지 않으신 분들은 아직 printf() 디버깅이 편할 것이다. 하지만 실행하다보면 pintf()의 출력이 로직상 맞지 않는 경우가 있다.
개행을 해주지 않으면, 개행직전까지 printf()로 터미너로 출력하려던 내용들은 모두 사라진다.
따라서, segfault나 core dump오류가 났다면, 오류가 나기 직전까지 개행\n없이 printf()출력하려던 내용들은 출력되지 않는다. 그렇기에 논리적으로 말이 안되는 출력문이 터미널에 찍힐 수 있는 것이다. pintf()를 이용한 디버깅시 모든 문구에 개행문자를 넣어주면 디버깅시 고뇌에 빠지는 시간이 줄어들 것이다.
(그리고 디버거 사용법을 미리 익혀두면, 추후 더욱 줄어들 것이다)
우리는 앞선 explicit과 같은 방법에서 free list는 따로 어딘가에 존재하는게 아니라, 루트에서 시작된 linked list라는 것을 알 수 있다. segregated도 결국 유사한 방식으로 할 수 있는 것이다. explicit때는 아래 그림과 같이
linked list(의 루트)를 헤더 사이에 넣어주었다. 여기서 linked list의 root는 next node와 prev node의 시작점이 되는곳을 일컬어서 말한다. segregated list에서도 저것처럼 예쁘게 관리했어야 한다.
위처럼 작성하는게 과제에서 원했던 부분 중 하나였고, 가장 깔끔하지만 나는 그냥 밖에….. 전역변수로 선언했다. 이번 나의 구현에서 아쉬웠던 점 중 하나이다.
segregated-fit 구현은 생각보다 쉬웠다. explicit에서는 하나의 프리리스트를 관리했었는데, 그 프리리스트의 개수를 20개로 늘려주는 정도의 작업이 필요했다. 공부내용을 돌이켜보면, Implicit-free-list가 명시적할당기(explicit Allocator)구현 공부 내용의 70%였고, explicit공부가 20%였던 것 같다. 여기까지 기초탄탄으로 왔다면, segregated-fit 등은 충분히 구현에 도전해볼만한 수준인 것 같다. 첫 Implicit에서 프롤로그블럭 위치잡아줄때에 비하면 뭐… 새로이 추가되는 개념들은 훨씬 쉬운 것 같다.
🚀Buddy System
sw정글 선배들의 글을 뒤져보아도, CMU의 git-repository를 털어보아도, 구글링을 해 보아도 Buddy System에 대한 코드는 그 어디에서도 찾아볼 수 없었다. 사실 미개척지를 가본다는 설레임으로 도전해 보았던 것 같다. 세계최초 (cmu의)Malloc_lab에 부합하는 코드로 Buddy System을 만들어보겠다라는 마음도 있었다. 그리고… 결국 해냈다. 기쁜 마음으로 이 글에 포스팅을 이어나가겠다.
🍯당신이 몰랐을 malloc-(6): 98점🍯
🍯꿀6
깃헙에 검색을 해보면 98점짜리 코드가 돌아다닐 것이다. 해당 코드는 100사이즈를 기준으로 ra태그를 붙여준다. 그리고 find함수를 별도로 두지 않고, segregated_free_list에서 너무 작지 않음 블럭이나 ra태그로 reallocation bit여부를 판단하고 적정 블럭을 찾아 할당해준다.
하지만 허무한 사실… 친구들이 해당 코드에서 reallocation부분에서의 ra태그 이용부분을 지웠음에도 불구하고 98점이 나온다고 한다. 다른부분에서 중요한 최적화가 이루어졌다는 것이다.
🍖그날의 회고(짧게)
필자는 버디버디(?)를 만들어 제출하는 그날까지도, 3시간정도 자고 삼각김밥을 먹으며 아침부터 코딩을 했다. 잠을 자지 않고 30시간동안 강의실에서 구현을 하는 친구들도 있었다. 리눅스의 slub방식처럼 미리 사이즈를 잘라두고, 일정크기 이상의 사이즈에 대해서 segregated 적용시켜보자는 아이디어도 있었고, realloc을 여러번 하는 테스트케이스를 물리치기 위해, 미리 사이즈를 두배로 realloc한 뒤 빈공간에 정보를 입력해 두자는 등 다양한 의견과 아이디어가 나왔었다. 개인적인 의견으로 2일만 더 있었으면 무수면 30시간 코딩도 없었을 터이고, 다른 사람들도 본인들의 아이디어를 구현해낼 수 있었지 않을까 싶다.
(11월2일 ~ 11월3일에 대한 짧은 회고 끝)
✍️Buddy System 작성
Results for mm malloc:
trace valid util ops secs Kops
0 yes 97% 5694 0.000285 19951
1 yes 94% 5848 0.000324 18061
2 yes 97% 6648 0.000378 17569
3 yes 97% 5380 0.000323 16656
4 yes 40% 14400 0.000457 31517
5 yes 75% 4800 0.000369 13026
6 yes 78% 4800 0.000369 13012
7 yes 45% 12000 0.000516 23251
8 yes 45% 24000 0.000852 28182
9 yes 15% 14401 0.115379 125
10 yes 40% 14401 0.003628 3969
Total 66% 112372 0.122881 914
Perf index = 39 (util) + 40 (thru) = 79/100
세계최초(?)Buddy System 구현 코드 깃에서 보기(클릭)
🧐Buddy System 코드 분석
결론부터 말하자면, coalescing함수만 만들면 95%는 완성이다. 일단 2n으로 블럭을 잘라 줄 수 있는 함수를 만들었다.
int ALIGN_double(size_t size)
{
size_t searchsize = 1;
// size_t searchsize = size;
while (1)
{
if (searchsize >= size)
return searchsize;
searchsize *= 2;
}
return 0;
}
그리고.. 아래는 내가 작성한 coalescing의 sudo code 이다
static void *coalesce(void *bp)
{
while (1)
{ // buddy가 계속 있다면, 끝없이 coalescing
if (내가 버디보다 뒤에있는 친구였다면..)
{
if (버디한테 할당할수 있으면)
{
remove_block(버디블럭);
전체 블럭에 2배사이즈 할당!
bp = 버디블럭
}
else
break;
}
else
{ //내가 버디보다 앞에있는친구였다면...
if (버디한테 할당할수 있으면)
{
remove_block(버디블럭);
전체블럭에 2배사이즈 할당!
}
else
break;
}
}
bp = (void *)bp;
insert_block(bp, size);
return bp;
}
대충 위와 같은 내용이다. 하지만 여기서 중~요한 점이 있다.버디를 어떻게 찾느냐에 관한 문제이다. 할당 요청 사이즈가 32(25)가 들어왔다면, 00…0010000(2) 하위 다섯번째 자리 수가 1인지 0인지에 따라 버디를 결정하면 된다.
라고 생각하셨나요?
하지만 heap의 바닥주소가 0으로 시작하지 않으면 성립하지 않는다. 따라서, 현재 bp에서 root_heap을 찾아 빼주고, 글고 나서야 (32요청받았을경우)5번째 자리수가 0인지 1인지에 따라 앞쪽버디인지, 뒤쪽 버디인지를 알 수 있는 것이다. 세부코드까지 궁금하신 분들은 위에서 그 세부코드를 확인하면 좋을 것 같다.
정말 고칠 시간이 없어서, 마찬가지로 전역변수로 선언을 해주었다. 만약 이 글을 읽는 누군가가(아마도 정글후배님들?) 나의 코드를 CMU가이드라인에 맞추어 root를 프롤로그 블럭 사이에 코드가 잘 돌아가는 모습을 이메일로 보내준다면, 밥 or 커피 사례를 약속하겠다.(현재의 코드도 일단 잘 돌아가긴 한다)
(☝️☝️☝️요렇게 바꿔주시고 저에게 연락주세요!!)
프로젝트를 마치며…
그리고 마지막으로 7번째 팁을 첨부하고 글을 마치도록 하겠다
🍯당신이 몰랐을 malloc-(7): slub, 그리고 최신할당기🍯
🍯꿀7(장문 주의)
코드를 이리저리 만지다보니, 최신 알고리즘으로 malloc_lab을 완성하고 100점을 받아야겠다! 라고 생각했다.
98점코드? 넌 내가 넘어주겠어!!
최신논문을 검색해보았으나 관련 정보는 나오지 않았다. 할당기에 관한 학술적 연구는 소극적으로 이루어지는 것 같다. 한가지 알 수 있었던 사실은 구글에서 만든 TCmalloc(Thread Caching malloc)이 가장 최신의 범용 할당기이다. 작은 오브젝트를 관리하는 Thread Local Cache와 큰 오브젝트를 관리하는 Central Heap으로 메모리를 나누고, Thread local cache에서 메모리가 부족할 때는 Central heap에서 얻어와 할당한다고 한다.
큰 메모리공간이 필요할 때는 vmalloc을 사용한다고 한다. vmalloc으로 할당받은 데이터들은 가상메모리공간에서는 연속적이지만, 물리메모리공간에서는 연속적이지 않다. 저번주에 구현했던 rbtree가 여기에 쓰인다. rbtree를 통해 적정 노드들을 찾아서 할당한다.
그렇다면 우리는 어떻게 구현해야 100점을 받을 수 있을까?
리눅스는 어떻게 구현되어있을까 검색 해 보았다. 코치님이 RB트리에서 어떻게 메모리를 사용하는지 보여주었다. 악착같이 메모리를 효율적으로 쓰려는 노력이 우리의 빠릿빠릿한 OS그 밑바닥에 들어있는 것이다. 그래서 이번에도 리눅스에 적용된 할당기 구현방법에 대해 검색해보았따. 여러가지 기술들이 적용되어있으며 slub방식이 그중 하나이다.
글을 읽다보니 slub의 개념은 쉽지 않았다. slab이 진화해서 slub이 되었으며, 쉽게말해 미리 할당받을 크기들을 준비해두는 방식인 것이다. 이는 buddy system과 상충되는 개념이 아닌것이다. buddy system과 slub을 같이사용함으로써 유틸성을 훨씬 더 높일 수도 있는것이다.
그리고… 리눅스 커널에서 내부 라이브러리들을 열었다. 이건 아직 내 능력 밖의 일이구나라는 생각을 하고, 빠른 포기를 선택했다.
추가사항: 과제를 진행하며 mdriver에 옵션을 주어 실행하면, 리눅스에 내장되어있는 malloc()함수로도 테스트케이스를 돌리고 그 결과를 (내코드의 결과와) 볼 수 있다. mdriver의 옵션에 대해 잠깐 읽어보면 코드에 대한 다양한 실험들을 해볼 수 있을 것이다
(사진: 나뭇잎으로 형광등을 막아가며 공부하는 나)
😵배우면서 깨달은 내용을 정리해 보았습니다. 틀린 것 같은 개념을 아래 댓글에 달아주시면 감사합니다😵
🌜 Thank you for reading it. Please leave your comments below😄
댓글 남기기