[운영체제 -3] OS CPU Scheduling

Scheduling은 운영체제 학습 중 가장 중요한 항목 중 하나라고 해도 과언이 아니라고들 한다. OS가 하는 Scheduling이 무엇이고, 어떠한 것들이 있고, 그리고 어떠한 알고리즘을 통해서 수행하는지 확인해보자. 우선 Scheduling의 개요를 살펴보자.

 

일반적인 Process의 흐름

 

프로세스는 일반적으로 위 그림과 같은 흐름을 가지게 된다. 계속 CPU가 일을 하다가 IO가 등장해서 Waiting으로 가고, 또 CPU가 일을 하다가 IO가 등장해서 Waiting으로 가고 를 반복한다. 물론 어떤 도중이던 Interrupt가 발생해서 CPU를 뺏길 수는 있다. 이렇게 프로세스 내에서 CPU가 일을 하고 있는 시간을 CPU Burst라고 부르고, IO를 기다리고 있는 시간을 IO Burst 라고 부른다 (참고로 IO를 어려워 하는 분들이 있는데, 이름과 상관없이 Waiting이면 그냥 다 IO라고 생각하면 된다). Scheduling에서 중요한 관점은, 바로 Process 마다 이 CPU Burst, IO Burst의 빈도, 횟수, 길이가 모두 매우 다르다는 점이다. 프로그램마다 CPU만 진득하게 오래 쓰기도 하고, IO가 매우 많기도 하다 (보통 IO가 많이 일어나는 프로그램들이 많고, CPU만 진득하게 쓰는 프로그램은 매우 드물다).

 

항상 문제되는 것은 IO Bound Job 들이다. CPU만 쭉 쓰면 다들 쭉 쓰고 반납하고 하면 되는데, IO Bound Job들은 사람과의 Interaction을 하는 프로그램들이기 때문에 반응성이 중요하다. 만약 스케줄링이 진행되지 않고 CPU를 쭉 쓰고 받고 하게 된다면, CPU Bound Job들이 CPU를 계속 쓰게 되며 IO Bound Job은 수행되기가 매우 어려워지고, 이로 인해 사용자들의 UX는 매우 저하된다. 

 

이와 같이 CPU를 균등하게 배분시켜야 IO Bound Job들도 일을 수행할 수 있는데, 균등도 중요하지만, IO Bound Job들을 대상으로 사람과 상호작용하는 프로그램들이 너무 오래기다리지 않도록 하는 것도 매우 중요하다 (우선순위의 문제). 따라서, 어떤 순서대로, 어떻게 균등하게, 어떻게 효율적이게, 어떻게 합리적이게 CPU를 주고 뺏을 것이가에 대한 설계를 CPU Scheduling이라 한다. 

 

 

* 참고로, 나랑 같은 의문점이 드시는 분이 있을까봐 설명하자면, Scheduling 이 진행된다고 해도, 결론적으로 FIFO는 기반이다. 그러므로 Queue에 줄을 세운다는 뜻이 붙는 것이다. 예를들면 RR 기법 (이제 나옵니다) 으로 Scheduling을 한다 해도 FIFO 기반으로 알고리즘이 시행되므로, Queue 구조에 세워두는 것이다. "들어온 순서" 뿐만 아니라 "우선 순위"도 같이 판단한다고 해서 Queue란 자료구조를 굳이 사용하지 않을 이유가 없다는걸 이해하면 되는 것 같다.

 

 

CPU Scheduling, Dispatcher 와 Scheduling Algorithms

 

 

CPU Scheduling은 OS가 Ready State의 프로세스들 중에서 CPU를 줄 Process를 고르는 과정으로, OS가 수행하는 Scheduling 알고리즘 코드에 의해 수행된다. Scheduling 하는 시점은 Process State과 큰 연관이 있는데, Running > Waiting, Running > Ready, Waiting > Ready, Exit 등과 같은 시점에서 스케줄링이 필요하다. 이렇게 Scheduler에 의해 결정된 프로세스에게 CPU 제어권을 넘기는 것을 Dispatcher 라고 하는데, Context Switch를 필요에 의해 발생시킨다. 

 

지난번 포스트에서 확인했듯이, Scheduling에는 매우 중요한 두 가지 종류가 있는데, 바로 Process가 자진해서 CPU를 반납해서 진행하는 스케줄링인 Non-preemptive Scheduling, IR, Timer 등 강제로 CPU가 반납되어서 진행하는 스케줄링인 Preemptive Scheduling이 있다. 

 

