ECE 4550/5550G Project 2∗ Due Tuesday March 31, 2020 at 11:59PM in Canvas (220 Points) Objective To design, implement, and measure the performance of popular real-time scheduling algorithms. 1 Project Overview In Project 1, you learned that FreeRTOS uses a simple priority-based scheduling algorithm. In this project, you will be implementing two real-time scheduling algorithms that we have seen and studied in class on FreeRTOS. The algorithms are: 1. Rate monotonic (RM) 2. Earliest-deadline first (EDF) You will also measure the overhead of the scheduling algorithms and its impact on timeliness. As in Project 1, you will validate your implementation through a systemic debugger (in our case the serial port communication). Creating new schedulers can be a lot of work and may seem intimidating, but follow along, as we will provide you with skeleton code and plenty of hints along the way. Besides, you will feel great when you are done! 2 Getting Started From Canvas, download the zip file. Inside, you will see a set of files (project2.ino, scheduler.cpp and scheduler.h) inside the rm and edf directories. A modified version of FreeRTOS is also provided inside libraries; we expose a few FreeRTOS APIs (particularly xTaskGetCurrentTaskHandle and xTaskGetIdleTaskHandle), and enable certain functionality (configUSE TICK HOOK, configUSE TRACE FACILITY, and INCLUDE eTaskGetState) that we think you will find useful. Your first job is to look over scheduler.cpp and scheduler.h, paying close attention to code segments that were written to guide you with the im- plementation. Then, consult the example sketch project2.ino to understand how to create a task set, and call the scheduling policy of your choice. 3 Tasks & Rubrics 1. (80 points) Implement the RM scheduling algorithm with the following requirements: • Your algorithm does not need to perform any schedulability test. • In the event that a job misses its deadline, it should be suspended and run as a new job at its next release time. In other words, the current (missed) instance of the task is dropped. ∗This project was created by Dr. Anway Mukherjee (
[email protected]). 1 • If a job executes for more than its worst-case execution time (i.e., an execution overrun occurs), you need to detect it and suspend it until its next release time. Again, conceptually, this overrun job is dropped. • Your code should print out relevant information to the serial monitor, e.g., which task is executing, if a task misses its deadline, etc. The key to implementing RM in FreeRTOS is determining how to update the priority of a task/job. You can debug/test your code with an arbitrary task set or you can use the ones given below. However, it is recommended that you stick with just two tasks in a task set; having more tasks may result in a failed heap allocation. Note, however, that this is merely a hardware limitation and does not affect the awesome experience you’re gaining from this project! There are several FreeRTOS APIs that you may find helpful: • vTaskGetInfo populates a TaskStatus t structure for just a single task. The TaskStatus t structure contains, among other things, the members for the task handle, task name, task priority, task state, and the total amount of execution time consumed by the task. • xTaskGetHandle looks up the handle of a task from the task’s name. • xTaskGetTickCount/xTaskGetTickCountFromISR returns the number of ticks since vTaskStartScheduler was called. Note that any function not ending with “FromISR” may not be safe to be called from the interrupt context. • uxTaskPriorityGet/vTaskPrioritySet obtains/sets the priority of a task. Hints: • Use the serial port to better understand/debug code inside scheduler.cpp. However, since the print buffer capacity is limited, use Serial.println() judiciously. • You will have to write a scheduler task inside scheduler.cpp that will check for timely completion/deadline misses. Set the priority of this task accordingly. • One task structure that will be useful is xExtended TCB in scheduler.cpp. Feel free to add members to xExtended TCB to help with maintaining a list of per-task parameters. • One function that will be useful to you is vApplicationTickHook(), which is found in FreeRTOS/src/tasks.c. This is a user-defined function that is called at every system tick. Your job is to somehow integrate this function with the scheduler task (and rest of the given code in scheduler.cpp) to formally implement RM. Ideally, you should not do heavy compu- tation inside vApplicationTickHook() since it works within the interrupt context. Note that you will also need to implement all the supplied stub functions in scheduler.cpp to make it work. What to include in your report: A description of your RM implementation. This description should be detailed enough that a competent peer of yours can follow along and implement your work. 2. (80 points) Implement the EDF scheduling algorithm with the same requirements as RM (see above).Both RM and EDF follow the same pattern of execution, although specific functions will vary. The key to implementing EDF in FreeRTOS is calculating and updating job priorities on the fly. The function prvUpdatePrioritiesEDF() may come in handy. EDF uses a modified version of linked list data structure to store the tasks (and their related parameters) being scheduled, while RM uses arrays. This part is well documented in the supplied source code. Note that the implementation uses two lists, xTCBOverflowedList and pxTCBList, for ease of implementation. xTCBOverflowedList stores sorted linked list for periodic tasks that have missed their deadlines, and pxTCBList is the actual list of active tasks to be sched- uled. Linked list specific APIs include vListInitialiseItem(), listSET LIST ITEM OWNER(), 2 listSET LIST ITEM VALUE(), vListInsert(), and uxListRemove(). Their actual implementa- tion(s) can be found in FreeRTOS/src/list.c You can, however, use an array to make your life easier but it may cause additional overhead (why?). What to include in your report: A description of your EDF implementation. You don’t need to repeat information already described under your RM implementation. 3. (50 points) Test your RM and EDF algorithms using the following two task sets, as shown in Ta- bles 1–2. The time units are in milliseconds. When constructing the task set, make sure that each task parameter is a multiple of your scheduler task’s period (defined as schedSCHEDULER TASK PERIOD in scheduler.h). Table 1: Task set #1 Task C D T τ1 100 400 400 τ2 200 700 800 Table 2: Task set #2 Task C D T τ1 300 400 400 τ2 200 700 800 What to include in your report: In 1-3 paragraphs, compare and contrast the scheduling algorithms and their performance on these task sets. 4. (10 points) For each of the algorithms, augment your scheduler task to account for scheduler overhead. Rerun the task sets above. What to include in your report: Describe your findings and observations in 1-2 paragraphs. 4 Turning In Your Work You are to upload the following documents on Canvas. • Your report in PDF format. • Your RM and EDF code. Please remember that you must turn in your own work. Failure to do so will result in you being reported to the university. 3