Seminar (7CP)

Wintersemester 2012/2013

Instructor: Björn Brandenburg

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.

**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**.

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.

- 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.

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

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.

Presenter: Aastha Mehta

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).

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

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).

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

Introduction to Multiprocessor Real-Time systems [slides]

Presenter: Björn Brandenburg

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

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

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

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

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

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

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