Real-time Architectures (2IN20) spring 2004


(31-8-2004) NOTE: the examination of August 13 has been corrected. Final marks have been published again through owinfo (in order not to make a difference with the previous exam). Preliminary solutions are found here. The remainder of the week of 30-8 we will be out of office, unfortunately.


With respect to the practical work, please hand it in at the secretary in HG 5.08. We will grade it with insuffient, sufficient or good to be published via the website. Since the exam resulted in a considerable number of 5-scores we decided to round a combination of a 5 score and a ‘good’ into a 6. This is the only way the practical affects the final grade.


NOTE: the examination has been corrected with final marks published through owinfo. Actually, this has been done too early as you are still expected to hand in the practical exercise. Apologies for this and we will avoid this situation in the future. Solutions to the examination are found here.


NOTE: we updated the section on assignments and exercises (8-6). Also, mind the examination date. Included is a directory with large slides (8-6). Included is a powerpoint with the procedure of calculating response times (16-6).




This course is organized around the issue of real-time requirements and their impact on the hardware-software architecture of a system. This includes:

·         examples of applications with real-time requirements;

·         the techniques used to enforce real-time properties in a verifiable manner (e.g., real-time scheduling, Quality of Service management);

·         examples of particular problems and solutions.

The considered system domain will the hardware software interface of most notably, (networked) embedded systems and (multi)processing architectures. Applications are drawn from real-time control and multimedia applications such as video streaming.

This year is the first time that the course is tought. We expect to be on a learning curve so it won’t be perfect, unfortunately.

There will be 8 weeks of regular lectures (rather than 9 because of an unfortunate assignment of holidays to Mondays). Some parts of the lectures may be used for small exercises which will be given as homework assignments. The course is completed by passing the final examination and doing a practical assignment. The assignment has to be completed before the start of the new term in September and can be done with groups of 2 students. These groups must hand in their own, original work, programmed and reported by themselves.

On this site we will maintain the current status of the course in terms of the contents, expected reading, assignments and presented slides.

Course program (tentative)

Week 1 (29-03): Introduction, Examples, Specification concepts, Reference model

Week 2 (05-04): Scheduling policies, scheduling analysis. Expected reading: references 1 and 3. We do expect that you study these.

Week 3 (12-04): holiday

Week 4 (19-04): continued from previous, see reference 6 [we try to get an online version]

Week 5 (26-04): Fixed priority scheduling & resource reservation. We expect you to study reference 7. Reference 6 may be helpfull as well.

Week 6 (03-05): cnt’d: Overview of previous lecture, CE terminal architecture

Week 7 (10-05): midterm break

Week 8 (17-05): Overview of previous, Earliest Deadline First, Mapping, Real-time operating systems and POSIX, study reference 13.

Week 9 (24-05): Guest speaker: prof. dr. Fohler, Time triggered and event triggered systems

Week 10 (31-05): holiday

Week 11 (07-06): Distributed video: QoS in real-time distributed systems

Week 12 (14-6): Distributed clock synchronization, Real-time databases

Most of these slides are also contained in a directory with large versions. An description of the procedure to construct worst-case response time is found here.

Time & Location: Monday, 13.30-15.30, AUD 2.

Examination: there will be a final exam on June 23, 14.00-17.00 with a reprise on August 13, 14.00-17.00. It is allowed to use copies of the slides at the exam, and the articles referred to on the site. In addition, there will be an assigment to be handed out after week 5.

Assignment: We propose to you a choice of four assignments. Since we do not know the platform you can use, we include one option that is entirely theoretical. You are allowed to use any sources to support your work but you have to hand in your own original work, including relevant references (especially those that you based your work on). Any attempt of fraud will be taken very seriously. Comments on the exercises are welcome, reasonable adjustments are ok. The idea is that it takes you roughly one week and deepens your insight so, if times becomes a problem please contact us. If usefull we will make a FAQ for the exercises. Note: we have to review these exercises internally so there may be small adaptations later.

·         Exercise A: producer/consumer with different rates, updated 8-6-04.

·         Exercise B: Evaluate performance and predictability of POSIX primitives

·         Exercise C: Distributed clock synchronization

·         Exercise D: Elevator system architecture

·         ... these files in pdf format

The assignment is due the first day of the next term (September 1, 2003, hand it in to Lukkien). Not making this is failing. There will be no acceptance after this date. You are expected to work in couples.


J.J. Lukkien

HG 5.07, tel.: 5147


          HG 5.08, tel.: 8209 (secr.)


          HG 5.09, tel.: 5412


Literature:there is an enormous amount of information available on the internet, including complete courses like ours. Just playing 5 minutes with Google wil bring you more information than is reasonable to list here. For the course we don’t use a particular book since they are quite expensive and none covers all the subjects. The slides together with the selected articles should be enough. The slides are nevertheless based on the books and we recommend to buy and study at least one of the books.


Additional exercises:

·        Assigning priorities

·        Virtual time



·        G.C. Butazzo, “Hard real-time computing systems, predictable scheduling – algorithms and applications”, Kluwer Academic Publishers, 1997, ISBN 0-7923-9994-3

§         remarks: good and clear discussion of real-time scheduling; not much besides that

·        J.W.S. Liu, “Real-time systems”, Prentice-Hall, 2000, ISBN 0-13-099651-3

