Operating System

2006 Fall, Project Three

VIP Philosophers Dining

Due Time:

1.     Upload final version: 23:59:59, Jan 21st, 2007  .

2.     Demonstration: 18:30 ~ 21:30 , Jan 22nd, 2007 in DTH 219

Problem:

        Dining-philosophers problem is an illustrative example of a common computing problem in concurrency. It is a classic multi-process synchronization problem. The philosophers have three states: THINKING, EATING and HUNGRY when dining. At first, they think for a while at THINKING state. When they finish thinking, they feel hungry and try to pick up the chopsticks at HUNGRY state. A philosopher can start to eat at EATING state only when he succeeds to pick up two chopsticks beside him. After finishing eating, the philosophers start to think again for next round.

        Our dining-philosophers problem is a little different. The dining table is still for five people. More than 5 philosophers are waiting in line for dining. A philosopher waits until 5 people are at the table to start a round of thinking and eating if there are still others in line. After some rounds of thinking and eating, a philosopher leaves the table and the first philosopher in line replaces him to dine. Some philosophers are VIP such that once they are hungry, they can grab chopsticks from their non-VIP neighbors to eat. The preempted non-VIP neighbors return to HUNGRY state and put down the other chopstick. The main problem is to simulate our dining-philosophers problem without deadlock and starvation. Note that some philosophers might dine for unlimited rounds.

Project:

Implement a synchronization monitor to solve the problem above. Read problem inputs from stdin and print to stdout any state changes of all dining philosophers in the following format. Explain why your program is free from deadlock and starvation in your report and in demonstration. We will grade with other input cases. Note that you might want to reduce the HUNGRY states for more efficient implementation.

Sample Input:

6                                // total 6 philosophers, ID 0 to 5. The maximum is 10, ID 0 to 9.

1000 1000 1 0        // thinking time: 1000 us, eating time: 1000 us, 1 round, non-VIP

1000 1000 2 1        // thinking time: 1000 us, eating time: 1000 us, 2 rounds, VIP

1000 1000 1 1

1000 1000 1 0

1000 1000 1 0

1000 1000 1 0

 

Sample Output:

01234   // ID 0 to 4, sit at the table in order and start dining

TTTTT   // T: THINKING, H: HUNGRY, E: EATING -:LEFT respectively

THTTT   // print the states when any state is changed. 
TETTT  
HETTT
HEHTT
HEHHT
HEHET
HEHEH
HTHEH

ETHEH
ETHHH 

ETEHH  // 2 preempt 3
51234  // ID 0 left and replaced with ID 5
TTEHH 
TTEHE
TTEH-  // ID 4 left
TT-H-  // ID 2 left
TT-E-  // ID 3 resume

TH-E-
TE-E-
TE---  // ID 3 left
T----  // ID 1 left

H----
E----
-----  // ID 5 left

 

Platform:

        OS: Linux       

Programming Language: C/C++     

Machine: try to find one yourself

Demonstration:

When demo, handing in a report with at most 3 pages. Justify your program is free from both deadlock and starvation, and show how you did it and how good it is. Do not just describe your program.

Grading:

        Programming Architecture:    20%

        Result:    40%

        Report:   20%

        Demo :   20%

        Bonus :  The HUNGRY time and status are reduced obviously.  15%

 

        If your program is neat and correct, you will get more points. You will loss 30 points if you implement without synchronization monitor. Late penalty of demo is 2 points per day, and late penalty of handing in is 10% per day. E.g. if 2 days late for handing in and 1 day late for demo with grade 92. The final score will be (92 - 2) * 90% * 90% = 72.9

Handing in:

Upload the files to FTP server

Host: 140.112.90.167  User: os  Password: project3

You should create your own directory like R95922148. Note that the initial should be capital. You have to upload your source code and executable file, including Makefile, *.c, *.h, …