[OS] CPU 스케줄링

박시은·2023년 11월 20일

OS

목록 보기

22/27

▶ CPU 스케줄링⭐

▷ 목적

CPU가 쉬지 않고 최대한 일을 하도록 하기 위해 CPU 스케줄링을 한다!
멀티프로그래밍을 통해 CPU 효율을 극대화 ( *오버헤드를 최소화 )
프로세들에게 합리적으로 CPU 자원 배분(=CPU 스케줄링)

Burst (버스트)
- 어떤 현상이 짧은 시간 안에 집중적으로 일어나는 것을 의미
- ex. 수강신청
CPU burst
- 프로세스가 CPU에서 연속적으로 CPU를 사용하는 시간 (job size)
I/O burst
- 프로세스가 IO 작업을 요청하고, 그 결과를 기다리는 시간 (CPU 사용x)

즉, 프로세스는 CPU burst와 I/O burst가 번갈아가며 실행되는 것을 알 수 있다.

CPU-Burst Times 히스토그램

I/O작업을 수행하는 빈도가 많아질수록 cpu burst시간이 짧아진다. (작은 job들이 많음)
CPU Burst 시간이 많은지(= CPU Bound), 적은지(= IO Burst 시간이 많음 = IO Bound)에 따라 분류할 수 있다.
- CPU Burst가 많은 프로세스 = CPU를 많이 사용하는 프로세스 (동영상 편집 프로그램, 머신러닝 프로그램)
- I/O Burst가 많은 프로세스 = I/O를 많이 사용하는 프로세스 (백엔드 API 서버, 비디오 재생)

▷ CPU 스케줄러

CPU 스케줄러란?
- ready 상태인 여러 프로세스 중에서 다음 실행할 프로세스를 선택하여 running 상태로 만드는 것
- 즉, ready queue에서 프로세스를 선택하여 CPU에 할당
- 이러한 할당 과정을 dispatch라고 한다.
  자세히 알고 싶다면 클릭하기!

디스패치 지연 (Dispatch Latency)
- 디스패처가 현재 실행 중인 프로세스를 멈추고, 다른 프로세스를 실행하는 시간을 의미한다.
- 즉, Context Switching 시간을 의미

▷ CPU 스케줄링 결정 시점

프로세스의 상태가 변화함에 따라, CPU 스케줄링 결정이 일어나는 상황
- ① Running → Waiting
- ② Running → Ready
- ③ Waiting → Ready
- ④ New → Ready
- ⑤ Terminates

Ready → Running 은?
- CPU 스케줄링 결정이 일어나지 않는다.
- 이미 정리되어 있는 Ready Queue에서 단순히 프로세스를 꺼내는 CPU로 할당시키는 것이기 때문이다.

▶ 선점 vs 비선점

구분	선점형 스케줄링	비선점 스케줄링
개념	① 가장 자원이 필요한 프로세스(우선순위 높음)에게 CPU를 분배하며, 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식 [ 새치기와 비슷한 개념 ]	① 프로세스가 종료되거나 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식 ② 하나의 프로세스가 자원 사용 독점
장점	하나의 프로세스의 자원 독점을 막고 골고루 배분 가능	① 선점형보다 문맥교환에 의한 오버헤드가 적다 ② 응답시간을 예상할 수 있다.
단점	문맥 교환 과정에서 오버헤드 발생	① 자원 골고루 사용 불가 ② 당장 사용해야 하는 상황에서도 무작정 기다림
발생 경우	현재 실행중인 프로세스가 계속 실행될 수 있고 다른 준비된 프로세스를 실행할 수 있으므로 선택의 여지가 있음 => 선점 ① Running → Ready ② Waiting → Ready ③ New → Ready	CPU가 아무 일도 하지 않아 반드시 새로운 프로세스를 실행해야 하므로 선택의 여지가 없음 => 비선점 ① Running → Waiting ② Terminates

⚠️ 선점 동작 방식에서의 주의사항
- 공유하는 자료를 갱신하고 있는 동안 선점 당하면 문제가 생긴다.
- 커널 작업 중에 선점 당하면, 커널의 중요한 자료에 문제가 생길 수 있다.
- 중요한 운영체제 작업 중에는 인터럽트의 발생을 불허한다.

▶ 스케줄링 기준

스케줄링 기준

