7.1.2   Challenges in Analyzing Real-Time Systems

The challenges in finding workable solutions for real-time scheduling problems
can be seen in more than 30 years of real-time systems research. Unfortunately
most important problems in real-time scheduling require either excessive practical
constraints to be solved or are NP-complete or NP-hard. Here is a sampling from
the literature as summarized in [Stankovic95].

1. When there are mutual exclusion constraints, it is impossible to find a
   totally on-line optimal run-time scheduler.
2. The problem of deciding whether it is possible to schedule a set of periodic
   processes that use semaphores only to enforce mutual exclusion is NP-hard.
3. The multiprocessor scheduling problem with two processors, no resources,
   arbitrary partial-order relations, and every task having unit computation
   time is polynomial. A partial-order relation indicates that any process can
   call itself (reflexivity), if process A calls process B, then the reverse is not
   possible (antisymmetry), and if process A calls process B and process B
   calls process C, than process A can call process C (transitivity).
4. The multiprocessor scheduling problem with two processors, no resources,
   independent tasks, and arbitrary computation times is NP-complete.
5. The multiprocessor scheduling problem with two processors, no resources,
   independent tasks, arbitrary partial order, and task computation times of
   either 1 or 2 units of time is NP-complete.
6. The multiprocessor scheduling problem with two processors, one resource,
   a forest partial order (partial order on each processor), and each computation
   time of every task equal to 1 is NP-complete.
7. The multiprocessor scheduling problem with three or more processors, one
   resource, all independent tasks, and each computation time of every task
   equal to 1 is NP-complete.
8. Earliest deadline scheduling is not optimal in the multiprocessing case.
9. For two or more processors, no deadline scheduling algorithm can be optimal
   without complete a priori knowledge of deadlines, computation times,
   and task start times,

It turns out that most multiprocessor scheduling problem are in NP, but for deterministic
scheduling this is not a major problem because a polynomial scheduling algorithm can be
used to develop an optimal schedule if the specific problem is not NP-complete [Stankovic95].
In these cases, alternative, off-line heuristic search techniques can be used. These off-line
techniques usually only need to find feasible schedules, not optimal ones. But this is what
engineers do when workable theories do not exist – engineering judgment must prevail.