Windows Thread Synchronization 24

 

 

 

 

 

Six philosophers with six chopsticks

 

The dining table has 6 people with 6 chopsticks (may use different people and chopsticks number).   Six people sit around a table with a single chop stick between each two adjacent people.  A single bowl is placed in front of each of them.  Two chopsticks (on his left and right) must be in hand in order to eat noodle.  After he eats a bit of rice, he puts the chop sticks down for some time and thinks for another amount of time.  He repeats this process over and over again.  As can be seen, there are only six chop sticks. Deadlock is obviously possible in this case.  For instance, each of them grabs a chopstick on his right.  But, he cannot eat as there is no longer any chopstick to his left.  So, each diner waits for a left chopstick that may never arrive.

 

The Six philosophers with six chopsticks problem

 

 

Starvation Issue


Imagine that two diners are quick thinkers and quick eaters. They think faster and get hungry faster. Assume that, they are sitting down in the opposite chairs as shown below.

 

 

Because they are so fast, it is possible that they can lock their chopsticks and eat. After finish eating and before their neighbors can lock the chopsticks and eat, they start again and lock the chopsticks and eat. In this case, the other four diners, even though they have been sitting for a long time, they have no chance to eat. This is called a starvation. Note that it is not a deadlock because there is no circular waiting, and everyone has a chance to eat. Starvation happens when some thread gets deferred forever and violates the idea of fairness which each thread gets a turn to make progress. This just a simple example of starvation because you can find more complicated thinking-eating sequence that also can generates starvation.

 

The Six philosophers with Semaphore Program Example

 

The following solution to the problem using semaphore is based on the principle that, six chop sticks can only be used by three people, restricting only maximum three people that can attempt to eat at any one time.

Create a new empty Win32 console application project. Give a suitable project name and change the project location if needed.

 

The Six philosophers with six chopsticks example: Creating new Win32 empty console application project in Visual C++ IDE

 

Then, add the source file and give it a suitable name.

 

The Six philosophers with Semaphore Program Example: Adding new C++ source file to the existing project

 

Next, add the following source code.

 

// Solution to 6 diners with 6 chopsticks problem using semaphores

#include <windows.h>

#include <stdio.h>

#include <wchar.h>

#include <assert.h>

 

#define    Diners    6

 

// Global variables

// handle to see who attempts to eat

HANDLE hSemEat=NULL;

// binary semaphores for each chop stick

HANDLE hSemChopSticks[Diners];

// Handle to Philosophers

HANDLE hDiners[Diners];

// tell philosophers to stop

BOOL bStopDiners[Diners];

 

//////////Thread Code /////////

// Id from 0 to Diners-1

void DinerNum(int Id)

{

    // Can discard the limit for forever eating & thinking i.e. for(;;)

    for(;;)

      {

            wprintf(L" Diner #%d - Thinking, not enough chopsticks...\n", Id);

           

            if(bStopDiners[Id] == TRUE)

            {

                  ExitThread(0);

            }

      

        //  Wait till turn to eat/signaled

        WaitForSingleObject(hSemEat,INFINITE);

           

        // Pick chopsticks

        WaitForSingleObject(hSemChopSticks[Id],INFINITE);

        WaitForSingleObject(hSemChopSticks[(Id+1)%Diners],INFINITE);

          

        wprintf(L"  Diner #%d - Eating with two chopsticks...\n", Id);

 

        // Put down chopsticks

        ReleaseSemaphore(hSemChopSticks[(Id+1)%Diners],1,NULL);

        ReleaseSemaphore(hSemChopSticks[Id],1,NULL);

        // Release the right to eat

        ReleaseSemaphore(hSemEat,1,NULL);

        }

    }

 

//////////// Create the diners /////////////

void CreateDiners(void)

{

      int i;

     

      for(i=0;i<Diners;++i)

      {

            DWORD dwThreadID;

           

            // set flag off for stopping

            bStopDiners[i]=FALSE;

           

            hDiners[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)DinerNum,(LPVOID)i,0,&dwThreadID);

           

            assert(hDiners[i]!=NULL);

      }

}

 

 

////////////CreateSemaphores//////////

void CreateSemaphores(void)

{

    int i;

     

    // create eating semaphore

    // Initial and max are set to 3

    hSemEat = CreateSemaphore(NULL,Diners/2,Diners/2,NULL);

    assert(hSemEat!=NULL);

 

    for(i=0;i<Diners;++i)

      {

            hSemChopSticks[i]=CreateSemaphore(NULL,1,1,NULL);

            assert(hSemChopSticks[i]!=NULL);

      }

}

 

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

void AttemptToStop(void)

{

      int i;

 

      wprintf(L"\n=====Attempting to stop all threads=========\n\n");

     

      for(i=0;i<Diners;++i)

      {

            bStopDiners[i]=TRUE;

      }

     

    // wait for all threads to finish

    WaitForMultipleObjects(Diners,(CONST HANDLE *)hDiners,TRUE,INFINITE);

    }

 

/////////Close All Handles//////////

void CloseAllHandles(void)

{

      int i;

     

      for(i=0;i<Diners;++i)

      {

        CloseHandle(hDiners[i]);

        CloseHandle(hSemChopSticks[i]);

      }

     

      CloseHandle(hSemEat);

}

 

///// Main //////////

int wmain(void)

{

    CreateSemaphores();

    CreateDiners();

    AttemptToStop();

    CloseAllHandles();

    ExitProcess(0);

    return 0;

}

 

Build and run the project. The following screenshot is a sample output.

 

The Six philosophers with Semaphore Program Example: A sample of console program output

 

 

 

 

< Thread Synchronization 23 | Thread Synchronization Programming | Win32 Programming | Thread Synchronization 25 >