CPU scheduler

Ready queue에 있는 프로세스들 중 CPU core를 할당할 프로세스를 정하는 것이 CPU scheduler 다.

• CPU scheduling은 우선 순위에 근거하여 CPU 할당 및 재할당한다.

Preemptive and Nonpreemptive scheduling

• non-preemptive : I/O or event wait과 exit만 일어나는 것

• preemptive : 모든 과정이 다 일어나는 것

Dispatcher

Scheduler는 CPU를 할당하는 프로세스를 정하는 것이고 Dispatcher는 실제로 CPU를 제공하는 것이다.

Scheduling Criteria

• CPU utilization - CPU 활용도

• Throughput - 시간당 처리된 프로세스의 양

• Response time - 첫 번째 응답까지 걸리는 시간

• Turnaround time - 전체 과정이 끝나는 시간

• waiting time - ready queue에서 기다린 시간

Scheduling algorithm

• **FCFS(first-come First-served)

  • non-preemptive

  • Convoy effect - 긴 프로세스 뒤에 짧은 프로세스

    

• SJF(Shortest-Job-First)

  • Starvation - 낮은 우선 순위 프로세스들은 실행될 일이 없는 문제

  • non-preemptive
    
    average waiting time = (0+6+3+7)/4 = 4

  • preemptive
    

  • Shortest-remaining-time-first

• Detemining length of next CPU burst

  • Statice technique - 타입에 따라 burst time을 예측하는 기술

  • Dynamic technique - 평균에 기반하는 기술, simple average와 exponential average가 있다.

• RR(Round robin)

  • 프로세스마다 CPU 타임이 주어지는데 시간이 끝나면 다시 ready queue 마지막에 추가된다.

  • preemptive algorithm

  • time sharing system

  • response time이 제일 좋음

  • waiting time이 좋음

  • 프로세스는 (n-1)q 시간을 넘기지 않게 기다린다. (q는 time quantum)

  

• Priority scheduling

  • SJF의 문제점 starvation의 solution aging, 시간이 지날 수록 우선 순위를 올리는 방식
    

• Priority scheduling with Round-Robin

  • 우선 순위가 높은 것을 먼저 처리하지만 우선 순위가 같은 프로세스들은 Round-Robin 알고리즘을 사용하는 방식

Multilevel queue scheduling

• Prioritization based upon process type
  
• foreground (interactive) - RR 80%
• background (batch) - FCFS 20%

Multileve feedback queue scheduling

• adaptive하게 다양한 queue를 찾아감