[운영체제 OS]스케줄링 알고리즘 SJF(Shortest Job First) 정리, 장점, 한계, non preemptive

[운영체제 목차, 포스팅 링크]

 

안녕하세요~~ 오랜만에 쓰는 운영체제 글이야요

무엇을 주제로 포스팅을 할까 고민하다가 운영체제 스케줄링 알고리즘 포스팅을 FCFS, RR, Multilevel Queue까지만 진행한 것 같아서 오늘은 운영체제 글의 완성도를 높일 겸 FCFS 알고리즘 이후에 나온 SJF 알고리즘을 살펴볼게요 

Shorteset Job First Scheduling (SJF)

최단 작업 우선 스케줄링

SJF가 나온 이유에 대해서 살펴보려면 먼저 그 전 단계인 FCFS 알고리즘의 단점을 이해하고 있어야 해요

기존의 문제점을 해결하기 위해 새로운 솔루션이 제기 되는거니까요!

 

자 그럼 잠깐 FCFS의 문제점을 짚고 넘어갑시다.

FCFS 문제점? waiting time이 커요. 기억이 안나는 친구들을 위한 링크! ↓

[운영체제]FIFO/FCFS (피포/first come first served)정의와 문제 & Convey Effect

이 문제를 해결하기 위해 나온 알고리즘이 SJF입니다. waiting time이 작은 것이 장점이 되겠죠?

어떻게 이 waiting time을 줄이 수 있었을까요? FIFO랑 다르게 CPU를 적게 사용하는 것부터 먼저 수행을 시켜 끝내버리면 평균 waiting time이 좋아질거예요. 그래서 이름도 가장 빨리 끝나는걸 먼저 수행하자라는 뜻인 shortest job first 입니다.

 

this algorithm associates with each process the length of process's next CPU burst

즉 이 알고리즘은 그 다음 프로세스가 CPU를 얼마나 사용하는지 에 대한 길이와 관련이 있어요 ㅎㅎ

뒤에 가서 동작방식을 좀 더 자세히 살펴볼겁니다.

 

사진의 첫 문단에 대한걸 지금까지 다 녹여서 설명했어요!

- 가장 CPU burst가 적은 것을 먼저 수행한다. (빨리 끝나는 놈부터 조진다(?) ㅎㅎ)

 

 

- SJF가 average waiting time이 가장 적게 걸린다.

(이마트 가면 소액결제 셀프 계산대있자나요? 물건 별로 없는애들 빨리빨리 가게해주는..

그걸 SJF라 생각하고 FCFS를 마트 계산대에 누가 많이 샀든 적게 샀든 온 순서대로 줄 서는걸 빗대어 생각하면 이해하기 좀 더 수월할 거예요)

 

 

 

 

 

 

- Non-preemptive하다.

마지막 Non-preemptive에 관한 부문만 설명이 빠진 것 같은데,,

SJF는 두 가지 버전이 있습니다. preemptive한 버전과 nonpreemptive한 버전!

둘 다 살펴볼꺼예요. 근데 구분상 nonpreeptive한 SJF는 그냥 SJF라 부르고, preeptive한 SJF는 'shortest remaining time first'라 부릅니다. 그래서 위 사진에는 non preemptive하다라고 설명을 한거예요.

Nonpreemptive - Once CPU given to the process it cannot be preempted until completes its CPU burst.

Nonpreemptive는 양보하지 않는다? 끼어들 수 없다? 도중에 변환 안된다? 중단이 안된다 정도로 생각하시면 됩니다.

 

non-preemptive vs preemptive

non-preemptive하고 preemptive하고 예시를 통해 비교해볼께요

상황: 현재 시점에서 수행시간이 제일 짧은 애(3초)를 수행을 시켰어요. 그리고 일초가 지났습니다. 그러면 수행하고 있던 job은 2초를 더 수행해야겠죠? 1초가 지나서 딱 봤는데 새로운 프로세스가 도착을 한겁니다. 근데 이 새로운 프로세스를 수행하는데 걸리는 시간이 1초입니다. 즉 현재 2초가 남아있는데 1초짜리가 들어온 상황입니다.

 

non-preemptive 경우 :

non-preemptive 에서는 그냥 2초 짜리를 계속 하는거죠 중단 못 시킨다고 했잖아요? 즉 계속 진행시키는겁니다.

preemptive 경우:

preemptive의 경우 새로 들어온 애가 수행 중이던 job을 중단시키고 수행시킬 수 있습니다. (새치기, 짤라먹기 가능ㅎㅎ) 이렇게 중단시키는 preemptive 방식이라고 가정을 하면 현재 수행되는 2초를 중단하고 1초짜리 실행하는 거죠. 그 때는 이거를 shortest job first 라고 하기 보다는 shortest remaining time first라고 표현하는 것이 맞습니다. 명칭 그대로 남은 시간이 가장 적은 것을 수행하는 것! 

이런 차이 때문에 non-preemptive 버전은 그냥 SJF라고하고 preemptive버전은 shortest remaining time first라고 합니다.

공통점?

수행시간이 작은 것을 먼저 수행시킨다는 개념은 똑같습니다.

