Chapter 05. Process Scheduling (2of4) - FCFS, RR

목차

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

FCFS (First-Come-First-Service)

선착순 알고리즘

• Non-preemptive scheduling

• 스케줄링 기준 (Critia)

  • (ready queue에)도착시간

• 자원을 효율적으로 사용 가능 (High resource utilization)

  • why ?
  • 오는대로 그냥 무지성으로 넣어버려
    불필요한 스케줄링 안한다~
    = scheduling overhead가 낮다
    = CPU가 계쏙 일할 수 있다.

• Batch system에 적합, interactive system(대화형)에 부적합

• 단점

  • Convoy effect

    • (난 2초면 작업 끝나는데 앞에 줄이 너무길어....)
    • 대기시간 > 실행시간

  • 긴 평균 응답시간(response time)

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	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

Normalize : 정규화 = 기준을 동일 시 하는 것

NTT가 클 수록 불공평하다.

P2 때문에 뒤에 대기시간 길어짐

P3~P5 : convoy effect

RR (Round-Robin)

선착순 알고리즘

• Preemptive scheduling
• 스케줄링 기준 (Critia)
  • (ready queue에)도착시간
• ☆자원 사용 제한 시간(time quantum)이 있음☆
  • 제한 시간이 지나면 자원을 반납함
  • 장점 : 특정 프로세스의 자원독점(monopoly) 방지
  • 단점 : Context switch overhead가 큼
• 대화형, 시분할 시스템에 적합
• Time quantum(δ)(제한시간)이 시스템 성능을 결정하는 핵심요소
  • δ → 무한 => FCFS
  • δ → 0 => processor sharing (동시에 쓰는 느낌을 준다)
  • 체감 프로세서 속도 = 실제 프로세서 성능의 1/n

(예제 직접해보기)

δ=2

Process ID	Arrival time	Burst time (BT)	Wating time (WT)	Turnaround time (TT) = BT + WT	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) = (5+18+4+15+12) / 5 = 10.8

δ=3

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	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) = (3+19+5+14+8) / 5 = 9.8