Scheduling of a hybrid set of tasks

Introduction

In Scheduling of periodic tasks codelab , you learned how to schedule of set of periodic tasks using the Rate Mononotic Algorithm (RMA).

In this codelab, we address the problem of scheduling a hybrid set of tasks. A hybrid set of tasks is made of both periodic and aperiodic tasks. For this purpose, we first apply a simple Background Scheduling approach, where aperiodic tasks are scheduled in time slots and no periodic task is active. Given the limitation of this approach, we then implement servers for aperiodic tasks. We will first implement a Polling Server and second a Deferrable Server.

What you’ll build

In this codelab, you will build an application with a number of periodic and aperiodic tasks, using Background Scheduling, a Polling Server and a Deferrable Server. In all cases, periodic tasks will be scheduled using the Rate Monotic Algorithm.

What you’ll learn

How to implement Background Scheduling.
How to dimension a Server task.
How to implement a Polling and a Deferrable server.

What you’ll need

You need to have finished the Digging into RTX.
You need to have completed the Scheduling of periodic tasks codelab
You need to have completed the Robust Development Methodologies (I) codelab and the Robust Development Methodologies (II) codelab.

Background Scheduling of Aperiodic Tasks

In this first part of the codelab, we implement the scheduling of aperiodic tasks in the background. We thus first implement a set of periodic tasks using the Rate Monotonic Algorithm and then add a Background Task that will execute aperiodic tasks whenever no periodic task is being executed.

Implement RM for a set of periodic tasks

The set of periodic tasks to be implemented is the one described in the exercice related to Background scheduling. Based on the implementation of the Rate Monotonic Algorithm of a previous codelab, you must first adapt the program for the set of periodic tasks described in the exercice. If you do so and analyze your program using Tracealyzer, you should get a trace similar to this one:

Adding a generator of aperiodic requests

In a true system, aperiodic requests would be generated by different actors, like the user pressing a button or an alarm generated by a sensor. In this codelab, we are targeting to reproduce the same results as the ones obtained in the exercice.

For this purpose, we may use an aperiodic event generator as the one given below. The priority of the thread used for creating aperiodic requests should be high enough for guaranteeing that events are generated on time.

application/aperiodic_gen.h

#ifndef APPLICATION_APERIODIC_GEN_H_
#define APPLICATION_APERIODIC_GEN_H_

#include "app_config.h"

#if defined(CREATE_APERIODIC_TASKS)
void initialize_aperiodic_request(void);
void start_aperiodic_request_gen(void* arg);
#endif

#endif  // APPLICATION_APERIODIC_GEN_H_

application/aperiodic_gen.c

#include "aperiodic_gen.h"

// possible other includes

#if defined(CREATE_APERIODIC_TASKS)
static const uint32_t aperiodic_arrival_times[]   = {200U, 700U, 1700U, 2100U};
static const uint32_t aperiodic_computing_times[] = {300U, 100U, 100U, 300U};
static const uint32_t nbr_of_aperiodic_requests =
    sizeof(aperiodic_arrival_times) / sizeof(aperiodic_arrival_times[0]);
static uint32_t aperiodic_index                 = 0;
osMessageQueueId_t aperiodic_task_queue  = NULL;
static const uint32_t aperiodic_task_queue_size = 4;
static const uint32_t aperiodic_task_msg_size   = sizeof(aperiodic_computing_times[0]);

void initialize_aperiodic_request(void) {
    // create a queue for aperiodic requests
    aperiodic_task_queue =
        osMessageQueueNew(aperiodic_task_queue_size, aperiodic_task_msg_size, NULL);
    if (aperiodic_task_queue == NULL) {
        app_error_handler(CANNOT_CREATE_QUEUE);
    }
}
void start_aperiodic_request_gen(void* arg) {
    // we assume that all threads start with a START_DELAY delay
    if (START_DELAY > 0U) {
        osDelayUntil(START_DELAY);
    }

    // generate aperiodic requests
    while (aperiodic_index < nbr_of_aperiodic_requests) {
        // wait for the next request to be generated
        osDelayUntil(aperiodic_arrival_times[aperiodic_index] + START_DELAY);

        osStatus_t status =
            osMessageQueuePut(aperiodic_task_queue,
                              (void*)(&aperiodic_computing_times[aperiodic_index]),
                              1,
                              osWaitForever);
        if (status != osOK) {
            app_error_handler_with_info(CANNOT_PUT_TO_QUEUE, status);
        }

        aperiodic_index++;
    }

    // the thread will exit once all aperiodic requests have been generated
}
#endif

The functions above may be used as illustrated below:

    // initialize aperiodic requests generation
    initialize_aperiodic_request();

    // start a thread for generating aperiodic requests
    static const osThreadAttr_t ap_th_att_gen = {.name     = "AperiodicThreadGen",
                                                 .priority = osPriorityNormal7};
    osThreadId_t tid_ap_thr_task_gen =
        osThreadNew(start_aperiodic_request_gen, NULL, &ap_th_att_gen);
    if (tid_ap_thr_task_gen == NULL) {
        app_error_handler(CANNOT_CREATE_THREAD);
    }

