[OS] 프로세스를 스케줄링 하는 방법들 (Scheduling) - OS 공부 3

안녕하세요 Pingu입니다.

 

이번 글에서는 운영체제에서 프로세스를 실행할 순서를 설계하는 Scheduling(이하 스케줄링)에 대해 알아보려고 합니다! 제가 공부할 때 참고하고 있는 OSTEP 책에선 Chapter 7 - CPU Scheduling 부분입니다.

 

이번 글에서 배울 스케줄링 정책은 FIFO(First In First Out), SJF(Shortest Job First), STCF(Shortest Time-to-Completion First), RR(Round Robin)입니다. 그럼 바로 알아보겠습니다.

 

Scheduling Introduction

이제 저희는 프로세스를 실행하는 low-level 메커니즘들을 알고 있습니다. 예를 들면 Context Switch 같은 녀석들입니다. 아직 이런 부분을 잘 모르겠다면 여기를 참고해주세요! 그럼 모두 잘 이해했다는 가정 아래 이제는 OS 스케줄러가 사용하는 high-level 정책들을 알아보겠습니다. 스케줄링의 기원은 컴퓨터 시스템에서 비롯된 것이 아닌 여러 운영 관리 분야에서 비롯된 것들을 컴퓨터에 적용한 것입니다. 예를 들면 잠시 후 배울 FIFO 같은 경우 버스를 타려고 기다리는 사람들을 버스에 태우는 방법과 비슷하다고 볼 수 있습니다. 줄을 먼저 선 사람을 버스에 태우는 방법이 바로 FIFO 방식입니다. 이렇게 실제 생활의 스케줄링 방법을 컴퓨터 시스템으로 가져온 기법들을 설명하기 위해 몇 가지 가정을 정의할 건데요, 이는 다음 섹션에서 알아보도록 하겠습니다.

 

Wokrload assumption

그럼 스케줄링 정책을 이해하기 위해서 몇 가지 가정을 정의해 보겠습니다. 여기서 가정하는 부분의 내용을 wordload라고 부르며 workload를 많이 알 수록 스케줄링 정책을 잘 설계할 수 있습니다. Workload의 뜻을 다시 짚고 가자면 사전적으로는 작업량이라고 볼 수 있고 컴퓨터 과학의 입장에서 보면 하나의 프로세스의 특징들을 고려해 얼마만큼 자원을 필요로 하느냐를 뜻합니다. 지금 정의하는 workload 가정들은 비현실적이지만 하나씩 알아가 보며 이러한 가정들을 제거할 거예요. 그럼 지금 정의할 가정들을 살펴보겠습니다.

• 모든 작업은 한 번 실행될 때 실행시간이 동일하다.
• 모든 작업은 동시에 도착한다
• 작업이 시작되면 끝날 때까지 실행한다.
• 모든 작업은 CPU에서만 작동한다. I/O를 발생시키지 않는다.
• 모든 작업의 실행시간을 알고 있다.

어떠신가요? 읽기만 하셔도 비현실적이지 않나요? 이러한 가정을 하는 이유는 설명을 좀 더 직관적으로 하기 위함입니다. 설명을 하다가 이러한 가정들을 하나씩 제거하며 설명하도록 하겠습니다!

 

Scheduling Metrics

Workload 가정을 세웠으니 이제는 스케줄링 정책들을 비교하는 기준을 알아보겠습니다. 이를 scheduling metric라고 합니다. 그럼 기준들을 알아볼까요?

• Turnaround Time (반환 시간)
  • Turnaround Time = Completion Time - Arrival Time
  • 반환 시간은 프로세스가 완료된 시간에서 프로세스가 도착한 시간을 뺀 시간입니다. 즉 어떤 프로세스가 완료될 때까지 걸린 시간이라고 보면 됩니다.
• Response Time (응답 시간)
  • Response Time = FirstRun Time - Arrival Time
  • 응답 시간은 프로세스가 처음 실행되는 시간에서 프로세스가 도착한 시간을 뺀 시간입니다. 예를 들어 P1 프로세스가 0초에 도착하여 5초에 처음 실행되었다면 응답 시간은 5초가 됩니다.