Scheduler의 중요한 과제는 아까 잠깐 생각해봤듯이 모두에게 균등하고, 중요성을 고려하여 효율적인 Scheduling을 하는 것이다. 그럼 이 Scheduling의 적합성을 평가하는 척도 용어들 부터 알아보자. 

 

 

 

     (1) Scheduling 적합성 척도 (Criteria, Performance Index)

 

 

 

시스템 입장 - 얼마나 일을 잘 처리하는가가 중요함

 

이용률(Utilization) : 전체 시간 중 CPU가 실제 일을 한 시간을 말한다. 놀게 하지 않고 얼마나 일을 잘 시켰는가. 

처리량(Throughput) : 주어진 시간동안 몇 개의 일을 처리했는가. 

 

 

프로그램 입장 - 내가 빨리 CPU를 얻어서 빨리 끝내는 것이 중요함

 

소요시간(Turnaround Time) : CPU를 쓰기 위해 Ready Queue에 들어와서, 다 끝나고 나갈때까지 걸린 총 시간을 말한다.

대기시간(Waiting Time) : CPU를 기다리기 위해 Ready Queue에서 줄서서 기다린 시간을 모두 합한 시간을 말한다.

응답시간(Response Time) : Ready Queue에 들어와서 처음으로 CPU를 얻기까지 걸리는 시간을 말한다

 

 

 

 

     (2) Scheduling 알고리즘

 

 

 

FCFS (FIFO)

 

무조건 먼저 온 순서대로 처리하는, Queue의 정석 그대로를 말한다. 해당 알고리즘은 CPU를 강제로 뺏을 수 없는, 한가지 원리로 인해서 진행되는 Non-preemptive Scheduling 이다. 당연히 효율적이지 못하다. 처음 Scheduling의 개요에서도 알 수 있듯이, CPU Bound Job이 등장하면 끝도 없이 CPU를 사용할 수 있기 때문에, 늦게 도착한 CPU들은 CPU-starvation 현상이 발생하는데, 이를 Convoy Effect 라고 부른다. (Scheduling의 필요성이 시작된 이유이기도 함)

 

 

SJF (Shortest Job First)

 

Scheduling이 필요한 시점에서 CPU Burst가 가장 짧은 프로세스한테 제일 먼저 스케줄링을 주는 알고리즘을 말한다. 다같이 기다리는 시간 척도인 Waiting Time Avg 값이 가장 짧아지는 알고리즘으로 유명하다. 해당 알고리즘은 Preemptive, Non-preemptive한 두가지 방식이 있다. 

Non-preemptive : 진행중인 애보다 더 짧은 CPU Burst를 가진 애가 도착해도 넘겨주지 않는다

Preemptive : Process 가 도착할 때마다 판단, 만약 해당 시점에서 더 짧은 CPU Burst를 가진 애가 있으면 CPU를 넘겨준다. 이를 SRTF (Shortest Remaining Time First) 라고도 부른다. 

 

SRTF는 Waiting Time Avg 가 가장 짧아지고 이상적인 알고리즘이긴 하다. 하지만 큰 단점들이 존재한다. 

1) CPU Starvation : FIFO와는 반대의 Starvation이 발생할 수 있다. CPU Burst가 긴 친구가 어쨌든 열심히 기다려서 자기 차례가 되었는데, 갑자기 더 짧은 CPU Burst 가진 친구가 100개 넘게 들어온다고 생각하면, starvation을 겪게 된다. 

2) CPU 사용시간을 미리 알 수가 없고, 점화식으로 추정을 진행해야 한다. 따라서, 점화식을 진행하는 알고리즘이 엮여서 수행되어야 한다. 

 

 

Priority Scheduling

 

우선순위를 기준으로 Scheduling을 하게 되며, 우선 순위가 더 높은 Process가 도달할 경우 CPU를 뺏어서 주게 되는 Preemptive 한 scheduling이다. 우선 순위는 우선 순위 지표 (Priority Number) 값들을 같이 가지고 있는데, 이를 통해서 판단을 하게 된다. 이런 판단 기준이 간단한 알고리즘들과 동일하게, Starvation이 발생하게 된다. 하지만, 만약 Aging 기법을 사용하여 오래 기다렸으면 우선 순위를 높여주는 알고리즘이 추가된다면, Starvation 현상을 해결할 수 있는 기법이 되기도 한다. 

 

 

Round Robin (*) 

 

현재 대부분의 OS 들이 채택하고 있는 Scheduling 알고리즘으로, 당연히 Preemptive 한 스케줄링 기법이다. FIFO 기법을 기반으로, 각 Process 들에게 동일한 크기의 할당 시간(Time-Quantum)을 부여한다. Process 진행 중 할당 시간이 끝나면 (Timer H.W의 등장) CPU를 OS가 뺏게 되고, Ready Queue 맨 뒤에 가서 줄을 서게 된다. 

 

