Pick your Poison

Here are some possible projects you can chose for the exam. They are ordered by increasing difficulty (simple projects will result in an increase up to 1 point, middle projects will result in an increase up to 3 points, and difficult projects can arrive to an increase of 4 points).

Simple Projects

• Write a tool for designing/implementing real-time applications using cyclic executive or multiple periodic real-time tasks (threads or processes) scheduled by fixed priorities. The tool accepts as input a set of tasks (described through periods and WCETs - optional: add relative deadlines), and the task bodies implemented in C (something similar to cyclic_test.c). If cyclic executive is selected, the tool computes the minor cycle and the major cycle, generates a proper schedule, and generates the C code for the executive. If priority scheduling is selected, the tool assigns the proper priorities to the tasks, and generates the C code for a real-time application creating a thread (or process) per task, implementing periodic behaviours, assigning the proper priorities, etc... In any case, the schedulability of the system must be checked before generating the application's code. Optional: if using threads, make every job non-preemptable (and run the proper schedulability check). The tool can be written in C or C++, and it must generate C code that compiles without warnings. The tool should not have a graphical interface (do not waste time in it: it will not improve the evaluation of the project), and must be non-interactive (controlled through command-line parameters).
• Write a program that checks the schedulability of a task set scheduled through fixed priorities (optional: add support for generic priority assignments - even non optimal), using both response time analysis and time demand analysis (the analysis must consider shared resources, but not nested critical sections). All the iterative steps for computing the worst-case response time must be printed. All the demanded time computations for all the considered scheduling points must be printed. Optional: output the schedule on the screen (using GTK) or on a file (in xfig or SVG format). The program must be non-interactive (controlled through command-line parameters).

Medium Difficulty

• Write a set of shell scripts allowing to create a ramfs or initrd for embedded systems (a half-working example, which does not support all the required features, is here). The scripts must not have external dependencies and must support cross-compilation (optional: allow to build the cross-compiler). The inclusion of custom programs, kernel modules, or boot scripts in the image must be supported. The shell script must be non-interactive (controlled through command-line parameters. Use "getopt" to parse them). The size of the initramfs must be reduced to the minimum. The resulting image must be able to run in Qemu.

• As the previous project, but support for eglibc, uclibc, klibc, or the musl libc is required instead (optional: provide generic support for any embedded C library). Implement some kind of simple real-time application using real-time priorities (and maybe accessing the hardware at low level), and install it in an initramfs using the scripts. The application must automatically start at boot.
• Write a real-time application simulating a (simple) physical system to be controlled and a controller for it. The "physical system simulator" is a POSIX process which periodically:
  • Reads some actuator values (produced by the controller) from a non-blocking pipe (if no value is present, the previous value is reused. If more values are present on the pipe, only the last one is used)
  • Iteratively solve the differential equation that describes the system, computing an output value based on the actuator values and the internal system state
  • Sends an output value (for example, the pendulum position) to the controller through a real-time signal
  The controller is a POSIX process composed by some threads:
  • A "sampling thread", which periodically receives the output value from the physical system simulator
  • One (or more) "control thread", which periodically receive the sampled value computing new actuator values
  • An "output thread", which periodically sends the actuator values to the system simulator process
  Some of the threads must be periodic (remember to motivate how the period are chosen, based on control theory). Processes and threads must be scheduled according to Rate Monotonic or Deadline Monotonic, and priorities must be properly set.
• Write a multithreaded application that simulates a physical system and a controller for it, similarly to previous project (the difference is that this project can use a simpler implementation, without processes and real-time signals). At least three threads are needed: a thread simulating the physical system, at least one thread implementing the controller, and a thread displaying the output on the screen. All the threads are periodic (compute the periods in the correct way, according to control theory), communicate through shared memory (use mutexes and condition variables to synchronize them), and are scheduled using RM or DM (assign the proper priorities). The application must output a control performance metric. The application must be implemented using POSIX threads, and must run at least on three systems between Linux, RTLinux, RTAI, Xenomai, and L4 (Drops, or L4KA).
• Install a microkernel-based real-time OS (for example, Drops) and test some simple real-time applications on it. Perform some latency measurement, and compare the latency with the one achieved on L4Linux, and on a regular Linux kernel
• Measure and compare the latencies experienced on some simple real-time systems of your choice (Xenomai, Preempt-RT, etc...)

