• Thread T1 : period=1 second, capacity=200 millisecond. The deadline is equal to the period.
• Thread T2 : period=400 millisecond, capacity=100 millisecond. The deadline is equal to the period.

Exercise 3 : Synchronization : mutex vs counting semaphore

1. Compile and test the program. What can you see? Explain this behavior.
2. Modify this program to correct this wrong behavior. For such a purpose, you can use the pthread_mutex_lock and pthread_mutex_unlock functions or the sem_wait and sem_post functions.

1. Compile and test this program. This program implements a producer/consumer synchronization. The buffer stores only one character. Producers write data in the buffer character by character. Consumers read data from the buffer character by character. The buffer is built with two counting semaphores called number_of_full_positions and number_of_empty_positions (respectivly initialized with the values 0 and 1). Those semaphores model/store the number of busy and empty positions into the buffer. These semaphores allow you to block producers when no empty locations exist in the buffer and respectively to block consumers when no full locations exist in the buffer.
   The algorithm of a producer is :
   

   while(1)
   {
      P(number_of_empty_positions);
      Produce and put a character into the buffer;
      V(number_of_full_positions);
   }
   

   
   
   The algorithm of a consumer is :

   while(1)
   {
      P(number_of_full_positions);
      Read and display a character from the buffer;
      V(number_of_empty_positions);
   }
   

2. Change this program in order to define a buffer that is able to store upto 4 characters (e.g. a buffer composed of 4 positions). The buffer must be a FIFO buffer.
3. Change your program in order to allow several producers and several consumers to handle your 4 positions buffer.

III. Programming RTEMS with Ada

• First, for exercises 4 to 10, we will compile and run programs on Linux. Here, we use a GNAT compiler with a Linux runtime.
• Second, for exercises 11 to 13, we will compile on Linux programs that will be run on a RTEMS/Sparc Leon processor. We always use the GNAT compiler, but with a RTEMS runtime. We will see in this second set of exercises that we handle the same programming language, but with a different compiler.

III.1 Introduction to Ada : sequential programming

source adalinux.bash

Exercise 4 : hello world

Save the file hello.adb. Compile this program with the following command:

gnatmake -g hello

What are the different files generated by gnatmake ?

Exercise 5 : input/output

1. Download, compile and test the following file: readint.adb.
2. Change readint.adb in order to read an integer from the keyboard and to print it on the screen.
3. In this changed program, what does the program do when we give it a string instead of an integer?
4. Write a package called my_io which contains the source code to print to the screen/read from keyboard float and integer data. Change the program of question 3 in order to use your package my_io.

Exercise 6 : compute average of floats

Write a program that:

• Allows you to read several floats from the keyboard.
• When you give 0.0 to your program, your program computes and displays the average, maximum value and minimum value of all floats previously read from the keyboard.
• We do not have to handle an array in this program.

Exercise 7 : generic package

Download and save these files: stacks.ads, stacks.adb, and the main procedure test_stack.adb. These files implement a polish calculator.

1. Compile and test these programs.
2. Add three procedures :
   1. The first one implements the divide operator.
   2. The second one allows to reverse the order of the data stored in the stack.
   3. The last one allows to display to the screen the data stored in the stack.

III.2 Concurrency with Ada

Exercise 8 : declaring a task

Write an Ada program :

1. Which defines a task type element.
2. Which declares 10 tasks of type element.
3. The body of the tasks type element must display a message to the screen every second.

1. Increment the counter.
2. Display the value of the counter and displays either "tick" or "tock".
3. Wait for one second before starting a new iteration.

1. Compile and test the program.
2. How many tasks your program contains?
3. Can you say when the tasks start to run ?
4. Can you say when the main procedure is terminated?
5. This program raises a very classical concurrency problem. What is this problem?
   
   To give of solution to the problem of the question 5, we would like to change the program. We add a new task called mutex. This task has two entries allowing a rendez-vous with the two other tasks : these two entries, called P and V have no parameter. This task should allow to implement critical sections on shared resources.
   
   
6. Propose a source code for this third task. Explain how it works.
7. Update the previous program in order to ensure critical section of the shared counter.

In this program, we implement a producer/consumer synchronization. These consumers and producers share integer data by a buffer, which is a simple integer table. This table can store 4 integers. The buffer is managed according to a FIFO policy : the first inserted/produced integer will also be the first to be removed/consumed.

