| Due: | Monday, March 20 at the start of class |
|---|---|
| Purpose: | To give you experience with Concurrent Programming using shared memory |
One interesting class of applications of concurrent programming is simulation, in which a program simulates a real-world system by using individual processes to simulate its individual components. For this project, we will be simulating a bank, having some number of tellers. Each customer arrives at the bank, waits in a single line until a teller becomes free, and then goes to that teller to transact his business, leaving the bank when his business is done. In this case, each individual customer will be simulated by a process.
The major parameters of this system are: the number of tellers, the rate at which new customers arrive (specified as an average interval between arrivals), and the average time it takes to service a customer. Clearly:
If (average inter-arrival time) >> (average service time) / (# of tellers) then customers will seldom stand in line, but tellers will often not be productively employed.
If (average inter-arrival time) < (average service time) / (# of tellers) then the waiting line will grow without limit and customers will become very angry.
If (average inter-arrival time) = (average service time) / (# of tellers) then the system will eventually reach a steady state with a fairly constant waiting line length.
For this project, you will be writing a program that simulates this system. At startup, your program will accept the three parameters mentioned above plus the length of time to run the simulation. All times will be entered in seconds. To avoid having to run the program for an entire day, we will simulate ten seconds of "simulated world" time by one second of actual program run time.
The simulation will proceed as follows:
One process will be responsible for creating new customers at random intervals, such that the average time between new customers is equal to the specified parameter. It will exist throughout the simulation.
Each customer will be simulated by a process that is created when the customer arrives, works its way through the bank, and then terminates.
The waiting line will be simulated by a general semaphore that uses a FIFO queue.
The semaphore will be initialized to the number of tellers. If there are n tellers, then the first n customers doing a wait() on this semaphore will be able to proceed without delay.
When each customer process enters the bank, she will do a wait() on this semaphore. When she is finished being served, she will do a signal(), allowing another customer to pass the semaphore and use the teller.
Your program must conform to the following specifications:
The following values must be entered to your program on the command line and they must be in the order given. Your program should also have a usage statement to indicate the correct list of parameters. See the example using C or the example using C++ to help you with this.
The parameters are:
number of tellers
mean time between arrivals
mean service time
length of time to run the simulation
All of the time values should be entered in simulated world seconds, with ten simulated world seconds simulated by one second of program run time. (This means that times input by the user should be a multiple of 10.)
Each customer process should write three lines to the screen, at the following times:
When she arrives in the bank and enters the waiting line.
When she steps up to a teller and starts being served.
When she is through being served and leaves the bank.
Each line should consist of the current time (in real-world seconds since the start of the simulated day) and an appropriate message, and should identify the customer by number. (That is, the first customer created is customer 1, the second is customer 2, etc.)
Finally, at the end of the simulation a summary message should be printed, giving:
The total number of customers who have been served.
The average time spent waiting in line by customers who have been served.
Note: any customer who is present in the bank when the simulation ends must be allowed to complete her work and leave the bank - even if this means that some tellers work overtime a bit. This means that you must keep track of the number of customer processes that are still in existence and not finish the simulation until this becomes 0 after the simulation time is up.
The output of a sample run of the program is attached.
Note well: You must treat both the screen and the variables that record the number of customers and cumulative data to be printed out at the end as shared resources to be accessed only by one process at a time. This will require some number of additional semaphores. Even if your code appears to work, it will receive a poor grade if you do not properly ensure mutual exclusion on accesses to these!
You should turn in a listing of your program, and the output of a sample run (use the same data as in the sample output). Name your executable bank and make sure that it is in the same directory as the source code.
Because all the processes will be updating certain shared variables, the most natural way to write this program is to use shared memory. While Unix processes do not share memory by default, some systems have system calls that do create processes that share memory. Also, many systems now support threads.
We will use the (fairly) portable pthreads library to create our threads. The key function for us will be pthread_create(3) (The "3" in parentheses indicates that the manual page for this function is in section 3 of the manual: the section on subroutines). We will also use POSIX unnamed semaphores for synchronization.
To use pthreads and POSIX semaphores you should include the following lines in your program:
#include <semaphore.h> #include <pthread.h>
You will also need to include -lpthread as an option to cc or CC when linking your program so that the pthreads library will be linked in.
You may look at either thread.c or thread.cc for a short, simple use of pthreads and POSIX semaphores.
You can find detailed information about pthreads (pthreads(5), pthreads_create(3), pthread_join(3), and pthread_exit(3)) and the POSIX unnamed semaphores (sem_init(3), sem_wait(3), sem_post(3), and sem_destroy(3)) in the manual pages using the "man" command.
To help you use these routines, sample implementations of the dining philosophers problem are attached.
The process that generates the customer processes can be structured as follows:
|
while the end of the simulation has not yet been reached do begin sleep() a random amount of time --- based on inter-arrival mean if simulation end time not yet reached then create a customer thread end; |
A customer process can be structured as follows:
|
Be sure to divide time parameters by 10 before calling this routine - if you divide after then a small value returned by random_int() will become a zero.
Mean inter-arrival time: 10 Mean service time: 30 Number of tellers: 3 Length of simulation: 70 At time 30, customer 1 arrives in line At time 30, customer 1 starts being served At time 30, customer 2 arrives in line At time 30, customer 2 starts being served At time 30, customer 3 arrives in line At time 30, customer 3 starts being served At time 40, customer 1 leaves the bank At time 50, customer 4 arrives in line At time 50, customer 4 starts being served At time 50, customer 4 leaves the bank At time 50, customer 5 arrives in line At time 50, customer 5 starts being served At time 50, customer 6 arrives in line At time 50, customer 7 arrives in line At time 60, customer 3 leaves the bank At time 60, customer 5 leaves the bank At time 60, customer 6 starts being served At time 60, customer 7 starts being served At time 70, customer 7 leaves the bank At time 70, customer 8 arrives in line At time 70, customer 8 starts being served At time 70, customer 8 leaves the bank At time 100, customer 6 leaves the bank At time 110, customer 2 leaves the bank Simulation terminated after 8 customers served Average waiting time = 2.50