Further reading

Gallmeister [Gal95] provides a thorough and very readable introduction to POSIX in general and its real-time aspects in particular. Liu and Layland [Liu73] introduce rate-monotonic scheduling; this paper became the foundation for real-time systems analysis and design. The book by Liu [Liu00] provides a detailed analysis of real-time scheduling. Benini et al. [Ben00] provide a good survey of system-level power management techniques. Falik and Intrater [Fal92] describe a custom chip designed to perform answering machine operations.

Questions

Q6-1 Identify activities that operate at different rates in

Q6-2 Name an embedded system that requires both periodic and aperiodic computation.

Q6-3 An audio system processes samples at a rate of 44.1 kHz. At what rate could we sample the system’s front panel to both simplify analysis of the system schedule and provide adequate response to the user’s front panel requests?

Q6-4 Draw a UML class diagram for a process in an operating system. The process class should include the necessary attributes and behaviors required of a typical process.

Q6-5 Draw a task graph in which P1 and P2 each process separate inputs and then pass their results onto P3 for further processing.

Q6-6 Compute the utilization for these task sets:

Q6-7 What factors provide a lower bound on the period at which the system timer interrupts for preemptive context switching?

Q6-8 What factors provide an upper bound on the period at which the system timer interrupts for preemptive context switching?

Q6-9 What is the distinction between the ready and waiting states of process scheduling?

Q6-10 A set of processes changes state as shown over the interval [0,1 ms]. P1 has the highest priority and P3 has the lowest priority. Draw a UML sequence diagram showing the state of all the processes during this interval.

Q6-11 Provide examples of

Q6-12 For the following periodic processes, what is the shortest interval we must examine to see all combinations of deadlines?

Q6-13 Consider the following system of periodic processes executing on a single CPU (P1 has the highest priority and P4 the lowest):

Can we add another instance of P1 to the system and still meet all the deadlines using RMS?

Q6-14 Given the following set of periodic processes running on a single CPU (P1 has highest priority), what is the maximum execution time of P5 for which all the processes will be schedulable using RMS?

Q6-15 A set of periodic processes is scheduled using RMS; P1 has the highest priority. For the process execution times and periods shown below, show the state of the processes at the critical instant for each of these processes.

Q6-16 For the given periodic process execution times and periods (P1 has the highest priority), show how much CPU time of higher-priority processes will be required during one period of each of the following processes:

Q6-17 For the periodic processes shown below:

In each case, compute the schedule for an interval equal to the least-common multiple of the periods of the processes. P1 has the highest priority and time starts at t = 0.

Q6-18 For the periodic processes shown below:

In each case, compute the schedule for an interval equal to the least-common multiple of the periods of the processes. P1 has the highest priority and time starts at t = 0.

Q6-19 For the periodic processes shown below:

In each case, compute the schedule for an interval equal to the least-common multiple of the periods of the processes. P1 has the highest priority and time starts at t = 0.

Q6-20 For the given set of periodic processes, all of which share the same deadline of 12:

Q6-21 For the periodic processes given below, find a valid schedule

Q6-22 For the periodic processes and deadlines given below:

Q6-23 If you wanted to reduce the cache conflicts between the most computationally intensive parts of two processes, what are two ways that you could control the locations of the processes’ cache footprints?

Q6-24 A system has two processes P1 and P2 with P1 having higher priority. They share an I/O device ADC. If P2 acquires the ADC from the RTOS and P1 becomes ready, how does the RTOS schedule the processes using priority inheritance?

Q6-25 Explain the roles of interrupt service routines and interrupt service handlers in interrupt handling.

Q6-26 Briefly explain the dual-kernel approach to RTOS design.

Q6-26 What are the kernel-level units of execution in WinCE?

Q6-27 Draw a UML state diagram for the predictive shutdown mechanism of a cell phone. The cell phone wakes itself up once every five minutes for 0.01 second to listen for its address. It goes back to sleep if it does not hear its address or after it has received its message.

Q6-28 How would you use the ADPCM method to encode an unvarying (DC) signal with the coding alphabet {−3,−2,−1,1,2,3}?

Lab exercises

L6-1 Using your favorite operating system, write code to spawn a process that writes “Hello, world” to the screen or flashes an LED, depending on your available output devices.

L6-2 Build a small serial port device that lights LEDs based on the last character written to the serial port. Create a process that will light LEDs based on keyboard input.

L6-3 Write a driver for an I/O device.

L6-4 Write context switch code for your favorite CPU.

L6-5 Measure context switching overhead on an operating system.

L6-6 Using a CPU that runs an operating system that uses RMS, try to get the CPU utilization up to 100%. Vary the data arrival times to test the robustness of the system.

L6-7 Using a CPU that runs an operating system that uses EDF, try to get the CPU utilization as close to 100% as possible without failing. Try a variety of data arrival times to determine how sensitive your process set is to environmental variations.

L6-8 Measure the effect of cache conflicts on real-time execution time. First, set up your system to measure the execution time of your real-time process. Next, add a background process to the system. One version of the background process should do nothing, another should do some work that will invalidate as many of the cache entries as possible.