CPU 스케줄링

지섭·2023년 7월 21일

CPU 스케줄링의 목표

CPU 스케줄링: 다른 프로세스가 suspended 되어있는 동안 어떤 프로세스가 CPU를 사용할 지 결정하는 것
멀티프로그래밍에서 CPU 활용도(Utilization)을 최대화하기 위해 사용
프로세스 실행 과정에서 CPU burst-I/O burst 사이클이 일어남

CPU burst -> I/O burst -> CPU burst -> I/O burst
- CPU burst: CPU가 더 이상 ready 상태가 아닐 때까지 사용하는 시간
- I/O burst: 프로세스가 I/O를 기다리는 시간(CPU burst 전까지 기다리는 시간)
CPU burst를 어떻게 분배할지가 주요 문제
CPU burst는 짧은 burst가 대부분, 긴 burst는 잘 안 일어남

CPU 스케줄러

CPU 스케줄러가 ready queue에 있는 프로세스들 중에서 선택해서 CPU 코어를 할당해줌

CPU 스케줄링은 크게 비선점, 선점 방식으로 나눌 수 있음:

비선점(nonpreemptive) 방식: 프로세스 상태가 다음 네 가지 경우에 해당할 때
1) running -> waiting
2) running -> ready
3) waiting -> ready
4) terminates

프로세스가 running 상태에 있을 때, 종료되거나 I/O로 인해 block될 때까지 실행

선점(preemptive) 방식: 위의 방식이 아닌 모든 스케줄링은 선점 방식
ex) 공유 자원에 접근, 인터럽트 등

running 상태의 프로세스가 interrupt 일어나고, OS에 의해 ready 상태로 옮겨짐

디스패처(dispatcher): dispatch(할당하다) + er

스케줄러가 선택한 프로세스에 CPU를 할당하는 역할을 함

디스패치 지연시간(dispatch latency): 디스패처가 하나의 프로세스를 정지하고, 다른 프로세스가 실행되도록 하는데 걸리는 시간

스케줄링 시 기준(criteria)

CPU 사용량(CPU Utilization), 높을수록 좋음
처리량(Throughput), 높을수록 좋음
프로세스 실행 시간(Turnaround time), 낮을수록 좋음
대기 시간(Waiting time) - 프로세스가 ready queue에 대기하는 시간, 낮을수록 좋음
응답 시간(Response time) - 요청이 일어났을 때, 첫 응답(결과 말고)이 일어나는데 걸리는 시간, 낮을수록 좋음

비선점(nonpreemptive)

First-Come-First-Serve

도착 순서대로 처리함

Shortest Job Next(SJN) or Shortest Job First(SJF)

큰 프로세스는 starvation(자원 충분히 받지 못하는 현상) 발생

Priority Scheduling

우선순위 낮은 프로세스 starvation 발생
대기 시간(Waiting time)을 고려하는 방식으로 보상할 수 있음

Deadline Scheduling

Hard RTS(real-time system) 스케줄링
특정 deadline 전에 실행이 완료되어야 함

Round-Robin

GPOS(General Purpose OS, 범용 OS
ex) Windows, Mac)에 많이 사용
time slice가 주어지고, 주어진 time slice가 모두 끝나면 다른 프로세스로 전환
공평하게 프로세스 실행 가능
중요한 프로세스가 시간을 충분히 할당받지 못함

<Time slice(quantum)을 너무 많이 쪼개면 컨텍스트 스위칭 자주 발생 -> 비효율적>

선점(preemptive)

높은 우선순위의 프로세스가 CPU를 요청하면 낮은 우선순위의 프로세스는 CPU 요청하면 양보함
최적의 스케줄링을 위해서 컨텍스트 스위칭을 고려해야 함

Shortest Remaining Time
- 남은 시간이 적은 프로세스부터 처리
Priority Scheduling
- P: priority inversion
- S: priority inheritance
비선점 방식, 선점 방식 각각이 문제를 가지고 있는데,
비선점 방식은 우선순위 높은 작업에 시간을 충분히 사용하지 못하는 문제가 있고, 선점 방식은 우선순위 낮은 작업이 starve하는 문제 있음.