C 언어로 배우는 리얼타임 시스템 스케줄링: RM과 EDF

리얼타임 시스템은 정해진 시간 내에 작업을 완료하는 것이 중요한 시스템입니다. 이러한 시스템에서 스케줄링은 작업의 실행 순서를 결정하여 시스템의 안정성과 효율성을 보장하는 핵심 요소입니다. 본 기사에서는 리얼타임 시스템의 주요 스케줄링 알고리즘인 RM(Rate-Monotonic)과 EDF(Earliest Deadline First)를 C 언어로 구현하며 학습하는 방법을 소개합니다. 이를 통해 알고리즘의 원리와 실제 적용 방법을 이해하고, 리얼타임 시스템 설계에 필요한 기초 지식을 습득할 수 있습니다.

리얼타임 시스템과 스케줄링 기본 개념

리얼타임 시스템은 작업이 특정 시간 안에 완료되어야 하는 특수한 요구를 가진 시스템입니다. 이러한 시스템은 주로 항공, 의료 기기, 제조 공정 제어 등 시간에 민감한 분야에서 사용됩니다.

리얼타임 시스템의 정의

리얼타임 시스템은 작업의 정확성과 더불어 시간적 제약 조건도 충족해야 하는 시스템을 의미합니다. 작업이 지정된 기한을 초과하면 시스템 실패로 간주될 수 있습니다.

스케줄링의 원리

스케줄링은 시스템 내의 작업을 실행하기 위한 순서를 결정하는 과정을 말합니다. 리얼타임 스케줄링은 다음 두 가지를 목표로 합니다.

시간 제약 준수: 각 작업이 기한 내에 완료되도록 보장.
자원 최적화: CPU와 메모리 등 시스템 자원을 최대한 효율적으로 활용.

스케줄링 알고리즘의 유형

고정 우선순위 스케줄링: 작업의 우선순위가 미리 정해진 방식 (예: RM).
동적 우선순위 스케줄링: 실행 중에 우선순위가 변경되는 방식 (예: EDF).

스케줄링은 리얼타임 시스템의 성공적인 설계와 운영의 핵심이며, 시스템의 안정성과 신뢰성을 크게 좌우합니다.

RM 스케줄링 알고리즘의 원리

RM(Rate-Monotonic) 스케줄링은 고정 우선순위 스케줄링 알고리즘으로, 작업의 주기가 짧을수록 높은 우선순위를 부여합니다. 이는 정적 스케줄링 방식으로, 작업의 우선순위는 시스템 설계 시 고정됩니다.

RM 스케줄링의 특징

고정 우선순위: 각 작업의 우선순위는 주기에 따라 미리 정해집니다.
주기 기반: 작업의 주기가 짧을수록 더 높은 우선순위를 가집니다.
단순성: 알고리즘이 간단하여 구현과 분석이 용이합니다.

작동 방식

작업 집합에서 모든 작업의 주기를 계산합니다.
주기가 짧은 작업부터 높은 우선순위를 부여합니다.
시스템 실행 시, 높은 우선순위 작업이 항상 먼저 실행되며, 작업이 완료되기 전이라도 우선순위가 높은 새 작업이 도착하면 선점됩니다.

RM 스케줄링의 장단점

장점:
간단한 구현 및 분석.
높은 예측 가능성.
단점:
CPU 활용률이 100%에 도달하지 못하는 경우가 있음(최대 활용률 ≈ 69.3% for n → ∞).
작업 주기가 동적으로 변화하는 경우 적합하지 않음.

RM 스케줄링은 일정한 주기를 가지는 작업에 적합하며, 시스템 안정성을 높이는 기본 알고리즘으로 사용됩니다.

EDF 스케줄링 알고리즘의 원리

EDF(Earliest Deadline First) 스케줄링은 동적 우선순위 스케줄링 알고리즘으로, 작업의 데드라인(마감 시간)을 기준으로 우선순위를 결정합니다. 데드라인이 가까운 작업이 항상 먼저 실행되며, 이는 시스템 실행 중 동적으로 변경됩니다.

EDF 스케줄링의 특징