해당 기법의 가장 좋은 점은 Process 마다의 응답 시간(Response Time)이 매우 좋아져서, starvation 현상이 해소된다는 점이다. 또한, CPU Burst가 짧은 애들은 빨리 쓰고 나갈 수 있고, CPU 사용 예상 시간을 계산하지 않아도 된다. 그리고 RR 기법은 CPU 사용하려는 시간이 긴 애들은 길게 기다리게 되고, 짧은 애들은 짧게 기다리게 되는 균등성을 가진 알고리즘으로 유명하다. (Time Quantum (q) 설정에 따라서 성향이 매우 달라지는데, q가 매우 클수록 그냥 FIFO가 되는 것이고, q가 작을수록 context switch 오버헤드가 발생하게 된다)

 

 

지금까지 배운 4가지 알고리즘은 Ready Queue에 한줄로 서서, 각자의 판단 기준을 가지고 뒤로 보내고 순환시키고를 반복하면서 동작하는 방식이라고 봐도 된다. 위에서 말했지만, 그래서 기반이 Queue 인 것이다(개인적으로 이걸 이해하는게 제일 중요했던 것 같음. 왜 Queue인지 진짜 너무 이해가 안됐었음). 이제는 여러 줄을 통해서 대기를 시키는 방식들을 알아보자. 

 

 

Multi - Level Queue

 

Multi-Level Queue의 모습

 

Multi-Level Queue란 Ready Queue 자체를 여러개로 분할하여, 우선 순위별로 분배를 하는 것을 말한다. 위 그림에서와 같이 Process의 중요도는 분할되어 있으며, 시스템 관련 프로세스가 1위, 유저와 상호작용하는 프로세스가 2위이다. Process 들은 각자 본인이 속한 Priority 계급에 맞게 가서 줄을 서야 하고, 순위대로 CPU 할당이 분배된다. 이 순위는 바뀌지 않으므로, MLQ 역시 starvation 문제가 발생할 가능성이 있다.

 

따라서 철저히 우선순위대로 CPU를 분할하기보단, 각 큐에 CPU Time을 적절한 비율로 할당하기도 한다. 예를들어 foreground에는 1,2,3 순위와 같은 System, Interactive 한 Process (사실 System Process 는 무조건 IR 발생함) 들에게 80%의 할당 시간을 주고, CPU Burst Job 들 같은 Batch 용 Process 들을 background로 판단하고 20% 정도의 할당 시간을 주어, starvation 을 해소해주는 방식으로 CPU를 부여할 줄을 판단하기도 한다.  각 줄 내부에서 어떤 Process 에게 CPU를 부여할 것인지는 줄에 특성에 맞게 스케줄링 하는 경우가 많다. 가령, Foreground 분류 Process 들은 Interaction 이 중요하므로 Round Robin 스케줄링을 하되, Background 에서는 non-preemptive 한 scheduling 을 사용 (FCFS) 하여 CPU Change overhead 를 줄이기도 한다.  

무슨 소리냐면, Foreground 는 IO 들이 많이 발생해서 IR 가 계속적으로 발생할 것이므로, RR을 사용하여 공정하고 효율적인 알고리즘을 쓰지만, Background 는 IR이 많이 발생하지 않을거라서 굳이 시간제한을 두고 CPU를 뺏어가면서 CPU Change overhead 를 줄 필요가 없다는 얘기다. 따라서 CPU 사용을 보장해줄 수 있도록 non-preemptive 한 스케줄링을 사용하기도 한다

 

 

Multi-Level Feedback Queue (*)

 

Multi-Level Feedback Queue의 모습

 

 

이름은 Multi-Level Queue 와 유사하지만, 꽤나 다른 알고리즘으로 진행된다. MLFQ는 RR처럼 Queue 별로 Time-Quantum을 부여하게 된다. 그리고 처음 들어오는 Process 같은 경우는 항상 우선순위를 높게 줘서 높은 Priority Queue (그림상 1번 큐)로 들어가게 된다. 1번 Queue에서 할당된 시간 안에 종료되지 못했을 경우 두번째 줄로 옮겨진다. 각 큐 안에서는 Round Robin 알고리즘을 통해서 해당 큐에 있는 Process 들 간의 CPU 전환이 이루어진다. 

 

Round Robin 만으로도 부족하여, CPU Burst 시간이 짧은 애들은 자연스럽게 빨리빨리 처리하게 되어 Average Waiting Time 이 개선시킨 알고리즘이라고 보면 된다. 우선순위가 높은 Queue들은 RR 로 처리하고, 마지막 Queue 는 FCFS 로 처리하여 쭉 처리될 수 있도록 한다. MLFQ 방식은 RR를 기반으로 최적화된 알고리즘으로 보면 되고, 현재 RR, MLFQ 알고리즘들을 채택하여 운영체제가 운영된다고 생각하면 된다. 

 

 