Note

The above code is not fully MISRA compliant - up to you to fix the small violations still present

Implement background scheduling of aperiodic tasks

With Background Scheduling, aperiodic tasks are scheduled in the background in time slots. So, whenever no periodic task is ready to execute, one aperiodic task is picked from a queue and is run. This can be implemented using the queue of aperiodic tasks as illustrated below:

Background Scheduling can be implemented by adding a task with low priority that will serve the aperiodic requests queued in the aperiodic tasks queue. The strategy for choosing the aperiodic request can be any strategy (based on arrival for instance, meaning FCFS) and is independant from the RM itself.

For implementing Background Scheduling, you should thus:

add a function named background_task_thread that attempts to get a message from the aperiodic_task_queue instance. It should wait for a message with a osWaitForever timeout.
add a function named app_main_background() that integrates the aperiodic request generation code illustrated above, together with the code for running RM on the selected set of periodic tasks. This function should also execute the background_task_thread in a separate thread with low priority.
call the app_main_background() function from your main program.

If you implement Background Scheduling correctly and analyze the results correctly, you should observe the same task scheduling as the one obtained in the solution of the related exercice.

Implement a polling server

Implementing a polling server first requires to dimension it, as described in the related exercice. Once the \(T_{S}\) and \(C_{S}\) values of the polling server are known, you may integrate the following implementation of a polling server task in your application.

application/polling.c

extern osMessageQueueId_t aperiodic_task_queue;

__NO_RETURN void polling_task_thread(void* arg) {
    // cppcheck-suppress misra-c2012-11.5
    // rationale: void* being the one solution in c that
    //            allows generic interfaces - albeit not type safe
    struct task_info_t task_info = (struct task_info_t) * ((struct task_info_t*)arg);

    if (START_DELAY > 0U) {
        osDelayUntil(START_DELAY);
    }

    // we assume that all threads start at time START_DELAY with phase 0
    uint32_t next_period_start_time = START_DELAY;

    for (;;) {
        // update next period start time
        next_period_start_time += task_info.period;

        // poll for aperiodic requests
        // for simplicity, we assume that we won't get more than 3 aperiodic requests
        uint32_t aperiodic_computing_times[] = {0, 0, 0};
        uint32_t nbr_of_aperiodic_requests   = 0;

        for (;;) {
            uint32_t aperiodic_computing_time = 0;
            osStatus_t status                 = osMessageQueueGet(
                aperiodic_task_queue, &aperiodic_computing_time, NULL, 0);
            if (status != osOK && status != osErrorResource) {
                app_error_handler_with_info(CANNOT_GET_FROM_QUEUE, status);
            }
            if (status == osErrorResource) {
                break;
            }
            aperiodic_computing_times[nbr_of_aperiodic_requests] =
                aperiodic_computing_time;
            nbr_of_aperiodic_requests++;
        }

        // execute aperiodic tasks
        // if one or more aperiodic requests exist -> make sure that we have the budget
        // for each request

        // at polling time the budget is the full server budget
        uint32_t server_budget = task_info.computation_time;
        for (uint8_t index = 0; index < nbr_of_aperiodic_requests; index++) {
            if (aperiodic_computing_times[index] <= server_budget) {
                // budget is available, execute the task
                busy_wait_ms(aperiodic_computing_times[index]);

                // update the budget
                server_budget -= aperiodic_computing_times[index];
            } else {
                // the task cannot be executed entirely with the available budget
                // requeue the request
                osStatus_t status =
                    osMessageQueuePut(aperiodic_task_queue,
                                      (void*)(&aperiodic_computing_times[index]),
                                      1,
                                      osWaitForever);
                if (status != osOK) {
                    app_error_handler_with_info(CANNOT_PUT_TO_QUEUE, status);
                }
            }
        }

        // wait until the end of the period
        osDelayUntil(next_period_start_time);
    }
}

This function must be integrated in your application in the same way as the Background Scheduling task was integrated. If you implement scheduling with a Polling Server correctly and analyze the results correctly, you should observe the same task scheduling as the one obtained in the solution of the related exercice.

Implement a deferrable server

Implementing a Deferrable Server rather than a Polling Server only requires to modify the polling_task_thread function given above into a deferrable_task_thread function. In fact, the deferrable_task_thread function is less complex to realize that the polling_task_thread function. This function must simply continuously wait for aperiodic requests and execute the aperiodic tasks within the allocated server budget. In addition, it must replenish the server budget at the start of each task period. For this purpose, it must wait for aperiodic requests with a timeout corresponding to the end of the task period. The function is thus easily implemented with two embedded loops.

Note

Be aware that when the function osMessageQueueGet is called with a timeout value that is > 0, then the function returns osErrorTimeout when no message is available. When the function is called with a 0 timeout value, then it returns osErrorResource when no message is available. This latter case is illustrated in the polling_task_thread function.

If you implement scheduling with a Deferrable Server correctly and analyze the results correctly, you should observe the same task scheduling as the one obtained in the solution of the related exercice.