Operating System - CPU Scheduling

CPU Scheduling

CPU Scheduling이란?

ㆍ 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.

 

CPU Scheduling의 목적

ㆍ 공정한 스케줄링, 처리량의 극대화, 응답 시간의 최소화

ㆍ 균형 있는 자원의 사용, 프로세스 실행의 무한한 연기를 배제, 반환시간 예측 가능

---

Scheduling Criteria

스케줄링의 척도

1. CPU Utilization(CPU 이용률) : CPU가 얼마나 놀지 않고 부지런히 일하는가

2. Throughput(처리율) : 시간 단위당 실행을 완료한 프로세스의 수 (시간당 몇 개의 작업을 처리하였는가)

3. Turnaround Time(반환시간) : 작업이 Ready Queue에 처음 들어갔을 때부터 Terminated 되기까지의 시간

4. Waiting Time(대기시간) : 작업이 Ready Queue에서 CPU의 service를 받기까지 기다린 시간

5. Response Time(응답 시간) : 사용자가 컴퓨터에 명령을 내린 후 처음 응답을 받을 때까지 기다린 시간

---

프로세스 상태

상태 변환		프로세스 상태 변환의 내용
생성 → 준비	Admit	프로세스를 Ready Queue에 할당 (Job Scheduler가 담당)
준비 → 실행	Dispatch	Ready Queue에 있는 하나의 프로세스를 선택하여 CPU에 할당 (CPU Scheduler가 담당)
실행 → 준비	Time Slice Out	CPU를 할당받은 프로세스가 CPU의 제한된 사용시간을 모두 쓴 경우에 발생
실행 → 대기	I/O	CPU를 할당받은 프로세스가 I/O, 다른 자원 요구 등 CPU 이외의 서비스 작업을 원할 경우 발생
대기 → 준비	Wake Up	I/O 작업 처리와 같은 대기 중이던 프로세스의 이벤트의 처리가 끝났을 때 발생
실행 → 완료	Terminate	프로세스의 정상, 비정상 종료 시 발생

---

 CPU Scheduling의 종류

Preemptive(선점) vs Non-Preemptive(비선점)

ㆍ Preemptive(선점) : CPU가 현재 실행 중인 프로세스의 작업을 강제로 중단하고 다른 프로세스를 처리하는 방식

ㆍ Non-Preemptive(비선점) : 현재 실행 중인 프로세스가 종료되기 전까지는 다른 프로세스를 처리하지 않는 방식

 

Non-Preemptive(비선점)

FCFS(First Com First Served)

ㆍ 각 프로세스는 도착시간에 따라 CPU에 할당되는 방식이다.

ㆍ 비선점형 방식이기 때문에, CPU의 활용도가 떨어진다는 특성이 있다.

ㆍ 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹는 부정적인 형상에 주의해야 한다.

 

Non-Preemptive SJF(Shortest Job First)

ㆍ 수행 시간이 가장 짧은 프로세스에게 CPU를 먼저 할당하는 방식이다.

ㆍ FCFS 스케줄링과 마찬가지로 비선점형 방식이기 때문에, CPU의 활용도가 떨어진다는 특성이 있다.

ㆍ FCFS 스케줄링과 비교하여 비교적 빠른 대기시간과 반환시간을 가지고 있다.

 

Preemptive(선점)

Preemptive SJF(Shortest Job First)

ㆍ 현재 수행 중인 프로세스의 남은 수행 시간보다 더 짧은 수행 시간을 가진 프로세스가 도착하게 된다면, 현재 수행 중인 프로세스에게서 CPU을 빼앗아 새로 도착한 프로세스에게 CPU를 할당하는 방식의 스케줄링 기법이다.

ㆍ 선점형 방식이기 때문에 CPU 활용도가 높으며, 비선점형 스케줄링 기법에 비해 최소한의 평균 대기시간을 제공한다.

 

Round Robin

ㆍ 각 프로세스가 Time Quantum이라 불리는 시간의 양에 의해 제한되어 실행되는 특성을 가진 스케줄링 기법이다.

ㆍ Time Quantum이 크면 FCFS와 같게 되고, Time Quantum의 크기가 너무 작으면 실행시간에 차지하는 오버헤드가 많아져서 전체 실행시간이 느려지는 현상이 발생 가능하다. 이 같은 상황을 고려해서 적절한 Time Quantum의 설정이 필요하다.