Scheduling in Batch System

배치 시스템에서 사용되는 스케쥴링 알고리즘들

First Come First Served 알고리즘

1개의 레디 큐 존재

비선점형 방식(프로세스에 할당된 cpu를 자발적으로 내놓을때까지 뺏을수없다.)

실행중인 프로세스가 블락되면  큐의 맨앞 프로세스가 실행 되고 블락된 프로세스가 다시 레디상태가 되면 큐의 맨 뒤로 이동된다.

이해하기 쉽고 구현하기 간단한 알고리즘

Shortest Job First 알고리즘

비선점형 방식

프로세스의 실행시간이 미리 알려져있어야함. 최적의 평균 turnaround time(모든 job이 동시에 제출되어야 한다는 조건!!)

모든 job이 동시에 제출된다고 가정했을때 turnaround time이 적은것부터 처리하는게 모든 프로세스를 가장 빠른 시간에 처리할수있다.

하지만 이 가정이 깨졌을때는 turnaround time이 적은것부터 처리하는게 더 느릴 수도 있다.

A    B    C    D    E

RUNTIME        2    4    1    1    1    

Arrive time      0    0    3    3    3           SJF이 적용됬을때 

실행순서 A,B,C,D,E일때 Average Turnaround Time(ATT) = (2+6+4+5+6)/5 = 4.6

A    B    C    D    E

RUNTIME        2    4    1    1    1    

Arrive time      0    0    3    3    3           SJF이 적용안됬을때

실행순서 B,C,D,E,A일때  Average Turnaround Time(ATT) = (4+2+3+4+9)/5 = 4.4

Shortest Remaining Time Next

SJF의 선점형 버전이다.(프로세스의 cpu를 뺏음)

새로 큐에 들어온 프로세스의 런타임이 현재 실행중인 프로세스의 남은 수행시간보다 적을경우 현재 실행중인 프로세스는 중지되고 새로운 잡이 시작된다.(선점형 방식)

즉 잔여실행시간이 제일 적은것부터 실행시킨다.