ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.06.2025
Просмотров: 4222
Скачиваний: 0
Scheduling
Using square brackets to denote the list of ready tasks and curly brackets for the list of all blocked processes, the scheduled tasks look as follows:
t1 |
[t2, t3] {} |
o t1 is being blocked |
|
t2 |
[t3] |
{t1} |
|
t3 |
[t2] |
{t1} |
|
t2 |
[t3] |
{t1} |
o t3 unblocks t1 |
t3 |
[t2, t1] {} |
||
t2 |
[t1, t3] {} |
t1 |
[t3, t2] {} |
t3 |
[t2, t1] {} |
... |
Whenever a task is put back into the “ready” list (either from running or from blocked), it will be put at the end of the list of all waiting tasks with the same priority. So if all tasks have the same priority, the new “ready” task will go to the end of the complete list.
Priorities The situation gets more complex if different priorities are involved. Tasks can be started with priorities 1 (lowest) to 8 (highest). The simplest priority model (not used in RoBIOS) is static priorities. In this model, a new “ready” task will follow after the last task with the same priority and before all tasks with a lower priority. Scheduling remains simple, since only a single waiting list has to be maintained. However, “starvation” of tasks can occur, as shown in the following example.
Starvation Assuming tasks tA and tB have the higher priority 2, and tasks ta and tb have the lower priority 1, then in the following sequence tasks ta and tb are being kept from executing (starvation), unless tA and tB are both blocked by some events.
Dynamic
priorities
tA |
[tB, ta, tb] {} |
||
tB |
[tA, ta, tb] {} |
o tA blocked |
|
tA |
[tB, ta, tb] |
{} |
|
tB |
[tA, ta, tb] |
{tA} |
o tB blocked |
ta |
[tb] |
{tA, tB} |
|
... |
|||
For these reasons, RoBIOS has implemented the more complex dynamic priority model. The scheduler maintains eight distinct “ready” waiting lists, one for each priority. After spawning, tasks are entered in the “ready” list matching their priority and each queue for itself implements the “round-robin” principle shown before. So the scheduler only has to determine which queue to select next.
Each queue (not task) is assigned a static priority (1..8) and a dynamic priority, which is initialized with twice the static priority times the number of “ready” tasks in this queue. This factor is required to guarantee fair scheduling for different queue lengths (see below). Whenever a task from a “ready” list is executed, then the dynamic priority of this queue is decremented by 1. Only after the dynamic priorities of all queues have been reduced to zero are the dynamic queue priorities reset to their original values.
79
5 Multitasking
The scheduler now simply selects the next task to be executed from the (non-empty) “ready” queue with the highest dynamic priority. If there are no eligible tasks left in any “ready” queue, the multitasking system terminates and continues with the calling main program. This model prevents starvation and still gives tasks with higher priorities more frequent time slices for execution. See the example below with three priorities, with static priorities shown on the right, dynamic priorities on the left. The highest dynamic priority after decrementing and the task to be selected for the next time slice are printed in bold type:
– |
6 |
[tA]3 |
8 |
[ta,tb]2 |
|
4 |
[tx,ty]1 |
|
ta |
6 |
[tA]3 |
7 |
[tb]2 |
|
4 |
[tx,ty]1 |
|
tb |
6 |
[tA]3 |
6 |
[ta]2 |
|
4 |
[tx,ty]1 |
|
t |
5 |
[] |
A |
6 |
[ta,tb]23 |
4 |
[tx,ty]1 |
|
ta |
5 |
[tA]3 |
5 |
[tb]2 |
|
4 |
[tx,ty]1 |
|
... |
||
ta |
3 |
[tA]3 |
3 |
[t ] |
|
4 |
[tx,tyb]12 |
|
tx |
3 |
[tA]3 |
3 |
[ta,tb]2 |
|
3 |
[ty]1 |
...
(2 · priority · number_of_tasks = 2 · 3 · 1 = 6) (2 · 2 · 2 = 8)
(2 · 1 · 2 = 4)
5.5 Interrupts and Timer-Activated Tasks
A different way of designing a concurrent application is to use interrupts, which can be triggered by external devices or by a built-in timer. Both are very important techniques; external interrupts can be used for reacting to external sensors, such as counting ticks from a shaft encoder, while timer interrupts can be used for implementing periodically repeating tasks with fixed time frame, such as motor control routines.
The event of an external interrupt signal will stop the currently executing task and instead execute a so-called “interrupt service routine” (ISR). As a
80
Interrupts and Timer-Activated Tasks
general rule, ISRs should have a short duration and are required to clean up any stack changes they performed, in order not to interfere with the foreground task. Initialization of ISRs often requires assembly commands, since interrupt lines are directly linked to the CPU and are therefore machine-dependent (Figure 5.2).
data bus
Interrupt
CPU |
Ext |
|||||||||||||||||
CS / enable
GND
Figure 5.2: Interrupt generation from external device
Somewhat more general are interrupts activated by software instead of external hardware. Most important among software interrupts are timer interrupts, which occur at regular time intervals.
In the RoBIOS operating system, we have implemented a general purpose 100Hz timing interrupt. User programs can attach or detach up to 16 timer interrupt ISRs at a rate between 100Hz (0.01s) and 4.7 10-8Hz (248.6 days), by specifying an integer frequency divider. This is achieved with the following operations:
TimerHandle |
OSAttachTimer(int scale, TimerFnc function); |
int |
OSDetachTimer(TimerHandle handle); |
The timing scale parameter (range 1..100) is used to divide the 100Hz timer and thereby specifies the number of timer calls per second (1 for 100Hz, 100 for 1Hz). Parameter TimerFct is simply the name of a function without parameters or return value (void).
An application program can now implement a background task, for example a PID motor controller (see Section 4.2), which will be executed several times per second. Although activation of an ISR is handled in the same way as preemptive multitasking (see Section 5.2), an ISR itself will not be preempted, but will keep processor control until it terminates. This is one of the reasons why an ISR should be rather short in time. It is also obvious that the execution time of an ISR (or the sum of all ISR execution times in the case of multiple ISRs) must not exceed the time interval between two timer interrupts, or regular activations will not be possible.
The example in Program 5.7 shows the timer routine and the corresponding main program. The main program initializes the timer interrupt to once every second. While the foreground task prints consecutive numbers to the screen, the background task generates an acoustic signal once every second.
81
5 Multitasking
Program 5.7: Timer-activated example
1 |
void timer() |
|
2 |
{ |
AUBeep(); /* background task */ |
3 |
} |
|
1int main()
2{ TimerHandle t; int i=0;
3t = OSAttachTimer(100, timer);
4/* foreground task: loop until key press */
5while (!KEYRead()) LCDPrintf("%d\n", i++);
6OSDetachTimer(t);
7return 0;
8}
5.6References
BRÄUNL, T. Parallel Programming - An Introduction, Prentice Hall, Englewood Cliffs NJ, 1993
BRINCH HANSEN, P. The Architecture of Concurrent Programs, Prentice Hall, Englewood Cliffs NJ, 1977
BRINCH HANSEN, P. (Ed.) Classic Operating Systems, Springer-Verlag, Berlin, 2001
DIJKSTRA, E. Communicating Sequential Processes, Technical Report EWD123, Technical University Eindhoven, 1965
HOARE, C.A.R. Communicating sequential processes, Communications of the ACM, vol. 17, no. 10, Oct. 1974, pp. 549-557 (9)
82
WIRELESS |
6 |
|
COMMUNICATION |
||
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
||
|
.. . . . . . . . |
||
There are a number of tasks where a self-configuring network based on wireless communication is helpful for a group of autonomous mobile robots or a single robot and a host computer:
1.To allow robots to communicate with each other
For example, sharing sensor data or cooperating on a common task or devising a shared plan.
2.To remote-control one or several robots
For example, giving low-level driving commands or specifying highlevel goals to be achieved.
3.To monitor robot sensor data
For example, displaying camera data from one or more robots or recording a robot's distance sensor data over time.
4.To run a robot with off-line processing
For example, combining the two previous points, each sensor data packet is sent to a host where all computation takes place, the resulting driving commands being relayed back to the robot.
5.To create a monitoring console for single or multiple robots
For example, monitoring each robot’s position, orientation, and status in a multi-robot scenario in a common environment. This will allow a postmortem analysis of a robot team’s performance and effectiveness for a particular task.
The network needs to be self-configuring. This means there will be no fixed or pre-determined master node. Each agent can take on the role of master. Each agent must be able to sense the presence of another agent and establish a communication link. New incoming agents must be detected and integrated in the network, while exiting agents will be deleted from it. A special error protocol is required because of the high error rate of mobile wireless data exchange. Further details of this project can be found in [Bräunl, Wilke 2001].
8383