CPU 스케줄링 /SJF SRT

프로세스 작업 수행을 위해 언제, 어느 프로세스에 CPU를 할당할 것인지 결정하는 작업

기법 종류

• 스케줄러 동작 시점, Time Slice, 프로세스 생성/소멸 시, 프로세스 Block 상태 변경 시
• 스케줄러가 운영체제에 많이 관여-선점, 적게 관여-비선점

SJF (Shortest Job First), SRT (Shortest Remaining Time)

SJF (Shortest Job First)

- 비선점 방식 (non - preemptive)

- 대기 작업 중 수행 시간이 짧게 판정된 작업 수행

- 짧은 작업 먼저 수행이 오버헤드 측면에서 유리

 

문제점)

- 작업 수행 시간을 사전에 정확히 판정 어려움

 

SRT (Shortest Remaining Time)

- 선점 방식 (preemptive)

- SJF 기법에 선점방식을 도입/변형 방식

- 실행 중 작업이라도 처리 시간이 더 짧은 작업이 생기면 선점

 

문제점)

- 긴 작업에 대한 실행 시간 추적 보유 (오버헤드)

- 긴 작업은 SJF 보다 대기 시간 오래 소요

SJF와 SRT의 평균 대기시간 및 평균 반환시간

SJF 기법 계산

SRT 기법 계산

• 대기시간: 작업이 대기 큐에서 대기한 시간, 반환시간: 작업이 제출된(도착) 시간부터 완료까지 시간
• 프로세스 자원 점유 변경 시 문맥 교환이 일어나므로 빈번한 자원 점유 변경 시 오버헤드 증가에 따른 성능 감소

예제)

5개의 작업에 대한 도착 시간과 CPU 사이클 시간이 아래표와 같다고 다음 물음에 답하시오

위에서 SRT, SJF 스케줄링 알고리즘을 적용할 경우 평균 대기시간과 반환시간을 구하시오.

 

A)

선점형 스케줄링은 하나의 프로세스가 cpu를 점유하고 있을 때 작업중인 프로세스를 중단시킬 수 있는 방식으로 srt가 여기에 속한다.

비선점형 스케줄링은 하나의 프로세스가 cpu를 점유하고 있을 때 작업중인 프로세스를 중단시킬 수 없는 방식으로 sjf가 여기에 속한다.

 

SRT 방식

남아있는 도착 시간이 가장 짧은 작업을 먼저 처리한다. 위의 그림을 보면 a가 먼저 시작이 되므로 1을 처리하고 a의 남은 시간은 5가 된다.

b가 들어오는데 a보다 b가 남은 시간이 짧으므로 a는 대기 상태가 되고 b가 처리된다. b가 1을 처리하고 나니 남은 시간은 2가 된다. 그리고 c가 들어오는데 b보다 c가 남은 시간이 적으므로 c가 처리되고 b는 대기상태가 된다. c를 처리하고 나면 d가 들어온다.

a, b, d의 남은 시간이 각각 5,2,4이므로 b를 먼저 처리하고 d를 처리하고 a를 처리한다.

 

평균 대기시간은

a,b,c는 도착즉시 시작했으므로 0, d는 도착 후 2초를 기다렸으므로 0+0+0+2=2/4=0.5다

 

평균 반환시간은

a는 0에서 시작해서 14에서 끝났으므로 14

b는 1에서 시작해서 5에서 끝났으므로 4

c는 2에서 시작해서 3에서 끝났으므로 1

d는 3에서 시작해서 9에서 끝났으므로 6

그래서 14+4+1+6=25/4=6.25

 

SJF 방식

마찬가지로 도착시간 가장 짧은 a를 먼저 실행하고 a가 끝나면 b,c,d 모두 기다리는데 이 중 c가 실행시간이 가장 짧으므로 실행한다. c가 끝나고 나면 b,d가 기다리는데 b가 짧으므로 b를 실행하고 d를 실행한다.

 

평균대기시간 a는 0, c는 2에 들어와서 6에 실행됨으로 4, b는 1에 들어와서 7에 실행됨으로 6, d는 3에 들어와 10에 실행됨으로 7

0+4+6+7=17/4=4.25

 

평균 반환시간은 

a는 0에서 시작해서 6에서 끝났으므로 6

b는 1에서 시작해서 10에서 끝났으므로 9

c는 2에서 시작해서 7에서 끝났으므로 5

d는 3에서 시작해서 14에서 끝났으므로 11

6+9+5+11=31/4=7.5다

 

https://blog.skby.net/cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81/

https://blog.naver.com/jjaiwook79/30069179687