JUNGLE 240422 ~ 240423 (W05)

in Study #Jungle

KRAFTON JUNGLE Week 05

AVL 트리

  • 자가 균형 이진 탐색 트리의 일종
  • 트리의 높이를 최소화하여 검색, 삽입 및 삭제 작업의 시간 복잡도 개선
  • 각 노드의 서브트리 높이 차이가 1보다 크지 않도록 균형을 유지하는 트리
  • 따라서 균형 계수 (Balance Factor) 라고 하는 높이 차이를 계산하여 트리를 회전시켜 균형 유지

AVL 트리의 특징

  1. 균형 유지: AVL 트리는 항상 높이의 차이가 1 이하인 균형을 유지
  2. 탐색 속도: AVL 트리는 균형을 유지하기 때문에 탐색 연산의 시간 복잡도는 O(log n)
  3. 삽입 및 삭제 효율성: AVL 트리에서 삽입 및 삭제 연산을 수행할 때마다 균형을 유지하기 위해 회전 연산 수행

AVL 트리의 회전

  • Left-Left (LL): 오른쪽으로 너무 많은 높이가 쌓였을 때 발생
  • Right-Right (RR): 왼쪽으로 너무 많은 높이가 쌓였을 때 발생
  • Left-Right (LR): 왼쪽 자식의 오른쪽 서브트리에 삽입이 발생할 때 발생
  • Right-Left (RL): 오른쪽 자식의 왼쪽 서브트리에 삽입이 발생할 때 발생

8장: Exceptional Control Flow

  • 제어 이동: 인스트럭션 I(k)에 대응되는 주소를 a(k)라고 했을 때, a(k)에서 a(k+1)로의 전환
  • 제어 흐름: 제어 이동의 배열. 보통의 제어 흐름에서 I(k)와 I(k+1)은 메모리 상에서 나란히 존재
  • 예외적인 제외 흐름: 프로그램 실행 중에 다양한 예외 상황에 대비하여 예외 처리 메커니즘 사용
  1. 예외 상황은 어떤 프로세서 상태의 변화에 대한 대응으로 제어 흐름의 갑작스런 변화를 의미
    • 현재 인스트럭션의 실행에 직접적으로 관련된 경우: 가상 메모리 페이지 오류, 산술 오버플로우, divide by zero
    • 현재 인스트럭션의 실행과 관련 없는 경우: 시스템 타이머 정지, I/O 요청이 완료된 경우
  2. 시스템은 가능한 예외 상황의 종류마다 중복되지 않는 양의 정수를 예외 번호로 할당
    • 프로세서 설계자가 할당: divide by zero, 페이지 오류, 메모리 접근 위반, breakpoint, 산술연산 오버플로우 등
    • 운영체제 커널 설계자가 할당: 시스템 콜, 외부 I/O 디바이스에서 온 시그널
  3. 시스템 부팅 시, 운영체제는 예외 테이블을 할당하고 초기화해서 엔트리 k는 예외 상황 k에 대한 핸들러의 주소를 가짐
    • 런타임에 프로세서는 이벤트 발생을 감지하고 대응하는 예외번호 k를 결정
  4. 프로세서가 이벤트 발생을 감지하면, 예외 테이블이라고 하는 점프 테이블을 통해 예외 처리 핸들러로 간접 프로시저 콜을 한다.
    • 프로세서는 예외 테이블의 엔트리 k를 통해 간접 프로시저 콜을 해 예외 상황을 발생시킴
    • 예외 테이블의 시작 주소는 예외 테이블 베이스 레지스터라는 특별한 CPU 레지스터에 저장된다.
  5. 예외처리 핸들러가 처리를 끝내면, 예외 상황을 발생시킨 이벤트의 종류에 따라서 다음 중 1가지 일 발생
    • 핸들러는 제어를 현재 인스트럭션 I(curr)로 돌려준다.
    • 핸들러는 제어를 다음 인스트럭션 I(next)로 돌려준다.
    • 핸들러는 중단된 프로그램 종료
