[운영체제] CPU 스케줄러(CPU Scheduler)

스케줄링 대상은 Ready Queue에 있는 프로세스들이다.

비선점형(Non-Preemptive) 스케줄링

한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스 종료까지 다른 프로세스가 CPU를 점유하지 못하는 것

FCFS(First Come First Served)

• 특징

  • 프로세스의 도착 순서대로 CPU를 할당

• 문제점

  • convoy effect
    • 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
  
  

SJF(Shortest Job First)

• 특징

  • 다른 프로세스가 먼저 도착했어도 CPU 작업 시간이 짧은 프로세스에 먼저 CPU를 할당

• 문제점

  • starvation
    • 사용 시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없다.

선점형(Preemptive) 스케줄링

프로세스가 정상적으로 수행중인 동안 다른 프로세스가 CPU를 점유할 수 있는 것

SRTF(Shortest Remaining Time First)

• 특징

  • 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.

• 문제점

  • starvation

  • 새로운 프로세스가 도달할 때마다 스케줄링을 다시 하기 때문에 CPU 작업 시간을 측정할 수가 없다.

    
    

Round Robin

• 특징

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다.
  • 할당 시간을 만족하면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 대기한다.

• 문제점

  • time quantum이 너무 커지면 FCFS와 같아지고, 너무 작아지면 잦은 컨텍스트 스위치로 오버헤드가 발생한다.

    
    

Multi-level Queue

• 특징

  • 프로세스를 그룹으로 나누어 각 그룹에 따라 Ready Queue를 여러 개 둔다. 각 큐마다 다른 규칠을 지정할 수 있다.
  • 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 선다.

• 문제점

  • starvation

    
    

Multi-level feedback Queue

• 특징

  • Multi-level Queue와 동일한 개념을 가지지만, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
  • 즉, starvation을 해결할 수 있다.
  
  
  

Priority: 우선순위가 높은 프로세스가 먼저 선택되는 스케줄링이다. 선점과 비선점 모두 가능하다. starvation 현상이 나타날 수 있다.