동적 우선순위: 작업의 우선순위가 실행 중에도 데드라인에 따라 변화합니다.
데드라인 기반: 데드라인이 가장 임박한 작업이 우선적으로 실행됩니다.
최적성: EDF는 단일 프로세서 환경에서 가능한 가장 높은 CPU 활용률(100%)을 보장합니다.

작동 방식

작업 집합에서 각 작업의 데드라인을 확인합니다.
데드라인이 가장 가까운 작업에 높은 우선순위를 부여합니다.
실행 도중 새 작업이 도착하거나 데드라인이 갱신되면 우선순위를 재조정하여 가장 임박한 데드라인의 작업을 실행합니다.

EDF와 RM의 차이점

우선순위 설정: RM은 고정된 우선순위, EDF는 동적으로 변화하는 우선순위를 사용합니다.
CPU 활용률: RM은 최대 약 69.3%의 활용률을 가지지만, EDF는 100% 활용률을 보장합니다.
복잡성: EDF는 동적 조정이 필요하여 RM보다 구현이 복잡합니다.

장단점

장점:
높은 자원 활용률.
데드라인 중심으로 작업을 최적화.
단점:
복잡한 구현 및 계산량 증가.
시스템 과부하 시 예측이 어려움.

EDF는 리얼타임 시스템에서 성능 최적화가 중요한 경우 적합하며, 복잡한 환경에서도 높은 효율성을 제공합니다.

C 언어로 구현하는 RM 알고리즘

RM(Rate-Monotonic) 스케줄링 알고리즘은 주기가 짧은 작업에 높은 우선순위를 부여하여 실행하는 고정 우선순위 알고리즘입니다. 다음은 C 언어를 활용해 RM 알고리즘을 구현하는 방법을 소개합니다.

기본 코드 구조

RM 스케줄링 구현은 작업의 주기를 입력받아 우선순위를 계산하고, 작업을 실행하는 방식으로 구성됩니다.

코드 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;          // 작업 ID
    int period;      // 작업 주기
    int execution;   // 실행 시간
    int remaining;   // 남은 실행 시간
} Task;

void scheduleRM(Task tasks[], int n, int hyperPeriod) {
    for (int time = 0; time < hyperPeriod; time++) {
        int highestPriority = -1;
        int selectedTask = -1;

        // 우선순위 선택 (주기가 짧은 작업 우선)
        for (int i = 0; i < n; i++) {
            if (tasks[i].remaining > 0 && (highestPriority == -1 || tasks[i].period < tasks[highestPriority].period)) {
                highestPriority = i;
            }
        }

        // 선택된 작업 실행
        if (highestPriority != -1) {
            tasks[highestPriority].remaining--;
            printf("Time %d: Task %d executing\n", time, tasks[highestPriority].id);

            // 작업 완료 시 초기화
            if (tasks[highestPriority].remaining == 0) {
                tasks[highestPriority].remaining = tasks[highestPriority].execution;
            }
        }
    }
}

int main() {
    Task tasks[] = {
        {1, 4, 1, 1}, // 작업 1: 주기 4, 실행 시간 1
        {2, 6, 2, 2}, // 작업 2: 주기 6, 실행 시간 2
    };
    int n = sizeof(tasks) / sizeof(tasks[0]);
    int hyperPeriod = 12; // 초과 주기(12는 4와 6의 최소 공배수)

    scheduleRM(tasks, n, hyperPeriod);
    return 0;
}

코드 설명

작업 구조체(Task): 작업의 ID, 주기, 실행 시간, 남은 실행 시간을 정의합니다.
우선순위 결정: 주기가 가장 짧은 작업을 선택합니다.
작업 실행 및 리셋: 선택된 작업을 실행하고, 실행이 완료되면 다음 주기로 초기화합니다.

실행 결과

Time 0: Task 1 executing  
Time 1: Task 2 executing  
Time 2: Task 2 executing  
Time 4: Task 1 executing  
...

응용 및 확장

작업의 추가/삭제 기능 구현.
주기적 작업 외에 비주기적 작업 지원.
스케줄링 실패 시 경고 메시지 추가.