• Fairness (형평성)
  • 여러 개의 프로세스들의 완료 시간이 얼마나 비슷한지 비교하는 기준입니다. 예를 들어 P1 프로세스는 10초 만에 완료되었고 P2 프로세스는 1초 만에 완료되었다면 Fairness가 좋지 못한 스케줄러라고 볼 수 있습니다.
• Throughput 
  • 단위 시간당 완료된 프로세스 수
• Deadline (마감 시간)
  • Turnaround Time < Deadline Time
  • 실시간 시스템에서 주로 사용되며 프로세스가 완료되는 시간이 Deline Time보다 작아야 한다는 조건이 있습니다.

이러한 조건들로 스케줄링 정책들을 비교할 수 있습니다. 이번 글에서는 Turnaround Time (반환 시간)을 중점적으로 다루려고 합니다. 이러한 조건들은 어떤 작업에 따라 중요도가 달라질 수 있습니다. 예를 들어 응답 시간이 평균적으로 5초인 스케줄러로 설계된 컴퓨터를 사용한다고 가정하겠습니다. 그러면 사용자가 마우스를 움직이거나 키보드를 입력할 때 바로 움직이지 않고 5초 뒤에 움직이게 되는 것입니다. 이러한 상황을 렉이 걸렸다고들 합니다. 즉 이런 조건들을 잘 조절해서 좋은 스케줄러를 만들어야 할 것 입니다. 그럼 이러한 부분을 고려하며 실제 스케줄링 기법들을 하나씩 살펴보도록 하겠습니다.

 

FIFO (First In, First Out)

가장 간단한 알고리즘인 FIFO는 자료구조에서 Queue와 같은 원리를 가진 스케줄링 기법입니다. 이름에서도 알 수 있듯 처음 들어온 게 처음 실행된다는 말입니다. 즉 들어온 작업이 무엇이든 간에 먼저 들어온 작업이 있다면 그 작업이 수행된 뒤에 새로 들어온 작업이 수행됩니다. 예를 보며 이해해보겠습니다.

위의 그림에는 A, B, C 프로세스가 있습니다. 이들은 모두 0초에 도착했고 완료되는데 필요한 시간은 모두 10초입니다. 도착한 시간이 동일하다면 알파벳순으로 실행한다는 규칙도 있다고 가정할 때 FIFO 스케줄링 기법을 사용해서 프로세스를 수행하면 위와 같은 시간 그래프가 나타나게 됩니다. 그럼 여기서 Turnaround Time과 Response Time을 한 번 구해볼까요?

 

A는 0초에 도착해서 0초에 시작했고 10초에 완료되었습니다. 따라서 Turnaround Time은 10초, Response Time은 0초입니다.

B는 0초에 도착해서 10초에 시작했고 20초에 완료되었습니다. 따라서 Turnaround Time은 20초, Response Time은 10초입니다.

C는 0초에 도착해서 20초에 시작했고 30초에 완료되었습니다. 따라서 Turnaround Time은 30초, Response Time은 20초입니다.

평균을 구해보면 Turnaround Time의 평균은 20초, Response Time의 평균은 10초가 됩니다.

 

아직은 FIFO 밖에 모르니 이게 좋은지 나쁜지는 모르겠습니다. 그럼 다른 예를 보겠습니다. 이번 예를 보기 위해서는 아까 정의한 가정 중 하나인 "모든 작업은 동일한 수행 시간을 갖는다"를 없애야 합니다. 이 가정을 없앤 예를 살펴보겠습니다.

위의 예는 A, B, C가 모두 0초에 도착했고 도착시간이 동일하면 알파벳 순으로 실행되는 것도 동일합니다. 하나 다른 점은 A에게 필요한 시간이 100초라는 점입니다. (B, C는 아까와 동일하게 10초입니다.) 이런 작업의 경우 FIFO를 사용했을 때 Turnaround Time과 Response Time을 구해보겠습니다!

 

A는 0초에 도착해서 0초에 시작했고 100초에 완료되었습니다. 따라서 Turnaround Time은 100초, Response Time은 0초입니다.

