Dynamic priority scheduling

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Dynamic priority scheduling is a type of scheduling algorithm in which the priorities are calculated during the execution of the system. The goal of dynamic priority scheduling is to adapt to dynamically changing progress and form an optimal configuration in self-sustained manner. It can be very hard to produce well-defined policies to achieve the goal depending on the difficulty of a given problem.

Earliest deadline first scheduling and Least slack time scheduling are examples of Dynamic priority scheduling algorithms.

Optimal schedulable utilization[edit]

The idea of real-time scheduling is to confine processor utilization under schedulable utilization of a certain scheduling algorithm, which is scaled from 0 to 1. Higher schedulable utilization means higher utilization of resource and the better the algorithm. In preemptible scheduling, dynamic priority scheduling such as earliest deadline first (EDF) provides the optimal schedulable utilization of 1 in contrast to less than 0.69 with fixed priority scheduling such as rate-monotonic (RM).[1]

In periodic real-time task model, a task's processor utilization is defined as execution time over period. Every set of periodic tasks with total processor utilization less or equal than the schedulable utilization of an algorithm can be feasibly scheduled by that algorithm. Unlike fixed priority, dynamic priority scheduling could dynamically prioritize task deadlines achieving optimal schedulable utilization in the preemtible case.

References[edit]

  1. ^ Krishna, C.M. and Shin, K.G. Real-time Systems, ISBN 9780070570436, 1997