Multithreading issue - Dining Philosopher

I have couple of issues with this code.
1. when philosohers are not eating, they are thinking ( for now I defined that time for 10 sec), so should i have sleep() when they are thinking or keep running the loop.
2. This code is very CPU intensive, I added sleep(1000) end of the loop, that helped. Is there any other way i can optimize the code for less CPU  intensive.
3. Only one philosopher gets to eat at a time, what can be done so that atleast a few philosophers can start eating. Do you think that is because of deadlock. I will be implementing Mutex or Semaphore next but this exercise entails how deadlock can occur and why there is a need for synchronization object.
4. For next exercise I will be using Synchronization object. Which one i should use - CS, Mutex, Semaphore and why?
Thats all for now.
///////////////////////////////////////////////////////////
//Thread.cpp
#include<stdio.h>
#include "Thread.h"


//DWORD Thread::m_ID = 0;

Thread::Thread()
{
	leftChop = rightChop = -1;

	HANDLE hnd = CreateThread(NULL,0,Thread::ThreadProc,this,0,&m_ThreadID);
	if(hnd == NULL)
	{
	}

	m_State = STATE_THINKING;
	pPhil = 0;
	m_ReadyToEat = 0;
}


Thread::~Thread()
{
}

DWORD WINAPI Thread::ThreadProc(LPVOID lpParameter)
{
	Thread*p = (Thread*)lpParameter;
	if(p == 0) return 0;

	//p->m_ID++;
#if DEBUG
		
	printf("Thread %d is running. Status= %s.\n", p->m_ThreadID, p->getStatus(p->m_State));
#endif


	int leftStatus = -1, rightStatus = -1;

	char buf[40];
	time_t oldtime, newtime= 0;
	struct tm  *ts;
	oldtime = time(&oldtime);

	ts = localtime(&oldtime);
	//printf ( "Starting time: %s", asctime (ts) );
 
	for(;;)  
	{
		time_t ntime = time(0);
		
		//Grab left chop
		if(p->m_ReadyToEat 
			&& p->m_State == STATE_THINKING)
		{
			
			if( !p->pPhil->leftChopInUse(p->m_ID))
			{
				p->assignLeftChop();
			}

			//Grab right chop
			if(!p->pPhil->rightChopInUse(p->m_ID))
			{
				p->assignRightChop();
			}

			//Ok if you own both chops then use it
			if((p->pPhil->leftChopOwner(p->m_ID) == p->m_ID) 
				&& (p->pPhil->rightChopOwner(p->m_ID) == p->m_ID))
			{
					p->m_ReadyToEat = 0;

					int leftStatus = p->pPhil->leftChopOwner(p->m_ID);
					int rightStatus = p->pPhil->rightChopOwner(p->m_ID);

					//printf("\n[%s] (Status= %d) %d thread ID (%d) is EATING. His Left Status=%d, Right Status=%d\n",asctime (ts),p->m_ReadyToEat, p->m_ThreadID, p->m_ID, leftStatus, rightStatus);
					printf("\n[%s] (Status= %d) %d thread ID (%d) is EATING.\n",asctime (ts),p->m_ReadyToEat, p->m_ThreadID, p->m_ID);

					p->process();
					

					//Set the old time
					oldtime = ntime;
					p->m_State = STATE_EATING;

					p->pPhil->resetLeftChop(p->m_ID);
					p->pPhil->resetRightChop(p->m_ID);
					continue;
			}
		}

		if(ntime > oldtime + ALLOCTIMEFRAME)
		{

		 	if(	!p->m_ReadyToEat )	
			{
				p->m_ReadyToEat ^= 1;
				p->m_State = STATE_THINKING;
			}
			
			//printf ( "Time elapsed. Current time: %s", asctime (ts) );

			oldtime = ntime;
			ts = localtime(&ntime);
		
			leftStatus = p->pPhil->leftChopOwner(p->m_ID);
			rightStatus = p->pPhil->rightChopOwner(p->m_ID);

			//printf("\n[%s](Status= %d) %d thread ID (%d) is THINKING.His Left Status=%d, Right Status=%d\n", asctime (ts), p->m_ReadyToEat, p->m_ThreadID, p->m_ID,leftStatus,rightStatus);
			//printf("\n[%s] (Status= %d) %d thread ID (%d) is THINKING. Ready to Eat = %d\n",asctime (ts),p->m_ReadyToEat, p->m_ThreadID, p->m_ID, ((p->m_ReadyToEat)?1:0));
		}

		
		printf("\n[%s] (Status= %d) %d thread ID (%d) is THINKING. Ready to Eat = %d. LeftOwner = %d RightOwnder = %d\n",asctime (ts),p->m_ReadyToEat, p->m_ThreadID, p->m_ID, ((p->m_ReadyToEat)?1:0),leftStatus,rightStatus);
			
		if( WaitForSingleObject(gEvent,5000) == WAIT_OBJECT_0) break;

		Sleep(1000);
	}
		
	printf("Thread %d is exiting.\n", p->m_ThreadID);
	//return 0;	
}

