1. (3 points) What is a valid implementation of the Java notify operation required to guarantee about the selection of the thread that is unblocked. Consult the Java Language Specification.
Don't get confused by the wording of this question -- it's asking
what is guaranteed about the selection of a thread to be notified
when a notify operation occurs. So, you're looking for a
guarantee about selection. The words "valid implementation of the Java
notify operation" mean this: a valid implementation is one that meets
the specifications. So, what do the specifications say about the
notify operation?
It says, essentially, that when there is more than one thread that could be notified, an arbitrary one will be picked -- that is, one will be picked nondeterministically. There will be no guarantees about which one -- that is, there is no ordering among the notified threads that will be observed. It is up to the implementers of the virtual machine to decide how to select the thread that is notified. So, the selection process that may be in place with one impelementation may be quite different from that of another implementation.
2. (5 points)
Solve the sleeping barber problem (see below) using CSP.
Your solution must have a Barber process, a WaitingRoom process, and an
array of Customer processes. In CSP, the notation
Proc[i] (1..n) : [ code for process ]
can be used to define an array of processes each of which has a variable i whose value indicates it index among the n process. The notation Proc[j]?x and Proc[j]!x can be used to read from or write to, respectively, the process in the array whose index is given by the current value of j. Each Customer process should repeatedly seek haircuts. Assume there is a statement wait that delays the execution of the Customer for some period of time to simulate what the Customer does after getting a haircut or after finding all of the chairs full.
Sleeping Barber Problem:
A barber shop has one barber and n chairs for waiting customers, if any, to sit in. If there are no customers present, the barber waits for a customer to arrive. When a customer arrives, the customer receives a haircut from the barber. If additional customers arrive while the barber is cutting a customer's hair, they either sit down (if there are empty chairs) or leave the shop (if all chairs are full).
OK, here's one solution to the problem. This tries to model closely the interaction between the customers, barber, and waiting room as given in the problem specification. The customer enters the waiting room, and if it finds the room empty and the barber sleeping (not busy) the customer goes straight to the barber for a haircut. If the customer finds the barber busy but sees seats open, the customer sits down. If the customer sees the shop full, he/she leaves the shop. When the barber is through with a customer, he looks to the waiting room to see if there are any more customers. If there are, the next customer is told that the barber is ready, so the customer then goes to the barber for a haircut. When the shop is empty, the barber rests and waits for another customer to ask him for a haircut. Imagine that the waiting room has an attendant or a receptionist that does the job of asking people to sit, or telling a customer when it's time for them to get a haircut. Suppose that there are n chairs in the waiting room and that there are m customers that try to enter the shop (we're assuming that m>n is possible). Note that a customer that can go directly to the barber for a haircut never takes a seat in the waiting room.
process WAITING_ROOM: chairs: 0..n-1 of integer; barber_busy: boolean (initially = false); in, out: integer (initially = 0); *[ barber_busy = false; in = out; (i:1..m)customer(i)?enter() -> barber_busy = true; customer(i)!ready(); [] barber_busy = true; in < out + n; (i:1..m)customer(i)?enter() -> chairs(in mod n) = i; in := in + 1; customer(i)!sit(); [] in = out + n; (i:1..m)customer(i)?enter() -> customer(i)!full(); [] out < in; barber?more() -> barber!ok(); customer(chairs(out mod n))!ready(); out := out + 1; [] out = in; barber?more() -> barber_busy = false; barber!ok(); ] end process CUSTOMER: status: integer (initially = 0); /* status = 0: Customer is outside shop status = 1: Customer is inside shop, looking around status = 2: Customer is sitting down inside the shop */ *[ status = 0 -> waiting_room!enter(); status = 1; [] status = 1; waiting_room?sit() -> status = 2; [] status = 1; waiting_room?full() -> wait; status = 0; [] status <> 0; waiting_room?ready() -> barber!cut(); barber?done(); wait; status = 0; ] end process BARBER: *[ (i:1..m)customer(i)?cut() -> /* cut customer i's hair */ customer(i)!done(); waiting_room!more(); waiting_room?ok(); ] end MAIN = [waiting_room::WAITING_ROOM || barber::BARBER || customer(i:1..m)::CUSTOMER].
3. (2 points) Do problem 2.3 on page 44 of the text.
Explain what the following path expressions do:
(a) path { open + read } ; close end
This means that we can have many open and/or read operations executing at once. After they have all completed, we will have one close operation. Then, the cycle may repeat. Note that between any two close operations, there must be at least one open and/or read operation.
It is not the case that open and read operations are mutually exclusive -- if we wanted that, we would use the following path:
path { open } + { read } ; close endWhat the questions says is that there may be many things going at once, each of which is executing either an open or a read, but not both. Then, when they're all done, we can do exactly one close operation.
(b) path ( openread ; read } ; { openwrite ; write } end
This means that we can have many processes executing the following sequence at once: openread followed by read. It will always be the case that the number of openread operations performed will be greater than or equal to the number of read operations performed. After all have completed, then we can have many processes executing the following sequence at once: openwrite followed be write. Again, it will always be the case that the number of openwrite operations performed will be greater than or equal to the number of write operations. After all have completed, then we can repeat the cycle. Note that between any two executions of the openwrite; write sequence, there must be at least one execution of the openread; read sequence. Similarly, between any two executions of the openread; read sequence, there must be at least one execution of the openwrite; write sequence.