지금까지 등장한 Scheduling 알고리즘들은 OS CPU Scheduling 에서 대표적이고 중요한 알고리즘들이며, 그밖에 다른 스케줄링 알고리즘들이 있는데, 다음과 같다. 

 

 

Multi-Processor Scheduling

 

해당 알고리즘은 Multi-Processor 즉, CPU가 여러개일 경우 적용되는 스케줄링이라고 생각하면 된다. 사실 화장실에서 볼 일 보는 자리가 한 자리 있든지, 두 자리 있든지 상관 없기 때문에 지금까지 배운 Scheduling 알고리즘들이 CPU 여러개일때 어떻게 동작을 시키는지를 확인하면 된다. Multi Processor Scheduling은 다음과 같은 종류가 있다는 정도만 알고 넘어가면 될 것 같다. 

 

1) Symmetric Multi Processing (Homogeneous Processor)

부착된 n개의 CPU가 H/W나 S/W 적으로 완벽히 동일한 경우를 말한다. 이런 경우 Queue를 한 줄 세우기 해서 알아서 꺼내가도록 하는 방식을 하기도 하지만, 특정 Processor에서 수행되어야 하는 프로세스가 있는 경우도 있다. 한 줄 세우기 없이 각 CPU들이 알아서 스케줄링 하기도 한다. 

 

2) Asymmetric Multi Processing

하나의 CPU가 Control CPU로 지정되어, 전체적인 Control을 담당하게 된다. 이 CPU는 시스템 데이터의 접근과 공유 등 중요한 일들을 책임지며, 나머지 CPU들은 Processing 등의 일을 수행하며 Control CPU의 지시를 따른다.

 

 

Real Time Scheduling

 

정해진 시간내 반드시 수행되어야 하는 기법을 말하며, Deadline에 대한 보장이 필요한다. 시간 기준이 매우 엄격한 Hard Type과, 높은 Priority 정도만 갖게하여 매우 엄격한 정도는 아닌 Soft Type으로 나뉜다. 예를 들어, OTT 서비스 같은 경우 동영상 데이터에 대한 처리가 유저에게 불편하지 않도록 높은 우선순위를 가져서 진행되어야 하지만, 조금씩의 miss는 불가피하게 판단한다. 

 

 

Thread Scheduling

 

Thread란 지난 포스트에서 배웠듯이, Process의 일꾼, 손이라고 보면 된다. 따라서 Thread Scheduling이란 말그대로 Process 안에서 동작하는 Thread들을 스케줄링 하는 것을 말한다. Thread Scheduling 도 두가지 관점으로 나뉘게 된다. 

 

1) Local Scheduling - User Level Thread

운영체제는 Thread의 존재를 모르고, 유저가 프로그램을 만들면서 관리하는 것을 말한다. 즉, OS는 그냥 Process에 대해서만 CPU 결정을 하고, 그 안에서 누구할테 줄지는 프로그램이 User Level에서 짜여진대로 진행한다.

 

2) Global Scheduling - Kernel Level Thread

운영체제가 Thread의 존재를 알고 있고, 직접 관리하는 것을 말한다. OS가 Process들을 스케줄링하듯, Process 내에서도 Thread들을 줄세워서 판단하여 어떤 Thread에게 줄지 직접 결정한다.  

 

 

OS Scheduling 알고리즘은 위에 확인한 부분들은 OS 과정에서 대표적으로 알려져 있는 알고리즘들로, 운영체제에 따라서 해당 알고리즘들을 기반으로 여러 경우에 따라 다양한 알고리즘을 적용한다. 즉, 컴퓨터 상에서 정말 많은 상황들이 발생하기 때문에, 다양한 알고리즘을 OS별로 최적화하여 사용한다고 보면 된다. 알고리즘의 최적성에 대한 평가는 1)Queueing Models, 2) Implementation & Measurement, 3) Simulation 등을 통해서 평가된다. 

 

대표적인 스케줄링 알고리즘들에 대해서 알고 있고, 알고리즘 예제 등 문제를 풀어보는 경험을 하면 좋을 것 같다. 

----------------

 

 

모든 출처:

 

1.이화여자대학교 반효경 교수님 운영체제 수업 (14학년도 1학기 수업)

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 

 

운영체제

 

2. 서울대학교 홍성수 교수님(RTOS Lab) 운영체제 수업 (S-DS 수업 자료)