프로세스 스케줄링이란? 비선점 스케줄링, 선점 스케줄링

프로세스 스케줄링의 정의

프로세스 스케줄링 - 비선점 스케줄링, 선점 스케줄링

스케줄링은 운영 체제의 동작 기법으로 다중 프로그래밍을 가능하게 한다. 운영 체제는 CPU 등의 자원을 프로세스들에 적절히 분배하여 시스템의 성능을 개선할 수 있다. 프로세스 스케줄링은 다중 프로그래밍 환경에서 여러 프로세스가 CPU를 효율적으로 사용할 수 있도록 순서를 결정하는 작업이다. 이는 프로세스 간에 공정한 자원 분배와 시스템의 성능 향상을 목표로 한다. 프로세스가 CPU를 항상 점유하고 있지 않다. 입력을 기다리거나 데이터를 출력하는 동안 CPU를 사용하지 않는다. 일반적으로 프로세스는 CPU 처리, I/O 처리 주기를 반복한다. 따라서 프로세스를 여러 개 처리할 때, 한 프로세스의 CPU, I/O 처리 과정 동안 계속 대기하고 다음 프로세스를 실행하는 것보다 사용하지 않는 리소스는 다른 프로세스가 사용하는 게 생산성을 향상할 수 있다.

비선점 스케줄링

프로세스가 처리기를 할당받고 자발적으로 CPU를 반납할 때까지 계속 실행되는 방식으로, 스케줄러가 종료되기 전까지 어떤 프로세스에 의해서도 처리기를 넘겨주지 않고 프로세스를 강제로 중단시키지 않는다. 선점 스케줄링에 비해 구현이 간단하다. 그래서 프로세스 간의 오버헤드가 적다. 다만 프로세스가 긴 시간 동안 CPU를 점유할 경우 다른 프로세스들이 대기해야 하므로 평균 대기 시간이 증가할 수 있다. 또한 자원을 효율적으로 사용하기 어려울 수 있다. 비선점 스케줄링은 FCFS(First Come First Service 선입선출), SJF(Shortest Jot First 단기업우선), HRN(Highest Response-ratio Next), Deadline(기한부) 스케줄링, Priority(우선순위) 스케줄링이 있다.

