CPU Scheduling

• 컴퓨터는 한가지의 Process만 진행할 수 있지만, 여러가지의 Process를 받게되면 우선순위를 정하거나 컴퓨터 내의 알고리즘으로 순서를 대처해야함

• Preemptive

  • running state에서 ready state로 interrupt하는 경우
  • I/O or event completion에 의해 wating state에서 ready state로 이동하는 경우

• CPU Scheduling의 4가지 종류

  • FCFS(First-come, First-Served) : 먼저 들어운 순으로 running state ⇒ Queue 방식
    • Convoy effect 발생가능 : 진행시간이 짧은 Process앞에 진행시간이 긴 Process가 위치하게 되면 비효율적인 Process처리가 일어날 수 있음
  • SJF(Shortest-Job-First) : 짧은 시간의 Process를 먼저 진행 (우선순위 스케쥴링)
    • waiting time 관점에서 가장 Optimal한 방식
    • 두가지 방식이 존재(non-preemtive & preemtive 방식)
      • non-preemptive 방식 : 진행중인 Process와 무관하게 우선순위가 높은 Process가 등장하면 ready 큐에 위치
      • preemptive 방식 : 진행중인 Process보다 우선순위가 높은 Process가 등장 시에 진행중인 Process를 ready state로 interrupt 시키고 그 Process를 진행시킴
    • 문제점 : Starvation (우선순위가 낮은 Process는 실행이 아예 안될 수도 있음) ⇒ 우선순위가 높은 Process가 올수록 앞에 배치되기 때문에 우선순위가 낮은 Process는 계속 뒤로 밀리게 됨
    • Starvation의 해결방법은 Aging기법을 사용 : 시간이 지날수록 Process에 우선순위를 부여하여 우선순위를 증가시켜서 해결
  • RR(Round Robin)
    • time quantum을 두고 그 시간을 넘기면 큐 맨뒤로 보냄
    • SJF보다 높은 turnaround time을 갖지만 response time에서 높은 성능을 보임
  • Multilevel Queue
    • Foreground(interactive) → 바로 반응해야하는 Process를 Round Robin방식으로 처리
    • Background(batch) → FCFS방식으로 처리
    • 여러개의 큐를 사용하여 앞선 큐에서는 RR방식으로 중요도가 높은 Process를 처리하고 중요도가 낮은 Process는 FCFS방식으로 처리한다