Fine (Buffet) Dining Philosopher's Problem Application

Task

Application – Fine (Buffet) Dining Philosopher’s problem
For this problem, our philosophers are now having a meal in a fine dining buffet restaurant (assume one exists). In this restaurant, there are a lot of rules and regulations. For example, you need various tools/utensils to eat different kind of food in a manner that is suitable for the restaurant. (For example, you need a soup spoon for soup, and a clam opener for lobsters, and chopsticks for rice etc.).

To abstract the problem, we assume that there is a total of k types of tools to be used. For type j, the restaurant has tj copies of type j tools to be offered for the philosophers. Every philosopher, when he/she arrives, he/she knows what are the food they want to eat, and thus how many of each type of tool its need. (For each philosopher, we denote sj to be the number of tools that a philosopher needs).

Notice that for different philosophers, the value of si is different.
The restaurant has a set of m tables. When a philosopher arrives at the restaurant, it first informsthe restaurant the number of tools he/she needs. However, the restaurant does not immediately give him/her the utensils. Instead, the philosopher will sit down on one of the tables, and then periodically request the tools that it needs.

 

If there is no table available, the philosopher will be put on a waiting queue and will be seated to the first table available.
Once a philosopher is sat, he/she will start making requests for tools for eating at random times. Each time a philosopher can request at most two tools. Every time a request is made, the restaurant will determine whether the tools is available, and whether satisfying the request will potentially lead to a deadlock (using the deadlock avoidance algorithm mentioned in class). As a result, the restaurant may deny the request and tell the philosopher that the request the denied. The philosopher will then wait for a random amount of time before making the next request (may or may not be the same).

Once a philosopher obtained all the tools, he/she will spend some time eating his/her meal and then leaves. Once he/she leaves, the table becomes open and the restaurant can sit another philosopher on
that table.

Program Structure

Your program structure should resemble that of program 2. The first thing your program should do is to read an input file (which filename should be provided via the command line). The file format will be as follows:
• The first line contains three positive number, separated by (any number of) spaces
o The first number is the number of types of tools (k)
o The second number is the number of tables(m)
o The third number is the number of philosophers (n)
• Then the following n lines contain information about each philosopher. It contains the following fields, separated by (any number of spaces), 
o The first field is a string (at most 20 characters), contains the name of the philosopher
o The next field is a number that contains the total number of tools that the philosopher needs (let call this number p)
o Then there will p numbers, each number (between 0 and k-1, inclusive) denote a tool that the philosopher wants. Notice that the number can repeat (since a philosopher may request multiple copies of the same tool). The numbers should be read in and stored into a list (to represent the order of requests).

The main process will be responsible for assigning tables to each philosopher, including assigning a table to a philosopher that is waiting when the table becomes available. The logic for the main program should looks like the following.

Read in the input file
Initialization
Create the threads
Sit the first m philosophers
Signal each thread to start
While (there are philosopher not finished)

When a table becomes available
If there are still philosopher(s) waiting
assign the next waiting philosopher to that table else
inform that table that no one else is coming in

Clean up if necessary
Output(“All done”)
Exit

 

Each thread is a table that will sit one philosopher at a time, the logic of each thread is as follows: Initialization if necessary

 

Wait for the signal from the main process to start
Repeat
While not done
Repeat
Check the current time (using time()) [denote it as t]
If the time is odd
Call Request() to request the next tool on the list
Else
Call Request() to requestthe next two tool on the list (if there is only one item on
the list, then request that item only)
If (request is granted)
Update the tools that the philosopher got
Else
Move the requested item to the end of the list
Sleep for 1 sec + (t mod 1000) milliseconds
Until the philosopher obtains all the tools
Sleep for 2 seconds
Return all the tools back to the restaurant
Signal the main process that he is done eating and is leaving
Wait until either a new philosopher is seated, or the main process told the thread that
there is no more philosopher waiting
Clean up if necessary
exit

There may be some functionality that is not included in the pseudo code, and you need to figure out
how to fit those in.

Request() function
For requesting tools, you should implement a Request() function that will take in (at least) the following parameter: the philosopher that request the tools (you can identify him/her either by the philosopher himself/herself or by the table (thread) that he/she is in); and the tool(s) that he/she request (either 1 or

 

2). Your function should run the deadlock avoidance algorithm to check whether the lock should be granted. It should return a Boolean (or int) that indicate whether the request is successful or not. Obviously, some data structures need to be updated if the request is granted, you need to decide whether you want to apply those changes inside or outside the function.