[운영체제 Step8] - 프로세스 스케줄링 알고리즘

이번 시간엔 프로세스 스케줄링이 일어날 때 여러 알고리즘에 의해서 수행되는데, 어떤 알고리즘이 있는지 어떻게 연산이 되는지 등을 알아보겠습니다.

다 정리하려면 굉장히 많겠지요???

그래서 2가지 글로 나누어서 설명을 해보고자 합니다. 가능하면 한 개로 할 수 있으면 좋겠네요

첫 번째 FCFS (First-Come-First-Service)입니다.

쉽게 이해하자면 선착순입니다.

먼저 오는 프로세스에게 먼저 CPU를 할당해주겠다는 의미입니다.

따라서 비선점 스케줄링이라고도 합니다.(프로세스가 끝날 때까지 누구도 뺏을 수 없음)

그리고 스케줄링의 기준은 도착 시간을 기준으로 선택하고 먼저 도착한 프로세스를 먼저 처리하게 됩니다.

그러므로 자원을 효율적으로 사용할 수 있습니다.

왜 그럴까요?

자, 컴퓨터 공학에서는 비용이라는 개념을 빼놓고 이야기 할 수 없습니다.

아무래도 선착순으로 자원 할당을 하기 때문에 FCFS기법을 사용하면 Context Switching이 적어 오버헤드도 줄어듭니다.

따라서 비용이 적어진다는 장점이 생기게 됩니다.

그러므로 스케줄링 오버헤드가 적어지고 CPU가 계속 일할 수 있습니다.

이 FCFS는 배치 시스템(일괄처리 시스템)에 적합하다는 특징도 가지고 있습니다.

왜냐하면 일괄처리 시스템은 들어오는 프로세스를 빨리 응답해주는 것보다 오는 순서대로 빨리 빨리 처리해주는 것이 목적이기 때문에 배치 시스템에 적합합니다. 하지만 인터랙티브 시스템(대화형 시스템)에서는 응답을 기준으로 계속 기다려야 하기 때문에 부적합할 수 있습니다.(초장에서 배웠어요)

 

이 FCFS에는 단점도 있습니다.

그 중 하나가 긴 평균 응답시간입니다. 

요청을 보내고 받는데 얼마나 기다려야 할지 예측하기가 힘들 수 있기 때문입니다.

그리고, 내가 할 일은 2초면 끝나는데 나보다 먼저 도착한 어떤 녀석은 20초가 걸린다고 해봅시다.

그럼 난 2초만 쓰면 되는데 먼저 들어온 녀석 때문에 다른 프로세스가 대기하는 시간이 길어질 수 있습니다.

우리는 이것을 Convoy Effect라고 부릅니다.

그래서 그림으로 표현을 해보면 다음과 같습니다.

프로세스들이 CPU에 도착을 하고 본인의 업무를 다 하면 종료되겠습니다.

표로 알아보겠습니다.

프로세스 P1 ~ P5까지 CPU에 할당하기 위해 들어왔습니다.

각각의 Arrival time과 Burst time이 다음과 같을 때 WT와 TT, NTT를 구해봅시다.

P1의 경우 제일 먼저 도착하게 됩니다. 그래서 기다리는 시간이 없으므로 WT 는 0이됩니다.

Turnaround는 실행시간과 대기 시간의 합친 시간입니다. 그러므로 TT는 3초가 됩니다.

그리고 NTT는 Normalized TT의 준말인데, 정규화시간이라고 불립니다.

이는 상대적으로 BT보다 TT가 얼마나 되느냐를 묻는 의미입니다. 보통 1보다 크면 기다리는 체감이 더 많다고 느낄 수 있다고 합니다. 그래서 P1의 NTT는 3 / 3이되어 정확하게 1입니다.

P2에서는 P1이 끝난 뒤 실행이 됩니다. 그러므로 3일 때 실행되어 WT는 총 2입니다. TT는 BT + WT이므로 9입니다. 

따라서 NTT는 1.3이 됩니다.

P3부터는 꽤나 흥미롭습니다. P3은 3초에 도착하여 2초만 Burst하는데, P2가 10초에 끝나기 때문에 WT가 무려 7초나 됩니다. 따라서 TT는 9초입니다. 이에 따라 NTT는 9/2가 되어 4.5가 됩니다.

고작 2초만 Burst하면 되는데 기다리는 시간이 너무 길어졌다는 것을 확실하게 알 수 있습니다.

P4와 P5는 생략하겠습니다.

자, P2하나 때문에 나머지 프로세스들이 오래 기다려서 NTT가 모두 커졌습니다.

이런 현상을 바로 Convoy Effect라고 합니다!

다음 스케줄링 기법으로 넘어가겠습니다.

 

• RR (Round - Robin)

너무 FCFS에선 순차적으로 프로세스를 처리해서 불만이 생길 수 잇습니다.

그래서 우리 CPU를 돌아가면서 쓰자, 너 몇초 쓰고 나 몇초 쓰고 이렇게 나누자! 하는 것이 RR기법입니다.

