Scheduling of Periodic Tasks with Data Dependency on Multiprocessors

Abstract:

This article studies the scheduling problem of a set of tasks with time or data constraints on a number of identical processors with full connections. We present an algorithm, in which a set of static schedule lists can be obtained, each for a processor, such that each task starts executing after its release time and completes its computation before its deadline, and all the precedence relations between tasks resulting from data dependency are satisfied. The data dependency relations between tasks are represented by Synchronous Dataflow Graphs (SDF) as they can indicate tasks concurrency and enable effective scheduling on multiprocessor platforms. The SDF, however, does not support the time constraints of tasks directly, thus an adaption is applied to conform to the time limits. With this adaption, the periodic tasks of implicit-deadline or constrained-deadline can be scheduled on multiprocessor platform effectively.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 2131-2136
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.2131
• Online since: September 2013
• Authors: Jin Lin Wang
• Keywords: Data-Dependency, Multiprocessor, Real-Time, Scheduling, SDF

References

[1] OSEK, OSEX/VDX Operating System Specification 2. 2. 1, OSEK Group, 2003, www. osek-vdx. org.

DOI: 10.1049/ic:19981075

[2] RTEMS, RTEMS C user's guide, Edition 4. 9. 2, for RTEMS 4. 9. 2, OAR Corporation, (2009).

[3] VxWorks, VxWorks 653 - DO-178B Certified ARINC 653 Real-Time Operating System, Wind River, (2006).

[4] ARINC, ARINC Specification 653: Avionics Application Software Standard Interface, Aeronautical Radio INC, (2005).

DOI: 10.1201/9781315222240-22

[5] Julien Forget, Frederic Boniol, Emmanuel Grolleau, David Lesens and Claire Pagetti, Scheduling Dependent Periodic Tasks Without Synchronization Mechanisms, RTAS 2010, pp.301-310, doi: 10. 1109/RTAS. 2010. 26.

DOI: 10.1109/rtas.2010.26

[6] Jia Xu, Multiprocessor Scheduling of Processes with Release Times, Deadlines, Precedence, and Exclusion Relations, IEEE Transactions on software engineering, vol. 19, No. 2, Feb. (1993).

DOI: 10.1109/32.214831

[7] Edward Ashford and David G. Messerschmitt, Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing, IEEE Transactions on computers, vol. C-36, No. 1, Jan. (1987).

DOI: 10.1109/tc.1987.5009446

[8] Margarete Sackmann, Peter Ebraert and Dirk Janssens, A Fast Heuristic for Scheduling Parallel Software with Respect to Energy and Timing Constraints, IEEE International Distributed Processing Symposium, 2011, pp.1397-1406.

DOI: 10.1109/ipdps.2011.284

[9] T.C. Hu, Parallel sequencing and assembly line problems, Operat. Res., vol. 9, pp.841-848, (1961).

[10] Ishfaq Ahmad, Yu-Kwong Kwok, Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors, ISPAN 1996, p.207.

DOI: 10.1109/ispan.1996.508983