B는 0초에 도착해서 100초에 시작했고 110초에 완료되었습니다. 따라서 Turnaround Time은 110초, Response Time은 100초입니다.

C는 0초에 도착해서 110초에 시작했고 120초에 완료되었습니다. 따라서 Turnaround Time은 120초, Response Time은 110초입니다.

평균을 구해보면 Turnaround Time의 평균은 110초, Response Time의 평균은 70초입니다. 

 

FIFO의 단점이 보이시나요? 위의 예처럼 시간이 많이 필요한 작업이 먼저 수행된다면 뒤에 도착하는 빨리 끝날 수 있는 작업들이 수행되지 못하게 됩니다. 이러한 단점을 convoy effect라고 합니다. B, C의 입장에서 보면 자신이 먼저 수행되는 게 이득인데 A 때문에 수행되지 못해서 화가 날수도 있습니다. 이러한 문제는 어떻게 해결해야 할까요? 수행 시간이 짧은 애들부터 수행해버리면 해결 할 수 있을까요? 그럼 그 방법으로 다음 섹션에서 한 번 해보겠습니다.

 

SJF (Shortest Job First)

이번에는 아까 FIFO에서 발생한 convoy effect를 해결하는 방법으로 수행시간이 짧은 애들부터 수행하려고 합니다. 이러한 방법을 SJF (Shortest Job First)라고 하며 아까는 동일한 시간에 도착한 프로세스들을 알파벳 순서로 수행했지만 이번에는 수행시간이 짧은 프로세스부터 수행해보겠습니다. 아 참고로 SJF는 SPN(Shortest Process Next)라고도 불립니다!

아까 FIFO에서 본 예를 SJF로 수행해보겠습니다. 아까의 예를 다시 알려드리면 A,B, C는 모두 0초에 도착했고 A는 100초, B,C는 10초의 시간이 필요합니다. 아까와 다른 점은 동시에 도착했을 때 알파벳 순으로 수행하는 것이 아닌 수행 시간이 짧은 애들을 먼저 실행할 거예요. 이번에도 Turnaround Time, Response Time을 구해보겠습니다!

 

A는 0초에 도착해서 20초에 시작했고 120초에 완료되었습니다. 따라서 Turnaround Time은 120초, Response Time은 20초입니다.

B는 0초에 도착해서 0초에 시작했고 10초에 완료되었습니다. 따라서 Turnaround Time은 10초, Response Time은 0초입니다.

C는 0초에 도착해서 10초에 시작했고 20초에 완료되었습니다. 따라서 Turnaround Time은 20초, Response Time은 10초입니다.

평균을 구해보면 Turnaround Time의 평균은 50초, Response Time의 평균은 10초입니다.

 

어떤가요? 아까 FIFO로 동일한 작업을 수행했을 때(Turnaround Time의 평균은 110초, Response Time의 평균은 70초)와 비교하면 훨씬 좋아지지 않았나요? Turnaround Time의 평균이 줄어들게 된 것을 볼 수 있습니다. 이렇게 SJF는 항상 가장 짧은 프로세스를 먼저 실행하기 때문에 항상 최적의 Turnaround TIme을 가져다줄 수 있습니다. 하지만 단점은 이를 바로 없애 버릴 정도로 큽니다. 이 단점을 이해하기 위해서는 아까 정의한 가정중 하나인 "모든 작업은 동일한 시간에 도착한다"를 없애야 합니다. 그럼 이를 없앤 예를 보며 단점을 이해해보겠습니다.

위의 예에서 달라진 점은 B, C의 도착시간이 0초가 아니고 10초라는 점입니다. 즉 A는 0초에 도착한 100초짜리 작업, B, C는 10초에 도착한 10초짜리 작업입니다. 0초에서 SJF로 프로세스들을 스케줄링 하려고 봤더니 A프로세스만 존재합니다. 그래서 A를 수행합니다. 10초에 B,C가 도착하지만 아까 정의한 가정때문에 작업은 한 번 실행되면 멈출 수 없습니다. 그래서 결국 B,C는 겨우 10초를 늦은 이유로 A가 모두 수행되기를 기다려야 합니다. 이 예에서도 Turnaround Time, Response Time을 구해보겠습니다.

 

