정의
실시간 스케줄링 참조 모델은 스케줄링 문제를 워크로드 모델·자원 모델·스케줄링 알고리즘으로 나누어 기술하는 추상 틀이다. 이 분야의 결과들은 같은 문제에서 축을 하나씩 갈아 끼우며 쌓여 왔다.[1]
실시간 시스템이 데드라인을 지키는지 판정할 때 응용이 무엇을 계산하는지까지 들여다볼 필요는 없다. 시간 제약을 hard로 걸어 두면 시스템의 시간적 정확성은 최악 실행 시간이나 최소 도착 간격처럼 응용과 무관한 소수의 파라미터만으로 따질 수 있고, 그래서 응용마다 새로 세우지 않아도 되는 일반적인 스케줄링 법칙을 이끌어 낼 수 있다.[1] 참조 모델은 그 파라미터가 무엇이고 무엇을 가정하는지를 고정해 주는 자리이며, 용어와 표기를 하나로 맞춰 서로 다른 연구의 결과를 견줄 수 있게 하는 실용적인 몫도 함께 진다.[2]
세 축
워크로드 모델은 처리해야 할 일을 기술한다. 응용은 n개의 태스크로 이뤄진 정적 집합이고, 각 태스크는 잠재적으로 무한한 job의 열을 낳는다.[2] 태스크가 job을 언제 내놓는지는 주기 태스크 모델이, job이 언제까지 끝나야 하는지는 데드라인이, 한 job이 얼마나 오래 도는지는 최악 실행 시간이 맡는다.
자원 모델은 그 일을 처리할 하드웨어를 기술한다 — 프로세서가 몇 개이고 서로 같은지, 태스크들이 프로세서 말고 무엇을 더 공유하는지가 여기 들어간다.
스케줄링 알고리즘은 어느 시점에 어느 job을 실행할지 정하는 규칙이다. 연구 문헌은 태스크 모델·플랫폼 모델·상호작용 모델을 갈아 끼우며 같은 문제의 변형들을 다뤄 왔다.[1] 알고리즘 쪽의 갈래는 실시간 스케줄링 알고리즘 분류에서 다룬다.
자원 모델
프로세서가 여럿인 시스템은 셋으로 나뉜다. 프로세서가 서로 다른 heterogeneous, 완전히 같은 homogeneous, 속도 배율만 다른 uniform이다.[2] 고전적인 단일 프로세서 스케줄링 이론은 이보다 훨씬 좁게 잡는다 — 프로세서 하나를 태스크들이 공유하고, 더 높은 우선순위의 요청이 들어오면 실행 중인 태스크를 즉시 뺏는다고 놓는다.[3]
공유 자원도 자원 모델의 일부다. 대부분의 연구는 태스크가 서로 독립이어서 프로세서를 두고 겨루는 것 말고는 서로를 막지 않는다고 가정하고, 상호 배제가 필요한 자원이 들어오면 그 자원을 쥔 태스크 때문에 막히는 시간을 따로 모델에 넣는다. 그 시간이 어디서 생기는지는 임계 구역에서 다룬다.
선점 방식
스케줄러가 실행 중인 태스크를 언제 뺏을 수 있느냐에 따라 세 방식으로 갈린다. preemptive는 더 높은 우선순위 태스크가 임의 시점에 뺏을 수 있고, non-preemptive는 한 번 시작한 태스크가 끝날 때까지 뺏기지 않으며, cooperative는 태스크 안에 미리 정해 둔 스케줄링 지점에서만 뺏긴다 — 이때 태스크의 실행은 선점 불가 구간들의 연속이 된다.[2]
범용 운영체제에도 같은 대비가 있다. 타이머 인터럽트로 주기적으로 제어를 되찾는 비협조적 방식이 있고, 프로세스가 시스템 콜을 부를 때까지 기다리는 협조적 방식이 있다 — 후자에서 무한 루프에 빠진 프로세스를 멈출 방법은 재부팅뿐이다.[4]
컨텍스트 스위치
컨텍스트 스위치는 지금 도는 실행 흐름의 범용 레지스터와 프로그램 카운터, 커널 스택 포인터를 저장하고 다음 실행 흐름의 것을 복원하는 저수준 코드다. 스택까지 바꿔 끼우므로 커널은 한 실행 흐름의 문맥으로 들어갔다가 다른 실행 흐름의 문맥으로 빠져나온다. 비용은 0이 아니어서 시스템 콜 비용과 함께 측정 도구로 재는 대상이다.[4]
스케줄링 이론은 보통 선점과 스케줄러 실행에 드는 비용을 무시하거나 각 태스크의 최악 실행 시간에 이미 흡수시켰다고 가정하고, 이 오버헤드가 실제로 미치는 영향은 별도의 실증 연구 주제로 다룬다.[2]
스케줄과 스케줄러
스케줄러는 지금 도는 실행 흐름을 그대로 둘지 다른 것으로 바꿀지 결정하는 운영체제의 부분이고, 컨텍스트 스위치는 그 결정을 실행에 옮기는 수단이다.[4] 결정이 시간 축 위에 쌓인 결과가 스케줄이다.
모델이 갖춰지면 던질 수 있는 질문도 정해진다. 모든 데드라인을 지키는 스케줄이 존재하는가, 그리고 지정된 스케줄러가 실행 중에 실제로 그런 스케줄을 만들어 내는가다.[1] 두 질문을 판정하는 절차는 스케줄가능성 분석에서 다룬다.