2 분 소요

기본 개념

  • 단일 처리기에서는 오직 하나의 프로세스만이 실행 가능하다.
  • 다중 프로그래밍의 목적은 CPU 사용률 최대화이다. => 스케쥴링 알고리즘이 중요해짐

CPU 입출력 버스트 사이클 (CPU I/O Burst Cycle)

  • 프로세스 실행은 CPU버스트, I/O 버스트가 번갈아가면서 사이클을 이룬다.

CPU 스케쥴러

  • 단기 스케쥴러라고도 한다.
  • 메모리 내의 프로세스를 CPU에 할당한다.

선점 스케쥴링 (Preemptive Scheduling)

  • 중간에 교체 가능 한 스케쥴링
  • Race condition이 발생 할 수 있다

디스패처 (Dispatcher)

  • CPU의 제어를 실행되는 프로세스에게 주는 모듈이다.
    • 문맥 교환, 사용자 모드 전환, 사용자 프로그램의 적절한 위치로 이동(jump)의 기능이 있다.
  • 모든 프로세스의 문맥 교환 시 실행된다.
    • 이 때의 지연을 dispatch latency라고 한다.

스케쥴링 기준

  • CPU 이용률 ↑
  • 처리량 ↑
    • 단위 시간 당 처리한 프로세스의 갯수
  • 총 처리 시간 ↓
  • 대기 시간 ↓
    • 준비 완료 큐에서의 총 대기시간
  • 응답 시간 ↓

스케쥴링 알고리즘

FCFS (First Come First Served)

  • 가장 빨리 온 프로세스가 가장 먼저 처리됨
  • convoy effect 발생 가능
    • 가장 많은 시간이 소요되는 프로세스가 맨 먼저 오게 돼 대기 시간이 많아진다.
  • 비선점형

SJF (Shortest Job First)

  • 가장 짧은 프로세스가 먼저 수행된다.
  • 장기 스케쥴링 시 주로 사용된다. (시간을 파악해야 하므로)
  • 비선점

SRJF (Shortest Remaining Job First)

  • SJF의 선점형

우선 순위

  • 우선 순위를 부여 해 높은 우선순위부터 실행한다.
  • 기아 상태, 무한 봉쇄의 가능성이 있다.
    • 시간이 지날 수록 우선순위를 높이는 Aging으로 해결 할 수 있다.
  • 선점형과 비선점형 둘 다 가능하다.

Round Robin

  • 동일한 시간만큼 프로세스를 번갈아가면서 실행한다.
  • 선점형
  • Time Slice가 너무 크면 FCFS와 다를 바가 없고, 너무 작으면 오버헤드가 커진다.

다단계 큐

  • Ready 큐를 여러 개 생성한다.
  • ex) foreground 큐, background 큐를 생성 해 foreground를 우선적으로 처리한다.
  • RR 사용 해 slice한다.
  • 비선점

다단계 피드백 큐

  • 프로세스가 CPU사이를 이동할 수 있다.

멀티 프로세서 스케쥴링

  • load sharing(부하 공유)가 중요하다.

  • 비대칭 다중처리
    • 주 서버와 보조서버를 둔다.
    • 주 서버는 시스템적인 처리를 한다. (스케쥴링 결정, I/O)
    • 보조 서버는 사용자 코드 처리를 한다.
  • 대칭 다중처리 (SMP, Symmetric Multiprocessing)
    • 각 처리기가 독자적으로 처리한다.

처리기 친화성 (Processor Affinity)

  • 한 처리기에서 다른 처리기로의 이주를 피한다.
  • Soft Affinity : 이주 가능
  • Hard Affinity : 이주 불가능

Load Balancing

  • SMP 시스템에서는 부하 분배가 균등해야 한다.
  • push 이주, pull 이주

다중코어 프로세서

  • 하나의 칩에 처리기가 여러 개 존재
  • 스케쥴링이 복잡해짐
  • 캐시 미스로 메모리 멈춤(stall) 발생 시 처리기 내부의 스레드를 통해 전환한다.
  • 거친(coarse-grained) 다중스레딩
    • 긴 지연 시간일 시 다중스레드 실행
  • 세밀한(fine-grained) 다중스레딩

실시간 CPU 스케쥴링

  • Soft 실시간 시스템
    • 데드라인이 X
  • Hard 실시간 시스템
    • 데드라인 O
  • 지연시간 최소화
    • 인터럽트 지연
    • 디스패치 지연

승인 제어(admission-control) 알고리즘

  • 마감 시간 이내에 완수 가능하다면 승인, 아니라면 거절

Rate Monotonic 알고리즘

  • 주기에 따라 우선순위 결정
  • 주기가 짧은게 우선
  • CPU 자원 최대화 불가능

Earliset Deadline First

  • 우선 순위 동적 부여
  • 마감 시간이 빠른게 우선

카테고리:

업데이트:

참고