Hardware Reference
In-Depth Information
activation
termination
dispatching
Execution
scheduling
preemption
Figure 2.1
Queue of ready tasks waiting for execution.
In many operating systems that allow dynamic task activation, the running task can
be interrupted at any point, so that a more important task that arrives in the system
can immediately gain the processor and does not need to wait in the ready queue. In
this case, the running task is interrupted and inserted in the ready queue, while the
CPU is assigned to the most important ready task that just arrived. The operation of
suspending the running task and inserting it into the ready queue is called
preemption
.
Figure 2.1 schematically illustrates the concepts presented above. In dynamic real-
time systems, preemption is important for three reasons [SZ92]:
Tasks performing exception handling may need to preempt existing tasks so that
responses to exceptions may be issued in a timely fashion.
When tasks have different levels of criticality (expressing task importance), pre-
emption permits executing the most critical tasks, as soon as they arrive.
Preemptive scheduling typically allows higher efficiency, in the sense that it al-
lows executing a real-time task sets with higher processor utilization.
On the other hand, preemption destroys program locality and introduces a runtime
overhead that inflates the execution time of tasks. As a consequence, limiting preemp-
tions in real-time schedules can have beneficial effects in terms of schedulability. This
issue will be investigated in Chapter 8.
Given a set of tasks,
J
=
,a
schedule
is an assignment of tasks to the
processor, so that each task is executed until completion. More formally, a schedule
can be defined as a function
σ
:
{
J
1
,...,J
n
}
+
+
,
R
→
N
such that
∀
t
∈
R
∃
t
1
,t
2
such that
[
t
1
,t
2
)
σ
(
t
)=
σ
(
t
). In other words,
σ
(
t
) is an integer step
function and
σ
(
t
)=
k
, with
k>
0, means that task
J
k
is executing at time
t
, while
σ
(
t
)=0means that the CPU is idle. Figure 2.2 shows an example of schedule
obtained by executing three tasks:
J
1
,
J
2
,
J
3
.
t
∈
t
∈
[
t
1
,t
2
) and
∀
Search WWH ::
Custom Search