[운영체제와 정보기술의 원리] 6. CPU 스케줄링

Oct 15, 2021

'운영체제와 정보기술의 원리' 스터디를 진행하며 정리한 내용이다.

CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치.
일반적으로 한 시스템 내에 하나씩밖에 없으므로 시분할 환경에서 매우 효율적으로 관리되어야 하는 자원.
기계어 명령은 크게 CPU 내에서 수행되는 명령, 메모리 접근을 필요로 하는 명령, 입출력을 동반하는 명령으로 나누어볼 수 있음.
- CPU 내에서 수행되는 명령
  1. Add 명령 - CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령. CPU 내에서 수행되므로 명령의 수행 속도가 빠르다.
- 메모리 접근을 수행하는 명령
  1. Load 명령 - 메모리에 있는 데이터를 CPU로 읽어들이는 명령
  2. Store 명령 - CPU에서 계산된 결괏값을 메모리에 저장하는 명령
    CPU 내에서 수행되는 명령보다는 오래 소요되지만 비교적 짧은 시간에 수행할 수 있음.
    CPU 내에서 수행되는 명령과 메모리 접근을 수행하는 명령은 일반명령에 해당함.
- 입출력을 동반하는 명령
  - CPU나 메모리 접근 명령에 비해 대단히 오랜 시간이 소요됨.
  - 특권명령으로 규정해 운영체제를 통해 서비스를 대행하도록 하고 있음.
프로그램의 수행은 서로 다른 두 단계의 조합으로 이루어짐.
1. 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계
  - CPU 버스트라고 함.
  - 프로그램이 I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 일련의 작업
2. I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
  - I/O 버스트라고 함.
  - I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업.
I/O 바운드 프로세스
- I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
- 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램(interactive program)
- 짧은 CPU 버스트를 많이 가짐.
CPU 바운드 프로세스
- I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스를 말함.
- 프로세스 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램.
- 소수의 긴 CPU 버스트로 구성됨.
CPU 스케줄링은 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 필요한 것.
- 시분할 시스템에서 CPU 버스트가 균일하지 않은 다양한 프로그램이 공존하므로 효율적인 CPU 스케줄링 기법이 반드시 필요함.
프로세스들을 살펴보면 CPU를 한 번에 오래 사용하기보다는 잠깐 사용하고 I/O 작업을 수행하는 프로세스들이 많음.
- 이러한 CPU 버스트가 짧은 프로세스는 대화형 작업으로 사용자와 인터랙션을 해가며 프로그램을 수행시킴.
- CPU의 빠른 서비스를 필요로 하기에 (대화형 작업은 빠른 응답이 중요함) CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요함.
따라서 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직하다.
- I/O 바운드 프로세스에게 먼저 CPU를 할당할 경우 CPU를 잠깐만 사용한 후 곧바로 I/O 장치의 이용률이 높아짐.
- CPU 바운드 프로세스에게 먼저 CPU를 할당하면 그 프로세스가 CPU를 다 사용할 때까지 I/O 바운드 프로세스는 응답시간이 길어질 뿐 아니라 해당 I/O 장치도 그 시간 동안 작업을 수행하지 않는 휴면 상태가 되기 때문에 비효율적.

1. CPU 스케줄러

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드.
타이머 인터럽트가 발생하면 CPU 스케줄러가 호출되고 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 됨.
CPU 스케줄링이 필요한 경우
1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
CPU 스케줄링 방식에는 두 가지가 있음.
- 비선점형(nonpreemptive) 방식
  - CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법을 말함.
- 선점형(preemptive) 방식
  - 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법을 말함.
- 위 네 가지 경우에서 1, 4는 비선점형 스케줄링, 2, 3은 선점형 스케줄링에 해당함.
- 3의 경우 I/O 작업이 완료된 프로세스가 인터럽트 당한 프로세스보다 우선순위가 높아 인터럽트 처리 후 수행되던 프로세스에게 CPU를 다시 할당하는 것이 아닌 문맥교환을 통해 I/O가 완료된 프로세스에게 CPU를 할당하는 경우가 해당됨.
CPU를 빼앗는 방법으로는 할당시간(time quantum)을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적.

2. 디스패처

새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처(dispatcher)라고 부름.
디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행함.
새로운 프로세스의 문맥을 복원시킨 후엔 시스템의 상태를 사용자모드로 전환해 사용자 프로그램에게 CPU의 제어권을 넘기게 됨.
- 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾을 수 있게 됨.
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연시간(dispatch latency)이라고 하며, 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당됨.

3. 스케줄링의 성능 평가

