辅导案例-5550G
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 (anwaym@vt.edu).
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
51作业君 51作业君

扫码添加客服微信

添加客服微信: IT_51zuoyejun