운영체제(7) - CPU 스케줄링

CPU 스케줄링

Preemptive vs Non-preemptive

Preemptive: 강제로 스케줄링 ex) 응급환자 Non-preemptive: 먼저 온 순서대로 스케줄링

스케줄링 기준

• CPU Utilization (CPU 이용률)
• Throughput (처리율)
• Turnaround time (반환시간)
• Waiting time (대기시간)
• Response time (응답시간)

CPU 스케줄링 알고리즘

First-Come, First-Served

• Nonpreemptive scheduling
• 간단하고 공정한 스케줄링 알고리즘
• 하지만 호위효과가 나타난다(먼저 들어온 프로그램의 실행을 기다리느라 뒤의 프로그램이 마치 호위무사처럼 대기하는 현상).

• Gantt Chart

  Process	Burst Time
  P1	24
  P2	3
  P3	3

• AWT = (0+24+27)/3 = 17

Shortest-Job-First

• Burst Time이 가장 작은 순서대로 스케줄링
• Optimal하긴 하지만 Burst Time을 예측하는 것이 현실적이지 않고 Overhead가 일어날 수 있다.
• Shortest-Remaining-Time-First (최소잔여시간 우선)이라고도 한다.

Priority Scheduling

• 우선순위가 높은 것부터 스케줄링
• time limit, memory requirement, i/o to CPU burst와 같은 내부적 요소나 사용료, 시의적 이유와 같은 외부적 요소로 우선순위가 결정될 수 있다.
• 시간이 지나도 자신의 차례가 돌아오지 않는 starvation 문제가 일어날 수 있다. 이는 오래 머물면 우선순위를 높여주는 againg으로 해결할 수 있다.

Round-Robin

• 정해진 시간만큼을 할당하는 스케줄링
• 시간을 무한대로 주면 FCFS와 같고 0에 가깝게 주면 context switching이 너무 많이 일어나 overhead가 일어날 수 있다.

Multilevel Queue Scheduling

• 프로세스를 여러 그룹으로 나눌 수 있다. ex) System processes, Interactive processes, Interactive editing processes, Batch processes, Student processes
• 각각의 Queue 에 절대적 우선순위 존재
• CPU time 을 각 Queue 에 차등배분
• 각 Queue 는 독립된 scheduling 정책

Multilevel Feedback Queue Scheduling

• 복수 개의 Queue
• 너무 많은 CPU time 사용 시 다른 Queue 로
• 기아 상태 우려 시 우선순위 높은 Queue 로