Title: Dynamic Migration Decisions in Multicore Systems
Abstract: Since multicore platforms are becoming more common for real-time systems, multicore real-time scheduling algorithms become more relevant. For a more efficient use of the additional processing capacity of multiple cores, many of these algorithms allow tasks to migrate between cores, which improves the schedulability of task systems, but comes at the cost of additional migration overhead. One possible approach to reduce this overhead is the restriction of migration to predefined migration points that are known to be beneficial. For semipartitioned scheduling algorithms, an approach exists that identifies a set of potential migration points at which migrating tasks can be split statically, so that at run time, each job of the task migrates at this point. This has the disadvantage that it is impossible to avoid task migration, even if the actual run times of the current job would otherwise allow the job to finish on its current core.
This thesis presents a solution for this problem by introducing dynamic migration decisions. Instead of using a statically selected point, an algorithm for dynamic migration decisions tries to choose the latest possible migration point out of the predefined set, depending on the run-time behaviour of the current job. In order to use as much run-time information as possible, the presented algorithms use the concept of evaluation points, which are defined as the latest possible points at which migration decisions can be made. For each migrating job, an evaluation point is initially set and repeatedly recalculated, until migration decisions can no longer be delayed and a migration point is selected. From this approach, three algorithms are derived, which differ in the way evaluation points are defined. The algorithms presented in this thesis define evaluation points as points in code, points in execution time, and a combination of both, respectively.
All presented algorithms can be combined with any semipartitioned scheduling algorithm. It is shown that dynamic migration decisions do not cause any deadline misses in any task set, if the task set is schedulable with fixed migration points. An analysis of the additional required operations shows, that both the number of evaluation points, and the required effort for each evaluation point are at most logarithmic for all algorithms in the average case. Since the required effort decreases with increasing run times, the static assignment of split tasks to cores needs to consider only a constant overhead for each part of a split task.
All presented algorithms have been implemented on a Raspberry Pi v2 model B, based on a FreeRTOS port. Time measurements of this implementation indicate, that the overhead for dynamic migration decisions is unlikely to impact the schedulability of a given task system. While dynamic migration decisions make it possible to avoid migration if the current run times allow it, the measured response times show no significant adverse impact of the additional overhead of the presented algorithms.
Publication Year: 2020
Publication Date: 2020-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot