Real-time scheduling of parallel tasks in the Linux Kernel

• Author(s): Fonseca, José ; Nogueira, Luis ; Maia, Cláudio ; Pinho, Luis Miguel
• Date: 2012
• Persistent ID: http://hdl.handle.net/10400.22/3693
• Origin: Repositório Científico do Instituto Politécnico do Porto
• Subject(s): Real-time scheduling; Task-level parallelism; Work-stealing; Linux
• Document Type: Report
• Language: English

Description

This paper proposes a global multiprocessor scheduling algorithm for the Linux kernel that combines the global EDF scheduler with a priority-aware work-stealing load balancing scheme, enabling parallel real-time tasks to be executed on more than one processor at a given time instant. We state that some priority inversion may actually be acceptable, provided it helps reduce contention, communication, synchronisation and coordination between parallel threads, while still guaranteeing the expected system’s predictability. Experimental results demonstrate the low scheduling overhead of the proposed approach comparatively to an existing real-time deadline-oriented scheduling class for the Linux kernel.