스케줄링 알고리즘에는 어떤 종류가 있나요?

김상욱·2024년 11월 30일

스케줄링 알고리즘에는 어떤 종류가 있나요?

스케줄링 알고리즘은 CPU 또는 프로세스를 관리하는 중요한 역할을 하며, 크게 CPU 스케줄링 알고리즘과 디스크 스케줄링 알고리즘으로 나눌 수 있다.

비선점형 스케줄링(Non-preemptive Scheduling)
실행 중인 프로세스를 강제로 중단하지 않고, 프로세스가 자발적으로 종료되거나 자원을 반환할 때까지 기다립니다.

FCFS(First-Come, First-Served)
프로세스가 도착한 순서대로 실행되기 때문에 구현이 간단하고 공정하지만 평균 대기 시간이 길어질 수 있고 Convoy Effect(콘보이 현상)이 발생할 수 있다.
Convoy Effect는 긴 작업 하나가 뒤따르는 짧은 작업들의 실행을 지연시키는 현상.

SJF(Shortest Job First)
실행 시간이 가장 짧은 프로세스를 먼저 실행한다. 평균 대기 시간이 가장 짧아지는 효율적인 알고리즘이다. 하지만 실행 시간의 예측이 어려우며 긴 작업이 계속 지연될 수 있다.(Starvation)
Starvation은 앞에 작업이 계속 진행되기 때문에 특정 작업이 계속 미뤄져서 실행이 엄청나게 밀리는 현상

Priority Scheduling : 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행. 이 또한 중요한 작업을 빨리 처리할 수 있지만 낮은 우선순위의 프로세스가 무한정 대기하는 기아(Starvation)문제가 발생할 수 있음.

선점형 스케줄링(Preemptive Scheduling)
실행 중인 프로세스를 강제로 중단하고, 더 중요한 작업을 우선적으로 처리.

Round Robin(RR)
각 프로세스에 Time Quantum(시간 할당량)을 정해주고, 할당된 시간만큼만 실행함. 그 후 대기열의 다음 프로세스로 넘어감. 공정한 알고리즘이며, 응답 시간이 짧아짐. 단, Time Quantum 설정이 너무 작으면 Context Switching이 빈번해져 오버헤드가 커지고, 너무 크면 FCFS처럼 동작.

SRTF(Shortest Remaining Time First)
남은 실행 시간이 가장 짧은 프로세스를 우선적으로 실행함. SJF(Shortest Job First)의 선점형 버전. 평균 대기 시간이 최소화되지만 실행 시간 예측이 어렵고, Starvation 문제 발생 가능성 있음.

Priority Scheduling(선점형)
실행 중인 프로세스보다 높은 우선순위를 가진 새로운 프로세스가 도착하면, 현재 작업을 중단하고 우선순위가 높은 작업을 실행. 우선순위가 높은 작업을 빠르게 처리할 수 있으나 Starvation 문제가 여전히 존재 가능.

다단계 큐 스케줄링(Multilevel Queue Schedulng)
프로세스를 우선순위에 따라 여러 큐로 분리하고, 각 큐는 서로 다른 스케줄링 알고리즘을 사용. 상위 큐는 시간 할당량에 따른 알고리즘인 Round Robin, 하위 큐는 FCFS(First-Come First-Served)를 사용. 프로레스의 특성에 따라 적절한 처리가 가능. 낮은 우선순위 큐가 자주 무시될 가능성이 있음.
-> 상위 큐가 비어야 하위 큐의 작업이 실행.
상위 큐에는 사용자 응답성이 중요한 대화형 프로세스(interactive Process)가 배치됨. 하위 큐에는 배치 작업(Batch Process) 또는 백그라운드 작업이 배치.(순서보다는 완료가 중요한 작업)
: 배치형 작업 - 사용자와의 직접적인 상호작용 없이 실행되는 작업으로 대규모 데이터 처리나 긴 실행 시간을 필요로 하는 작업.

