비선점 프로세스 스케줄링(Non-Preemptive scheduling)

이 문서의 내용

OS는 CPU를 효율적으로 사용하기 위해서 프로세스 스케줄링을 수행합니다. 

멀티 프로세스 환경에서 Context Switching에 따른 오버헤드가 발생하며, 이를 최소화 하기 위한 기법이 프로세스 스케줄링입니다. 

프로세스 스케줄링은 크게 선점 스케줄링과 비선점 스케줄링으로 구분되며 구현 방식에 따라서 더 세분화됩니다.

비선점 스케줄링(Non-Preemptive scheduling)

다른 프로세스가 CPU를 사용하고 있을 때 이를 선점하지 못하고 CPU 할당을 대기하는 스케줄링입니다.

비선점 스케줄링은 구현 방식에 따라서 다음과 같이 구분됩니다.

FCFS/FIFO	SJF	Priority based	HRN
단순 선입 선출로 CPU 선점	CPU burst time이 짧은 작업부터 CPU 선점	임의의 우선 순위를 할당하여 CPU 선점	대기 시간과 CPU burst time을 계산하여 응답률이 높은 작업부터 CPU 선점

한 번 CPU를 할당 받은 프로세스는 작업이 끝날 때까지 CPU를 사용하고 반환합니다. 따라서 응답 시간을 예측하기 쉽습니다.

다른 프로세스의 CPU를 선점하지 못하므로 나중에 작업 풀에 들어온 중요도가 높은 작업이 늦게 실행 될 수 있습니다.

비선점 스케줄링: 선입 선출(FCFS/FIFO)

대표적인 비선점 스케줄링 구현 방법은 FCFS(First-Come First-Served)입니다.

Queue 자료 구조에서의 선입 선출(FIFO, First-In First-Out) 스케줄링으로 단순히 먼저 들어온 작업에 CPU를 우선 선점하게 됩니다.

Process	Order	Arrival time	CPU burst time
P1	1	0	10
P2	2	2	3
P3	3	4	5

• P1 프로세스는 0초에 CPU를 선점합니다.
• P2 프로세스는 10초에 CPU를 선점합니다.
• P3 프로세스는 13초에 CPU를 선점합니다.

비선점 스케줄링: 최단 작업 우선(SJF, Shortest-Job First)

SJF는 CPU burst time이 짧은 작업이 CPU를 선점하는 스케줄링입니다. 따라서 각 작업이 처리되는데 필요한 시간을 예상 할 수 있을 때 사용됩니다.

Process	Order	Arrival time	CPU burst time
P1	1	0	7
P2	3	2	7
P3	2	4	4

• P1 프로세스는 0초에 CPU를 선점합니다.
• P2 프로세스가 2초에 도착하고 P3 프로세스가 4초에 도착합니다.
• P2 프로세스가 먼저 도착했지만 P3 프로세스의 CPU burst time이 더 짧기 때문에 7초에 CPU를 선점합니다.
• P2 프로세스는 11초에 CPU를 선점합니다.

비선점 스케줄링: 우선 순위 기반(Priority based)

우선 순위 기반 스케줄링은 프로세스에 임의의 우선 순위를 적용하여 CPU를 선점하는 방법입니다.

FCFS 또는 SJF와 달리 복잡한 알고리즘에 의해 우선 순위가 적용되기 때문에 비선점 스케줄링 중에서 비교적 시스템 응답 속도가 높은 스케줄링입니다.

반면 스케줄링을 위한 우선 순위 할당 알고리즘에 오류가 있는 경우 오히려 성능이 저하 될 수 있습니다.

Process	Order/Task	Arrival time	CPU burst time
P1	1 Business logic	0	7
P2	3 DB Read	2	2
P3	2 DB Write	4	9

• P1 프로세스는 0초에 CPU를 선점합니다.
• P2 프로세스가 2초에 도착하고 P3 프로세스가 4초에 도착합니다.
• P2 프로세스가 먼저 도착했지만 P3 프로세스의 작업이 더 중요하기 때문에 7초에 CPU를 선점합니다.
• P2 프로세스는 16초에 CPU를 선점합니다.

비선점 스케줄링: HRRN(Highest Response Ratio Next)

HRRN은 시스템 응답 시간에 따른 스케줄링으로 SJF와 우선 순위 기반 스케줄링의 혼합된 형태입니다.

대표적인 HRN의 우선 순위 결정 로직은 다음과 같습니다.

HRRN 우선 순위 = 시스템 응답률 = (CPU burst time + Waiting time) / CPU burst time

위 공식에 따라서 CPU를 선점하지 못한 시간이 길어질수록 우선 순위가 증가합니다.

Process	Order	Response ratio	Arrival time	CPU burst time
P1	1	1 = (7+0)/7	0	7
P2	3	1.83 = (6+5)/6	2	6
P3	2	2 = (5+5)/5	2	5

• P1 프로세스는 0초에 CPU를 선점합니다.
• P2와 P3 프로세스가 2초에 도착합니다.
• P2와 P3 프로세스는 7초에 CPU를 선점하기 위해 시스템 응답 시간을 계산합니다.
• P2 프로세스의 응답률은 1.83, P3 프로세스의 응답률은 2로 응답률이 더 좋은 P3 프로세스가 7초에 CPU를 선점합니다.
• P2프로세스는 12초에 CPU를 선점합니다.

우선 순위를 결정하기 위해 대기 시간에 의존하기 때문에 CPU burst time이 동일한 상황에서도 다른 스케줄링 결과가 나올 수 있습니다.

상기 예시에서 P3 프로세스가 4초에 도작한 경우라면 응답률이 1.6이 되므로 P2 프로세스가 CPU를 선점하게 됩니다.

정리 및 복습

• FCFS(First-Come First-Served) 스케줄링은 선입 선출(FIFO)로 단순히 먼저 들어온 작업이 CPU를 선점합니다.
• SJF(Shorted-Job First) 스케줄링은 최단 작업이 우선 CPU를 선점합니다.
• 우선 순위 기반(Priority based) 스케줄링은 작업마다 임의의 우선 순위를 할당하고 우선 순위가 높은 작업이 CPU를 선점합니다. 
• HRRN(Highest Response Ratio Next) 스케줄링은 시스템 응답률이 높은 작업이 CPU를 선점합니다.

HRRN 우선 순위 = 시스템 응답률 = (CPU burst time + Waiting time) / CPU burst time

• 비선점 스케줄링은 이미 CPU를 할당받은 프로세스의 작업이 종료되기를 기다려야 합니다.
• 따라서 더 높은 우선 순위의 작업이 뒤늦게 들어온 경우 처리되지 못하고 대기해야 하는 문제가 발생 할 수 있습니다.
• 반면 프로세스의 CPU 선점과 종료 시점을 비교적 정확하게 파악 할 수 있다는 장점이 있습니다.