실시간 운영체제

3. 스케줄링

전통적인 설계 방식에서, 태스크는 수행(running), 대기(ready), 블록(blocked)의 세 가지 상태 중 하나로 존재한다. 대부분의 태스크는 블록 상태이며, 오직 하나의 태스크만 수행 상태이다. 간단한 시스템일수록 대기 상태의 태스크 목록은 짧으며, 많은 경우에도 2~3개 정도이다.

일반적으로 스케줄러의 대기 태스크 목록의 데이터 구조는 스케줄러의 임계 구역(CPU의 선점이 금지되며, 어떠한 경우에는 모든 인터럽트가 비활성화된다.)에서 소비되는 시간을 최소화할 수 있게 설계된다. 그러나 데이터 구조의 선택은 대기 리스트에 들어갈 수 있는 최대 태스크의 수에도 좌우된다.

대기 목록에 태스크가 적다면, 이중 연결 리스트 구조로 대기 목록을 구현하는 것도 효율적이다. 반면, 태스크가 많아지면 우선 순위를 기준으로 미리 정렬하거나, 높은 우선 순위의 태스크를 낮은 우선 순위의 태스크보다 먼저 대기 리스트에 추가할 수 있도록 설계하여, 태스크를 실행할 때마다 전체 목록을 뒤져 우선 순위가 높은 태스크를 찾는 작업을 반복하지 않도록 한다. 즉, 대기 목록을 검색하는 동안 CPU의 선점을 금지하지 않거나 긴 임계 구역을 작게 나누어야 한다. 이는 낮은 우선 순위의 태스크를 리스트에 추가하는 동안이라도, 높은 우선 순위의 태스크를 대기 상태로 만드는 인터럽트가 발생하면, 높은 우선 순위의 태스크를 먼저 대기 목록에 추가하고 바로 수행할 수 있도록 한다는 것이다.

새로운 태스크가 생성되면 이 태스크는 일단 대기 상태가 된다. 스케줄러는 현재 수행 중인 태스크 역시 대기 상태로 변경하고, 두 개의 태스크를 대기 상태 태스크 목록에 집어넣는다. 그 후, 가장 우선 순위가 높은 태스크를 다시 수행하는데 이 전체 과정에 걸리는 시간을 중요 응답 시간(critical response time) 혹은 플라이백 타임(flyback time)이라고 부른다. 잘 설계된 실시간 운영체제의 경우, 새로운 태스크를 대기 상태로 만드는 데 3~20개의 명령어를 사용한다. 또, 가장 높은 우선 순위를 가진 대기 태스크를 수행 상태로 변경하는데 5~30개의 명령어를 사용한다.

고급 실시간 운영체제에서는 실시간 태스크와 비실시간 태스크가 컴퓨터 자원을 공유하므로, 대기 리스트는 상당히 길어질 수 있다. 이러한 시스템에서 스케줄러 대기 리스트를 연결 리스트로 구현하는 것은 알맞지 않다.

실시간 운영체제(RTOS)의 핵심적인 특징은 응용 프로그램의 태스크를 수용하고 완료하는 데 걸리는 시간의 일관성 수준이며, 이러한 변동성을 "지터"라고 한다.^[2] "하드" 실시간 운영체제(하드 RTOS)는 "소프트" 실시간 운영체제(소프트 RTOS)보다 지터가 적다. 하드 RTOS에서는 늦은 응답이 잘못된 응답인 반면, 소프트 RTOS에서는 늦은 응답이 허용된다. 주요 설계 목표는 높은 처리량이 아니라 소프트 또는 하드 성능 범주를 보장하는 것이다. 일반적으로 또는 대개 마감 시간을 충족할 수 있는 RTOS는 소프트 실시간 OS이지만, 결정적으로 마감 시간을 충족할 수 있다면 하드 실시간 OS이다.^[3]

RTOS는 스케줄링을 위한 고급 알고리즘을 가지고 있다. 스케줄러의 유연성은 더 넓은 컴퓨터 시스템의 프로세스 우선순위 조정을 가능하게 하지만, 실시간 OS는 더 좁은 범위의 응용 프로그램에 자주 전념한다. 실시간 OS의 핵심 요소는 최소한의 인터럽트 지연 시간과 최소한의 스레드 전환 지연 시간이다. 실시간 OS는 주어진 시간 내에 수행할 수 있는 작업량보다 얼마나 빠르고 예측 가능하게 응답할 수 있는지에 더 가치를 둔다.^[4]