위 코드 예제를 통해 RM 알고리즘의 작동 원리를 이해하고 리얼타임 시스템 설계에 활용할 수 있습니다.

C 언어로 구현하는 EDF 알고리즘

EDF(Earliest Deadline First) 스케줄링 알고리즘은 데드라인이 가장 가까운 작업을 우선적으로 실행하는 동적 우선순위 알고리즘입니다. 다음은 C 언어를 활용하여 EDF 알고리즘을 구현하는 방법을 설명합니다.

기본 코드 구조

EDF 구현은 작업의 데드라인을 계산하고, 가장 임박한 데드라인을 가진 작업을 선택하여 실행하는 방식으로 설계됩니다.

코드 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;          // 작업 ID
    int period;      // 작업 주기
    int execution;   // 실행 시간
    int remaining;   // 남은 실행 시간
    int deadline;    // 데드라인
} Task;

void scheduleEDF(Task tasks[], int n, int hyperPeriod) {
    for (int time = 0; time < hyperPeriod; time++) {
        int selectedTask = -1;
        int earliestDeadline = -1;

        // 데드라인에 따른 작업 선택
        for (int i = 0; i < n; i++) {
            if (tasks[i].remaining > 0 && (earliestDeadline == -1 || tasks[i].deadline < earliestDeadline)) {
                selectedTask = i;
                earliestDeadline = tasks[i].deadline;
            }
        }

        // 선택된 작업 실행
        if (selectedTask != -1) {
            tasks[selectedTask].remaining--;
            printf("Time %d: Task %d executing\n", time, tasks[selectedTask].id);

            // 작업 완료 시 초기화
            if (tasks[selectedTask].remaining == 0) {
                tasks[selectedTask].remaining = tasks[selectedTask].execution;
                tasks[selectedTask].deadline += tasks[selectedTask].period; // 다음 데드라인 갱신
            }
        }
    }
}

int main() {
    Task tasks[] = {
        {1, 4, 1, 1, 4}, // 작업 1: 주기 4, 실행 시간 1, 초기 데드라인 4
        {2, 6, 2, 2, 6}, // 작업 2: 주기 6, 실행 시간 2, 초기 데드라인 6
    };
    int n = sizeof(tasks) / sizeof(tasks[0]);
    int hyperPeriod = 12; // 초과 주기(12는 4와 6의 최소 공배수)

    scheduleEDF(tasks, n, hyperPeriod);
    return 0;
}

코드 설명

작업 구조체(Task): 작업의 ID, 주기, 실행 시간, 남은 실행 시간, 데드라인을 정의합니다.
데드라인 기반 우선순위 결정: 데드라인이 가장 가까운 작업을 선택합니다.
작업 실행 및 데드라인 갱신: 작업이 완료되면 남은 시간을 초기화하고 데드라인을 갱신합니다.

실행 결과

Time 0: Task 1 executing  
Time 1: Task 2 executing  
Time 2: Task 2 executing  
Time 4: Task 1 executing  
...

응용 및 확장

작업이 데드라인을 초과했을 때 경고 메시지 추가.
비주기적 작업 지원.
시스템 과부하 시 대체 작업 수행 로직 추가.

EDF 알고리즘의 구현을 통해 데드라인 중심의 작업 스케줄링 방식과 이를 효율적으로 설계하는 방법을 학습할 수 있습니다.

스케줄링 알고리즘 성능 비교

RM(Rate-Monotonic)과 EDF(Earliest Deadline First)는 리얼타임 시스템에서 널리 사용되는 스케줄링 알고리즘입니다. 두 알고리즘은 성능, 활용도, 구현의 복잡성 등 다양한 측면에서 차이를 보입니다.

CPU 활용률 비교

RM 알고리즘:
RM은 최대 CPU 활용률이 (U = n(2^{1/n} – 1))로 제한됩니다. 작업 수 (n)이 증가하면 활용률은 약 69.3%에 수렴합니다.
EDF 알고리즘:
EDF는 단일 프로세서 환경에서 100% CPU 활용률을 보장합니다. 즉, 데드라인이 충족 가능한 경우 모든 작업을 스케줄링할 수 있습니다.

우선순위 관리

