운영체제의 스케줄링 알고리즘: 실시간 시스템에서의 선점형 스케줄링

스케줄링 알고리즘의 핵심: 실시간 시스템의 생존 조건

실시간 시스템에서 스케줄링 알고리즘은 단순한 성능 최적화 도구가 아닙니다. 시스템의 생존과 신뢰성을 좌우하는 핵심 인프라입니다. 실시간 시스템은 처리 결과의 정확성뿐만 아니라, 결과가 도출되는 시간적 제약을 반드시 만족해야 합니다. 이 시간적 제약, 즉 ‘데드라인’을 지키지 못하면 시스템은 심각한 오류 상태에 빠지거나 전체 시스템이 멈출 수 있습니다. 따라서 실시간 시스템의 스케줄링은 항상 데드라인을 최우선으로 고려합니다.

실시간 시스템의 두 가지 유형: Hard와 Soft

실시간 시스템을 스케줄링하기 전에, 시스템이 어떤 유형인지 명확히 구분해야 합니다. 이 구분은 허용 가능한 실패의 수준을 정의하며, 알고리즘 선택의 근본적 기준이 됩니다.

• Hard Real-Time System (경성 실시간 시스템): 데드라인을 절대적으로 지켜야 합니다. 데드라인을 초과하는 것은 시스템의 완전한 실패로 간주됩니다. 예시로는 항공기 제어 시스템, 자동차의 에어백 제어 시스템, 원자력 발전소 제어 시스템 등이 있습니다. 여기서는 ‘데드라인 미스’가 인명 피해나 막대한 재산 손실로 직결됩니다.
• Soft Real-Time System (연성 실시간 시스템): 데드라인을 최대한 지키는 것이 중요하지만, 일부 초과가 시스템 전체의 실패를 의미하지는 않습니다. 다만 서비스 품질이 저하됩니다. 예시로는 스트리밍 미디어 서버, 실시간 주식 차트 시스템, 대화형 멀티미디어 애플리케이션 등이 있습니다. 버퍼링이나 프레임 드롭이 발생할 수 있지만, 시스템은 계속 동작합니다.

이 글에서 다루는 선점형 스케줄링 기법은 주로 Hard Real-Time System을 보장하기 위한 필수 메커니즘입니다.

선점형 스케줄링: 실시간성을 보장하는 유일한 방법

비선점형 스케줄링에서는 실행 중인 태스크가 자발적으로 CPU를 반납할 때까지 다른 태스크는 대기해야 합니다. 이 방식은 실시간 시스템에서는 치명적입니다. 긴급한 데드라인을 가진 태스크가 CPU를 선점하지 못하고, 무한 루프에 빠진 일반 태스크를 하염없이 기다려야 할 수 있기 때문입니다. 따라서 모든 실시간 운영체제의 스케줄링은 반드시 선점형이어야 합니다. 선점형 스케줄링은 스케줄러가 더 높은 우선순위의 태스크가 준비되면, 현재 실행 중인 태스크의 실행을 강제로 중단시키고 CPU를 회수하여 높은 우선순위 태스크에 할당하는 방식입니다.

실시간 시스템을 위한 주요 선점형 스케줄링 알고리즘

다음 알고리즘들은 실시간 태스크의 데드라인을 보장하기 위해 설계되었으며, 각각의 적용 시나리오와 제약 조건이 명확합니다.

Rate-Monotonic Scheduling (RMS, 주기 모노토닉 스케줄링)

주기적인 태스크 집합을 스케줄링하는 고전적이면서도 이론적 토대가 확실한 알고리즘입니다. 여기서 ‘주기’란 태스크가 반복적으로 실행되어야 하는 시간 간격을 의미합니다, rms의 규칙은 매우 직관적입니다. 더 짧은 주기를 가진 태스크에게 더 높은 우선순위를 부여합니다. 이는 더 자주 실행해야 하는 태스크가 더 긴급하다는 가정에서 출발합니다.

RMS의 가장 큰 장점은 스케줄 가능성 테스트가 존재한다는 점입니다. 태스크의 수, 실행 시간, 주기만 알면 아래 공식을 통해 이 태스크 집합이 데드라인을 보장하며 스케줄 가능한지 수학적으로 판단할 수 있습니다.