A는 0초에 도착해서 0초에 시작했고 100초에 완료되었습니다. 따라서 Turnaround Time은 100초, Response Time은 0초입니다.

B는 10초에 도착해서 100초에 시작했고 110초에 완료되었습니다. 따라서 Turnaround Time은 100초, Response Time은 90초입니다.

C는 10초에 도착해서 110초에 시작했고 120초에 완료되었습니다. 따라서 Turnaround Time은 110초, Response Time은 100초입니다.

평균을 구해보면 Turnaround Time의 평균은 약 103.3초, Response Time의 평균은 60.3초입니다.

 

어떤가요? 단점이 바로 보이시나요? 어떤 작업이 현재 수행되고 있는 작업보다 짧아도 늦게 도착하면 수행되기 위해 기다려야 합니다. 이러한 문제를 어떻게 해결할 수 있을까요? 다음 섹션에서 알아보겠습니다!

 

STCF (Shortest Time-to-Complition First)

아까 SJF의 단점을 보완하는 방법이 STCF(Shortest Time-to-Completion First)입니다. STCF는 SRT(Shortest Remaining-Time next)라고도 불립니다. 이를 정의하기 위해서는 이제 아까 정의한 가정을 하나 없애야 합니다. 없앨 가정은 "작업이 시작되면 끝날 때까지 실행한다."입니다. 또한 스케줄러에 timer interrupt와 context switch 기능을 추가합니다. 이에 따라 이제 STCF 스케줄러는 preempt(선점) 스케줄러가 됩니다. 선점 스케줄러라는 것은 어떤 작업을 수행하는 도중에 다른 작업을 수행할 수 있도록 스케줄링할 수 있는 스케줄러를 말합니다. 지금까지의 스케줄러들은 모두 non-preemptive 스케줄러였기 때문에 아까 SJF와 같은 문제가 발생했었습니다.

 

그럼 이제 선점 스케줄러인 STCF를 살펴보겠습니다. 아까 SJF에서 문제가 발생했던 예를 그대로 가지고 와서 STCF로 실행시켜보겠습니다. 우선 아까의 예는 100초가 걸리는 A는 0초에 도착하고 10초가 걸리는 B, C는 10초에 도착했었습니다. 하지만 비선점 스케줄러인 SJF에서는 B, C가 도착한 10초 시점에 A를 작동하고 있었기 때문에 A보다 더 일찍 끝낼 수 있는 B,C가 A가 끝나기를 기다려야만 했습니다. 아래의 그림은 STCF로 동일한 예를 동작시킨 결과입니다.

위의 그림에서 볼 수 있듯 STCF는 10초에서 A를 계속 수행하는 것이 아닌 그 시점에서 가장 빨리 수행될 수 있는 B,C가 먼저 수행되는 것을 볼 수 있습니다. 그럼 STCF를 사용한 예의 Turnaround Time, Response Time은 어떻게 될까요?

 

A는 0초에 도착해서 0초에 시작했고 120초에 완료되었습니다. 따라서 Turnaround Time은 120초, Response Time은 0초입니다.

B는 10초에 도착해서 10초에 시작했고 20초에 완료되었습니다. 따라서 Turnaround Time은 10초, Response Time은 0초입니다.

C는 10초에 도착해서 20초에 시작했고 30초에 완료되었습니다. 따라서 Turnaround Time은 20초, Response Time은 10초입니다.

평균을 구해보면 Turnaround Time의 평균은 50초, Response Time의 평균은 3.3초입니다.

 

아까 SJF를 사용할 때 보다 더 효율적으로 동작하는 것을 볼 수 있습니다!

 

SJF와 STCF의 차이를 다시 보겠습니다.

위처럼 STCF를 사용하면 B, C가 빨리 수행되는 것을 볼 수 있습니다.

 

사실 지금까지는 Turnaround Time을 줄이는 방식으로 스케줄러를 소개했습니다. 하지만 아까 Response Time을 설명할 때 말한 것처럼 Response Time도 아주 중요한 비교 기준입니다. 그럼 다음 섹션에서 Response Time을 줄이는 방법을 같이 생각해보겠습니다!

 