1. In a first step, write an Ada program composed of only one producer and one consumer. For such a purpose, you must use :
   • The Semaphores package (both files Semaphores.ads and Semaphores.adb). This protected type implements a counting semaphore in Ada. You have a program that shows how to use this package in order to build a critical section between several tasks.
   • In your program, you must define two counting semaphores called number_of_full_positions et number_of_empty_positions (respectively initialized with the values 0 and 4). Those semaphores model/store the number of busy and empty positions into the buffer. These semaphores allow you to block producers when no empty location exist in the buffer and respectively to block consumers when no full locations exist in the buffer.
   • The algorithm of a producer is :

     loop
        P(number_of_empty_positions);
        Produce and put the integer into the buffer;
        V(number_of_full_positions);
     end loop;
     

   • The algorithm of a consumer is :

     loop
        P(number_of_full_positions);
        Read and display an integer from the buffer;
        V(number_of_empty_positions);
     end loop;
     

2. Change your program in order to allow several producers and several consumers to handle the buffer.
3. From a practical point of view, Ada programmers do not use semaphores to implement a semaphore. They usually directly implement the synchronization protocol into a protected object. Write a protected object that implements a FIFO buffer of 4 integers that can be handled by several producers and consumers. This protected object must provide two subprograms:
   1. A first sub-program that allows a producer to store a new integer in the buffer.
   2. A second sub-program that allows a consumer to read/remove an integer from the buffer.
   3. Here is a possible protected object specification for this question:

         Buffer_Size : constant Integer :=4;
         type Buffer_Type is array (1..Buffer_Size) of Integer;
      
         protected type Synchronized_Buffer is
            entry Write(Val : in Integer);
            entry Read(Val : in out Integer);
         private
            Buffer_Data : Buffer_Type;
            Index_Cons : Integer :=1;
            Index_Prod : Integer :=1;
            Number_Element : Integer:=0;
         end Synchronized_Buffer;
      

We would like to write an Ada program to convert base 10 integers to base 2 integers. To convert, we use the method which consists in dividing several times the base 10 integer by 2. To increase efficiency, we would like to implement this program with a pipe-line of Ada tasks. The task interface is the following:

  type Stage; 
  type Stage_Ptr is access Stage; 

  task type Stage is
      entry Next_Stage (
            A_Task : in     Stage_Ptr ); 
      entry Divide (
            Value  : in     Integer ); 
  end Stage;

1. An entry called Next_Stage: this entry allows a stage n to store a pointer to the next stage n+1. This entry is only used at program initialization in order to build the pipe-line.
2. An entry called Divide: this entry of a stage n is called by the stage n-1. This entry does the following statements :
   • It divides by 2 the received data and displays to the screen the remainder (0 or 1).
   • After division, if the result is greater than 0, the current stage must send the result to the next stage to continue the computation.
   • After division, if the result is greater than 0 and if the data has reached the last stage, the program must display an error message.
   • Finally, after division, if the result is equal to 0, it means that the computation is completed.

• Dynamically allocate and initialize a 8 stages pipe-line.
• Allows the user to give a base 10 integer from the keyboard and to send it to the first stage of the pipe-line.

III.3 Real-time programming with Ada on RTEMS

Exercise 11 : cross compiling of an Ada program


In this exercise, we will compare the "Linux/Intel 386" Ada runtime and the "RTEMS/Leon" Ada runtime. Download and save the following file. Put it in a directory called EXO11.

1. Compile the hello.adb program with the command gnatmake -g hello.adb.
2. Launch the command file hello : what is the meaning of the displayed information?
3. Launch hello and check that the program works well on Linux.
   
   
   
4. Now, we will run the same program on a RTEMS and Leon/Sparc processor. For such a purpose, launch the source rtems.bash command, as we made it to compile our first C programs. Now you can compile C or Ada programs for RTEMS.
5. Compile again the hello.adb program, but now with the following command:

   make clean
   make
   

6. This command has built a new executable file called o-optimize/hello.exe.
7. Launch the file o-optimize/hello.exe. What is the meaning of the displayed information?
8. Can we directly launch the binary o-optimize/hello.exe from your Unix Shell?
9. Then, run o-optimize/hello.exe on the tsim simulator as follow:

   $tsim
   tsim>
   tsim>load o-optimize/hello.exe
   tsim>go
   Hello world
   

