운영 체제 (Operating System) - CPU Scheduling

1. 스캐줄링의 개념

어떻게 Process에 자원을 할당할 것인지에 대한 정책으로, Multiprogramming에서 기반했다고 한다. 잠시 2강에서 배웠던 Multiprogramming의 개념에 대해서 다시 살펴보고 가자. Multitasking으로 발전 전에 I/O로 인한 CPU Idle 상태 시간을 줄이고자 등장한 방식으로, 실행중인 프로세스가 I/O상태가 된다면, 다른 Job을 동시에 실행하는 방식이었다. (CPU와 I/O를 동시에 실행할 수 있는 것은 5강에서 배운 DMA라는 추가 HW덕분으로 추정된다) 

이때 Job의 queue에서 어떤 Job을 실행해야 할 지 선택할 기준이 필요하다. 어떻게 CPU사용률과 처리량의 극대화하여 프로세스에게 CPU사용을 할당해야 하는가?를 담당하는 것이 스케줄링이다. (추가로 이땐 스케줄링으로도 공평성이나 Priority를 수행하지 못했고, Time sharing방식이 도입되서야 이 문제가 해결되었다)

그렇다면 효율적인 스케줄링이란 무엇일까? 이는 Process의 특성에 따라서 다르다. 예를 들어 주기가 짧지만 CPU 수행 시간(CPU Burst)이 긴 CPU-Bound Process와 I/O 처리 시간(I/O Burst)가 길어 주기가 길지만 CPU수행시간(CPU Burst)이 짧은 I/O-Bound Process로 Process를 분류하자면 어떤 종류의 Process가 많냐에 따라서 스케줄링 기법의 효율성은 달라질것이다. 한 종류의 Process에 특화된 시스템도 분명히 필요하지만, 스케줄링이 일반적인 경우에 높은 효율성을 가져야 하므로 프로세스의 Burst time과 Frequency를 분석하였다.

분석 결과 서로 다른 Process이고 System임에도 대체로 위와 같은 경향을 보였고, 이를 기반으로 스케줄링을 분석하였다. (대체로 3~5의 bursttime을 갖는 프로세스가 많더라~)

 

 

2. 스케줄링의 메카니즘

스케줄링의 결정이 언제 이루어지냐에 따라서 스케줄링은 비선점형 스케줄링(Non-preemptive scheduling)과 선점형 스케줄링(Preemptive scheduling)으로 나뉜다. 만약에 스케줄러가 1) Running->Waiting 혹은 2)Ready->Running로 변화할 때만 결정한다면 즉, Multiprogramming과 같이 OS가 강제로 CPU사용을 해제하지 못하고 I/O나 실행 때만 스케줄링 한다면 이를 비선점형 스케줄링(Non-preemptive scheduling)이라고 한다. 그 외에 OS가 현재 CPU를 사용하고 있는 Process의 수행을 정지할 수 있다면 즉, Running->Ready로 상태를 변화시킬 수 있을 때 이를 활용하는 스케줄링 방식을 선점형 스케줄링(Preemptive scheduling)이라고 한다. 이거 조금 햇갈렸는데 실행중인 프로세스가 CPU를 완전히 선점한다는 뜻이 아니라, Ready 상태의 프로세스가 실행 중인 프로세스를 선점할 수 있다는 점에서 선점형 스케줄링이라 표현한다고 한다. (용어가 너무 햇갈린다 ㅠ)

이제 효율적인 스케줄링을 알기 위해 효율의 기준을 알아보자. 여기에는 CPU 사용률(CPU Utilization), 처리량(Throughput), 응답 시간(Response time), 대기시간(Waiting time), 전체 실행 시간(Turnaround time)이 포함된다. 시스템의 용도에 따라서 효율의 기준이 다르기 때문에 우선 우리는 개인 컴퓨터가 중시하는 응답시간과 대기시간을 바탕으로 진행해볼것이다.

 

 

3. 스케줄링 알고리즘

다양한 방식의 스케줄링이 존재한다. 여기서는 다음과 같은 알고리즘들을 살펴볼 것이다.

