03. 운영체제 - CPU Virtualization (2)

Scheduling: Introduction

운영체제에서 스케줄링은 자원을 필요로하는 프로세스들에게 자원을 할당해주는 것을 말한다.

CPU 스케줄링은 적절한 스케줄링 정책을 통해 프로세스들에게 CPU time을 할당해주는 것이다.

앞서 CPU Time sharing에 의해서 CPU Virtualization이 이루어진다고 하였는데, 이때 어떻게 CPU time을 나누어가질 것인지에 대한 것이 스케줄링이다.

 

그러면 어떤 지표에 근거해서 스케줄링을 수행해야할까?

Scheduling Metrics

• Turnaround time (성능지표) : T(turnaround) = T(completion) - T(arrival)
• Fairness

Turnaround time은 시스템에 job이 들어온 시간과  job이 완료된 시간의 차이이다. turnaround time이 짧을수록 job이 요청된 후 빠르게 완료된다는 뜻이므로 성능이 높다고 할 수 있다.

또한 성능 뿐만 아니라 얼마나 공평하게 CPU 자원을 나눠갖는지에 대한 공평성(fairness)에 대해서도 고려해야한다.

성능과 fairness는 일반적으로 트레이드오프 관계를 갖는다. 

 

간단한 워크로드부터 시작해서 스케줄링 방법을 알아보자.

1. 모든 job은 동일한 시간동안 수행되고

2. 모든 job은 시스템에 동시에 도착하고

3. 모든 job은 CPU만 사용하고

4. 각 job의 수행시간을 알고있다.

라고 가정한다.

 

FIFO (First In, First Out)

Queue자료구조와 같이 먼저 들어온 job을 먼저 처리해주는 방식으로 FCFS(First Come, First Served)라고도 한다. 

위의 경우 평균 Turnaround time은 (10+20+30)/3 = 20 이다. (모든 job이 한번에 들어온다고 가정했으므로)

Convoy effect

FIFO는 구현이 간단하지만 문제점이 있다.

만약 각 job의 실행시간이 모두 동일하다는 1번 가정을 없애보자.

만약 제일 먼저 실행되는 job이 위와같이 엄청나게 긴 시간을 실행하게되면 뒤에오는 job들도 모두 함께 멈춰서 기다려야한다. 

이렇게 되면 평균 turnaround time은 (100+110+120)/3 = 110 이다.

이렇게 앞에 실행되는 job의 실행시간이 길어지면 기다리는 job들의 turnaround time도 함께 길어지는 문제가 convoy effect이다. 

 

SJF (Shortest Job First)

FIFO의 문제를 해결한 방법이다.

가정 4에서 각 job의 수행시간이 알려져있다고 하였으므로, 가장 실행시간이 짧은 job부터 실행하는 방법이다. 

예를 들어 위의 경우에 A job을 가장 마지막에 실행하고 B, C를 먼저 실행하게된다. 

그러면 평균 turnaround time은 (10+20+120)/3 = 50이 되어 성능이 개선된다. 

 

그런데 만약 2번 가정인 job이 한번에 들어온다는 가정을 제거하면, job이 아무때나 도착할 수 있게된다.

SJF의 경우는 비선점 스케줄링 방식으로, 중간에 실행시간이 더 짧은 job이 도착하더라도 현재 실행중인 job을 멈추지않는다. 

따라서 A가 먼저 들어와 실행되고 10초 후에 B와 C가 들어오게되면, 평균 turnaround time은 (100 + 100 + 110)/3 = 103.33 이 되어 여전히 convoy effect가 발생한다.

STCF (Shortest Time-to-Completion First)

위 문제를 해결하게 위해 SJF에 preemption 을 도입한 방식이 STCF 이다. 

preemption 이란 앞서 어떤 프로세스가 스케줄링 된후 실행되고 있더라도, 더 짧은 time-to-completion을 갖는 프로세스가 들어오면 이전 프로세스를 잠시 멈춰두고 새로운 프로세스를 우선 실행시킬 수 있도록 하는 것이다. 

STCF로 돌리면 위와 같이 스케줄링이 이루어지며, 평균 turnaround time은 (120 + 10 + 20)/3 = 50이 된다. 

 

Scheduling Metric : Response time

스케줄링의 또 다른 평가지표로 response time이 있다. 

• T(response) = T(firstrun) - T(arrival)

이는 job이 시스템에 도착한 시간과 처음으로 스케줄링된 시간의 차이이다.

SJF나 STCF같은 스케줄링 방식은 response time에 있어서 좋지 않은 성능을 보인다. 왜냐하면 실행시간이 긴 job은 계속해서 우선순위가 밀리기 때문이다.

 

Round Robin (RR) 

Round robin은 response time 측면을 고려한 스케줄링 방식이다.

일정 time slice (Scheduling quantum) 동안 한 job을 실행하고 시간이 지나면 다음 job을 수행하는 방식으로 모든 job들을 돌아가며 하나씩 수행하는 방식이다. 

Scheduling quantum은 반드시 타이머 인터럽트 주기의 배수가 되어야한다.

RR은 공평하며 response time 측면에서는 좋지만, turn-around time은 다소 길어질 수 있다.

• Time slice가 짧을수록
  • response time이 향상된다.
  • 하지만 너무 자주 context switching이 일어나며 context switching 비용이 전체 성능을 차지해버릴 수도 있다.
• Time slice가 길수록
  • reponse time 측면에서는 좋지 않다.
  • switching 비용을 줄일 수 있다.

Incorporating I/O

가정 3인 모든 job은 CPU만 사용한다는 가정을 없애보자.

job A와 B는 50ms의 CPU time을 필요로하고,

A는 10ms마다 I/O 요청을 보내는 상황을 생각하자. (I/O는 각각 10ms가 소요된다고 가정)

그리고 스케줄러에 의해 A가 더 먼저 실행된다면, 

위의 경우 A가 I/O를 기다리는 동안 CPU는 아무것도 하지 않고 낭비되는 상황이 생긴다.

이를 해결하기 위해

• job이 I/O 요청을 하면
  • I/O 가 완료될때까지 job은 block된다.
  • 그러면 스케줄러는 CPU에 다른 job을 스케줄링할 수 있게된다. 
• I/O 작업이 끝나면
  • 인터럽트가 걸리고, OS는 프로세스를 blocked에서 ready 상태로 변경해준다.

위와 같은 과정을 통해 중간에 I/O작업이 수행되더라도 CPU 사용을 최적화할 수 있다.