Response Time

스케줄링 정책을 비교하는 방법에 Turnaround Time, Response Time이 있다는 것은 위에서 설명했습니다. 그리고 지금까지 이어진 FIFO -> SJF -> STCF의 순서대로 소개된 스케줄러들은 모두 Turnaround Time을 줄이는 것에 중점을 둔 순서였습니다. 지금까지 배운 스케줄링 방법 중 STCF는 만약 모든 작업의 수행 시간을 알고 있고 작업이 CPU에서만 사용되며 측정 항목 중 Turnaround Time이 가장 중요하다면 훌륭한 방법이 될 것입니다. 이러한 부분은 초창기 컴퓨터에서 사용한 batching system에서는 좋은 방법입니다. 하지만 요즘의 컴퓨터들에는 time sharing 기법이 도입되었고 사용자는 여러 개의 프로그램을 한 번에 동작시킬 수 있게 되었고 사용자 상호작용도 중요하게 생각합니다. 이런 시스템을 Interactive System이라고 합니다. 때문에 Turnaround Time가 가장 중요하다고 볼 수는 없게 되었습니다. 즉 Response Time도 고려를 해줘야 하는 것이죠!

 

그럼 SJF의 Response Time을 한 번 살펴보겠습니다.

위의 예는 A, B, C가 0초에 동시에 도착했으며 모두 5초의 실행시간을 가진 작업입니다. 이러한 작업을 SJF로 실행하게 되었을 때 Response Time을 한 번 구해보겠습니다.

 

A는 0초에 도착해서 0초에 시작했기 때문에 Response Time은 0초입니다.

B는 0초에 도착해서 5초에 시작했기 때문에 Response Time은 5초입니다.

C는 0초에 도착해서 10초에 시작했기 때문에 Response Time은 10초입니다.

평균 Response Time은 5초입니다.

 

만약 B, C작업이 마우스, 키보드 동작이었다면 어떻게 될까요? 사용자가 마우스를 움직인 지 5초 만에 움직이고 키보드로 입력한 지 10초 뒤에 입력이 된다면... 아무도 컴퓨터를 사용하지 않을 것 같아요... 그럼 어떻게 해야 이런 문제를 해결할 수 있을까요? Response Time을 작게 하는 방법이 바로 다음 섹션에서 소개될 Round Robin 기법입니다!

 

RR (Round Robin)

앞에서 말한 Response Time을 작게 할 수 있는 방법이 바로 이번에 소개할 Round Robin 방법입니다. RR은 어떤 작업이 수행될 때 끝날 때까지 수행하는 것이 아닌 정해진 시간(time slice, scheduling quantum)만큼만 수행합니다. 정해진 시간을 수행한 뒤에는 다른 작업을 수행하게 됩니다. 그럼 아까 위에서 본 예를 다시 가지고 와서 RR로 처리해보겠습니다.

 

아까 예를 기억 못 하실까 봐 다시 알려드리면 A, B, C가 0초에 동시에 도착했으며 모두 5초의 실행시간을 가진 작업입니다. 이를 time slice가 1초로 설정된 RR로 처리하면 아래와 같이 결과가 나타나게 됩니다.

어떤가요? SJF와 차이가 느껴지시나요? 그럼 time slice가 1초로 설정된 RR을 사용했을 때의 Response Time을 구해보겠습니다.

 

A는 0초에 도착해서 0초에 시작했기 때문에 Response Time은 0초입니다.

B는 0초에 도착해서 1초에 시작했기 때문에 Response Time은 1초입니다.

C는 0초에 도착해서 2초에 시작했기 때문에 Response Time은 2초입니다.

평균 Response Time은 1초입니다.

 

