[SJF]
최단 작업 우선(SJF)는 CPU 스케줄링에 사용 되는 알고리즘 이다. 스케줄링 알고리즘 중 최소 평균 대기 시간을 갖을 수 있는 장점이 있다. Greedy하게 접근하여 풀 수 있는 알고리즘이다. Greedy하지 않게 접근을 한다면, CPU의 갯수에 비례하여 N에 대하여 N!만큼의 경우가 존재하므로 NP이다.하지만 실제 OS에서는 하나의 프로세스가 얼만큼의 cpu-burst-time(수행시간)을 에측하기 힘든데, 이를 이용하기 위해서 정확한 실행시간을 예측할 수 있는 환경에서 사용하여야 한다.
[Terminology]
1. Burst Time(B.T,점유시간) = Completion Time (완료시간) - Waiting Time (기다린 시간)
실제 프로세스가 CPU를 점유하고 있는 시간
2. Turn around time(T.A.T,소요시간)=Waiting Time+Burst Time
프로세스 처리를 요청한 시간부터 끝나기 까지 걸린 시간이다.
3. Arrival Time (A.T,도착시간) = Completion Time (완료시간) - Turn Around Time (처리시간)
프로세스 요청하기 시작한 시간
4. Waiting Time (W.T,대기시간)= Turn Around Time – Burst Time
대기 시간
[ALGORITHM]
- Arival time에 따라 정렬한다.
- minimum Arrival time을 가지고 minimum Burst time을 가지는 프로세스를 선택한다.
- 프로세스 처리후, Arrival 프로세스 풀안에서(현재 처리할 수 있는 프로세스들중) 최소한의 Burst Time을 가지는 프로세스를 처리한다.
[why..?]
W.T는 T.A.T와 B.T에 종속적이다. 이때 프로세스의 B.T의 경우 어떤 순서로 프로세스를 읽든 항상,프로세스들의 B.T의 합은 변하지 않는다. 또한 T.A.T는 B.T에 의존적이다. 그렇다면 W.T를 줄이기 위한 방법은 무엇일까? 간단하게 생각해보면, B.T가 큰 프로세스를 처리하면, 다른 프로세스들의 W.T가 그만큼 늘어난다.
그러면서 자동적으로 현재 Pool에 있지 않은 프로세스들도 영향을 연쇄적으로 끼치게 된다. 즉 하나의 프로세스의 B.T로 인해서 생기는 W.T는 계속적으로 누적이되고 모든 프로세스(앞으로 처리해야할)에 영향을 끼치게 된다.
즉 그리디하게 접근이 가능하다.
