CPU 스케쥴링
기본 개념
단일 처리기 시스템에서는 한 순간에 오직 하나의 프로세스만이 실행될 수 있다.
다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.
CPU 입출력 버스트 사이클(CPU-I/O Brust Cycle)
프로세스 실행은 CPU 실행과 입출력 대기의 사이클 로 구성된다. 프로세스들은 이 두 상태 사이를 교대로 왔다 갔다 한다.
프로세스 실행은 CPU 버스트(Burst) 로 시작되고, 뒤이어 입출력 버스트 가 발생하며, 그 뒤를 이어 또 다른 CPU 버스트가 발생하며 이어 또 다른 입출력 버스트 등등으로 진행된다.
마지막 CPU 버스트는 또 다른 입출력 버스트가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다.
 |
|---|
| 단일코어 시스템에서의 병행 실행 |
CPU 버스트들의 지속 시간을 측정하면, 일반적으로 곡선이 지수형 또는 초지수형으로 특성화 된다.
짧은 CPU 버스트가 많이 있으며, 긴 CPU 버스트는 적다. 입출력 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가지게 될 것이며, CPU 중심의 프로그램은 다수의 긴 CPU 버스트를 가지게 될 것이다.
 |
|---|
| CPU 버스트 시간의 도표 |
CPU 스케쥴러(CPU Scheduler)
CPU가 유휴 상태가 될 때마다, OS는 Ready Queue에 있는 프로세스들 중에서 하나를 선택하여 실행한다. 실행 절차는 단기 스케쥴러에 의해 수행된다. 스케쥴러는 실행 준비가 되어있는 메모내의 프로세스들 중에서 선택하여 이들 중 하나에게 CPU를 할당한다.
선점 스케쥴링(Preemptive Scheduling)
CPU 스케쥴링은 아래와 같은 다섯가지 상황에서 발생할 수 있다.
- 한 프로세스가 실행 상태에서 대기 상태로 전환될 때
- 프로세스의 상태가 running -> wait 로 전환
- non preemtive scheduling
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때
- 프로세스의 상태가 running -> ready 로 전환
- preemtive scheduling
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때
- 프로세스의 상태가 wait -> ready 로 전환
- preemtive scheduling
- 프로세스가 생성 되고 준비 완료 상태로 전환 될 때
- 프로세스의 상태가 new -> ready 로 전환
- preemtive scheduling
- 프로세스가 종료할 때
- 프로세스의 상태가 running -> terminate 로 전환
- non preemtive scheduling
비선점 스케쥴링(Non Preemtive Scheduling) 에선, CPU가 한 프로세스에 할당 되면, 프로세스가 종료하든지 또는 대기 상태로 전환하여 CPU를 방출할 때 까지 CPU를 점유한다.
디스패처(Dispatcher)
디스패처는 CPU의 제어를 단기 스케쥴러가 선택한 프로세스에게 주는 모듈이며 아래과 같은 작업을 수행한다.
- 문맥 교환
- 사용자 모드로 전환
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적정한 위치로 이동
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 까지 소요되는 시간을 디스패치 지연(Dispather Latency) 이라고 한다.
스케쥴링 기준
여러 CPU 스케쥴링 알고리즘들 중 하나를 선택하기 위해 아래와 같은 기준을 참고한다.
- CPU 이용률(Utilization)
- 처리량(Throughput)
- 단위 시간당 완료된 프로세스의 갯수
- 총처리 시간(Turnaround Time)
- 프로세스를 실행하는데 소요된 시간
- 대기 시간(Waiting Time)
- 스케쥴링 알고리즘은 단지 프로세스가 Ready Queue에서 대기하는 시간의 양에만 영향을 준다.
- 대기 시간은 Ready Queue에서 대기하면서 보내는 시간의 합니다.
- 응답 시간(Response Time)
- 요구를 제출한 후 첫번째 응답이 나올때 까지의 시간
CPU 이용률과 처리량을 최대화 하고, 총처리 시간, 대기 시간, 응답 시간을 최소화 하는것이 바람직 하다.
스케쥴링 알고리즘
선입 선처리 스케쥴링(First-Come, First-Served Schduling) - Non Preemtive Scheduling
CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당 받는다.
평균 대기 시간이 종종 대단히 길 수 잇다.
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
 |
|---|
| P1, P2, P3 순으로 도착할때의 FCFS 알고리즘 |
위와 같은 순서로 프로세스가 도착할 때, FCFS 알고리즘에서 프로세스의 평균 대기시간은 (0 + 24 + 27) / 3 = 17 이다.
 |
