CPU Scheduling

스케줄링

• OS는 CPU 등의 자원을 프로세스에 적절히 배정함으로써 시스템의 성능을 개선할 수 있음
• 프로세스가 작업을 수행하려면 스케줄러로부터 cpu를 할당 받아야 함
• 프로세스 실행 = (CPU 실행 + I/O 대기) 의 사이클 = CPU - I/O Burst Cycle

CPU Scheduling = CPU 를 잘 사용하기 위해 프로세스를 잘 배정하기 !
 
 

프로세스를 스케줄링하기 위한 Queue

프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재함
 

1. Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
2. Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
3. Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

 

스케줄링 목표

1. 공정한 스케줄링
2. 응답시간 최소화  * 사용자에게 빠르게 응답 
3. 반환시간 최소화  * 반환 시간 : 프로세스 제출 ~ 완료
4. 대기시간 최소화  * ready queue에서 보내는 시간
5. 단위시간 당 처리량 극대화
6. 균형 있는 자원 사용
7. 무한 연기 회피
8. 우선 순위 처리 등등

💡 스케줄링 기준

CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률
처리량(Throughput): 단위 시간당 완료된 프로세스의 개수
총처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격
대기 시간(Waiting Time): 대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합
응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간

* CPU Utilization, Throughput을 최대화하고
Turaround Time, Waiting Time, Response Time을 최소화 하는 알고리즘이 바람직한 선택

* 하지만 대부분의 알고리즘의 경우는 Trade-Off !! 
   → 상황에 맞춰서 선택하는 것이 가장 좋은 방법

 

스케줄링 발생 상황

• I/O 발생 (한 프로세스가 실행 상태 → 대기 상태)
• 인터럽트 발생 (프로세스가 실행 상태 → 준비 완료 상태) 
• I/O 종료 (프로세스가 대기 상태 → 준비 완료 상태) 
• 프로세스 종료

 

Dispatcher

: CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈
 

 
 

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump) 하는 일
• dispatch latency : 디스패처가 하나의 프로세스를 정지하고, 다른 프로세스의 수행을 시작하는데까지 소요되는 시간

 

 

 

스케줄링 종류

• 선점 (preemptive) : 한 프로세스가 cpu를 할당받아서 실행하고 있을 때 다른 프로세스가 cpu를 사용하고 있는 프로세스를 중지시키고 cpu를 차지할 수 있는 스케줄링 기법 ➞ 처리 시간 예측 불가능 
• 비선점 (nonpreemptive) : 이미 사용되는 cpu를 빼았지는 못하고 사용이 끝날 때 까지 기다리는 스케줄링 기법 (종료, waiting 상태가 아니면 CPU를 놓지 않음) ➞ 처리 시간 예측 가능 

 
* 스케줄링 대상은 Ready Queue 에 있는 프로세스

선점	Priority Scheduling	- 우선순위가 가장 높은 프로세스에 CPU 를 할당      * 정적/동적으로 우선순위 부여  - 우선 순위가 낮은 경우 starvation 현상이 발생할 수 있음     ➞ aging(오래 기다리면 우선순위를 높여줌)을 통해 해결
	Round Robin	- 현대적인 CPU 스케줄링  - 동일한 크기의 할당 시간(Time Quantum)을 가짐     * Time Quantum (Time Slice) : 실행의 최소 단위 시간  - CPU 사용 시간이 랜덤한 프로세스들이 섞여있을 경우 효율적  - Response time이 빨라짐  - 할당 시간이 큰 경우 FCFS와 같아짐,     작은 경우 Context Switching이 잦아져 오버헤드 증가     ➞ 적당한 Time Quantum을 설정하는 것이 중요함
	Multilevel-Queue	- Ready큐를 여러 개 사용하는 기법  - 각각의 큐는 자신의 스케줄링 알고리즘을 수행  - 큐와 큐 사이에도 우선순위를 부여      ➞ 우선순위가 높은 queue는 긴 time quantum
	Multilevel-Feedback-Queue	- Multilevel-Queue와 비슷하지만, queue 간의 이동 가능  - CPU를 많이 사용한 경우 ➞ 밑으로 내림  - 너무 오래 기다린 경우 ➞ 위로 올림
	Rate Monotonic	- Realtime Scheduling   : 모든 프로세스들이 정해진 시간 내에 완료되야 하는 시스템     (soft - 노력 / hard - 반드시)  - 주기가 짧은 프로세스에 높은 우선순위를부여  - 정적인 우선순위를 사용하는 알고리즘 중 가장 optimal
	EDF(Earliest Deadline First)	- Realtime Scheduling  - 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여
비선점	FCFS  (First Come First Served)	- 먼저 온 순서대로 CPU 할당  - 수행 시간이 짧은 프로세스가 뒤에 오면 대기 시간이 길어짐
	SJF (Shortest Job First)	- 수행 시간이 짧은 프로세스를 먼저 실행  - FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리  - starvation 현상이 발생할 수 있음
	HRN  (Highest Response ratio Next)	- 우선 순위를 계산하여 점유 불평등을 보완     = SJF의 단점 보완   * 우선순위 = (대기시간 + 실행시간) / 실행시간