logo

SJF(Shortest Job First) 스케줄링

지금까지 우리는 도착 시간에 따라 프로세스를 스케줄링했습니다(FCFS 스케줄링). 그러나 SJF 스케줄링 알고리즘은 버스트 시간에 따라 프로세스를 스케줄합니다.

SJF 스케줄링에서는 준비 큐에 있는 사용 가능한 프로세스 중 버스트 시간이 가장 낮은 프로세스가 다음으로 스케줄링됩니다.

그러나 프로세스에 필요한 버스트 시간을 예측하는 것은 매우 어렵기 때문에 이 알고리즘을 시스템에 구현하는 것은 매우 어렵습니다.

SJF의 장점

  1. 최대 처리량
  2. 최소 평균 대기 및 처리 시간

SJF의 단점

  1. 기아 문제로 고통받을 수 있음
  2. 프로세스의 정확한 버스트 시간을 미리 알 수 없기 때문에 구현이 불가능합니다.

프로세스의 CPU 버스트 시간을 결정하는 데 사용할 수 있는 다양한 기술이 있습니다. 나중에 자세히 논의하겠습니다.

C의 문자열 배열

다음 예에는 P1, P2, P3, P4, P5라는 이름의 5개 작업이 있습니다. 도착 시간과 버스트 시간은 아래 표에 나와 있습니다.

PID 도착 시간 버스트 시간 완료 시간 처리 시간 대기 시간
1 1 7 8 7 0
2 13 10 7
6 2 10 4 2
4 7 10 31 24 14
5 9 8 이십 일 12 4

따라서 프로세스가 시간 0에 도착하지 않습니다. 빈 슬롯이 있을 겁니다. 간트 차트 시간 0부터 1(첫 번째 프로세스가 도착하는 시간)까지.

알고리즘에 따라 OS는 Ready Queue에 있는 사용 가능한 프로세스 중 버스트 시간이 가장 짧은 프로세스를 스케줄링합니다.

지금까지 준비 대기열에는 하나의 프로세스만 있으므로 스케줄러는 버스트 시간에 관계없이 프로세서에 이를 예약합니다.

이는 8 단위 시간까지 실행됩니다. 그때까지 준비된 대기열에 세 개의 프로세스가 더 도착하므로 스케줄러는 버스트 시간이 가장 낮은 프로세스를 선택합니다.

표에 제시된 프로세스 중 P3은 사용 가능한 모든 프로세스 중 버스트 시간이 가장 낮기 때문에 다음에 실행됩니다.

그럼 절차는 이렇게 진행됩니다 최단 작업 우선(SJF) 스케줄링 알고리즘.

OS SJF 스케줄링 알고리즘

평균 대기 시간 = 27/5