- CPU and I/O Bursts in Program Execution - 번갈아가며 수행된다.
CPU Burst의 분포
- I/O가 중간에 끼어드는 작업이 많았다.
- CPU만 길게 사용하는 작업은 매우 적다.
⇒ 효율적인 작업을 위해 CPU Scheduling이 필요하다.
- 필요한 것
- Interactive job에게 적절한 response 제공 필요
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
프로세스의 특성 분류
프로세스는 그 특성에 따라 다음 두 가지로 나눈다.
- I/O-bound process
- CPU를 잡고 계산하는 시간보다 I/O 작업에 많은 시간이 필요한 job
- many short CPU bursts
- CPU-bound process
- 계산 위주의 job
- few very long CPU bursts
CPU Scheduler & Dispatcher
-
CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
-
Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
- 이 과정을 Context Switching(문맥 교환)라고 한다.
-
CPU Scheduling이 필요한 경우는 프로세스가 다음의 상태 변화가 있는 경우
- Running → Blocked (ex) I/O 요청하는 시스템 콜)
- Running → Ready (ex) 할당 시간 만료로 timer interrupt)
- Blocked → Ready (ex) I/O 완료 후 interrupt)
- Terminate
-
비선점형 nonpreemptive
-
선점형 preemptive
Scheduling Criteria
Performance Index ( = Performance Measure, 성능 척도)
- CPU utilization (이용률)
- 전체 시간 중에서 CPU가 일한 시간 (CPU는 가능한 바쁘게 일을 해야 한다.)
- Throughput (처리량)
- 주어진 시간 내에 몇 개의 일을 수행
- Turnaround time (소요 시간, 반환 시간)
- CPU를 쓰러 들어와서 다 사용하는데까지 걸리는 시간 (Ready 부터 종료까지)
- Waiting Time (대기 시간)
- CPU 할당까지 기다린 시간 (얻었다 뺏겼다를 반복하는데 이런 기다리는 시간을 모두 합친 것)
- Response Time (응답 시간) - Waiting Time 과 구분
- Ready Queue에 들어와서 최초 CPU 할당을 얻기까지 걸리는 시간
CPU Scheduling Algorithm
FCFS (First Come First Served)
- 먼저오는 것을 먼저 처리
특징
- 비선점형
단점
- Convoy Effect : short process behind long process(소요 시간이 긴 프로세스가 먼저 할당되어 효율성이 떨어질 수 있다.)
SJF(Shortest Job First)
- CPU Burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄
- 비선점형
- 일단 CPU를 잡으면 이번 CPU Burst가 끝날때까지 CPU를 선점당하지 않음
- 선점형
- 현재 수행 중인 프로세스의 남은 CPU Burst time보다 짧은 CPU Burst time을 가진 프로세스가 들어오는 경우 CPU를 넘겨준다.(SRTF(Shortest Remaining Time First))
- 주어진 프로세스들에 대해 minimum average waiting time을 보장
단점
- Starvation : CPU Burst time이 긴 프로세스는 CPU 할당을 받지 못할 수 있다.
- CPU Burst time을 명확히 알 수 없다. (추정만 가능 - 과거의 CPU Burst time을 이용해서 추정 (exponential averaging)
Priority Scheduling
- 우선순위가 높은 것을 먼저 처리
- 비선점형
- 우선순위가 더 높은 것이 들어오더라도 현재 프로세스가 끝날때까지 CPU를 선점당하지 않음
- 선점형
- 우선순위가 더 높은 것이 들어오면 CPU를 넘겨준다.
단점
- Starvation : 우선순위가 낮은 프로세스는 CPU 할당을 받지 못할 수 있다.
- 해결책 : 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여준다.
Round Robin(RR)
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
- 할당 시간이 지나면 프로세스는 선점당하고 Ready Queue의 가장 뒤에 가서 줄을 선다.
- Response time이 짧아진다.
- 일반적으로 SJF보다 average turnaround tijme이 길지만 response time이 짧아진다.
성능
- 할당 시간이 너무 크다면 → FCFS와 유사해져 비효율적
- 할당 시간이 너무 짧다면 → Context Switching으로 인한 Overhead가 커진다.