void Thread::assignChops(int threadID, int id, int size)
{
	if( id < size ) rightChop = id+1;
	else rightChop = 0;

	if( id > 0 ) leftChop = id-1;
	else leftChop = size;

	if( id == 0 ) leftChop = size - 1;
	if( id == size - 1) rightChop = 0;

	printf("\n%d thread ID (%d) is assigned left chop = %d and right chop = %d.\n", threadID, id, leftChop, rightChop);
}

void Thread::assignLeftChop()
{
	pPhil->assignLeftChop(m_ID);
}

void Thread::assignRightChop()
{
	pPhil->assignRightChop(m_ID);
}


char* Thread::getStatus(int state)
{
	char* s;
	switch(state)
	{
		case(STATE_THINKING):
			s = "STATE_THINKING";
			break;
		case(STATE_EATING):
			s = "STATE_EATING";
			break;
	}
	return s;
}

//Do whatever in this process
void Thread::process()
{
	int value = 0;
	for(int i=0;i<20000;i++)
	{
		value = (i *(3000/45) + 3.2345 )* (0x20^4);
	}
}

/////////////////////////////////////////////////////////
//Phil.cpp
//Phil.cpp

#include<stdio.h>
#include "Phil.h"


Phil::Phil()
{
	gEvent = CreateEvent(NULL,true,false,NULL);
	memset(m_ChopStatus, -1,sizeof(ChopStatus)* MAX_PHIL);
}

void Phil::process(void)
{
	time_t oldtime, newtime= 0;
	struct tm  *ts;
	oldtime = time(0);

	ts = localtime(&oldtime);
	printf("\n\nStarting time: %s", asctime (ts) );
	
	for(;;)  
	{
		time_t ntime = time(0);

		if(ntime > oldtime + TIMEFRAME) 
		{
			SetEvent(gEvent);
			break;
		}
	}
}
	
void Phil::initiate()
{
	for(int i =0;i<MAX_PHIL; i++)
	{
		m_pThreadArray[i] = new Thread();
		m_pThreadArray[i]->pPhil = (Phil*)this;
		m_pThreadArray[i]->m_ID = i;

		m_ChopStatus[i].chopID = i;
		m_pThreadArray[i]->assignChops(m_pThreadArray[i]->m_ThreadID, m_pThreadArray[i]->m_ID, MAX_PHIL);
	}
}

void Phil::clean()
{
	for(int i =0;i<MAX_PHIL; i++)
	{
		delete m_pThreadArray[i];
	}
}

int Phil::getStatusForLeftNeighbor(int id)
{
	if(id == 0) 
		return m_pThreadArray[MAX_PHIL-1]->m_State;
	else
		return m_pThreadArray[id-1]->m_State;

}
	
int Phil::getStatusForRightNeighbor(int id)
{
	if(id == MAX_PHIL-1)
		return m_pThreadArray[0]->m_State;
	else
		return m_pThreadArray[id+1]->m_State;
}

int Phil::getIDForLeftNeighbor(int id)
{
	if(id == 0) 
		return m_ChopStatus[MAX_PHIL-1].chopID;
	else
		return m_ChopStatus[id-1].chopID;

}
	
int Phil::getIDForRightNeighbor(int id)
{
	if(id == MAX_PHIL-1)
		return m_ChopStatus[0].chopID;
	else
		return m_ChopStatus[id+1].chopID;
}

bool Phil::leftChopInUse(int id)
{
	return (m_ChopStatus[getIDForLeftNeighbor(id)].ownedBy == -1)?false:true;
}

int Phil::leftChopOwner(int id)
{
	return (m_ChopStatus[getIDForLeftNeighbor(id)].ownedBy);
}

bool Phil::rightChopInUse(int id)
{
	return (m_ChopStatus[getIDForRightNeighbor(id)].ownedBy == -1)?false:true;
}

int Phil::rightChopOwner(int id)
{
	return (m_ChopStatus[getIDForRightNeighbor(id)].ownedBy);
}


void Phil::assignLeftChop(int id)
{
	m_ChopStatus[getIDForLeftNeighbor(id)].ownedBy = id;
}

void Phil::assignRightChop(int id)
{
	m_ChopStatus[getIDForRightNeighbor(id)].ownedBy = id;
}

void Phil::resetLeftChop(int id)
{
	m_ChopStatus[getIDForLeftNeighbor(id)].ownedBy = -1;
}
	
void Phil::resetRightChop(int id)
{
	m_ChopStatus[getIDForRightNeighbor(id)].ownedBy = -1;
}

//////////////////////////////////////////////////////////

Open in new window

openujsAsked:
Who is Participating?
 
Infinity08Commented:
>> If I am doing checks (with functions: p->pPhil->leftChopOwner(p->m_ID) == p->m_ID) to grab chopstick only if noone owns it (owner == -1), so why do i even need mutex object. isnt mutex object going to do what I am doing already (lock the chopstick if someone else has already grabbed it).

