CPU Scheduling
Scheduling 목적
- 멀티 프로그래밍의 목적과 동일하다. CPU의 사용률을 높이기 위해 스케줄링을 한다.
- CPU를 할당받은 프로세스가 이벤트를 대기하는 상태에 있을 경우, CPU는 놀고 있는 상태가 된다. 이러한 경우 OS는 CPU를 그 프로세스로부터 회수해 다른 프로세스에게 할당하여 CPU가 일을 하게 해야 한다.
CPU burst, I/O burst
프로세스는 CPU 실행, 입출력 대기의 상태를 교대로 왔다 갔다한다.
CPU burst
프로세스가 CPU를 사용하여 작업을 수행하는 시간
I/O Burst
프로세스가 입출력 작업을 수행하는 시간
CPU bound, I/O bound
CPU Bound 프로세스
CPU burst >> I/O Burst 인 프로세스
I/O Bound 프로세스
I/O burst >> CPU Burst 인 프로세스
CPU Scheduler
CPU가 Idle 상태가 될 때마다, OS는 레디 큐에서 대기 중인 프로세스들 중에서 하나를 선택해서 실행해야 한다.
선택하는 역할은 CPU 스케줄러 (or 단기 스케줄러)가 담당한다.
Dispatcher
CPU 스케줄러가 선택한 프로세스에게 CPU를 할당하는 역할은 Dispatcher가 담당한다.
Dispatcher은 아래와 같은 작업을 수행한다.
- Context Switching 진행
- CPU 할당
- User Mode로 전환
- 프로세스를 다시 시작하기 위해 프로세스의 적절한 위치로 이동
Dispatcher는 모든 문맥 교환 시 호출되기 때문에, 가능한 최고로 빨리 수행되어야 한다.
디스패치 지연
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 걸리는 시간
선점, 비선점 스케줄링
비선점 스케줄링
프로세스가 CPU를 할당받으면 프로세스가 종료하든지 또는 대기 상태로 전환해 CPU 제어권을 넘길때까지 CPU를 점유한다.
즉, CPU를 사용중인 프로세스가 CPU 제어권을 스스로 넘길때까지 다른 프로세스가 CPU를 사용중인 프로세스에게서 CPU 제어권을 뺏어올 수 없다.
선점 스케줄링
비선점 스케줄링과 반대로 현재 CPU를 사용중인 프로세스에게서 CPU 제어권을 빼앗을 수 있다.
스케줄링 기준
스케줄링 알고리즘마다 특성을 가지고 특정 상황에서 어떠한 알고리즘을 선택하려면 다양한 알고리즘들의 서로 다른 특성을 반드시 고려해야 한다.
CPU 스케줄링 알고리즘을 비교하기 위해 여러가지 기준들이 제시되었다.
-
CPU 사용률(CPU utilization)
-
처리량(Thoughput): 단위 시간 당 완료된 프로세스 개수
-
총처리 시간(Turnaround time): 프로세스 제출 시간과 완료 시간의 간격
-
대기 시간(Waiting time): 레디 큐에서 대기하는 시간
-
응답 시간(Response Time): 첫 번째 응답이 나올 때까지의 시간
Scheduling 알고리즘
FCFS Scheduling
특징
- CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다.
- 비선점 스케줄링
- 프로세스 실행 순서에 따라 대기 시간, 총처리 시간이 달라진다.
- Convoy Effect = 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 현상
장점
- 간단하고 구현하기 쉽다.
단점
- 평균 대기 시간이 길 수 있다.
SJF Scheduling
Shortest-Job-First Scheduling
특징
- 레디 큐에서 대기하는 프로세스들 중 다음 CPU Burst가 가장 짧은 프로세스를 선택한다.
- 지수 평균을 사용해서 다음 CPU Burst의 근사적으로 구한다.
- 선점 or 비선점 스케줄링일 수 있다.
Exponential Average
- 프로세스의 과거 CPU Burst를 활용해서 다음 CPU Burst를 예측한다.
- t은 최근 정보, τ는 과거 정보, (0<=α<=1)
- τ(n+1)은 다음 CPU Burst 예측값
장점
가장 짧은 평균 대기 시간을 가지기 때문에 probably optimal하다
단점
다음 CPU Burst를 알 수가 없다
SRTF Scheduling
Shortest-Remaining-Time-First Scheduling
특징
- 선점형 SJF 스케줄링 알고리즘
- 현재 실행 중인 프로세스의 남은 CPU Burst보다 더 짧은 CPU-burst time인 프로세스로 선점한다.
Priority Scheduling
특징
- 가장 높은 우선순위를 가진 프로세스에게 할당된다.
- 우선 순위가 동일하면 FCFS 순서로 스케줄된다.
- 선점형 이거나 비선점형
- Starvation(or indefinite blocking)
- 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 상황)
- Aging 기법으로 해결할 수 있다.
- 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
장점
중요도에 따라 프로세스를 스케줄링할 수 있다.
단점
낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생할 수 있다.
Round Robin Scheduling
특징
- 선점형 FCFS 스케줄링
- 프로세스는 Time Quantum동안 CPU를 할당받는다.
- Time Quantum이 끝나면 인터럽트를 걸도록 타이머를 설정한다.
- Ready Queue는 원형 큐로 구현된다.
2가지 상황
- CPU Burst가 Time Quantum보다 작으면 프로세스 자신이 스스로 CPU를 반납한다.
- CPU burst가 Time Quantum보다 길면 타이머가 끝나고 OS에게 인터럽트를 발생시킨다.
장점
공평하게 프로세스를 스케줄링한다.
단점
- Time Quantum에 따라 성능이 매우 달라진다.
- Time Quantum이 매우 크면 FCFS 스케줄링과 동일하다
- Time Quantum이 매우 작으면 Context Switching 오버헤드(Dispatch Latency)가 너무 커진다.
Multi-level Queue Scheduling
특징
- 레디 큐를 다수의 별도 큐로 분류한다
- 각 큐는 자신의 스케줄링 알고리즘을 가진다
- 큐 사이에 스케줄링도 반드시 있어야 한다.
- 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다.
- 일반적으로 프로세스들은 메모리 크기, 프로세스의 우선순위, 프로세스 유형과 같은 특성에 따라 한 개의 큐에 영구적으로 할당된다
장점
작업에 우선순위를 부여할 수 있다.
단점
작업이 영구적으로 하나의 큐에 할당되므로 융통성이 적다.
Multi-level Feedback Queue Scheduling
특징
- 프로세스가 큐들 사이를 이동하는 것을 허용한다.
- 일반적으로 프로세스들을 CPU Burst 성격에 따라 우선순위를 구분한다.
- 프로세스가 CPU Burst를 많이 사용하면 낮은 우선순위의 큐로 이동된다.
- 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동한다. (Aging)
장점
우선순위 동적 조절
단점
가장 복잡하다
Thread Scheduling
특징
-
현대 OS는 프로세스가 아니라 레디 큐에서 커널 쓰레드와 사용자 쓰레드를 스케줄링한다.
- 사용자 쓰레드는 1차적으로 사용자 쓰레드 라이브러리에 스케줄링되고
- 사용자 쓰레드 라이브러리에 스케줄링 된 쓰레드가 OS 레디큐에 위치하여 CPU 스케줄러에 의해 스케줄링된다.
-
사용자 쓰레드 라이브러리는 사용자 스레드를 가용한 LWP 상에서 스케줄링한다.
-
PCS(process-contention scope)
- 동일한 프로세스에 속한 스레드들 사이에서 스케줄링
- 전형적으로 우선순위에 따라 행해진다
-
SCS(system-contention scope)
- 커널 스레드를 스케줄링 할 것인지 스케줄링
Multi-Processor Scheduling
대칭, 비대칭
비대칭 프로세서 스케줄링
- 하나의 처리기가 모든 스케줄링 결정을 한다.
- 나머지 처리기는 사용자 코드만을 수행한다.
대칭 프로세서 스케줄링
- 각 처리기가 독자적으로 스케줄링한다.
- 모든 프로세스는 공동의 레디 큐에 위치하거나 각 처리기마다 가지고 있는 레디큐에 위치 한다.
- 서로 다른 2개의 프로세서가 같은 프로세스를 선택하지 않아야 한다.
처리기 친화성
프로세스가 특정 프로세스에서 실행 중일때, 프로세스에 의해 가장 최근에 접근된 데이터는 프로세서의 캐시에 위치한다.
만약 프로세스가 다음에 실행될 때, 다른 처리기에서 실행된다면 가장 최근에 실행되었던 프로세서의 캐시는 무효화하고 다음에 실행될 프로세서의 캐시에 위치해야 한다.
이 과정이 비용이 많이 들기 때문에 대부분의 SMP 시스템은 한 프로세서에서 다른 프로세서로의 이주를 피하고 같은 프로세서에서 프로세스를 실행하려고 한다.
이 현상을 처리기 친화성이라고 한다. 즉, 프로세스가 현재 실행 중인 프로세서에 친화성을 가진다는 것을 의미한다.
Load Balancing
SMP 시스템에서 프로세서가 자신 만의 레디 큐를 가지고 있고 스케줄링할 경우에만 Load Balancing이 필요하다.
Push 이주
특정 태스크가 주기적으로 각 처리기의 부하를 검사하고, 만일 불균형 상태를 발견하면 과부하인 프로세서에서 쉬고 있거나 덜 바쁜 프로세소로 프로세서를 push 하여 부하를 분배하낟.
Pull 이주
쉬고 있는 프로세서가 바쁜 프로세서를 기다리고 있는 프로세스를 자기한테로 가져와서 실행시킨다.
Load balancing은 프로세서 친화성(캐시)의 장점을 없앤다.
멀티코어 프로세서
Real time Scheduling
응답성이 중요하기 때문에 선점형 알고리즘을 사용한다.
Soft Realtime, Hard Realtime
Soft Realtime 스케줄링
- 태스크를 특정 시간안에 실행 완료하는 것을 보장하지 않지만, 중요한 태스크가 덜 중요한 것보다 먼저 실행되는 것을 보장한다.
Hard Realtime 스케줄링
- 태스크가 무조건 특정 시간 안에 실행 완료되어야 하는 것을 보장한다.
