실시간 운영 체제

스케줄링

전통적인 설계 방식에서, 태스크는 수행(running), 대기(ready), 블록(blocked)의 세 가지 상태(state) 중 한 가지 상태로 존재한다. 대부분의 태스크가 블록상태이고, 오직 1개의 태스크만 수행상태이다. 간단한 시스템 일수록 대기 상태의 태스크 목록이 짧으며, 많은 경우도 2~3개 정도이다.
일반적으로 스케줄러 대기 태스크 목록의 데이터 구조는 스케줄러의 임계 구역 (CPU의 선점이 금지되며, 어떠한 경우에는 모든 인터럽트가 비활성화된다.) 에서 소비되는 시간을 최소화할 수 있게 설계 한다. 하지만, 데이터 구조의 선택은 대기 리스트에 들어갈 수 있는 최대 태스크의 숫자에도 좌우된다.
만약 대기 목록에 2~3개 정도에 적은 수의 태스크만 존재하는 구조라면, 단순히 이중 연결 리스트 구조로 대기 목록을 구현 하는 것도 효율적이다. 반면, 통상 적은 수에 태스크만 존재하지만 가끔 그보다 많은 수가 존재하는 경우라면, 태스크를 실행할 때마다 전체 목록을 뒤져 우선 순위가 높은 태스크를 찾는 작업을 반복적으로 하지 않도록 우선 순위를 기준으로 미리 정렬하거나 높은 우선 순위의 태스크를 낮은 우선 순위의 태스크보다 먼저 대기 리스트에 추가할 수 있도록 설계한다. 즉, 대기 목록을 검색하는 동안 CPU의 선점을 금지하지 않거나 긴 임계 구역을 작게 나누어야 한다는 의미이다. 이 말은 낮은 우선 순위의 태스크를 리스트에 추가하는 동안이라도, 높은 우선 순위의 태스크를 대기 상태로 만드는 인터럽트가 발생하면, 높은 우선 순위의 태스크를 먼저 대기 목록에 추가하고 바로 수행할 수 있도록 한다는 것이다.
새로운 태스크가 생성되면 이 태스크는 일단 대기 상태가 된다. 스케줄러는 현재 수행중인 태스크 역시 대기 상태로 변경하고, 두 개의 태스크를 대기 상태 태스크 목록에 집어 넣는다. 그 후, 가장 우선 순위가 높은 태스크를 다시 수행하는데 이 전체 과정에 걸리는 시간을 중요 응답 시간(critical response time) 혹은 플라이백 타임 (flyback time) 이라고 부른다. 잘 설계된 실시간 운영 체제의 경우, 새로운 태스크를 대기 상태로 만드는 데 3-20개의 명령어를 사용한다. 또, 가장 높은 우선 순위를 가진 대기 태스크를 수행 상태로 변경하는데 5-30개의 명령어를 사용한다.
고급 실시간 운영 체제에서는 실시간으로 동작하는 태스크들이 실시간으로 동작하지 않는 태스크들과 컴퓨터 자원을 공유한다. 따라서 대기 리스트는 상당히 길어질 수 있다. 이러한 시스템에서 스케줄러 대기 리스트를 간단한 연결 리스트(linked list)로 구현하는 것은 알맞지 않다.

태스크 간 통신과 자원 공유

멀티태스킹 시스템은 여러 개의 태스크 사이에 공유되는 데이터와 하드웨어 자원을 관리해 주어야 한다. 대부분의 경우 두 개 이상의 태스크가 동시에 같은 데이터나 하드웨어 자원에 접근하는 것은 위험하다. ("위험"하다는 것은 한 태스크가 복수의 데이터를 갱신하는 중일 경우, 결과가 일관성이 없고 예측 불가능하다는 뜻이다. 다른 태스크가 이 데이터들에 접근해도 되는 시점은 갱신이 시작하기 전이나 완전히 종료된 후 뿐이다.) 이 문제를 해결하기 위해서 보통 사용되는 3가지 방식을 소개한다.

일시적인 인터럽트 비활성화

