고정 우선순위 스케줄링(fixed-priority scheduling)은 태스크마다 우선순위를 한 번 정해 두고, 우선순위가 더 높은 태스크의 요청이 오면 실행 중인 태스크를 곧바로 멈추고 그 태스크를 실행하는 선점형 스케줄링이다. 한 태스크의 요청은 모두 같은 우선순위를 가지며, 요청마다 우선순위가 바뀔 수 있는 동적 스케줄링과 다르다. 이런 알고리즘을 정하는 일은 태스크에 우선순위를 배정하는 방법을 정하는 일과 같다.[1]
우선순위 배정
- RM: 주기가 짧은, 곧 요청 빈도가 높은 태스크일수록 높은 우선순위를 준다.[1]
- DM(Deadline Monotonic): 상대 마감 시한이 짧은 태스크일수록 높은 우선순위를 준다.[2]
모든 태스크의 상대 마감 시한이 주기와 같으면 DM은 RM과 같은 배정이 된다. 단일 프로세서에서 주기 태스크의 마감 시한이 주기 이하이고, 모든 태스크가 같은 시각에 첫 요청을 하면, DM은 고정 우선순위 배정 가운데 최적이다. 어떤 고정 우선순위 배정으로 스케줄할 수 있는 태스크 집합은 DM으로도 스케줄할 수 있다.[2]
태스크의 첫 요청 시각이 서로 달라 모든 태스크가 함께 요청하는 순간이 없으면 DM은 최적이 아니다. 이때는 Audsley의 최적 우선순위 배정 알고리즘을 쓸 수 있다. 태스크가 주기적이고 실행 시간이 유한하며 서로 영향을 주지 않고 스스로 멈추지 않으면, 이 알고리즘은 가장 낮은 우선순위부터 차례로, 그 자리에서 마감 시한을 지키는 태스크를 하나 골라 배정한다. 어느 자리에서든 그런 태스크가 없으면 가능한 배정이 없다고 판정한다. 태스크가 개이면 아직 배정되지 않은 태스크가 개 남은 자리에서 최대 개를 검사하므로, 마감 시한을 지키는지 검사하는 횟수는 모두 아래를 넘지 않는다.[3]
단일 프로세서에서 태스크마다 서로 다른 고정 우선순위를 주어 선점 스케줄하고, 태스크의 최소 도착 간격을 주기로 두며, 마감 시한이 주기보다 길 수 있다고 하자. 이때도 우선순위를 낮춰도 최악 응답 시간이 줄지 않는 분석과 함께 쓰면 Audsley의 알고리즘은 최적이다.[4]
Audsley의 알고리즘이 어떤 스케줄 가능성 검사와 함께 최적 배정을 내려면, 그 검사가 아래 세 조건을 지켜야 하고 세 조건을 지키면 충분하다.[5]
- 한 태스크가 스케줄 가능한지는 더 높은 우선순위 태스크들 사이의 상대 우선순위 순서에 좌우되지 않는다.
- 더 낮은 우선순위 태스크들 사이의 상대 우선순위 순서에도 좌우되지 않는다.
- 우선순위가 이웃한 두 태스크를 맞바꿀 때, 높은 자리로 올라간 태스크는 낮은 자리에서 스케줄 가능했으면 올라가서도 스케줄 가능하다.[5]
태스크에 release jitter가 있고 마감 시한이 주기 이하이면, 마감 시한 에서 release jitter 를 뺀 값이 작은 태스크일수록 높은 우선순위를 주는 (D−J)-monotonic 배정은 고정 우선순위 배정 가운데 최적이다. 어떤 고정 우선순위 배정으로 스케줄할 수 있는 태스크 집합은 (D−J)-monotonic으로도 스케줄할 수 있다.[6]
배정에 따라 결과가 갈린다. 주기 , 실행 시간 인 두 태스크가 , , , 이면, RM대로 태스크 1에 높은 우선순위를 줄 때는 모든 마감 시한을 지킨다. 태스크 2에 높은 우선순위를 주면 이어야 하므로 태스크 1이 마감 시한을 놓친다.[1]
태스크의 중요도만으로 우선순위를 정하면, 다른 배정으로는 모든 마감 시한을 지키는 태스크 집합에서도 마감 시한을 놓칠 수 있다. 주기 100, 실행 시간 10인 태스크가 주기 10, 실행 시간 1인 태스크보다 중요해 높은 우선순위를 받으면, 두 태스크가 함께 시작하고 첫 마감 시한이 각각 100과 10일 때 이용률이 0.2뿐인데도 뒤 태스크가 마감 시한을 놓친다. RM대로 주기가 짧은 태스크에 높은 우선순위를 주면 두 태스크 모두 마감 시한을 지킨다.[7]
스케줄 가능성 검사
태스크가 서로 독립이면, 한 태스크가 받는 간섭은 그보다 우선순위가 높은 태스크의 집합으로 정해지고 그 집합 안의 순서와는 상관없다. 주기 태스크의 마감 시한이 주기 이하이고 모두 같은 시각에 시작하면, 응답 시간 분석은 DM뿐 아니라 어떤 고정 우선순위 배정에도 쓸 수 있다.[3]
태스크가 공유 자원을 상호 배제로 쓰면, 우선순위가 높은 태스크가 그 자원을 잡은 낮은 우선순위 태스크 때문에 블로킹될 수 있다.[3] 이 블로킹 시간을 분석에 더하는 방법은 응답 시간 분석에서 다룬다.
우선순위 단계 수
Lehoczky와 Sha는 1986년에, 주기를 일정한 비율의 격자로 우선순위 단계에 대응시키면 우선순위 단계가 256개만 있어도 단계 수에 제한이 없을 때와 거의 같은 스케줄 가능성을 얻는다는 것을 보였다. 256단계는 1바이트로 나타낼 수 있다.[8]
단일 프로세서에서 주기 태스크의 우선순위 단계 수 이 태스크 수 보다 적어 여러 태스크가 한 단계를 함께 쓰고, 같은 단계의 요청은 먼저 온 순서로 처리한다고 하자. 그러면 주어진 우선순위 배정은, 모든 태스크가 같은 시각에 첫 요청을 하고 같은 단계의 태스크는 상대 마감 시한이 긴 것부터 처리된다고 둘 때 모든 태스크의 첫 요청이 마감 시한을 지키면 유효하다. 상대 마감 시한이 짧은 태스크부터 차례로, 시간 수요 분석(time-demand analysis)으로 그 단계가 마감 시한을 지키는 동안은 같은 단계에 넣고 지키지 못하게 되면 다음 단계로 넘기는 배정을 DM-LPL(Deadline-Monotonic-with-Limited-Priority-Level)이라 한다. DM-LPL은 이런 시스템에서 최적이어서, 우선순위 단계가 개인 프로세서 하나에서 feasible한 태스크 집합은 DM-LPL로 스케줄할 수 있다.[2]
POSIX
POSIX.1-2024는 스레드를 우선순위별 목록에 두고, 정책과 상관없이 우선순위가 가장 높은 비어 있지 않은 목록의 맨 앞 스레드를 실행하게 한다. SCHED_FIFO 정책에서는 같은 우선순위의 스레드를 목록에서 기다린 순서대로 고르고, 선점된 스레드는 자기 우선순위 목록의 맨 앞으로 간다.[9]
근거 문서에 따르면, 스레드마다 옮겨 다니지 않는 우선순위(non-migrating priority)를 두고 늘 실행 가능한 스레드가 있는 가장 높은 우선순위 대기열의 맨 앞 스레드를 고르는 정책은 실시간 환경에 알맞을 수 있다. 가장 큰 까닭은 이 정책이 결정적이라는 것으로, 우선순위가 가장 높은 스레드가 늘 실행되고 같은 우선순위에서는 실행 가능해진 지 가장 오래된 스레드가 먼저 실행된다.[10]
EDF와의 차이
태스크가 주기적이고 서로 독립이며, 실행 시간이 일정하고 마감 시한이 다음 요청 시각이며 선점할 수 있으면, 요청마다 현재 요청의 마감 시한으로 우선순위를 정하는 EDF는 이용률 가 일 때, 그리고 그때만 스케줄할 수 있다. 같은 가정에서 고정 우선순위로 늘 스케줄되는 이용률의 최소 상한은 이보다 낮고, 그 식은 RM에서 다룬다.[1]