1. FCFS(First Come First Service 선입선출)
FIFOCFirst In First Out)로도 명칭 하며, 프로세스들이 준비상태 큐(대기 큐, 작업준비 큐, 준비완료리스트, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당한다. 가장 간단한 방법으로 프로세스 간의 공평성은 유지할 수 있지만, 짧은 작업이나 중요한 작업이 지연되는 단점이 발생한다. 비선점 방식으로 일단 CPU를 차지하면 완료될 때까지 독점하게 되며 대화식 방식으로는 적합하지 않다. 작업 완료 시간을 예측하기 쉽다.

2. SJF(Shortest Jot First 단기업우선)
실행시간이 가장 짧은 것부터 먼저 실행하는 방식으로 준비 상태 큐에서 기다리고 있는 프로세스 중에서 가장 짧은 게 우선된다. 평균 대기시간이 프로세스 스케줄링 중 가장 짧고, 실행 시간이 짧은 프로세스가 많은 작업에 유리하다. 하지만 실행시간이 긴 프로세스는 CPU 할당 순위가 계속 밀리는 무한연기 상태가 발생한다.

3. HRN(Highest Response-ratio Next)
대기시간이 긴 프로세스나 실행시간이 짧은 프로세스에 우선순위 공식을 이용하여 우선순위를 높여 주는 방식이다. 일단 CPU를 차지하면 우선순위 계산에서는 큰 값을 지니는 프로세스가 먼저 실행한다. 프로세스가 끝날 때까지 점유하는 비선점 방식이다. SJF 방식의 단점인 긴 실행시간을 지닌 프로세스의 불리함을 보완하기 위한 방식이다.

4. Deadline(기한부) 스케줄링
프로세스가 주어진 기한 내에 수행하면 그 실행은 유용하게 되나, 각 프로세스는 마감이 있고 기한 내에 수행을 완료하지 못하면 처음부터 다시 실행하거나 제거한다. 작업이 요구하는 리소스를 정확히 파악해야 해서 복잡하다. 따라서 사용자는 자원에 대한 정확한 정보를 사전에 작업이 요구하고 시스템에 제공해야 한다. 프로세스 실행 시 많은 기한부 프로세스가 동시에 제출되면 스케줄링이 복잡해진다. 자원관리 오버헤드가 발생한다.

 

5. Priority(우선순위) 스케줄링
준비상태 큐에서 기다리고 있는 프로세스마다 우선순위를 부여하고, 프로세스의 중요도에 따라 우선순위를 결정하고, 이에 따라 가장 높은 우선순위부터 먼저 CPU를 할당한다. 우선순위는 시스템에 의해 결정하거나 사용자에게 결정되고 우선순위가 동일한 경우 FCFS 방식으로 CPU를 할당한다. 기억장치 요구, 시간제한, 개방된 파일 수 등 리소스 작업 사용량을 고려하거나 사용자에 의해 정해진 작업실행 정책 등을 고려한다. 우선순위가 낮은 프로세스는 무한연기 상태가 되어 기아 상태로 결국 실행되지 못할 수 있다.

 

선점 스케줄링

선점 스케줄링 방식은 어떤 프로세스가 처리기를 점유하고 실행 중, 프로세스가 자발적으로 CPU를 반납하지 않아도 처리기의 사용을 요청받으면 스케줄러가 시간 할당량이 만료되면 강제로 현재 실행 중인 프로세스를 중단하고 다른 프로세스로 전환 방식이다. 프로세스가 강제로 중단되어 다른 프로세스로 전환될 수 있고 짧은 시간 동안 여러 프로세스가 번갈아 가며 CPU를 사용할 수 있다. 응답 시간이 빠르고, 프로세스 간의 경쟁에서 우선순위를 부여할 수 있어 특정 프로세스에 높은 우선순위를 부여할 수 있다. 하지만 문맥 교환 오버헤드가 증가할 수 있고 프로세스 간의 공정한 자원 분배를 위해 우선순위 스케줄링이 필요하다.

 

1. RR(Round Robin 라운드 로빈) 스케줄링
프로세스가 먼저 CPU를 할당받는데, FCFS처럼 준비상태 큐에 먼저 들어온 뒤, 해당 프로세스에 정해진 시간 동안만 할당받는다. 시간 내에 완료되지 못하면 준비상태 큐의 가장 뒤로 옮겨진 후 다음 프로세스에 CPU 할당을 넘기고, 자신은 가서 실행의 기회를 기다린다. 시분할 시스템(Time Sharing System)을 위한 방식으로 할당 시간에 따라 FCFS와 같아지고, 문맥 교환 및 오버헤드 발생이 증가한다. 비선점 방식인 FCFS(PIFO) 방식을 선점 방식으로 바꾼 것이다.

2. SRT(Shortest Remaining Time) 스케줄링
시분할 시스템에 적합한 방식으로 선점 SJF기법이라고도 불리며 비선점 방식의 SJF 기법을 선점 방식으로 변환한 기법이다. 현재 실행 중인 프로세스의 남은 실행시간과 비교하여 새로운 프로세스가 준비상태 큐에 도착하면, 가장 짧은 실행시간의 프로세스를 CPU에 할당하는 방법이다. 오버헤드가 발생하고 실행 중인 준비상태 큐의 각 프로세스의 시간을 관리하며 선점 방식을 지원한다. 대기시간이 SJF 기법보다 길어진다.

3. 선점 우선순위 스케줄링
가장 우선순위가 높은 프로세스 중에서 준비상태 큐의 프로세스에 CPU를 할당하는 방법이다. 선점 방식으로 비선점 우선순위 기법을 변화시킨 것으로, 준비상태 큐에 도착한 프로세스와 새로 제출되어 현재 실행 중이고 CPU를 할당받은 프로세스 중의 우선순위가 높은 프로세스에 CPU를 할당하는 방식이다.

4. 다단계 큐(Multi-Level Queue) 스케줄링
여러 개의 특징적 그룹으로 나누어 작업을 그룹별로 유형별의 큐를 별도로 관리하는 기법이다. 다단계 큐를 가지고 있으며 우선순위 등을 구분하여 관리한다. 큐는 단독적으로 자체 스케줄링 정책을 가지고 스케줄링 된다. 다단계 큐마다 우선순위가 지정되며 프로세스 간의 우선순위보다 높은 우선순위의 큐에 프로세스가 도착하면 낮은 우선순위의 큐에 있는 프로세스는 중단되고 먼저 실행된다. 프로세스가 큐에 들어간 이후에는 다른 준비상태 큐로 이동할 수 없다.

 

비선점 스케줄링과 선점 스케줄링 비교

프로세스 스케줄링 방식은 시스템의 요구 사항과 특성에 따라 선택되며, 각 방식은 장단점을 가지고 있어 적절한 상황에 사용된다. 프로세스 전환 시, 비선점 스케줄링은 프로세스가 자발적으로 CPU를 반납할 때까지 계속 실행되며, 중간에 다른 프로세스로 전환되지 않는다. 선점 스케줄링은 시간 할당량이 만료되면 현재 실행 중인 프로세스가 강제로 중단되고 다른 프로세스로 전환된다. 프로세스의 우선순위에 따라 실행되는 시점을 결정할 때는 비선점 스케줄링은 현재 실행 중인 프로세스가 완료되거나 입출력(IO) 요청 시에만 프로세스 전환이 이루어지므로 우선순위에 따른 강제 중단이 없지만 선점 스케줄링은 우선순위에 따라 프로세스가 중단되고 강제적인 중단이 가능하므로 CPU를 할당받을 수 있다. 비선점 스케줄링은 한 프로세스가 CPU를 오래 점유할 경우 평균 대기 시간이 다른 프로세스들이 대기해야 하므로 증가하여 프로세스 예측이 어렵다. 반면 선점 스케줄링은 시간 할당량이 만료되면 응답 시간을 예측하기 쉽고, 다른 프로세스로 전환되므로 프로세스 간의 공정한 자원 분배가 가능하여 프로세스 예측이 쉽다. 비선점 스케줄링은 프로세스가 자발적으로 CPU를 반납할 때까지 대기하므로 응답 시간을 예측하기 어렵고, 선점 스케줄링은 시간 할당량이 만료되면 다른 프로세스로 전환되므로 응답 시간을 예측하기 쉽다. 비선점 스케줄링은 구현이 간단하고 프로세스 간 문맥 교환 오버헤드가 적지만, 선점 스케줄링은 강제적인 중단이 가능하므로 문맥 교환이 자주 발생하여 오버헤드가 증가할 수 있다.