(
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
·
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.
Lecturers:
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:
Books:
· 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.
Articles:
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”,
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.
11.
M.
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, http://www.idt.mdh.se/estimedia/steffens.pdf, 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.