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

비선점 스케줄링 알고리즘은 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스캐줄링 기법입니다.

프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용하게 됩니다.

모든 프로세스에 대한 요구를 공정하게 처리할 수 있고 프로세스 응답 시간의 예측이 용이하며, 일괄 처리 방식에 적합하다는 장점이 있습니다.

하지만 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있다는 단점이 있습니다.

비선점 스케줄링 알고리즘으론 FCFS, SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있습니다.

그 중 FCFS, SJF, HRN 알고리즘에 대해서 알아보겠습니다.

---

성능 기준

스케줄링 성능은 평균 대기 시간, 평균 실행 시간, 평균 반환 시간으로 측정합니다.

• 대기 시간 : 프로세스가 대기한 시간으로, 프로세스가 준비상태 큐에 들어온 시간부터 측정이 됩니다. 수식으로 정리하자면 반환 시간 - 수행 시간 - 도착시간 입니다
• 실행 시간 : 프로세스가 CPU를 할당받아 실행한 시간입니다.
• 반환 시간 : 프로세스의 대기 시간과 실행시간의 합입니다.

---

FCFS (First Come First Service, 선입선출)

준비상태 큐에 도착한 순서대로 차례로 CPU를 할당하는 기법으로 가장 간단한 알고리즘입니다.

먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됩니다.

상황 1

프로세스 번호	P1	P2	P3
실행 시간	20	4	6

위와 같은 상황에서 P1, P2, P3 순서로 큐에 들어왔으면

진행시간	P1	P2	P3
0	실행	0	0
20	완료	20대기, 실행	20대기
24		완료	24대기, 실행
30			완료

위와 같이 진행되며

평균 실행 시간 : (20 + 4 + 6) / 3 = 10

평균 대기 시간 : (0 + 20 +24) / 3 = 14.6666...

평균 반환 시간 : (20 + 24 + 30) / 3 = 24.6666...

으로 측정됩니다.

상황2

작업	도착 시간	CPU 사용 시간
P1	0	13
P2	3	35
P3	8	25

진행 시간	P1	P2	P3
0	실행
3	실행3 중	도착
8	실행8 중	대기5	도착
13	실행13 완료, 반환 13	대기10, 실행	대기 5
48		실행 35 완료, 반환 45(10+35)	대기 40
73			실행 25 완료, 반환 65(40+25)

위와 같이 진행되며

평균 실행 시간 : (13 + 35 + 25) / 3 = 24.3333...

평균 대기 시간 : (0 + 10 + 40) / 3 = 16.6666...

평균 반환 시간 : (13 + 45 + 65) / 3 = 41

으로 측정됩니다.

---

SJF (Shortest Job First, 단기 작업 우선)

준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법입니다.

가장 적은 평균 대기 시간을 제공하는 최적 알고리즘이지만 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생할 수 있습니다.

상황1

작업	도착 시간	CPU 사용 시간
P1	0	20
P2	0	4
P3	0	6

진행 시간	P1	P2	P3
0	대기0	실행	대기0
4	대기4	실행4 완료, 반환 4	대기4, 실행
10	대기10, 실행		실행6완료, 반환 10
30	실행20완료, 반환 30

위와 같이 진행되며

평균 실행 시간 : (20 + 4 + 6) / 3 = 10

평균 대기 시간 : (10 + 0 + 4) / 3 = 4.6666.....

평균 반환 시간 : (30 + 4 + 10) / 3 = 14.6666....

으로 측정됩니다.

상황2

작업	도착 시간	CPU 사용 시간
P1	0	20
P2	1	7
P3	2	4

진행 시간	P1	P2	P3
0	실행
1	실행1	도착
2	실행2	대기1	도착
20	실행20완료, 반환 20	대기19	대기18, 실행
24		대기 23, 실행	실행4 완료, 반환 22
31		실행7완료, 반환 30

위와 같이 진행되며

평균 실행 시간 : (20 + 7 + 4) / 3 = 10.3333.....

평균 대기 시간 : (0 + 23 + 18) / 3 = 13.6666.....

평균 반환 시간 : (20 + 30 + 22) / 3 = 24

으로 측정됩니다.

상황 3

작업	도착 시간	CPU 사용 시간
P1	0	6
P2	1	3
P3	2	4

진행 시간	P1	P2	P3
0	실행
1	실행1	도착
2	실행2	대기1	도착
6	실행6완료, 반환 6	대기5, 실행	대기4
9		실행3완료, 반환 8	대기7,  실행
31			실행4완료, 반환 11

위와 같이 진행되며

평균 실행 시간 : (6 + 3 + 4) / 3 = 4.3333....

평균 대기 시간 : (0 + 5 + 7) / 3 = 3

평균 반환 시간 : (6 + 8 + 11) / 3 = 8.3333....

으로 측정됩니다.

---

HRN (Hightest Response-ratio Next)

실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법입니다.

우선 순위 계산 공식을 이용하여 서비스 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당합니다.

우선 순위 계산 공식은
(대기 시간 + 서비스 시간) / 서비스 시간
입니다.

우선순위를 계산하여 그 숫자가 높은 것부터 낮은 순으로 우선순위가 부여됩니다.