EXERCISES

E28.1 Printers

Complete the PRINTER class (page 934), implementing the job queue as a bounded buffer and making sure queue manipulation routines as well as print do not need to process the special "stop request" print job (print may have not j.is_stop_request as a precondition).

E28.2 Why import must be deep

Assume that a shallow import mechanism (rather than deep_import) were available. Construct an example that will produce an inconsistent structure --- one in which a separate object is attached to a non-separate entity.

E28.3 The "inheritance anomaly"

In the BUFFER example used to illustrate the "inheritance anomaly" ("Synchronization
for concurrent O-O computation", page 950), assume that each routine specifies the exit state in each case using a yield instruction, as in

put (x: G) is
  do
    "Add x to the data structure representing the buffer";
    if "All positions now occupied" then
      yield full
    else
      yield partial
    end
  end

Write the corresponding scheme for remove. Then write the class NEW_BUFFER with the added procedure remove_two and show that the class must redefine both of the inherited features (along with the specification of which features are applicable in which states).

E28.4 Deadlock avoidance (research problem)

Starting from the Business Card principle (page 960), investigate whether it is feasible to introduce a validity rule governing the use of non-separate actual arguments to separate calls and avoiding some of the possible resulting deadlocks. The rule should be reasonable (that is to say, it should not preclude commonly useful schemes), enforceable by a compiler (in particular an incremental compiler), and easily explainable to developers.

E28.5 Priorities

Examine how to add a priority scheme to the duel mechanism of class CONCURRENCY, retaining upward compatibility with the semantics defined in the presentation of procedures yield, insist and related ones. (See "Duels and their semantics", page 969)

E28.6 Files and the precondition paradox

Consider the following simple extract from a routine manipulating a file:

f: FILE;
...
if f /= Void and then f.readable then
  f.some_input_routine
    -- some_input_routine is any routine that reads
    -- data from the file; its precondition is readable.
end

Discuss how, in spite of the absence of obvious concurrency in this example, the precondition paradox can apply to it. (Hint: a file is a separate persistent structure, so an interactive user or some other software system can access the file in between the various operations performed by the extract.) Discuss what can happen as a consequence of this problem, and possible solutions.

E28.7 Locking

Rewrite the class LOCKING_PROCESS as an heir of class PROCESS. (Page 980; class PROCESS was on page 933.)

E28.8 Binary semaphores

Write one or more classes implementing the notion of binary semaphore. (Hint: start from the classes implementing locks.) As suggested at the end of the discussion of locks, be sure to include high-level behavior classes, meant to be used through inheritance, which guarantee a correct pattern of reserve and free operations. (See "Locks", page 978.)

E28.9 Integer semaphores

Write one or more classes implementing the notion of integer semaphore.

E28.10 Coroutine controller

Complete the implementation of coroutines ("Coroutines", page 982) by spelling out how the controller is created.

E28.11 Coroutine examples

The chapter on Simula presents several examples of coroutines. Use the coroutine classes of the pressent chapter to implement these examples.

E28.12 Elevators

Complete the elevator example ("An elevator control system", page 984)by adding all the creation procedures as well as the missing algorithms, in particular for selecting floor requests.