The Study On Task Synchronization Oriented Scheduling Algorithms For Multicore Embedded Real-Time Systems

With the rapid advancement of multi/many core processor systems and embedded realtime applications,the research of embedded real-time operating system has become a hotspot,where the real-time task scheduling is the core techique.However,the problem of task synchronization,which is stemmed from the resource access contention among tasks running on multicore platforms with shared resources,can delay the exeution times of tasks and thus may significantly affect the schedulability of task system.This problem poses new challenges to the designs on the real-time scheduling algorithms for multicore systems.When compared to global scheduling,partitioned based scheduling has less online overhead and thus better performance due to migration-less activities at run-time.On the other hand,in comparison with suspension based resource access protocol,the spin-lock based protocol(such as MSRP(Multiprocessor Stack Resource Policy))can avoid deadlock and has better performance and simpler implementation,which has been widely adopted in real-time systems.Aiming at the trends towards heterogeneous multicore architecture for embedded applications and the ever-increasing demands of system dependability for real-time activities,based on partitioned-EDF(Earliest Deadline First)scheduling and MSRP protocol,this thesis studies the schedulability theory,mapping heuristic and kernel implementation for reliability-aware partitioning algorithm on homogeneous multicores as well as mapping scheme on heterogeneous multicores.This is to address the critical problem of real-time scheduling targeted at multicore computing platforms under the limitations of task synchronization.For homogeneous multicore real-time systems with resource sharing under the reliability requirements,we first develop the system utilization bound for the partitioned EDF scheduler with the MSRP protocol and PB(Primary/Backup)technique,and then derive the non-monotonicity of the bound,i.e.,the bound may decrease when more cores are deployed.Based on the pessimistic analysis of the utilization bound,this thesis proposes a reliability and synchronization aware task partitioning algorithm RSA-TPA.By thoroughly studying the characteristics of blocking interferences among tasks,we first exploit the decreased number of deployed cores and a resource-guided method to reduce the bound on the blocking overheads of tasks.Then,those unmapped(primary/backup)tasks are iteratively prioritized subject to their dynamic utilization estimates.We also design a task-to-core mapping policy to assign a task that leads to the minimum system utilization increase among possible cores,resulting in improved system schedulability and workload balancing.Moreover,to further reduce the time complexity of scheduling algorithm,we present a simplified RSA-TPA-efficient.The simulation results show that RSA-TPA can obtain higher schedulability ratio(e.g.,60% more)compared to the existing mapping schemes that focus on either system reliability or task synchronization.For the shared resource heterogeneous multicore real-time systems,we first derive the sufficient schedulability condition for the scheduling of partitioned EDF with MSRP protocol based on the analysis of worst-case blocking overheads of tasks.Then,we estimate the approximate system utilization where the phenomenon of the non-monotonicity of the bound still exists.Following the insights obtained from the bound,this thesis proposes a synchronization aware task partitioning algorithm for heterogeneous multicores(SA-TPAHM).In the algorithm,a solution to tighten the bound on the synchronization overheads of tasks upon heterogeneous platforms is first presented for better feasibility test.Next,the task ordering priority(for determining the sequence of un-mapped tasks to be allocated next)is dynamically calculated for more schedulable possibility of the whole task set.Moreover,by means of multiple probes and computing the system utilization,each task-to-core allocation guarantees the minimized increment in the system utilization for balanced workload on cores.The extensive simulation results demonstrate the advantage of SA-TPAHM with respect to schedulability ratio(e.g.,60% more)over the existing mapping schemes targeted at homogenous multicores.To further evaluate the practical viability of our proposed partitioning algorithms,we implement them together with other related mapping algorithms in Linux kernel.The measurement results reveal that our mapping schemes can have lower run-time overheads(e.g.,15% less)due to fewer context switchings on each core under EDF algorithm(and thus better applicability)in contrast to the existing mapping schemes,thanks to the partitions generated with balanced workload distribution across cores.