일을 돌아가면서 하기 때문에 남의 자원을 쓸 수 있겠죠. 그래서 선점 스케줄링입니다.

그리고 스케줄링 기준을 보시면 먼저 도착한 프로세스를 기준으로 나눕니다.(도착 시간에 따라)

여기까진 FCFS와 비슷해보입니다.

하지만 FCFS와 절대적으로 다른 부분은 자원 사용 제한 시간 (Time Quantum)이 있습니다.

만약 제한 시간이 지나면 하던 작업을 멈추고 자원을 반납해야 합니다.

이 제한시간을 System Parameter라고 부릅니다.

그래서 어떤 특정 프로세스가 자원을 독점(monopoly)하는 것을 방지할 수 있습니다.(장점)

하지만 그로 인해 Context Switching이 커지므로 오버헤드가 커진다는 단점이 있습니다.(단점)

FCFS에서는 한 번 주면 끝났는데 RR에서는 계속 프로세스를 돌려야 되는 것이 단점일 수 있습니다.

그럼 이 기법은 어떤 시스템에 적합할까요?

응답이 빨라야 하는 시스템에 적합할 것입니다.

즉, Interactive System과 Time sharing System에도 적합하다는 특징을 가지고 있습니다.

지금까지 RR의 정의였습니다.

그럼 이 RR의 성능을 결정하는 요소는 무엇일까요?

바로 Time Quantum 이 되겠습니다.

즉, 제한 시간이 성능에 중요한 영향을 미칠 수 있습니다.

만약 이 제한 시간이 너무 크다면 FCFS와 별 다를 바 없을 것입니다. ( 한 번 자원 받으면 끝까지 감)

근데 제한 시간이 0에 수렴한다면 CPU를 동시에 쓴다는 느낌이 들 것입니다. 그로 인해 체감되는 프로세서 속도는 실제 프로세서 성능을 N배 나눈 것과 같은 속도의 체감을 느끼게 될 것입니다.

그로 인해 계속 컨텍스트 스위칭이 일어나 오버헤드가 커지게 된다는 단점이 존재할 것입니다.

RR을 그림으로 이해해봅시다.

FCFS와 다른 점이 어떤 것인가요?

밑에 Timer-runout이라는 선이 추가되었지요??

RR에서는 P1이라는 프로세스가 작업을 수행하다가 Time Quantum에 의해 선점되어 종료되면 그대로 종료되는 것이 아니라 P1, p2들의 제일 뒤로 가게됩니다.

먼저 왔으니까 새치기해서 제일 먼저 또 수행하는 것이 절대아닙니다. 꼭 유념해주세요.

제일 뒤로가서  다시 Ready Queue상태에 돌입하게 되고 자신의 차례를 기다리는 것. 그것이 RR입니다.

이번에도 표로 이해해볼까요?

자 P1 ~ P5까지 있습니다.

P1은 먼저 작업을 연산하는데, 지금 Time Parameter가 2초입니다. 근데 P1의 BT가 3이기 때문에 일을 다 수행 못하고 Ready Queue로 가서 대기합니다. 1초 남은 상태에서요.

그러던 중 도착해있던 P2가 작업을 연산하고 또다시 2초가 걸립니다. 이 때 P3도 도착합니다. 근데 P2의 BT는 7초이므로 2를 뺀 5가 남아있는채로 P2는 Ready Queue로 가서 대기합니다.

지금까지 Ready Queue에는 P1(1초), P3(2초), P2(5초)가 순서대로 실행되려고 기다리고 있습니다.

그 다음으로 P3가 들어오지만 P1이 먼저 대기하고 있었기 때문에 P1이 실행됩니다.

그렇게 함으로써 P1은 자신의 연산을 다 수행하고 WT는 P2를 기다렸던 2초가 되고 TT는 5초(3초 + 2초)가 되어 총 NTT는 5 / 3 = 1.7이 되겠습니다.

이후 P3가 실행됩니다. P3의 BT는 2초이기 때문에 이번 한번에 모든 연산을 실행합니다.

그러므로 WT는 P1을 실행할 때 1초와 P2를 기다릴 때 1초 총 2초가 되고 TT는 4초가 됩니다. NTT는 4 / 2이므로 2초가 되겠습니다.

나머지는 표로 확인해보겠습니다.

그럼 평균 응답시간은 어떻게 구할 수 있을까요?

여기선 따로 응답을 하는걸 설정하지 않았기 때문에 TT가 응답시간이 됩니다.

그러므로 5 + 18 + 4 + 15 + 12 / 5 = 10.8 즉, 10.8초가 평균 응답시간이 되겠습니다.

그럼 Time Quantum에 따라서 성능이 어떻게 바뀌는지 확인해보겠습니다.

이번엔 타임 파라미터가 3일 때입니다.

비교적으로 평균 응답시간(TT)가 9.8초가 되었으니 조금 더 빠른걸 알 수 있습니다.

무조건 타임 파라미터가 크다고 성능이 좋은 것도 아니고 작다고 성능이 좋은 것이 아니므로 효율적으로 사용하기 위해서 적절한 타임 파라미터 설정이 필요하겠습니다.

감사합니다.