|---|
| P2, P3, P1 순으로 도착할때의 FCFS 알고리즘 |
위와 같은 순서로 프로세스가 도착할 때, FCFS 알고리즘에서 프로세스의 평균 대기시간은 (6 + 0 + 3) / 3 = 3 이다.
즉, FCFS 알고리즘 상에서 평균 대기 시간은 일반적으로 최소가 아니며, 프로세스 CPU 버스트 시간이 크게 변할 경우에는 평균 대기 시간도 상당히 변할 수 있다.
모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(Convoy Effect) 라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.
최단 작업 우선 스케쥴링(Shortest Job First Schduling) - Non Preemtive Scheduling or Preemtive Scheduling
가장 작은 다음 CPU 버스트를 가진 프로세스에게 CPU를 할당한다.
각 프로세스에 다음 CPU 버스트 길이를 연관시켜, 가장 작은 CPU 버스트를 가진 프로세스에게 CPU를 할당한다. 즉, 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케쥴링된다.
| Process | Burst Time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
 |
|---|
| SJF 알고리즘에서의 P1, P2, P3, P4의 스케쥴링 |
위와 같은 상황에서 평균 대기시간은 (3 + 16 + 9 + 0) / 4 = 7 이다.
SJF 스케쥴링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적임이 증명 가능하다.
장기 스케줄링에 많이 이용되는 알고리즘이지만, 단기 스케쥴링에서는 다음 CPU 버스트의 길이를 알 수 있는 방법이 없다.
SJF 알고리즘은 선점형 이거나 비선점형 일 수 있다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 Ready Queue에 도착하면 선택이 발생 된다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수 있다. 이때, 선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스를 선점 할 것이고, 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
 |
|---|
| 선점형 SJF 알고리즘에서의 P1, P2, P3, P4의 스케쥴링 |
이 예에서 평균 대기시간은 ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3)) / 4 = 26 / 4 = 6.5 이다.
우선순위 스케쥴링(Priority Scheduling) - Non Preemtive Scheduling or Preemtive Scheduling
우선순위가 각 프로세스들에게 연관되어 있으며, CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.
SJF 알고리즘은 우선순위(p)가 다음 CPU 버스트의 역인 단순한 우선순위 알고리즘이다
| Process | Burst Time | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
 |
|---|
| 우선순위 알고리즘에서의 P1, P2, P3, P4, P5의 스케쥴링 |
우선 순위 스케쥴링의 주요 문제는 무한 봉쇄(Indefinite Blocking) 또는 기아 상태(Starvation) 이다.
- 무한 봉쇄(Indefinite Blocking)
- 우선순위가 낮은 프로세스의 경우, 무한히 CPU의 할당을 기다릴 수 있다.
- 기아 상태(Starvation)
- 높은 우선순위를 가진 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못할수 있다.
낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대한 한가지 해결책으로는 노화(Aging) 이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 것이다.
라운드 로빈 스케쥴링(Roud Robin Scheduling) - Preemtive Scheduling
CPU 스케쥴러는 Ready Queue를 돌면서 한 번에 한 프로세스에게 한번의 시간 할당량 동안 CPU를 할당한다.
라운드 로빈 스케쥴링 알고리즘은 특별히 시분할 시스템을 위해 설계되었다.
시간 할당량(Time Quantum) 또는 시간 조각(Time Slice) 라고 불리는 작은단위의 시간을 정의하여 해당 시간동안 프로세스에게 순차적으로 CPU 할당한다. 일반적으로 시간 할당량은 10 ~ 100밀리초 이다.
일반적으로 아래 두 경우 중 하나가 발생한다.
- 프로세스의 CPU 버스트가 한번의 시간할당량보다 작을경우
- 프로세스 자신이 CPU를 자발적으로 방출한다. 스케쥴러는 그 후 Ready Queue에 있는 다음 프로세스로 진행한다.
- 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴경우
- 타이머가 끝나고 OS에서 인터럽트를 발생시킨다. 문맥교환이 일어나고, 실행하던 프로세스는 Ready Queue의 꼬리에 넣어진다. 그 후 CPU 스케쥴러는 Ready Queue의 다음 프로세스로 진행한다.
만일 시간 할당량을 4밀리초라고 할 떄, 그 예는 아래와 같다.
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
 |
|---|
| RR 알고리즘에서의 P1, P2, P3의 스케쥴링 |
RR 스케쥴링 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크다면, RR 스케쥴링 알고리즘은 FCFS 스케쥴링 알고리즘과 같다. 이와 반대로 시간 할당량이 매우 작다면 RR 스케쥴링 알고리즘은 매우 많은 문맥교환을 발생시킨다.
 |
|---|
| 시간 할당량이 작을수록 문맥교환 획수가 늘어나는 예시 |
 |
