[SW 사관학교 정글 8기] WEEK04 (RB-TREE)

탐험준비 - Red-Black Tree

📢 “정글끝까지 가기 전에, 준비운동을 하며 필수 스킬을 익혀봅시다!”

지난 3주간은 고급 언어인 Python 언어로 가변 리스트, 우선순위 큐와 같은 추상화된 데이터 타입 (abstract data type)을 사용하여 컴퓨터를 다루는 방법을 익혔습니다. 이번 3주간은 Assembly 언어와 매우 가까운 C언어를 사용하여 좀 더 컴퓨터의 본질에 가까이 가 봅시다.
3주간 각 1주차 씩 Red-Black tree → malloc → 웹 proxy 서버를 C언어로 구현하면서, C언어 포인터의 개념, gdb 디버거 사용법 등을 익혀봅니다. 또한, Segmentation fault 등 새로운 에러들을 마주해봅니다! 🙂
알고리즘(CLRS), 컴퓨터 시스템(CS:APP) 교재를 참고하여 진행합니다.
RB tree - CLRS 13장, malloc - CS:APP 9장, 웹서버 - CS:APP 11장

“C언어는 F1 레이스 카와 비슷하다. 그 무엇보다도 빠르고 성능 좋지만, 아무나 운전할 수 없고, 아무나 운전하도록 두어서도 안된다.”

“C 프로젝트를 망가뜨리고 싶다면, 초짜를 프로젝트 멤버로 투입하면 된다. 수 개월 안에 찾을 수 없는 버그가 생길 것이다”

키워드

WEEK04: 동적 메모리 할당, 포인터, 메모리 누수, 균형 이진 탐색 트리, 데이터 세그먼트

Red-Black Tree 구현

이론 공부
구현

코치님의 말씀

이번 주 과정은 Red-black tree만 익히는 게 아닙니다.
Red-black tree라는 data structure의 작동 구조에만 집중하고 있는 듯 한데, 아시다시피 이번 과정은 data structure만 익히는 게 아닙니다.
C언어와 컴퓨터의 좀 더 낮은 구조를 이해하고 그것을 이용할 수 있는 능력을 익히는 것도 있고,
기본적으로는 C 언어로 짠 프로그램이 제대로 돌아가는지, 문제가 없는지 파악하고 문제를 해결하는 방법을 익히는 것도 중요합니다.

코치님의 질문

🙋‍♀️ 1번

Q. Segmentation Fault (core dumped) 라는 메시지를 받고 무엇이 잘못되었는지 파악할 수 있는지

A. 프로그램이 허용되지 않은 메모리 영역에 접근을 시도하거나, 허용되지 않은 방법으로 메모리 영역에 접근을 시도할 경우 발생한다.

(따로 강의실에서 팀원들과 작성하고 있었는데 코치님이 급 방문하셔서 질문했다.. 하지만 위의 답변은 책의 내용 그대로라고 하시면서 꼬리질문을 하셨다...)

=> null을 가르킬 때!
-> "C언어"에서 null은 정수형이다. 즉, 0이다. 포인터에서 null을 가리킨다는 것은 0을 가리킨다는 것. 포인터가 정수형을 가르킨다는 것은 오류다..
-> 어떠한 메모리 주소도 가리키지 않을 때!!!
=> 포인터 변수에 숫자 넣었을때(null포함), 포인터 연산자를 잘못 사용하였을 때 ...

자세한 설명 포스팅 보러가기

🙋‍♀️ 2번

Q. core dumped 라고 하는데 core라는 녀석은 어디에 dump되며 core가 있으면 뭘 할 수 있는지

A.
"core dumped"라는 메시지는 프로그램이 비정상적으로 종료되어서 운영체제가 해당 상태를 기록하기 위해 코어 덤프(core dump)를 생성했다는 것을 의미한다.
코어 덤프는 프로그램이 충돌할 때 메모리의 상태와 관련된 정보를 포함하는 파일입니다. 일반적으로 이 파일은 실행 중인 프로그램이 위치한 디렉토리에 생성된다.

코어 덤프 파일은 일반적으로 디버깅 목적으로 사용한다.

코어 덤프 파일을 분석하는 방법은 여러 가지가 있다. 예를 들어, gdb(GNU Debugger)를 사용하여 코어 덤프 파일과 원본 소스 코드를 연결하여 충돌의 원인을 찾을 수 있습니다. gdb를 사용하면 메모리 덤프를 검사하고 프로그램이 충돌한 지점을 확인할 수 있다.

