CPU 스케줄링📆

CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리장치이다. 프로그램이 시작되어 메모리에 올라가면 프로그램 카운터(Program Counter: PC)라는 이름의 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다. 그러면 CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행하게 된다.

프로그램의 수행은 서로 다른 두 단계의 조합으로 이루어진다. 첫째는 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계이고, 둘째는 I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계이다.

전자를 CPU 버스트, 후자를 I/O버스트라고 부른다. 즉 프로그램이 I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 직접 직접 CPU를 가지고 명령을 수행하는 일련의 작업이 CPU 버스트이고, 이해 비해 I/O 버스트는 I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업을 말한다.

각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지 않다. I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스를 I/O 바운드 프로세스라 하고 그 반대를 CPU 바운드 프로세스라 한다.

CPU 스케줄링은 이와 같이 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함게 실행되기 때문에 필요하다.

컴퓨터 시스템 내에서 수행되는 프로세스들의 CPU 버스트를 분석해보면 대부분의 프로세스는 CPU 버스트가 짧게 나타난다. 이는 CPU를 한번에 오래 사용하기보다 잠깐 사용하고 I/O 작업을 수행하는 프로세스들이 많다는 것이다.

CPU 버스트가 짧은 프로세스는 대부분 대화형 작업으로 사용자와 인터랙션을 해가며 프로그램을 수행시키는데 이는 사용자에게 입력을 받아 CPU연산을 수행하고 그 결과를 다시 출력하는 작업을 수행한다. 이러한 작업을 수행하는 프로세스는 CPU의 빠른 서비스를 필요로 하기 때문에 CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다.

1. CPU 스케줄러

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드이다. 프로세스가 CPU를 할당받고 기계어 명령을 수행하다가 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출된다. 그러면 CPU 스케줄러는 준비 큐에서 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 된다.

CPU 스케줄링 필요한 경우는 몇가지가 있다.

1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
4. CPU에서 실행상태에 있는 프로세스가 종료되는 경우

CPU 스케줄링 방식에는 비선점형 방식과 선점형 방식이 있다.

비선점형 방식이란 CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법을 말한다.
선점형 방식은 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법을 말한다.

위에 스케줄링이 필요한 4가지 경우중 1번과 4번은 비선점형 스케줄링의 예시가 되고, 2번과 3번은 선점형 스케줄링 방식에 해당한다.

2. 디스패처

CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다.
이렇게 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처(dispatcher)라고 부른다.

디스패처는 현재 수행 중이던 프로세스의 문맥(context)을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.

3. 스케줄링 성능 평가

스케줄링 기법의 성능 평가는 크게 시스템 관점의 지표와 사용자 관점의 지표로 나누어진다.

시스템 관점의 지표로는 CPU 이용률과 처리양이 있으며, 사용자 관점의 지표로는 소요시간, 대기시간, 응답시간 등 기다린 시간과 관련된 지표들이 있다.

시스템 관점의 지표

CPU 이용률 : 전체 시간 중에서 CPU가 일을 한 시간의 비율을 나타낸다. cpu는 대부분 시스템에 하나만 존재하므로 CPU가 일을하지 않는 상태에 머무르는 시간을 최대한 줄이는 것이 중요한 목표이다.

CPU처리량 : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝마쳤는지(CPU 버스트를 완료한 프로세스 개수)를 나타낸다.

사용자 관점의 지표

소요시간 : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간, 즉 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합

대기시간 : CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합

응답시간 : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간

4. 스케줄링 알고리즘❗️(중요⭐️)

1) 선입선출 스케줄링(First-Come First-Served:FCFS)

선입선출 스케줄링은 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말한다.

프로세스	CPU 버스트 시간
P1	12
P2	3
P3	3

예시이다. 프로세스의 도착 순서가 p1, P2, P3라 하고 CPU 버스트 시간이 12, 3, 3이라고 가정하면 다음과 같은 결과가 나온다.

만약 프로세스가 p2, p3, p1 순으로 도착한다고 한다면 이런 결과가 나온다.

이 두 가지 상황을 비교해보면 CPU버스트가 짧은 프로세스가 먼저 도착한 후자의 경우 평균 대기시간이 크게 줄어들었음을 볼 수 있다.

CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다. 따라서 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다.

즉 CPU버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지는 반면, 짧은 프로세스가 먼저 도착하면 평균대기시간이 짧아지게 된다.

따라서 FCFS 스케줄링의 가장 큰 단점은 CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다리게 되는 것이다.(콘보이 현상)

2) 최단작업 우선 스케줄링(Shortest-Job First: SJF)

SJF 스케줄링 알고리즘은 CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다.

SJF 알고리즘은 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다. SJF의 선점형 구현 방식에서는 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗게 된다.

프로세스	도착시간	CPU 버스트 시간
P1	0	14
P2	4	8
P3	8	2
P3	10	8

• SJF 비선점형 스케줄링

• SJF 선점형 스케줄링

선점형 방식에서는 프로세스가 새롭게 도착하거나 작업이 끝날 때마다 CPU 버스트 시간을 비교하게 된다.

