Real-Time Systems (2IN26) autumn 2010 (for BIS, CSE, and ES)

 

Last update: April 16th, 2011.

 

News:

-      April 16th, 2011: Partial exam 2YN26 with draft answers of Monday, April 11th made available.

-      February 7th, 2011: Partial exam 2YN26 with draft answers of Thursday, January 20th made available.

-      January 31st, 2011: Partial exam 2XN26 (reprise) with draft answers of Thursday, January 20th made available.

-      January 10th, 2011: “Reading guide” for 2YN26 uploaded.

-      December 1st, 2010: Re-schedule of student presentations.

-      November 19th, 2010: Assignments allocated to groups, schedule of assignments changed.

-      November 12th, 2010: Assignments added.

-      November 4th, 2010: Partial exam 2XN26 with draft answers of Wednesday, November 3rd made available.

-      October 20th, 2010: “Reading guide” for 2XN26 updated.

-      October14th, 2010: “Expected reading” split in two parts: 2XN26 and 2YN26.

-      October 11th, 2010: [Stanovich et al 10] added to the “Expected reading” list.

-      September 20th, 2010: Erroneous hyperlinks to previous examinations corrected.

-      September 15th, 2010: Errata extended.

-      September 15th, 2010: [Stankovic 92] made available via StudyWeb and added to list of expected reading.

-      September 14th, 2010: Prof. Dr.-Ing.habil C. Hentschel will give guest-lectures on Thursday, December 16st and Friday, December 17th.

-      September 14th, 2010: Dr. Damir Isovic will give guest-lectures on Thursday, October 21st and Friday, October 22nd.

-      September 7th, 2010: Location change on Thursdays during the first quartile; from Pav. M23 to Bldg. Helix, HEC 0.01.

 

Examinations

 

The examinations (including draft answers) of (previous years of) 2IN20 (!):

Examinations (including draft answers) of 2IN25 (!):

Examinations (including draft answers) of 2IN26:

·         2010/2011: November 3rd, 2010 (2XN26), January 20th, 2011 (reprise 2XN26), January 20th, 2011 (2YN26), April 11, 2011 (2YN26).

 

Notes:

·         2IN20 is a 4 ECTS credits BaMa predecessor of 2IN26.

·         2IN25 is a 5 ECTS credits BaMa predecessor of 2IN26.

 

Introduction

 

The course addresses basic concepts of real-time systems, presents examples of real-time systems, covers real-time systems analysis and design, and gives an in-depth treatment of timing analysis and scheduling. The course is organized around the issue of real-time requirements and their impact on the architecture of a system. The considered system domain will be networked embedded systems. Applications are drawn from automotive domain (e.g. real-time control) and multi-media applications, such as video streaming.

This year, there are 16 weeks of regular lectures, divided in 2 quartiles. Some parts of the lectures will be used for small exercises which will be given as homework assignments. Students are expected to make those assignments prior to the lecture and will be invited to present their solutions during the lecture. The course is completed by passing both partial examinations and doing an obligatory assignment. The assignment involves studying one or more articles (or doing a practical work), writing a report, and giving a presentation. The assignment can be done with groups of 4 or 5 students. These groups must hand in their own, original work, reported by themselves.

On this site the current status of the course will be maintained in terms of the contents, and expected reading. Assignments and presented slides will only be available from StudyWeb.

Course objectives (high-level):

The objective of this course is to bring students into the position to analyze and (partially) design real-time systems, and conduct research in the area of real-time systems.

Course objectives (lower-level):

The student can:

(i)                   explain and apply the fundamental concepts and terminology of real-time systems;

(ii)                 explain and address the fundamental problems of real-time systems;

(iii)                analyze real-time systems designs;

(iv)                design a real-time system (at least partially); and

(v)                 identify and assess the relevant literature and research trends of real-time systems.

Course program (see last year’s 2IN25 course for a preliminary course program)

Quartile 1 (August 30th – November 7th):

Week 1 (02-09): RTS.A1-Overview, RTS.A1-Introduction;
           (03-09): No lectures (Recap for 2IN60: 2IN60.prior-knowledge-I, OS-Processes & Threads);

Week 2 (09-09): RTS.B3-Specification-concepts, RTA.D0-Water-Vessel, RTS.B3-Reference Model;
           (10-09): No lectures (Recap for 2IN60: 2IN60.prior-knowledge-II, OS-Atomicity);

Week 3 (16-09): RTS.B3-Reference Model (cntd), RTS.B4-Policies-1;
           (17-09): RTS.Exercises-1;

Week 4 (23-09): RTS.B4-Policies-1 (ctnd), RTS.B5-Analysis-1-Basics;
           (24-09): RTS.Exercises-2;

