[Home] [Prev] [Next] [Index]

D.2 Priority Scheduling

D.2 Priority Scheduling

1
[This clause describes the rules that determine which task is selected for execution when more than one task is ready (see 9.2). The rules have two parts: the task dispatching model (see D.2.1), and a specific task dispatching policy (see D.2.2).]

D.2.1 The Task Dispatching Model

1
[The task dispatching model specifies preemptive scheduling, based on conceptual priority-ordered ready queues.]

Dynamic Semantics

2
A task runs (that is, it becomes a running task) only when it is ready (see 9.2) and the execution resources required by that task are available. Processors are allocated to tasks based on each task's active priority.

3
It is implementation defined whether, on a multiprocessor, a task that is waiting for access to a protected object keeps its processor busy.

3.a
Implementation defined:  Whether, on a multiprocessor, a task that is waiting for access to a protected object keeps its processor busy.

4
Task dispatching is the process by which one ready task is selected for execution on a processor.  This selection is done at certain points during the execution of a task called task dispatching points. A task reaches a task dispatching point whenever it becomes blocked, and whenever it becomes ready. In addition, the completion of an accept_statement (see 9.5.2), and task termination are task dispatching points for the executing task. [Other task dispatching points are defined throughout this Annex.]

4.a
Ramification: On multiprocessor systems, more than one task can be chosen, at the same time, for execution on more than one processor, as explained below.

5
Task dispatching policies are specified in terms of conceptual ready queues, task states, and task preemption. A ready queue is an ordered list of ready tasks. The first position in a queue is called the head of the queue, and the last position is called the tail of the queue. A task is ready if it is in a ready queue, or if it is running. Each processor has one ready queue for each priority value.  At any instant, each ready queue of a processor contains exactly the set of tasks of that priority that are ready for execution on that processor, but are not running on any processor; that is, those tasks that are ready, are not running on any processor, and can be executed using that processor and other available resources. A task can be on the ready queues of more than one processor.

5.a
Discussion:  The core language defines a ready task as one that is not blocked.  Here we refine this definition and talk about ready queues.

6
Each processor also has one running task, which is the task currently being executed by that processor. Whenever a task running on a processor reaches a task dispatching point, one task is selected to run on that processor. The task selected is the one at the head of the highest priority nonempty ready queue; this task is then removed from all ready queues to which it belongs.

6.a
Discussion:  There is always at least one task to run, if we count the idle task.

7
A preemptible resource is a resource that while allocated to one task can be allocated (temporarily) to another instead. Processors are preemptible resources. Access to a protected object (see 9.5.1) is a nonpreemptible resource.

7.a
Reason: A processor that is executing a task is available to execute tasks of higher priority, within the set of tasks that that processor is able to execute.  Write access to a protected object, on the other hand, cannot be granted to a new task before the old task has released it.

When a higher-priority task is dispatched to the processor, and the previously running task is placed on the appropriate ready queue, the latter task is said to be preempted.

8
A new running task is also selected whenever there is a nonempty ready queue with a higher priority than the priority of the running task, or when the task dispatching policy requires a running task to go back to a ready queue. [These are also task dispatching points.]

8.a
Ramification: Thus, when a task becomes ready, this is a task dispatching point for all running tasks of lower priority.

Implementation Permissions

9
An implementation is allowed to define additional resources as execution resources, and to define the corresponding allocation policies for them. Such resources may have an implementation defined effect on task dispatching (see D.2.2).

9.a
Implementation defined:  The affect of implementation defined execution resources on task dispatching.

10
An implementation may place implementation-defined restrictions on tasks whose active priority is in the Interrupt_Priority range.

10.a
Ramification: For example, on some operating systems, it might be necessary to disallow them altogether. This permission applies to tasks whose priority is set to interrupt level for any reason: via a pragma, via a call to Dynamic_Priorities.Set_Priority, or via priority inheritance.

NOTES

11 7
Section 9 specifies under which circumstances a task becomes ready. The ready state is affected by the rules for task activation and termination, delay statements, and entry calls. When a task is not ready, it is said to be blocked.

12 8
An example of a possible implementation-defined execution resource is a page of physical memory, which needs to be loaded with a particular page of virtual memory before a task can continue execution.

13 9
The ready queues are purely conceptual; there is no requirement that such lists physically exist in an implementation.

