Final Preparation

22C:116, Fall 1995

1. Background: In hard real-time systems, computational events E must be performed at specific times for the system to be considered correct. Typically, for each event Ei, there are two times, Bi and Di, such that Bi<Di and the event Ei must occur at time t such that Bi<t<Di. We call Bi the beginning time for event Ei and Di the deadline time for event Ei, and we call the interval [Bi,Di] the service window for event Ei.

   Amulet, a real-time extension of Charm (see Homework 12), contains the following primitives:

   call( c, d, m )

   Calls char c prior to deadline d, passing message m.

   delayed_call( t, c, d, m )

   Calls char c after time t but prior to deadline d, passing message m.

   time()

   Returns the time; normal arithmetic operations apply to times.

   deadline()

   Returns the deadline under which the current char is operating.

   Amulet is non-preemptive (except to the extent that interrupts preempt the processor, and interrupt service routines merely schedule calls to chars). Scheduling Amulet uses deadlines -- of the pending calls to chars, the char with the earliest deadline is called first. Delayed calls are implemented by sorting the messages into order by delivery times and moving the messages to the scheduling list when the real-time equals the delivery time.

   Real-time systems frequently include what are called periodic real-time tasks. In such a task, there is a series of events Ei which must be performed periodically. That is, the service windows for Ei are equally spaced in time, or, formally, for all i in the periodic sequence, Di-Bi=W (the constant service window width for the series) and Di-D(i-1)=P (the constant period for the series).

   Another category of real-time process is the pseudoperiodic process. Such a process is very similar to a periodic process, but instead of having a well defined period, there is a constraint on the minimum and maximum interval between successive events Ei. Thus, if Ei occurs at time t, B(i+1)=t+min and D(i+1)=t+max, where min and max are constant for the task.

   Finally, there are non-periodic hard-real-time tasks. For these, the intervals between successive events Ei and E(i+1) are not based on constants. For each event Ei, there is a well defined Bi and Di, but these vary from one event to the next in the sequence.

   Think about how you would implement Amulet. What does the main program (the scheduler) look like? How does Amulet interact with the real-time clock hardware?

   Think about how you would code a periodic real-time task in Amulet. How would you code a pseudoperiodic real-time task?

2. Background: Throughout the semester, we have discussed a number of mutual exclusion mechanisms.

   Think about What is the minimum set of assumptions we have made about atomic operations supported by the hardware?

   Suppose you had a shared memory machine where the different CPUs had different width paths to memory, so one CPU operated, for example, on 128 bit words, while another used a 32 bit path, and yet another used an 8 bit path. Perhaps there is even a machine with a one-bit path to memory. Can you propose a solution to the mutual exclusion problem on this system?

3. Background: In DEMOS-MP, processes leave behind a forwarding address every time they migrate. Consider a DEMOS-MP system where processes are not dynamically created, but rather, where a fixed (but large) set of processes runs for a long time.

   Think about how the set of forwarding addresses grows with time as processes migrate. Does it grow without bound, or is there a limit? If there is a limit, the chain of forwarding addresses leading to a process is guaranteed to be of bounded length independant of the number of times the process has migrated. What structures may the graph of forwarding addresses for a process eventually take on? Can you prove that the structure of this graph is such that it will always be possible to get to a process from any machine on the net?

4. Background: In all of the distributed systems discussed in class, access to network resources was primarily protected by one or another form of capability.

   Think about whether or not access control lists can be applied to resource protection in distributed systems? Can you apply cryptographic security to ACLs?