프로세스 스케줄링
CPU 스케줄링이라고도 합니다.
멀티프로그래밍(Multiprogramming)의 목적은 CPU를 최대한 사용하기 위해 여러 개의 프로세스를 항상 실행시키는 것입니다.
시간 공유(Time Sharing)의 목적은 프로세스 간에 CPU를 빠르게 전환함으로써 사용자가 각 프로그램이 실행되는 동안 서로 상호작용할 수 있도록 만드는 것입니다.
이러한 목적들을 당성하기 위해 프로세스 스케줄러는 CPU에서 프로그램 실행을 위해 사용 가능한 프로세스를 선택합니다. 이렇게 어떤 프로세스를 CPU에 할당할 것인가를 결정하는 일을 프로세스 스케줄링(Process Scheduling)이라고 합니다.
CPU가 하나인 시스템은 하나의 running 프로세스를 가질 수 있고, 여러 프로세스가 존재하는 경우 나머지 CPU가 free 상태가 될 때까지 대기해야 하기 때문에 적절한 스케줄링이 필요합니다.
이 스케줄링을 수행하는 다양한 스케줄링 알고리즘들이 존재합니다.
Preemptive vs Non-preemptive
Preemptive
Preemptive(선점)는 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있습니다.
Non-preemtive
Non-preemtive(비선점)는 한 프로세스가 CPU를 점유했다면 I/O 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것입니다.
Scheduling Criteria
스케줄링 알고리즘의 성능 평가하는 기준입니다.
- CPU 이용률 (CPU Utilization)
전체 시간 중 CPU가 쉬지 않고 일한 시간 - 처리량 (Throughput)
단위 시간당 수행 완료한 프로세스 수 - 소요 시간 (Turnaround Time)
프로세스가 Ready Queue에서 대기한 시간부터 작업을 완료하는 데 걸린 시간 - 대기 시간 (Waiting Time)
프로세스가 Ready Queue에서 대기한 시간 - 응답 시간 (Response Time)
프로세스가 처음으로 CPU를 할당받기까지 걸린 시간
Scheduling Algorithm
FCFS Scheduling
First Come First Served
CPU에 먼저 도착하는 순서대로 프로세스를 할당해주는 방식입니다.
- 프로세스가 종료될 때까지 CPU를 빼앗지 않아 Non-preemptive 방식
- FIFO 방식의 큐(Queue)와 작동 방식이 동일
하나의 긴 프로세스로 인해 나머지 프로세스가 오래 기다리게 되어 CPU 효율성이 낮아지는 Convoy Effect가 발생할 수 있습니다.
SJF Scheduling
Shortest Job First
프로세스의 수행 시간이 짧은 순서대로 CPU에 할당하는 방식입니다. FCFS의 Convoy Effect를 해결할 수 있습니다.
항상 최소의 평균 대기 시간을 보장하지만 수행시간이 긴 프로세스는 계속 뒤로 밀려나는 기아(Starvation) 현상이 발생할 수 있습니다.
현실적인 컴퓨터 환경에서는 프로세스의 CPU 점유 시간을 알 수 없습니다. 프로세스 실행 중에는 수많은 변수가 존재하기 때문에 실제로 수행하여 측정해야 CPU 점유 시간을 알 수 있습니다. 예측으로 사용 가능하지만 오버헤드가 매우 큰 작업으로 잘 사용되지 않습니다.
-
Non-preemptive SJF
프로세스가 도착하는 시간에 따라 평균 대기 시간이 달라질 수 있습니다. CPU 점유 시간이 긴 프로세스를 실행하는 중에 CPU 점유 시간이 짧은 프로세스가 도착하면 결국 대기해야합니다. -
Preemptive SJF
새로운 프로세스가 도착했을 때, 현재 남아있는 작업 중 가장 빨리 끝나는 작업부터 CPU를 할당해주면 평균 대기 시간을 더 줄일 수 있습니다. 하지만 결국 기아 현상은 막을 수 없습니다.
Priority Scheduling
프로세스에게 우선순위를 부여해 우선순위가 제일 높은 프로세스에게 CPU를 할당하는 방식입니다.
SJF도 우선순위 스케줄링의 일종입니다.
하지만 결국 우선순위가 늦은 프로세스가 계속해서 수행되지 않는 기아 현상이 발생할 수 있습니다. 이를 시간이 자날수록 오래 대기한 프로세스의 우선순위를 높이는 에이징(Aging) 기법을 통해 해결합니다.
다른 스케줄링 알고리즘과 결합하여 선점, 비선점 모두 가능합니다.
RR Scheduling
Round Robin
각 프로세스가 동일한 크기의 할당 시간(Time Quantum)을 갖습니다. 할당 시간이 지나면 다음 작업으로 넘어가고, 진행하던 프로세스가 작업이 남아 있다면 다시 대기 상태로 돌아갑니다.
n개의 프로세스가 Ready Queue에 존재하고 할당 시간이 q라면 모든 프로세스는 (n-1)q 이상 기다리지 않게 됩니다. 따라서 기아 현상은 발생하지 않고 응답 시간이 빠르다는 장점이 있습니다.
하지만 프로세스가 끝나지 않고 할당이 바뀌기 때문에 평균 소요 시간이 SJF에 비해 깁니다.
할당 시간 q가 클수록 FCFS와 유사해지고, q가 작을수록 Context Switching의 오버헤드가 커지기 때문에 적절한 q를 배정하는 것이 중요합니다.
Multilevel Queue
프로세스는 기준에 따라 여러 그룹으로 나눌 수 있습니다.
- System Processes: 커널 수준의 프로세스
- Interactive Processes: 사용자 수준의 대화형 프로세스
- Interactive Editing Processes
- Batch Processes: 대화형 프로세스의 반대, 일정량을 한 번에 처리하는 프로세스 (ex. 컴파일러)
- Student Processes
각 그룹에 따라 Queue를 두어 사용하는 방식이 Multilevel Queue입니다.
Queue마다 다른 규칙을 지정할 수 있는데 우선순위를 지정할 수 있습니다.
우선순위 뿐만 아니라 Queue마다 CPU 시간을 다르게 줄 수도 있고 Queue마다 다른 스케줄링 방식을 사용할 수도 있습니다.
Multilevel Feedback Queue
Multilevel Queue에서 프로세스가 Queue 사이에서 이동할 수 있는 성질이 추가된 것입니다. 우선순위를 부여해서 에이징(Aging) 기법을 통해 구현될 수 있습니다.
우선순위는 프로세스들의 과거 CPU 점유 시간을 이용하여 미래의 행동을 예상하여 부여합니다. 이를 이용해서 기아 현상을 해결할 수 있습니다.
