프로세스 스케줄링

1. 선점(Preemptive) 스케줄링

선점 스케줄링이란 우선순위가 높은 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유하는 스케줄링 기법

실행 중인 프로세스를 중단하고,더 우선순위가 높은 다른 프로세스에게 CPU를 양보
비교적 응답이 빠르다는 장점이 있으나, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드가 발생하게 된다.
선점 스케줄링의 예로는 RR, SRT, 다단계 큐, 다단계 피드백 큐가 있음.

📌 선점 스케줄링 알고리즘
🔹 Round Robin : 시간 할당량(Time Quantum) 지나면 다음 프로세스로 교체
🔹 SRTF (Shortest Remaining Time First) : 남은 시간이 더 짧은 새 작업이 오면 현재 작업 중단
🔹 선점형 우선순위(Priority Scheduling) : 더 높은 우선순위의 프로세스가 도착하면 중단됨

2. 비선점(Non-preemptive) 스케줄링

프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 기법

한 번 실행된 프로세스는 끝날 때까지 CPU를 점유한다. 그래서 새로 도착한 프로세스는 대기해야 한다.
중요한 작업이 길면, 뒤에 있는 짧은 작업이 오래 기다릴 수 있기 때문에 기아현상 발생 가능

📌 비선점 스케줄링 알고리즘
🔸 FCFS (First Come First Serve) : 먼저 도착한 순서대로 실행
🔸 SJF (Shortest Job First) : 실행시간이 짧은 것부터 실행
🔸 비선점 우선순위 스케줄링 : 우선순위 높은 순으로 실행, 중간 교체 없음
🔸 HRN (Highest Response Ratio Next) : 반응 비율 기반, 대기시간 고려

문제풀이

비선점은 들어온 순서대로 처리하니까 쉬움
선점형은 실행 도중에도 더 짧은 프로세스가 도착하면 현재 작업을 중단하고 짧은 걸 먼저 실행하므로실행 순서가 바뀜

1.FCFS

난이도 ⭐
도착한 순서대로 처리하면 됨

최소 평균 반환시간 t 는 실행시간이 짧은 것부터 실행 (P2 → P1 → P3)
t = ( 0 + 3 + 12 ) / 3 = 15 / 3 = 5
최대 평균 반환시간 T 는 실행시간이 긴 것부터 나열 (P3 → P1 → P2)
T = (0 + 12 + 21) / 3 = 33 / 3 = 11
T - t = 11 - 5 = 6

2.SFJ

난이도 ⭐
실행시간 짧은 것부터 실행하면 됨
평균대기시간 / 평균반환시간 / 평균실행시간 중 무엇을 구해야 하는지 확인

프로세스	실행시간	대기시간	반환시간
P-2	3	0	3
P-1	6	3	9
P-4	7	9	16
P-3	8	16	24
		28 / 4 = 7	52 / 4 = 13

Task	도착시간	실행시간	대기시간	반환시간
Task1	0	6	0	6
Task2	1	3	6	9
Task3	2	2	9	2
합계			15	17

Task2의 반환시간 = 2의 대기시간(Waiting Time) + 2의 실행시간(Burst Time) = 6 + 3 = 9

⭐ 도착시간이 0일 때 T1만 도착했기 때문에 T1가 실행시간이 길더라도 먼저 실행된다. (왜? 해당 시간에 도착한 작업이 T1뿐)

3.HRN

난이도 ⭐
비선점 스케줄링 알고리즘 중 하나로, 대기시간이 길어질수록 우선순위가 높아지는 방식
우선순위 = 1 + 대기시간/서비스 시간
→ 숫자가 클수록 우선순위가 높다!

✅ HRN 우선순위 계산식

대기시간 (Waiting Time) = 현재 시점 − 도착시간 − 아직 실행 안 된 경우
서비스시간 (Service Time) = 실행시간, 즉 Burst Time
짧은 작업(SJF)에게 유리하면서도,오래 기다린 작업도 점점 우선순위가 높아져 기아 현상(starvation) 방지 가능!

A = 1 + (8 / 2) = 1 + 4 = 5
B = 1 + (10 / 6) = 2.6666
C = 1 + (15 / 7) = 3.14
D = 1 + (20 / 8) = 3.5
우선 순위 큰 순서대로 A > D > C > B

4.SRT

난이도 ⭐⭐
SRT(Shortest Remaining Time First)는 선점형 프로세스 스케줄링 알고리즘 방식
현재 실행 중인 프로세스보다 남은 실행시간이 더 짧은 새로운 프로세스가 도착하면 CPU를 양보하기
그래프 그리면서 풀기
반환시간 = 종료시간 - 도착시간

5.RR(Round Robin)

난이도 ⭐⭐⭐
타임 퀀텀 (Time Quantum) 이 주어짐
선입선출 (FIFO) 방식으로 할당시간(타임 퀀텀)만큼 실행 후 대기 큐로 이동
새로운 작업이 도착하면 도착 순서대로 대기 큐에 추가
대기큐 + 남은 시간 두 개를 그리면서 풀어야 함
무조건 짧은게 우선이 아니라 큐에 들어간 순서대로 다시 실행되므로 만약 프로세스가 3개면 3개가 번갈아 가면서 실행됨
유형 : CPU 사용 순서 / 평균 대기시간 / 평균 반환시간 문제!
⭐ 대기 시간 (Waiting Time, WT) = 완료 시간 (FT) - 도착 시간 (AT) - 실행 시간 (BT)
⭐ 반환 시간 (Turnaround Time, TAT) = 완료 시간 (FT) - 도착 시간 (AT)

CPU 사용 순서 문제

라운드 로빈 방식에서 주의할 점

⭐ 남은 실행 시간만 보고 풀면 틀린다.

⭐ 대기큐를 그려야 한다.

라운드 로빈 (RR) 스케줄링을 풀 때 대기 큐의 순서를 반드시 고려해야 한다. 단순히 "남은 실행 시간"만 보고 짧은 작업을 먼저 실행하는 것이 아니라, 큐에 들어간 순서대로 작업이 실행된다.

타임 퀀텀(시간 할당)이 끝나면 무조건 대기 큐로 이동! → 대기 큐에 있는 순서대로 실행! → 남은 실행 시간이 짧아도 먼저 실행되지 않음 → 그래서 모든 작업이 번갈아가면서 실행됨

라운드 로빈에서는 남은 시간이 적은 작업이 있더라도 먼저 들어온 순서대로 실행된다. 즉, ABC 세 개의 작업이 남아 있다면, ABC 순서대로 계속 번갈아가면서 실행된다. 이걸 놓치면 잘못된 순서로 풀게 되어 답이 틀릴 수 있다.