다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
다단계 큐 스케줄링의 개선된 버전으로, 프로세스의 실행 시간이 길어질수록 하위 우선순위 큐로 이동. Starvation 문제를 완화 가능하지만 알고리즘 설계와 매개변수 조정이 복잡해짐. 상위 큐는 짧은 Time Quantum을 가지며 하위큐로 내려갈수록 긴 Time Quantum 또는 FCFS 방식을 사용.
동작 방식
새로운 프로세스는 항상 최상위 큐에서 시작. 응답 시간이 중요한 대화형 프로세스를 주로 처리 -> 최상위 큐가 비어 있지 않으면, 하위 큐의 프로세스는 실행되지 않음. -> 프로세스가 Time Quantum을 초과하거나 자원을 충분히 사용하면 하위 큐로 이동. 낮은 우선순위 큐로 이동할수록 프로세스는 더 긴 Time Quantum을 부여받거나 FCFS로 동작.

스케줄링 알고리즘 실습 가능한 종류

1. First-Come, First-Served (FCFS)

특징: 작업이 도착한 순서대로 실행.
실습 아이디어:
- 작업(요청)을 Queue에 저장하고, FIFO(First In, First Out) 방식으로 처리.
- Java 실습: java.util.Queue를 사용하여 작업 처리 구현.
- Spring 실습: HTTP 요청을 Controller에서 Queue에 넣고, Worker Thread로 처리.

import java.util.LinkedList;
import java.util.Queue;

public class FCFSScheduler {
    public static void main(String[] args) {
        Queue<String> taskQueue = new LinkedList<>();
        taskQueue.add("Task1");
        taskQueue.add("Task2");
        taskQueue.add("Task3");

        while (!taskQueue.isEmpty()) {
            System.out.println("Processing: " + taskQueue.poll());
        }
    }
}

2. Round Robin

특징: 각 작업에 일정한 Time Quantum을 할당.
실습 아이디어:
- Task를 List로 관리하고, 각 작업에 Time Quantum을 설정.
- Java에서는 Thread.sleep()을 사용하여 Time Quantum을 구현.
- Spring에서는 @Scheduled를 활용한 주기적 작업 처리 시뮬레이션.

import java.util.ArrayList;
import java.util.List;

public class RoundRobinScheduler {
    public static void main(String[] args) throws InterruptedException {
        List<String> tasks = new ArrayList<>(List.of("Task1", "Task2", "Task3"));
        int timeQuantum = 2; // seconds

        while (!tasks.isEmpty()) {
            for (int i = 0; i < tasks.size(); i++) {
                System.out.println("Processing: " + tasks.get(i));
                Thread.sleep(timeQuantum * 1000); // Simulate time quantum
                tasks.remove(i);
                i--; // Adjust index after removal
            }
        }
    }
}

3. Priority Scheduling

특징: 작업 우선순위에 따라 실행 순서 결정.
실습 아이디어:
- PriorityQueue를 사용하여 우선순위 기반의 작업 처리 구현.
- 작업 클래스에 priority 필드를 추가하여 정렬 기준 설정.

import java.util.PriorityQueue;

class Task implements Comparable<Task> {
    String name;
    int priority;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compareTo(Task other) {
        return Integer.compare(other.priority, this.priority); // Higher priority first
    }

    @Override
    public String toString() {
        return name + " (Priority: " + priority + ")";
    }
}

public class PriorityScheduler {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();
        taskQueue.add(new Task("Task1", 3));
        taskQueue.add(new Task("Task2", 1));
        taskQueue.add(new Task("Task3", 2));

        while (!taskQueue.isEmpty()) {
            System.out.println("Processing: " + taskQueue.poll());
        }
    }
}

4. Multilevel Feedback Queue

특징: 프로세스가 다른 큐로 이동하면서 처리.
실습 아이디어:
- 여러 Queue를 만들어 작업을 큐 간에 이동.
- 시간 초과 시 낮은 우선순위 큐로 작업을 옮기는 로직 구현.

Spring 실습 가능 요소

Spring Task Scheduling:
- @Scheduled를 활용하여 주기적 작업 실행(예: Round Robin 시뮬레이션).
- 다양한 작업의 우선순위를 고려하여 작업 관리.
비동기 처리:
- Spring의 @Async를 활용하여 작업을 비동기로 실행.
- ExecutorService를 사용해 스레드풀 기반의 스케줄링 구현.
Job Queue 시스템:
- Redis와 같은 메시지 큐를 사용하여 실제 대규모 작업 스케줄링을 시뮬레이션.
- RabbitMQ나 Kafka와 연동하여 스케줄링 알고리즘과 메시지 전달 구현.