Week 5 (30-09): RTS.B5-Analysis-2-FPPS;
           (01-10): RTS.Exercises-3;

Week 6 (07-10): RTS.B5-Analysis-2-FPPS-overview, RTS.B4-Policies-2-FP-servers;
           (08-10): RTS.B4-Policies-3-RAP;

Week 7 (14-10): RTS-Exercises-3 (cntd), RTS-Exercises-5, RTS.B5-Analysis-5-FPPS-extensions;
           (15-10): RTS-Exercises-8;

Week 8 (21-10): Guest-lecture by Dr. Damir Isovic from the Mälardalen University of Västerås, Sweden.
           (22-10): Guest-lecture by Dr. Damir Isovic from the Mälardalen University of Västerås, Sweden.

Week 9 (28-10): No lectures (examination week)!
           (29-10): No lectures (examination week)!

Week 10 (04-11): No lectures (examination week)!
             (05-11): No lectures (examination week)!

Quartile 2 (November 8th – January 30th):

Week 11 (11-11): RTS.B5-Analysis-6-FPPS-arbitrary-deadlines, RTS.B5-Analysis-7-FPDS;
             (12-11): No lectures (lecturer ill);

Week 12 (18-11): RTS.Exercises-6
             (19-11): RTS.D1 QoS for MCTs

Week 13 (25-11): RTS.Exercises-7, RTS.B5-Analysis-8-FPDS-pessimistic, RTS.B5-Analysis-9-practical-factors
             (26-11): RTS.B5-RT Communication

Week 14 (02-12): No lectures (granting additional preparation time for assignments and presentations)
             (03-12): Presentations by students: Assignment 1 (groups 12, 15, 4)

Week 15 (09-12): Presentations by students: Assignment 6 (group 2), Assignment 11 (group 6)
             (10-12): No lectures (“Open day”)

Week 16 (16-12): guest lectures by Prof.Dr.-Ing.habil. C. Hentschel from the Brandenburg University of Technology of Cottbus, Germany.
             (17-12): guest lectures by Prof.Dr.-Ing.habil. C. Hentschel from the Brandenburg University of Technology of Cottbus, Germany.

Week 17 (23-12): No lectures (Christmas Holidays)!
             (24-12): No lectures (Christmas Holidays)!

Week 18 (30-12): No lectures (Christmas Holidays)!
             (31-01): No lectures (Christmas Holidays)!

Week 19 (06-01): Presentations by students: Assignment 2 (groups 5, 1, 17)
             (07-01): Presentations by students: Assignment 3 (group 11), Assignment 4 (group 16) & Assignment 5 (group 9)

Week 20 (13-01): Presentations by students: Assignment 7 (group 14) and Assignment 8 (group 13)
             (14-01): Presentations by students: Assignment 9 (group 10) & Assignment 10 (group 8)

Week 21 (20-01): No lectures (examination week)!
             (21-01): No lectures (examination week)!

Week 22 (27-01): No lectures (examination week)!
             (28-01): No lectures (examination week)!

RTA Reading guides: 2XN26 and 2YN26.

Time & Location:

Quartine \ Day

Thursday: 13.45 – 15.30

Friday: 13.45 – 15.30

1

HEC. 0.01

Pav. B1

2

Pav. M23

Pav. B1

Examination: There will be two partial exams, the first one 2XN26 in Semester A in October/November 2010 and the second one 2YN26 in January 2011. There will be a reprise for both partial examinations. You are not allowed to take any information with you to the examination! Next to the exam, there will be an assignment.

Visualization tools

·         Realtime

Assignments: Not making this is failing. There will be no acceptance after the examination date of the second partial exam. You are expected to work in teams.

·         Guidelines for RTS assignments

·         Overview of assignments

·         Assignment 1: Analysis for H-FPPS – independent applications (3x)

·         Assignment 2: Analysis for H-FPPS – dependent applications (3x)

·         Assignment 3: Improved analysis for H-FPPS (1x)

·         Assignment 4: Upper bounds for worst-case response times (1x)

·         Assignment 5: FPS with limited preemption (1x)

·         Assignment 6: Worst-case execution-time problem – Overview of methods and survey of tools (2x)

·         Assignment 7: Integrating Time-Triggered tasks in mC/OS-II (2x)

·         Assignment 8: Preemption thresholds in mC/OS-II (2x)

·         Assignment 9: Electric Lupo (1x)

·         Assignment 10: Swift mode changes based on FPPS & SRP (1x)

Lecturers:

R.J.Bril (main lecturer)

          HG 5.09, tel.: 5412

 

Guest lecturers:

  • Dr. D. Isovic, Mälardalen University of Västerås (S);
  • Prof. Dr.-Ing.habil C. Hentschel, TU Cottbus (D);

 