RM 알고리즘:
작업의 주기에 따라 우선순위를 고정하며, 실행 중에는 우선순위가 변하지 않습니다.
EDF 알고리즘:
작업의 데드라인에 따라 동적으로 우선순위를 조정합니다. 데드라인이 가까운 작업이 항상 먼저 실행됩니다.

알고리즘의 복잡성

RM 알고리즘:
고정 우선순위 기반으로 작동하여 구현이 간단하고 실행 중의 계산량이 적습니다.
EDF 알고리즘:
동적 우선순위를 유지해야 하므로 매 작업마다 우선순위를 계산하고 갱신해야 하며, RM에 비해 구현이 복잡합니다.

장단점 요약

특징	RM 알고리즘	EDF 알고리즘
CPU 활용률	최대 약 69.3%	최대 100%
우선순위 관리	고정 우선순위	동적 우선순위
구현 난이도	간단	상대적으로 복잡
적합성	주기가 고정된 작업에 적합	데드라인 중심 시스템에 적합
과부하 상황	일부 작업 실패 가능	데드라인 초과 작업 발생 가능

사용 시나리오

RM 사용 사례:
작업 주기가 고정되어 있고, 복잡한 동적 관리가 필요하지 않은 경우.
예: 산업 제어 시스템, 주기적 데이터 수집.
EDF 사용 사례:
데드라인 중심 작업이 많고, 자원 활용도를 최적화해야 하는 경우.
예: 멀티미디어 스트리밍, 항공 제어 시스템.

RM과 EDF는 각기 다른 특성과 강점을 가지고 있으며, 시스템의 요구사항에 따라 적절한 알고리즘을 선택해야 합니다.

리얼타임 시스템에서 발생 가능한 문제 해결

리얼타임 시스템은 시간 제약과 자원 제약이 존재하기 때문에 스케줄링 실패나 데드락과 같은 문제가 발생할 수 있습니다. 이러한 문제를 사전에 예방하고 해결하는 방법을 이해하는 것이 중요합니다.

스케줄링 실패 문제

스케줄링 실패는 작업이 데드라인 내에 완료되지 못하는 상황을 의미합니다.

원인

작업 집합의 CPU 요구량이 시스템의 최대 용량을 초과한 경우.
RM 알고리즘 사용 시 활용률이 69.3%를 초과한 경우.
EDF 알고리즘 사용 시 과부하로 인해 데드라인이 초과된 경우.

해결 방법

작업 집합 분석: 작업의 CPU 요구량(실행 시간/주기)을 계산하고, 총합이 허용 가능한 범위인지 확인합니다.
우선순위 조정: 중요도가 낮은 작업을 연기하거나 제거하여 높은 중요도의 작업을 우선적으로 실행합니다.
오프라인 스케줄링: 작업 집합을 사전에 분석하여 스케줄링 가능성을 검증합니다.

데드락 문제

데드락은 작업들이 서로의 자원을 기다리며 정지 상태가 되는 문제입니다.

원인

작업이 필요한 자원을 순서 없이 요청하는 경우.
자원 할당 그래프에서 순환이 발생한 경우.

해결 방법

자원 할당 순서 정의: 자원을 획득하는 순서를 정하여 순환을 방지합니다.
데드락 탐지 알고리즘: 자원 할당 그래프를 분석하여 순환이 발생했는지 확인합니다.
타임아웃 설정: 작업이 일정 시간 동안 자원을 획득하지 못하면 대기 상태를 종료합니다.

시간 초과 문제

리얼타임 작업이 지정된 기한 내에 완료되지 못할 때 발생합니다.

해결 방법

최적화된 알고리즘 사용: RM 대신 EDF를 사용하여 CPU 활용도를 극대화합니다.
작업 분리: 실행 시간이 긴 작업을 더 작은 단위로 나눠 스케줄링 가능성을 높입니다.
시뮬레이션 테스트: 작업 집합과 시스템 환경에서 시뮬레이션을 통해 시간 초과 가능성을 분석합니다.

장기적인 개선 방안

