SJF 스케줄링

1 개요

shortest-job-first scheduling; SJF scheduling

최단 작업 우선 스케줄링; SJF 스케줄링, SJF 알고리즘

• 버스트 시간이 짧은 프로세스부터 CPU 할당
• 버스트 시간이 짧은 것을 우선 처리하는 스케줄링 방식
• 버스트 시간이 짧을수록 우선순위를 높게 책정하는 우선순위 스케줄링
• 버스트 시간이 같으면 FCFS 스케줄링
• 비선점형, 선점형 모두 가능

선점형 SJF 스케줄링은 SRTF 스케줄링이라고 함

여기서는 비선점형 SJF 스케줄링을 다룸

2 예시 1

프로세스	실행시간	반환시간	대기시간
P0	6	6	0
P1	3	8	5
P2	8	21	13
P3	7	13	6
평균	-	13	6

P1P0P3P2

391624

• 평균 대기 시간 = ( 0+ 5 + 13 + 6 ) / 4 = 6

3 예시 2

프로세스	도착 시간	버스트 시간	턴어라운드 시간	대기 시간
P1	0	8	8	0
P2	1	4	11	7
P3	2	9	24	15
P4	3	5	14	9
평균	-	-	14.25	7.75

P1P2P4P3

8121726

• 평균 대기 시간 = ( 0 + 7 + 15 + 9 ) / 4 = 7.75

4 문제점 및 개선

• 최적이긴 하지만 CPU 버스트 시간을 미리 알 수가 없음
• 따라서 다음 버스트 시간이 이전 버스트 시간과 비슷할 것이라고 예측하여 적용
• 다음 버스트 시간 = 이전 버스트 시간들의 지수 평균

[math]\displaystyle{ \tau_{n+1}=at_n+(1-\alpha)\tau_n }[/math]

5 같이 보기

• SRTF 스케줄링 (=선점형 SJF 스케줄링)
• FCFS 스케줄링
• 우선순위 스케줄링
• 스케줄링 알고리즘

6 참고

• http://siber.cankaya.edu.tr/OperatingSystems/ceng328/node123.html