참고로 아까 SJF로 동일한 예를 작동했을 때는 평균 Response Time이 5초였습니다. 근데 지금은 1초로 줄었습니다! 정말 엄청난 발전이군요. Response Time에서는 정말 대단한 성능 향상이 있었습니다. 하지만 마우스를 움직이는데 1초나 걸린다면 아직도 만족스럽지는 않습니다. 더 줄이고 싶다면 어떻게 해야 할까요? 바로 time slice를 줄이면 됩니다. 만약 time slice가 0.01ms라고 해보겠습니다. 그럼 마우스를 움직이면 0.01초 만에 움직이게 될 겁니다! 그렇다면 time slice를 최대한으로 줄이는 게 마냥 좋을까요?? 그렇지는 않습니다. Time slice가 너무 작게 되면 context switch가 너무 자주 발생하게 되고 context switch을 하는데 필요한 비용이 전체 성능에 큰 영향을 끼칠 수 있게 됩니다. 즉 정말 간단한 작업인데도 불구하고 time slice가 너무 작아서 작업 수행에 필요한 비용보다 context switch 비용 때문에 성능이 크게 저하될 수 있습니다. 배보다 배꼽이 큰 상황이 발생하는 것이죠. 따라서 적당한 time slice를 설정해 주는 것이 중요합니다. 

 

그럼 RR을 사용하면 Turnaround Time은 어떻게 될까요? 위의 예에서 바로 한 번 알아보겠습니다.

A는 0초에 도착해서 13초에 완료되었기 때문에 Turnaround Time은 13초입니다.

B는 0초에 도착해서 14초에 완료되었기 때문에 Turnaround Time은 14초입니다.

C는 0초에 도착해서 15초에 완료되었기 때문에 Turnaround Time은 15초입니다.

평균 Turnaround Time은 14초가 됩니다.

 

아까 SJF를 수행했을 때 평균 Turnaround Time은 참고로 10초였습니다. RR을 사용하니 Turnaround Time은 더 나빠졌습니다. 즉 RR이 모든 기준에서 가장 좋은 방법이 아니라는 것을 알 수 있습니다. 사실 Turnaround Time만 보게 되면 아주 간단한 FIFO보다도 성능이 나빠질 수 있습니다.

 

지금 까지 알아본 방법들은 크게 2가지로 나눌 수 있습니다. 첫 번째 유형인 SJF, STCF는 Turnaround Time을 최적화하지만 Response Time은 좋지 않습니다. 두 번째 유형인 RR은 Response Time은 좋지만 Turnaround Time이 좋지 않습니다. 따라서 둘의 관계는 반비례관계로 책에는 이를 이렇게 표현했습니다. "You can't have your cake and eat it too" 즉 둘 중 하나는 어느 정도 포기해야 한다는 뜻 같습니다.

 

혹시 스케줄링을 설명하기 위해 정의한 5개의 가정을 기억하시나요? 지금까지 저희는 3개의 가정을 모두 없앴고 2개만 남았습니다. 2개의 가정을 다시 한번 보자면 "모든 작업은 CPU에서만 작동되며 I/O를 수행하지 않는다", "모든 작업의 수행 시간을 알고 있다"입니다. 이게 남은 2개의 가정을 없애봐야겠죠? 

 

Incorporating I/O

그럼 2개의 가정 중 하나인 "모든 작업은 CPU에서만 작동되며 I/O를 수행하지 않는다"를 먼저 없애 보겠습니다. 스케줄러는 어떤 작업이 I/O 요청을 시작할 때 결정을 내릴 수 있습니다. I/O 작업은 CPU를 사용하지 않기 때문입니다. 즉 I/O 작업이 수행되는 동안에는 CPU를 차단해야 합니다. 이렇게 I/O를 수행 중일 때 CPU를 차단하는 방식을 Busy Waiting 방법이라고 합니다. 예를 들어 하드디스크에 어떤 데이터를 저장하려고 할 때 데이터의 크기가 커서 오래 걸리게 된다면 CPU가 오랜 시간 일을 하지 않는 상태가 될 수 있습니다. 따라서 I/O 작업이 수행되는 동안 CPU에서는 다른 작업을 수행해야 합니다. 이렇게 I/O 작업이 수행되는 동안 CPU가 다른 작업을 수행하도록 하는 것을 Blocked라고 합니다. 스케줄러는 I/O가 완료되는 시기도 결정해야 합니다. 이 경우 인터럽트가 발생하고 I/O를 발생시킨 작업은 다시 Ready 상태로 돌아가야 합니다. 이렇게 I/O가 발생할 때 처리해야 하는 부분을 OS는 어떻게 처리할 수 있을까요?

 

