OS - CPU 스케줄링

최신 운영체제에서는 실질적으로는 프로세스가 아니라 커널 수준 스레드를 스케줄 한다. 그러나 프로세스 스케줄링과 스레드 스케줄링 용어는 상호 교환적으로 사용된다.

 

1. 기본 개념 

 

코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있다. 나머지 프로세스는 CPU의 코어가 가용 상태가 되어 다시 스케줄 될 수 있을 때까지 기다려야 한다. 

 

1.1 CPU I/O Burst Cycle

 

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. 프로세스들은 이 두 상태 사이를 교댜로 왔다 갔다 한다.

프로세스 실행은 CPU burst로 시작된다 뒤이어 I/O burst가 발생하고, 그 뒤를 이어 또 다른 CPU burst가 발생하며 이어 또 다른 I/O burst 등등으로 진행된다. 

결국 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

I/O 중심의 프로그램은 전형적으로 짧은 CPU burst를 많이 가질 것이다. CPU 중심의 프로그램은 다수의 긴 CPU burst를 가질 수 있다. 

이러한 분포는 CPU 스케줄링 알고리즘을 구현할 때 매우 중요할 수 있다.

 

1.2 CPU 스케줄러

 

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러에 의해 수행된다. 

스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다. 

ready queue는 반드시 FIFO 방식의 큐가 아니어도 되는 것에 유의해야한다. ready queue는 선입선출 큐, 우선순위 큐, 트리 또는 단순히 순서가 없는 연결 리스트로 구현할 수 있다.

큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB)들 이다.

 

1.3 선점 및 비선점 스케줄링

 

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 한 프로세스가 실행 상태에서 대기 상태로 전환할 때(예를 들어 I/O 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait()를 호출할 때)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 
4. 프로세스가 종료될 때 

상황 1과 4의 경우, 스케줄링 면에서는 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다. 

그러나 상황 2와 3을 위해서는 선택의 여지가 있다. 

상황 1과 4에서만 스케줄링이 발생할 경우, 우리는 이러한 스케줄링 방법을 비선점 또는 협조적이라고 한다. 그렇지 않으면, 그것은 선점이라고 한다.

비선점 스케줄링에서는, 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. 

불행하게도 선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다. 두 프로세스가 자료를 공유하는 경우를 고려하자. 한 프로세스가 자료를 갱신하고 있는 동안 선점되어 두 번째 프로세스가 실행 가능한 상태가 될 수 있다. 

이때 두 번째 프로세스가 데이터를 읽으려고 할 때, 데이터의 일관성은 이미 깨진 상태이다.

선점은 또한 운영체제 커널 설계에 영향을 준다. 시스템 콜을 처리할 동안, 커널은 한 프로세스를 위한 활동으로 바쁠 수 있다. 그러한 활동은(I/O 큐와 같은) 중요한 커널 자료 변경을 포함할 수 있다.

만일 이러한 변경 도중에 해당 프로세스가 선점되고, 커널이 동일한 구조를 읽거나 변경할 필요가 있으면 어떤 일이 발생할까? 혼란이 계속해서 일어날 것이다. 

 

1.4 디스패처

 

CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처(dispatcher)이다. 디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 한다.

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적정한 위치로 이동하는 일 

디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 최고로 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다. 

 

2. 스케줄링 기준

 

CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되었다. 비교하는 데 사용되는 특성에 따라서 최선의 알고리즘을 결정한느 데 큰 차이가 발생한다. 사용되는 기준은 다음을 포함한다.

• CPU 이용률
• 처리량: 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로 이것을 처치량이러고 한다.
• 총처리 시간: 총처리 시간은 준비 큐에서 대기한 시간, CPU에서 실행하는 시간, 그리고 I/O 시간을 합한 시간이다.
• 대기 시간: 대기 시간은 준비 큐에서 대기 하면서 보낸 시간의 합이다.
• 응답 시간: 요청을 받은 후 첫 번째 응답이 나올 때까지의 시간 

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다. 

 

3. 스케줄링 알고리즘 

 

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다. 

 

3.1 선입 선처리 스케줄링(First-Come, First-Served Scheduling)

 

가장 간단한 CPU 스케줄링 알고리즘은 선입 선처리(FCFS) 스케줄링 알고리즘이다. 이방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 

선입선처리 정책의 구현은 선입선출 큐로 쉽게 관리할 수 있다. 프로세스가 준비 큐에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다. CPU가 사용 상태가 되면 준비 큐의 앞부분에 있는 프로세스에 할당된다. 

부정적인 측면으로 선입 선처리 정책하에서 평균대기 시간은 종종 대단히 길 수 있다. 

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(convoy effect)라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳는다. 

선입 선처리 스케줄링 알고리즘은 비선점형이라는 것을 주의하라. 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료하든지 또는 I/O 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유한다.

 

3.2 최단 작업 우선 스케줄링 (Shortest-Job-First Scheduling)

 

