[OS] 최단 작업 우선 스케줄링(SJF) 이란?

SJF(Shortest Job First) Scheduling ?

최단 작업 우선 스케줄링(Shortest Job First Scheduling)은 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식이며, CPU 스케줄링 알고리즘으로 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘이다.

 

SJF 특징

• 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 항상 양보하기 때문에 기아 상태가 발생할 수 있다.
  • 기아 상태(starvation) :  특정 프로세스의 우선 순위가 낮아, 원하는 자원을 할당 받지 못하는 상태
• 대기 상태(waiting)에 있는 프로세스의 요구시간에 대한 정확한 자료를 얻기 어렵다는 문제점이 존재한다.
• 단기 스케줄링 보다는 장기 스케줄링에 유리하다.
• 비선점 스케줄링 알고리즘이다.
• 실행 시간이 짧은 작업은 신속하게 처리할 수 있으므로 평균 대기 시간이 가장 짧다는 장점도 존재한다.

SJF 스케줄링 흐름

먼저 다음과 같이 실행되는 3개의 프로세스가 있다고 할 때, SJF 정책을 따르면 프로세스는 다음과 같이 실행될 수 있다.

(단, A,B,C 모두 도착 시간은 0 이라고 가정한다.)

• 0초에 도착한 B가 먼저 CPU를 할당하고 10만큼 일을 수행한다.
• 다음으로 0초에 도착한 C는 10만큼 기다린 후에 10만큼 일을 수행한다.
• 마지막으로 A가 20만큼 기다린 후에 100만큼 일을 수행한다.

위 그림을 토대로 반환 시간, 대기 시간을 구해보면 다음과 같다.

• 반환 시간(turnaround time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간 (완료 시간 - 도착 시간)
• 대기 시간(waiting time) : 프로세스가 준비 상태에서 대기한 시간 (시작 시간 - 도착 시간)

	대기 시간	반환 시간	도착 시간
A	20	120	0
B	0	10	0
C	10	20	0

위 표를 이용하여 평균 반환시간, 평균 대기시간을 구하면 다음과 같다.

• 평균 반환시간 : (120 + 10 + 20) / 3 = 50
• 평균 대기시간 : (20 + 0 + 10) / 3 = 10

하지만, 프로세스의 도착 시간이 다른 경우에 SJF 정책은 매우 비효율적인 스케줄링 기법이 될 수 있다.

먼저, 정책에 따라서 먼저 실행 된 프로세스는 중단할 수 없다고 가정하고 아래 예시를 살펴보자.

우선 A,B,C의 도착 시간은 다음과 같다.

• A는 0초에 도착한 프로세스이다.
• B,C는 10초에 도착한 프로세스이다.

위 그림의 경우를 가지고 SJF 정책을 따르면 프로세스는 다음과 같이 실행될 수 있다.

• 가장 먼저 0초에 도착한 A가 100만큼 일을 수행한다.
• 그 다음으로 B가 100만큼 기다린 후에 10만큼 일을 수행한다.
• 마지막으로 C가 110만큼 기다린 후에 10만큼 일을 수행한다.

위 그림을 토대로 반환 시간, 대기 시간을 구해보면 다음과 같다.

	대기 시간	반환 시간	도착 시간
A	0	100	0
B	90	100	10
C	100	110	10

위 표를 이용하여 평균 반환시간, 평균 대기시간을 구하면 다음과 같다.

• 평균 반환시간 : (100 + 100 + 110) / 3 = 103.3333
• 평균 대기시간 : (0 + 90 + 100) / 3 = 63.3333

 

이렇게 어떤 일이 현재 수행중인 일보다 짧아도 늦게 도착하는 경우, 해당 일이 CPU를 선점할 때까지 오랫동안 기다려야 하는 경우가 발생할 수 있다.

이러한 SJF의 단점을 보완하고자 Shortest Time-to-Completion First (STCF) 스케줄링 정책이 출현했다.

 

다음 글에서는 STCF에 대해서 포스팅 할 예정이다.

---

출처

• https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8B%A8_%EC%9E%91%EC%97%85_%EC%9A%B0%EC%84%A0_%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81