정의
순환 스케줄링은 hard 데드라인을 갖는 job들의 실행 시각을 설계 시점에 테이블로 확정해 두고, 런타임에는 스케줄러가 그 테이블대로 job을 디스패치하며 hyperperiod마다 테이블을 처음부터 되풀이하는 방식이다.[1]
스케줄링 결정을 실행 전에 모두 끝내 두는 계열의 대표이며, 안전이 걸린 임베디드 시스템에서 오랫동안 지배적인 소프트웨어 구조였다.[2] 분류상의 자리는 실시간 스케줄링 알고리즘 분류에서 다룬다.
테이블과 hyperperiod
테이블은 결정 시각과 그 시각에 실행할 태스크의 쌍을 나열한 것이고, 실행할 주기 태스크가 없는 시각에는 유휴를 뜻하는 값이 들어간다. 테이블은 hyperperiod 안에서 한 번 완전히 소진되고 다시 처음부터 반복되며, hyperperiod는 모든 태스크 주기의 최소공배수다.[3] 태스크 실행은 비선점이라 별도의 실시간 운영체제가 필요 없고 job 디스패치는 함수 호출 하나로 끝난다. 시스템 동작 모드마다 다른 테이블을 두어 모드를 바꿀 수도 있는데, 모드 전환은 hyperperiod 경계에서만 허용된다.[2]
job에 배정하는 프로세서 시간은 그 job의 최대 실행 시간이며, 어떤 job도 배정된 시간을 넘기지 않는 한 테이블은 모든 데드라인을 지킨다. 런타임에는 스케줄러가 하드웨어 타이머를 다음 결정 시각에 만료되도록 걸고 인터럽트를 받아 다음 job을 시작한다.[1] 배정의 근거가 되는 실행 시간 값은 최악 실행 시간에서 다룬다.
프레임 구조
임의의 시각마다 결정을 내리는 테이블은 유연하지만 프로그래머블 타이머에 의존하고 인터럽트가 잦아 스케줄링 오버헤드가 크다. 그래서 hyperperiod를 길이가 같은 프레임으로 나누고 프레임 경계에서만 타이밍을 강제하는 구조를 얹는다. 각 job은 함수로 구현되어 한 프레임 안에 들어가야 하고, 한 프레임에 여러 job이 놓일 수 있으며, hyperperiod당 프레임 수는 hyperperiod를 프레임 크기로 나눈 값이다.[2]
프레임 크기 는 세 제약을 함께 만족해야 한다.[1]
- 선점 없이 한 프레임 안에서 job이 시작하고 끝나야 하므로 이다.
- 테이블의 항목 수를 작게 유지하려면 hyperperiod가 의 배수여야 하고, 이는 적어도 한 태스크의 주기를 가 나눠떨어뜨린다는 것과 같다.
- 데드라인 위반을 데드라인이 도래하는 시점에 검출하려면 모든 태스크의 release와 데드라인 사이에 완전한 프레임 경계가 하나는 있어야 하므로 다.
세 제약을 동시에 만족할 수 없으면 실행 시간이 긴 job을 여러 slice로 쪼개 나눠 배치한다. 프레임 크기 선택, job 분할, 프레임 배치 세 결정은 서로 얽혀 있어 따로 내릴 수 없다.
주기 4에 실행 1인 태스크, 주기 5에 실행 2인 태스크, 주기 10에 실행 1인 태스크를 함께 돌린다면 hyperperiod는 20이고 프레임 크기 2가 세 제약을 모두 만족한다. 이때 테이블은 프레임 열 개짜리가 되고, 세 태스크의 job 열한 개가 그 안에 배치되며 남는 자리는 빈 구간으로 남는다.
장점
- 매우 단순하다. 필요한 것은 테이블 하나뿐이고 동작이 완전히 결정적이라 높은 신뢰도로 검증하고 시험할 수 있다. 프로세스도 스레드도 락도 없으므로 경쟁 상태와 교착이 생기지 않고, 스케줄링 이상 현상도 없다. 주기 태스크가 쓰지 않는 슬롯에서는 aperiodic job을 돌릴 수 있어 aperiodic job이 자연스럽게 낮은 우선순위를 갖는다.[2]
- 스케줄을 오프라인에서 만들기 때문에 job 사이의 복잡한 의존 관계, 통신 지연, 자원 경쟁을 테이블을 짜는 단계에서 함께 고려할 수 있고, 그 결과 교착과 예측 불가능한 지연이 없음을 보장할 수 있다. 완료 시각 지터에 대한 요구가 있으면 그것도 테이블에 담을 수 있다.[1]
- 태스크가 미리 배정된 슬롯에서만 실행되므로 실제로 겪는 지터가 매우 작고, 스케줄링 결정이 오프라인에서 끝나 런타임 오버헤드가 크지 않다.[3]
한계
- 취약하다. 무엇 하나 바뀌면 테이블을 새로 계산해야 하고, 모든 태스크의 release 시각이 고정이어야 하며, 함께 실행될 수 있는 태스크 조합을 전부 미리 분석해야 한다. job을 잘게 쪼개는 일은 어렵고 실수하기 쉽다. 프레임 수가 아주 커질 수 있어 모드 전환 지연이 길어지기도 한다.[2]
- 이용률이 높고 태스크가 많을수록 코드 조각을 타임 슬롯에 끼워 맞추는 일이 시간을 잡아먹는 반복 작업이 된다. 게다가 나중에 태스크 하나만 바뀌어도 특정 마이너 사이클이 넘쳐 타임라인 전체를 다시 짜야 한다.[4]
- 주기·데드라인 제약을 지키도록 동작을 끼워 넣는 문제 자체가 단일 프로세서에서 이미 NP-hard다. 그래서 실무에서는 최적성을 고집하지 않고 휴리스틱으로 테이블을 만든다.[5]
- 태스크 주기 하나가 조금 바뀌기만 해도 프레임 크기와 hyperperiod 값이 달라져 테이블 전체를 다시 설계해야 한다.[3]
- sporadic job은 도착 시각과 실행 시간을 미리 알 수 없어 사전 보장이 불가능하고, 도착 시점에 남은 여유로 수락 여부를 판정하는 수밖에 없다. aperiodic job 처리도 원시적이어서 soft 실시간 계산이 상당히 있으면 응답 시간이 만족스럽지 않다.[1]
테이블을 넘긴 실행
순환 스케줄은 각 job이 배정된 시간을 넘기지 않는다는 전제 위에 서 있다. 한 태스크가 예측한 실행 시간을 넘겼는데 중단되지 않으면 뒤따르는 태스크들이 차례로 밀려 프레임 경계를 넘어가는 도미노 효과가 일어난다.[3]
차량용 표준이 같은 발상을 어떻게 규정하는지는 AUTOSAR OS의 정적 활성화 테이블에서, 실행 시각을 설계 시점에 고정하는 구조 일반은 시간 구동 아키텍처에서 다룬다.