PP Assignment 2: Pub Simulation
The Problem
An owner of a Public House suspects that the way in which the bar
is operated means that customers have to spend too much time waiting
to be served, and so tend to go elsewhere instead. In order to
evaluate the situation a simulation of the Bar has been
commissioned. Initially this simulation will simply run with text
output describing the events as they occur in the Bar, and collect a
minimal amount of statistical data.
Intension of assignment
Even if valuable to the owner, the simulation is not the
main purpose of this assignment – indeed, if so was the case
there are much better techniques for simulating than
writing a concurrent program.
The requirement of this assignment is to write a program in which
synchronization and communication takes place between several
concurrent processes. It is intended to force you to solve (and not
simply avoid) a range of interesting synchronisation problems.
Choice of programming language
The programming language of your choice is JR.
Did you solve the exercise 4? It is very much
recommended that you do that exercise before starting with this assignment.
After you have completefter that exercise you
should have bits of JR code ready for this assignment.
Synchronisation constructs
For synchronisation you are only allowed to use message passing in
JR. Anything else is strictly forbidden -- no semaphores, no
monitors, etc. This also means that you are not allowed to use
shared variables.
The Pub
The pub consists of a number of tables, a serving area containing a
beer tap and a cupboard (holding the clean glasses, cups, milk,
coffee and chocolate), a clock, a Landlord, a Barmaid, an Assistant,
and a number of customers. The Pub is operated by the Landlord and
Barmaid, whose job is to make and serve drinks to customers who
order at the Bar in a first-come-first-served
manner. Each customer may only order a single drink at one
time. The Landlord and Barmaid can each serve only a single customer
at a time, although others may be waiting to be served.
The Landlord and Barmaid
-
There is one order queue to both the Landlord and the
Barmaid.
-
On receipt of an order, the Landlord or the Barmaid will refuse to
serve a drink for any customer ordering after closing time
(although closing time is not called by the Landlord in the
traditional sense).
-
If it is not closing time, the Landlord and Barmaid serve
customers independently. They serve beer, cappuccino, or hot
chocolate, according to what the customers order. After having
received an order they go to the cupboard and take out a glass or
a cup, according to the type of drink ordered. If none are
available, the Landlord or Barmaid will wait at the cupboard for a
glass or cup to be placed back in the cupboard by the Assistant.
-
Beer: Obtain a glass (takes a set amount of time). Obtain the
beer tap. Fill the glass (also takes a set amount of
time).
-
Cappuccino: Obtain a cup (takes a set amount of time). Obtain
each ingredients coffee and milk (each take a set amount of
time). Mix the drink (take a set amount of time).
-
Hot chocolate: As for Cappuccino, but requiring milk and
chocolate powder.
After making the drinks the ingredients are returned to the
cupboard.
-
The Barmaid leaves at closing time. The Landlord will not leave
the pub until all others (customers, Assistant, Barmaid) have left
the pub.
The Landlord
-
At ten-minutes before closing time the Landlord
calls “last orders” to warn the customers
that closing time is soon.
-
The Landlord will be alerted by the Clock of this.
-
The Landlord may finish serving any customers order he
started before attending to the “last
orders” call.
The Serving area
The serving area consists of the beer tap and a cupboard. The
cupboard (or bar disk) contains all the ingredients, and the cups
and glasses.
-
There are a limited number of glasses and cups in the system.
-
Each of the ingredients (coffee, chocolate powder and milk) and
the beer tap are separate resources. Each of these resources
may only be used by one person at a time.
-
To serve a customer the Landlord or the Barmaid takes one glass
or cup, collects all the ingredients they need, one at the time,
makes and pours the drink, puts the ingredients back and finally
serves the customer.
The Customers
-
The customers enter the Pub at regular time intervals spread
throughout the lifetime of the simulation.
-
On entering the Pub, each customer will order a drink, which will
be served by either the Landlord or the barmaid and will then move
to a favorite table. (It is assumed that all customers have a
known favorite table to make the simulation simpler).
-
Each customer orders only one type of drink. The type of drink
ordered is determined at random according to the set ratio.
(See requirements
section below).
-
Standing, they will drink the contents of their drink in a set
time and then try to put the empty glass/cup down on the
table.
-
If the table is full when a customer wants to put the glass down,
the customer will have to wait for the table to be cleared by the
Assistant before putting the glass down.
-
Having placed the glass on the table, the customer may then go
back to the bar to order another drink until the customer has
either drunk the set number of drinks (configured at compile time)
or the Landlord refuses to give a drink because it is after
closing time. In either case, the customer will leave the pub
straight away.
-
Some of the beer-drinking customers exhibit the following
additional behavior: when they hear the landlord call "last
orders", if they are not currently drinking the last of their set
number of drinks, they will finish their current beer
instantly and go to the bar to order one and only
one more. Make sure to carefully read the details of this point
in the "last orders"
section
The Tables
There are a number of tables in the bar that the customer use to
put down their glasses and cups after finishing their drink.
-
The tables have a limited number of units of space for cups and
glasses. A cup takes up two units of space on the table, a glass
takes up one unit.
-
There is no bound on the number of customers around any table. A
customer never puts down his drink on a table unless it is
finished.
-
It must be possible to fill a table. If there is only one free
unit of space left on the table and a customer wants to put down a
cup he may not block a second customer being able to put down his
glass.
-
Tables mind their own bussiness: tables should be independent of
each other. For instance, a delay in one table should not affect
the other ones.
The Assistant
The Assistant has the job of clearing the glasses and cups away
from each table in turn, washing them and placing them back in the
cupboard once they are all washed.
-
It is assumed that the Assistant is able to transport as many
glasses as necessary on each clearing-up round. Any glasses on a
table are assumed to be empty – the Assistant does not check
the glasses to see if they are empty before collecting them.
-
There is a set period of time allowed for the collection of each
glass/cup, washing of each glass/cup, and replacement of each
glass/cup in the cupboard.
-
After each collect-wash-replace cycle the Assistant is allowed a
rest period (for a length configurable at compile time) before
commencing another cycle.
-
The assistant continues this operation after closing time is
reached, making his final round once all customers have left.
The Clock
The clock in the bar serves two purposes:
-
It will alert the Landlord of both
“last orders” and “closing
time”. The Landlord will alert his customers when
it is time for last orders.
-
The clock serves and updates the current time that each process
uses to print their actions. This part is optional: processes
can also use time stamps for statistics.
You don't have to write the clock yourself. You should use the
following two classes. MyTime.java provides a class
for representing times. Clock.jr implements the clock
which keeps track of the time in the simulation. It is used as
follows:
-
The constructor of the Clock class takes two arguments.
The first argument decides how many milliseconds one second of
simulation time should take in real time. So if you give it the
value 10, each second in the simulation will take 10 milliseconds.
The second argument sets the total time of the simulation (closing
time). As soon as you create a clock object it starts ticking.
It continues ticking even after the closing time. You need to
manually stop the clock using the
operation shutdown().
-
The operation getTime() will return the current
simulation time.
-
The operation setAlarm(cap void() alarm, MyTime t) sets a
timer such that the capability alarm will be called after
the time t has elapsed from the time the timer was
set. That means that if the simulation time was 18:32:12 when the
timer is set and the timeout is 00:01:20 then the alarm will be
set off at simulation time 18:33:32. This timer can be used to
make sure that certain things happen at specific times during the
simulation.
-
The operation setAlarmEndTime(cap void() alarm) sets a
timer such that the capability alarm will be called when
the clock reaches the end of simulation time (closing time).
-
The operation shutdown() terminates the clock.
The Statistics
At the end of the simulation, i.e. when all other processes have
terminated cleanly, the landlord should do some sanity checks
of the Bar and print out some statistics on the run. The result of
the sanity checks must be printed. You must
The Last Orders Problem
As anyone in the UK will tell you, last orders is a serious
problem. It's a problem with the pub lab too – namely getting
the program to terminate cleanly once the landlord has called for
last orders. Here are some hints of how to solve the problem
– and how not to solve it.
Non solution 1 - Really bad
Use a global variable that customers check before they order.
There are two major drawbacks with this solution:
-
Polling. This is a close
relative of the evil busy-wait loop. It involves repeatedly
attempting some action after some period of sleep. Polling might
be a good way of solving some problems, but clearly this isn't one
of them.
-
Customers are not interrupted. The main idea is that the
customers that care about last call reacts instantly and finish
their drinks. Gulp. This can't happen if they have to check a
global variable.
Non solution 2 - just bad
This one works like the previous example, but you let the customers
drink with small sips, checking once every second if last call have
passed.
Once again, this is polling, and besides, this method doesn't help
you understand anything more about concurrent programming, which is
the main goal of the assignment. Customers are interrupted, but
it's not a nice environment to have a beer if you have to check if
the place is closing between every sip.
Non solution 3 - not OK
Before you start drinking, calculate the time left until last call,
and don't sleep longer than that.
This way is not very realistic. In concurrent programming, you
hardly ever know in advance when things will happen. Using this
solution, you wouldn't learn anything useful.
Possible solutions - callbacks and timeouts
A potential problem is if you assume a strict client-server
relationship between landlord and customer. One way around this
limitation is to ensure that every customer that comes into the pub
says "Hello" to the landlord and hands over a pointer to himself (or
to a personal channel) to the landlord (who stores it in some
structure). When they leave, they say goodbye, so he can remove
that pointer again. When last call occurs, the landlord has a means
to communicate with every customer. He also knows how many are in
the pub. The details of what you do depend on the structure of your
solution, and the programming language you are using.
Drinking: Waiting not Sleeping!
Note that the process of drinking (for those thirsty customers)
should be viewed as a timeout rather than a "sleep": a thirsty
customer is waiting for a last orders call, and he times out when
his drink is finished.
Requirements
Documentation
The documentation is as important as the laboration itself. You
will be failed if you ignore this demand. There are some specific
points you should address in your documentation of assignment 2:
-
Describe any modifications, assumptions and basic design decisions
that have been made about the behavior of the various components
of the simulation.
-
Identify all potential sources of deadlock in the problem
specification and describe briefly how they are avoided in the
implementation. Your documentation should include at least the
following:
-
Could the barmaid and landlord be involved in a deadlock when
they take the ingredients for the cupboard? Why (not)?
-
Could the barmaid and landlord be involved in a deadlock when
they take the glasses and cups for the cupboard? Why
(not)?
-
You should give an explanation of your implementation. If your
code meets certain demands of readability (see below) an
explanation of the tricky parts of the software suffices.
-
Your documentation must be in normal plain ASCII .txt-format.
Code quality
-
The code structure has to be clear (even visually - use of
indentation and newlines where necessary) and should not be hidden
in extensive documentation of trivialities ("this is an assignment
of A to B"). Especially the call structure has to be either
obvious or documented.
-
The code should use helpful variable, data structure and function
names (allows fewer comments).
You must not
-
Kill a thread or process. You may not use any of
the following Java and/or JR methods/functions:
- Thread.stop
- Thread.resume
- Thread.suspend
- Thread.interrupt
- setDaemon
- JR.exit
-
If any of those primitives are found in your code, you
will fail the assignment no matter the functionality of it.
-
Use any kind of polling. Read this link on some examples of what
we consider to be polling
-
Solve the last orders problem in a manner forbidden in the
description above.
-
Resolve communication with an all-purpose one-channel
solution.
Tips and Tricks
-
Divide up the code in classes. For example one for the Landlord,
one for the Barmaid, etc...
-
Run your program without customers entering the pub.
This should work if your solution is correct. The
solutions should not be dependent on the events created by the
customers.
-
Make very sure of who's actually doing the work. It easy to make
some mistakes like leaving the Clock to call the “last
call”-call and then actually finish the drinks for the
customers! Make this easier for yourself by printing the name of
the process performing an action.
-
Make sure you do not have
any busy-waiting loops. Look
through your solution carefully before handing it in. For
example, you are likely to have busy waiting if you use
[]else-> inside of a
while (some_condition) {inni ... } statement in
JR.
-
The use of semaphores (other than for controlling simple
resources and basic mutex for statistics) is strongly
discouraged.
-
Use short delay times – there is no need for a simulation
run to take more than 20—30 seconds.
Credits
- Written by David Sands, based on an exercise in Bustard, D.W., Elder,
J.W.G., and Welsh, J.:
Concurrent Program Structures, Prentice Hall International,
1988, and a similar assignment by Alwyn Barry.
- Magnus Björk (vt00): Wrote the “The last orders
problem”
- Joakim Axelsson (2004-09-07): Merged pages and clarified the
document.
- Daniel Hedin and Andrei Sabelfeld contributed various
improvements
- Staffan Björnesjö (2008-09-19): A few minor changes and an
example class for constants.
- Josef Svenningsson has made various changes and refinements over
the years.