CPU 스케줄링의 다른 접근 방법은 최단 작업 우선(SJF) 알고리즘이다. 이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다. 

CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당한다. 두 프로세스가 동일한 길이의 다음 CPU 버스트를 가지면 순위를 정하기 위해 선입 선처리 스케줄링을 적용한다. 

이 스케줄링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트 길이에 의해 스케줄링이 되기 때문에 Shortest-next-CPU-burst 알고리즘이라는 용어가 더 적합해 보인다. 

SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적임을 증명할 수 있다. 

짧은 프로세스를 긴 프로세스 앞으로 이동함으로써, 짧은 프로세스의 대기 시간을 긴 프로세스의 대기 시간이 증가하는 것보다 더 많이 줄일 수 있다. 결과적으로, 평균대기 시간이 줄어든다.

SJF 알고리즘이 최적이긴 하지만, 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다. 

한 가지 접근 방식은 SJF 스케줄링가 근사한 방법을 사용하는 것이다. 다음 CPU 버스트의 길이를 알 수는 없으나, 그 값을 예측할 수는 있을 것이다. 우리는 다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 기대한다. 그러므로 다음 CPU 버스트 길이의 근삿값을 계산해, 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택한다.

다음 CPU 버스트는 일반적으로 측정된 이전의 CPU 버스트들의 길이를 지수 평균한 것으로 예측한다. 

SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있다. 

선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고, 반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 보스트를 끝내도록 허용한다. 

선점형 SJF 알고리즘은 때때로 shortest remaining time first 스케줄링이라고 불린다. 

 

3.3 라운드 로빈 스케줄링 (Round-Robin Scheduling)

 

라운드 로빈(RR) 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 시간 햘당량(time quantum), 또는 타임슬라이스(tome slice)라고 하는 작은 단위의 시간을 정의한다. 시간 할당량은 일반적으로 10에서 100밀리초 동안이다. 

준비큐는 원형 큐로 동작한다. CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다. 

라운드 로빈 스케줄링을 구현하기 위해, 우리는 다시 준비 큐가 선입선출 큐로 동작하게 만든다. 새로운 프로세스들은 준비 큐의 꼬리에 추가된다. CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치한다. 

두 가지 경우 중 하나가 발생할 수 있다. 

1. 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작을 수 있다.

이 경우에 프로세스 자신이 CPU를 자발적으로 방출할 것이다. 스케줄러는 그 후 준비 큐에 있는 다음 프로세스를 진행할 것이다.

1. 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우로, 타이머가 끝나고 운영체제로 인터럽트를 발생할 것이다.

문맥 교환이 일어나고 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다. 그 후 CPU 스케줄러는 준비 큐의 다음 프로세스를 선택할 것이다. 

라운드 로빈 스케줄링 알고리즘에서는, 유일하게 실행 가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 할당받는 프로세스는 없다. 만일 프로세스의 CPU 버스트가 한 번의 시간 할당량을 초과하면, 프로세스는 선점되고 준비 큐로 되돌아간다. 따라서 RR 스케줄링 알고리즘은 선점형이다.

RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우 시간 할당량이 매우 크다면, RR 정책은 선입 선처리 정책과 같다.이와 반대로 시간 할당량이 매우 적다면(예를 들어, 1마이크로초) RR 정책은 매우 많은 문맥 교환을 야기한다.

총처리 시간 또한 시간 할당량의 크기에 좌우된다. 한 프로세스 집합의 평균 총처리 시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지 않는다. 일반적으로, 대부분의 프로세스가 단일 시간 할당량 안에 다음 CPU 버스트를 끝낸다면, 평균 총처리 시간은 개선된다.

그러므로 시간 할당량이 문맥 교환 시간에 비해서는 커야하지만 너무 커서는 안된다. 

실제로 대부분의 현대 운영체제들은 10에서 100밀리초 범위의 시간 할당량을 가지고 있다. 문맥 교환을 하는데 걸리는 시간은 보통 10마이크로초 미만이다. 

 

3.4 우선순위 스케줄링

 

SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다. 우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 선입 선처리(FCFS) 순서로 스케줄 된다. 

SJF 알고리즘은 우선순위가 다음 CPU 버스트의 역인 단순한 우선순위 알고리즘이다. CPU 버스트가 클수록 우선순위가 낮으며, 그 역도 성립한다. 

우선순위는 일반적으로 0에서 7 또는 0에서 4095까지 같은 일정 범위의 수가 사용된다. 그러나 0이 최상위 또는 최하위 우선순위인가에 대해서 일반적인 합의는 없다. 여기서는 낮은 수가 높은 우선순위를 나타낸다고 가정한다. 

우선순위는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선순위는 프로세스의 우선순위를 계산하기 위해 어떤 측정 가능한 양들을 사용한다. 예를 들어, 시간 제한, 메모리 요구, 열린 파일의 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율 들이 우선순위의 계산에 사용된다. 