First-Come, First-Served Scheduling

Shortest-Job-First Scheduling

Priority Scheduling

Round-Robin Scheduling

Multilevel Queue Scheduling

Multilevel Feedback Queue Scheduling

각 알고리즘의 메카니즘을 알아보고 효율성에 대해서 알아보자.

 

3-1. First-Come, First-Served Scheduling

가장 먼저 CPU할당을 요청한 프로세스에 CPU를 먼저 할당하는 방식이다. FIFO Queue를 활용하여 간단하게 구현 가능하고, 들어온 순서가 기준이므로 비선점형이다. 다음은 평균 대기시간에 대한 예시이다.

이처럼 작업의 수행 순서에 따라 대기 시간이 변할 수 있다는 특징을 갖는다.

 

 

3-2. Shortest-Job-First Scheduling

CPU Burst time이 가장 짧은 Process에 CPU를 먼저 할당하는 방식이다. CPU Burst time이 가장 짧은 프로세스를 먼저 처리하다 보니 평균 대기시간이 최소이다. 이 방식은 두가지로 또 나뉠 수 있는데, 새로운 프로세스의 CPU Burst time이 최소일 때 현재 실행중인 프로세스를 중지하고 CPU를 선점하느냐 하지 않느냐를 기준으로 선점형 방식과 비선점형 방식으로 나뉜다. 이때 Shortest-Job-First Scheduling의 선점형 방식을 Shortest Remaining Time First Scheduling(SRTF)라고 따로 부른다.

이 알고리즘의 실행 예시와 평균 대기시간에 대해 알아보자.

 

3-3. Priority Scheduling

미리 주어진 Priority에 따라 CPU를 할당하는 방식으로, 이 또한 새로운 프로세스의 Priority가 최대일 때 현재 실행중인 프로세스를 보류하냐 하지 않냐에 따라 선점형 방식과 비선점형 방식으로 나눌 수 있다. 하지만 두 방식 모두 최대 Priority를 갖는 프로세스가 계속 생성된다면 대기중인 비교적 낮은 Priority를 갖는 프로세스가 영원히 수행되지 않을 수 있기 때문에 Starvation문제를 피해갈 수 없다. 그래서 대안으로 대기 시간에 따라 Priority를 증가해주는 Aging기법을 이용하기도 한다.

 

3-4. Round-Robin Scheduling

CPU를 일정한 시간 단위(Time Quantum)씩 할당하는 방식으로, 선점형 방식이다. 응답 시간이 짧다는 장점이 있지만, 문맥전환이 많아 높아진 Overhead때문에 효율이 떨어질 수 있다. 이는 Time Quantum(q)의 시간으로 분석할 수 있는데, 만약 q가 크다면 FCFS와 다를 바가 없을것이고 q가 작을 경우에는 Context switching으로 인해 효율이 매우 좋지 않을 것이다.

각 프로세스가 할당 받는 시간은 1/n크기의 CPU 시간을 q로 쪼개어 할당 받을것이고, 각 Process의 다음 Time Quantum이 돌아오기 까지의 대기시간은 최대 (n-1) x q일것이다

 

3-5. Multilevel Queue Scheduling

Ready queue를 여러 개의 Queue로 분리하여 각기 다른 스케줄링 알고리즘을 사용하는 기법이다. 이렇게 나눌 필요가 있을가? 라고 생각할 수 있는데, 프로그램 마다 중시 하는 기준 (응답시간,대기시간 등)이 다를테고, 각 프로세스마다 성격(CPU-Bounded or I/O-Bounded Process)이 다르기 때문에 다른 성격의 프로세스들에 대해 최적의 스케줄링 기법을 제공해야할 필요가 있기 때문이다.

예를 들어 Interactive한 동작이 필요한 Process를 위해 짧은 응답시간이을 제공하는 Round Robin기법을 Foreground Queue에 설정하고, 많은 CPU작업량을 요구하는 Process를 위해 FCFS 기법을 Background Queue에 설정하여 두 프로세스에게 알맞는 스케줄링 알고리즘을 제공할 수 있을것이다.

