CPU 스케줄링

CPU 스케줄링

cpu 스케줄링 : 어떤 프로세스 에게 cpu를 할당할지 결정하는 것

일반적으로 모든 프로그램은 cpu burst와 i/o burst를 반복하면서 실행이 된다. 프로그램의 종류에 따라서 burst가 빈번할 수도 있고 빈번하지 않을 수도 있는데 주로 사람과 상호작용하는 프로그램의 경우 burst가 빈번하고 과학적인 계산을 하는 프로그램의 경우 burst의 빈도가 적다. burst가 빈번한 프로그램을 i/o bound job이라고 하고 burst의 빈도가 적은 프로그램을 cpu bound job이라고 한다.

실제 PC에서는 이러한 job들이 굉장히 많이 섞여 있기 때문에 스케줄링의 필요성이 나타나다.

preemptive (선점형) vs nonpreemptive (비선점형)
preemptive : 강제로 cpu를 빼앗는 방식
nonpreemptive : cpu를 자발적으로 반납하는 방식

성능 척도

cpu 스케줄링을 평하기 위한 척도로는 크게 5가지가 존재한다.

• cpu 이용률
cpu 이용률은 전체 시간 중에서 cpu가 놀지 않고 실제 일한 시간을 의미한다. cpu는 굉장히 비싼 자원이기 때문에 최대한 놀지 않고 일을 시키는 것이 중요하다.

• 처리량
처리량은 일정 주어진 시간 동안에 몇개의 작업을 완료했는지를 의미한다.

이 2가지 성능 척도는 시스템 입장의 성능 척도로 단순히 cpu가 얼마나 많이 일하는지에 대한 정보에 해당한다.

• Turnaround Time (소요시간)
  소요시간은 cpu burst가 들어와서 작업을 진행 후 완료가 되어 i/o burst로 나갈때까지의 시간을 의미한다.

• Waiting Time (대기시간)
  일반적으로 cpu를 사용하려면 ready queue에 줄을 서서 cpu할당을 기다리게 되는데 이런 순수한 기다리는 시간을 대기시간이라고 한다.

• Respond Time (응답시간)
  응답시간은 ready queue에 들어온 프로세스가 처음으로 cpu를 얻기까지 걸리는 시간을 의미한다.

대기시간 vs 응답시간
대기시간과 응답시간은 유사한 개념이지만 다른 척도이다. 일반적으로 한 cpu 버스트 동안에도 cpu를 상요하다 뺏겼다 하는 것을 반복하게 되는데 이 때 cpu를 뺏길 때마다 생기는 기다리는 시간을 모두 합친 개념이 대기시간이다.
반면에 응답시간은 단순히 대기하다 가장 처음 cpu를 받게 되기 까지의 시간을 의미하며 대기시간 내에 포함된다.
추가적으로 소요시간은 전체 이런 시간들을 모두 합쳐서 작업이 완료되고 나가기 까지의 시간을 의미한다.

CPU 스케줄링 알고리즘

FCFS(First-Come First-Served)

FCFS : 먼저 온 순서대로 프로세스에 cpu를 할당하는 방식

현실 세계에서 가장 많이 사용되는 방식으로 비선점형 스케줄링 방식이다.

앞에 어떤 프로세스가 들어왔는 지에 따라 대기 시간에 많은 영향이 발생되는데 긴 프로세스가 먼저 들어오는 경우 평균 대기시간이 증가하지만 짧은 프로세스가 먼저 들어오게 되면 평균 대기시간이 줄어든다.

FCFS는 긴 프로세스가 들어오게 되면 작업을 완료할 때까지 다른 프로세스들이 기다려야 하는 문제점이 발생한다. 이런 문제를 convoy effect라고 부르며 그다지 좋은 스케줄링 방식은 아니다.

SJF(Shortest Job First)

SJF : cpu burst 시간이 가장 짧은 프로세스에 cpu를 할당하는 방식

SJF 방식은 cpu 사용 시간이 가장 짧은 프로세스에 cpu를 할당하는 방식으로 평균 대기 시간을 최소화할 수 있는 알고리즘이다.

SJF는 선점형이나 비선점형이냐에 따라 구분된다. 비선점형의 경우 프로세스 실행 중에 해당 프로세스 보다 더 짧은 cpu 사용 시간을 가진 프로세스가 들어와도 기존 프로세스의 cpu 사용권을 보장한다. 반면에 선점형의 경우 cpu 사용 시간이 더 짧은 프로세스가 들어오면 해당 프로세스에 cpu 사용권을 넘기며 선점형 방식에서 평균 대기 시간이 가장 최소화된다.