우선 이런 문제를 이해하기 위해 예를 보겠습니다.

위의 예에서는 A, B 두 개의 작업이 존재합니다. A 작업과 B 작업은 모두 50초의 수행 시간을 가지고 있습니다. 그리고 A 작업은 10초마다 I/O를 발생시킵니다. 여기서 발생하는 I/O는 모두 10초씩 걸린다고 가정하겠습니다. 이때 만약 스케줄러가 I/O가 발생하는 동안 A 작업이 계속 CPU를 차지하고 있고 다른 작업이 접근하는 것을 차단한다면 위의 그림과 같은 결과가 발생합니다. 이러한 방법을 Busy Waiting 방법이라고 합니다. 이는 CPU가 I/O 작업을 수행하는 동안 놀게 되는 문제가 발생합니다.

바로 위에서 본 예와 동일한 작업에서 I/O를 수행하는 동안 A 작업이 CPU를 포기하고 B에게 CPU를 할당해주는 방식을 택한 경우입니다. 이런 방법을 Blocked 방법이라고 하며 이렇게 하면 아까 Busy Waiting 방법보다 훨씬 빠르고 효율적으로 작업을 수행할 수 있게 됩니다. 이렇게 하기 위해서는 이전에 작성한 글인 Process의 상태 전이 부분에서 알아본 개념을 사용해야 합니다.

위와 같은 상태 전이 그림을 참고해서 설명하도록 하겠습니다.

Busy Waiting 방법에서는 A 작업이 Running 상태에서 실행을 하다가 I/O를 발생시키면 상태가 변하지 않고 계속 Running 상태를 유지합니다. 따라서 B 작업이 수행될 수가 없게 됩니다. 

Blocked 방법에서는 A 작업은 실행이 되다가 I/O를 발생시키면 Blocked 상태가 되는 것입니다. 따라서 I/O가 수행 중일 때 B는 Ready 상태에서 Running 상태가 되고 I/O를 완료하면 A가 Ready가 되고 다시 스케줄링될 수 있는 상태가 됩니다.

 

지금은 하나의 작업만 I/O를 발생시켰습니다. 그럼 만약 여러 개의 작업에서 I/O를 발생시킨다면 어떻게 해야 할까요? 이에 대한 답은 다음 글에서 알아보도록 하겠습니다.

 

No More Oracle

그럼 이제 하나의 가정만 남았습니다. 바로 "모든 작업의 수행 시간을 알고있다" 입니다. 실제로 저희는 모든 작업의 수행시간을 알수 없습니다. 지금까지 알아본 SJF, STCF와 같은 방법은 수행시간을 알아야 사용할 수 있었습니다. 따라서 어떤 프로세스가 만들어졌을 때 OS에게 이 프로세스의 수행시간을 알려줘야 하는데 이는 어떻게 알려줄 수 있을까요?

 

사용자가 알려주는 것이 가장 좋겠지만 항상 그럴 수는 없기 때문에 예측을 통해 알려주게 됩니다. 예측은 exponential moving average(지수 이동 평균)라는 방법으로 할 수 있습니다.

위의 식과 그래프가 지수 이동 평균을 나타냅니다. 위의 그래프를 보면 예측값이 실제값을 잘 따라가는 것을 볼 수 있습니다. 

 

Summary

이번 글에서는 스케줄링의 기본 아이디어를 소개하고 두 가지의 접근 방식을 소개했습니다. 하나는 Turnaround Time을 최적화하는 방법이고 다른 하나는 Response Time을 최적화하는 방법이었습니다. 또한 I/O를 처리하는 방법에 대해서도 알아보았습니다. 하지만 아직 OS가 미래를 예측할 수 없는 근본적인 문제를 해결하진 못했습니다. 따라서 과거의 정보를 사용하여 미래를 예측하는 스케줄러를 구축하여 이런 문제를 해결해야 합니다. 이러한 해결방법은 MLFQ(Multi Level Feedback Queue)라는 스케줄러로 다음 글에서 알아보도록 하겠습니다!

 

감사합니다!