SJF 알고리즘을 토대로 위 문제의 평균 waiting time을 계산해봅시다.

첫 번째 P1이 들어오면 nonpreemptive이므로 P1이 끝날때까지 계속 수행합니다.

P1이 도는 동안 P2, P3, P4가 다 들어왔네요~! 여기서 제일 CPU burst가 작은 P3가 P1다음으로 수행됩니다.

P3은 CPU가 1이니까 8에서 끝날거고 그 다음 P2와 P4중 뭘 먼저 시킬까 CPU burst를 봤는데 둘이 똑같네요 그러면 먼저 들어온 P2를 수행시킵니다.

 

P1은 바로 수행됐기 때문에 기다린 시간이 0초!

P2는 2초에 들어왔는데 8초에 수행되었으니 waiting time이 6초

P3는 4초에 들어왔는데 7초에 수행되었으니 기다린 시간은 3,

P4는 5에 들어왔는데 12에 수행되었으니 기다린 시간은 7초가 되겠죠

이를 평균 내보면 해당 시뮬레이션에서 평균 기다린 시간은 4초인 것을 계산할 수 있어요

SJF의 한계!

근데 SJF가 되었던 SRTF가 되었던 이 스케줄링 방식을 우리 컴퓨터 방식에는 적용하기가 힘들어요!!!

 

상황을 다시 한 번 빗대어서 설명해보겠습니다.

카트를 딱 가져왔을 때 만약 계산 라인이 3개가 있어요. 근데 3개 라인 중 여러분들은 어디에 줄을 서나요?

그 라인에 선 사람들의 카트에 얼마씩 담겨져 있는지 보고 줄이 빨리 줄 것 같은 라인으로 줄을 서잖아요?

그게 바로 SJF로 여러분이 이미 실생활에서 스케줄링을 하고 있는겁니다. 근데 이 알고리즘은 앞 사람이 카트에 얼마나 담겨져 있는지 알수 있기 때문에 수행할 수 있는 겁니다.

 

 

The real difficulty with the SJF algorithm is knowing the length of the next CPU request.

SJF 알고리즘에서 어려운점은 다음 CPU 요청의 길이를 아는 거예요

 

그런데 컴퓨터에서는 프로세스가 어떤 CPU burst를 가지는지 CPU가 수행 될 때에는 몰라요.

왜? I/O를 요청하는 명령어가 나와야 그 때까지가 CPU burst이므로 미리 측정할 수가 없습니다.

 

즉 프로세스가 얼마만큼의 CPU burst를 가지는지 미리 알 수가 없습니다. 그래서 SJF는 실제로 적용하기 어려워요. 과거 사람들이 나름 예측을 해보자~~ 해서 과거의 CPU burst가 어떻게 됐는지 데이터를 토대로 예측을 하려 했어요. 근데 그 예측이 잘 안되고 일관성도 없고 그렇기 때문에 이렇게 예측해보려고 하는 시도가 있었음에도 불구하고 결과가 좋지는 못했죠 ㅎㅎ

 

예측을 어떻게 했나에 대한 간단한 설명.

We expect that the next CPU burst will be similar in length to the previous one.

사람들은 다음 버스트 시간이 이전 버스트 시간과 비슷할거라고 예측했어요

By computing an approximation of the length of the next CPU burst, we can pick the process with the shortest predicted CPU burst.

대략 다음 CPU burst 길이를 계산함으로써 예측된 CPU busrt 프로세스로 SJF알고리즘을 돌릴 수 있을거라 생가했죠.

The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts.

다음 CPU는 보통 이전 CPU버스트들의 지수 평균을 갖는걸로 생각돼 다음과 같은 공식을 썼습니다.

여기서 tn은 n번째 CPU burst의 길이를 말합니다.

타우n이 지난 이력들의 정보를 가지고 있다면 tn은 가장 최근의 정보를 가지고 있는 변수입니다.

 

해당 공식을 적용하면 위 그래프처럼 예측되고 (파란색이 예측값)

실제와는 저런 차이(?)를 가져요.

 

결과론적으로는 FCFS/SJF 두가지는 컴퓨터에서는 적합하지 않아요 뒤에 더 좋은 알고리즘이 개발되었으니까요!이 시기에는 운영체제에서 실제 사용하고 있는 알고리즘은 나오지 않았어요 ㅎㅎ (FCFS/SJF아님) 

다음 포스팅에서는! FCFS, SJF 다음에 나온 알고리즘을 살펴보겠어요! 그 뒤가 실제 우리가 사용하고 있는 알고리즘이랍니다.

요약 정리글

- 기다리고 있는 작업 중에서 수행 시간이 가장 짧다고 판단되는 것을 먼저 수행한다.

- FCFS보다 평균 대기시간을 감소시키는 반면, 큰 작업에 관해서는 FCFS에 비해 대기시간 예측이 어렵다.

 

다음 포스팅!↓ 우선순위 스케줄링은 요기

[운영체제 OS]우선순위 스케줄링(Priority Scheduling) 총정리,장단점, aging 스케줄링, 우선순위 부여기준

도움이 됐다면 광고 클릭, 댓글, 공감, 피드백 부탁드려요 오늘도 수고하셨습니다 ★