시스템 설계 초기부터 분석: 스케줄링 가능성을 고려하여 작업 설계 및 자원 배치를 계획합니다.
실시간 운영체제 활용: 리얼타임 스케줄링 지원이 포함된 RTOS(Real-Time Operating System)를 도입합니다.
모니터링 및 조정: 시스템 실행 중 작업의 우선순위나 자원 사용량을 지속적으로 모니터링하여 조정합니다.

리얼타임 시스템에서 발생 가능한 문제를 사전에 예방하고, 발생 시 적절히 대응함으로써 시스템 안정성과 신뢰성을 유지할 수 있습니다.

학습 심화를 위한 연습 문제와 실습

리얼타임 스케줄링 알고리즘에 대한 이해를 깊게 하기 위해 연습 문제와 실습을 제공합니다. RM과 EDF 알고리즘의 작동 원리와 구현 방법을 적용하고, 다양한 시나리오를 분석하며 학습을 심화할 수 있습니다.

연습 문제

문제 1: RM 알고리즘 스케줄링 가능성 검증

다음 작업 집합이 RM 알고리즘을 사용하여 스케줄링 가능한지 계산하세요.

작업 1: 주기 = 4, 실행 시간 = 1
작업 2: 주기 = 6, 실행 시간 = 2
작업 3: 주기 = 8, 실행 시간 = 2

힌트: CPU 활용률 ( U = \sum_{i=1}^n \frac{C_i}{T_i} )를 계산하고, 활용률 한계 ( U = n(2^{1/n} – 1) )와 비교합니다.

문제 2: EDF 알고리즘 데드라인 초과 여부 분석

다음 작업 집합이 EDF 알고리즘으로 데드라인 초과 없이 스케줄링 가능한지 분석하세요.

작업 1: 데드라인 = 5, 실행 시간 = 2
작업 2: 데드라인 = 8, 실행 시간 = 3
작업 3: 데드라인 = 10, 실행 시간 = 2

문제 3: 코드 수정

제공된 RM 또는 EDF 알고리즘 코드에서 작업 추가 기능을 구현하세요. 사용자가 새로운 작업의 주기와 실행 시간을 입력할 수 있도록 프로그램을 확장합니다.

실습 과제

과제 1: RM 및 EDF 알고리즘 비교

제공된 RM과 EDF 알고리즘 코드를 사용하여 동일한 작업 집합을 스케줄링합니다.
두 알고리즘의 CPU 활용률, 데드라인 준수율, 스케줄링 실패 사례를 비교하세요.

과제 2: 비주기 작업 추가

비주기적 작업(데드라인이 없는 작업)을 처리하는 기능을 구현합니다.
비주기 작업이 리얼타임 작업과 충돌하지 않도록 스케줄링 우선순위를 조정합니다.

과제 3: 시뮬레이션 환경 구축

다양한 작업 집합을 자동으로 생성하는 프로그램을 작성합니다.
생성된 작업 집합을 RM과 EDF 알고리즘으로 실행하고 결과를 비교합니다.

결과 분석

문제 풀이와 실습 결과를 토대로 두 알고리즘의 장단점 및 적합한 활용 시나리오를 분석합니다.
작업 집합의 구성(주기, 실행 시간, 데드라인)에 따른 스케줄링 성능 변화를 평가합니다.

위 연습 문제와 실습 과제를 통해 RM과 EDF 알고리즘의 이론적 개념과 실제 적용 방법을 심화 학습할 수 있습니다.

요약

본 기사에서는 리얼타임 시스템에서 RM(Rate-Monotonic)과 EDF(Earliest Deadline First) 스케줄링 알고리즘의 원리, 구현 방법, 성능 비교, 문제 해결 방법, 그리고 학습 심화를 위한 연습 문제와 실습 과제를 다루었습니다.

RM은 간단하고 예측 가능한 고정 우선순위 방식으로, 주기가 고정된 작업에 적합합니다. 반면, EDF는 높은 CPU 활용률을 보장하며 데드라인 중심의 동적 환경에서 강력한 성능을 발휘합니다.

제공된 코드와 실습을 통해 이 두 알고리즘의 개념과 실제 응용 방법을 익히고, 리얼타임 시스템 설계와 구현 능력을 향상시킬 수 있습니다.