외부적 우선순위는 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양, 그 작업을 후원하는 부서 그리고 정치적인 요인등과 같은 운영체제 외부적 기준에 의해 결정된다. 

우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다. 프로세스가 준비 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교한다. 

선점형 우선순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다. 

비선점형 우선순위 스케줄링 알고리즘은 단순히 준비완료 큐의 머리 부분에 새로운 프로세스를 넣는다. 

우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄 또는 기아 상태이다. 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주할 수 있다. 우선순위 스케줄링 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다. 

낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대한 한 가지 해결 방안은 노화(aging)이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다. 예를 들어 1초마다 대기 중인 프로세스의 우선순위를 1씩 증가시킬 수 있을 것이다. 

다른 옵션은 라운드 로빈과 우선순위 스케줄링을 결합하는 방법이다. 시스템이 우선 순위가 가장 높은 프로세스를 실행하고 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용하여 스케줄 하는 방식이다. 

 

3.5 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

 

우선순위와 라운드 로빈 스케줄링을 사용할 때 모든 프로세스가 단일 큐에 배치되고 스케줄러는 우선순위가 가장 높은 프로세스를 선택하여 실행시킬 수 있다. 큐가 관리되는 방식에 따라 우선순위가 가장 높은 프로세스를 결정하기 위해 O(n) 검색이 필요할 수 있다. 

실제로, 우선순위마다 별도의 큐를 갖는 것이 더 쉬운 때도 있으며 우선순위 스케줄링은 우선순위가 가장 높은 큐에서 프로세스를 스케줄 한다. 다단계 큐라고 하는 이 방법은 우선순위 스케줄링이 라운드 로빈과 결합한 경우에도 효과적이다. 

우선순위가 가장 높은 큐에 여러 프로세스가 있는 경우 라운드 로빈순서로 실행된다. 이 방식의 가장 일반적인 형태에서 우선순위가 각 프로세스에 정적으로 할당되며 프로세스는 실행시간 동안 동일한 큐에 남아 있다. 

프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 다단계 큐 스케줄링 알고리즘을 사용할 수도 있다. 예를 들어, 흔히 포그라운드 프로세스와 백그라운드 프로세스를 구분한다. 이 두 가지 유형의 프로세스는 응답시간 요구사항이 다르므로 스케줄링 요구 사항이 다를 수 있다. 

또한 포그라운드 프로세스는 백그라운드 프로세스보다 우선순위를 가질 수 있다. 포그라운드 및 백그라운드 프로세스에 별도의 큐가 사용될 수 있으며 각 큐에는 자체 스케줄링 알고리즘이 있을 수 있다. 

예를 들어, 백그라운드 큐는 FCFS 알고리즘에 의해 스케줄 되는 반면, 포그라운드 큐는 RR 알고리즘에 의해 스케줄 될 수 있다. 

추가로, 큐와 큐 사이에 스케줄링도 반드시 있어야 하며, 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다. 예를 들어, 실시간 큐는 대화형 큐보다 절대적으로 높은 우선순위를 가질 수 있다. 

이제 4개의 큐를 가진 다단계 큐 스케줄링 알고리즘의 예를 보자. 각 큐는 다음과 같은 우선순위를 갖는다.

1. 실시간 프로세스
2. 시스템 프로세스
3. 대화형 프로세스
4. 배치 프로세스

각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다. 예를 들어, 실시간 프로세스, 시스템 프로세스, 대화형 프로세스를 위한 큐들이 모두 비어 있지 않으면, 배치 큐에 있는 프로세스는 실행될 수 없다. 배치 프로세스가 실행되고 있는데, 대화형 프로세스가 준비 큐에 들어가면 배치 프로세스는 선점될 것이다. 

다른 가능성은 큐들 사이에 시간을 나누어 사용하는 것이다. 각 큐는 CPU 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다. 예를 들어, 포그라운드-백그라운드 큐의 예에서, 포그라운드 큐는 자신의 프로세스들 사이에서 라운드 로빈 스케줄링을 위해 CPU 시간의 80%가 주어지고, 백그라운드 큐는 CPU 시간의 20%를 받아 자신의 프로세스들에 선입 선처리 방식으로 줄 수 있다.

 

3.6 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

 

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 예를 들어, 포그라운드와 백그라운드 프로세스를 위해 별도의 큐가 있으면, 프로세스들은 한 큐에서 다른 큐로 이동하지 않는다. 왜냐하면 프로세스들이 포그래운드와 백그라운드의 특성을 바꾸지 않기 때문이다. 이러한 방식은 스케줄링오버헤드가 장점이 있으나 융통성이 적다.

대조적으로 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다. 프로세스들을 CPU 버스트 성격에 따라서 구분한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동된다. 이 방법에서는 I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다. 마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 이러한 노화 형태는 기아 상태를 예방한다. 

일반적으로, 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법