운영체제 - CPU 스케줄링

어떤 프로그램이 실행 된다는 것은 CPU burst와 I/O burst를 반복하며 실행된다는 뜻.

CPU 스케줄링

: 어떤 프로세스에게 CPU를 줄 것인지를 결정 (누구한테 줄 것인가? 언제 뺏을 것인가?)

선점 / 비선점 스케줄링

• 선점(preemptive) : 강제로 회수
  ex) timer interrupt, I/O 완료 후 interrupt
• 비선점(nonpreemptive) : 자진 반납
  ex) I/O 시스템 콜, Terminate

스케줄링 척도(Criteria)

• CPU utilization (이용률)
  : 전체 시간 중에서 CPU가 사용된 시간의 비율 (시스템 입장)
• Throughput (처리량)
  : 주어진 시간 동안에 몇개의 작업을 수행했는가 (시스템 입장)
• Turnaround time (소요시간)
  : 실행시간과 대기시간을 합한 시간
• Waiting time (대기 시간)
  : 대기시간의 총합 (preemptive 스케줄링의 경우, 대기를 여러번 할 수 있음)
• Response time (응답 시간)
  : CPU를 처음 얻기까지 걸린 시간

스케줄링 알고리즘

• FCFS(First-Come First-Served)
  • 큐에 도착한 순서대로 CPU 할당
  • nonpreemptive
  • 실행시간이 짧은 프로세스가 나중에 배치되면 대기시간이 길어짐
• SJF(Shortest Job First)
  • 실행시간이 짧은 프로세스를 먼저 수행
  • nonpreemptive
  • 평균 대기시간 감소
  • 수행시간이 긴 프로세스는 CPU를 받지 못할수도 있음 (Starvation)
  • CPU 수행시간을 정확히 알 수 없음 (과거를 통해 예측은 가능)
• SRTF(Shortest Remaining Time First)
  • SJF의 preemptive 버전
  • 현재 수행중인 프로세스의 남은 시간보다 더 짧은 시간을 가지는 프로세스가 도착하면 CPU를 빼앗김
  • minimum average waiting time을 보장
• Priority Scheduling
  • 우선순위가 높은 프로세스에게 CPU를 할당
  • preemptive, nonpreemptive 두가지 버전 존재
  • SJF는 일종의 priority 스케줄링. Starvation 현상 발생 => Aging으로 해결 (오래 기다린 프로세스의 우선순위를 높임)
• Round Robin Scheduling
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  • preemptive
  • Response time이 작아짐
  • time quantum이 크면 FCFS와 같게 되고, 작으면 context switch 오버헤드가 커짐
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우
    => 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• Multilevel Queue
  • Ready queue를 여러 개로 분할
  • 각각의 큐는 우선순위를 가짐
• Multilevel Feedback Queue
  • 처음에는 우선순위가 가장 높은 큐에 배정
  • 해당 큐의 time quantum을 다 채운 프로세스는 그 다음 우선순위인 큐로 내려감