Question

Consider the Dining-Philosophers problem (Chapter 5.7.3), in which a set of philosophers sit around a table with one chopstick between each of them. Let the philosophers be numbered from 0 to n−1 and be represented by separate threads. Each philosopher executes Dine(i), where “i” is the philosopher’s number. Assume that there is an array of semaphores, Chop[i] that represents the chopstick to the left of philosopher i. These semaphores are initialized to 1.

void Dine( int i )

{

Chop[ i ] .P(); /∗ Grab left chopstick ∗/

Chop[( i+1)%n ] .P(); /∗ Grab right chopstick ∗/

EatAsMuchAsYouCan ();

Chop[ i ] .V(); /∗ Release left chopstick ∗/

Chop[( i+1)%n ] .V(); /∗ Release right chopstick ∗/

}

This solution can deadlock. Assume that it does. List the four conditions of deadlock and explain why each of them is satisfied during the deadlock.

Answer 1

#include<iostream>
#define n 4 // number of processes are 4
using namespace std;
int compltedPhilo = 0,i;
struct fork{
    int taken;
}ForkAvil[n];//fork structures
struct philosp{
    int left;
    int right;
}Philostatus[n]; //philosphers structures

void goForDinner(int philID){
//same like threads concept here cases implemented
    if(Philostatus[philID].left==10 && Philostatus[philID].right==10)
        cout<<"Philosopher "<<philID+1<<" completed his dinner\n";
    //already completed dinner then
    else if(Philostatus[philID].left==1 && Philostatus[philID].right==1){
            //if just taken two forks
            cout<<"Philosopher "<<philID+1<<" completed his dinner\n";

            Philostatus[philID].left = Philostatus[philID].right = 10; //remembering that he completed dinner by assigning value 10
            int otherFork = philID-1;

            if(otherFork== -1)
                otherFork=(n-1);

            ForkAvil[philID].taken = ForkAvil[otherFork].taken = 0; //releasing forks
            cout<<"Philosopher "<<philID+1<<" released fork "<<philID+1<<" and fork "<<otherFork+1<<"\n";
            compltedPhilo++;
        }
        else if(Philostatus[philID].left==1 && Philostatus[philID].right==0){ //left already taken, trying for right fork
                if(philID==(n-1)){
                    if(ForkAvil[philID].taken==0){ //KEY POINT OF THIS PROBLEM, THAT LAST PHILOSOPHER TRYING IN reverse DIRECTION
                        ForkAvil[philID].taken = Philostatus[philID].right = 1;
                        cout<<"Fork "<<philID+1<<" taken by philosopher "<<philID+1<<"\n";
                    }else{
                        cout<<"Philosopher "<<philID+1<<" is waiting for fork "<<philID+1<<"\n";
                    }
                }else{
    //except last philosopher case
                    int dupphilID = philID;
                    philID-=1;
                     if(philID== -1)
                        philID=(n-1);
                     if(ForkAvil[philID].taken == 0){
                        ForkAvil[philID].taken = Philostatus[dupphilID].right = 1;
                        cout<<"Fork "<<philID+1<<" taken by Philosopher "<<dupphilID+1<<"\n";
                    }else{
                        cout<<"Philosopher "<<dupphilID+1<<" is waiting for Fork "<<philID+1<<"\n";
                    }
                }
            }
            else if(Philostatus[philID].left==0){ //nothing taken yet
                    if(philID==(n-1)){
                        if(ForkAvil[philID-1].taken==0){ //KEY POINT OF THIS PROBLEM, THAT LAST PHILOSOPHER TRYING IN reverse DIRECTION
                            ForkAvil[philID-1].taken = Philostatus[philID].left = 1;
                            cout<<"Fork "<<philID<<" taken by philosopher "<<philID+1<<"\n";
                        }else{
                            cout<<"Philosopher "<<philID+1<<" is waiting for fork "<<philID<<"\n";
                        }
                    }else{
     //except last philosopher case
                        if(ForkAvil[philID].taken == 0){
                            ForkAvil[philID].taken = Philostatus[philID].left = 1;
                            cout<<"Fork "<<philID+1<<" taken by Philosopher "<<philID+1<<"\n";
                        }else{
                            cout<<"Philosopher "<<philID+1<<" is waiting for Fork "<<philID+1<<"\n";
                        }
                    }
        }else{}
}int main(){
    for(i=0;i<n;i++)
        ForkAvil[i].taken=Philostatus[i].left=Philostatus[i].right=0;

    while(compltedPhilo<n){
        /* while loop will run until all philosophers complete dinner
        Actually problem of deadlock occur only try to take at same time
        This for loop will say that they are trying at same time.
        */
        for(i=0;i<n;i++)
            goForDinner(i);
        cout<<"\nTill now num of philosophers completed dinner are "<<compltedPhilo<<"\n\n";
    }
    return 0;
}

ElHomeworkLib dinning.exe Fork 1 taken by Philosopher 1 Fork 2 taken by Philosopher 2 Fork 3 taken by Philosopher 3 Philosopher 4 is waiting for fork 3 Till now num of philosophers completed dinner are Fork 4 taken by Philosopher 1 Philosopher 2 is waiting for Fork 1 Philosopher 3 is waiting for Fork 2 Philosopher 4 is waiting for fork 3 Till now num of philosophers completed dinner are Philosopher 1 completed his dinner Philosopher 1 released fork 1 and fork 4 Fork 1 taken by Philosopher 2 Philosopher 3 is waiting for Fork 2 Philosopher 4 is waiting for fork 3