|---|
| 총처리 시간이 시간 할당량에 따라 변하는 모습 |
문맥교환을 하는데 걸리는 시간은 보통 10마이크로초 이다.
시간 할당량이 문맥교환 시간에 비해 커야 하지만 너무 커져서는 안된다.
다단계 큐 스케쥴링(Multilevel Queue Scheduling) - Preemtive Scheduling
Ready Queue를 다수의 별도의 큐로 분리하여, 각각 별도의 스케쥴링 알고리즘을 가지게 한다.
일반적으로 포그라운드(Foreground)(대화형) 백그라운드(Background)(일괄처리) 프로세스는 응답시간에 대한 요구사항이 다르기 때문에, 프로세스의 유형을 구분하여 각 특성에 맞춰 다른 스케쥴링 알고리즘을 사용한다.
프로세스들은 메모리 크기, 프로세스의 우선순위 혹은 프로세스 유형과 같은 프로세스의 특성에 따라 한개의 큐에 영구적으로 할당된다. 각 큐는 자신만의 스케쥴링 알고리즘을 가지고 있다.
큐와 큐 사이에 스케쥴링도 반드시 있어야 하며, 일반적으로 고정 우선순위 의 선점형 스케쥴링으로 구현된다.
 |
|---|
| 다단계 큐 스케쥴링 |
각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.
다단계 피드백 큐 스케쥴링(Multilevel Feedback Queue Scheduling) - Preemtive Scheduling
다단계 큐 스케쥴링과 유사하지만 다른점은 프로세스가 큐들 사이를 이동하는것을 허용한다.
다단계 큐 스케쥴링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 대조적으로 다단계 피드백 큐 스케쥴링 알고리즘은 프로세스가 큐들 사이를 이동하게 한다.
먼저 프로세스들을 CPU 버스트 성격에 따라 구분한다. 어떤 프로세스가 CPU 시간을 저무 많이 사용하면, 낮은 우선운위의 큐로 이동된다. 이러한 방법에서는 입출력 중심의 프로세스와 대화형 프로세스들은 높은 우선순위의 큐에 넣는다. 마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐에 넣는다. 이러한 노화(Aging) 형태는 기아상태를 예방한다.
 |
|---|
| 다단계 큐 스케쥴링 |
일반적으로 다단계 피드백 큐 스케쥴러는 다음의 매개변수에 의해 정의된다..
- 큐의 개수
- 각 큐를 위한 스케쥴링 알고리즘
- 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
- 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
- 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법
스레드 스케쥴링
사용자 수준 과 커널 수준 스레드를 구별하는 OS에서 스케쥴되는 대상은 프로세스가 아니라 커널 수준의 스레드이다. 사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커넣은 그들의 존재를 알지 못한다.
경쟁 볌위(Contention Scope)
사용자 수준과 커널 수준 스레드의 차이 중 하나는 그들이 어떻게 스케쥴 되는지 이다.
다대일, 다대다 모델을 구현하는 시스템에서 스레드 라이브러리는 사용자 수준 스레드를 가용한 LWP 상에서 스케쥴한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위(Process Contention Scope, PCS) 로 알려저 있다.
전형적으로 PCS는 우선순위에 따라 행해진다.
CPU상에서 어느 커널 스레드를 스케쥴 할 것인지 경정하기 위해서 커널은 시스템 경쟁 범위(System Contention Scope, SCS) 를 사용한다. SCS 스케쥴링에서의 CPU에 대한 경쟁은 시스템 상의 모든 스레드 사이에서 일어난다.
Windows, Linux와 같은 일대일 스레드 모델을 사용하는 시스템은 오직 SCS만을 사용하여 스케쥴한다.
다중 처리기 스케쥴링
여러개의 CPU 코어가 사용가능해 지면서, 부하 공유(Load Sharing) 가 가능해 진다.
다중 처리기 스케쥴링에 대한 접근 방법
다중 처리기 시스템의 CPU 스케쥴링에 관한 해결방법은 크게 두가지가 있다.
- 비대칭 다중처리(Asymmetric Multiprocessing)
- 주 서버라는 하나의 처리기가 모든 스케쥴링 결정과 입출력 처리 그리고 다른 시스템의 활동을 취급하게 한다.
- 다른 처리기들은 다만 사용자 코드만 수행한다.
- 단지 한 처리기만 시스템 자료구조를 접근하여 자료공유의 필요성을 배게하기 때문에 간단하다.
- 대칭 다중처리(Symmetric Multiprocessing, SMP)
- 각 처리기가 독자적으로 스케쥴링 한다.
- 모든 프로세스는 공동의 Ready Queue에 있거나 각 처리기 마다 가지고 있는 사유의 Ready Queue에 있게 된다.
- Windows, Linux, MacOS를 포함한 거의 모든 현대의 OS들은 SMP를 지원한다.