• Write a Real-Time application that captures audio using ALSA and performs some kind of digital signal processing on it. The application must be composed by multiple processes or threads, (a task capturing the audio, one or more tasks processing it in some way, maybe a task displaying a spectrogram in real-time), and must be able to show that using real-time techniques it is possible to reduce the ALSA overruns / underruns.
• Write a Real-Time oscilloscope (using ALSA for input), using a multitask design. The output can be performed by using the frame buffer device, GTK, or SDL. The ALSA input buffers (and buffer size) must be reduced to the minimum, to minimize the latency. Real-Time techniques must be used to reduce such buffers.
• Write a real-time scheduling simulator able to simulate the schedule of generic real-time task sets (variable execution times, variable inter-arrival times) on multiprocessor (implement the real-time scheduling algorithm you prefer, but make it easily customisable).
• Write a real-time applications creating a set of periodic real-time tasks (threads or processes). Every task should have a specified period and should execute for a specified time (number of tasks, periods, and execution times should be configurable via command line options). Measure the distribution of the response times for each task. Optional: perform response-time analysis, and check if the response times match the theory. Optional 2: add some non real-time tasks in background that cause high kernel latencies. Estimate the worst-case kernel latency by comparing the measured response times with RTA

Difficult Projects

• Like the previous project, but execution times and periods are not fixed: for each task, the user can specify a Probability Mass Function (PMF) of the execution times and a PMF of the inter-arrival times. Check how the measured response times compare with worst-case analysis
• Implement the sporadic server, an EDF scheduler, or a real-time scheduler of your choice in the Linux scheduler
• Implement a Real-Time thread API (for example, the HARTIK API, or the RTAI API) by using POSIX threads, and/or by using a user-level threading library such as GNU Pth. Write a simple real-time application using this API, and test it on the Preempt-RT Linux kernel.
• Measure the unpredictabilities generated by the migration overhead in an SMP (or multi-core) system running a global fixed priorities scheduler.
• Port HLS for Linux to a newer (3.x) kernel (maybe rewriting from scratch might be simpler).
• Implement the stochastic analysis of periodic task sets scheduled by fixed priorities, as described in the paper "Stochastic Analysis of Periodic Real-Time Systems". To simplify things, you can implement a program generating the transition matrix P (from Equation 4 - and following - in the paper). Then, the eigenvalues problem can be solved by truncating P and using octave or similar programs

General Rules

When starting to work on a project, send me an email, and I'll send you additional some additional information.

If you have doubts, or find some problems developing the project, email me before wasting too much time. During the development of the project, I'll be available for clarifications, suggestions, and explainations.

Before the exam, you will have to send me an email with the complete source code, instructions about how to use it, and a small report (less than 8 pages, in text format). In particular, you will have to motivate your design decisions (why you used threads / processes, how you chose the number of tasks, how you assigned periods, deadlines and priorities, etc...).

Remember, the goal of the project is to show that you studied and understood the theory explained during the course.

If you use a source code management system such as CVS, subversion, or git (this is a plus), a changelog automatically obtained from the SCM ("git log", or similar commands) is welcome and might add some points to the evaluation (if it shows a correct development process).

Note that:

• C and C++ programs MUST compile without warnings when the -Wall switch is used.
• The code should be properly indented (some broken editors mix tabs and spaces, resulting in unreadable code). In general, the "indent" command is your friend (see "man indent").

Please read the notes about C programming and makefiles before starting to code.