core dump는 "메모리가 놓아졌다" 이런 의미를 가지는데 코어 덤프라 불리는 이유는 컴퓨터 초창기에 메모리를 주로 코어라고 지칭했기에 그렇다.

🙋‍♀️ 3번

Q. valgrind는 뭐고 gdb는 뭔지

A.
Valgrind는 메모리 누수를 탐지하는 리눅스용 디버깅 툴
gdb는 GNU 에서 나온 디버거 프로그램

🙋‍♀️ 4번

Q. char s1 ="abc"; 와 char s2 = malloc(4); 라는 문장에서 s1과 s2가 저장된 주소, malloc이 return 하는 주소는 어떤 메모리 세그먼트에 할당되는지

A.
1. char *s1 = "abc";

이 문장은 문자열 "abc"를 가리키는 포인터 s1을 선언하고 초기화한다.
문자열 리터럴은 프로그램의 데이터 세그먼트에 저장된더. 이는 실행 파일의 데이터 세그먼트에 상수 문자열이 저장되며, 실행 중에 수정할 수 없다.
s1은 문자열 "abc"의 시작 주소를 가리키는 포인터이므로, 데이터 세그먼트에 저장된 "abc"의 시작 주소를 가리킵니다.

2. char *s2 = malloc(4);

이 문장은 동적으로 메모리를 할당하여 이를 가리키는 포인터 s2를 선언하고 초기화한다.
malloc() 함수는 힙(heap) 세그먼트에서 메모리를 할당한다. 힙은 프로그램 실행 중에 동적으로 할당 및 해제되는 메모리 영역이다.
malloc() 함수는 할당한 메모리 블록의 시작 주소를 반환한다. 이는 힙 세그먼트에서 할당된 메모리 블록의 시작 위치를 가리킨다.

🙋‍♀️ 5번

Q. C에서는 return "abc"; 같은 짓을 하면 왜 쌍욕을 먹는지

A. 함수가 문자열을 반환하다는 것은 문자열의 주소를 반환한다는 것이다. 따라서 반환되는 문자열의 주소값이 반환 후에도 유효한 주소값이어야 한다.
=> 직접 실습을 해 본 결과, 읽기모드는 가능하고 편집이 불가능했음

🙋‍♀️ 6번

Q. malloc을 해 두고 free를 안하면 어떻게 되는지

A.
malloc() 함수를 사용하여 동적으로 메모리를 할당한 후에 그 메모리를 해제하지 않으면 메모리 누수(memory leak)가 발생한다. 메모리 누수란 프로그램이 더 이상 필요로하지 않는 메모리를 해제하지 않고 그대로 두는 것을 의미. 이는 프로그램이 실행되는 동안 사용 가능한 메모리가 점차 고갈되어 시스템 성능에 부정적인 영향을 미칠 수 있다.

🙋‍♀️ 7번

Q. free 한 이후에도 pointer 변수로 값을 바꾸면 어떻게 되는지

A.
정의되지 않은 동작: 포인터가 이미 해제된 메모리를 가리키고 있기 때문에 해당 메모리에 접근하려고 하면, 프로그램이 비정상적으로 종료되거나 예기치 않은 결과가 발생할 수 있다.

새로 설정된 값 변경: 일부 시스템에서는 free() 함수를 호출한 후에 해당 메모리 영역을 재사용하거나 다른 목적으로 사용할 수 있다. 이 경우, 해당 메모리 영역에 다른 값이 쓰여질 수 있으며, 그 결과 포인터 변수가 이를 가리키게 된다.

🙋‍♀️ 8번

Q. 왜 sizeof(struct node { char color; struct node *next; }) 가 9가 아니고 16이 되는지

구조체의 크기는 1바이트 (color) + 7바이트 (padding) + 8바이트 (next) = 16바이트
-> malloc-lab 주차에서 알게된다...

회고

알고리즘 주차까지 적응하느라 겉돌았던 것 같은데, C언어를 시작하면서 공부가 재밌고 강의실에서 공부하는 것도 잘 적응했다. 따라서 하루 루틴이 정해진 것 같다. 앞으로 루틴을 지키면서 열심히 공부해보려고 한다!
RBTree는 구현하고 테스트하면서 내가 구현한 것을 검사할 수 있었는데, 의사코드 해석이 가장 중요했던 것 같다. 이론을 빠삭하게 공부해도 의사코드가 이해안되는 경우가 많았다. 의사코드를 한줄한줄 이해하다보면 코드로 구현하는 것은 수월했다.
목요일에는 퀴즈를 봤는데 생각보다 어려웠다... 더 빡세게 c언어를 공부해야할 것 같다. 앞으로도 화이팅!