Concurrent and Real-Time Software Development in Ada

IL2206 EMBEDDED SYSTEMS
Laboratory 1 : Concurrent and Real-Time
Software Development in Ada
Version 1.2.3
1 Objectives
The programming language Ada has been developed for embedded and realtime systems. Concurrency is supported directly by the language. Ada offers
powerful communication mechanisms, like rendezvous and the concept of
protected object. Support for real-time systems is provided by the real-time
annex. The objective of the laboratory is to introduce the student to Ada and
its features for concurrency and real-time. For more information on Ada consult the KTH library, which has many books on the Ada programming language.
2 Preparation Tasks
Read the entire laboratory manual in detail before you start with the preparation tasks. Complete the preparation tasks before your lab session in order to
be allowed to start the laboratory exercises.
It is very important that students are well-prepared for the labs, since both
lab rooms and assistants are expensive and limited resources, which shall be
used efficiently. The laboratory will be conducted by groups of two students.
However, each student has to understand the developed source code and the
preparation tasks. Course assistants will check, if students are well-prepared.
Whenever you have completed a task of the laboratory, mark the task as
completed by putting a cross into the corresponding circle.
All program code shall be well-structured and well-documented. The language used for documentation is English.
Documentation
1
For this laboratory all tasks of Section 3 can be considered as preparation
tasks. However, if you have worked seriously and encounter problems, you
can still book and visit a laboratory session to discuss with the assistants.
Preparation Tasks for this Laboratory
2.1 Installation of gnat
For this laboratory the development tool gnat (GNU Ada) will be used. GNAT
supports the full real-time annex of Ada 2005/2012 and is part of the gcc tool
suite. GNAT is available under UNIX and thus there should be no problem to
install it, if you use any Linux distribution.
We strongly recommend the use of the virtual machine that is provided
by KTH. If you want to use a native Linux installation, you need to make sure
that you use only one processor core when doing this laboratory. If you use
Ubuntu on the virtual machine, you can install gnat with the command sudo
apt-get install gnat.
KTH will only provide support for the installation on the virtual machine,
and cannot provide any support for own Ada-installations on Windows, Mac
⃝ 2.1 completed OS, or Linux.
• If you use the real-time annex in Ada, the programs need to be run in
supervisor mode for the correct timing!
• Ada programs will in general use all cores. If programs shall run on a
single core, it has to be enforced by the user. In Linux the user can use
the command sudo taskset -c 0 ./program_name to enforce execution of a single core.
Important Notes
2.2 Code Skeletons
KTH provides code skeletons for the laboratory, which can be downloaded
from the course page in Canvas.
2.3 Modular Types and Attributes in Ada
Ada provides a modular integer data type, which can be used to implement a
circular buffer. This data type is used in the code skeletons for Section 3.2 provided for the laboratory. In case an addition or other operation yields a result
that is larger or smaller than the highest or smallest value that the data type
can represent, then “wrap-around semantics” are used. The following examples illustrates the usage of this data type, and also shows how attributes like
First and Last can be used to access certain properties of the defined data
type. Attributes play an important role in Ada and can be used in different
circumstances.
2
1 with Ada.Text_IO;
2 use Ada.Text_IO;
3
4 procedure Modular_Types is
5
6 type Counter_Value is mod 10;
7 package Counter_Value_IO is
8 new Ada.Text_IO.Modular_IO (Counter_Value);
9
10 Count : Counter_Value := 5;
11
12 begin
13 Put("First value of type Counter_Value: ");
14 Counter_Value_IO.Put(Counter_Value'First,1);
15 Put_Line(" ");
16 Put("Last value of type Counter_Value: ");
17 Counter_Value_IO.Put(Counter_Value'Last,1);
18 Put_Line(" ");
19 for I in 1..5 loop
20 Count := Count + 6;
21 Counter_Value_IO.Put(Count);
22 Put_Line("");
23 end loop;
24 end Modular_Types;
Execution of the code gives the following output.
1 ada> ./modular_types
2 First value of type Counter_Value: 0
3 Last value of type Counter_Value: 9
4 1
5 7
6 3
7 9
8 5
3 Laboratory Tasks
3.1 Semaphore
The Ada language does not directly provide library functions for a semaphore.
However, semaphores can be implemented by means of a protected object.
Skeletons for the package are available on the course page. Use the package specification Semaphore in the file semaphores.ads and modify the corresponding package body in the file semaphores.adb so that the package implements a counting semaphore. ⃝ 3.1 completed
3
3.2 Producer-Consumer Problem
The producer-consumer problem is a very relevant problem in the design of
embedded systems. The problem is illustrated in the Figure 1 and can be forProducer
P1
Consumer
C1
.
.
.
Buffer .
.
.
Producer
Pm
Consumer
Cn
Figure 1: Producer-Consumer Problem
mulated as follows. There are m producer and n consumer processes, which
are connected to a single buffered communication channel. Producers write
data to the communication channel, consumers read data from the communication channel. For a reliable communication, the following synchronisation properties have to be fulfilled:
• A consumer cannot read a data element from an empty buffer
• A producer cannot write a data element into a full buffer
In the above formulation of the producer-consumer problem, consumers can
read data from any sender and are not concerned from which sender the data
comes from. When data is read, it is also removed from the buffered channel.
(a) Develop a solution for the producer-consumer problem by means of
a protected object that uses a buffer of a fixed size. Use the package Buffer from the package specification file buffer.ads and package body file buffer.adb, which together with an initial code skeleton
producerconsumer_prot.adb for the main program implementation is
available on the course web page. Use the protected object to implement
the producer consumer problem and save the final implementation in the
file producerconsumer_prot.adb.
The buffer implementation uses modular types. These enable define
data types, which allow a ’wrap-around’ if the maximum value (or minimum value) is reached and the next value (or previous value) should
be calculated. For instance, if a variable V is implemented as a modular
integer type between 0 and 5, and the current value is 5, then adding 1
to the variable V would give the result 0.
Modular Types in Ada
4
Please study the executable example on modular types in Ada, which is
available in the Lab1’s Canvas page to understand how modular types
can be used.
Note: The main procedure and its corresponding source code file need to
have the same name. Thus the main procedure needs to have the name
ProducerConsumer_Prot. ⃝ 3.2-a completed
(b) Develop a solution for the producer-consumer problem using the rendezvous mechanism. Use the same buffer structure as in Task a, but
implement the circular buffer as an own server task. Save your implementation as producerconsumer_rndvzs.adb. An initial skeleton for
producerconsumer_rndvzs.adb can be found on the course web page. ⃝ 3.2-b completed
(c) Develop a solution for the producer-consumer problem using your
semaphore implementation from Task 3.1. Use the same buffer structure
as in Task a, but implement the circular buffer as a shared variable. An initial skeleton for producerconsumer_sem.adb can be found on the course
web page. In order to use the semaphore package it shall be installed
in the same directory as producerconsumer_sem.adb. It can then be accessed by the following code.
1 with Semaphores;
2 use Semaphores;
Use two semaphores NotFull and NotEmpty, which shall be used to block
a) tasks that want to write to a full buffer, and b) tasks that want to read from
an empty buffer, and another semaphore AtomicAccess to ensure mutual exclusive access to the buffer data structure. Your code shall use the code for
the buffer provided in the skeleton producerconsumer_sem.adb and shall not
be based on a protected object or rendezvous.
Draw also the diagram that illustrates your solution extending the figure
above. ⃝ 3.2-c completed
3.3 Real-Time Annex
Note: All programs using the real-time annex must be run as root, if you run
on a Linux machine. Otherwise the scheduler will not respect the priorities.
3.3.1 Periodic Tasks in Ada
A real-time Ada program, where six tasks with fixed priorities are scheduled
priority-driven, produce the following output on a single core computer.
> sudo taskset -c 0 ./periodictasks_analyse_priority
Warm-Up - No task released for 100 Milliseconds
Task 4- Release: 0.200, Completion: 0.374, Response: 0.174, WCRT: 0.174, Next Release: 0.900
Task 5- Release: 0.400, Completion: 0.582, Response: 0.182, WCRT: 0.182, Next Release: 1.000
Task 6- Release: 0.600, Completion: 0.702, Response: 0.102, WCRT: 0.102, Next Release: 1.000
Task 1- Release: 0.800, Completion: 0.946, Response: 0.146, WCRT: 0.146, Next Release: 1.700
Task 2- Release: 1.000, Completion: 1.089, Response: 0.089, WCRT: 0.089, Next Release: 1.500
5
Task 6- Release: 1.000, Completion: 1.179, Response: 0.179, WCRT: 0.179, Next Release: 1.400
Task 3- Release: 1.200, Completion: 1.289, Response: 0.089, WCRT: 0.089, Next Release: 2.000
Task 5- Release: 1.000, Completion: 1.359, Response: 0.358, WCRT: 0.358, Next Release: 1.600
Task 4- Release: 0.900, Completion: 1.396, Response: 0.496, WCRT: 0.496, Next Release: 1.600
Task 2- Release: 1.500, Completion: 1.589, Response: 0.089, WCRT: 0.089, Next Release: 2.000
Task 6- Release: 1.400, Completion: 1.592, Response: 0.192, WCRT: 0.192, Next Release: 1.800
Task 1- Release: 1.700, Completion: 1.788, Response: 0.088, WCRT: 0.146, Next Release: 2.600
Task 6- Release: 1.800, Completion: 1.889, Response: 0.089, WCRT: 0.192, Next Release: 2.200
Task 5- Release: 1.600, Completion: 1.897, Response: 0.297, WCRT: 0.358, Next Release: 2.200
Task 4- Release: 1.600, Completion: 1.986, Response: 0.386, WCRT: 0.496, Next Release: 2.300
Task 3- Release: 2.000, Completion: 2.096, Response: 0.096, WCRT: 0.096, Next Release: 2.800
Task 2- Release: 2.000, Completion: 2.185, Response: 0.185, WCRT: 0.185, Next Release: 2.500
Task 6- Release: 2.200, Completion: 2.322, Response: 0.122, WCRT: 0.192, Next Release: 2.600
Task 5- Release: 2.200, Completion: 2.413, Response: 0.213, WCRT: 0.358, Next Release: 2.800
Task 2- Release: 2.500, Completion: 2.588, Response: 0.088, WCRT: 0.185, Next Release: 3.000
Task 4- Release: 2.300, Completion: 2.591, Response: 0.291, WCRT: 0.496, Next Release: 3.000
Task 1- Release: 2.600, Completion: 2.729, Response: 0.129, WCRT: 0.146, Next Release: 3.500
Task 3- Release: 2.800, Completion: 2.889, Response: 0.089, WCRT: 0.096, Next Release: 3.600
Task 6- Release: 2.600, Completion: 2.908, Response: 0.308, WCRT: 0.308, Next Release: 3.000
Task 5- Release: 2.800, Completion: 2.998, Response: 0.198, WCRT: 0.358, Next Release: 3.400
Task 2- Release: 3.000, Completion: 3.090, Response: 0.090, WCRT: 0.185, Next Release: 3.500
Task 6- Release: 3.000, Completion: 3.180, Response: 0.180, WCRT: 0.308, Next Release: 3.400
Task 4- Release: 3.000, Completion: 3.270, Response: 0.270, WCRT: 0.496, Next Release: 3.700
Task 2- Release: 3.500, Completion: 3.589, Response: 0.089, WCRT: 0.185, Next Release: 4.000
Task 3- Release: 3.600, Completion: 3.689, Response: 0.089, WCRT: 0.096, Next Release: 4.400
Task 1- Release: 3.500, Completion: 3.768, Response: 0.268, WCRT: 0.268, Next Release: 4.400
Task 6- Release: 3.400, Completion: 3.795, Response: 0.395, WCRT: 0.395, Next Release: 3.800
Task 6- Release: 3.800, Completion: 3.889, Response: 0.089, WCRT: 0.395, Next Release: 4.200
Task 5- Release: 3.400, Completion: 3.975, Response: 0.575, WCRT: 0.575, Next Release: 4.000
Task 2- Release: 4.000, Completion: 4.089, Response: 0.089, WCRT: 0.185, Next Release: 4.500
Task 5- Release: 4.000, Completion: 4.179, Response: 0.179, WCRT: 0.575, Next Release: 4.600
Task 6- Release: 4.200, Completion: 4.289, Response: 0.089, WCRT: 0.395, Next Release: 4.600
Task 4- Release: 3.700, Completion: 4.334, Response: 0.634, WCRT: 0.634, Next Release: 4.400
Task 3- Release: 4.400, Completion: 4.547, Response: 0.147, WCRT: 0.147, Next Release: 5.200
Task 2- Release: 4.500, Completion: 4.636, Response: 0.136, WCRT: 0.185, Next Release: 5.000
Task 1- Release: 4.400, Completion: 4.726, Response: 0.326, WCRT: 0.326, Next Release: 5.300
Task 6- Release: 4.600, Completion: 4.817, Response: 0.217, WCRT: 0.395, Next Release: 5.000
Task 5- Release: 4.600, Completion: 4.907, Response: 0.307, WCRT: 0.575, Next Release: 5.200
Task 4- Release: 4.400, Completion: 4.997, Response: 0.597, WCRT: 0.634, Next Release: 5.100
Task 2- Release: 5.000, Completion: 5.090, Response: 0.089, WCRT: 0.185, Next Release: 5.500
Task 6- Release: 5.000, Completion: 5.179, Response: 0.179, WCRT: 0.395, Next Release: 5.400
Task 3- Release: 5.200, Completion: 5.289, Response: 0.089, WCRT: 0.147, Next Release: 6.000
Task 1- Release: 5.300, Completion: 5.390, Response: 0.090, WCRT: 0.326, Next Release: 6.200
Task 6- Release: 5.400, Completion: 5.489, Response: 0.089, WCRT: 0.395, Next Release: 5.800
Task 2- Release: 5.500, Completion: 5.590, Response: 0.090, WCRT: 0.185, Next Release: 6.000
Task 5- Release: 5.200, Completion: 5.648, Response: 0.448, WCRT: 0.575, Next Release: 5.800
Task 4- Release: 5.100, Completion: 5.718, Response: 0.617, WCRT: 0.634, Next Release: 5.800
Task 3- Release: 6.000, Completion: 6.089, Response: 0.089, WCRT: 0.147, Next Release: 6.800
Task 2- Release: 6.000, Completion: 6.179, Response: 0.179, WCRT: 0.185, Next Release: 6.500
Task 6- Release: 5.800, Completion: 6.182, Response: 0.382, WCRT: 0.395, Next Release: 6.200
Task 1- Release: 6.200, Completion: 6.289, Response: 0.089, WCRT: 0.326, Next Release: 7.100
Task 6- Release: 6.200, Completion: 6.379, Response: 0.179, WCRT: 0.395, Next Release: 6.600
Task 5- Release: 5.800, Completion: 6.452, Response: 0.652, WCRT: 0.652, Next Release: 6.400
Task 2- Release: 6.500, Completion: 6.589, Response: 0.089, WCRT: 0.185, Next Release: 7.000
Task 6- Release: 6.600, Completion: 6.689, Response: 0.089, WCRT: 0.395, Next Release: 7.000
Task 5- Release: 6.400, Completion: 6.720, Response: 0.320, WCRT: 0.652, Next Release: 7.000
Task 3- Release: 6.800, Completion: 6.889, Response: 0.089, WCRT: 0.147, Next Release: 7.600
Task 4- Release: 5.800, Completion: 6.898, Response: 1.098, WCRT: 1.098, Next Release: 6.500
Task 4- Release: 6.500, Completion: 6.988, Response: 0.488, WCRT: 1.098, Next Release: 7.200
Task 2- Release: 7.000, Completion: 7.130, Response: 0.130, WCRT: 0.185, Next Release: 7.500
Task 1- Release: 7.100, Completion: 7.221, Response: 0.120, WCRT: 0.326, Next Release: 8.000
Task 6- Release: 7.000, Completion: 7.310, Response: 0.310, WCRT: 0.395, Next Release: 7.400
Task 6- Release: 7.400, Completion: 7.489, Response: 0.089, WCRT: 0.395, Next Release: 7.800
Task 5- Release: 7.000, Completion: 7.490, Response: 0.489, WCRT: 0.652, Next Release: 7.600
Task 2- Release: 7.500, Completion: 7.590, Response: 0.090, WCRT: 0.185, Next Release: 8.000
Task 3- Release: 7.600, Completion: 7.690, Response: 0.090, WCRT: 0.147, Next Release: 8.400
Task 5- Release: 7.600, Completion: 7.780, Response: 0.180, WCRT: 0.652, Next Release: 8.200
Task 6- Release: 7.800, Completion: 7.889, Response: 0.089, WCRT: 0.395, Next Release: 8.200
Task 4- Release: 7.200, Completion: 7.939, Response: 0.739, WCRT: 1.098, Next Release: 7.900
Task 2- Release: 8.000, Completion: 8.089, Response: 0.089, WCRT: 0.185, Next Release: 8.500
Task 1- Release: 8.000, Completion: 8.178, Response: 0.178, WCRT: 0.326, Next Release: 8.900
Task 6- Release: 8.200, Completion: 8.289, Response: 0.089, WCRT: 0.395, Next Release: 8.600
Task 5- Release: 8.200, Completion: 8.379, Response: 0.179, WCRT: 0.652, Next Release: 8.800
Task 4- Release: 7.900, Completion: 8.386, Response: 0.486, WCRT: 1.098, Next Release: 8.600
6
Task 3- Release: 8.400, Completion: 8.512, Response: 0.112, WCRT: 0.147, Next Release: 9.200
Try to order the tasks according to their task priority. Give a motivation how
you have arrived at your conclusion. ⃝ 3.3.1 completed
3.3.2 Rate-Monotonic Scheduling
Given is the following set of periodic tasks:
Γ1 = {τ1(100, 300, 100, 300), τ2(100, 400, 100, 400), τ3(100, 600, 100, 600)}
where the times are given in milliseconds. A periodic task τi
is defined as a
tuple τi(ϕi
, Ti
, Ci
, Di), where ϕi denotes the phase, Ti the period, Ci the computation time, and Di the relative deadline.
1. Calculate the utilisation and draw the rate-monotonic schedule for this
set of tasks for one hyperperiod.
2. Given is the skeleton program periodictasks_priority.adb. Run the
program for some time iterations on a single core1 and calibrate the program by adjusting the constant Calibrator, so that the measured worst
case execution time for the running task is close to the given computation time.
3. Implement the periodic task set Γ1 in Ada, so that the tasks are scheduled rate-monotonically. Build your implementation on the calibrated
skeleton program periodictasks_priority.adb.
(a) Save the program as rms.adb. Execute the program and validate
the expected behaviour.
(b) Save the output from one simulation in electronic format and provide it as part of your solution.
(c) Run the program several times for a few hyperperiods. Does the
program follow the schedule from Task 1? Try to explain possible
deviations between the schedule in reality and the theoretical one.
(d) (Optional) If possible, run the program rms.adb using all cores on
your computer2
.
4. Add now an additional task τ4 = (100, 1200, 200, 1200).
(a) Draw the schedule for the program for one hyperperiod.
(b) Save the program as rms2.adb. Run the program several times for
a few hyperperiods. Compare the resulting schedule with the one
of Task 4a. Explain possible deviations.
NOTE: In case you see no deadline violations, increase the length
of the computation times by adjusting the constant Calibrator.
(c) Save the output from one simulation in electronic format and provide it as part of your solution.
⃝ 3.3.2 completed
1
In Linux you can use the command sudo taskset -c 0 ./rms to enforce execution of a single core.
2
In Linux the cores 0 to 3 will be used, if you use the command sudo taskset -c 0,1,2,3
./rms2. For more information on your cores, run sudo less /proc/cpuinfo.
7
3.3.3 Overload Detection with Watchdog Timer
In order to be able to detect an overloaded system, add both a watchdog timer
task and one additional helper task to your program rms2.adb and save it as
overloaddetection.adb.
The watchdog timer and the helper task shall communicate with each
other using rendezvous. An overload happens when there is not enough
free CPU capacity to run all the user tasks until completion within a hyperperiod. Study the principal functionality of a watchdog timer in the lecture
notes and design the watchdog timer. Then think about how an additional
helper task should be designed, so that the watchdog timer task can detect an
overloaded system. In case of an overload, the watchdog timer shall output a
warning. Make a sketch of your design and be prepared to explain the functionality of your solution to the course staff. To solve this task, it is important
to understand how the fixed-priority scheduling algorithm determines which
task should be scheduled and executed, and when these decisions are taken.
Thus, you also have to think about which priorities should be given to the
watchdog timer task and the helper task.
1. Run the system with overload detection and the task set Γ1 = {τ1, τ2, τ3}
as described in Section 3.3.2-3.
2. Run the system with overload detection and the task set Γ2 =
{τ1, τ2, τ3, τ4} as described in Section 3.3.2-4. Did you observe a system
overload? When did it occur? If not, increase the workload. Explain the
results.
⃝ 3.3.3 completed
3.3.4 Mixed Scheduling
Add now three background tasks to the program from Task 3.3.2-3, which run
on a low priority and are scheduled in a round-robin fashion. The tasks shall
be repeatedly3 executed and each background task has an execution time of
100 milliseconds. Implement this system as mixedscheduling.adb using the
high-priority task set Γ1 = {τ1, τ2, τ3}.
In order to enable mixed scheduling, use the following pragmas for the
high-priority and the background tasks.
pragma Priority_Specific_Dispatching(
FIFO_Within_Priorities, 2, 30);
pragma Priority_Specific_Dispatching(
Round_Robin_Within_Priorities, 1, 1);
Calculate the time, when the first background task should be executed in
⃝ 3.3.4 completed theory and compare with the practical result.
3.3.5 (Optional) Multi-processor execution
If your host machine supports it, increase the number of processors allocated to the VM, for instance to 2. Run the programs overloaddetection of
3Note that repeatedly is not the same as periodically!
8
Task 3.3.3-2 and mixedscheduling of Task 3.3.4. How does this change affect
the execution compared to a single-processor run? Make a rough sketch of
the schedule for overloaddetection. Does the program follow it?
4 Examination
Demonstrate the programs that you have developed for the laboratory staff
during your laboratory session. Be prepared to explain your program in detail. In order to pass the laboratory the student must have completed all tasks
of Section 3 and have successfully demonstrated them for the laboratory staff.
9