[CS] 스케줄링

1. 스케줄링의 목적

멀티프로그래밍 (Multi-programming)

• 여러 개의 프로세스가 시스템 내에 존재한다.
• 자원을 할당할 프로세스를 선택하는 것이 스케줄링 (Scheduling)
• 자원 관리
  • 시간 분할 (time sharing) 관리
    • 하나의 자원을 여러 스레드들이 번갈아가며 사용
    • ex) 프로세서 (Processor)
    • 프로세스 스케줄링 (Process Scheduling)
  • 공간 분할 (space sharing) 관리
    • 하나의 자원을 분할하여 동시에 사용
    • ex) 메모리 (Memory)
      ㅤ

스케줄링 (Scheduling)의 목적

• 시스템의 성능 (Performance) 향상
• 대표적 시스템 성능 지표 (index)
  • 응답 시간 (response time)
    • 작업 요청 (submission)으로부터 응답을 받을 때까지의 시간
  • 작업 처리량 (throughput)
    • 단위 시간 동안 완료된 작업의 수
  • 자원 활용도 (resource utilization)
    • 주어진 시간 (Tc) 동안 자원이 활용된 시간 (Tr)
    • Utilization = Tr / Tc
• 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택
  ㅤ

시스템 성능 지표들

• 평균 응답 시간 (mean response time)
  • 사용자 지향적. ex) Interactive, real-time system에서 중요한 지표.
• 처리량 (throughput)
  • 시스템 지향적. ex) batch system 등 일괄 처리 시스템에서 중요한 지표.
• 자원 활용도 (resource utilization)
• 공평성 (fairness)
  • ex) FIFO
• 실행 대기 방지
  • 무기한 대기 방지
• 예측 가능성 (predictability)
  • 적절한 시간 안에 응답을 보장하는가?
• 자원 할당의 공정성 보장
• 단위 시간 당 처리량 최대화
• 적절한 반환시간 보장
• 오버헤드 최소화
• 자원 사용의 균형 유지
• 반환시간과 자원의 활용 간에 균형 유지
• 우선순위
• 서비스 사용 기회 확대
• 서비스 수 감소 방지
  ㅤ

대기 시간, 응답 시간, 반환 시간

ㅤ ㅤ

2. 스케줄링 기준 및 단계

스케줄링 기준 (Criteria)

스케줄링 기법이 고려하는 항목들

• 프로세스의 특성
  • I/O-bounded or compute-bounded
• 시스템 특성
  • Batch system or interactive system
• 프로세스의 긴급성 (urgency)
  • Hard- or Soft- real time, non-real time systems
• 프로세스 우선 순위 (priority)
• 프로세스 총 실행 시간 (total service time)
  ㅤ

CPU burst vs I/O burst

• 프로세스 수행 = CPU 사용 + I/O 대기
• CPU burst: CPU 사용 시간
  • CPU burst time이 긴 경우를 compute bounded 프로세스라고 한다.
• I/O burst: I/O 대기 시간
  • I/O burst time이 긴 경우를 I/O bounded 프로세스라고 한다.
• Burst time은 스케줄링의 중요한 기준 중 하나
  ㅤ

스케줄링의 단계 (Level)

• 발생하는 빈도 및 할당 자원에 따른 구분.
• Long-term Scheduling
  • 장기 스케줄링
  • Job Scheduling
• Mid-term Scheduling
  • 중기 스케줄링
  • Memory allocation
• Short-term Scheduling
  • 단기 스케줄링
  • Process Scheduling
    ㅤ

Long-term Scheduling

• Job Scheduling
  • Job이 Kernel에 등록되면 프로세스가 된다.
  • 시스템에 제출할 (Kernel에 등록할) 작업 (Job) 결정
  • Admission Scheduling, High-level Scheduling
• 다중프로그래밍 정도 (degree) 조절
  • 시스템 내에 프로세스 수 조절
• I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야함
  • 두 프로세스를 적절히 섞어서 선택해야, 시스템이 효율적으로 돌아간다.
• 시분할 시스템에서는 모든 작업을 시스템에 등록
  ㅤ

Mid-term Scheduling

• 메모리 할당 결정 (memory allocation)
  • Intermediate-level scheduling
  • Swapping (swap-in/swap-out)
    ㅤ

Short-term Scheduling

• Process scheduling
  • Low-level scheduling
  • 프로세서를 할당할 프로세스를 결정
    • Process scheduler, dispatcher
• 가장 빈번하게 발생
  • Interrupt, block (I/O), time-out 등
  • 매우 빨라야한다.
    ㅤ
    ㅤ

3. 스케줄링 정책 (Policy)

• 선점 vs 비선점
  • Preemptive scheduling, Non-preemptive scheduling
• 우선순위
  • Priority
    ㅤ

Preemptive/Non-preemtive scheduling

• Non-preemtive scheduling (비선점 스케줄링)
  • 할당 받을 자원을 스스로 반납할 때까지 사용
    • ex) system call, I/O 등
  • 장점
    • Context switch overhead가 적다.
  • 단점
    • 잦은 우선순위 역전 (우선순위가 높은 프로세스를 실행하지 못하는 경우 발생), 평균 응답 시간 증가
• Preemptive scheduling (선점 스케줄링)
  • 타의에 의해 자원을 빼앗길 수 있음
    • ex) 할당 시간 종료, 우선 순위가 높은 프로세스 등장
  • Context switch overhead가 큼 (프로세스가 자주 바뀔 수 있다.)
  • Time-sharing system, real-time system 등에 적합.
    ㅤ

Priority (프로세스의 중요도)

• Static priority (정적 우선순위)
  • 프로세스 생성 시 결정된 priority가 유지됨
  • 구현이 쉽고, overhead가 적음
  • 시스템 환경 변화에 대한 대응이 어려움
• Dynamic priority (동적 우선순위)
  • 프로세스의 상태 변화에 따라 priority 변경
  • 구현이 복잡하고, priority를 재계산하므로 overhead가 큼
  • 시스템 환경 변화에 대한 유연한 대응 가능
    ㅤ
    ㅤ

[OS] Lecture 5. Process Scheduling (1/4) / 운영체제 강의