스케줄링 기법의 성능을 평가하기 위해 여러 지표들이 사용되는데, 이 지표들은 크게 시스템 관점의 지표와 사용자 관점의 지표로 나누어볼 수 있음.
- 시스템 관점의 지표로는 CPU 이용률과 처리량이 있음.
- 사용자 관점의 지표로는 소요시간, 대기시간, 응답시간 등 기다린 시간과 관련된 지표들이 있음.
CPU 이용률(CPU utilization)
- 전체 시간 중에서 CPU가 일을 한 시간의 비율을 나타냄.
- CPU는 고비용 자원이므로 CPU 이용률은 시스템 전체의 성능과 밀접하게 관련되어 있어 CPU가 일을 하지 않고 휴면(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표가 됨.
처리량(throughput)
- 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지(CPU 버스트를 완료한 프로세스의 개수)를 나타냄.
- CPU의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼의 CPU를 사용하고 이번 CPU 버스트를 끝내어 준비 큐를 떠났는지 측정하는 것이 처리량의 개념
- 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리함.
소요시간(turnaround time)
- 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼의 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간, 즉 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합을 뜻함.
- 프로그램이 시작해 종료하는 데까지 걸리는 시간이 아님을 주의.
대기시간(waiting time)
- CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합을 뜻함.
- 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있음.
응답시간(response time)
- 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간을 뜻함.
- 타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 짧아지므로 처음 CPU를 얻기까지 걸리는 시간을 줄어들게 되어 응답시간이 향상된다.
- 대화형 시스템에 적합한 성능 척도로서 사용자 입장에서 가장 중요한 성능 척도

4. 스케줄링 알고리즘

선입선출 스케줄링(First-Come First-Served: FCFS)
- 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말함.
- CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않음.
- 합리적인 스케줄링 방식인 것 같지만 경우에 따라 비효율적인 결과를 초래하기도 함.
  - CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지고 I/O 장치 이용률도 동반 하락하게 됨.
- CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지는 반면, CPU 버스트가 짧은 프로세스가 먼저 도착하게 되면 평균 대기시간이 짧아지게 됨.
- CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상을 콘보이 현상(Convoy effect)라고 한다.
최단작업 우선 스케줄링(Shortest-Job First: SJF)
- CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식.
- 프로세스들이 준비 큐에서 기다리는 전체적인 시간이 줄어들게 됨.
- 평균 대기시간을 가장 짧게 하는 최적 알고리즘(optimal algorithm)으로 알려져 있음.
- 비선점형 방식
  - CPU를 획득하면 그 프로세스가 CPU를 자진 반납하기 전까지는 CPU를 빼앗지 않는 방식
- 선점형 방식
  - 준비 큐에서 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식을 말함.
  - SRTF(Shortest Remaining Time First)라고도 부름.
- 프로세스들이 준비 큐에 도착하는 시간이 불규칙한 환경에서는 선점형 방식이 프로세스들의 평균 대기시간을 최소화하는 최적 알고리즘이 됨.
- 준비 큐에 한꺼번에 도착하고 그 후에 따로 도착하지 않는 환경에서는 비선점형 방식과 선점형 방식이 서로 같은 결과를 나타내기도 함.
- 일반적인 시분할 환경에서는 중간중간에 새로운 프로세스가 도착하는 경우가 발생하므로 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있는 방식이 됨.
- SJF 스케줄링 기법의 구현에서 현실적으로 어려운 부분은 프로세스의 CPU 버스트 시간을 미리 알 수 없다는 점.
  - 예측을 통해 CPU 버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 CPU를 할당하게 됨.
  - CPU 버스트 시간의 예측은 과거의 CPU 버스트 시간을 통해 이루어짐.
- 계속 CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제가 발생할 수 있기 때문에 항상 좋은 방식이라고는 말할 수 없다.
- CPU 버스트가 짧은 프로세스가 계속 도착할 경우 CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못할 수도 있는데 이 현상을 기아 현상(starvation)이라고 한다.
우선순위 스케줄링(priority scheduling)
- 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말함.
- 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정.
- 우선순위를 결정하는 방식에는 여러 가지가 있는데 CPU 버스트 시간을 기준으로 하거나 시스템과 관련된 중요한 작업을 수행하는 프로세스 우선순위를 높게 부여할 수도 있다.
- 비선점형 방식
  - CPU를 얻었으면 우선순위가 더 높은 프로세스가 도착하더라도 CPU를 자진 반납하기 전까지 선점하지 않는다.
- 선점형 방식
  - 현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점해서 새롭게 도착한 프로세스에게 할당하는 경우
- 우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선순위가 낮은 프로세스는 CPU를 얻지 못한 채 계속 기다려야 하는 기아 현상이 발생할 수 있음.
  - 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 노화(aging) 기법을 통해 해결할 수 있다.
라운드 로빈 스케줄링(Round Robin Scheduling)
- 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다.
- 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간(time quantum)이라고 부름.
- 할당시간이 너무 길면 라운드 로빈 스케줄링은 FCFS와 같은 결과를 나타내게 됨.
- 할당시간이 너무 짧으면 CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커짐.
- 따라서 일반적으로 할당시간을 수십 밀리초 정도의 규모로 설정하게 됨.
  - 여러 프로세스가 동시에 수행되는 환경에서 대화형 프로세스가 CPU를 한 번 할당받기까지 지나치게 오래 기다리지 않을 정도의 시간 규모에 해당됨.
- 라운드 로빈 스케줄링은 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적.
- 할당시간이 만료되어 CPU를 회수하는 방법으로는 타이머 인터럽트를 사용하게 됨.
- 라운드 로빈 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것.
- 자신이 CPU를 쓰고자 하는 양이 적으면 소요시간이 짧아지고, 많으면 소요시간도 거기에 비례해서 길어진다. 대기시간 역시 비례해서 증가하므로 공정하다고 할 수 있음.
- 동일한 CPU 버스트 시간을 가지는 프로세스들이 도착했을 경우 FCFS에서는 CPU를 먼저 쓰고 나가는 프로세스의 소요시간 및 대기시간이 짧아지는 반면, 라운드 로빈 스케줄링에서는 CPU를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 소요시간 및 대기시간이 가장 오래 기다린 프로세스에 맞춰지게 된다. 따라서 라운드 로빈 스케줄링의 평균 대기시간 및 평균 소요시간은 FCFS의 거의 두 배가 된다.
- 일반적인 시스템에서는 CPU 버스트 시간이 균일하지 않고 각자 다른 CPU 버스트 및 I/O 버스트를 가지는 경우가 대부분이다.
  - 이 경우 라운드 로빈 스케줄링을 적용하면 CPU 버스트 시간이 짧은 프로세스는 빨리 끝마치고, 반대로 CPU 버스트 시간이 긴 프로세스는 상대적으로 오래 기다린다.
  - FCFS는 CPU 버스트가 긴 프로세스가 먼저 도착하는 경우 소요시간의 편차가 크고 평균값드 극단적으로 상승하게 된다.
멀티레벨 큐(multi-level queue)
- 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법. 즉, 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것.
- 멀티레벨 큐는 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 됨.
- 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영됨.
  - 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하는 반면, 계산 위주의 작업을 위한 후위 큐에서는 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄이도록 함.
- 여러 개의 준비 큐에 대해서 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요함.
  - 고정 우선순위 방식(fixed priority scheduling)
    - 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어 있을 때에만 서비스하게 됨.
    - 전위 큐에 있는 프로세스에게 우선적으로 CPU가 할당되고, 전위 큐가 비어 있는 경우에만 후위 큐 프로세스에 CPU 할당.
  - 타임 슬라이스(time slice) 방식
    - 큐에 대한 기아 현상을 해소할 수 있는 방식으로, 각 큐에 CPU 시간을 적절한 비율로 할당함.
멀티레벨 피드백 큐(Multilevel Feedback Queue)
- 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동가능하다는 점이 다르다.
- 멀티레벨 피드백 큐를 정의하는 요소들로는 큐의 수, 각 큐의 스케줄링 알고리즘, 프로세스를 상위 큐로 승격시키는 기준, 프로세스를 하위 큐로 강등시키는 기준, 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준 등이 있음.
- 프로세스의 CPU 작업시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있게 함.
다중처리기 스케줄링
- CPU가 여러 개인 시스템을 다중처리기 시스템(multi-processor system)이라고 부른다.
- 다중처리기 스케줄링에서는 일부 CPU에 작업이 편중되는 현상을 방지하기 위해 각 CPU별 부하가 적절히 분산되도록 하는 부하균형(load balancing) 메커니즘을 필요로 한다.
- 대칭형 다중처리(symmetric multi-processing)
  - 각 CPU가 각자 알아서 스케줄링을 결정하는 방식
- 비대칭형 다중처리(asymmetric multi-processing)
  - 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식
실시간 스케줄링
- 실시간 시스템에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 함.
- 경성 실시간 시스템(hard real-time system)
  - 미사일 발사, 원자로 제어 등 시간을 정확히 지켜야 하는 시스템.
  - 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링해야 함.
- 연성 실시간 시스템(soft real-time system)
  - 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않음. ex) 멀티미디어 스트리밍 시스템
- 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 사용함.
- 연성 실시간 시스템처럼 일반 작업과 VOD 작업 등이 혼합된 환경에서는 데드라인이 존재하는 프로세스에게 일반 프로세스보다 높은 우선순위를 할당하는 방식도 사용함.

5. 스케줄링 알고리즘의 평가

큐잉모델(queueing model)
- 주로 이론가들이 수행하는 방식
- 확률분포를 통해 프로세스들의 도착률과 CPU 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표인 CPU의 처리량, 프로세스 평균 대기시간 등을 구하게 됨.
구현 및 실측(implementation & measurement)
- 구현가들이 수행할 수 있는 방식
- 커널의 CPU 스케줄링 수행 코드를 수정해서 커널을 컴파일한 후 시스템에 설치하는 과정을 필요로 함. 그 후 원래 커널과 스중한 커널에서 프로그램을 실행시켜보고 실행시간을 측정.
시뮬레이션(simulation)
- 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떤 결과가 나오는지를 확인하는 방법.