백준알고리즘 11399번을 풀다가 생각난김에 머리 속에 있던 내용들을 정리하려고 한다.
SJF(Shortest Job First)란 CPU가 scheduling을 할때 실행시간이 짧은 프로세스부터 우선순위로 처리하는 방식으로, 가장 최적의 평균 대기시간을 제공하는 방식이다. 하지만 SJF는 실제로 적용되기 어려운 점이 있다. 프로세스마다 얼마나 CPU를 이용해야하는지 돌리기 전에는 알 방법이 없기 때문이다. 그래서 계산을 통한 예측으로 시간을 판단한다.
예를들면 다음과 같다.
프로세스 p1, p2, p3, p4가 각각 실행시간 5, 7, 2, 4의 실행시간을 갖고 CPU를 점유하기를 대기하고 있을 떄 전체 대기 시간의 합이 최소가 되기 위해서는 p3-> p4-> p1-> p2 순서대로 처리가 되어져야한다.
대기시간과 처리시간을 계산해보면 다음과 같다.
p3: (0 + 2) = 2
p4: ((0 + 2) + 4) = 6
p1: ((0 + 2 + 4) + 5) = 11
p3: ((0 + 2 + 4 + 5) + 7) = 18
전체 프로세스들의 평균 대기시간을 구하면
(2 + 6 + 11 + 18)/4 = 37/4
가 되는 것이다.
이러한 아이디어는 선점형과 비선점형이 둘다 가능한데, 비선점형이 여기서말하는 SJF이고 선점형은 SRTF(Shortest Remaining Time First) 스케줄링이라고 한다. 마찬가지의 개념이지만 선점형에서는 잔여시간을 가지고 판단을 한다. 즉 5의 처리시간의 프로세스가 1만큼 처리한 후 4의 잔여시간이 있을 때 3의 처리시간을 갖는 프로세스가 도착한다면 SJF는 그대로 이어서 남은 4만큼 처리한 후 처리하지만 SRTF는 3의 처리시간을 갖는 프로세스를 먼저 처리하는 방식이다.
SRTF는 SJF와 거의 유사하기 때문에 따로 예제는 들지 않도록 하고 참고할만한 링크를 걸어두도록 하겠다.
이러한 방식의 아이디어는 단점이 하나 있는데, 바로 처리시간이 긴 프로세스는 CPU를 점유하지 못하는 기아상태가 될 수 있다는 점이다. 따라서 실제 적용시에는 필요에 따라 다른 scheduling방식과 혼용해서 사용할 수도 있다.
마지막으로 처음쓰는 운영체제 글인데 학교에서 OS를 배울때 교수님께서 항상 강조하시던 말씀중 인상깊었던 것이 있다.
OS에는 정답이 없으며, 다양한 관점에서 니드를 충족시킬줄 알아야한다.
<링크>