Concurrent Programming (19530-V)

Dr. Richard S. Hall WS 01/02

- Übung 3 -

Assigned: 6.11.2001
Due: 20.11.2001


1.  Exercise

A roller-coaster control system only permits its car to depart when it is full. Passengers arriving at the departure platform are registered with the roller-coaster by a turnstile. The controller signals the car to depart when there are enough passengers to fill the car to its maximum capacity of M passengers. The car goes around the roller-coaster track and then waits for another M passengers; ignore passengers leaving the car. The roller-coaster consits of three processes: TURNSTILE, CONTROL, and CAR. TURNSTILE and CONTROL interact by the shared action passenger (indicating an arrival) and CONTROL and CAR interact by the shared action depart (indicating car departure). Draw the structure diagram for the system and create an FSP description of the overall system.

2.  Exercise

A recursive lock is a lock that when acquired by a process can be acquired again and again by that process without the process having to release it before re-acquiring it. Conceptually, the lock keeps a counter of how many times it was acquired by the same process and the lock is only freed after an equivalent number of releases have occurred from the same process.

Given the following declarations:

    const N = 3
    range P = 1..2  // process identities
    range C = 0..N  // counter range for lock

Model a recursive lock as an FSP process called RECURSIVE_LOCK with the alphabet {acquire[p:P], release[p:P]}. The action acquire[p] acquires the lock for a particular process p.

3.  Exercise

A central computer connected to remote terminals via communication links is used to automate seat reservations for a concert hall. A booking clerk can display the current state of reservations on the terminal screen. To book a seat, a client chooses a free seat and the clerk enters the number of the chosen seat at the terminal and issues a ticket. A system is required which avoids double-booking of the same seat while allowing clients free choice of the available seats. Construct a model of the system and demonstrate that your model does not permit double-bookings.

Your TERMINAL process should allow the customer to choose a seat, at which point the process should query to determine if the seat is reserved or not. If the seat is not reserved, then it should be booked otherwise nothing changes.