ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.06.2025
Просмотров: 4226
Скачиваний: 0
Preemptive Multitasking
depth of subroutines (for example recursion) in the task. Secondly, each task is switched to the mode “ready”. Thirdly and finally, the main program relinquishes control to one of the parallel tasks by calling OSReschedule itself. This will activate one of the parallel tasks, which will take turns until they both terminate themselves. At that point in time – and also in the case that all parallel processes are blocked, i.e. a “deadlock” has occurred – the main program will be reactivated and continue its flow of control with the next instruction. In this example, it just prints one final message and then terminates the whole program.
The system output will look something like the following:
task 2 : 1 task 1 : 1 task 2 : 2 task 1 : 2 task 2 : 3 task 1 : 3
...
task 2 : 100 task 1 : 100 back to main
Both tasks are taking turns as expected. Which task goes first is systemdependent.
5.2 Preemptive Multitasking
At first glance, preemptive multitasking does not look much different from cooperative multitasking. Program 5.2 shows a first try at converting Program 5.1 to a preemptive scheme, but unfortunately it is not completely correct. The function mytask is identical as before, except that the call of OSReschedule is missing. This of course is expected, since preemptive multitasking does not require an explicit transfer of control. Instead the task switching is activated by the system timer. The only other two changes are the parameter PREEMPT in the initialization function and the system call OSPermit to enable timer interrupts for task switching. The immediately following call of OSReschedule is optional; it makes sure that the main program immediately relinquishes control.
This approach would work well for two tasks that are not interfering with each other. However, the tasks in this example are interfering by both sending output to the LCD. Since the task switching can occur at any time, it can (and will) occur in the middle of a print operation. This will mix up characters from one line of task1 and one line from task2, for example if task1 is interrupted after printing only the first three characters of its string:
71
5 Multitasking
task 1 : 1 task 1 : 2 tastask 2 : 1 task 2 : 2 task 2 :k 1: 3 task 1 : 4
...
But even worse, the task switching can occur in the middle of the system call that writes one character to the screen. This will have all sorts of strange effects on the display and can even lead to a task hanging, because its data area was corrupted.
So quite obviously, synchronization is required whenever two or more tasks are interacting or sharing resources. The corrected version of this preemptive example is shown in the following section, using a semaphore for synchronization.
Program 5.2: Preemptive multitasking – first try (incorrect)
1 #include "eyebot.h"
2 #define SSIZE 4096
3 struct tcb *task1, *task2;
4
5void mytask()
6{ int id, i;
7id = OSGetUID(0); /* read slave id no. */
8for (i=1; i<=100; i++)
9LCDPrintf("task %d : %d\n", id, i);
10OSKill(0); /* terminate thread */
11}
12
13int main()
14{ OSMTInit(PREEMPT); /* init multitasking */
15task1 = OSSpawn("t1", mytask, SSIZE, MIN_PRI, 1);
16task2 = OSSpawn("t2", mytask, SSIZE, MIN_PRI, 2);
17if(!task1 || !task2) OSPanic("spawn failed");
18
19OSReady(task1); /* set state of task1 to READY */
20OSReady(task2);
21 |
OSPermit(); |
/* start multitasking */ |
22OSReschedule(); /* switch to other task */
23/* -------------------------------------------------- */
24/* processing returns HERE, when no READY thread left */
25LCDPrintf("back to main");
26return 0;
27};
72
Synchronization
5.3 Synchronization
Semaphores for synchronization
In almost every application of preemptive multitasking, some synchronization scheme is required, as was shown in the previous section. Whenever two or more tasks exchange information blocks or share any resources (for example LCD for printing messages, reading data from sensors, or setting actuator values), synchronization is essential. The standard synchronization methods are (see [Bräunl 1993]):
•Semaphores
•Monitors
•Message passing
Here, we will concentrate on synchronization using semaphores. Semaphores are rather low-level synchronization tools and therefore especially useful for embedded controllers.
5.3.1 Semaphores
The concept of semaphores has been around for a long time and was formalized by Dijkstra as a model resembling railroad signals [Dijkstra 1965]. For further historic notes see also [Hoare 1974], [Brinch Hansen 1977], or the more recent collection [Brinch Hansen 2001].
A semaphore is a synchronization object that can be in either of two states: free or occupied. Each task can perform two different operations on a semaphore: lock or release. When a task locks a previously “free” semaphore, it will change the semaphore’s state to “occupied”. While this (the first) task can continue processing, any subsequent tasks trying to lock the now occupied semaphore will be blocked until the first task releases the semaphore. This will only momentarily change the semaphore’s state to free – the next waiting task will be unblocked and re-lock the semaphore.
In our implementation, semaphores are declared and initialized with a specified state as an integer value (0: blocked, t1: free). The following example defines a semaphore and initializes it to free:
struct sem my_sema; OSSemInit(&my_sema, 1);
The calls for locking and releasing a semaphore follow the traditional names coined by Dijkstra: P for locking (“pass”) and V for releasing (“leave”). The following example locks and releases a semaphore while executing an exclusive code block:
OSSemP(&my_sema);
/* exclusive block, for example write to screen */
OSSemV(&my_sema);
Of course all tasks sharing a particular resource or all tasks interacting have to behave using P and V in the way shown above. Missing a P operation can
73
5 Multitasking
result in a system crash as shown in the previous section. Missing a V operation will result in some or all tasks being blocked and never being released. If tasks share several resources, then one semaphore per resource has to be used, or tasks will be blocked unnecessarily.
Since the semaphores have been implemented using integer counter variables, they are actually “counting semaphores”. A counting semaphore initialized with, for example, value 3 allows to perform three subsequent non-block- ing P operations (decrementing the counter by three down to 0). Initializing a semaphore with value 3 is equivalent to initializing it with 0 and performing three subsequent V operations on it. A semaphore’s value can also go below zero, for example if it is initialized with value 1 and two tasks perform a P operation on it. The first P operation will be non-blocking, reducing the semaphore value to 0, while the second P operation will block the calling task and will set the semaphore value to –1.
In the simple examples shown here, we only use the semaphore values 0 (blocked) and 1 (free).
Program 5.3: Preemptive multitasking with synchronization
1 #include "eyebot.h"
2 #define SSIZE 4096
3struct tcb *task1, *task2;
4struct sem lcd;
5
6void mytask()
7{ int id, i;
8id = OSGetUID(0); /* read slave id no. */
9for (i=1; i<=100; i++)
10{ OSSemP(&lcd);
11LCDPrintf("task %d : %d\n", id, i);
12OSSemV(&lcd);
13}
14OSKill(0); /* terminate thread */
15}
16
17int main()
18{ OSMTInit(PREEMPT); /* init multitasking */
19 OSSemInit(&lcd,1); /* enable semaphore */
20task1 = OSSpawn("t1", mytask, SSIZE, MIN_PRI, 1);
21task2 = OSSpawn("t2", mytask, SSIZE, MIN_PRI, 2);
22if(!task1 || !task2) OSPanic("spawn failed");
23OSReady(task1); /* set state of task1 to READY */
24OSReady(task2);
25 |
OSPermit(); |
/* start multitasking */ |
26OSReschedule(); /* switch to other task */
27/* ---- proc. returns HERE, when no READY thread left */
28LCDPrintf("back to main");
29return 0;
30};
74
Synchronization
5.3.2 Synchronization Example
We will now fix the problems in Program 5.2 by adding a semaphore. Program 5.3 differs from Program 5.2 only by adding the semaphore declaration and initialization in the main program, and by using a bracket of OSSemP and OSSemV around the print statement.
The effect of the semaphore is that only one task is allowed to execute the print statement at a time. If the second task wants to start printing a line, it will be blocked in the P operation and has to wait for the first task to finish printing its line and issue the V operation. As a consequence, there will be no more task changes in the middle of a line or, even worse, in the middle of a character, which can cause the system to hang.
Unlike in cooperative multitasking, task1 and task2 do not necessarily take turns in printing lines in Program 5.3. Depending on the system time slices, task priority settings, and the execution time of the print block enclosed by P and V operations, one or several iterations can occur per task.
5.3.3 Complex Synchronization
In the following, we introduce a more complex example, running tasks with different code blocks and multiple semaphores. The main program is shown in Program 5.4, with slave tasks shown in Program 5.5 and the master task in Program 5.6.
The main program is similar to the previous examples. OSMTInit, OSSpawn, OSReady, and OSPermit operations are required to start multitasking and enable all tasks. We also define a number of semaphores: one for each slave process plus an additional one for printing (as in the previous example). The idea for operation is that one master task controls the operation of three slave tasks. By pressing keys in the master task, individual slave tasks can be either blocked or enabled.
All that is done in the slave tasks is to print a line of text as before, but indented for readability. Each loop iteration has now to pass two semaphore blocks: the first one to make sure the slave is enabled, and the second one to prevent several active slaves from interfering while printing. The loops now run indefinitely, and all slave tasks will be terminated from the master task.
The master task also contains an infinite loop; however, it will kill all slave tasks and terminate itself when KEY4 is pressed. Pressing KEY1 .. KEY3 will either enable or disable the corresponding slave task, depending on its current state, and also update the menu display line.
75
5 Multitasking
Program 5.4: Preemptive main
1#include "eyebot.h"
2#define SLAVES 3
3 #define SSIZE 8192
4struct tcb *slave_p[SLAVES], *master_p;
5struct sem sema[SLAVES];
6struct sem lcd;
7
8int main()
9{ int i;
10OSMTInit(PREEMPT); /* init multitasking */
11for (i=0; i<SLAVES; i++) OSSemInit(&sema[i],0);
12OSSemInit(&lcd,1); /* init semaphore */
13for (i=0; i<SLAVES; i++) {
14slave_p[i]= OSSpawn("slave-i",slave,SSIZE,MIN_PRI,i);
15if(!slave_p[i]) OSPanic("spawn for slave failed");
16}
17master_p = OSSpawn("master",master,SSIZE,MIN_PRI,10);
18if(!master_p) OSPanic("spawn for master failed");
19for (i=0; i<SLAVES; i++) OSReady(slave_p[i]);
20OSReady(master_p);
21 |
OSPermit(); |
/* activate preemptive multitasking */ |
22OSReschedule(); /* start first task */
23/* -------------------------------------------------- */
24/* processing returns HERE, when no READY thread left */
25LCDPrintf("back to main\n");
26return 0;
27}
Program 5.5: Slave task
1 |
void slave() |
|
2 |
{ int id, i, count = 0; |
|
3 |
/** read slave id no. */ |
|
4 |
||
5 |
id = OSGetUID(0); |
|
6 |
OSSemP(&lcd); |
|
7 |
LCDPrintf("slave %d start\n", id); |
|
8 |
OSSemV(&lcd); |
|
9 |
while(1) |
|
10 |
||
11 |
{ OSSemP(&sema[id]); /* occupy semaphore */ |
|
12 |
OSSemP(&lcd); |
|
13 |
for (i=0; i<2*id; i++) LCDPrintf("-"); |
|
14 |
LCDPrintf("slave %d:%d\n", id, count); |
|
15 |
OSSemV(&lcd); |
/* max count 99 */ |
16 |
count = (count+1) % 100; |
|
17 |
OSSemV(&sema[id]); /* free semaphore */ |
|
18 |
} |
|
19 |
} /* end slave */ |
|
76
Scheduling
Program 5.6: Master task
1void master()
2{ int i,k;
3 |
int block[SLAVES] |
= {1,1,1}; /* |
slaves |
blocked |
*/ |
4 |
OSSemP(&lcd); /* |
optional since |
slaves |
blocked |
*/ |
5LCDPrintf("master start\n");
6LCDMenu("V.0", "V.1", "V.2", "END");
7OSSemV(&lcd);
8
9while(1)
10{ k = ord(KEYGet());
11if (k!=3)
12{ block[k] = !block[k];
13OSSemP(&lcd);
14if (block[k]) LCDMenuI(k+1,"V");
15else LCDMenuI(k+1,"P");
16OSSemV(&lcd);
17 |
if (block[k]) |
OSSemP(&sema[k]); |
18else OSSemV(&sema[k]);
19}
20else /* kill slaves then exit master */
21{ for (i=0; i<SLAVES; i++) OSKill(slave_p[i]);
22OSKill(0);
23}
24} /* end while */
25} /* end master */
26
27int ord(int key)
28{ switch(key)
29{
30case KEY1: return 0;
31case KEY2: return 1;
32case KEY3: return 2;
33case KEY4: return 3;
34}
35return 0; /* error */
36}
5.4Scheduling
A scheduler is an operating system component that handles task switching. Task switching occurs in preemptive multitasking when a task’s time slice has run out, when the task is being blocked (for example through a P operation on a semaphore), or when the task voluntarily gives up the processor (for example by calling OSReschedule). Explicitly calling OSReschedule is the only possibility for a task switch in cooperative multitasking.
77
5 Multitasking
Each task can be in exactly one of three states (Figure 5.1):
•Ready
A task is ready to be executed and waiting for its turn.
•Running
A task is currently being executed.
•Blocked
A task is not ready for execution, for example because it is waiting for a semaphore.
Blocked
V(sema) |
P(sema) |
||||||||||
start of time slice |
|||||||||||
OSReady |
OSKill |
||||||||||
Ready |
Running |
||||||||||
OSReschedule |
or terminate |
||||||||||
or end of time slice |
|||||||||||
Figure 5.1: Task model
Each task is identified by a task control block that contains all required control data for a task. This includes the task’s start address, a task number, a stack start address and size, a text string associated with the task, and an integer priority.
Round robin Without the use of priorities, i.e. with all tasks being assigned the same priority as in our examples, task scheduling is performed in a “round-robin” fashion. For example, if a system has three “ready” tasks, t1, t2, t3, the execution order would be:
t1, t2, t3, t1, t2, t3, t1, t2, t3, ...
Indicating the “running” task in bold face and the “ready” waiting list in square brackets, this sequence looks like the following:
t1 [t2, t3] t2 [t3, t1] t3 [t1, t2]
...
Each task gets the same time slice duration, in RoBIOS 0.01 seconds. In other words, each task gets its fair share of processor time. If a task is blocked during its running phase and is later unblocked, it will re-enter the list as the last “ready” task, so the execution order may be changed. For example:
t1 (block t1) t2, t3, t2, t3 (unblock t1) t2, t1, t3, t2, t1, t3, ...
78