Study the
<A HREF="../P/sem_norc.sr">SR Program: A Semaphore Prevents the Race Condition.</A>
Explain exactly how the semaphore prevents undersirable interleaving of
instructions of the two processes.
<P>

<HR><P>

Study the
<A HREF="../P/sem_nor2.sr">SR Program: A Semaphore Prevents Another Race Condition.</A>
Why is the semaphore <CODE>mutex</CODE> in the <CODE>auditor</CODE> process?
What might happen if you took it out?
Can you verify your hypothesis with an experiment?
<P>

<HR><P>

Complete the following program, using general counting semaphores,
so that the processes are constrained to
terminate in the order: A (any copy), B (any copy),
A (any copy), A, B.
<PRE>
resource ABAAB()

sem ... # semaphore declarations and initializations

process A(i := 1 to 3)
   ... # P()'s and V()'s only
end A

process B(j := 1 to 2)
   ... # P()'s and V()'s only
end B

end ABAAB
</PRE>
<P>

Now, do it again using only binary semaphores (the semaphore can only take
on the values 0 and 1).
<P>

<HR><P>

<A NAME="MULPC">Bounded Buffer: Multile Producers and Consumers</A>
<P>

Study the
<A HREF="../P/sem_bbou.sr">SR Program: Bounded Buffer Producer and Consumer.</A>
Modify it so that the producer process is in its own resource and the consumer
process is in its own resource.
Then modify the program so that the producer process is created several
times and the consumer resource is also created several times (the number
of times for each is gotten from command line arguments).
Are there any race conditions introduced by having multiple producers access
the bounded buffer at the same time?
How about if multiple consumers access the buffer at the same time?
If so, prevent any such race conditions with one or more additional
semaphores.
<P>

This is Lab #4.5.2 (page 101) in the text. Using as guides the Example
Programs 2.15, 3.4, and 4.2 in the text, write a multi-resource,
multi-process SR program that has a single bounded buffer with size of
Nslots (default value 20), Nprods (default value 3) producer processes,
and Ncons (default value 5) consumer processes. The single bounded
buffer will be in its own resource. The producers will all be created
from one resource, and the consumers will all be created from one
resource. Therefore you will have four resources.
<P>

All default values should be overridable with command line arguments:
<PRE>
sr -o bbou bbou.sr
bbou Nslots Nprods Ncons Tprod Tcon Trun
</PRE>
<P>
where Tprod is the maximum producer nap() time to ``produce'' an item
and where Tcon is the maximum consumer nap() time to ``consume'' an
item.
<P>

Watch out for race conditions on the variable put_in if multiple
producers call deposit() at about the same time! Watch out for race
conditions on the variable take_out if multiple consumers call fetch()
at about the same time! These race conditions are of theoretical
interest only since in reality SR will not generate context switches
at a fine enough granularity to see the race condition. But practice
safe programming anyway.
<P>

Play around with the random number generator arguments, the buffer
size, the number of producers, the number of consumers, the producer
max nap time, and the consumer max nap time to get a buffer that
drifts between empty and full.
<P>

<HR><P>

Find another classical operating system synchronization problem and
write an SR program simulating it, using semaphores to protect
critical sections and synchronize the processes.
<P>

<HR><P>

Study the
<A HREF="../P/sem_dphi.sr">SR Program: The Dining Philosophers.</A>
Modify it so it is starvation-free, by introducing another state,
``very hungry''.
<P>

<HR><P>

Study the
<A HREF="../P/sem_rdwr.sr">SR Program: The Database Readers and Writers.</A>
Modify it so it is starvation-free, that is,
so that a continuous stream of arriving readers cannot starve a writer.
There are two ways to do this.
One is strict FIFO:
readers and writers queue up on the database
and enter in the order of their arrival
with any group of consecutive readers allowed to read at the same time.
The other way tries to allow a little more concurrent database access:
whenever a writer finishes, it sweeps into the database
<EM>all</EM> waiting readers,
even those that arrived after any waiting writer.
<P>

<HR><P>

Study the
<A HREF="../P/sem_slba.sr">SR Program: The Sleeping Barber.</A>
Modify it so there are multiple barber processes.
Analyze your modifications for race conditions.
<P>

<HR><P>

Haunted House with One Touring Car
<P>