CPU utilization (CPU 이용률)
- CPU를 최대한 일하게 한다.
Throughput (처리량)
- 단위시간당 실행을 완료하는 프로세스들의 개수
Turnaround time (총 처리 시간)
- 프로세스의 제출시간과 완료시간의 간격
- Ready Queue 대기시간 + CPU실행시간 + I/O 시간
  - 제출시간: 프로세스가 Ready Queue에 들어온 시간
  - 완료시간: 프로세스가 ‘Terminated’되거나, ‘Waiting을 거쳐 Ready’로 변경된 순간의 시간 ⇒ ‘I/O 시간’
Waiting time (대기 시간)
- Ready Queue에서 대기하면서 보낸 시간의 합
Response time (응답시간)
- 대화식 시스템에서 응답이 시작되는 데 까지 걸리는 시간
- 평균 응답시간이 짧아야 하고, 응답시간의 편차가 작아야 한다.
- ex. 터미널에 키보드로 A 입력시, A가 입력되었음을 시스템이 알아차리는데 걸리는 시간
Burst time(실행 시간)
- CPU 할당 후 입출력을 요구할 때까지의 시간

스케줄링 알고리즘 최적화 기준

Max CPU Utilization (CPU 이용률 최대화)
Max Throughput (처리량 최대화)
Min Turnaround Time (총 처리시간 최소화)
Min Waiting Time (대기시간 최소화)
Min Response Time (응답시간 최소화)

▶ CPU 스케줄링 종류

▷ FCFS (선입 선처리 스케줄링)

FCFS(First Come, First Serve)
- Ready Queue에 먼저 도착한 프로세스 먼저 처리
- 비선점 방식의 스케줄링 (중간에 CPU를 뺏기지 않음, 공평성 보장)
- 호위 효과 (Convoy Effect)
  - 긴 프로세스 뒤에 작은 프로세스가 있을때 모두 긴 작업을 대기해야 하는 상황
  - 미국 옥수수🌽 트럭 등치 아저씨 생각하기... 30분 넘게 아무도 못 지나가

예시 ①

process	Burst Time (연속사용시간)
P1	24
P2	3
P3	3

가정: Burst Time은 위와 같고, 프로세스가 순차적으로 도착(P1, P2, P3)
[ 간트 차트 ]
- 총 처리 시간 (Turnaround Time) → Burst Time의 합산
  24 + 3 + 3 = 30
- 대기시간 (Wairing time)
  FCFS에서의 특정 프로세스 대기시간 = 특정 프로세스의 시작시간
  P1 = 0, P2 = 24, P3 = 27 (24+3)
- 평균 대기시간 (Average waiting time)
  (0 + 24 + 27) / 3 = 17
- 예시 ①은, [ 호위효과(Convoy Effect)🌽가 발생한다! ]

예시 ②

process	Burst Time (연속사용시간)
P1	24
P2	3
P3	3

가정: P2 , P3 , P1순으로 프로세스가 도착
[ 간트 차트 ]
- 대기시간 (Waiting time)
  P1 = 6, P2 = 0, P3 = 3
- 평균 대기시간 (Average waiting time)
  (6 + 0 + 3) / 3 = 3
- 순서 조정만 했을 뿐인데 평균 대기 시간이 크게 감소한 것을 확인할 수 있다. (호위효과 발생 x)

▷ SJF (최단 작업 우선 스케줄링)

SJF (Shortest Job First)
- 호위 효과를 방지하기 위해 Burst Time(CPU 이용시간)이 가장 짧은 프로세스부터 먼저 처리
- 비선점형 스케줄링 방식이라서 Burst Time이 긴 프로세스의 경우 기아 상태가 발생 할 수 있다.
- FCFS보다는 Waiting Time을 줄일 수 있다.
- 가장 적은 평균 대기 시간을 보장하는 효과적인 알고리즘이지만, 각 프로세스의 CPU Burst Time을 미리 알기가 힘들다. (시뮬레이션 해보지도 않았는데 모든 job들의 사이즈 알 수 없음.)

예시 ①

process	Burst Time (연속사용시간)
P1	6
P2	8
P3	7
P4	3

[ 간트 차트 ]
평균 대기 시간 (Average waiting time)
(3 + 16 + 9 + 0) / 4 = 7

다음 CPU Burst Time 예측

SJF는 가장 좋은 스케줄링 방법이지만 CPU Burst Time을 미리 알 방법이 없다.
- 따라서, CPU Burst Time을 예측해야한다.
예측 방법 (~~시험에 안나온다고 하심😄~~)
- "다음 프로세스의 버스트 길이가 직전 프로세스의 버스트 길이와 비슷할 것이다." 라는 가정을 통해 CPU의 Burst Time을 예측한다.