SJF 알고리즘이 평균 대기시간을 최소화하는 알고리즘이기는 하지만 시스템에서 평균을 줄이는 것이 항상 좋은 방식이라고는 말할 수 없다.

CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 계속해서 기다려야 하는 문제가 발생할 수 있다.

예를 들어서 이러한 경우이다.

프로세스	도착시간	CPU 버스트 시간
P1	0	10
P2	4	20
P3	8	30
P4	10	1000
P5	20	100
P6	24	200
P7	30	300

CPU 버스트 시간이 각각 10, 20 , 30인 프로세스 p1, p2, p3가 수행된 후 CPU 버스트 시간이 1000인 프로세스 p4는 그 다음에 오는 p5, p6, p7의 CPU 버스트 시간이 짧은데다 여기에 만약 계속해서 CPU 버스트 시간이 짧은 프로세스들이 도착한다면 p4는 영원히 CPU를 할당받지 못할 수도 있다. 이러한 현상을 기아 현상이라고 한다. 이는 SJF 알고리즘의 가장 심각한 문제점이다.

3) 우선순위 스케줄링

우선순위 스케줄링이란 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다.

우선순위를 결정하는 방식에는 여러가지가 있을 수 있다. CPU 버스트 시간을 우선순위 값으로 정의하면 이는 SJF 알고리즘과 동일한 의미를 가지게 된다. 또한 우선순위 스케줄링도 비선점형 방식과 선점형 방식으로 각각 구현할 수 있다.

우선순위 스케줄링 방식에서의 문제점 중 하나는 SJF 스케줄링 알고리즘과 같이 기아 현상이 발생할 수 있다는 점이다.

이러한 문제점을 해결하기 위해 노화(aging)기법을 사용할 수 있다. 노화 기법이란 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법이다.

4) 라운드 로빈 스케줄링

라운드 로빈 스케줄링(Round Robin Scheduling)은 시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식이라 할 수 있다.

라운드 로빈 스케줄링에서는 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다. 이때 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간이라고 부른다.

아래와 같이 프로세스 p1, p2, p3가 순서대로 도착했다고 가정했을때

프로세스	CPU 버스트 시간
P1	24
P2	17
P3	3

할당시간이 10인 라운드 로빈 스케줄링을 적용하면 결과는 다음 차트와 같다.

라운드 로빈 스케줄링은 일반적으로 SJF 방식보다 평균 대기 시간은 길지만 응답시간이 더 짧다.

할당시간이 만료되어 CPU를 회수하는 방법으로는 🕰타이머 인터럽트를 사용하게 된다.

라운드 로빈 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다.

5) 멀티레벨 큐

멀티레벨 큐(multi-level queue)란 준비 큐를 여러개로 분할해 관리하는 스케줄링 기법을 말한다. 즉 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아닌 여러 줄로 서는 것이다. 쉽게말해 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것이다.

CPU는 하나밖에 없으므로 어떤 줄에 서 있는 프로세스를 우선적으로 스케줄링 할 것인가 하는 문제가 발생한다.

멀티레벨 큐는 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다.

멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다.

전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하고,
계산 위주의 작업을 위한 후위 큐에서는 응답시간이 큰 의미를 갖지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄인다.

멀티레벨 큐에서는 또 다른 스케줄링이 필요한데, 이는 큐 자체에 대한 스케줄링이다. 여러 개의 준비 큐에 대해서 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요한 것이다.

큐에 대한 스케줄링으로 가장 쉽게 생각할 수 있는 방식은 고정 우선순위 방식(fixed priority scheduling)이다. 이 방식에서는 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐를 비어 있을 때에만 서비스하게 된다.

6) 멀티레벨 피드백 큐

멀티레벨 피드백 큐(Multilevel Feedback Queue)는 CPU를 기다리는 프로세스를 여러 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

멀티레벨 피드벡 큐의 대표적인 방식은 다음 사진과 같다.

상위에 있는 큐일수록 우선순위가 높고, 상위 2개의 큐는 각각 할당시간이 5와 10인 라운드 로빈 스케줄링을 사용한다. 세 번째 큐는 FCFS 스케줄링 기법을 사용한다. 프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다. 그러면 CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 빨리 서비스받고 작업을 완료할 수 있다.

그러나 CPU 버스트 시간이 긴 프로세스들은 5만큼의 시간 동안 CPU를 사용하고도 작업이 완료할 수 없기 때문에 할당 시간이 10인 하위큐로 내려가서 줄 서게 된다. 이후 하위 큐에서 본인 차례가 되어 할당시간 10을 추가로 사용하고도 작업이 완료되자 않으면, 이 프로세스는 CPU를 오래 사용하는 계산 위주의 프로세스로 간주되어 최하위 큐로 이동하게 되고 FCFS 스케줄링을 적용받게 된다.

큐에 대한 스케줄링 방식으로는 최상위 큐가 우선적으로 CPU를 배당받고, 상위 큐가 비었을 때에만 하위 큐에 있는 프로세스들이 CPU를 할당받을 수 있게 된다.