CS 3304 Solutions to Homework Assignment 5

CS 3304
Solutions to Homework Assignment 5
August 7, 1997

[15] 1.

A particular Ada program models two commodities, known as red and blue. There are producer and consumer tasks that produce and consume these commodities as follows:

Producer producer1 always produces three red's and one blue at a time;
Producer producer2 always produces one red and three blue's at a time;
Consumer consumer1 always consumes five red's and two blue's at a time;
Consumer consumer2 always consumes three red's and five blue's at a time; and
Consumer consumer3 always consumes four red's and four blue's at a time.

Each producer and consumer has its own Ada task.

Implement one or more Ada tasks to accomplish the buffering required by the above producer/consumer problem. Give a scenario in which your solution deadlocks. Explain how to avoid that deadlock.

To make the problem meaningful for Ada, assume that RED and BLUE are types declared and implemented elsewhere. Since there are two commodities that need to be represented independently, the best solution will use one buffer for each type. However, the two buffers need to be accessed in a protected fashion. Hence they should both be local to a single task.

We can accomplish this task by modifying the BUF_TASK task on pages 461-462. Figures and show the result.

Figure: Ada task to control two buffers (1 of 2)

Figure: Ada task to control two buffers (2 of 2)

Each of the two producers and three consumers needs a separate entry, since each has different demands on the buffers. It would be possible to have producer entry and one consumer entry if the demands on the buffers were always passed as parameters; however, see the deadlock concerns below.

The INSERT and REMOVE procedures are overloaded and are derived from generic procedures in Figure (see Section 8.8.1).

Figure: Getting insert and remove procedures from generics

The use of these procedures does extend the time of a rendezvous considerably, which may be undesirable.

Deadlock could occur if the buffer sizes were set too small. For example, if RED_BUFSIZE =5 and BLUE_BUFSIZE =5, then only repetitions of one of the two sequences

PRODUCER1,PRODUCER2,CONSUMER3

and

PRODUCER2,PRODUCER1,CONSUMER3

can occur. The first and second consumers are never serviced and hence are deadlocked. The solution is to have adequately large buffers. This solution may be impossible if the (arbitrary) demands of a producer or consumer are passed by parameters.

As a final thought, imagine being assigned the job of maintaining this code!

[15] 2.

Assume a program written in Ada has three tasks, searcher, builder, and printer, that are written to loop forever, each doing its own specialized job. Of course, an exception may cause one of these tasks to exit prematurely. You are to add a new task watcher to the program that also loops forever and that checks up on the health of each task every minute or so (see the Ada delay statement in section 9.6 of the reference manual). If a task has failed, then watcher restarts it.

When the Ada run time system is unable to start up a task or when a rendezvous fails for any reason, it raises the TASKING_ERROR exception.

Use Ada exception handling to implement the watcher task, and explain what changes need to be made to searcher, builder, and printer to accommodate the watcher task. If there are any limitations to your solution, point those out.

We assume that a task is healthy if it eventually rendezvous with the watcher task. Each of the three tasks must be written to get to a point where it will accept a rendezvous with watcher every few seconds. The entry in each task can be called watcher. Hence a call to printer.watcher is a health check on the printer task. The watcher entry does not need to have any action associated with it but should have alternate entries or a delay also available so that it does not suspend for many seconds waiting for the watcher task. See Figure for a possible skeleton for searcher.

Figure: A skeleton for the searcher task

The actual implementation Figure . We assume that restart is a function capable of restarting a failed task, with some exception handling abilities of its own, in case of a ``permanent'' failure.

Figure: The watcher task

[15] 3.

Chapter 14, Problem 5.

As a helper, we define the relation

notin(Element,List)

that is true if Element is not one of the elements in List. Then the relation

emptyintersection(List1,List2)

has three cases, depending on whether or not one of the two lists is empty. The Prolog program is:

notin(Element,[]).
notin(Element,[Head|Tail]) :- notin(Element,Tail), not(Element=Head).
emptyintersection(List,[]).
emptyintersection([],List).
emptyintersection([Head1|Tail1],[Head2|Tail2])
    :- notin(Head1,[Head2|Tail2]), notin(Head2,[Head1|Tail1],
       emptyintersection(Tail1,Tail2).

[15] 4.

Chapter 14, Problem 7.

The relation

last(List,Element)

is defined to be true if the last element of List is Element. If List is empty, then the relation is clearly false. As a consequence, we need only consider the two cases that List has one element or has two or more elements. Here is the Prolog program:

last([Head | [] ],Head).
last([Head1 | [Head2 | Tail]],Element) :- last([Head2|Tail],Element)

About this document ...

The command line arguments were:
latex2html -split 0 -t CS 3304 Solutions to Homework Assignment 5 solvehw5.

The translation was initiated by cs3304sm class account on Fri Aug 8 07:39:44 EDT 1997

cs3304sm class account
Fri Aug 8 07:39:44 EDT 1997