Seminar: Real-Time Scheduling and Synchronization

Seminar (7CP)

Wintersemester 2012/2013

Content

Embedded real-time systems are pervasive in everyday technologies such as cars (e.g., engine control, anti lock brakes, etc.), airplanes (e.g., fly-by-wire), and robotics (e.g., signal processing, actuator control). Software in such safety-critical systems must be predictable in the sense that outputs should be produced always at the right time. For example, a car’s airbag is of little use if triggered only fractions of a second late. In general, real-time constraints arise whenever computers interact with the physical environment, or when users perceive delays as unacceptable (e.g., in GUIs, during video playback, audio processing, video gaming, etc.).

In this seminar, we will study the fundamental resource allocation policies that enable provably predictable real-time computing, first starting with classic uniprocessor results and then quickly advancing to recent papers on multiprocessor real-time systems.

Organization

When: regular meetings every Tuesday from 16:00 (c.t.) to 18:00, and occasionally on Thursdays (at the same time), unless noted otherwise.

Where: room 005, E1 5 (MPI-SWS building, UdS Campus).

Attendance policy: Seminars thrive on lively discussions. Therefore, attendance is mandatory. Absences require prior approval by the instructor (with the obvious exception of medical emergencies).

Paper topics will be assigned at the first organizational meeting on October 16th.

Requirements

The seminar consists of a writing, a presentation, and a participation component. Each student will present and summarize one paper.

Lecture: each student will present her/his assigned paper in a 30–45 minute presentation. The presentation will be graded both on factual correctness and presentation style. The goal of the presentation is to teach your fellow students the key insights and techniques in the paper. Do not attempt to provide a comprehensive summary, that is, you do not have to discuss every detail. Rather, convey the key ideas and the intuition underlying the solution.
Written summary: each student will summarize her/his assigned paper in a 4–8 page abstract. The written summary is due a day before the presentation and will be handed out to all participants. It should convey the key points of the papers and will be graded on correctness of both language and content. All text must be your own words or clearly marked as a quote. Plagiarism is unacceptable.
Participation: each participant is expected to actively participate in the discussion and to skim the paper under discussion prior to class. (Bring a copy to class for reference during discussion.)

The instructor reserves the right to deduct grade points for repeated failure to contribute in class.

Covered Papers

Liu, C. and Layland, J. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 30:46–61.
Audsley, N., Burns, A., Richardson, M., Tindell, K., and Wellings, A. (1993). Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284–292.
Sha, L., Rajkumar, R., and Lehoczky, J. (1990). Priority inheritance protocols: an approach to real-time synchronization. IEEE Transactions on Computers, 39(9):1175–1185.
Baruah, S., Burns, A., and Davis, R. (2011). Response-time analysis for mixed criticality systems. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 34–43.
Davis, R.I., Burns, A., Bril, R.J., and Lukkien, J.J. (2007). Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35(3):239–272.
Zhang, F. and Burns, A. (2009). Schedulability Analysis for Real-Time Systems with EDF Scheduling. IEEE Transactions on Computers, 58(9):1250–1258.
Abeni, L. and Buttazzo, G. (1998). Integrating multimedia applications in hard real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium, pages 4–13.
Baruah, S. (2007). Techniques for multiprocessor global schedulability analysis. In Proceedings of the 28th IEEE Real-Time Systems Symposium, pages 119–128.
Bertogna, M. and Cirinei, M. (2007). Response-time analysis for globally scheduled symmetric multiprocessor platforms. In Proceedings of the 28th IEEE Real-Time Systems Symposium, pages 149–160.
Burns, A., Davis, R., Wang, P., and Zhang, F. (2012). Partitioned EDF scheduling for multiprocessors using a C=D task splitting scheme. Real-Time Systems, 48(1):3–33.
Leontyev, H. and Anderson, J. (2010). Generalized tardiness bounds for global multiprocessor scheduling. Real-Time Systems, 44(1):26–71.
Brandenburg, B. and Anderson, J., (2012). The OMLP Family of Optimal Multiprocessor Real-Time Locking Protocols. Design Automation for Embedded Systems, to appear. DOI: 10.1007/s10617–012–9090–1.
Ward, B. and Anderson, J. (2012). Supporting Nested Locking in Multiprocessor Real-Time Systems. In Proceedings of the 24th Euromicro Conference on Real-Time Systems, pages 223–232.

Meetings and Topics

Oct 30, 2012

Liu, C. and Layland, J. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 30:46–61.

Presenter: Ievgeniia Chekavska

Nov 6, 2012

Audsley, N., Burns, A., Richardson, M., Tindell, K., and Wellings, A. (1993). Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284–292.

Nov 13, 2012

Sha, L., Rajkumar, R., and Lehoczky, J. (1990). Priority inheritance protocols: an approach to real-time synchronization. IEEE Transactions on Computers, 39(9):1175–1185.

Presenter: Aastha Mehta

Nov 15, 2012

Baruah, S., Burns, A., and Davis, R. (2011). Response-time analysis for mixed criticality systems. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 34–43.

Presenter: Felipe Cerqueira

Note: Nov 15, 2012 is a Thursday (meeting in same location).

Nov 27, 2012

Zhang, F. and Burns, A. (2009). Schedulability Analysis for Real-Time Systems with EDF Scheduling. IEEE Transactions on Computers, 58(9):1250–1258.

Presenter: Florian Haupenthal

Nov 29, 2012

Davis, R.I., Burns, A., Bril, R.J., and Lukkien, J.J. (2007). Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35(3):239–272.

Presenter: Igor Vozniak

Note: Nov 29, 2012 is a Thursday (meeting in same location).

Dec 11, 2012

Abeni, L. and Buttazzo, G. (1998). Integrating multimedia applications in hard real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium, pages 4–13.

Presenter: Haluk Özduman

Dec 13, 2012

Introduction to Multiprocessor Real-Time systems [slides]

Presenter: Björn Brandenburg

Note: Dec 13, 2012 is a Thursday (meeting in same location).

Dec 18, 2012

Baruah, S. (2007). Techniques for multiprocessor global schedulability analysis. In Proceedings of the 28th IEEE Real-Time Systems Symposium, pages 119–128.

Presenter: Sergio Soto

Jan 15, 2013

Bertogna, M. and Cirinei, M. (2007). Response-time analysis for globally scheduled symmetric multiprocessor platforms. In Proceedings of the 28th IEEE Real-Time Systems Symposium, pages 149–160.

Presenter: Wenkai Dai

Jan 22, 2013

Burns, A., Davis, R., Wang, P., and Zhang, F. (2012). Partitioned EDF scheduling for multiprocessors using a C=D task splitting scheme. Real-Time Systems, 48(1):3–33.

Presenter: Alexander Wieder

Jan 29, 2013

Brandenburg, B. and Anderson, J., (2012). The OMLP Family of Optimal Multiprocessor Real-Time Locking Protocols. Design Automation for Embedded Systems, to appear. DOI: 10.1007/s10617–012–9090–1.

Presenter: Youcef Amine Benabbas

Feb 5, 2013

Ward, B. and Anderson, J. (2012). Supporting Nested Locking in Multiprocessor Real-Time Systems. In Proceedings of the 24th Euromicro Conference on Real-Time Systems, pages 223–232.

Presenter: Arpan Gujarati

Feb 7, 2013

Leontyev, H. and Anderson, J. (2010). Generalized tardiness bounds for global multiprocessor scheduling. Real-Time Systems, 44(1):26–71. Manohar Vanga

Presenter: Manohar Vanga