[OS] 6. Process Scheduling 3

이전의 FCFS, RR은 공평성에 초점을 두고 봤으나 이번에는 시스템적으로 효율성/성능에 초점을 둔 방법들을 보자. 

SPN (Shortest-Process-Next)

• Non-preemptive scheduling
• 스케줄링 기준
  • 실행시간 (burst time 기준)
  • Burst time이 가장 작은 프로세스를 먼저 처리해준다. (즉, 일찍 끝나는 것 부터 먼저 처리)
    • SJF(Shortest Job First) scheduling
• 장점
  • 평균 대기시간(WT: Waiting Time)을 최소화 할 수 있다. 
  • 시스템 내 프로세스 수 최소화 
    • 스케줄링 부하 감소, 메모리 절약 >> 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답 시간 제공 
• 단점
  • Starvation(무한대기) 현상 발생
    • BT가 긴 프로세스는 계속 자원을 할당 받지 못할 수 있다. 
      • Aging등 으로 해결 가능(ex. HRRN)
  • 정확한 실행시간(BT) 을 알 수 없음 
    • 실행시간 예측 기법이 필요하다

 

SRTN (Shortest Remaining Time Next) 

• SPN의 변형 
• Preemptive scheduling
  
  • 잔여 시간(RT: Remaining Time)이 더 작은 프로세스가 ready 상태 중에 있다면 선점하게 된다. 
• 장점
  • SPN의 장점을 극대화 할 수 있다. 
• 단점
  • 프로세스 생성시, 총 실행 시간 예측이 필요하다
  • 프로세스의 잔여 실행 시간을 계속 추적해야한다 (= overhead 발생)
  • Context switching overhead 발생 

사실 이 방법은 보기만 했을 때 굉장이 이상적이어 보인다. 그래서 그런지 이 방법은 구현 및 사용이 비현실적이라고 한다. 예측 및 추적해야하는 요소들이 많고, context switch 비용까지 많이 들어가니 실 구현이 어렵지 않나 싶다. 

 

 

 

HRRN (High-Response-Ratio-Next)

• 이 또한 SPN의 변형 (SPN + Aging concepts)
• Non-preemptive scheduling
• Aging Concepts
  • 프로세스의 대기 시간(WT: Wating Time)을 고려하여 기회를 제공한다 
• 스케줄링 기준 
  • Response ratio가 높은 프로세스 우선
• Response ratio(응답률) = (WT + BT) / BT
  • SPN의 장점 + Starvation 방지
    • WT가 늘어남에 따라, 즉 오래 기다릴 수록 응답률이 올라가서 우선 순위 또한 올라가게 된다. 
  • 실행 시간 예측 기법이 여전히 필요하다 (= overhead)