✔ 예외 상황과 프로시저 콜의 차이
  1. 프로세서는 프로시저 콜을 사용해서 핸들러로 분기하기 전에 스택에 return address를 push. 주소는 예외 종류에 따라 현재 인스트럭션 or 다음 인스트럭션
  2. 프로세서는 핸들러가 리턴할 때 스택 상에 추가적인 프로세서 상태를 push
  3. 제어가 사용자 프로그램에서 커널로 전환될 때, 모든 아이템은 커널 스택 상에 push
  4. 예외 핸들러는 커널 모드에서 돌아가며, 모든 시스템 자원에 접근 가능

예외 종류

  • Async: 외부의 입출력 디바이스 내 이벤트로 발생 (Interrupt)
  • Sync: 인스트럭션을 실행한 결과로 발생 (Trap, Fault, Abort)
Interrupt (Async)
  • 프로세서 외부에 있는 입출력 디바이스에게 온 시그널의 결과로 발생
  • 입출력 디바이스는 프로세서 칩의 핀에 시그널을 보내서 인터럽트를 발생시키고, 디바이스를 식별하는 예외번호를 시스템 버스에 보냄
  • 프로세서는 현재 인스트럭션의 실행을 완료한 후에, 인터럽트 핀의 시그널을 발견하고 시스템 버스에서 예외번호를 읽어들이고, 적절한 인터럽트 핸들러를 호출
  • 핸들러가 리턴할 때, 제어를 다음 인스트럭션으로 돌려줌. 프로그램은 인터럽트가 발생하지 않은 것처럼 계속해서 실행될 것
Trap (Sync)
  • 의도적인 예외 상황, 특정 인스트럭션을 실행한 결과로 발생
  • 트랩 핸들러는 인터럽트 핸들러와 마찬가지로 제어를 다음 인스트럭션으로 돌려줌
  • 가장 중요한 사용은 syscall과 유사한 인터페이스를 제공하는 것 (커널 서비스 이용)
  • syscall 인스트럭션을 실행하면 트랩이 인자들을 해독하고 적절한 커널 루틴을 호출하는 예외 핸들러로 이동시킴
Fault (Sync)
  • 핸들러가 복구할 가능성이 있는 에러 조건에서 발생
  • Fault가 발생하면 프로세서는 제어를 Fault 핸들러로 이동
  • 에러 조건을 정정하면 제어를 Fault가 발생한 인스트럭션으로 돌려줌
  • 그렇지 못하면, 핸들러는 커널 내부의 Abort 루틴으로 리턴해서 응용 프로그램 종료
Abort (Sync)
  • 복구할 수 없는 치명적인 에러에서 발생
  • Abort 핸들러는 절대로 응용 프로그램으로 제어를 리턴하지 않으며, 응용 프로그램을 종료하는 루틴으로 넘겨줌

리눅스 / x86-64 시스템의 예외 상황

  • Exception Number 0: Divide Error (Fault)
  • Exception Number 13: General Protection Fault (Fault)
  • Exception Number 14: Page Fault (Fault)
  • Exception Number 18: Machine Check (Fault)
  • Exception Number 32-255: OS-defined Exceptions (Interrupt or Trap)

시그널 (Signal)

시그널 전송 (Sending Signals)
  • 커널은 프로세스의 컨텍스트 내에 있는 일부 상태를 갱신해서 시그널을 목적지 프로세스로 보냄
  • 다음 2가지 이유 중 하나로 전송됨
    1. 0으로 나누기나 자식 프로세스의 종료 같은 시스템 이벤트
    2. 어떤 프로세스가 커널에 명시적으로 시그널을 목적 프로세스에 보낼 것을 요구하기 위해 kill 함수 호출
✔ 프로세스 그룹
  • 모든 프로세스는 항상 한 개의 프로세스 그룹에 속하며, 양수 프로세스 그룹 ID로 식별
  • getpgrp 함수를 호출해서 현재 프로세스의 process group ID를 얻을 수 있음
  • setpgid 함수를 호출해서 프로세스 pid의 프로세스 그룹을 pgid로 변경
