프로세스 스케줄링 #2 - Basic Scheduling algorithms(FCFS, RR, SPN, SRTN, HRRN, MLQ, MFQ)

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)

 

FCFS (First-Come-First-Service)

• Non-preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 도착 시간 (ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능
  • High resource utilization 
  • 불필요한 스케줄링 오버헤드가 적고 프로세서 계속 사용가능
• Batch system에 적합, interactive system에 부적합
  • 순서보다는 퍼포먼스에 중점
• 단점
  • Convoy effect
    • 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기시간 >> 실행 시간)
  • 긴 평균 응답시간(response time)

Process ID	Arrival time	Burst time (BT)	Waiting time  (WT) = TT-BT	Turnaround time (TT)	Normalized TT  (NTT) = TT/BT
P1	0	3	0	3	3/3 = 1
P2	1	7	2	9	9/7 = 1.3
P3	3	2	7	9	9/2 = 4.5
P4	5	5	7	12	12/5 = 2.4
P5	6	3	11	14	14/3 = 4.7

• Normalized TT : 1이 가장 이상적
• P2로 인해서 P3, P4, P5의 대기시간이 길어짐 -> convoy effect

 

RR (Round-Robin)

• Preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 도착 시간 (ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원 사용 제한 시간(time quantum)이 있음
  • System parameter (δ)
  • 프로세스는 할당된 시간이 지나면 자원 반납
    • Timer-runout
  • 특정 프로세스의 자원 독점(monopoly) 방지
  • 일정 시간마다 계속 Context switch가 일어남 -> Context switch overhead가 큼
• 대화형, 시분할 시스템에 적합
• Time quantum (δ)이 시스템 성능을 결정하는 핵심 요소
  • Very large (infinite) δ -> FCFS
  • Very small time quantum -> processor sharing
    • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌
      • 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
    • High context switch overhead

 

RR (Round-Robin), δ = 2

Process ID	Arrival time	Burst time (BT)	Waiting time  (WT) = TT-BT	Turnaround time (TT)	Normalized TT  (NTT) = TT/BT
P1	0	3	2	5	5/3 = 1.7
P2	1	7	11	18	18/7 = 2.6
P3	3	2	2	4	4/2 = 2
P4	5	5	10	15	15/5 = 3
P5	6	3	9	12	12/3 = 4

Average response time(TT) = 10.8

 

 

RR (Round-Robin), δ = 3

Process ID	Arrival time	Burst time (BT)	Waiting time  (WT) = TT-BT	Turnaround time (TT)	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	3	5	5/2 = 2.5
P4	5	5	9	14	14/5 = 2.8
P5	6	3	5	8	8/3 = 2.7

Average response time(TT) = 9.8

 

 

SPN (Shortest-Process-Next)

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

Process ID	Arrival time	Burst time (BT)	Waiting time  (WT) = TT-BT	Turnaround time (TT)	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

 

SRTN (Shortest Remaining Time Next)

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

-> 구현 및 사용이 비현실적

 

 

HRRN (High-Response-Ratio-Next)

• SPN의 변형
  • Starvation 을 해결하기 위해 Wating Time을 고려
  • SPN + Aging concepts
  • Non-preemptive scheduling
• Aging concepts
  • 프로세스의 대기 시간(WT)을 고려하여 기회를 제공
• 스케줄링 기준 (Criteria)
  • Response ratio가 높은 프로세스 우선
• Response ratio = WT+BT / BT (응답률)
  • SPN의 장점 + Starvation 방지
  • 실행 시간 예측 기법 필요 (overhead)

Process ID	Arrival time	Burst time (BT)	Waiting time  (WT) = TT-BT	Turnaround time (TT)	Normalized TT  (NTT) = TT/BT
P1	0	3	0	3	3/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)

-> Fairness (공평성)

 

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

-> Efficiency/Performance (효율성, 성능)

 

• 실행시간 예측 부하를 해결하기 위한 방법
  • MLQ (Multi-level Queue)
  • MFQ (Multi-level Feedback Queue)

 

MLQ (Multi-level Queue)

• 작업 (or 우선순위)별 별도의 ready queue를 가짐
  • 최초 배정 된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기법 사용
• Queue 사이에는 우선순위 기반의 스케줄링 사용
  • E.g., fixed-priority preemptive scheduling
• 장점
  • 중요한 job(우선순위가 높다)을 빠르게 처리할 수 있다.
• 단점
  • 여러 개의 Queue 관리 등 스케줄링 overhead
  • 우선순위가 낮은 queue는 starvation 현상 발생 가능

 

MFQ (Multi-level Feedback Queue)

• 프로세스의 Queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보(패턴) 활용
• 특성
  • Dynamic priority
  • Preemptive scheduling
  • Favor short burst-time processes
  • Favor I/O bounded processes
  • Improve adaptability
• 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음
• 단점
  • 설계 및 구현이 복잡, 스케줄링 overhead가 큼
  • Starvation 문제 등
• 변형
  • 각 준비 큐마다 시간 할당량을 다르게 배정
    • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
  • 입출력 위주 프로세스들을 상위 단계의 큐로 이동, 우선 순위 높임
    • 프로세스가 block될 때 상위의 준비 큐로 진입하게 함
    • 시스템 전체의 평균 응답 시간 줄임, 입출력 작업 분산 시킴
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
    • 에이징 (aging) 기법
• Parameters for MFQ scheduling
  • Queue의 수
  • Queue별 스케줄링 알고리즘
  • 우선 순위 조정 기준
  • 최초 Queue 배정 방법
  • ...

 

 

 

강의

www.youtube.com/watch?v=r1JVA7yOPAM&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=9

www.youtube.com/watch?v=keY9Wi7scEs&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=10

www.youtube.com/watch?v=actKUqea6Xc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=11