Book: G.C. Buttazzo, “Hard real-time computing systems, predictable scheduling – algorithms and applications”, Springer, 2005, ISBN 0-387-23137-4 (2nd edition).

Related slides: http://feanor.sssup.it/~giorgio/slides/realtime/;

Errata: http://feanor.sssup.it/~giorgio/errata-HRT2.pdf.

Additional errata: Errata.

Expected reading:

·         For 2XN26 (final):

[1]  Risk Forum: What really happened on Mars Rover Pathfinder, December 1997.

[2]  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.

[3]  D. Polock and D. Zoebel,Conformance testing of priority inheritance protocols, In: Proc. 7th IEEE International Conference on Real-Time Computing Systems and Applications (RTCSA), pp. 404-408, December 2000.

[4]  J.A. Stankovic, Real-Time Computing, Byte, pp. 155 – 160, August 1992.

[5]  M. Stanovich, T.P. Baker, A.I. Wang, and M. González Harbour, Defects of the POSIX Sporadic Server and How to Correct Them, In: Proc. 16th IEEE RTAS, pp. 35 – 45, April 2010.

·         In addition for 2YN26 (final):

[6]  L. Almeida and P. Peidreiras, Scheduling with temporal partitions: response-time analysis and server design, In: Proc. 4th ACM International Conference on Embedded Software (EMSOFT), pp. 95 - 103, September 2004.

[7]  M. Behnam, Insik Shin, T. Nolte, and M. Nolin, SIRAP: A synchronization protocol for hierarchical resource sharing in real-time open systems, In: Proc. 7th ACM & IEEE International Conference on Embedded Software (EMSOFT), pp. 279 – 288, September 2004.

[8]  M. Bertogna, N. Fisher, and S. Baruah. Static-priority scheduling and resource hold times, In: Proc. 15th International Workshop on Parallel and Distributed Real-Time Systems, pp. 1-8, March 2007.

[9]  R.I. Davis and A. Burns, Hierarchical Fixed Priority Pre-Emptive Scheduling, In: Proc. 26th IEEE Real-Time Systems Symposium (RTSS), pp. 389-398, December 2005.

[10]       R.I. Davis and A. Burns, Resource sharing in Hierarchical Fixed Priority Pre-Emptive Systems, In: Proc. 27th IEEE Real-Time Systems Symposium (RTSS), pp. 257-267, December 2006.

[11]       R.I. Davis, A. Burns, R.J. Bril, and J.J. Lukkien, Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised, Real-Time Systems, ISSN 1573-1383 (online), http://www.springerlink.com/content/8n32720737877071/, January 30th, 2007, ISSN 0922-6443 (print), 35(3): 239-272, April 2007.

[12]       C. Hentschel, R.J. Bril, Y. Chen, R. Braspenning, and T.-H. Lan, Video Quality-of-Service for consumer terminals - a novel system for programmable components, In: IEEE Transactions on Consumer Electronics, 49(4): 1367-1377, November 2003.

[13]       I. Shin and I. Lee, Periodic resource model for compositional real-time guarantees, In: Proc. 24th IEEE Real-Time Systems Symposium (RTSS), pp. 2-13, December 2003.

[14]       L. Steffens, G. Fohler, G. Lipari, and 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.

Further reading (final):

[15]       R.J. Bril, J.J. Lukkien, and W.F.J. Verhaegh, Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption, Real-Time Systems Journal, ISSN 1573-1383 (online), DOI 10.1007/s11241-009-9071-z, http://www.springerlink.com/content/f05r404j63424h27, April 28th, 2009, ISSN 0922-6443 (print), 42(1-3): 63 – 119, August 2009.

[16]       G.C. Buttazzo, Rate Monotonic vs. EDF: Judgment Day, Real-Time Systems, 29(1): 5 – 26, 2005.

[17]       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.

[18]       J. Goossens and R. Devillers, The non-optimality of the monotonic priority assignments for hard real-time offset free systems, Real-Time Systems, 13(2): 107-126, September 1997.

[19]       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.

[20]       C. Hentschel, Scalable Video Algorithms for Resource Constrained Platforms, Workshop on Resource Management for Media Processing in Networked Embedded Systems, Ed. R.J. Bril and R. Verhoeven, pp. 43 – 50, March 2005.

[21]       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.

[22]       J.W.S. Liu, Real-Time Systems, Prentice Hall, 2000.

[23]       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.

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

[25]       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.

[26]       D. Zoebel and P. Polock and A. van Arkel, Testing for the Conformance of Real-time Protocols Implemented by Operating Systems, Electronic Notes in Theoretical Computer Science, Vol. 133, pp. 315- 332, May 2005. http://www.sciencedirect.com/science/journal/15710661