Fortunately, there was a small vending machine on the table, which could supply matches, papers, and tobacco, one item at a time, in some unexpected order. As the supplies appeared the philosophers tried to grab them up and hoard them, sometimes pushing each other out of the way; for example, the philosopher with tobacco tried to grab matches and papers, and the philosopher with papers tried to grab tobacco and matches, contending with the tobacco philosopher for the matches. Whenever a philosopher had all three items--matches, paper, and tobacco--he would immediately roll his own, smoke it down, discard the butt in a handy ashtray, and then begin contending for further supplies.
A sequence of supplies, or `outputs' from the vending machine can be represented with a sequence of letters: `m' for matches, `p' for papers, and `t' for tobacco. Similarly, we can refer to the philosophers as M, P, and T, according to what supplies they brought. A sequence `ptpt' from the machine would let M smoke twice, if he was the only philosopher at the table. However, if P was at the table, he might try to grab the tobacco, and if T was at the table, he might try to grab the papers, so that M could only smoke twice if he was fast and lucky. The vending machine might also produce a sequence like `pppttt', forcing M to hoard the papers, even if he was the only one at the table.
The machine can provide supplies in any order, and some of these sequences are more useful than others. A ``fully smokable sequence'' is a sequence of m's, t's, and p's of length k, such that if the philosophers cooperate correctly, or are very lucky, then there are k/2 butts in the ashtray after the sequence has been smoked. Any sequence with odd length is not fully smokable, and some even-length sequences such as `mmmmpp' are also not fully smokable.
To conclude our story, the philosophers would like to start their individual smoking as quickly as possible and would also like, as a group, to fully smoke every fully smokable sequence. If the philosophers cooperate in an intelligent fashion, can both goals be satisfied?
PS: It appears that when the vending machine was loaded, the serviceman chalked three numbers on its top--the total number of matches, total number of papers, and total number of packets of tobacco inside. Assuming the machine produces supplies until it is completely empty, can the philosophers use this information to organize their smoking more efficiently?
More specifically, you are to write a program `phil' that takes one of three command-line arguments: M, P, or T, and then acts as that philosopher. Your three `phil' processes--phil M, phil P, and phil T--will represent the three philosophers, and will typically run concurrently in the background. Your `phil' program should be able to work when only one or two philosophers are at the table, though a single philosopher or pair of philosophers is only expected to smoke sequences of supplies they can actually use.
A `vend' program is provided that will supply you philosophers with smoking materials, and which forks off an ashtray process to receive the smoked butts. The butts are important, as it is the ashtray process that keeps track of the smoking. The `vend' process uses a simple rendezvous protocol, described below, to supply smoking materials to the philosophers and to collect the smoked butts.
Vend uses four `channels', for tobacco, matches, papers, and the ashtray. These channels do two things--perform a rendezous, and transfer a value. To provide a supply--tobacco, for example--vend sends a particular prime number on the tobacco channel. When, say, phil M has received tobacco (with a value x) on the tobacco channel and paper (with value y) on the papers channel, M `smokes' by sending the product x * y on the ashtray channel.
The vend program reads (or generates) a sequence of supplies and then sends the sequence using the three supplies channels. After generating the supply sequence and before providing any supplies, vend quietly forks off an `ashtray' process which receives the butts, i.e., the products x * y from the smokers. The vendor process prints a message when each supply is sent, and the ashtray process prints a message when each butt is received, providing a trace of process interaction. The ashtray process also prints a message when the supplied sequence is fully smoked.
The vend program also places the total initial amount of each supply in shared memory--location TLOC for tobacco, MLOC for matches, and PLOC for papers, as defined in vend.h. The philosophers are free to use this information to organize their smoking, and to possibly restrain their greed in grabbing supplies. A special semaphore `READY' is defined in vend.h. Vend signals once on READY after it has put the number of each supply in shared memory. Your phil program(s) should probably wait on READY after calling sinit() and before reading the numbers of these supplies.
Ideally, you `phil' program will use this information to terminate successfully and quietly. If your `phil' process does not terminate, then when the ashtray process receives the last value it is expecting, it clears the semaphore block, causing any processes waiting on semaphores to be terminated. This will produce an error message from each waiting `phil' process and cause it to terminate. (Of course, if you process was doing something else, it won't get terminated, so it doesn't hurt to check things with an occasional `ps' command, or to run the supplied "reset" script, which kills off all the philosophers.)
When the `ashtray' process finishes and deletes the semaphore block, it prints the message "deleting semaphore block..." If you see error messages of the form "Process [blah]: semop() error on [blah]," then some phil processes had not terminated yet. You will also get this error messages when vend or the phil processes are interrupted with a ^C or other signal.
To send a value on channel ci:
place the value in shared memory location i
signal on semaphore 2*i
wait on semaphore 2*i+1
To receive a value on channel ci:
wait on semaphore 2*i
get the value from shared memory location i
signal on semaphore 2*i+1
Note that this protocol will work correctly when you have multiple
receivers and a single sender (vend sending to the philosophers),
but you may want to modify it slightly, perhaps by adding mutual
exclusion to allow only one sender at a time, for the case of
multiple senders and a single receive (philosophers sending to the
ashtray). See philskel.c and vend.c for examples of functions to
send and receive on a channel.
umbc8 > phil T & start the tobacco philosopher umbc8 > phil M & start the matches philosopher umbc8 > phil P & start the papers philosopher umbc8 > vend mptmpt start the vending machine supply sequence is: mptmpt output from `vend' and ashtray vendor : supplying m vendor : supplying p vendor : supplying t ashtray: butt from T vendor : supplying m vendor : supplying p ashtray: butt from P vendor : supplying t ashtray: butt from M ashtray: all supplies smoked! ashtray: deleting semaphore block . . .At this point, you may get some errors that look like "Process [blah]: semop() error on swait()," if your philosopher processes are still running. Your philosopher processes should terminate cleanly for full credit.
submit cs421_0101 proj1 phil.c
Do not submit from more than one account, or by email. You can
submit a file as many times as you like; only the final submission
is saved. The submit program copies your program into a protected
directory in my account, which has the same name as your user id.
Submit has a number of other options, including checking and
retraction; see the man page for details.
Projects that do not compile get 0 points. You program should work with the routines vend.c, vend.h, sem.c, and the makefile as provided; when I compile and test you program for grading, I will be using the original versions. The makefile will compile your phil program, as well as vend and some example programs. If you want to use C++, or have some other valid reason for modifying the makefile, check with me first, and submit your makefile in addition to your other files.
You must do the project described here. Doing some other similar or dissimilar project, no matter how difficult or clever, may be worth 0 points. This is not a group project. Please do your own work, and be careful about sharing your code.
philskel.c skeleton of a philosopher program vend.c the vendor program; includes documentation sem.c semaphore package; includes documentation sig.c example program using ssig() wai.c example program using swai() sclear.c reset semaphores and shared memory show.c display semaphores and shared memory reset shell script to kill off phil processes tests shell script to test phil program Makefile makefile to compile and link everything