운영체제 CPU 스케줄러 - mapc-team/document GitHub Wiki

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

FCFS(First Come First Served)

특징

• 먼저 온 순서대로 처리
• 비선점형(Non-Preemptive)스케줄링
• 일단 CPU를 잡으면 CPU burst가 완료될 때까지 반환하지 않음. 할단되었던 CPU가 반환 되었을 때에만 스케줄링이 이루어짐

문제점

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

SJF(Shortest Job First)

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 선 할당
• 비선점형(Non-Preemptive)스케줄링

문제점

• Starvation: CPU 사용시간이 긴 프로세스는 거의 영원히 CPU를 할당 받지 못할 수 있다.

SRTF(Shortest Remaining Time First)

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형(Preemptive)스케줄링
• 현재 수행중인 프로세스의 burst time보다 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏긴다.

문제점

• Starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링.
• 우선순위는 정수로 표현하고, 작은 숫자가 우선순위가 높다.
• 선점형(Preemptive) 스케줄링 방식: 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다.
• 비선점형(Non-Preemptive) 스케줄링 방식: 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.

문제점

• Starvation
• 무기한 봉쇄(Indefinite blocking): 실행준비는 되어있으나 CPU를 사용못하는 프로세스를 CPU가 무한 대기하는 상태

해결책

• aging: 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여줌

Round Robin

특징

• 각 프로세스는 동일한 크기의 할당시간(time quantum)을 갖게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
• RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다.

장점

• Response time이 빨라진다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다. (공정한 스케줄링)

주의할 점

• time quantum이 너무 커지면 FCFS와 같아진다.
• time quantum이 너무 작으면 잦은 context switching으로 인해 overhead가 발생한다.