즉, 비선점형 방식의 경우 cpu를 다 쓰고 나가는 시점에 스케줄링을 결정하고 선점형 방식의 경우 새로운 프로세스가 도착하면 언제든지 스케줄링을 결정하는 방식이다.

priority scheduling (우선 순위 스케줄링)
우선순위 스케줄링 방식은 프로세스 별로 우선순위를 정해서 가장 높은 프로세스에 cpu를 할당하는 방식으로 SJF 방식이 우선순위 스케줄링 방식 중 하나이다.
즉, SJF 방식은 cpu 사용 시간에 따라 프로세스 별로 우선순위를 할당한 우선순위 스케줄링 방식인 것이다.

SJF의 문제점

SJF 알고리즘의 경우 2가지 주요한 문제점이 존재한다.

먼저 starvation이 발생할 수 있다. 만약 cpu 사용시간이 짧은 프로세스가 계속 ready queue로 들어온다고 가정해보자. 그렇다면 cpu 사용시간이 긴 프로세스들은 계속 밀리게 되어 cpu를 받지 못하게 된다. 이런 현상을 starvation이라고 한다.

aging 기법
aging 기법은 starvation을 해소하기 위한 기법으로 아무리 우선순위가 낮은 프로세스라고 하더라도 오래 기다리면 점점 우선순위를 높여서 언젠가는 높은 우선순위를 통해 cpu를 할당 받게 해주는 기법이다. 마치 사람이 노화를 하듯이 시간에 따라 우선순위가 높아진다 하여 aging 기법이라고 한다.

또 다른 문제로는 cpu 사용시간을 미리 알 수 없다는 것이다. 실제 컴퓨터 내 프로세스들을 cpu를 얼마나 사용할지 알 수 없다. 그렇기 때문에 사용시간을 과거에 cpu를 얼마나 사용했는지에 기반해 추정을 해서 사용을 하게 된다.

Round Robin

Round Robin : CPU에 할당 시간을 주어 스케줄링 하는 방식

현대적인 cpu 스케줄링 방식은 Round Robin 방식에 기반하고 있다. 이는 각 프로세스에 cpu를 할당 할 때 할당 시간을 지정해 그 시간이 끝나면 timer interrupt를 걸어 cpu를 뺏어 다음 프로세스에 전달하는 방식이다.

Round Robin 방식은 어떤 프로세스이든 적어도 한번은 cpu를 맛볼 수 있는 기회가 생긴다는 점에서 응답 시간이 빨라지는 방식이다.

Round Robin 방식에서는 할당 시간을 어떻게 정할지가 중요한데 너무 짧게 주게 되면 문맥 교환이 빈번하게 일어나 오버헤드가 커지는 문제가 발생하고 너무 길게 주게 되면 FCFS 알고리즘과 유사하게 동작되는 문제가 발생한다.

이런 대표적인 알고리즘 외에도 여러 queue를 만들어 우선순위별로 스케줄링하는 Multilevel Queue방식, 멀티 프로세서 상황에서의 스케줄링 방식, Realtime 스케줄링 방식, 스레드 스케줄링 방식 등 여러 방식이 존재한다.

스케줄링 알고리즘 평가

스케줄링 알고리즘을 적용하고자 할 때 어떤 스케줄링 알고리즘이 적합한지 판단하려면 각 알고리즘을 평가할 수 있어야 한다. 이런 평가 기준으로는 크게 3가지가 존재한다.

• Queuing model
  Queuing model은 도착률과 처리률을 통해 일종의 수식을 거쳐 계산을 진행하고 그 결과값을 통해 평가하는 방식으로 현대에는 많이 사용하지 않는 과거의 이론적인 방식이다.

• Implementaiton & Measurement
  Implementation & Measurement는 실제 시스템에 구현해서 돌려보고 측정하는 방식으로 주로 운영체제 커널을 직접 수정해 구현 후 알고리즘에 대한 성능 측정을 진행하는 방식이다. 커널 수정이 필요하다 보니 전문성이 필요해 쉽게 사용하기는 어려운 방식이다.

• 시뮬레이션
  Implementation & Measurement방식이 너무 어렵다 보니 모의 프로그램을 만들어 측정하고자 하는 알고리즘을 작성 후 해당 프로그램을 돌려 성능 측정을 하는 방식을 시뮬레이션 방식이라고 한다. 이 때 실제 프로세스의 cpu 버스트 패턴에 관련된 정보를 추출해서 시뮬레이션 프로그램의 입력값으로 집어넣어 테스트하는 것이 좋으며 이렇게 집어넣는 입력값을 trace라고 한다.