A tool for the deterministic scheduling of real-time programs implemented as periodic Ada tasks
Pages 54 - 73
Abstract
In this paper, we describe an experimental tool for the scheduling and execution of real-time programs on a single processor. This tool accepts a real-time program implemented as a system of periodic tasks written in a subset of Ada. It translates the program into equivalent Ada source code in which the task bodies are executed by a run-time dispatcher according to a deterministic, cyclic schedule.The schedule is represented as a table of scheduling actions describing the execution of the program for a major cycle, which is repeated at intervals of the major period of the least common multiple of all task periods. Each scheduling action covers an interval in the major cycle, and specifies a sequence of statements within a task that is to be executing during that interval. A compile-time scheduler arranges these scheduling actions within the major cycle such that all timing and rendezvous constraints will be satisfied. The periodic Ada tasks all start simultaneously (there is no task phasing), so that the schedule satisfying all constraints in the first major cycle can be repeated indefinitely.A simple example of a translation is presented, and the results of using this tool to schedule and execute some experimental task systems are described.
References
[1]
[1] Reference Manual for the Ada Programming Language . United States Department of Defense, Ada Joint Program Office, ANSI/MIL-STD-1815A- 1983 edition, February 1983.
[2]
[2] Verdix Ada Development System: Sun-3 UNIX to Motorola 68000 Family, Version 5.7. Verdix Corporation, March 1989.
[3]
[3] T.P. Baker. A one-pass algorithm for overload resolution in Ada. ACM Transactions on Programming Languages and Systems, 3.4:601-614, October 1982.
[4]
[4] T.P. Baker. A single-pass syntax directed front end for Ada. In Proceedings of ACM SIGPLAN Symposium on Compiler Construction, pages 309-318, Boston, Massachusetts, 1982.
[5]
[5] T.P. Baker. Stack-based scheduling of realtime processes. Real-Time Systems, 3(1):67-99, March 1991.
[6]
[6] T.P. Baker and Alan Shaw. The Cyclic Executive Model and Ada. Technical Report 88-04-07, University of Washington, Department of Computer Science, Seattle, Washington, 1988.
[7]
[7] M.I. Chen and K.J. Lin. Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems. Technical Report UIUCDCS-R-89- 1511, University of Illinois at Urbana-Champaign, Department of Computer Science, April 1989.
[8]
[8] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Bell Laboratories, Murray Hill, New Jersey, 1987.
[9]
[9] E.W. Giering and T.P. Baker. Compile time scheduling of an Ada subset. In Proceedings of the Seventh Washington Ada Symposium, pages 143- 155, ACM, June 1990.
[10]
[10] E.W. Giering and T.P. Baker. Toward the deterministic scheduling of Ada tasks. In Proceedings of the 1989 IEEE Real-time Systems Symposium, pages 31-40, IEEE, December 1989.
[11]
[11] John B. Goodenough and Lui Sha. The priority ceiling protocol: a method for minimizing the blocking of high priority Ada tasks. In Proceedings of the 2nd International Workshop on Real-Time Ada Issues, May 1988.
[12]
[12] Marion G. Harmon. Predicting execution time of real-time programs on contemporary machines. In Proceedings of the 28th Annual Southeast Regional Conference, page 192, Association for Computing Machinery, ACM, Greenville, South Carolina, April 1990.
[13]
[13] C.A.R. Hoare. Monitors: an operating system structuring concept. Communications of the ACM, 17(10):549-557, October 1974.
[14]
[14] Edward W. Giering III. Compile Time Processing of Ada Task Constructs for Real-Time Programming . PhD thesis, Florida State University, Department of Computer Science, Tallahassee, Florida, April 1991.
[15]
[15] Joseph Y-T. Leung and M.L. Merrill. A note on preemptive scheduling of periodic, real-time tasks. Information Processing Letters, 11(3):115- 118, November 1980.
[16]
[16] Joseph Y-T. Leung and Jennifer Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2:237-250, 1982.
[17]
[17] C.L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the Association for Computing Machinery, 20(1):46-61, January 1973.
[18]
[18] A.K.-L. Mok. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment . PhD thesis, MIT, May 1983.
[19]
[19] Aloysius K. Mok. Sartor - a design environment for real-time systems. In Proc. 9th IEEE COMPSAC, pages 174-181, October 1985.
[20]
[20] Chang Yun Park and Alan C. Shaw. Experiments with a program timing tool based on source-level timing schema. Computer, 24(5):48-57, May 1991.
[21]
[21] Ragunathan Rajkumar, Lui Sha, John P. Lehoczky, and K. Ramamritham. An Optimal Priority Inheritance Protocol for Real-Time Synchronization. Technical Report, Carnegie Mellon University, 1989. Submitted for publication.
[22]
[22] Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky. Priority Inheritance Protocols - An Approach to Real-Time Synchronization. Technical Report, Carnegie Mellon University, Departments of CS, ECE and Statistics, Pittsburgh, Pennsylvania, 1987.
Index Terms
- A tool for the deterministic scheduling of real-time programs implemented as periodic Ada tasks
Recommendations
A tool for the deterministic scheduling of real-time programs implemented as periodic Ada tasks
In this paper, we describe an experimental tool for the scheduling and execution of real-time programs on a single processor. This tool accepts a real-time program implemented as a system of periodic tasks written in a subset of Ada. It translates the ...
Preference-oriented fixed-priority scheduling for periodic real-time tasks
A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, ...
Exact schedulability tests for real-time scheduling of periodic tasks on unrelated multiprocessor platforms
In this paper, we study the global scheduling of periodic task systems on unrelated multiprocessor platforms. We first show two general properties which are well known for uniprocessor platforms and which are also true for unrelated multiprocessor ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Fall 1994107 pages
Copyright © 1994 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 September 1994
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations3Total Citations
- 359Total Downloads
- Downloads (Last 12 months)95
- Downloads (Last 6 weeks)13
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in