U = Σ (Ci / Ti) ≤ n(2^(1/n) – 1)

여기서 U는 총 CPU 사용률, Ci는 태스크 i의 최악 실행 시간, Ti는 태스크 i의 주기, n은 태스크 수입니다. n이 무한대로 갈 때, 이 우선 상한은 약 69% (ln 2)에 수렴합니다. 즉, RMS 하에서 모든 데드라인을 보장하려면 CPU 사용률이 69% 이하여야 함을 의미합니다. 이는 CPU 자원을 희생하여 스케줄링의 예측 가능성과 신뢰성을 얻는 전형적인 트레이드오프입니다.

Earliest Deadline First (EDF, 가장 빠른 데드라인 우선)

RMS의 CPU 사용률 제한을 극복한 동적 우선순위 기반 알고리즘입니다. 이처럼 eDF의 규칙은 이름 그대로입니다. 현재 시점에서 데드라인이 가장 가까운 태스크에게 가장 높은 우선순위를 부여합니다. 태스크의 주기나 실행 시간과 무관하게, 데드라인만이 유일한 기준입니다.

EDF의 가장 강력한 이론적 배경은 필요충분조건을 가진다는 것입니다. 태스크 집합이 스케줄 가능하기 위한 필요충분조건은 총 CPU 사용률 U가 100% 이하인 것뿐입니다.

U = Σ (Ci / Ti) ≤ 1

이는 이론적으로 CPU를 100%까지 활용하면서도 모든 데드라인을 보장할 수 있음을 의미합니다. RMS보다 훨씬 효율적입니다. 하지만 동적 우선순위 변경으로 인한 런타임 오버헤드가 더 크며, 과부하 상황(CPU 사용률 > 100%)에서 어떤 태스크의 데드라인을 놓칠지 예측하기 어려워 시스템 동작이 불안정해질 수 있습니다. RMS는 과부하 시 우선순위가 낮은 태스크가 데드라인을 놓치는 예측 가능한 패턴을 보입니다.

실제 적용: 우선순위 역전 문제와 그 해결책

이론적으로 완벽한 스케줄링 알고리즘을 도입하더라도, 실제 시스템 구현에서 공유 자원(예: 메모리, I/O 디바이스, 세마포어)에 대한 접근은 치명적인 문제를 일으킵니다. 바로 우선순위 역전 현상입니다.

우선순위 역전은 다음과 같은 시나리오로 발생합니다.

1. 낮은 우선순위 태스크(L)가 공유 자원 R에 대한 락을 획득하고 실행 중입니다.
2. 중간 우선순위 태스크(M)가 준비되어, 선점으로 인해 L의 실행을 중단시킵니다. (M은 R을 필요로 하지 않음)
3. 높은 우선순위 태스크(H)가 준비되어 실행되려 하지만, H는 R이 필요합니다. R은 아직 L이 잡고 있고, L은 M에 의해 선점당해 실행조차 못하고 있습니다.
4. 그래서, 가장 높은 우선순위를 가진 H가 중간 우선순위인 M이 실행을 마칠 때까지 무기한 대기해야 하는 상황이 발생합니다. H의 우선순위가 사실상 M보다 낮아진 것과 같은 효과입니다.

이 문제는 실시간 시스템에서 데드라인 미스를 유발하는 주요 원인입니다. 이를 해결하기 위한 표준적인 기법이 우선순위 상속 프로토콜과 우선순위 천장 프로토콜입니다.

우선순위 상속 프로토콜 (Priority Inheritance Protocol. Pip)

프로토콜의 기본 원리는 자원 경합 상황에서 발생할 수 있는 역전 현상을 방지하는 데 집중합니다. 높은 우선순위 태스크(H)가 낮은 우선순위 태스크(L)에 의해 점유된 자원을 대기할 때 L의 우선순위를 H의 수준으로 일시적 상향 조정하며, 홈페이지데일리 또한 이러한 스케줄링 로직을 바탕으로 시스템의 실시간 응답성을 확보합니다. 이러한 메커니즘은 L이 중간 우선순위 태스크(M)에 의해 선점되는 것을 차단하여 자원 반납 속도를 가속화하고, 결과적으로 H의 대기 시간을 최소화한 뒤 자원 해제와 동시에 L을 원래의 우선순위로 복귀시킵니다.