RTOS는 일반적으로 멀티태스킹 운영체제이며, 스케줄링은 태스크의 우선 순위에 따라 수행된다. 실행 중인 태스크보다 우선 순위가 높은 태스크가 실행 가능한 상태가 되면 즉시 태스크 전환을 수행한다. 즉, RTOS는 "선점형 멀티태스킹"(선점 참조)이어야 한다. 또한 RTOS의 경우, 커널이 우선 순위가 낮은 태스크에 의한 시스템 콜을 실행 중일 때 임계 구역이 아니라면 우선 순위가 높은 태스크를 실행하는 "선점형 커널"이어야 한다.

범용 OS처럼 태스크의 소비 시간에 따라 우선 순위를 변화시키는 것은 일반적으로 수행하지 않는다. 단, 시간 제약이 없는 저우선 순위 태스크를 함께 사용하는 경우 등, 해당 태스크에서는 우선 순위를 공통으로 하고, 자발적으로 CPU를 양보하는 협조적 멀티태스킹이나, 타이머 인터럽트에 의해 순서대로 전환하는 시분할적인 스케줄링을 함께 사용하는 경우도 있다.

고급 실시간 시스템에서는 실시간 태스크 외에 비실시간 태스크도 공존하므로, 실행 가능 리스트는 매우 길어질 수 있다. 그러한 시스템에서는 스케줄러의 실행 가능 리스트를 단순한 선형 리스트로 구현하는 것은 불충분하다. 이 때문에, 우선 순위별로 실행 가능 리스트를 분할하여 검색 처리를 불필요하게 하는 경우도 있다.

3. 1. 스케줄링 알고리즘

• 협력형 스케줄링
• 선점형 스케줄링
• 고정 우선순위 스케줄링
• 라운드 로빈 스케줄링
• 고정 우선순위 선점형 스케줄링, 선점형 시분할 구현
• 지연 선점형 고정 우선순위 스케줄링
• 비선점형 고정 우선순위 스케줄링
• 임계 구역 선점형 스케줄링
• 정적 시간 스케줄링
• 최종 기한 우선 스케줄링 방식
• 확률적 방향 그래프와 다중 스레드 그래프 순회

4. 태스크 간 통신과 자원 공유

멀티태스킹 시스템은 여러 태스크 간에 데이터와 하드웨어 자원을 공유해야 한다. 일반적으로 두 개 이상의 태스크가 동시에 같은 데이터나 하드웨어 자원에 접근하는 것은 위험하며, 이는 데이터 갱신 중 결과의 불일치 및 예측 불가능성을 초래할 수 있다.^[6] 다른 태스크가 이러한 데이터에 접근하는 것은 갱신 전이나 완료 후에만 가능하다.

이 문제를 해결하기 위한 세 가지 일반적인 접근 방식은 다음과 같다.

• 인터럽트를 일시적으로 비활성화(마스크)
• 이진 세마포어 (락 또는 뮤텍스)
• 메시지 전달

4. 1. 일시적인 인터럽트 비활성화

4. 2. 세마포어(뮤텍스)

4. 3. 메시지 전달

• 우선 순위 역전: 낮은 우선 순위 메시지를 처리하는 태스크가 메시지 큐에서 더 높은 우선 순위 메시지(또는 높은 우선 순위 태스크에서 간접적으로 발생하는 메시지)를 무시할 때 발생한다.
• 프로토콜 교착 상태: 둘 이상의 태스크가 서로에게 응답 메시지를 보내기를 기다릴 때 발생한다.

5. 인터럽트 핸들러와 스케줄러

인터럽트 핸들러는 실행 중인 가장 높은 우선 순위의 태스크조차도 중단시킬 수 있다.^[4] RTOS는 스레드 대기 시간을 최소화하기 위해 인터럽트 핸들러의 기능을 가능한 한 최소화한다.^[2] 인터럽트 핸들러는 가능한 경우 하드웨어와의 모든 상호 작용을 연기하며, 일반적으로 인터럽트를 승인하거나 비활성화하고 작업을 수행해야 함을 알리는 것으로 충분하다. 이는 세마포어를 해제하거나, 플래그를 설정하거나, 메시지를 전송하여 드라이버 작업을 차단 해제함으로써 수행할 수 있다.^[4] 스케줄러는 종종 인터럽트 핸들러 컨텍스트에서 작업을 차단 해제하는 기능을 제공한다.^[4]

