CPU 스케줄링
CPU 스케줄링은 운영체제가 CPU를 효율적으로 분배하는 방법입니다. 여러 프로세스나 스레드가 동시에 실행되려 할 때, CPU는 어떤 프로세스나 스레드에 CPU를 할당할지를 결정해야 합니다. 그리고 그 방법을 CPU 스케줄링이라고 합니다.
스케줄러의 종류
장기 스케줄러 (Long-Term Scheduler )
Long-Term Scheduler 는 새로운 프로세스가 생성되거나, 준비 상태로 전환될 때, 프로세스를 메모리에 올려 CPU가 프로세스를 처리할 수 있도록 합니다. 메모리에 적재되기 전에 대기 상태에 있는 프로세스 중에서 시스템의 메모리 사용을 효율적으로 하기 위해 프로세스의 수를 조절하여 어떤 것을 메모리에 적재할 지 결정합니다.
중기 스케줄러 (Medium-Term Scheduler) (수정 해야함)
중기 스케줄러는 메모리에 너무 많은 프로세스가 존재해 메모리가 부족해지면 메모리에 있는 프로세스를 디스크와 같은 보조 기억 장치로 내보내고, 필요 시 다시 불러오는 작업을 수행합니다.
단기 스케줄러 (Short-Term Scheduler)
현재 실행중인 프로세스와 대기 상태인 프로세스들 사이에서 CPU를 할당하는 역할을 합니다. 프로세스의 상태를 Running , Ready , Waiting 등으로 전환하며 CPU를 가장 적절한 프로세스에게 할당합니다.
단기 스케줄러는 매우 자주 실행되며 프로세스가 CPU를 사용할 때마다 결정됩니다.
선점 여부에 따른 스케줄링
선점형 스케줄링 (Preemptive Scheduling)
선점형 스케줄링 (Preemptive Scheduling) 이란 운영체제에서 프로세스 스케줄링을 수항핼 때, 현재 처리 중인 프로세스를 중단하고 다른 프로세스를 처리할 수 있도록 하는 스케줄링 방식입니다. 이는 프로세스 간의 공정성을 보장하고, 시스템 자원을 효율적으로 활용하는 데에 중요한 역할을 합니다.
비선점형 스케줄링 (Non-preemptive Schedulimg)
비선점 스케줄링 (Non-preemptive Schedulimg) 은 한번 CPU를 할당받은 프로세스는 그 자체로 종료되거나, I/O 작업이 있을 때까지 CPU는 해당 프로세스의 작업만 처리합니다. 이 과정에서 다른 프로세스는 해당 프로세스의 CPU를 강제로 빼앗을 수 없습니다.
일반적으로 선점형 스케줄링 보다 호출빈도가 낮고, Context Switching Overhead가 적다. 이는 어떠한 프로세스가 작업을 마치고 자발적으로 대기 상태로 들어가거나, 종료되는 경우 다른 프로세스가 실행된다.
선입선출 스케줄링 (FCFS)
선입선출 스케줄링 (First-Come First-Served) 이란 프로세스들이 도착한 순서대로 CPU를 할당받아 실행됩니다. 즉 먼저 도착한 프로세스가 먼저 실행되며, 실행이 끝날 때까지 다른 프로세스는 대기 상태로 남게 됩니다. 이는 비선점형 스케줄링의 특징이며, 선입선출 스케줄링 역시 비선점형 스케줄링의 방식 중 하나입니다.
간단하고 직관적이며, 프로세스들이 도착한 순서대로 CPU를 할당받아 작업을 처리하기 때문에 모든 프로세스들이 공정하게 CPU를 할당받게 됩니다.
하지만 긴 작업이 처리 해야하는 프로세스가 가장 먼저 도착하게 되면 그 뒤로 도착한 프로세스들이 긴 시간 동안 대기해야 합니다. (Convoy Effect) 이 때문에 뒤에 밀려있는 프로세스들은 응답 시간이 지연되고, I/O 작업이 많은 프로세스가 CPU를 점유할 경우
FCFS 방식은 다른 프로세스를 처리하기 위해 CPU가 디른 프로세스로 할당되지 않기 때문에 CPU 자원을 비효율적으로 사용하게 됩니다.
최단 작업 우선 스케줄링 (SJF)
최단 작업 우선 스케줄링 (Shortest Job First, SJF) 은 전체 실행 시간 이 가장 짧은 프로세스를 우선적으로 실행하는 방식입니다. 이 알고리즘은 작업의 실행 시간을 기준으로 스케줄링을 결정하며 평균 대기 시간을 완화할 수 있다는 장점이 있습니다.
하지만 아래 그림과 같은 현상이 발생할 수 있습니다.
SJF 스케줄링 방식은 비선점형 스케줄링 방식이기 때문에 긴 작업 시간을 가지고 있는 A 프로세스 가 먼저 도착하고, CPU를 할당 받아, A 프로세스의 작업을 처리하던 도중 B 프로세스 , C 프로세스 가 Ready Queue에 도착하게 되면, 대기 상태에 이르게 됩니다. 그리고 B 프로세스와 C 프로세스 는 긴 작업 시간을 가지는 A 프로세스 가 끝나야만 CPU를 할당받아 작업을 처리할 수 있습니다.
이렇게 발생하는 Convoy Effect는 프로세스 도착시간에 따라 영향을 많이 받으며 응답 시간이 긴 시간의 작업 시간을 갖는 프로세스에 따라 길어질 수 있습니다.
그리고 이를 해결하기 위한 SRTF(Shortest Remaining Time First) 스케줄링 방식이 고안되었습니다.
SJF 스케줄링 방식은 평균 대기 시간을 완화하는데 효과적인 알고리즘이긴 하나, 프로세스의 실행 시간을 정확히 예측하여야 하고, 해당 정보가 불충분하거나 정확하지 않으면 효율적인 구현이 어렵습니다. 또한 긴 작업 시간을 가진 작업이 짧은 작업 시간을 가진 프로세스에 밀려 긴 시간 동안 기아 상태 (Starvation)에 이르게 되는 문제가 생길 수 있습니다.
최소 잔류시간 우선 스케줄링 (SRTF)
최소 잔류시간 우선 스케줄링(SRTF, Shortest Remaining Time First) 은 CPU 스케줄링 알고리즘 중 하나로 프로세스가 도착할 때 마다 현재 실행중인 프로세스와 도착한 프로세스의 잔여 실행 시간을 비교하여, 잔여 실행 시간이 더 짧은 프로세스가 우선적으로 CPU를 사용하도록 하는 방식이다.
해당 스케줄링 방식은 선점형 스케줄링 방식 중 하나이며, SJF(Shortest Job First) 의 선점형 버전이다.
SJF 방식에 비해 SRTF 방식은 선점이 가능하다는 특징이 있다. 하지만 작업 시간이 짧은 프로세스에 대한 작업 처리 요청이 빈번히 들어오는 경우에는 동일하게 Starvation 문제가 발생할 수 있습니다.
최단 작업 스케줄링(SJF)과 최소 잔류시간 우선 스케줄링 (SRTF)의 차이점
SJF와 SRTF의 가장 큰 차이점은 선점형과 비선점형 그리고 전체 실행 시간과 남은 실행 시간의 차이이다. 먼저 SJF는 비선점형 방식으로써, CPU가 중간에 해제되어 다른 프로세스를 처리할 수 없고, 프로세스의 남은 작업 시간이 아닌, 전체 실행 시간을 기준으로 프로세스를 스케줄링 한다. 반면 SRTF 방식은 선점형으로써, CPU가 동적으로 해제되어 다른 프로세스를 처리할 수 있고, 전체 실행 시간 기준이 아닌 남은 작업 시간을 기준으로 스케줄링 한다.
상대적으로 SRTF 방식이 선점형의 특징에 따라 짧은 응답시간을 갖고, SJF는 긴 작업을 처리하고 있는 경우 다른 프로세스는 처리할 수 없기 때문에 응답시간이 늦어질 수 있다.
우선순위 스케줄링
우선순위 스케줄링(Priority Scheduling) 은 프로세스 스케줄링 알고리즘 중 하나로, 각 프로세스에 우선순위를 부여하고, Reday Queue에 프로세스가 도착하면 이 우선순위를 기반으로 프로세스의 처리 순서를 결정하는 방식이다. CPU는 가장 높은 우선순위를 가진 프로세스에게 먼저 할당된다.
우선순위는 시스템에서 정적으로 결정될 수도 있고, 동적으로 변화할 수도 있습니다.
Round Robin 스케줄링
Round Robin(RR) 스케줄링은 선입선출(First-Come, First-Served, FCFS) 방식과 유사하지만 시간 할당량(TimeSlice) 이라는 개념을 추가한 방식입니다.
RR 스케줄링 방식은 각 프로세스에 할당될 시간 할당량이 설정됩니다. 이 시간 동안 프로세스에 CPU가 할당되어 작업을 처리합니다.
모든 준비 상태의 프로세스들은 Ready Queue에 들어가게 되고, Ready Queue는 선입선출 방식으로 관리되며, 가장 먼저 들어온 프로세스가 CPU를 먼저 할당받습니다. 그리고 시간 할당을 받은 만큼 작업을 처리하게 되며, 작업이 끝난다면 해당 프로세스는 큐에서 제거되어, 다음 프로세스가 CPU를 할당받습니다.
만약 시간 할당량 만큼 작업을 하고도 프로세스가 종료되지 않았다면, CPU는 해당 프로세스로부터 회수되고, 그 프로세스는 큐의 맨 끝으로 이동합니다. 그리고나서 다음 프로세스가 CPU를 할당받습니다. RR 스케줄링 방식은 이 과정을 반복하게 됩니다.
Round Robin 스케줄링은 모든 프로세스가 동일한 시간 할당량을 가지기 때문에 CPU가 공평하게 작업을 처리할 수 있다는 특징이 있습니다. 그렇기 때문에 어느 한 프로세스가 오랜 시간 대기 상태에 머물러 있는 기아 상태에 다른 스케줄링 방식보다 덜 노출될 수 있다는 장점이 있습니다. 하지만 RR 스케줄링 방식은 다른 스케줄링 방식보다 Context Switching 이 자주 발생할 수 있기에 오버 헤드가 더 발생 하고 작업 완료에 대한 시간은 다른 방식보다 더 늦어질 수 있다는 단점이 있습니다.
FCFS(First-Come First-Served) 와 RR(Round-Robin) 의 차이점
FCFS는 어떤 프로세스가 큐에 들어오면 CPU는 해당 프로세스의 모든 작업 처리가 끝날 때까지 해당 프로세스에 할당됩니다. 이에 비해 RR 방식은 FCFS 방식과 마찬가지로 큐에 들어 온 순서대로 CPU를 할당받아 작업을 처리하지만, 각 프로세스마다 시간 할당량을 분배하여 그만큼 작업을 하고, 작업하던 프로세스를 큐의 맨 뒤로 넘기고 (프로세스의 작업이 남아있다면) 다음 프로세스에 CPU를 할당하여 작업을 이어 나갑니다.
이러한 특징에서 알 수 있듯이 FCFS는 비선점형 스케줄링 방식이고, RR 방식은 선점형 스케줄링 방식입니다.
멀티 레벨 큐 스케줄링
멀티 레벨 큐 스케줄링 방식은 프로세스를 우선순위의 정도에 따라 여러 개의 큐로 나누어 관리하는 스케줄링 방식입니다. 쉽게 예시를 들자면 놀이공원이나 워터파크에 입장할 때, 입장객들이 많으면 일반적으로 줄을 서게 된다. 하지만 해당 놀러간 곳에 회원권이나, 특정 이벤트 당첨자의 경우 줄을 기다리지 않고, 바로 입장할 수 있는 시스템이 존재하는 곳도 있다.
이처럼 프로세스도 우선순위가 높은 작업들은 먼저 처리하는 줄(Queue) 을 따로 만들고, 그 뒤로 우선순위에 따라 여러 개의 큐를 만들어 프로세스들을 각각의 큐에 넣어 프로세스를 스케줄링 하는 방식이다. 그리고 그 각각의 큐는 서로 다른 Ready Queue이기 때문에 다른 스케줄링 방식을 사용할 수 있습니다.
멀티 레벨 큐 스케줄링은 각 큐에 대한 스케줄링 정책을 독립적으로 사용할 수 있어 시스템을 설계하고 이해하기가 용이하다는 장점이 있다. 또한 다양한 프로세스 특성에 맞게 큐를 나누고, 각 큐에 맞는 스케줄링 정책을 사용함으로써 유연하게 스케줄링을 할 수 있다.
하지만 시스템의 상태에 따라 기아 상태가 발생할 수 있고, 큐 간 불균형 문제가 발생할 수도 있습니다.
멀티 레벨 피드백 큐 스케줄링 (MLFQ)
멀티 레벨 피드백 큐(MLFQ, Multi-Level Feedback Queue) 는 멀티 레벨 큐 스케줄링 방식과 유사하지만 차이점이 있습니다.
멀티 레벨 피드백 큐는 작업마다 고정된 우선순위를 부여하는 것이 아닌, 각 작업의 특성에 따라 작업 패턴을 보고 우선순위를 부여합니다.
프로세스는 처음 높은 우선순위 큐에 할당되지만, CPU를 긴 시간 동안 사용하게 되면(CPU Bound) 낮은 우선순위 큐로 이동합니다. 반대로 프로세스가 짧은 시간 동안 CPU를 사용하고 빠르게 대기 상태에 이르는 경우에는 우선순위가 상승할 수 있습니다. 이 경우에는 I/O 작업을 빈번하게 수행하는 프로세스일 경우가 많습니다. (I/O Bound)
예를 들어 텍스트 에디터나 웹 브라우저는 실시간 응답이 중요한 프로세스이기 때문에 사용자의 입력(I/O)에 대해 민감하게 반응해야 합니다. 이러한 프로세스들은 짧은 TimeSlice를 필요로 하며, 이를 통해 빠르게 반응하여 사용자에게 피드백을 제공할 수 있기 때문에 보통 높은 우선순위 큐에 위치합니다.
이러한 스케줄링 방식은 프로세스의 우선순위를 유동적으로 변경할 수 있기 때문에, CPU 자원의 효율적 배분이 가능합니다.
우선순위가 높은 큐는 짧은 TimeSlice를 할당받고, 우선순위가 낮은 큐는 긴 시간의 TimeSlice를 할당 받습니다. 반대로 낮은 우선순위의 큐의 프로세스가 승급되기도 합니다. 이러한 스케줄링 방식은 프로세스의 우선순위를 유동적으로 변경할 수 있어, CPU 자원의 효율적 배분이 가능합니다.
MLFQ는 각 작업마다 고정된 우선순위를 부여하는 것이 아닌 각 작업의 특성에 따라 동적으로 우선순위를 부여한다. 예를 들어 어떤 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 해당 작업의 우선순위를 낮추고, 어떤 작업이 반복적으로 CPU를 반납하게 되면 해당 작업은 우선순위를 높게 유지한다.
기아 상태
CPU 스케줄링에서 기아 상태 (Starvation)는 특정 프로세스가 오랫동안 CPU를 할당받지 못해 실행되지 못하는 상태를 의미합니다. 해당 문제는 스케줄링 알고리즘에 의해 발생되고, 우선순위 기반 스케줄링에서 자주 나타날 수 있습니다.
원인
- 우선순위 스케줄링 (Priority Scheduling) :
- 우선순위가 높은 프로세스가 먼저 CPU를 할당받는 방식.
우선순위가 높은 프로세스가 CPU를 계속 할당받게 되면,우선순위가 낮은 프로세스는 CPU 할당을 받지 못해 무기한 대기 상태에 놓일 수 있음.
- 우선순위가 높은 프로세스가 먼저 CPU를 할당받는 방식.
- 비선점 스케줄링 (Non-preemptive Scheduling) :
- 한 번 CPU를 할당받은 프로세스는 자체적으로 종료되거나, 입출력 작업을 시작하기 전까지 CPU를 계속 사용. 이 경우, 짧은 작업이 계속해서 들어오면 긴 작업들이 CPU를 할당받을 기회를 얻지 못해 기아 상태에 빠질 수 있음.
- 자원 독점 (Resource Contention) :
- 특정 자원을 독점적으로 사용하는 프로세스가 있을 경우, 다른 프로세스들이 해당 자원을 기다리느라 CPU를 할당받지 못하게 되어 기아 상태에 빠질 수 있음.
기아 상태 (Starvation) 에 놓이게 되면 시스템 자원을 비효율적으로 사용하게 되고, 시스템 성능을 저하 시킬 수 있음. 또한 기아 상태에 놓인 프로세스는 정상적인 작업 처리가 어렵다.
해결 방법
에이징 (Aging)
프로세스가 시스템에서 대기하는 시간이 길어질수록 해당 프로세스의 우선순위를 점진적으로 눂여주는 기법입니다. 이는 기아 상태를 효과적으로 예방할 수 있으며, 우선순위 스케줄링의 공정성을 높여줍니다.
타임 슬라이스 조정
낮은 우선순위 프로세스에게 더 긴 시간의 타임 슬라이스를 할당하거나, 높은 우선순위 프로세스에게 더 짧은 타임 슬라이스를 할당하는 방법입니다. 우선순위가 낮은 프로세스라도 할당된 시간 동안 충분히 자원을 사용할 수 있도록 합니다.
Time Slice 란?
Time Slice는 CPU 스케줄링에서 프로세스가 CPU를 할당받아 실행되는 동안 사용할 수 있는 최대 시간을 의미합니다.
