정의
우선순위 기반 스케줄링은 매 순간 활성 job마다 우선순위를 결부시키고, 실행 자격이 있는 job 가운데 우선순위가 가장 높은 것을 골라 프로세서에 올리는 방식이다.[1]
실행 중에 결정을 내리는 온라인 계열의 한 갈래이며, 다른 갈래와의 대비와 분류상의 자리는 실시간 스케줄링 알고리즘 분류에서 다룬다.
동작 규칙
한 job은 도착했고, 데드라인이 아직 지나지 않았고, 실행이 끝나지 않았을 때 활성 상태다. 이 계열의 알고리즘은 대개 work-conserving하다 — 활성 job이 하나라도 있으면 프로세서를 놀리지 않는다. 스케줄링 알고리즘 자체가 스케줄 대상과 같은 프로세서 위에서 도는 만큼 단순하고 효율적이어야 하는데, work-conserving한 알고리즘의 런타임 오버헤드가 그렇지 않은 쪽보다 작은 편이라 온라인으로 결정을 내리는 알고리즘은 대체로 이 성질을 갖는다.[1]
스케줄링 결정은 job의 release나 완료 같은 이벤트가 일어날 때만 내려지므로 이 계열은 이벤트 구동이다. 준비된 job은 하나 이상의 큐에 놓이고, 각 이벤트 시점에 준비된 job 중 우선순위가 가장 높은 것이 실행된다. job을 어느 우선순위 큐에 넣을지 정하는 규칙과 선점을 허용하는지 여부까지 정하면 알고리즘이 완전히 규정된다.[2]
세 부류
우선순위가 얼마나 자유롭게 변할 수 있는지에 따라 세 부류로 나뉘고, 뒤 부류가 앞 부류를 포함한다.[1]
- 정적 우선순위 — 태스크마다 우선순위 하나가 결합되고 그 태스크가 내는 모든 job이 같은 값을 갖는다. 태스크 A가 태스크 B보다 우선순위가 높으면 둘 다 활성 job을 가진 어느 시점에서든 A의 job이 앞선다. rate monotonic이 여기 속한다.
- job 수준 동적 우선순위 — 두 job 사이의 우선순위 관계가 한 번 정해지면 뒤집히지 않는다. 우선순위가 job 단위로 고정되므로 태스크 관점에서는 job마다 값이 달라진다. EDF가 여기 속하며 앞 부류에는 속하지 않는다.
- 완전 동적 우선순위 — 두 job의 상대 우선순위가 언제든 바뀔 수 있다. 최소 여유 시간 우선이 여기 속한다.
단일 프로세서에서는 둘째 부류에 속하는 EDF가 이미 최적이라서 둘째와 셋째 부류의 구분이 잘 강조되지 않는다. 구분이 실질적인 차이를 만드는 것은 프로세서가 여럿인 쪽이다.
최소 여유 시간 우선은 셋째 부류가 왜 필요한지를 보여 준다. 시각 에서 job의 남은 실행 시간은 이고 여유 시간은 인데, 이 값이 실행 도중에도 계속 변하므로 두 job의 순서가 뒤집힐 수 있다. 대신 실행 시간까지 알아야 해서 데드라인만 있으면 되는 EDF보다 요구가 많고, 실제 실행 시간은 입력에 따라 달라지므로 최악값을 써야 한다.[2]
범용 스케줄링과의 관계
실시간이 아닌 시스템에서 쓰이는 스케줄링 알고리즘 대부분도 이 계열이다. FIFO와 LIFO는 release 시각을 우선순위로 삼은 것이고, 실행 시간이 짧은 쪽 또는 긴 쪽을 먼저 실행하는 방식은 실행 시간을 우선순위로 삼은 것이다. 실시간 쪽은 같은 틀에서 데드라인이나 여유 시간을 우선순위의 근거로 바꿔 넣는다.[2]
국소 최적과 전역 최적
우선순위 기반 알고리즘은 매 결정 시점에 국소적으로 최적인 선택을 한다. 자원을 비워 두는 것은 국소적으로 최적이 아니므로 이 알고리즘들은 자원을 의도적으로 놀리지 않는다.[2] 문제는 국소 최적이 전역 최적은 아니라는 점이다.
직관과 어긋나는 결과
우선순위 기반 스케줄링의 결과는 직관과 어긋날 수 있다. 우선순위가 낮은 job을 선점한 탓에 작업 전체의 완료가 오히려 늦어지는 경우가 있으며, 우선순위 배정 규칙이 달라지면 알고리즘의 성질도 크게 달라진다.[2]
우선순위를 어떤 정책으로 배정할지, 그리고 그 배정으로 데드라인이 지켜지는지를 어떻게 판정할지는 고정 우선순위 스케줄링과 스케줄가능성 분석에서 다룬다.