운영체제 강의 - scheduling

다중프로그래밍

• 여러개의 프로세스가 시스템 내 존재
• 자원을 할당 할 프로세스를 선택 해야 함 -> 스케줄링
• 자원 관리
  - 시간 분할 (time sharing) 관리 -> 프로세서 사용 시간을 프로세스들에게 분배
  - 공간 분할 (space sharing) 관리 -> 메모리
  

스케줄링의 목적

1. 시스템의 성능 향상
2. 대표적 시스템 성능 지표(index)
   • 응답시간 (response time): 작업 요청으로부터 응답을 받을때까지의 시간,
     ex) interactive system, real-time
   • 작업 처리량 (throughput): 단위 시간 동안 완료된 작업의 수
     ex) batch system
   • 자원 활용도 (resource utilization): 주어진 시간(Tc) 동안 자원이 활용된 시간(Tr)
     ex) 엄청 비싼 장비를 사용했을 때

목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

스케줄링 기준

• 스케줄링 기법이 고려하는 항목들
• 프로세스의 특성
  I/O-bounded or compute-bounded
• 시스템 특성
  Batch system or interactive system
• 프로세스의 긴급성
• 프로세스 우선순위
• 프로세스 총 실행 시간
• 등등
  

스케줄링의 단계(level)

Long-term scheduling

• Job scheduling
  시스템에 제출 할(kernel에 등록 할) 작업(Job) 결정
• 다중프로그래밍 정도(degree) 조절
  시스템 내에 프로세스 수 조절
• I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함
• 시분할 시스템에서는 모든 작업을 시스템에 등록(시간을 나누어 사용하기 때문에)

Mid-term sch.

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

Short-term sch.

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

스케줄링 정책(Policy)

• 선점 vs 비선점
  Preemptive scheduling, Non-preemptive scheduling

• 우선순위
  Priority

선점/비선점

선점: 누가 와서 내 것을 빼앗을 수 있다.
비선점: 뺏을 수 없다.

• 비선점
  - 할당 받은 자원을 스스로 반납할 때까지 사용
  ex) system call, I/O, Etc
  • 장점: Context switch overhead가 적음(한번 받으면 계속 사용할 수 있으니)
  • 단점: 잦은 우선순위 역전(우선순위 높은 애들을 먼저 처리 못함), 평균 응답 시간 증가
• 선점
  - 타의에 의해 자원을 빼앗길 수 있음
  ex) 할당 시간 종료, 우선순위가 높은 프로세스 등장
  - Context switch overhead가 큼(= overhead가 큼)
  • Time-sharing system, real-time system 등에 적합(= 응답성이 높음)

우선순위

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

Basic Scheduling algorithms

FCFS (First-Come-First-Service)

• Non-preemptive scheduling
• 스케줄링 기준 (Criteria)
  - 도착 시간 (ready queue 기준)
  - 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능
  - High resource utilization
  스케줄링에 대한 오버헤드가 적음(일찍 오는대로 주면 됨, CPU가 계속 일할 수 있음)
• Batch system에 적합, interactive system(대화형)에 부적합
• 단점
  - Convoy effect: 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간 >> 실행 시간)
  - 긴 평균 응답시간(response time)
  

RR (Round-Robin)

• preemptive sch.

• 스케줄링 기준 (Criteria)
  - 도착 시간 (ready queue 기준)
  - 먼저 도착한 프로세스를 먼저 처리

• 자원 사용 제한 시간(time quantum)이 있음
  - system parameter
  - 프로세스는 할당된 시간이 지나면 자원 반납
  Timer-runout
  - 특정 프로세스의 자원 독점 방지
  - Context switch overhead가 큼

• 대화형, 시분할 시스템에 적합

• Time quantum이 시스템 성능을 결정하는 핵심 요소, 이 값에 따라 평균 응답 시간이 달라짐
  - Very large (infinite) -> FCFS
  - Very small time quantum -> processor sharing
  : 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌, 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
  : High context switch overhead