14 10
While a task is running, it is not on any ready queue.  Any time the task that is running on a processor is added to a ready queue, a new running task is selected for that processor.

15 11
In a multiprocessor system, a task can be on the ready queues of more than one processor.  At the extreme, if several processors share the same set of ready tasks, the contents of their ready queues is identical, and so they can be viewed as sharing one ready queue, and can be implemented that way. [Thus, the dispatching model covers multiprocessors where dispatching is implemented using a single ready queue, as well as those with separate dispatching domains.]

16 12
The priority of a task is determined by rules specified in this subclause, and under D.1, "Task Priorities", D.3, "Priority Ceiling Locking", and D.5, "Dynamic Priorities".

D.2.2 The Standard Task Dispatching Policy

Syntax

1
The form of a pragma Task_Dispatching_Policy is as follows:

2
pragma Task_Dispatching_Policy(policy_identifier );

Legality Rules

3
The policy_identifier shall either be FIFO_Within_Priorities or an implementation-defined identifier.

3.a
Implementation defined:  Implementation-defined policy_identifiers allowed in a pragma Task_Dispatching_Policy.

Post-Compilation Rules

4
A Task_Dispatching_Policy pragma is a configuration pragma.

5
If the FIFO_Within_Priorities policy is specified for a partition, then the Ceiling_Locking policy (see D.3) shall also be specified for the partition.

Dynamic Semantics

6
[A task dispatching policy specifies the details of task dispatching that are not covered by the basic task dispatching model. These rules govern when tasks are inserted into and deleted from the ready queues, and whether a task is inserted at the head or the tail of the queue for its active priority.] The task dispatching policy is specified by a Task_Dispatching_Policy configuration pragma. If no such pragma appears in any of the program units comprising a partition, the task dispatching policy for that partition is unspecified.

7
The language defines only one task dispatching policy, FIFO_Within_Priorities; when this policy is in effect, modifications to the ready queues occur only as follows:

8 ·
When a blocked task becomes ready, it is added at the tail of the ready queue for its active priority.

9 ·
When the active priority of a ready task that is not running changes, or the setting of its base priority takes effect, the task is removed from the ready queue for its old active priority and is added at the tail of the ready queue for its new active priority, except in the case where the active priority is lowered due to the loss of inherited priority, in which case the task is added at the head of the ready queue for its new active priority.

10 ·
When the setting of the base priority of a running task takes effect, the task is added to the tail of the ready queue for its active priority.

11 ·
When a task executes a delay_statement that does not result in blocking, it is added to the tail of the ready queue for its active priority.

11.a
Ramification: If the delay does result in blocking, the task moves to the "delay queue", not to the ready queue.

12
Each of the events specified above is a task dispatching point (see D.2.1).

13
In addition, when a task is preempted, it is added at the head of the ready queue for its active priority.

Documentation Requirements

14
Priority inversion is the duration for which a task remains at the head of the highest priority ready queue while the processor executes a lower priority task.  The implementation shall document:

15 ·
The maximum priority inversion a user task can experience due to activity of the implementation (on behalf of lower priority tasks), and

16 ·
whether execution of a task can be preempted by the implementation processing of delay expirations for lower priority tasks, and if so, for how long.

16.a
Implementation defined:  Implementation-defined aspects of priority inversion.

Implementation Permissions

17
Implementations are allowed to define other task dispatching policies, but need not support more than one such policy per partition.

18
[For optimization purposes, ] an implementation may alter the points at which task dispatching occurs, in an implementation defined manner. However, a delay_statement always corresponds to at least one task dispatching point.

18.a
Implementation defined:  Implementation defined task dispatching.

NOTES

19 13
If the active priority of a running task is lowered due to loss of inherited priority (as it is on completion of a protected operation) and there is a ready task of the same active priority that is not running, the running task continues to run (provided that there is no higher priority task).

20 14
The setting of a task's base priority as a result of a call to Set_Priority does not always take effect immediately when Set_Priority is called.  The effect of setting the task's base priority is deferred while the affected task performs a protected action.

21 15
Setting the base priority of a ready task causes the task to move to the end of the queue for its active priority, regardless of whether the active priority of the task actually changes.



[Home] [Prev] [Next] [Index]

documentation@rational.com
Copyright © 1993-1998, Rational Software Corporation.   All rights reserved.