하지만 Queue가 다양해진 만큼 각 Queue에 갯수, 우선순위 등 CPU를 어떻게 할당할 지를 결정해야 한다. 이는 Queue에 대한 Priorirty 또는 Time slice를 사용하여 처리될 수 있다. 다음은 이러한 성격의 프로세스 예시이다.

 

3-6. Multilevel Feedback Queue Scheduling

"Multilevel Queue Scheduling + Queue간의 이동" 알고리즘이다. Queue의 이동을 통해 Aging을 구현할 수 있다. 예를 들어 일정 time slice만큼 실행해도 프로세스가 종료되지 못했다면 그 프로세스를 더 빠르게 실행해줄 수 있는 Queue에 옮기는 방식으로 구현할 수 있다. 다음 예시를 살펴보자.

이 알고리즘을 사용하기 위해서는 몇가지 요소들이 명시되어야 한다. 이는 다음과 같다

Queue의 개수 / 각 Queue마다의 Scheduling 기법 / 언제 Process를 한 단계 높은 Queue로 옮길 것인지에 대한 기준 / 언제 Process를 한 단계 낮은 Queue로 옮길 것인지에 대한 기준 / 어떤 Process가 특정한 Service를 필요로 할 때 그 것을 제공하는 Queue로 옮겨줄 방법

이를 바탕으로 위에서 들었던 예시의 요소를 살펴보자.

새로운 Process가 들어오면,

1. Q_0에서 8 ms 동안 수행됨

2. 1에서 종료되지 않았다면 Q1으로 이동, 16 ms 동안 수행됨

3. 2에서도 종료되지 않으면, Q2으로 이동, FCFS로 수행됨

 

 

4. Mutliple Processor Scheduling

프로세서가 많아짐에 따라 CPU Scheduling도 복잡해졌다. 각 프로세서에 연결된 장치들도 다를테고, 각 프로세스의 특징도 다를 것이므로 효율적인 스케줄링을 위해 고려해야할 요소들이 많아지게 되었다. 예를 들어 I/O장치가 하나의 프로세서에만 연결되어있다고 가정하자. 그렇다면 효율을 높이기 위해서는 이 프로세서에게 CPU 사용량이 높은 프로세스를 주면 안될 것이다.  이처럼 프로세서를 어떻게 연결하고 관리하는 가에 대해서 Multiple processor scheduling도 나뉘게 되었다.  만약 하나의 CPU만이 Scheduling이나 I/O 작업과 같은 시스템 자료 구조를 관리하고, 다른 CPU는 총괄 시스템 자료 구조 총괄 CPU가 시키는 것 Job만 하는 형태라면 이는 비대칭 멀티프로세싱 (Asymmetric Multiprocessing)이라고 불린다. 하나의 CPU만이 시스템 자료구조를 관리하므로 복잡도나 구현 난이도는 낮아지지만 성능은 떨어진다.

이와 반대로 모든 프로세서가 시스템 자료구조를 함께 관리하는 형태를 대칭 멀티프로세싱(Symmetric Multiprocessing)이라고 부른다. 동시에 접근할 수도 있으므로 복잡도나 구현 난이도가 올라가지만 성능이 빠를 것이다.

앞서 시스템 자료 구조 접근 Processor 방식을 기준으로 비대칭 멀티프로세싱과 대칭 멀티프로세싱으로 분류하고 특징을 알아봤다. 이제 각 프로세스를 실행할 때 어떤 프로세서가 그 프로세스를 실행하고 관리할 지(+ 어떻게 관리할지)를 알아보자.

우선 과거에 수행하던 CPU에 프로세스를 배정하는 Processor Affinity방식이 존재한다. 

그리고 다수개의 프로세서의 Ready queue를 어떻게 관리할지를 기준으로 Load balancing 문제도 존재한다. 만약 Ready queue를 각 CPU마다 둔다면 일부 CPU에 Process가 집중될 수 있고, CPU 모두에 하나의 Ready queue만 둔다면 사용 가능한 CPU에 차례대로 Process를 배정할 수 있다.