리눅스 커널 자료구조 알고리즘 상세분석2

리눅스 커널 자료구조 알고리즘 상세분석2

Second Edition

347쪽 | 257*188mm (B5) | 780g | ISBN : 978-89-97750-11-5

저자 정재준 (c)커널연구회 www.kernel.bz

책소개:

리눅스 커널은 전세계 뛰어난 개발자들에 의해서 지속적으로 향상되고 있고  그 속에 있는 소스코드들도 놀랄만큼 최적화되고 있다.  특히 리눅스 커널에 구현되어 있는 Linked List, Red-Black Tree등을 분석해 보면 아주 간결하면서도  효율적으로 만들어진 소스 코드라는 것을 느낄 수 있다.  이책은 리눅스 커널 소스에 구현되어 있는 자료구조 알고리즘을 모두가 이해하기 쉽도록 분석한 내용으로 구성되어 있다.

소프트웨어 코딩은 자료구조 알고리즘부터 출발한다.  자료구조 알고리즘은 코딩의 기본이며,  이것을 가장 잘 이해하기 위한 출발점이 되는 것이 링크드 리스트이다.  링크드 리스트를 사용하여 자료를 효율적으로 연결(포인터)하는 방법을 익힐 수 있다.  더구나 리눅스 커널 소스의 링크드 리스트는 아주 효율적으로 만들어져 있다.  앞쪽과 뒤쪽을 연결하는 2개의 포인터만으로 연결하는 위치에 따라서 Stack도 되고 Queue도 된다.  즉, 별다른 부가적인 데이터를 사용하지 않고 Linked List 연결관계만으로 Stack과 Queue을 모두 구현한다.  여러가지 자료구조 알고리즘 서적들에서 링크드 리스트를 설명하고 있지만,  리눅스 커널 소스에 있는 링크드 리스트가 가장 뛰어나다고 말할 수 있다.  이책은 필자가 커널연구회를 운영하며 수년동안 리눅스 커널 소스를 분석한 내용을 실무적으로 상세히 설명한다.

이책은 리눅스 커널 소스에 구현되어 있는 자료구조 알고리즘을 이해하기 쉽도록 설명하는 내용으로 전체 6장으로 구성되어 있다.

1장에서는 자료구조 알고리즘에 대한 기본 원리를 이해하기 쉽게 설명한다.

2장과 3장에서는 리눅스 커널에 구현되어 있는 Linked List를 설명하고 스택과 큐를 독자들이 직접 구현할 수 있도록 내용을 구성했다.

4장은 Red-Black Tree를 자세히 설명하고 키값을 삽입, 삭제하면서 트리의 좌우 균형을 어떻게 맞추어 가는지 직접 실습할 수 있도록 소스를 설명한다.

5장은 대용량 데이터 처리에 적합한 B+Tree에 대해서 소스와 함께 구현방법을 자세히 설명한다.

6장에서는 리눅스 커널 소스에 구현되어 있는 자료구조를 직접 확인하며 익힐 수 있도록 구성했다.

마지막으로 부록에서는 리눅스 커널 소스를 효율적으로 분석할 수 있는 방법들에 대해서 기술했다.

목차 내용 :

리눅스 커널 자료구조 알고리즘 상세분석2

저작권    2

커널연구회 로드맵    3

저자 소개    4

목차    5

1. 자료구조 알고리즘 개요    8

2. LINKED LIST    13

2.1 주소(포인터)연산 이해    13

2.2 링크드 리스트 전체소스    19

2.3 LIST_ADD (STACK)    32

2.4 LIST_ADD_TAIL (QUEUE)    39

3. QUEUE(KFIFO)    45

3.1 KFIFO 소스 분석    45

3.2 KFIFO 실습    55

4. RED-BLACK TREE    60

4.1 RED-BLACK TREE 개념    60

4.2 RED-BLACK TREE 소스    64

4.2.1 include/linux/rbtree.h    64

4.2.2 lib/rbtree.c    68

4.2.3 rbtree_test.c    79

4.2.4 실행 결과    84

4.3 RED-BLACK TREE 구조체    87

4.4 삽입(INSERT) 소스1 분석    90

4.4.1 노드(key=10) 삽입    92

4.4.2 노드(key=20) 삽입    95

4.4.3 노드(key=30) 삽입    98

4.4.4 노드(key=40) 삽입    104

4.4.5 노드(key=50) 삽입    107

4.4.6 노드(key=60) 삽입    110

4.4.7 노드(key=70) 삽입    112

4.4.8 노드(key=80) 삽입    115

4.5 삽입(INSERT) 소스2 분석    121

4.5.1 노드(key=80) 삽입    122

4.5.2 노드(key=70) 삽입    125

4.5.3 노드(key=60) 삽입    128

4.5.4 노드(key=50) 삽입    133

4.5.5 노드(key=40) 삽입    137

4.5.6 노드(key=30) 삽입    140

4.5.7 노드(key=20) 삽입    142

4.5.8 노드(key=10) 삽입    145

4.6 삽입(INSERT) 소스3 분석    151

4.6.1 노드(key=10) 삽입    151

4.6.2 노드(key=30) 삽입    154

4.6.3 노드(key=20) 삽입    157

4.6.4 노드(key=50) 삽입    164

4.6.5 노드(key=40) 삽입    165

4.6.6 노드(key=25, 22) 삽입    168

4.6.7 노드(key=35) 삽입    170

4.7 탐색(SEARCH) 소스 분석    175

4.8 삭제(ERASE) 소스 분석    182

4.8.1 노드(key=10) 삭제    189

4.8.2 노드(key=20) 삭제    193

4.8.3 노드(key=30) 삭제    196

4.8.4 노드(key=40) 삭제    203

4.8.5 노드(key=50) 삭제    206

4.8.6 노드(key=60) 삭제    212

4.8.7 노드(key=70) 삭제    216

4.8.8 노드(key=80) 삭제    219

5. B+TREE    222

5.1 B+TREE 소스    223

5.2 B+TREE 구조체    249

5.3 B+TREE 삽입 알고리즘    252

5.3.1 노드 분할    255

5.3.2 부모노드 생성    257

5.3.3 부모노드 분할    261

6. 리눅스 커널 자료구조    265

6.1 자료구조 기본    265

6.2 스케쥴러 자료구조    269

6.3 스케쥴러 소스 분석    276

6.3.1 스케쥴러 클래스 정의    278

6.3.2 CFS 스케쥴러 실행 함수    285

6.3.3 RT 스케쥴러 실행 함수    288

6.3.4 DeadLine 스케쥴러 실행 함수    289

부록A. 리눅스 커널 소스 분석 도구    292

A.1 커널소스 다운로드    294

A.2 커널소스 빌드    297

A.2.1 라즈베리파이 보드에서 직접 빌드    297

A.2.2 리눅스 Host PC에서 크로스 컴파일    298

A.3 커널 설치    299

A.4 커널소스 디버깅(KGDB)    302

부록B. 커널연구회 똑똑한왕자 소개    310

부록C. 커널연구회 교육과정 상세안내    322

C.1 커널연구회 교육과정 로드맵    322

C.2 C언어와 자료구조 알고리즘    323

C.3 리눅스 시스템 프로그래밍    327

C.4 ARM 아키텍쳐, STM32 프로그래밍    331

C.5 리눅스 커널 자료구조 알고리즘 실습    334

C.6 리눅스 커널 소스 디버깅 실습    338

C.7 리눅스 커널 DEVICE TREE 실습    342

C.8 교육 내용 테이블    346