범용 운영 체제에서는 사용자가 인터럽트를 마스크(비활성화)하지 못한다. 그 이유는 사용자의 프로그램이 운영 체제의 핵심 자원인 CPU를 너무 긴 시간동안 점유하고 있을 수 있기 때문이다. 다시 말해, 현재 사용되는 대다수의 CPU들은 사용자 모드 코드가 인터럽트를 비활성화할 수 있는 권한을 부여하지 않는다. 하지만, 많은 임베디드 시스템과 실시간 운영 체제들은 응용 프로그램이 운영 체제의 간섭 없이 시스템 콜을 효율적으로 사용할 수 있게 하기 위해 커널 모드에서도 동작할 수 있도록 한다.
단일 프로세서 시스템에서, 만약 응용 프로그램이 현재 커널 모드로 동작하고, 인터럽트를 비활성화할 수 있다면, 대개 인터럽트 비활성화야말로 두 개 이상의 태스크가 동시에 공유자원에 접근하는 것을 막아주는 최고의 기법이다. 인터럽트가 비활성화되어 있는 경우, 현재 돌고 있는 태스크는 다른 태스크나 인터럽트가 CPU를 제어할 수 없기 때문에 "배타성"을 띠며, 따라서 임계 구역은 보호 받는다. 태스크가 임계 구역에서 벗어나게 되면, 대기중인 인터럽트가 있다면 실행되도록 인터럽트를 다시 활성화시켜야 한다. 일시적으로 인터럽트를 비활성화하는 것은 임계 구역의 가장 긴 경로가 인터럽트 대기 시간보다 짧은 경우 유효한 전략이다. 그렇지 않다면 이 방법을 통하여 시스템의 최대 인터럽트 대기 시간을 증가시킬 가능성이 있다. 따라서 임계 구역이 단지 몇 개의 명령어로 이루어졌거나, 반복구문을 포함하지 않은 경우 유효하다고 할 수 있다.

세마포어

세마포어는 잠기거나 풀려있다. 잠겨 있을 때 작업들의 대기는 세마포어(가 풀리기)를 기다린다. 세마포어 디자인들이 가지는 문제점들은 잘 알려져 있다: 우선 순위 역전과 교착 상태이다. 우선 순위 역전은 높은 순위의 작업이 낮은 순위의 세마포어를 가지는 작업을 기다리는 상황이다. 대표적인 해결법은 세마포어를 가지는 작업이 최우선 순위가 되도록 하는 것이다. 교착에서는 두 개의 작업이 두 개의 세마포어를 역순으로 잠근다. 이것은 대개 대기열을 구현할 때 면밀하게 설계하거나 또는 floored semaphores(정해진 상황에서 세마포어의 제어권을 높은 순위의 작업에 넘기는)를 추가함으로써 해결된다.

메시지 전달

다른 해결책은 작업들이 서로 메시지를 주고 받게 하는 것이다. 이것 또한 똑같은 문제점들을 안고 있다: 작업이 낮은 우선 순위의 메시지를 수행하느라 in-box에 있는 더 높은 순위의 메시지를 무시할 때 우선 순위 역전이 일어난다. 두 개의 작업이 서로 상대방의 응답을 기다릴 때 교착이 일어난다.
실시간 동작은 세마포어 시스템의 경우보다는 덜 분명하지만, 메시지 기반 시스템들은 자체적으로는 고정적이지 않아 일반적으로 세마포어 시스템들보다는 더 잘 동작한다.

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

인터럽트 핸들러는 실행중인 가장 높은 우선의 태스크 조차도 중단 시킬 수 있으며, 실시간 운영 체제는 스레드 대기시간을 최소화하도록 설계되어 있기 때문에, 인터럽트 핸들러의 기능은 가능한 최소화되기 마련이다.

동적 메모리 할당

실시간 운영 체제의 동적 메모리 할당은 일반 운영 체제보다 엄격한 조건이 요구된다.
먼저, 할당 속도가 중요하다. 표준 메모리 할당 방식은 알맞은 크기의 사용되지 않는 메모리 블록을 찾기 위해서 연결 리스트를 검색하는 것이다. 하지만, 이 방식은 정해진 시간 안에 메모리 할당이 일어나야 하는 실시간 운영 체제에는 맞지 않는다.
또한, 메모리의 공간을 분할하여 사용하 보면 단편화(Fragmentation)가 발생한다. 따라서 메모리 자체는 충분하더라도 메모리를 확보할 수 없어, 프로그램이 멈추는 현상이 발생할 가능성이 있다. 데스크톱 컴퓨터에서는 자주 다시 시동하기 때문에 어느 정도의 단편화가 문제가 되지 않을 수 있다. 그러나 임베디드 시스템은 몇 년 동안 다시 시동하지 않고 동작하는 경우도 있으므로, 단편화가 허용될 수 없다.
간단한 임베디드 시스템에서는 단순한 고정 크기 블록 알고리즘도 잘 동작한다.
좀 더 자세한 내용은 메모리 할당을 참조.

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

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