밸~하

밸로그 여러분 안녕하세요 !

오늘은 지난시간에 이야기드린것 처럼 스케줄 알고리즘의 종류와 성능척도에 대해서 포스팅을 해보겠습니다.

지난 포스팅에는 운영체제가 자원을 효율적으로 프로세스에 할당하기위해서 프로세스 스케줄링을 통해서 프로세스에 자원을 할당해 준다고 했었습니다.
그럼 이 스케줄링은 어떤알고리즘에 의해서 수행되고 각각 알고리즘의 성능척도는 어떻게 되는지 알아보겠습니다.

먼저는 스케줄링의 성능척도입니다.

스케줄링 성능척도

CPU스케줄링 알고리즘은 여러종류가 존재하고 있습니다.
이 여러 알고리즘의 성능을 평가하는 기준 성능 척도라는 것이 존재합니다.
그럼 이 성능척도는 어떻게 측정이 되는지 알아보겠습니다.

1. 시스템 입장에서의 성능척도

먼저는 시스템 입장에서의 성능척도입니다.

시스템 입장에서의 성능척도는 두 가지 기준에 의해서 다룰 수 있는데요

• CPU 이용률(CPU Utilization)
• 처리량(throughput)
  이 두가지 입니다.

CPU이용률의 경우 전체 시간중 CPU가 쉬지않고 일한 시간을 CPU 이용률 이라고 합니다.
그리고 처리량의 경우 단위 시간당 수행 완료한 프로세스의 수를 처리량이라고 표현합니다.

즉, 시스템의 입장에선 CPU이용률과 처리량이 최대가 될수록 좋다 더 좋은 성능을 가지고 있다라고 표현할 수 있습니다.

2. 프로그램 입장에서의 성능 척도

그 다음은 프로그램 입장에서의 성능척도 입니다.
프로그램 입장에서의 성능 척도는 시스템의 입장과는 다르게
다른 세가지의 기준에 의해서 평가됩니다.

프로그램 입장에서의 성능척도는 세가지 기준이 존재합니다.

• 소요 시간(Turnaround Time)
• 대기 시간(Waiting Time)
• 응답 시간(Response Time)
  이렇게 세가지가 존재합니다.

소요 시간의 경우 프로세스가 Ready queue에서 대기한 시간부터 작업을 완료하는데 걸리는 시간을 의미합니다.
대기 시간의 경우 프로세스가 Ready queue에서 대기한 시간을 의미합니다.
응답 시간의 경우 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간을 의미합니다.

다시말해, 시스템의 입장과는 다르게 프로그램의 입장에서는 소요,대기,응답 시간이 모두 최소가 될수록 더 좋은 성능을 가지고 있다라고 표현할 수 있습니다.

그럼 이러한 성능 척도를 알아봤으니 이제부터는 스케줄링 알고리즘에 대해서 알아보겠습니다.

스케줄링 알고리즘의 종류

스케줄링 알고리즘에는 어떤 종류들이 있을까요??

많은 알고리즘들이 존재하지만 오늘은 그중 몇가지만 다뤄보도록 하겠습니다.

먼저는 FCFS scheduling에 대해서 알아보겠습니다

1. FCFS scheduling

FCFS스케줄링은 Fisrt Come First Served의 약자로 CPU에 먼저 도착하는 순서대로 프로세스를 할당해주는 방식입니다.

FCFS스케줄링은 각 작업이 종료될때까지는 CPU를 빼앗지 않기때문에 비선점(non-premptive)방식이며, FIFO방식의 큐와 동일합니다.

그렇기에 구현이 다른 scheduling보다 쉬워 간단한 시스템에 자주 사용되기도 합니다.
이렇게 처리를 하면 가장 먼저 준비 큐에 들어온 프로세스부터 순차적으로 처리를 하기 때문에 어떤 프로세스가 언제 수행될지를 알기 쉽습니다.

하지만 이러한 FCFS scheduling에는 단점이 존재합니다.

바로 프로세스들이 기다리는 시간이 매우 기어질 수도 있다는것입니다.

예를들어. 수행하는데10시간이 걸리는 프로세스가 있고 수행하는데 2시간이 걸리는 프로세스가 있다고 가정을 해보겠습니다. 그러면 2시간이 걸리는 프로세스는 2시간만이면 수행될 수 있음에도 불구하고 두번째로 들어왔기때문에 완료되기까지 12시간이 걸리게 됩니다.
그렇기때문에 비 효율적이기도 합니다.

이러한 현상을 바로 convoy Effect라고 합니다.
convoy Effect란?

