[CS] Process Scheduler #2

이 포스팅은 한국기술교육대학교 김덕수 교수님의 운영체제 강의를 참고하여 작성되었습니다.

 

기본 스케줄링 알고리즘

• 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

스케줄링 기준 : 도착 시간 (선착순)

자원을 효율적으로 사용 가능. Why? scheduling overhead가 적다

Batch system에 적합, interactive system에 부적합

단점

(1) Convoy effect : 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게되는 현상 (대기시간 >> 실행 시간)

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

 

 

 

RR (Round-Robin)

Preemptive scheduling

스케줄링 기준 : 도착 시간, 먼저 도착한 프로세스를 먼저 처리

자원 사용 제한 시간(time quantum)이 있음

- System parameter

- 프로세스는 할당된 시간이 지나면 자원 반납 / Time-runout

- 특정 프로세스의 자원 독점(monopoly) 방지

- Context switch overhead가 큼

대화형, 시분할 시스템에 적합

 

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

- Very large (infinite) > FCFS

- Very small time quantum > processor sharing

사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌 : 체감 프로세서 속도 = 실제 프로세서 성능의 1/n

High context switch overhead

 

 

 

 

 

긴 글 읽어주셔서 감사드립니다.

22.12.16