운영체제: CPU 스케줄링 알고리즘

 

CPU 스케줄러 결정 

1번과 4번 비선점형 스케줄링,  그외 나머지 선점형 스케줄링

1. 비선정형 방식

어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

 

비선점형 스케줄링의 종류

FCFS

가장 먼저 온 것을 가장 먼지 처리하는 스케줄링 방법

• 한 번 실행되면 그 프로세스가 끝나야지 다음 프로세스 실행 가능하다.
• 작성이 간단하고 이해하기 쉽다.
• Convoy Effect(호위 효과)가 발생할 수 있다. 

SJF

CPU를 가장 짧은 실행 시간을 가진 프로세스에 먼저 처리하는 스케줄링 방법

• 평균 대기 시간이 짧다.
• 긴 시간을 가진 프로세스가 실행되지 않는 현상 발생할 수 있다.

우선순위

프로세스에게 우선순위를 부여하고, 높은 우선순위를 가진 프로세스가 먼저 실행

• 낮은 우선순위 프로세스가 무한정 기다리는 문제가 발생할 수 있다.
  이를 해결하기 위해 우선순위를 일정 시간마다 증가시키는 우선순위 높이는 방법(Aging 기법)이 사용된다.

2. 선정형 방식

프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺐을 수 있는 방식

 

 

비선점형 스케줄링의 종류

라운드 로빈

모든 프로세스가 동일한 시간 할당량(Time Quantum) 동안 실행되며, 시간 할당이 끝나면 큐의 끝으로 이동시키는 방법

• 할당 시간 내에 처리를 완료하지 못하면 다음 프로세스로 넘어가므로 선점형 방식이다.
• n개의 프로세스가 있을 때 할당 시간을 q로 설정하면, 어떤 프로세스도 (n-1)q 시간 이상을 기다리지 않아도 된다.
• 응답 시간을 빠르게 할 수 있다는 장점이 있다.

 

SRF

중간에 실행 시간이 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행

• SJF의 선점형 버전

다단계

프로세스들을 여러 개의 큐로 분류하고 각 큐에 우선순위를 부여하는 방법

• 각 큐 사이에서 프로세스들이 이동할 수 없다. -> 유연성 떨어짐
• 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아(Starvation)현상이 나타날 수이다.