The thing is that the code that performs the check-and-grab is not atomic. In other words, if a thread switch happens right in the middle of it (eg. between the check and the grab), you run the risk that both threads succeed with the check, and thus both grab the chopstick. This is exactly what you want to prevent with a mutex : only one thread can perform a check-and-grab for the same chopstick at any given time.


>> But yes I can add code to release the chopstick immediately if other pair(right or left) not available (has different owner) to avoid deadlock.

That is absolutely necessary to make the dining philosopher problem work :) Otherwise all philosophers try to grab one or two chopsticks, and then hold on to it forever. Maybe one is lucky, and he gets two, but it could also be that all philosophers get exactly one chopstick.
It is essential that chopsticks are released if the philosopher cannot get both (ie. it's all or nothing).
0
 
Infinity08Commented:
>> 1. when philosohers are not eating, they are thinking ( for now I defined that time for 10 sec), so should i have sleep() when they are thinking or keep running the loop.

A sleep is just fine. Note that it is not necessarily precise to the millisecond, but then again, this is not a real-time system heh :)


>> 2. This code is very CPU intensive, I added sleep(1000) end of the loop, that helped. Is there any other way i can optimize the code for less CPU  intensive.

When a thread is not doing anything useful, make it sleep. That way, other threads get a chance to do their stuff. If all threads are sleeping, nothing happens (no CPU is consumed).
Note that if you do not actually want to wait for a given amount of time, but simply want to pass control to another thread iff another thread wants to run, then use Sleep(0). This immediately returns when no other thread wants to run.

Note that the process method you use now should probably also be a sleep.


>> 3. Only one philosopher gets to eat at a time, what can be done so that atleast a few philosophers can start eating. Do you think that is because of deadlock.

When a philosopher does not manage to get both chops (but he might have gotten one), make sure to release the chop he has, so his neighbor can get a chance of getting both.
Also, make sure to set your status correctly.


>>  I will be implementing Mutex or Semaphore next but this exercise entails how deadlock can occur and why there is a need for synchronization object.

You will need mutexes (or similar) to make this work properly.


>> 4. For next exercise I will be using Synchronization object. Which one i should use - CS, Mutex, Semaphore and why?

Try to think about what behavior you need from the synchronization object, and then see which one fits best.
0
 
openujsAuthor Commented:
One thing I just thought about - If I am doing checks (with functions: p->pPhil->leftChopOwner(p->m_ID) == p->m_ID) to grab chopstick only if noone owns it (owner == -1), so why do i even need mutex object. isnt mutex object going to do what I am doing already (lock the chopstick if someone else has already grabbed it).
But yes I can add code to release the chopstick immediately if other pair(right or left) not available (has different owner) to avoid deadlock.
0
 
itsmeandnobodyelseCommented:
>>>>             if( WaitForSingleObject(gEvent,5000) == WAIT_OBJECT_0) break;
If the gEvent would be in non-signaled state, it already would wait for 5 seconds cause 5000 is a timeout in milliseconds. So, you wouldn't need a Sleep after that. If the gEvent would be in signaled state, you would break the loop and finish.

If neither happened on that statement it is somewhat wrong with the gEvent.

On the other hand, 5 seconds is so much that you hardly ever will experience a dead-lock or a conflict. Even the Sleep(0) Infinity mentioned - will last about 15 milliseconds on a normal Windows system, what means that the philosophers most time were thinking and hardly will get a conflict for the fraction of a millisecond they actually were trying to grap the forks. That means if you want to get a real conflict you have to put the Sleep(0) between checking and grapping so that it is a fair chance that two threads would check nearly same time and because both got a go they would (try to) become owner of the fork. The goal of synchronisation is to make the check and grab for a fork an exclusive process where only one thread (the first one) would succeed while the second (or third) would be blocked until the first thread has freed the resource.

>>>> I will be using Synchronization object. Which one i should use - CS, Mutex, Semaphore and why?
On Windows a critical section (CS) is a fast mutex which is much faster than a (named) mutex or semaphore. But a  CS cannot used between processes but only between threads of one process. As that is exactly what you need, a CS is best in your case,

There is another synchronisation which is faster than CS. It is based on atomic incrementation. Given a shared integer which initially is zero and declared as volatile, threads which want to run a sequence of code exclusively would increment that integer using an atomic operation offered by the OS. Then each thread would check whether the result of the incrementation is 1. If so it would enter into the code which should run exclusively. If the result of the incrementation is greater 1, the thread "knows" that another thread must have incremented the integer before and it would then decrement (also atomically) the integer to reverse the own incrementation, wait a little time, and try again.

   while (InterlockedIncrement(&lockflag) > 1)
   {
          InterlockedDecrement(&lockflag);
          Sleep(0);  
   }
   // coming here we are exclusive cause we were first to increment the lockflag
   ...
   // free lockflag (would release blocked threads if they were in the above while loop)
   InterlockedDecrement(&lockflag);

0
 
openujsAuthor Commented:
Great solution
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.