▷ SRTF (최소잔여시간우선)⭐

SRTF (Shortest-Remaining-Time-First)
- 선점형 SJF를 SRTF라고 한다.
- 즉, 현재 진행중인 프로세스를 중단시키고 CPU 점유시간이 짧게 남은 프로세스 처리를 가능하게 한다.
- 도착시간이 다른 것과 선점의 개념을 추가한다.

SRTF에서 Turnaround Time (총처리시간) 구하기
- 프로세스의 Turnaround Time = 완료시간 - 도착시간
SRTF에서 Waiting Time (대기시간) 구하기
- 프로세스의 Waiting Time = Turnaround Time - Burst Time

예시

process Arrival Time Burst Time (연속사용시간)
P1 0 8
P2 1 4
P3 2 9
P4 3 5
- [ 간트 차트 ]
  ❗현재 들어온 프로세스의 Burst time이 현재 실행중인 프로세스의 Burst time보다 작을 때만 선점이 일어난다.
반환 시간 (Turnaround Time)
- P1 Turnaround Time : 17 - 0 = 17
- P2 Turnaround Time : 5 - 1 = 4
- P3 Turnaround Time : 26 - 2 = 24
- P4 Turnaround Time : 10 - 3 = 7
대기 시간 (Waiting Time)
- P1 Waiting Time : 17 - 8 = 9
- P2 Waiting Time : 4 - 4 = 0
- P3 Waiting Time : 24 - 9 = 15
- P4 Waiting Time : 7 - 5 = 2
총 처리 시간 (Turnaround Time)
- 8 + 4 + 9 + 5 = 26ms
평균 대기 시간 (Average waiting time)
- (9 + 0 + 15 + 2) / 4 = 6.5 (msec)

process	Arrival Time	Burst Time (연속사용시간)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

▷ PS (우선순위 스케줄링)

PS (Priority Scheduling)
- 각 프로세스에게 숫자로 우선순위를 표기하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 방식이다.
- SJF도 우선순위 스케줄링의 일종이다.

Priority Scheduling 종류
- Preemptive(선점형) Priority Scheduling
  - 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높으면 CPU를 선점한다.
  - Priority는 낮을수록 좋다. (but 시스템 따라 다를 수 있음)
- Nonpreemptive(비선점형) Priority Scheduling
  - 우선순위가 가장 높은 프로세스를 Ready Queue의 맨 앞에 넣는다.

우선순위는 Burst Time(길이)에 반비례한다.
- 긴 Burst ⇒ 우선순위가 낮음
- 짧은 Burst ⇒ 우선순위가 높음

문제점⭐
- 기아 상태(Starvation)
  - 낮은 우선순위의 프로세스가 계속해서 대기만 하는 상태
  - 내가 size가 크다고 계속 우선순위가 높은 애들이 새치기를 해대면 굶어 죽을거야😭😇
해결 방안⭐
- 에이징(Aging) 기법
  - 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  - 나이 먹으면 우선순위 증가됨

예시

process	Burst Time (연속사용시간)	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

[ 간트 차트 ]
❗단순히 우선순위가 가장 높은 순서대로 실행된다.
평균 대기 시간 (Average waiting time)
- 8.2 (msec)

▷ RR (라운드 로빈)⭐

RR (Round Robin)
- 시분할 시스템을 위해 설계된 선점형 스케줄링 방식
- 정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용한다.
  - 시간할당량(CPU 시간) = q (Quantum)
시간 q를 모두 사용했음에도 프로세스가 완료되지 않았다면, 실행 중이던 프로세스가 선점(새치기)당하여 준비완료 큐의 끝에 가게 된다. -> 문맥 교환 발생

예시
- 준비완료 큐에 5개의 프로세스 존재하고, q(시간할당량)가 20밀리초이면,
  각 프로세스는 매 100밀리초마다 최대 20밀리초를 할당 받는다.

시간할당량(q)에 따른 성능

q가 너무 클 때
- FCFS와 동일하게 동작한다. (어떤 job이 들어와도 제시간에 끝남)
- Convoy Effect(호위 효과) 가 발생할 수 있다.
q가 너무 작을 때
- Context Switching 이 매우 빈번하게 일어난다.
- 따라서 문맥 교환 발생이 많이 발생 -> 오버헤드 발생
정리
- 시간할당량(q)는 보통 10ms ~ 100ms로 설정한다.
- 그리고 Context Switching 시 오버헤드는 10마이크로초 이내여야 한다.