BASIC CONCEPTS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 34

scheduling

activation termination

READY RUN

preemption

signal wait on

free resource busy resource

WAITING

Figure 2.13 Waiting state caused by resource constraints.

A task waiting for an exclusive resource is said to be blocked on that resource. All
tasks blocked on the same resource are kept in a queue associated with the semaphore
protecting the resource. When a running task executes a wait primitive on a locked
semaphore, it enters a waiting state, until another task executes a signal primitive that
unlocks the semaphore. Note that when a task leaves the waiting state, it does not
go in the running state, but in the ready state, so that the CPU can be assigned to the
highest-priority task by the scheduling algorithm. The state transition diagram relative
to the situation described above is shown in Figure 2.13.

2.3 DEFINITION OF SCHEDULING PROBLEMS

In general, to define a scheduling problem we need to specify three sets: a set of n
tasks Γ= { τ 1 ,τ 2 ,...,τ n } , a set of m processors P = { P 1 ,P 2 ,...,P m } and a set of

s types of resources R = . Moreover, precedence relations among

tasks can be specified through a directed acyclic graph, and timing constraints can
be associated with each task. In this context, scheduling means assigning processors
from P and resources from R to tasks from Γ in order to complete all tasks under the
specified constraints [B + 93]. This problem, in its general form, has been shown to be
NP-complete [GJ79] and hence computationally intractable.

{ R 1 ,R 2 ,...,R s }

Indeed, the complexity of scheduling algorithms is of high relevance in dynamic real-
time systems, where scheduling decisions must be taken on line during task execution.
A polynomial algorithm is one whose time complexity grows as a polynomial function
p of the input length n of an instance. The complexity of such algorithms is denoted by
O ( p ( n )). Each algorithm whose complexity function cannot be bounded in that way
is called an exponential time algorithm . In particular, NP is the class of all decision
problems that can be solved in polynomial time by a non deterministic Turing machine.