Exercise 12 : fixed priority scheduling with Ada


Remind that to do this exercise, you must use the RTEMS cross-compiler for the Sparc/Leon processor (available from rtems.bash) and the tsim simulator.

In this exercise, we will experiment real-time scheduling of an Ada program on a RTEMS target. First, download this file and save it in a directory called EXO12.

1. Edit the gnat.adc file. What is the meaning of each pragma that is present in this file?
2. Edit the scheduling.adb file to assign a 12 priority level to task Task_A, a 11 priority level to task Task_B and a 13 priority level to the main procedure.
3. Compile scheduling.adb.
4. Test your program with the simulator and see the generated scheduling.
5. Change your program in order to assign an equal level of priority to all tasks. Compile and run this new program.
6. Add the statement delay 1.0 in the loop of each task body. What does this statement do? Compile and run this last program.

Exercise 13 : implementing periodic tasks scheduled according to Rate Monotonic

Remind that to do this exercise, you must use the RTEMS cross-compiler for the Sparc/Leon processor (available from rtems.bash) and the tsim simulator

First, download this file and save it in a directory called EXO13.

1. We assume the following task set :
   • Task T1 : period=1 second, capacity=10 millisecond.
   • Task T2 : period=500 millisecond, capacity=10 millisecond.
   • Task T3 : period=250 millisecond, capacity=10 millisecond.
   • Deadlines are equal to periods.
2. Assuming we use a preemptive Rate Monotonic scheduling, can you prove that this task set will meet its deadlines? Give the scheduling sequence of this tasks set (compute this scheduling sequence by hand).
3. We now write an Ada program that implements the previous periodic task set. You have to fill the files periodic.adb and generic_periodic_task.adb for such a purpose. The parts of the program you have to fill are shown by several stars:
   1. The file periodic.adb is the main procedure and has to create T1, T2 and T3. periodic.adb must also ensure that a critical instant will occur (e.g. T1, T2 and T3 must start at the same time, after completion time of the main procedure). First_Release_Time stores the first release time for T1, T2 and T3. Subprograms Program_T1, Program_T2 and Program_T3 are the code each task has to run at each of its release time.
   2. The generic_periodic_task.adb generic unit implements a periodic task. This generic package has to be instantiated three times : for T1, T2 and T3. For each task, this generic unit is parametrized by its period, its priority, its first release time and also the subprogram the task has to run each time the task is released.
4. Fill periodic.adb : you must instantiate the 3 tasks T1, T2 and T3.
5. Fill generic_periodic_task.adb : you must provide a body for the periodic task. In this task body, you must add the statements that allow the task to run 5 iterations. For each iteration, the task must run its code, compute and wait for its next periodic release time.
6. Compile and test your program with tsim.

V. Project 2013/2014 : implementing multi-processor scheduling algorithms

• Package tasks defines and implements tasks that can be handled by the simulator.
• Package schedulers implements the simulator itself. The provided simulator implements only one scheduler : a preemptive Rate Monotonic scheduling.

• You can work by groups of 2 students (no more).
• You must send your work by email no latter than the 15th of June : marks will be delivered to the USTH the 16th of June
• You must send both the source code you wrote and also a small report which contains the answers for the questions below.
• You are not allowed to add in your report or source code any pieces of text or source code from the web or from another student.

1. We assume a set of three periodic tasks defined by the following parameters S1=S2=S3=0, P1=5, C1=1, P2=10, C2=3, P3=30 et C3=8. Draw the scheduling sequence according to a preemptive Rate Monotonic scheduling. Is this task set schedulable?
2. Change main.adb to run the task set of the previous question, compile and test your program. Check that the scheduling you computed by hand is similar to the one computed by the simulator.
3. In the main procedure main.adb and in the file scheduler.adb, can you find :
   • Where and how the tasks of the system are initialized.
   • Where and how the task periodic releases are implemented.

1. At the same time, the scheduler can run two tasks if two tasks are ready to run. One task is run on each core.
2. At any time, the two tasks running on the cores are the ready tasks which have the smallest period.
3. If the two cores are busy and if a task A is released which has a smallest period than the two tasks running on the cores, then, task A must preempt the task which has the larger period.
4. A task can migrate from one core to another one. Two kinds of migrations exist : 1) when tasks can migrate at any time 2) when tasks can migrate only at the release time of the task.