우선순위 천장 프로토콜 (Priority Ceiling Protocol, PCP)

PIP보다 더 강력하고 예측 가능성을 높인 프로토콜입니다. 각 공유 자원에 미리 ‘천장 우선순위’를 할당하며, 이 우선순위는 해당 자원을 사용할 수 있는 모든 태스크 중 가장 높은 우선순위로 설정됩니다. 실시간 시스템의 자원 관리 체계인 우선순위 역전(Priority Inversion) 의 발생 원인과 해결 메커니즘을 조사한 바에 따르면, 태스크가 자원에 대한 락을 획득하는 순간 해당 태스크의 우선순위가 자원의 천장 우선순위로 상승하게 됩니다.

이 방식은 우선순위 역전을 근본적으로 차단할 뿐만 아니라 데드락 발생 가능성도 제거합니다. 구현이 더 복잡하지만, 고신뢰성 실시간 시스템에서는 사실상 표준으로 자리 잡았습니다.

실시간 Linux에서의 구현 체크리스트

일반 Linux 커널은 완전한 실시간성을 보장하지 않습니다. 실시간 성능을 확보하려면 다음과 같은 조치가 필수적입니다.

• 실시간 커널 패치 적용 (PREEMPT_RT): 일반 Linux 커널의 비선점 영역(스핀락, 인터럽트 핸들러 등)을 최대한 선점 가능하게 만드는 패치를 적용해야 합니다.
• 스케줄러 정책 설정: 실시간 태스크에는 SCHED_FIFO 또는 SCHED_RR 정책을 할당합니다. SCHED_FIFO는 선점형이며, 동일 우선순위 내에서는 선입선출 방식으로 동작합니다. SCHED_RR은 SCHED_FIFO에 라운드 로빈 타임 슬라이스를 추가한 방식입니다.
• CPU 고정 (CPU Affinity/Pinning): 실시간 태스크를 전용 CPU 코어에 고정시켜, 다른 일반 태스크나 인터럽트의 간섭을 최소화합니다.
• 인터럽트 부하 분산: 가능한 많은 디바이스 인터럽트를 실시간 태스크가 실행되지 않는 CPU 코어로 라우팅합니다.
• 메모리 잠금 (mlockall): 실시간 프로세스의 핵심 메모리를 스왑 아웃되지 않도록 물리 메모리에 고정합니다. 페이지 폴트로 인한 불확실한 지연을 제거합니다.

전문가 팁: 실시간 시스템 설계의 첫걸음은 Worst-Case Execution Time 분석

아무리 훌륭한 스케줄링 알고리즘을 도입해도, 각 태스크의 최악 실행 시간(WCET)을 정확히 모르면 모든 계산이 무의미해집니다. WCET 분석은 코드의 모든 경로, 캐시 미스 시나리오, 메모리 접근 지연을 고려한 보수적 추정이어야 합니다. 실제 평균 실행 시간의 2~5배, 경우에 따라 10배 이상으로 설정하는 경우도 있습니다. 이 보수적인 수치를 바탕으로 스케줄 가능성 테스트를 수행한 후, 시스템을 구축하는 것이 실시간 시스템 엔지니어링의 정석입니다.

특히 고빈도의 센서 데이터를 처리하는 환경에서는 이러한 시간 엄격성이 더욱 강조됩니다. 예를 들어, 모바일 기기의 가속도계 및 자이로스코프 데이터를 이용한 동작 인식 기술 사례처럼 밀리초(ms) 단위의 샘플링 데이터를 실시간으로 연산하여 사용자의 움직임을 파악해야 하는 시스템에서는, 알고리즘의 실행 지연이 곧 인식 오류나 시스템 프리징으로 이어질 수 있습니다.

“대충 돌아가니까 괜찮다”는 접근은 하드 실시간 시스템(Hard Real-Time System)에서는 재난을 초래합니다. 따라서 개발자는 센서 데이터의 수집부터 피처 추출, 분류 모델의 추론에 이르기까지 전 과정의 시간적 상한선을 명확히 규정하고 이를 보장하는 아키텍처를 설계해야 합니다.