6. 메모리 할당

실시간 운영체제에서 메모리 할당은 안정성과 속도 면에서 일반적인 운영체제보다 더 중요하다. 안정성을 위해 메모리 누수가 없어야 하며, 장치는 재부팅 없이 무기한 작동해야 한다. 따라서 동적 메모리 할당은 권장되지 않고, 가능한 모든 메모리 할당은 컴파일 시간에 정적으로 지정하는 것이 좋다.

일반적인 메모리 할당 방식은 적합한 여유 메모리 블록을 찾기 위해 불확정적인 길이의 연결 리스트를 스캔하는데,^[9] 이는 특정 시간 내에 메모리 할당이 완료되어야 하는 실시간 운영체제에서는 허용될 수 없다. 또한, 메모리 단편화 문제도 발생할 수 있다.

따라서 단순한 임베디드 시스템에는 고정 크기 블록 알고리즘이 낮은 오버헤드 때문에 매우 적합하다.

6. 1. 안정성

6. 2. 속도

7. 임베디드 시스템의 메모리 사용

몇몇 RTOS(임베디드 운영체제)는 ''XIP''(즉석 실행)을 지원한다. 커널과 응용 프로그램들이 코드를 RAM으로 먼저 전송하지 않고 ROM에서 직접 실행된다. 운영체제에 필요한 RAM 크기와 ROM 크기 사이의 교환을 제공한다.

8. 다양한 RTOS들

• https://web.archive.org/web/20170825082447/http://mdstec.com/ 국방/항공용 실시간 운영체제 NEOS (한국)
• https://www.rtst.co.kr/rtworks RTWORKS (한국)
• VxWorks
• QNX
• http://www.freertos.org FreeRTOS
• eCos
• 윈도우 CE
• BeOS
• LynxOS
• Nucleus RTOS
• OSEK/VDX
• ITRON
• RTLinux
• RTAI
• BeRTOS^영어
• ChibiOS/RT
• Contiki
• Enea OSE
• L4
• mbed (keil RTX 기반)
• μITRON
• OS-9
• pSOS^영어
• RedHawk Linux
• REX OS
• RT-11
• RTX^영어
• RTEMS
• T-Kernel
• THEOS
• TOPPERS
• VRTX^영어

9. API 분류

소규모 운영체제는 자체적으로 구현되는 경우가 많아, 사양도 각기 독자적인 경우가 많다. 공통 규격으로는 주로 일본을 중심으로 보급된 ITRON과 유럽을 중심으로 한 차량용 OSEK가 있다.

실시간 유닉스의 표준으로는, POSIX의 실시간 확장인 POSIX 1003.1b가 있다.

10. 응용 분야

RTOS는 다양한 분야에서 활용된다. 소규모 임베디드 시스템 등에 많이 사용되지만, 데스크톱 분야나 PDA 등 비교적 대규모 시스템부터, 나아가 미션 크리티컬 서버나 인공위성에까지 사용된다.

특히 멀티코어 및 범용 하드웨어를 지원하는 리눅스의 실시간 커널은 틈새 시장 업계에서 많이 사용된다. 예를 들어 멀티코어 MIPS와 함께 통신 업계에서 사용된 Montavista Linux CGE, 실시간 오디오 처리를 위한 데스크톱 환경인 우분투 스튜디오, 금융 업계에서는 금융 거래 시스템이나 고빈도 거래에까지 사용된다.

참조

_[1] 웹사이트 Real-time Operating Systems (RTOS) https://www.benzinga[...] 2023-09-13
_[2] 웹사이트 Response Time and Jitter https://web.archive.[...] 2010-12-04
_[3] 서적 Modern Operating Systems Pearson/Prentice Hall
_[4] 웹사이트 RTOS Concepts https://web.archive.[...] 2010-12-04
_[5] 웹사이트 Programming embedded systems: RTOS – what is real-time? https://www.embedded[...] 2023-05-23
_[6] 간행물 The Future of Unix on the IBM PC https://archive.org/[...] 1984-09
_[7] 웹사이트 CS 241, University of Illinois http://courses.engr.[...]
_[8] 서적 Modern Operating Systems Pearson/Prentice Hall
_[9] 문서 CS 241, University of Illinois http://courses.engr.[...]