Basic Concepts
Preemptive and Nonpreemptive Scheduling
CPU 스케줄링의 결정은 다음의 네 가지 상황에서 발생할 수 있다.
- 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
- 프로세스가 종료할 때
비선점 스케줄링(nonpreemptive)하에서는, 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. (1, 4번)
선점 스케줄링(preemptive)은 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽트나 시스템 호출 종료시에 더 높은 우선 순위 프로세스가 발생 되었음을 알았을 때, 현 실행 프로세스로부터 강제로 CPU를 회수하는 것을 말한다. (2, 3번)
데이터가 다수의 프로세스에 의해 공유될 때 racing condition이 발생될 수 있다.
mutex lock, monitor 등의 기법을 사용해서 racing condition을 피한다.
race condition (경쟁 상태)
경쟁 상태(race condition)란 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다. 입력 변화의 타이밍이나 순서가 예상과 다르게 작동하면 정상적인 결과가 나오지 않게 될 위험이 있는데 이를 경쟁 위험이라고 한다.
인터럽트는 어느 시점에서건 일어날 수 있고, 커널에 의해서 항상 무시될 수는 없기 때문에, 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.
Dispatcher
CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 포함한다.
- 한 프로세스에서 다른 프로세스로 context-switch하는 일
- 사용자 모드로 전환하는 일
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일
디스패처는 모든 프로세스의 context-switch 시 호출된다.
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다.
Scheduling Criteria
-
CPU 이용률(Utilization)
어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률을 말한다. -
처리량(Throughput)
단위 시간당 완료된 프로세스의 개수로써 나타낼 수 있다. -
총처리 시간(Turnaround Time)
프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이라고 한다. -
대기 시간(Waiting Time)
대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다. -
응답 시간(Response Time)
하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간이다.
CPU Utilization, Throughput을 최대화하고 Turaround Time, Waiting Time, Response Time을 최소화 하는 알고리즘의 선택이 바람직한 선택이다.
하지만 대부분의 알고리즘의 경우는 Trade-Off 임으로 본인의 Context에 맞춰서 선택하는 것이 가장 좋은 방법이다.
Scheduling Algorithms
CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다.
선입 선처리 스케줄링 (First-Come First-Served, FCFS)
가장 간단한 CPU 스케줄링 알고리즘으로, CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.
간단히 선입선출 큐로 관리할 수 있다.
단점은 선입 선출 과정에서 프로세스의 평균 대기 시간은 상당히 길어질 수 있다는 점이다.
다음과 같은 프로세스들이 대기 큐에 있다고 가정해보자.
| 프로세스 | 버스트 시간 |
|---|---|
| P1 | 24 ms |
| P2 | 3 |
| P3 | 3 |
만약 프로세스들이 P1 ~ P3 순으로 선입 선출 방식이 적용된다면, 각 프로세스의 대기 시간은 다음과 같다.
P1 = 0 ms, P2 = 24 ms, P3 = 27 ms -> 평균 17 ms
그러나 프로세스들이 P2, P3, P1 순으로 도착하면, 각 프로세스들의 대기 시간은 다음과 같다.
P1 = 6, P2 = 0, P3 = 3 -> 평균 3 ms
따라서 선입 선처리 스케줄링의 평균대기 시간은 일반적으로 최소가 아니다.
convoy effect
모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과라고 한다.
이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때 이득이다.
최단 작업 우선 스케줄링 (Shortest Job First Schduling)
최단 작업 우선(Shortest Job First, SJF) 알고리즘은 CPU 버스트 길이가 가장 작은 프로세스부터 순서적으로 CPU 코어를 할당한다.
최단 작업 우선(SJF) 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적임을 증명할 수 있다. 하지만 각 프로세스의 CPU 버스트 길이는 알 수 있는 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현하기가 어렵다. 따라서 우리는 프로세스별 CPU 버스트의 길이를 예측해서 스케줄링 해야만 한다.
SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 비선점형일 경우 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다.
우선순위 스케줄링 (Priority Scheduling)
우선순위가 각 프로세스들에 연관되어 있으며, CPU 코어는 가장 높은 우선순위를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 보통 FCFS 순서로 스케줄 된다.
우선순위는 내부적 또는 외부적으로 정의될 수 있다. 우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다.
우선순위 스케줄링 알고리즘의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)이다.
- 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄 된 것으로 간주할 수 있다. (Blocking)
- 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수 도 있다. (Starvation)
낮은 우선순위의 프로세스들이 무한히 봉쇄되는 문제에 대한 한가지 해결 방안은 노화(aging)이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
우선순위 스케줄링의 문제점을 해결할 수 있는 또 다른 방법은 우선순위 스케줄링과 라운드 로빈 스케줄링을 결합하는 방법이다.
라운드 로빈 스케줄링 (Round Robin Scheduling, RR)
라운드 로빈 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다.
여기서는, 시간 할당량(time quantum) 또는 타임슬라이스라고 하는 작은 단위의 시간을 정의한다.
기본 베이스는 준비 큐가 선입선출 큐로 동작하게 만든다. 그 후 CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치 한다.
이때 두 가지 상황이 발생할 수 있다.
- 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작다 -> 프로세스 스스로 CPU를 방출하게 되고, 다음 프로세스로 이동
- 한 번의 시간 할당량보다 긴 경우 -> 인터럽트가 발생하고, 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다.
다음과 같은 프로세스들이 대기 큐에 있다고 가정해보자.
| 프로세스 | 버스트 시간 |
|---|---|
| P1 | 24 ms |
| P2 | 3 |
| P3 | 3 |
만약 시간 할당량을 4 ms로 한다면, P1은 처음 4 ms 사용 후 나머지 20 ms는 맨 뒤로 가고, P2, P3는 바로 실행 후 종료한다.
라운드 로빈 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다.
극단적인 경우, 시간 할당량이 매우 크면, 선입 선처리 정책과 다를 바 없다.
반대로 시간 할당량이 매우 적다면, 매우 많은 문맥 교환을 야기할 수 있다.
따라서 일반적으로 시간 할당량이 문맥 교환 시간과 비교해 더 크도록 설정한다.
다단계 큐 스케줄링 (Multilevel Queue Scheduling)
우선순위마다 별도의 큐를 두는 것이다.
각 큐들은 자신의 스케줄링 알고리즘을 가질 수 있는데, 예를 들어 백그라운드 큐는 선입선출, 포그라운드는 라운드 로빈 알고리즘을 사용하는 경우이다.
또한, 큐와 큐 사이에도 스케줄링이 반드시 있어야 하는데, 보통의 우선순위는 실시간 -> 시스템 -> 대화형 -> 배치 순서이다.
다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)
다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 이와 반대로 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.
다단계 피드백 큐 스케줄링 알고리즘은 Aging과 Starvation을 예방한다.
이 알고리즘은 특정 시스템에 부합하도록 구성이 가능함으로 현대 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘이다.
하지만, 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수 값들을 선정하는 특정 방법이 필요하기 떄문에 가장 복잡한 알고리즘이기도하다.
Multiple-Processor Scheduling
다중 처리기 스케줄링에 대한 접근 방법
-
비대칭 다중 처리(asymmetric multiprocessing)
마스터 서버(master server)라는 하나의 프로세서가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급하게 하는 것이다.오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다. 반면 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다.
-
대칭 다중 처리(symmetric multiprocessing)
각 프로세서는 스스로 스케줄링할 수 있다.각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
Affinity
SMP(symmetric multiprocessing)을 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 이용하려 한다. 이를 프로세서 선호도라고 한다. 즉, 프로세스는 현재 실행 중인 프로세서에 대한 선호도를 보인다. (캐쉬 등의 리소스 관련해)
Processor Affinity는 여러 형태를 띈다.
- 약한 선호도(soft affinity): 운영체제는 프로세스를 특정 처리기에서 실행시키려고 노력은 하지만 프로세스가 처리기 사이에서 이주하는 것은 가능하다.
- 강한 선호도(gard affinity): 운영체제는 시스템 콜을 통하여 프로세스는 자신이 실행될 처리기 집합을 명시할 수 있다.
많은 시스템에서 soft affinity와 hard affinity를 모두 지원한다.
Load Balancing은 종종 Processor Affinity의 장점을 상쇄한다. 즉, 동일한 프로세서에서 스레드를 계속 실행하면 스레드가 해당 프로세서의 캐시 메모리에 있는 데이터를 활용할 수 있다는 이점이 있다. 하지만, 스레드를 한 프로세서에서 다른 프로세서로 이동하여 부하를 균등하게 조정하면 이러한 이점이 사라진다.
결국 이러한 기술들은 Trade off 관계 임으로 자신의 문맥에 맞추어서 잘 활용하자.
Load Balancing
SMP(symmetric multiprocessing, 대칭 다중 처리) 시스템에서 프로세서가 하나 이상이라는 것을 최대한 활용하려면, 부하(Load)를 모든 프로세서에 균등하게 배분(Balancing)하는 것이 매우 중요하다.
부하 균등화(Load balancing)은 SMP 시스템의 모든 프로세서 사이에 부하가 고르게 배분되도록 시도한다. 부하 균등화는 통상 각 처리기가 실행할 스레드를 위한 자기 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능이라는 것을 주의해야 한다.
부하 균등화를 위해서는 push migration와 pull migration 방식의 두 가지 일반적인 접근법이 있다.
- push migration: 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 쉬고 있거나 덜 바쁜 처리기로 스레드를 이동(또는 push)시킴으로써 부하를 분배 한다.
- pull migration: 쉬고 있는 프로세서가 바쁜 프로세서를 기다리고 있는 프로세스를 pull할 때 일어난다.
Load balancing의 개념은 여러 가지로써 존재할 수 있으니 문맥에 잘 맞추어서 구현 및 선택 하자.
Thread Scheduling
사용자 스레드와 커널 스레드의 연관 관계를 다대일과 다대다 모델로 구현하는 시스템에서는 스레드 라이브러리는 사용자 수준 스레드를 가용한 LWP(Light Weight Process)상에서 스케줄 한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위(process contention scope, PCS)로 알려져 있다.
CPU상에서 어느 커널 스레드를 스케줄 할 것인지를 결정하기 위해서 커널은 시스템 경쟁 범위(system contention scope, SCS)를 사용한다. SCS 스케줄링에서의 CPU에 대한 경쟁은 시스템상의 모든 스레드 사이에서 일어난다.
