Final Solution Demonstration

Design Solution

The earliest deadline first (EDF) scheduler system project is a real-time system using the FreeRTOS real-time kernel operating system for microcontrollers. The FreeRTOS OS and the EDF scheduler system project code is being executed on the STM32F4_DISCOVERY microcontroller. The system uses 3 tasks along with user defined tasks (UDT) which are generated periodically. These UDTs are generated by the “Deadline_Driven_Task_Generator” which generates tasks based on the period of each task. While the “Deadline_Driven_Scheduler” task decides which UDTs execute next via EDF. The system uses 5 queues and 3 linked lists to communicate and manage tasks. Where the queues pass data and the linked lists hold active, completed and overdue tasks for the system. In addition, the system uses various helper functions to manage UDTs and linked lists.

Monitor Task

The Monitor Task is responsible for obtaining information from the DDS regarding each of the DD task lists. These task lists are obtained by retrieving the head of each of the active, overdue and complete task linked lists, by calling get_active_dd_task_list, get_overdue_dd_task_list and get_complete_dd_task_list respectively. The heads are retrieved from the active_list_queue, overdue_list_queue and complete_list_queue respectively and since they are passed into the queue from the DDS by reference, the Monitor Task can iterate from the head of each list to determine the tasks in each linked list. The Monitor Task was chosen to be given the highest priority instead of the recommendation of setting it as the lowest. This is because the Monitor Task is to only be run once a hyperperiod (1500ms). Through this, the overhead is minimized during the execution of each hyperperiod where the Monitor Task is then guaranteed to run once after all the tasks are done.

DDS - Deadline Driven Schedular Task

The DDS is responsible for orchestrating the three linked lists that track tasks: active DD task list, overdue DD task list, and complete DD task list. This is done by receiving new periodic tasks from the Deadline Driven Task Generator via the release_dd_task function as dd_task structs. The DDS is also designed to receive aperiodic tasks that would need to be instantiated via the release_dd_task function as the periodic tasks are. From release_dd_task, new tasks are packaged into the release_queue which is received as a message in the DDS. The DDS will not run any new tasks while there are still new incoming tasks/messages in the release queue. This is because all the tasks need to be sorted in terms of EDF in the active DD task list. Once the release_queue is empty and assuming that the DDS isn't currently running any UDTs, the DDS can release the highest priority task in the active DD task list as the UDF. This is done by calling the dd_create function which sets the proper priority, current milliseconds as the task's release time and proceeds to create a new UDT via FreeRTOS. Once the new UDF is released, the DDS is unable to run any new UDT's until the current UDT is finished. Within the UDT, the task stalls for the amount of execution time that was specified in the supplied dd_task struct, assigns a completion time, and finishes by calling the complete_dd_task function which sends the newly-completed task ID in the complete_queue as a message to be received by the DDS. When the DDS receives the message, the task is removed from the active DD task list and placed into the complete or overdue DD task lists depending on whether it finished before its deadline or not. The DDS also monitors the active DD task list to check if tasks waiting to be run have turned overdue. If any overdue tasks are found, they are removed from the active list and placed into the overdue list. Finally, the DDS packages the head of each DD task list into its own queue as a message to be received by the Monitor Task (active_list_queue, overdue_list_queue, complete_list_queue). These queues are frequently overwritten to reflect the most up to date state of each task list.

Deadline Driven Task Generator

The Deadline Drive Task Generator was implemented to send the periodic DD tasks from the 3 test benches to the DDS. This is done by sending new task information to release_dd_task which forwards a new struct to the DDS. The periodicity of tasks is created by using FreeRTOS delays between successive releases of the same task where the amount of time to be delayed in milliseconds was calculated beforehand. By releasing new tasks this way, only one generator task was needed as compared to a generator for each task (option b). Furthermore, heap_4.c was configured for this task to work successfully including the ability to dynamically delete tasks elsewhere in the application.

User Defined Task

The UDT is a dynamically created and deleted task from the DDS. When the DDS wants to create a new DD task, this auxiliary task is called and is passed the struct containing the task's information. From the struct, the UDT is able to determine the execution time proceeds to stall within itself for that duration. Following, the UDT assigns the current milliseconds as the completion time to the task's struct and calls complete_dd_task where the task ID is sent as a message in the complete_queue back to be received by the DDS. Finally, the UDT suspends itself, is deleted by the DDS and the process is restarted once the DDS creates a new DD task.

The following diagram outlines the program architecture and the communication streams between tasks and the peripherals: