Real Time Systems

Course: COL 720
Semester II, 2021-22
Credits: 4 (3-0-2)



Instructor: Prof. Smruti R. Sarangi

Lectures
: Slot E

Piazza link:     piazza.com/iit_delhi/spring2022/col720
Course Load:  Minor (20%), Major (30%), Assignments (40%) (three assignments),  Term paper (10%) 

Office Hours: Just send me an e-mail.

Passing Criteria: Minimum 25% in both theory and assignments. Overall: 30%.
                             Audit pass: Minimum 25% in both theory and assignments. Overall: 40%



Teaching Assistants:

1. Priyanka Singla


Reference Books
[Textbook]  Real-Time Systems: Theory and Practice by Rajib Mall

                    All the slides are being used with the authors' permission. The videos are based on the original slides of Prof. Rajib Mall (IIT Kharagpur). They have also been created with the authors' permission. Some minor modifications have been made. The author (Prof. Mall) is not responsible for any errors of omission and commission insofar as the modifications and the videos are concerned.

Lectures and Slides:

Week
Lecture
Topics
Link to the Video
Week 1 1 Introduction
  2 Basic terminology and the design space
  3 Modeling timing constraints using FSMs  
Week 2 4 Basics of scheduling
  5 Cyclic and table-driven scheduling
  6 EDF
Proof of the optimality of EDF
Week 3 7

RMS
[Paper] Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Liu and Layland, Journal of the ACM, 1973

[Paper] The Rate Monotonic Scheduling Algorithm: Event Characterization and Average Case Behavior, Lehoczky, Sha, and Ding. IEEE Real Time Systems Symposium, 1989

  8 DMS
[Paper] Deadline Monotonic Scheduling, Audsley, 1990
  9 RMS Extensions
Week 4 10 Insufficient priorities and task jitter
  11 Types of priority inversions
  12 Priority Inheritance Protocol and Highest Locker Protocol
Week 5 13 Priority ceiling protocol
  14 Analysis of the inversions in the PCP protocol
  15 Global and partitioned scheduling in multiprocessors
  16 Limits to multiprocessor scheduling, distributed scheduling algorithms
Week 6 17 Clock synchronization, GPS, Cristian's algorithm
  18 Clock synchronization with Byzantine clocks, RTOS fundamentals
Week 7 19 HW for real time systems, timers, features of modern OSes
Week 8 20 Monolithic vs micro-kernels
  21 Structure of Windows NT, priority levels and scheduling issues
  22 Open source software, POSIX standards, AEPs, signals and thread extensions
Week 9 23 Types of RTOSs, PSOS, Issues in making Linux real time
  24 Montavista Linux, RTLinux, Virtual layers: RTAI and Xenomai
  25 Commercial RTOSs: ECOS, muCOS, VRTX, VXWorks, Lynx, QNX/Neutrino, OSEK-VDX
Week 10 26

Win CE kernel, virtual memory, interrupt handling
Android Dalvik VM, process priorities

  27 TinyOS, Benchmarking: Rhealstone metric, Tridimensional measure, determinism and latency benchmarks
  28 Quality of service: delay and jitter, CBR, VBR, and sporadic communication, CAN and LIN buses, Token ring architecture, Ethernet and wireless networks
Week 11 29 Real time LAN communication: global priority based protocols, bounded access protocols, IEEE 802.4 and IEEE 802.5 protocols, RETHER, performance evaluation
  30.1 Traffic characterization in real-time WAN networks, Unicast and multicast routing, RSVP protocol, Traffic shaping with token buckets and leaky rate control
  30.2 Work-conserving and non-work-conserving service disciplines, FCFS queuing, Mult-level framing, Rate-controlled static priority, IntServ and DiffServ
  31 Real time databases: absolute and relative validity, basic concurrency protocols, ACID semantics, 2PL, 2PL-WP, 2PL-HP, OCC Sacrifice and Broadcast-Commit protocols