[운영체제] 프로세스 스케줄링(process scheduling)

오늘은 여러 프로세스 스케줄링 알고리즘에 대해 알아보겠습니다.

 

그 전에 스케줄링의 다섯가지 목표에 대해 알아보겠습니다.

 

1. cpu 이용률 최대화

(MAX CPU utilization)

2. 각 프로세스 당 시간 할당률 최대화

(MAX throughput)

3. 프로세스가 처음 ready queue에 있을 때 부터 작업을 종료할 때까지의 시간 최소화

(MIN turnaround time)

4. 기다리는 시간 최소화

(MIN waiting time)

5.프로세스 실행 후 반응이 일어날 때까지의 시간 최소화

(MIN response time)

 

 

스케줄링 알고리즘에는 두 가지 종류가 있고 각각 장점이 있습니다.

 

1. 비선점형 (non-preemptive)

한 번 cpu가 할당되면  (1) I/O를 사용하기 위해 waiting state가 되거나, (2) 작업이 종료되었을 경우에만 cpu 이용을 중단하게 된다.

장점: context switching이 덜 발생한다.

 

2. 선점형 (preemptive)

한번 cpu가 할당되더라도 interrupt가 발생하면 운영체제에 의해 ready state가 된다. 

장점: interrupt에 즉각적으로 반응할 수 있다.

       response time이 감소한다.

       여러 프로세스가 동시에 사용되는 것처럼 동작할 수 있다. (=time sharing)

 

 

프로세스 스케줄링 알고지즘 중 6가지에 대해 살펴보겠습니다.

 

 

1. FCFS (First Come First Served) -선점형

 

스케줄링 기준: 도착 시간이 빠른 프로세스 먼저

장점: 가장 간단하다.

단점: 대체로 waiting time이 길다.

       cpu와 device 이용률이 낮다.

한마디로 비효율적인 방법이다. 

 

 

2. SJF (Shortest Job First)

 

장점: waiting time을 최소화 해준다. 

       시스템에 남아있는 프로세스 수를 최소화 해준다.

       많은 프로세스들(짧은 cpu이용시간을 가진 프로세스)에게는 응답이 빠르다.

단점: cpu이용시간이 긴 프로세스들은 짧은 cpu이용시간을 가진 프로세스가 계속 새로 진입한다면 우선순위가 계속 밀리게 되어서 영원히 실행되지 않는 starvation현상이 나타날 수 있다.

 

       2-1. SJF -비선점형 

 

       스케줄링 기준: cpu 이용 시간이 가장 짧은 프로세스 먼저

       

      2-2. SRTF (Shortest Remaining Time First) -선점형

 

      스케줄링 기준: 남은 cpu 이용 시간이 가장 짧은 프로세스 먼저

 

3. HRRN (Highest Response Ratio Next) -비선점형

 

스케줄링 기준: 높은 응답률(response ratio) 먼저

장점: starvation 현상을 방지할 수 있다. 

response ratio = (waiting time + estimated time) / estimated time

ready queue에서 기다린 시간을 반영하여 프로세스의 우선순위를 높여주는 것을 aging이라고 한다.

 

4. RR (Round Robin) -선점형

 

스케줄링 기준: 도착 시간이 빠른 프로세스 먼저

                    Time quantum에 따라 interrupt가 발생한다.

장점: 한 프로세스가 cpu를 독점하는 것을 막을 수 있다.

단점: context switch가 많아서 overhead가 발생할 수 있다.