CPU Scheduler

스케줄링의 대상은 Ready Queue에 있는 프로세스들이다. 즉 CPU의 할당에 대한 스케줄링을 진행한다.

선점형(Preemptive) & 비선점형(Non-preemptive) 스케줄러

선점형(Preemptive) 스케줄러

하나의 프로세스가 다른 프로세스 대신에 CPU를 차지할 수 있다. 즉, 이전에 CPU를 할당받아 사용 중인 프로세스가 존재하더라도 특정 조건에 충족한다면 다른 프로세스가 도중에 CPU를 뺏을 수 있다.

• SRTF (Shortest Remaining Time First)
• Priority Scheduling
• RR (Round Robin)

비선점형(Non-preemptive) 스케줄러

하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없다. 즉, 이전에 CPU를 할당받아 사용 중인 프로세스가 존재할 경우, 그 프로세스가 종료될 때까지 기다려야 한다.

• FCFS (First Come First Served)
• SJF (Shortest Job First)
• Priority Scheduling

FCFS (First Come First Served)

• 먼저 온 순서대로 프로세스를 스케줄링한다.
• 비선점형 스케줄링이다.

문제점

• convoy effect
  - 소요 시간이 긴 프로세스가 먼저 도착하여 시간을 잡아먹고 있는 부정적인 현상

SJF (Shortest Job First)

• 다른 프로세스가 먼저 도착했더라도 CPU burst time이 짧은 프로세스에게 CPU를 선 할당한다.
• 비선점형 스케줄링이다.

문제점

• Starvation
  - 어떠한 우선 순위로 작업을 처리할 때 우선순위가 낮은 작업이 영원히 처리되지 않는 현상

SRTF (Shortest Remaining Time First)

• 새로운 프로세스가 도착할때마다 새로운 스케줄링이 이뤄진다.
• 선점형 스케줄링이다.
  - 현재 수행중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 가진 새로운 프로세스가 도착하면 CPU를 넘긴다.

문제점

• Starvation
  - 어떠한 우선 순위로 작업을 처리할 때 우선순위가 낮은 작업이 영원히 처리되지 않는 현상
• 새로운 프로세스가 도착할 때마다 스케줄링을 다시 진행하기 때문에 CPU burst time(CPU 사용 시간)을 측정할 수 없다.

Priority Scheduling

• 우선순위가 가능 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선순위는 정수로 제공되고 수가 낮을수록 우선순위가 높게 책정된다.
• 선점형 스케줄링 방식
  - 더 높은 우선순위의 프로세스가 도착하면 실행 중인 프로세스를 멈추고 CPU를 선점한다.
• 비선점형 스케줄링 방식
  - 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다. (바로 다음에 실행할 프로세스로 스케줄링된다.)

문제점

• Starvation
  - 어떠한 우선 순위로 작업을 처리할 때 우선순위가 낮은 작업이 영원히 처리되지 않는 현상
• Indefinite blocking (무기한 봉쇄)
  - 실행 준비는 되었지만 CPU를 사용하지 못하는 프로세스를 CPu가 무기한으로 대기하는 상태

해결책

• Aging
  - 우선순위가 낮은 프로세스가 오래 대기했을 경우, 우선순위를 높여주는 방식

RR (Round Robin)

• 현대적인 CPU 스케줄링이다.
• 각 프로세스는 동일한 크기의 할당 시간(Time quantum)을 가지게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 Ready Queue의 가장 뒤에 다시 들어간다.
• CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다.
• 프로세스의 Context를 저장할 수 있기 때문에 가능하다.

장점

• Response Time이 빠르다.
  - n개의 프로세스가 Ready Queue에 있고 할당 시간이 q로 주어질 경우, 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻게 된다. 이는 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다는 의미이다.
• 프로세스가 기다리는 시간이 CPU를 사용할만큼 증가한다.
  - Fairness가 보장됨을 의미한다.

주의할 점

• 설정한 Time quantum이 너무 커지면 FCFS와 같아지고, 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 너무 잦은 Context Swtich로 인한 Overhead가 발생하기 때문에 적절한 Time quantum을 설정할 필요가 있다.