§         remarks: in-depth discussion of scheduling, many different situations, mathematically fairly complete, less on the mapping onto RTOS and on RT-communication.

·        C.M. Krishna, K.G. Shin, “Real-time systems”, McGraw-Hill Computer Science series, 1997, ISBN 0-07-114243-6.

§         remarks: more complete discussion with respect to the system context.

·        A.Burns, A. Wellings, “Real-time systems and programming languages 3rd ed.”, Addison-Wesley, 2000, ISBN 0-201-72988-1.

§         remarks: discussion entirely within the scope of software. Perhaps this book which will be the most valuable for CS-graduates for their professional life.

·        B.O. Gallmeister, POSIX.4, Programming for the Real World, O’Reilly & Associates INC, 1995, ISBN 1-56592-074-0

·        D.R. Butenhof, Programming with POSIX threads, Addison-Wesley professional computing series, 1997, ISBN 0-201-63392-2.



1.       Sha, Rajkumar & Lehockzky. “Priority inheritance protocols: An apprach to real-time synchronization”, IEEE Transactions on Computers, vol.39, 1990.

2.       R.L. Graham, “Bounds on Multiprocessing Timing Anomalies”, SIAM Jour. Appl. Math., 17 (1969), 416-429.

3.       C.Liu, J.Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-time Environment”, JACM 20(1), 1973, pp.40-61.

4.       M. Dertouzos, Control robotics: the procedural control of physical processes, in Proceedings of IFIP Congress, 1974, pp. 807-813.

5.       M. Joseph, P.Pandya, Finding Response times in a real-time system, The Computer Journal, Vol..29, nr.5, 1986.

6.       O. Redell and M. Sanfridson, Exact best-case response time analysis of fixed priority scheduled tasks, Proceedings of the 14th Euromicro Conf. on Real Time Systems ECRTS, pp. 165-172, June 2002.

7.       R.J. Bril, E.F.M. Steffens, and W.F.J. Verhaegh, Best-case response times and jitter analysis of real-time tasks, Journal of Scheduling, 7(2): 133-147, 2004.


NOTICE: clicking the above link results in a request for payment of $25,00. So, rather than following the link, look up the paper through the main page of the university (through the library). When you do that at the university you will get it directly. Again, we are not allowed to put the text there by ourselves.


8.       M.H. Klein, T. Ralya, B. Pollak, R. Obenza, and M. González Harbour, A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems, Kluwer Academic Publishers (KAP), 1993.

9.       R. Obenza, Guaranteeing real-time performance using RMA, Embedded Systems Programming, pp. 26-40, 1994.

10.   M. González Harbour, M.H. Klein, and J.P.Lehoczky, Fixed Priority Scheduling of Periodic Tasks with VaryingExecution Priority, In: Proc. 12th IEEE Real-Time Systems Symposium (RTSS), pp. 116 – 128, 1991.

11.   M. González Harbour, M.H. Klein, and J.P.Lehoczky, Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority, In: Proc. 12th IEEE Real-Time Systems Symposium (RTSS), pp. 116 – 128, 1991.

12.   A.M. Groba, A. Alonso, J.A. Rodriques, M. Garcia Valls, Response time of streaming chains: analysis and results, In: Proc. 14th IEEE Euromicro Conference on Real-Time Systems, pp.182 – 189, 2002.

13.   L. Sha, J. Lehoczky, and R. Rajkumar, Solutions to some practical problems in prioritized preemptive scheduling, In: Proc. 7th IEEE Real-Time Systems Symposium (RTSS), pp. 181 –191, 1986.

14.   C.W. Mercer and S. Savage and H. Tokuda, Processor Capability Reserves: Operating System Support for Multimedia Applications, In: Proc. International Conference on Multimedia Computing and Systems (ICMCS)", pp. 90-99, May 1994.

15.   [Rajkumar et al 98] R. Rajkumar and K. Juvva and A. Molano and S.Oikawa, Resource Kernels: A Resource-Centric Approach to Real-Time and Multimedia Systems, In: Proc. SPIE Vol. 3310, Conference on Multimedia Computing and Networking, pp. 150-164, January 1998.

16.   L. Steffens, G. Fohler, G. Lipari, G. Buttazzo, Resource Reservation in Real-Time Operating Systems – a joint industrial and academic position, In: Proc. International Workshop on Advanced Real-Time Operating System Services (ARTOSS), pp. 25 –30, July 2003.

17.   R.J. Bril, C. Hentschel, E.F.M. Steffens, M. Gabrani, G.C. van Loo, and J.H.A. Gelissen, Multimedia QoS in consumer terminals (invited lecture), In: Proc. IEEE Workshop on Signal Processing Systems (SIPS), pp. 332 – 343, September 2001.

18.   C. Lee, J. Lehoczky, R. Rajkumar, and D. Siewiorek, On quality of service optimization with discrete QoS options, In: proc. 5th IEEE Real-Time Technology and Applications Symposium (RTAS), pp. 276 – 286, 1999.

19.   L. Steffens, S. van Loo, and C. Otero Perez, Trends in Operating Systems – Resource Management for Future CE Systems (invited lecture), ESTIMEDIA Workshop,, October 2003.

20.   C.C. Wüst and W.F.J. Verhaegh, Quality control for Scalable Media Processing Applications, Journal of Scheduling, 7(2): 105-117, March 2004.