하루 요약

Q. 지금 지쳤나요?
A. 네

✏️오늘의 한 일

• RB TREE 정복 완료
• CSAPP 07,08

🌈오늘의 성장!

RBTree Lab 완료!

https://github.com/Anas-wg/jg_rbtree/blob/main/rbtree_lab/src/rbtree.c

Trouble Shooting

문제 원인

rbtree_delete_fixup() 함수에서 형제 노드 bro가 t->nil인 경우를 처리하지 않음

수정 전 코드

while (eb != t->root && eb->color == RBTREE_BLACK) {
    if(eb == t->nil){
      break;
    }
    // 방향 체크
    if(eb->parent->left == eb){
      is_eb_left = 1;
      bro = eb->parent->right;
    } else {
      is_eb_left = 0;
      bro = eb->parent->left;
    }
    // CASE 1: DB형제 RED
    if (bro->color == RBTREE_RED){
      // DB 형제와 부모 노드 색교환
      color_t temp = bro->color;
      bro->color = bro->parent->color;
      bro->parent->color = temp;
      // 부모 노드 기준 회전
      if(is_eb_left){
        left_rotate(t, bro->parent);
        bro = eb->parent->right; 
      } else {
        right_rotate(t, bro->parent);
        bro = eb->parent->left;
      }
    }

    // CASE 2: 형제 BLACK + 자식 둘 다 BLACK
    if ((bro->left == t->nil || bro->left->color == RBTREE_BLACK) &&
        (bro->right == t->nil || bro->right->color == RBTREE_BLACK)){
          bro->color = RBTREE_RED; // DB 형제노드 색교환
          eb = eb->parent; // 부모에게 짬처리 
    }

지금 수정 전 Code를 보면 형제가 NIL이고, 이경우 BLACK 이 되어 CASE 2로 넘어가야 했다.
그치만 bro의 left, right만 확인했기 때문에 bro == nil 일때 제대로 동작하지 않았던 것!

수정 후 코드

while (eb != t->root && eb->color == RBTREE_BLACK) {
    if(eb == t->nil){
      break;
    }
    // 방향 체크
    if(eb->parent->left == eb){
      is_eb_left = 1;
      bro = eb->parent->right;
    } else {
      is_eb_left = 0;
      bro = eb->parent->left;
    }

    // ✅ nil 형제 방지
    if (bro == t->nil) {
      eb = eb->parent;
      continue;
    }

    // CASE 1: DB형제 RED
    if (bro->color == RBTREE_RED){
      // DB 형제와 부모 노드 색교환
      color_t temp = bro->color;
      bro->color = bro->parent->color;
      bro->parent->color = temp;
      // 부모 노드 기준 회전
      if(is_eb_left){
        left_rotate(t, bro->parent);
        bro = eb->parent->right; 
      } else {
        right_rotate(t, bro->parent);
        bro = eb->parent->left;
      }
    }

    // CASE 2: 형제 BLACK + 자식 둘 다 BLACK
    if ((bro->left == t->nil || bro->left->color == RBTREE_BLACK) &&
        (bro->right == t->nil || bro->right->color == RBTREE_BLACK)){
          bro->color = RBTREE_RED; // DB 형제노드 색교환
          eb = eb->parent; // 부모에게 짬처리 
    }

해결 결과

bro가 t->nil인 경우에도 CASE 2 조건으로 들어가도록 명시적으로 처리함으로써, rbtree_find() 에서
반환되는 문제를 완전히 해결.

추가 탐구

주제

nil의 부모, 자식을 누군 초기화 하고 누군 초기화 안했는데 둘다 통과될까?

해당 코드

새로운 RB 트리를 정의하는 함수인데,
이때 nil 노드를 초기화 시, nil->left = nil->right = nil->parent = nil; 이 부분을
어떤 사람은 있고, 어떤 사람은 없는데 왜 둘다 되지? 라는 궁금증이 발생

rbtree *new_rbtree(void) {
  rbtree *t = (rbtree *)calloc(1, sizeof(rbtree)); // 동적 메모리 할당
  // TODO: initialize struct if needed
  // nil 노드 생성 & 초기화
  node_t *nil = (node_t *)calloc(1, sizeof(node_t));
  // nil 은 black
  nil->color = RBTREE_BLACK;
  // 초기상태 root노드 없으니까 nil
  nil->left = nil->right = nil->parent = nil;
  t->root = nil;
  t->nil = nil;    // 이걸 안 하면 NULL 접근되거나 쓰레기 값 뜰 수 있음
  return t;
}

정답은...

둘다 되는 게 맞았다.
원인은 로직 자체의 차이!

• nil의 부모, 자식 초기화가 필요 없는 경우

if (x != t->nil && x->parent->left == x) { ... }  // 항상 nil인지 먼저 체크

이렇게 nil 에 접근시 조건문에 진입하지 않도록 로직을 구현하면
nil의 자식에도 접근할 일이 없기 때문에 초기화하지 않아도 코드가 돌아갔던 것.

• nil의 부모, 자식 초기화가 필요 있는 경우

 // nil->left = nil->right = nil->parent = nil;

if (x->parent->left == x){
  is_eb_left = 1;
  bro = x->parent->right;
} else {
  is_eb_left = 0;
  bro = x->parent->left;
}

조건문에서 nil 검사를 하지 않기 때문에 x가 nil 이라면 nil->parent에 접근하게 된다.
이때 nil->parent = nil 을 위에서 방어적으로 초기화 해줬다면
문제없이 로직이 동작한다.

CSAPP 08

점진적 제어 흐름과 예외적 제어 흐름

1. 점진적 제어 흐름 (Sequential Control Flow)

• 인스트럭션 Ik와 Ik+1이 메모리상 나란히 존재.
• 단순히 명령어의 순차적 실행 외에도 시스템 상태 변화까지 고려.

2. 예외적 제어 흐름 (Exceptional Control Flow, ECF)

• 분기문, 함수 호출 이외의 흐름 변화를 모두 포함.
• 일반적인 ECF 종류:
  • 하드웨어 예외 (인터럽트, 오류 등)
  • 프로세스 간 문맥 교환
  • 리눅스 시그널 수신
  • C 언어에서의 비지역적 점프 (setjmp, longjmp)

---

프로세스의 구조와 동작

1. 프로세스란?

• 프로그램을 실행하는 추상적인 개념.
• 프로그래머는 시스템 콜을 통해 프로세스를 생성/제어 가능.
• 간단한 리눅스 쉘을 작성하여 작업 제어 기능 실습 가능.
• 독립적 논리적 제어 흐름 + 사적 주소 공간.

2. 논리적 제어 흐름 (Logical Control Flow)

• CPU는 여러 프로그램을 동시에 실행하지 않음.
• 각 프로세스의 명령어를 번갈아 실행 → 멀티태스킹 (Time Slicing).
• 여러 흐름이 실행 시간상 겹치면 → 동시성 (Concurrency).

3. 사적 주소 공간 (Private Address Space)

• 각 프로세스는 자신만의 메모리 공간을 갖는 것처럼 보임.
• 실제로는 OS가 메모리를 할당하고 접근 제어.

4. 모드 비트 (Mode Bit)

• 프로세스의 특권 수준을 나타냄.
• 커널 모드: 시스템 자원 접근 및 모든 명령어 실행 가능.
• 사용자 모드: 제한된 명령어 실행, 시스템 콜을 통해 커널 접근.

---

예외 처리 (Exception Handling)

1. 예외란?

• 하드웨어/소프트웨어에서 발생하는 예상치 못한 사건.
• 시스템은 예외 처리 매커니즘 제공.

2. 예외 처리 흐름

• 예외 번호: 각 예외는 고유 번호를 가짐.
• 예외 테이블: 예외 번호 → 처리 루틴 주소 저장.
• 예외 발생 시:
  • 현재/다음 명령어 주소 스택 저장.
  • 예외 처리기로 점프.

3. 예외의 종류

• 인터럽트: 외부 I/O 장치의 비동기 신호.
• 트랩: 프로그램의 의도적 요청 → 예: 시스템 콜.
• 오류 (Fault): 복구 가능한 에러, 예: 페이지 폴트.
• 중단 (Abort): 복구 불가능한 에러, 예: 머신 체크.

---

리눅스 시스템 콜

• 사용자 모드 → 커널 기능 사용을 위한 인터페이스.
• 예: 파일 읽기/쓰기, 프로세스 생성.
• 대부분 C 라이브러리에서 래퍼 함수 제공.

---

시그널 (Signal)

• 프로세스 간 또는 OS ↔ 프로세스 간 비동기 알림 메커니즘.
• 커널이 시스템 이벤트 감지 시 프로세스에 시그널 전달.
• 시그널 핸들러: 사용자 정의 함수로, 특정 시그널에 대한 처리 방식 지정.
  • 재진입 가능 함수, 비동기 안전 함수만 사용해야 동시성 버그 회피 가능.
• 아직 처리되지 않은 시그널 → Pending 상태.

---

⛏오늘의 삽질

이게 삽질이지... 그래도 해결했으니까 한잔해~~~