Chapter 05. Process Scheduling (3of4) - SPN, SRTN, HRRN

목차

• 기본 스케줄링 알고리즘들
  • FCFS (First-Come-First-Service)
  • RR (Round-Robin)
  • SPN (Shortest-Process-Next)
  • SRTN (Shortest Remaining Time Next)
  • HRRN (High-Response-Ratio-Next)
  • MLQ (Multi-level Queue)
  • MFQ (Multi-level Feedback Queue)

SPN (Shortest-Process-Next)

• Non-preemptive scheduling

• 스케줄링 기준 (Critia)

  • 실행시간 (burst time 기준)
  • burst time이 가장 작은 프로세스를 먼저 처리
  • SJF (Shortest Job First) scheduling

• 장점

  • 평균 대기시간(WT) 최소화
  • 시스템 내 프로세스 수 최소화
    • 스케줄링 부하 감소, 메모리 절약 → 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답시간 제공

• 단점

  • Starvation (무한대기) 현상 발생 (기아현상)

    • BT가 긴 프로세스는 자원을 할당 받지 못 할 수 있음
      • 이걸 해결하기위한 방법 = Aging ex) HRRN

  • 정확한 실행시간을 알 수 없음

    • 실행시간 예측 기법이 필요

Process ID	Arrival time	Burst time (BT)	Wating time (WT)	Turnaround time (TT) = BT + WT	Normalized TT (NTT) = TT/BT
P1	0	3	0	3	3/3 = 1
P2	1	7	12	19	19/7=2.7
P3	3	2	0	2	2/2 = 1
P4	5	5	0	5	5/5 = 1
P5	6	3	4	7	7/3 = 2.3

P2 : Starvation 기아현상

SRTN (Shortest Remaining Time Next)

남은 시간 적은 애 먼저 처리

• SPN의 변형
• Preemptive scheduling
  • 잔여 실행시간 더 적은 프로세스가 ready 상태(등장)가 되면 선점됨
• 장점
  • SPN의 장점을 극대화
• 단점
  • 프로세스 생성 시, 총 실행시간(BT)을 예측해야됨
  • 잔여 실행을 계속 추적해야함 = overhead
  • Context switching overhead (선점이니까~)

→ 구현 및 사용이 비현실적

숙제야

Process ID	Arrival time	Burst time (BT)	Wating time (WT)	Turnaround time (TT) = BT + WT	Normalized TT (NTT) = TT/BT
P1	0	3
P2	1	7
P3	3	2
P4	5	5
P5	6	3

HRRN (High-Response-Ratio-Next)

노약자 배려

• SPN의 변형 (SPN의 단점 : 기아현상)
  • SPN + Aging conecepts, Non-preemptive scheduling
• Aging conecepts
  • (나이가 많은애를 배려하겠다)
  • 프로세스의 대기시간(WT)를 고려하여 기회를 제공
• 스케줄링 기준(Criteria)
  • Response ratio가 높은 프로세스 우선
• Response ratio (응답률) = (WT+BT) / BT
  • (BT대비 얼마나 기다렸는가)
  • SPN의 장점 + Starvation 방지
  • 실행 시간(BT)를 예측할 필요있음 (overhead)

Process ID	Arrival time	Burst time (BT)	Wating time (WT)	Turnaround time (TT) = BT + WT	Normalized TT (NTT) = TT/BT = Response ratio
P1	0	3	0	3	1
P2	1	7	2	9	9/7=1.29
P3	3	2	7	9	9/2=4.5
P4	5	5	10	15	15/5=3
P5	6	3	6	9	9/3=3

Basic Scheduling algorithms

• FCFS (First-Come-First-Service)
• RR (Round-Robin)

공평성

• SPN (Shortest-Process-Next)
• SRTN (Shortest Remaining Time Next
• HRRN (High-Response-Ratio-Next)

효율성, 성능
문제점 : 실행시간 예측 부하

​ ↓

• MLQ (Multi-level Queue)
• MFQ (Multi-level Feedback Queue)