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

리눅스 커널 자료구조 알고리즘 상세분석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