✔ 시그널 보내는 방법
  1. /bin/kill 프로그램 사용해서 보내기
  2. kill 함수로 시그널 보내기
  3. alarm 함수로 시그널 보내기
시그널 수신 (Receiving Signals)
  • 전송된 시그널에 대해 반응해야 할 때 목적지 프로세스는 시그널을 받음
  • 프로세스는 시그널 핸들러를 실행해서 시그널을 무시하거나, 종료하거나, 획득 가능
✔ 펜딩 시그널 (Pending Signal)
  • 전송했지만 아직 수신되지 않은 시그널
  • 펜딩 시그널은 특정 타입에 대해 최대 1개만 존재할 수 있음
  • 어떤 프로세스가 특정 타입의 펜딩 시그널을 가지고 있으면 다음에 발생하는 같은 타입의 시그널은 큐에 들어가지 않음


  • 커널이 프로세스를 커널 모드에서 사용자 모드로 전환할 때, 커널은 해당 프로세스의 pending & ~blocked 집합을 체크
  • 이 집합이 비어있으면, 커널은 제어를 해당 프로세스의 논리 제어흐름 내의 다음 인스트럭션으로 전달
  • 이 집합이 비어있지 않다면, 커널은 집합 내에서 시그널을 선택해서 프로세스가 이 시그널을 수신하게 함
  • 시그널을 수신한 프로세스는 해당 시그널에 맞는 동작을 함
  • 해당 동작이 끝나면, 제어는 p의 논리 제어흐름 내의 다음 인스트럭션으로 돌아감
✔ signal 함수
sighandler_t signal(int signum, sighandler_t handler);
  • handler가 SIG_IGN: signum 타입의 시그널을 무시
  • handler가 SIG_DFL: signum 타입의 시그널에 대한 동작을 기본 동작으로 함
  • 그 외의 handler: 프로세스가 signum 타입의 시그널을 수신할 때마다 handler가 호출. 이는 signal handler라고 부르는 사용자 함수 주소
시그널 블록 (Signal Block)
  1. 묵시적 블록 방법: 커널은 핸들러에 의해 처리되고 있는 모든 대기 시그널의 처리를 막음
  2. 명시적 블록 방법 (함수 사용)
    • sigprocmask: 현재 블록된 시그널의 집합을 변경. 함수의 동작은 how 인자의 값에 따라 다름
      • SIG_BLOCK: set에 있는 시그널들을 blocked에 추가
      • SIG_UNBLOCK: set에 있는 시그널들을 blocked에서 제거
      • SIG_SETMASK: oldset이 NULL이 아니면 blocked 비트 벡터의 이전 값이 oldset에 저장됨
    • sigemptyset: set을 빈 집합으로 초기화
    • sigfillset: 모든 시그널을 set에 추가
    • sigaddset: signum을 set에 추가
    • sigdelset: signum을 set에서 제거
    • sigismember: signum이 set의 멤버인지 확인
시그널 핸들러 작성

⭐️ 시그널 핸들러를 다루는 것이 어려운 이유!!

  • 핸들러는 메인 프로그램과 동시에 돌아가고, 같은 전역변수를 공유
  • 시그널의 수신이 언제될 수 있는지 종종 직관적이지 않다.
  • 다른 시스템은 다른 시그널 처리 방식을 가짐
✔ 안전한 시그널의 처리
  1. 핸들러는 가능한 한 간단하게 유지하라.
  2. 핸들러에서 비동기성-시그널-안전한 함수(Async-Signal-Safe Function)만 호출하라.
  3. errno를 저장하고 복원하라.
  4. 모든 시그널을 블록시켜서 공유된 전역 자료구조들로의 접근을 보호하라.
  5. 전역변수들을 volatile로 선언하라.
  6. sig_atomic_t로 플래그들을 선언하라.