CPU Scheduling

성능 척도

• CPU utilization(이용률)

• throughput(처리량)

• turnaround time(소요시간,반환시간)

• waiting time(대기 시간)

• response time(응답 시간)

CPU Scheduler & Dispatcher'

• CPU Scheduler
  -Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

• Dispatcher
  -CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
  -이 과정을 context switch(문맥 교환)라고 한다
  

• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다
  1.Runnung -> Blocked
  2.Runnung -> Ready
  3.Blocked -> Ready
  4.Terminate

nonpreemptive(비선점형) : 강제로 뺴앗지 않음
preemptive(선점형) : 강제로 빼앗음

FCFS(First-Come First-Served)

선입 선출

SJF(Shortest-Job-First)

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• nonpreemptive
  -일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemptive) 당하지 않음
• preemptive
  -현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  -이 방법을 Shortest-Remaining-Time-Fist(SRTF)이라고도 부른다
  
• SJF is optimal
  -주어진 프로세스들에 대해 minimum average waiting time을 보장
  

Round Robin(RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐

• 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다

• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPUㅏ 시간의 1/n을 얻는다