CPU 스케쥴링 예제 총정리 | 선점형 비선점형 (FCFS ,SJF ,HRN ,RR ,SRT) 완벽 비교

CPU 스케쥴링의 정의

CPU 스케쥴링은 프로세스가 CPU를 효율적으로 공유하게 하는 기법입니다. 무슨 뜻이냐 
운영체제에서 준비 상태에 있는 여러 프로세스 중에서 CPU를 할당할 프로세스를 결정하는 작업

즉 "어떤 프로세스부터 CPU를 먼저쓸지 결정하는 것" 입니다.

---

CPU 스케쥴링 종류

이 CPU스케쥴링은 종류가 2가지로 아래와 같이 나뉩니다.

• 비선점형 스케쥴링 (Non-preemptive) 한 프로세스가 cpu를 할당 받으면 자발적으로 cpu를 반환 할때까지 계속 사용하는 방식
• 선점형 스케쥴링(Preemtive)
  운영체제가 실행중인 프로세스보다 더 높은 우선순위가 배정되었을때  해당 cpu를  강제로 빼앗을 수 있는 방식

구분	비선점형 스케줄링 (Non-preemptive)	선점형 스케줄링 (Preemptive)
특징	CPU 점유권을 스스로 포기할 때까지 유지	우선순위가 높은 프로세스가 오면 즉시 선점 가능
응답 속도	느림 (대기 시간 길어짐)	빠름 (즉각 반응 가능)
문맥 교환	적음	많음 (오버헤드 발생 가능)
안정성	예측 가능, 안정적	실시간 처리에 유리하지만 복잡
예시	FCFS, SJF(비선점형), HRN	SRTF, Round Robin, Priority(선점형)

---

비선점형 스케쥴링의 종류

1.FCFS

준비큐에 도착한 순서대로 cpu에 할당하는 가장 단순한 방식

장점 : 구현 간단
단점 : 긴 프로세스가 짧은 프로세스들을 장시간 대기 시킴

예제

프로세스	도착시간	사용시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

풀이

최종 정리표)

프로세스	도착시간	사용시간	시작시간	종료시간	대기시간
P1	0	8	0	8	0 - 0 = 0
P2	1	4	8	12	8 - 1 = 7
P3	2	2	12	14	12 - 2 = 10
P4	3	1	14	15	14 - 3 = 11

실행순서: 도착 순서대로 실행  p1->p2->p3->p4
평균 대기시간: (0 + 7 + 10 + 11) / 4 = 7ms

---

2.SJF(Shortest Job First)

실행시간이 가장 짧은 프로세스부터 실행

장점: 평균 대기시간이 최소화 
단점: 사용시간이 긴 작업이 무한 대기 가능성인 기아현상 (Starvation) 발생

예제

프로세스	도착시간	사용시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

풀이

최종 정리표)

프로세스	도착시간	사용시간	시작시간	종료시간	대기시간
P1	0	8	0	8	0 - 0 = 0
P4	3	1	8	9	8 - 3 = 5
P3	2	2	9	11	9 - 2 = 7
P2	1	4	11	15	11 - 1 = 10

실행순서: 가장 짧은 사용시간 우선 사용 p1->p4->p3->p2
평균 대기시간: (0 + 5 + 7 + 10) / 4 = 5.5ms

---

3.HRN

응답률이 높은 프로세스부터 우선처리 

응답률=(대기시간+사용시간)/사용시간

장점 : SJF의 기아(Starvation)문제 보완함
단점: 응답률 계산 오버헤드, 실제 사용 잘 안함

예제

프로세스	도착시간	cpu사용시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

풀이

1.시간(0) 

도착 프로세스는 P1만있으므로 -> P1 실행 (0~8)

프로세스	도착시간	대기시간	서비스시간	응답률
P1	0	0	8	(0+8)/8 = 1.0

2.시간(8)

p1은 종료가 끝났고 p1실행중일 때 p2,p3,p4도착 후 대기중,
각 프로세스별 응답률 계산

