[OS] 5-2. 프로세스 스케줄링 알고리즘 - FCFS, RR

목차

1. 스케줄링의 목적
2. 스케줄링 기준 및 단계
3. 스케줄링 정책
4. 기본 스케줄링 알고리즘들
5. Case study

---

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)

BT예측문제를 개선한 방식

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

---

FCFS (First-Come-First-Service)

(프로세스 하나가 코어를 할당 받으면 계속 쓰겠다는 스케줄링)

• Non preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 도착 시간 (ready queue) 기준
  • 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능
• High resource utilization / why? => 불필요한 스케줄링 오버헤드가 없음, Cpu가 계속 일을 할 수 있다. 
• Batch system(일괄처리시스템)에 적합, interactive system (대화형 시스템) 에 부적합
• (일괄처리시스템은 순서대로 빨리 처리에 유리)
• 단점
  
  • Convoy effect : 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게되는 현상 대기시간 >> 실행 시간 (나의 작업은 2초면 끝나는데 내 앞에 처리하는 작업은 20초가 걸림 => 나는 22초 소요됨)
  • 긴 평균 응답시간 (response time) (작업을 지시했는데 언제 돌려받을지 예상이안됨)

Convoy effect와 비슷한 예

FCFS (First-Come First Service) 가 수행될 때

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기법: 기준이 서로 다를 때 동일한 기준으로 평가할 때 사용하는 기법, 클수록 내가써야하는 대비 대기 시간이 오래걸림)

P3,P4,P5가 수행되어야 하는데 P2때문에 오랜 시간동안 대기함. => Convoy effect

FCFS의 단점임.

---

RR (Round Robin)

• Preemptive scheduling
• 스케줄링 기준 (Criteria)
  
  • 도착 시간 (ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원 사용 제한 시간 (time quantum) 이 있음
  
  • System parameter (δ)
  • 프로세스는 할당된 시간이 지나면 자원 반납(Timer runout)
  • 특정 프로세스의 자원 독점 (monopoly) 방지
  • Context switch overhead 가 큼
• 대화형, 시분할 시스템에 적합

Time quantum (δ) 이 시스템성능을 결정하는 핵심 요소

• Very large (infinite) δ => FCFS
• Very small time quantum => processor sharing (=제한시간이 0에 수렴한다면)
  
  • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌
  • 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
• High context switch overhead (오버헤드가 엄청 클 것이다)

time quantum이 끝나면 맨 뒤에 가서 줄을 선다 (=ready)

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) = (𝟓+𝟏𝟖+𝟒+𝟏𝟓+𝟏𝟐) / 𝟓=𝟏𝟎.𝟖𝟎

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) = (𝟑+𝟏𝟗+𝟓+𝟏𝟒+𝟖) / 𝟓=𝟗.𝟖𝟎

time quantum에 따라서 성능의 변화가 있음을 알 수 있다.

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---