스케줄 알고리즘은 다양한 분야에서 활용됩니다. 운영 체제(OS), 데이터베이스, 네트워크 등에서는 일련의 작업들을 어떤 순서로 처리할 것인지를 결정하는 데 활용됩니다. 이를 통해 작업 처리 시간을 최소화하거나 시스템 자원을 최대한 활용할 수 있습니다.
스케줄 알고리즘에는 다양한 종류가 있지만, 가장 기본적인 형태는 FCFS(First-Come-First-Serve) 알고리즘입니다.
이 알고리즘은 작업이 도착한 순서대로 처리하는 방식으로, 작업의 처리 시간이 길어질수록 다음 작업의 대기 시간이 증가합니다.
그 외에도 SJF(Shortest-Job-First), RR(Round Robin), Priority Scheduling, Multilevel Queue Scheduling 등의 알고리즘이 있습니다. 이 중 몇 가지 대표적인 알고리즘들을 예제와 함께 살펴보겠습니다.
1. FCFS(First-Come-First-Serve) 알고리즘
FCFS 알고리즘은 작업이 도착한 순서대로 처리하는 방식입니다. 따라서 각 작업의 처리 순서는 도착한 순서와 같습니다.
다음은 FCFS 알고리즘을 이용하여 3개의 작업을 처리하는 코드 예제입니다.
예를 들어, 3개의 작업 A, B, C가 도착한 순서가 A -> B -> C라면, FCFS 알고리즘은 A 작업부터 처리하고, A 작업이 끝나면 B 작업을 처리하고, B 작업이 끝나면 C 작업을 처리하는 방식입니다.
위 코드에서 arrival_time은 각 작업의 도착 시간을, burst_time은 각 작업의 처리 시간을 나타냅니다. start_time, end_time, wait_time은 각각 작업의 시작 시간, 종료 시간, 대기 시간을 나타내는 리스트입니다.
더 효율적인 방법으로 작업을 처리하기 위해서는 SJF(Shortest Job First) 알고리즘을 사용할 수 있습니다. 이 알고리즘은 실행 시간이 가장 짧은 작업부터 먼저 처리하는 방법입니다. 이 방법을 사용하면 평균 대기 시간과 평균 반환 시간이 줄어들어 전반적인 성능이 향상됩니다.
하지만 이 방법에도 문제가 있습니다. 만약 작업의 실행 시간이 긴 작업이 먼저 도착하면, 다른 작업들은 대기시간이 길어지게 됩니다. 이를 방지하기 위해선 우선순위 기반의 알고리즘을 사용할 수 있습니다.
우선순위 기반의 알고리즘은 각 작업마다 우선순위를 지정해 놓고, 우선순위가 높은 작업부터 처리하는 방식입니다. 이를 통해 더 나은 성능을 기대할 수 있습니다. 하지만 이 알고리즘에서도 우선순위가 높은 작업이 계속해서 도착하는 경우, 다른 작업들은 계속해서 대기해야 하므로 문제가 발생할 수 있습니다.
2. SJF(Shortest-Job-First) 알고리즘
SJF 알고리즘(Shortest-Job-First algorithm)은 CPU 스케줄링 알고리즘 중 하나로, 작업이 도착한 시간과 실행시간을 고려하여 CPU 자원을 할당하는 방식입니다.
SJF 알고리즘에서는 실행 시간이 짧은 작업을 우선적으로 처리하여 평균 대기 시간과 평균 반환 시간을 최소화하려는 목적이 있습니다
SJF 알고리즘을 구현하는 방법은 다음과 같습니다.
1)작업들을 도착한 시간 순서대로 정렬합니다.
2)실행 시간이 가장 짧은 작업부터 처리합니다. 만약 두 개 이상의 작업이 실행 시간이 동일하다면, 도착한 시간이 빠른 작업을 먼저 처리합니다
SJF 알고리즘을 코드로 구현해 보겠습니다. 여기서는 작업을 클래스로 정의하고, 리스트로 작업들을 관리하도록 하겠습니다
위 코드에서 Job 클래스는 작업 이름, 도착 시간, 실행 시간을 저장합니다.
sjf 함수는 Job 객체 리스트를 입력으로 받아 평균 대기 시간과 평균 반환 시간을 반환합니다.
함수 내에서는 우선 작업 리스트를 도착 시간순으로 정렬하고, 실행 시간이 가장 짧은 작업을 선택하여 수행합니다.
모든 작업이 수행될 때까지 이 과정을 반복합니다.
이를 통해 SJF 알고리즘을 구현할 수 있습니다. 다만, SJF 알고리즘의 경우 실행 시간을 예측하는 것이 어려울 수 있기 때문에 현실적으로는 사용이 제한될 수 있습니다.