Suppose there are Npass passenger processes (default 10)
and one Haunted House touring car process.
The passengers repeatedly wait to take rides in the car
to tour the Haunted House.
The car can only hold so much weight, Wcar pounds (default 1000).
When the car returns from a tour of the Haunted House and empties,
the first passengers in line to take a Haunted House tour take seats in the car,
up to the weight capacity of the car.
However, the car can go out on tour only when it is full,
so if there are not enough passengers in line when the car returns,
the car waits until it fills.
Passengers weigh a random number of pounds, between Wmin and
Wmax (default values 50 and 400, respectively;
no small children are allowed into the Haunted House).
The car is considered to have filled up
when the next person in line would cause the
total passenger weight to exceed the car's capacity.
That passenger cannot go, though, so waits at the head of the line for the
car to go out on tour and return and start filling again.
If, when the car returns and empties, the waiting passengers can all fit,
the car must wait until the first passenger comes along who will not fit.
<P>

The car takes a random amount of time between 0 and Ttour seconds
(default 5)
to tour the Haunted House, simulated with an SR <CODE>nap()</CODE>,
each time it fills up.
After getting a ride, each passenger will wander, SR <CODE>nap()</CODE>,
around the Haunted House grounds for a random amount of time
between 0 and Twander seconds (default 10)
before returning to the car stand to wait in line
for another tour of the Haunted House.
<P>

Develop code for a multi-resource
SR program simulating the Haunted House operations
containing the passenger processes and the car process.
Use semaphores for synchronization (no busy waiting allowed).
Run the simulation for Ttotal seconds (default 30).
Each of the Npass passengers will be a (created) instance
of a resource containing one process each.
The touring car will be represented by a single resource that has
one interface routine
<PRE>
take_a_ride(id: int; weight: real)
</PRE>
and a car process in it.
When a passenger calls the interface routine,
the passenger is blocked until given a tour of the Haunted House
and the car returns to drop its passengers off.
If the car is out on a tour when the passenger calls the interface routine,
the passenger blocks until the car returns and
there is room in the car.
The car process will call <CODE>load</CODE> and <CODE>unload</CODE> procedures
that are internal to the car resource.
Finally, there will be a driver resource that starts everything going.
Make sure that you have eliminated all race conditions!
<P>

There are many ways to do this.
One possibility is to have <CODE>take_a_ride()</CODE>
put the passenger's weight into a bounded buffer.
Here is skeleton code.
<PRE>
resource touring_car
  op take_a_ride(...)
body touring_car(...)            resource passenger
  proc take_a_ride(...)            import touring_car
  ...                            body passenger(...)
  end take_a_ride                  process tour
                                     do true ->
  procedure load(...)                  nap(...) # wander around grounds
  ...                                  cap_car.take_a_ride(...)
  end load                           od
                                   end tour
  procedure unload(...)          end passenger
  ...
  end unload

  process car
    do true ->
      load(...) # car waits until full
      nap(...) # full car so take a tour
      unload(...)
    od
  end car
end touring_car
</PRE>
<P>

Play around with the random number generator arguments, the car weight capacity,
the car maximum trip time, the passenger maximum grounds wander time,
the passenger weight range limits,
and the number of passengers to get a Haunted House tour operation that
drifts between busy and idle.
<P>

All default values should be overridable with command line arguments:
<PRE>
sr -o haunted_house haunted_house.sr
haunted_house Wcar Ttour Npass Wmin Wmax Twander Ttotal
</PRE>
<P>

<HR><P>

Haunted House with Multiple Touring Cars
<P>

Modify your haunted house car tour program so that there are multiple touring
cars, each with the same maximum weight capacity.
The cars wait in line to fill up.
Each car takes a random time to tour so they will not return to fill up
again in the order they left.
Make the number of cars, Ncars,
a parameter of the simulation (default value 3) overridable from the
command line.
<P>

Make the touring car into a separate resource that is created multiple
times.
Put into a coordinator resource that is created once the interface routines
<PRE>
take_a_ride(id, weight)
load(id)
unload(id)
</PRE>
<P>

A very important thing to do is to make sure when a car returns to unload
that the passengers who boarded the car are the ones released!
A single semaphore will not do; you need an array with one entry for each
passenger.
Also make sure that your program works correctly when Ncars is one.
<P>

<HR><P>

Use XTANGO's animation interpreter program, animator, to animate
some of the above programs.
<P>