하나의 긴 프로세스로 인해 나머지 프로세스가 오래 기다리게 되어 CPU효율성이 낮아지는 문제점 입니다.

이렇게만 들으면 FCFS스케줄링은 사용할 곳이 없다라고도 생각이 들 수가 있습니다 .

하지만 만약 모든작업이 동일한 시간만큼 수행이 된다는 보장이 있다면 상대적으로 구현하기가 쉬운 FCFS스케줄링이 사용하기에 훨씬 용이할 것입니다.

그다음 볼것은 바로 SJF scheduling에 대해서 알아보겠습니다.

2. SJF(Shortest Job First)scheduling

SJF스케줄링은 convoy Effect를 해결하기 위한 방식입니다.
이전에 작업이 긴 프로세스로 인하여 짧은 작업이 걸리는 프로세스가 늦게 처리되는 문제를 해결하기 위해
SJF스케줄링은 프로세스의 수행시간이 짧은 순서대로 CPU에 할당하는 스케줄링 입니다.
즉, CPU 사용시간이 긴 프로세스는 나중에 실행하고, CPU사용시간이 짧은 프로세스를 먼저 실행합니다.
그렇기에 SJF스케줄링은 항상 주어진 프로세스에 대해 최소의 평균 대기시간을 보장합니다.

그러나 이러한 SJF스케줄링에도 문제가 있는데 바로 Starvation 현상이 발생한다는 것입니다.

• Starvation이란?
• 수행시간이 긴 프로세스는 계속 뒤로 밀려나는 현상
  만약 수행시간이 길더라도 중요한 작업이 있다면 계속 뒤로 밀리는것이 아니라 수행이 되어야하는데 그렇지가 않다는 것입니다.

또한 SJF스케줄링의 경우는 각 프로세스가 얼마나 CPU를 사용할지 모르는 경우에는 사용하기가 어렵습니다. 단지 추정만 할 수 있습니다.

추정하는 방식에는 바로
과거의 CPU burst time을 이용하여 예측하는 지수평활법을 사용합니다. 즉 최근 가중치를 더 많이 반영하여 작업에 걸리는 수행시간을 추정한다는 것입니다.

SFJ스케줄링은 기본적으로 비선점 스케줄링 알고리즘으로 분류가 되기는합니다. 하지만 선점형 스케줄링 알고리즘으로도 구현을 할수가 있습니다.

만약 비선점 스케줄링으로 구현을 했을경우
모든 프로세스들이 다른시간에 도착을 한다고 가정을 하게 될경우 최적의 값이 나오지 않을 수 있습니다
이렇게 되는 경우
선점 스케줄링으로 구현을 하여
새로운 프로세스가 도착했을때, 현재 남아있는 작업중 가장 빨리 끝나는 작업부터 CPU를 할당해주는 SRTF(Shortest Remaining Time First)스케줄링으로 구현할 수 있습니다 .

하지만 여전히 단점인 Starvation현상을 막을 수는 없습니다.

그럼 이 starvation효과를 막을 수 있는 알고리즘은 어떤게 존재할까요?

이번에 알아볼 스케줄링은 Starvation효과가 발생하지 않는 스케줄링입니다.
바로 RR(Round Robin) scheduling입니다 .

3. RR(Round Robin scheduling)

Round Robin 스케줄링은 각 프로세스가 주로 10~100ms의 동일한 크기의 할당 시간을 갖고, 할당시간이 끝나면 프로세스는 자동으로 선점당하고, Ready 큐의 제일 뒤로 가서 다시 대기 하는 스케줄링 입니다.
즉, 정해진 time slice만큼의 시간동안 돌아가면 CPU를 이용하는 선점형 스케줄링이라고 할 수 있습니다.

-time slice : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

예를들어 n개의 프로세스가 Ready큐에 존재하고, 할당시간이 q라면 어떠한 프로세스도 (n-1)q이상 기다리지 않으므로 starvation현상이 발생하지 않습니다. 그렇기에 응답시간이 빠르다는 장점이 있습니다 .

다만, SJF보다는 평균소요시간이 더 깁니다.
RR스케줄링은 할당시간이 클수록 FCFS스케줄링과 방식이 유사하고, time slice가 작을수록 Context switch의 오버헤드가 커지기 때문에 적절한 시간을 배정하여 효율적으로 스케줄링을 구성하는것이 중요합니다.

오늘 볼 스케줄링은 여기까지 입니다 .

오늘은 스케줄링의 성능척도를 어떻게 나타내는지와
대표적인 스케줄링 3가지를 알아보았습니다.

다음 시간에는 3개외의 더많은 스케줄링 방식에 대해서 이야기를 드릴 수 있도록 하겠습니다.