1. At the same time, the scheduler can run two tasks if two tasks are ready to run. One task is run on each core.
2. At any time, the two tasks running on the cores are the ready tasks which have the smallest dynamic deadline.
3. If the two cores are busy and if a task A is released which has a dynamic deadline smaller than the two tasks running on the cores, then, task A must preempt the task which has the largest dynamic deadline.
4. A task can migrate from one core to another one. Two kinds of migrations exist : 1) when tasks can migrate at any time 2) when tasks can migrate only at the release time of the task.

VI. Project 2012/2013 : implementing an aperiodic server

• Package tasks defines and implements tasks that can be handled by the simulator.
• Package schedulers implements the simulator itself. The provided simulator implements only one scheduler : a Rate Monotonic scheduling.

• You can work by groups of 2 students (no more).
• You must send your work by email no latter than the 20th of June.
• You must send both the source code you wrote and also a small report which contains the answers for the questions below.
• You are not allowed to add in your report or source code any pieces of text or source code from the web or from another student.

1. We assume a set of three periodic tasks defined by the following parameters S1=S2=S3=0, P1=5, C1=1, P2=10, C2=3, P3=30 et C3=8. Draw the scheduling sequence according to a preemptive Rate Monotonic scheduling. Is this task set schedulable?
2. Change main.adb to run the task set of the previous question, compile and test your program. Check that the scheduling you computed by hand is similar to the one computed by the simulator.
3. In the main procedure main.adb and in the file scheduler.adb, can you find :
   • Where and how the tasks of the system are initialized.
   • Where and how the task periodic releases are implemented.

1. The server run aperiodic tasks arrived before the server activation.
2. It does not use processor if no aperiodic task is present : the server capacity is lost if no aperiodic task is present.
3. The server stops aperiodic execution when its capacity is exhausted.

• Explain in your report how the implemented scheduler works.
• Test your program with at least two task sets. You must send your program with the task sets you used to test your program. Your program must also be explained in your report.

VII. Project 2011/2012 : implementing a real time scheduling simulator

• Package user_level_tasks defines and implements tasks that can be handled by the simulator. These tasks are interacting with the simulator by two means:
  1. By rendez-vous in order to simulate the exhausted time. The wait_for_processor entry indicates to the simulator that a task is ready to be run and that it waits for the processor in order to run its next unit of time of its capacity. The release_processor entry is called by a task to report to the scheduler that the task has completed execution of one unit of time.
  2. By a protected object. The protected object user_level_scheduler stores the scheduling data handled by the scheduling simulator. These data are protected because the simulator and several tasks can access them at the same time. Note that with the provided example, this synchronization is not required : it is required when several schedulers work all together (e.g. multiprocessor scheduling). The protected data by the protected object are the list of the tasks (variables called tcbs and number_of_tasks), the current time of the simulation (variable current_time), ...
• Package user_level_schedulers implements the simulator itself. The provided simulator implements only one scheduler : a Rate Monotonic scheduling.

1. my_subprograms contains the code each task has to run for each release. For this example, the code only contains a display on the screen.
2. The main procedure example defines 3 tasks that are scheduled by Rate Monotonic.

• You can work by groups of 2 students (no more).
• You must send your work by email no latter than the 21th of June. I will ask to Daniel Hagimont if we can have an extra time, but its not sure.
• You must send both the source code you wrote and also a small report which contains the answers for the questions below.
• You are not allowed to add in your report or source code any pieces of text or source code from the web or from another student.

1. We assume a set of three periodic tasks defined by the following parameters S1=S2=S3=0, P1=5, C1=1, P2=10, C2=3, P3=30 et C3=8. Draw the scheduling sequence according to a preemptive Rate Monotonic scheduling. Is this task set schedulable?
2. Compile and run example.adb. Check that the scheduling you computed by hand is similar to the one computed by the simulator.
3. In the main procedure example.adb, can you find :
   • Where and how the tasks of the system are initialized.
   • Where and how the task periodic releases are implemented.

• Explain in your report what is a laxity.
• Explain in your report how MUF is working.
• Test your program with several task sets. You must send your program with the task sets you used to test your program. Your program must also be explained in your report.