프로세스	도착시간	사용시간	현재시간	대기시간	응답률 계산
P2	1	4	8	8 - 1 = 7	(7+4)/4 = 2.75
P3	2	2	8	8 - 2 = 6	(6+2)/2 = 4.0
P4	3	1	8	8 - 3 = 5	(5+1)/1 = 6.0

위 3개중 응답률이 가장 높은 P4 실행(8~9)

반응형

3.시간(9)

남은 프로세스 p2,p3 응답률 계산

프로세스	도착시간	사용시간	대기시간	응답률 계산
P2	1	4	9 - 1 = 8	(8+4)/4 = 3.0
P3	2	2	9 - 2 = 7	(7+2)/2 = 4.5

응답률이 높은 p3 실행(9~11)

4.시간(11)

남은 프로세스 p2 실행

프로세스	도착시간	사용시간	대기시간	응답률 계산
P2	1	4	11 - 1 = 10	(10+4)/4 = 3.5

최종 정리표)

프로세스	도착시간	cpu사용시간	시작시간	종료시간	대기시간
P1	0	8	0	8	0 - 0 = 0
P4	3	1	8	9	8 - 3 = 5
P3	2	2	9	11	9 - 2 = 7
P2	1	4	11	15	11 - 1 = 10

실행순서: 응답률 우선 처리  p1->p4->p3->p2
평균 대기시간: (0 + 5 + 7 + 10) / 4 = 5.5ms

---

선점형 스케쥴링의 종류

1.RR(Round Robin)

각 프로세스에 타임 슬라이스 시간을 할당하고 해당 시간 후에 강제로 cpu 를 빼앗아 큐의 뒤로 이동

장점: 응답이 빠르고 모든 프로세스가 공정한 기회를 얻음
단점: 타임슬라이스 작으면 컨텍스트 스위칭 오버헤드 증가

예제

타임 퀀텀(2ms)

프로세스	도착시간	사용시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

 

풀이

• (0~2): P1(남은 6ms)
• (2~4): P2(남은 2ms)
• (4~6): P3(완료)
• (6~8): P4(완료)
• (8~10): P1(남은 4ms)
• (10~12): P2(완료)
• (12~14): P1(남은 2ms)
• (14~16): P1(완료)

최종 정리표)

프로세스	도착시간	사용시간	시작시간	종료시간	대기시간
P1	0	8	0	16	16 - 0 - 8 = 8
P2	1	4	2	12	12 - 1 - 4 = 7
P3	2	2	4	6	6 - 2 - 2 = 2
P4	3	1	6	8	8 - 3 - 1 = 4

실행순서: p1->p2->p3->p4
평균 대기시간: (8 + 7 + 2 + 4) / 4 = 5.25ms

---

2.SRT(Shortest Remaining Time First)

SJF의 선점형 버젼입니다. 실행중인 프로세스보다 남은시간이 짧은 새 프로세스가 도착하면 즉시 전환 합니다.

장점: 평균 대기 시간 최소화
단점: 컨텍스트 스위칭 오버헤드 , 기아 현상 가능

예제

프로세스	도착시간	사용시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

풀이

• (0~1): P1(남은 7ms) ← P2 도착
• (1~2): P2(남은 3ms) ← P3 도착
• (2~3): P3(남은 1ms) ← P4 도착
• (3~4): P4(완료)
• (4~5): P3(완료)
• (5~8): P2(완료)
• (8~16): P1(완료)

최종 정리표)

프로세스	도착시간	사용시간	시작시간	종료시간	대기시간
P1	0	8	0	16	16 - 0 - 8 = 8
P2	1	4	1	8	8 - 1 - 4 = 3
P3	2	2	2	5	5 - 2 - 2 = 1
P4	3	1	3	4	4 - 3 - 1 = 0

실행순서: 남은 시간이 가장 짧은 프로세스 우선 처리  p3->p4->p8->p1
평균 대기시간: (8 + 3 + 1 + 0) / 4 = 3ms