[OS] CPU scheduling 알고리즘

1. FCFS(First Come First Served) 스케줄링

요청한 순서대로 프로세스에게 cpu를 할당해준다. 비선점 방식이다.

 

다음과 같이 프로세스들이 요청을 했다고 하자.

다음과 같은 순서대로 실행될 것이다.

이 방식은 수행 시간이 큰 프로세스가 모두 수행되는 동안 다른 프로세스가 기다려야 한다는 단점이 존재한다.

 

2. SJF(Shortest Job First) 스케줄링

SJF 알고리즘은 cpu 수행 시간이 짧은 프로세스부터 cpu를 할당해주는 방식이다. (수행 시간이 같으면 요청한 순서대로)

 

비선점 방식이다.

 

다음과 같이 프로세스의 요청이 동시에 들어왔다고 하자.

수행 시간이 짧은 프로세스부터 실행하기 때문에 아래와 같이 실행될 것이다.

평균 대기 시간이 짧다는 장점이 있다.

 

3. SRTF(Shortest Remaining Time First) 스케줄링

SRTF 방식은 선점 SJF 방식이라고도 한다.

 

SJF 방식을 사용하는데 비선점이 아닌 선점 방식을 사용한다.

 

선점 방식은 우선적으로 실행해야하는 프로세스가 있다면 기존 실행중이던 프로세스를 밀어내고 자신이 먼저 실행한다.

 

새로운 프로세스의 요청이 들어오면 기존에 실행 중이던 프로세스의 남은 수행 시간과 새로운 프로세스의 수행 시간을 비교하여 더 짧은 쪽이 먼저 실행한다.

 

다음과 같이 프로세스 요청이 들어왔다고 하자.

선점 방식이기 때문에 다음과 같은 순서로 실행될 것이다.

P3가 도착했을 때는 P3가 가장 남은 수행 시간이 길기 때문에 가장 나중에 실행된다.

 

4. 우선순위 스케줄링

프로세스의 우선순위 순서대로 cpu를 할당해준다. (우선순위가 같으면 요청한 순서대로)

 

SJF도 일종의 우선순위 스케줄링으로 볼 수 있다

 

다음과 같이 프로세스의 요청이 들어왔다고 하자.

 

 

 

다음과 같은 순서대로 실행될 것이다.

이 방식의 단점은 영구 대기(infinite blocking) 현상이 발생할 수 있다는 점이다.

 

먼저 요청이 들어온 프로세스보다 우선 순위가 높은 프로세스만 들어온다면 계속 기다리기만 할 것이다.

 

이 문제를 해결하기 위해 시간이 지날수록 대기하는 프로세스의 우선순위를 높여주는 방식이 있다.

 

5. 라운드 로빈 (Round Robin) 스케줄링

time quantum을 정해두고 이 시간이 지나면 다음 프로세스에게 cpu 할당을 해주는 방식이다.

 

예를 들어 time quantum이 3ms이고 다음과 같이 프로세스 요청이 들어왔다고 하자.

다음과 같은 순서대로 실행될 것이다.

라운드 로빈 스케줄링에서는 적절한 time quantum을 정하는 것이 중요하다.

 

너무 작으면 context switching이 많이 일어나게 되고 너무 크면 FCFS 방식과 다를게 없기 때문이다.