[운영체제] 16. 최소작업 우선 스케줄링 (SJF 스케줄링) 알고리즘

운영체제의 스케줄링 알고리즘을 평가하기 위해서는 다음과 같은 특성을 충분히 이해해야 한다.

• 프로세서 사용률

프로세서를 항상 실행상태로 유지하여 유휴 상태가 되지 않도록 한다.

• 처리율

단위 시간당 완료하는 작업의 수가 많도록 하여 짧은 작업을 우선 처리하거나 인터럽트 없이 처리한다

• 반환 시간

작업이 메모리에 들어가기 까지 걸린 시간, 준비 큐에 머무르는 시간, 실행 시간, 입출력 시간 등 작업을 완료하는데 소요된 시간

• 대기 시간

프로세스가 실행이 되기 전 까지 대기되는 시간을 뜻한다.

• 반응 시간

작업을 요청한 시간부터 반응을 시작하는 시간까지의 간격

 

최소 작업 우선 스케줄링 (SJF 스케줄링)

 

최소작업 우선 스케줄링이란 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당하는 방법이다.

 

최소 작업 우선 스케줄링은 FIFO 스케줄링에서 실행 시간에 따른 할당 방식의 차이가 FIFO와 SJF의 차이점이라고 할 수 있다.

 

장점

• 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기 시간이 가장 짧다.

단점

• 초기의 긴 작업을 짧은 작업을 종료할 때 까지 대기시켜 기아가 발생한다.
• 기본적으로 짧은 작업이 항상 실행되도록 설정하므로 불공정한 작업을 실행한다.
• 실행 시간을 예측하기 어려워 실용적이지 못하다.

 

비선점 SJF 스케줄링의 실행

 

아래의 그림을 분석해보자. 시간에 따라 프로세스의 할당 방식 차이를 주의깊게 보자.

 

 

• p1은 전에 아무 프로세스가 없기 때문에 바로 실행한다.
• p1의 실행 시간이 1일때, 2일때, 3일때, 4일때 각각 p2, p3, p4, p5가 들어온다.
• 각각의 프로세스 실행 시간을 비교하여 가장 짧은 프로세스 p4를 인지하고 p4를 실행 시킨다.
• p4의 실행이 끝나고 나서 그 다음의 실행 시간이 짧은 p3를 실행시킨다.
• p3의 실행이 끝나고 그 다음 실행 시간이 짧은 p5를 실행 시킨다.
• p5의 실행이 끝나고 그 다음 실행 시간이 짧은 p2를 실행 시킨다.

 

위와 같은 과정을 거치면 반환 시간꽈 대기 시간을 계산할 수 있다.

 

 

반환 시간 = 간트 차드에 실행 순서에 따른 실행 시간 + 대기 시간

대기 시간 = 반환 시간 - 실행 시간

선점 SJF 스케줄링의 실행

 

선점 SJF 스케줄링은 실행중 실행 시간에 따라 다른 프로세스가 프로세서를 선점할 수 있게 한다.

 

선점 SJF 스케줄링

 

아까와 같이 분석을 해보자

 

• p1은 아무 프로세스가 없기 때문에 바로 실행된다.
• 시간이 흐르고 실행 시간이 1일때 p2가 들어오는데, p2의 실행 시간(28)보다 p1의 실행 시간(10-1=9)가 더 짧기 때문에 계속 진행한다.
• 또 시간이 흐르고 실행 시간 2일 때 p3가 들어오는데 p1의 실행 시간(10-2=8)보다 p3의 실행 시간(6)이 더 짧기 때문에 p1의 실행을 잠시 중단하고 p3를 실행시킨다.
• 시간이 흐르고 실행 시간 3일때 p4가 들어오는데 p3의 실행 시간(6-1=5)보다 p4의 실행 시간(4)가 더 짧기 때문에 p3를 잠시 중단시키고 p4를 실행 시킨다.
• 시간이 흐르고 실행 시간이 4일 때 p5가 들어오는데, p4의 실행 시간(4-1=3) 보다 p5의 실행 시간(14)이 길기 때문에 p4를 그대로 유지시킨다.
• 시간이 흐르고 실행 시간이 7일 때 p4의 실행을 끝내고 그 다음으로 짧은 p3를 실행시킨다.
• 이와 같은 과정을 반복한다..

 

선점 SJF 스케줄링또한 위와 같은 과정을 거치면 반환 시간과 대기 시간을 구할 수 있다.

하지만 반환 시간과 대기 시간을 구하기 위해서 고려해야 할 것들이 있다.

 

 

반환 시간 = 종료까지 걸린 시간 - 시작 시간(중복된 시간)

프로세스의 종료 시간까지 겹치는 시간을 제외한다.

대기 시간 = 반환 시간 - 시작 시간(중복 시간) || - 실행 시간

반환 시간에서 시작 시간과 실행 시간을 빼주는데 이또한 겹치는 시간을 제외한다.