CFGReader

platform and bridge

    A. First Edition

    I am practicing with multi-thread.

    B.The problem

1. Tourists in Mont-Tremblant can hike to a platform to get a wonderful view of the mountains. The platform is precariously placed and can hold at most 5 people at a time. The path to the platform is through an old bridge which can hold only 3 people at a time. To prevent either the bridge or the platform from collapsing, the tourist processes execute the following code, with the initial values of the semaphores being set to 5 for ``platform'' and 3 for ``bridge''.

              P(bridge);          /* Ensure that there is place on the bridge */
              ENTER BRIDGE
              TOURIST ON BRIDGE
              P(platform);        /* Ensure space on platform before leaving bridge */
              HOP FROM BRIDGE TO PLATFORM
              V(bridge);          /* Let somebody get on the bridge */
              DO SIGHTSEEING
              P(bridge);          /* Coming back; ensure a place on the bridge */
              HOP FROM PLATFORM TO BRIDGE
              V(platform);        /* Let someone get on the platform */
              TOURIST ON BRIDGE
              EXIT BRIDGE
              V(bridge) ;         /* Let someone else get on the bridge */

   Unfortunately, the above code results in a deadlock when there are 5 tourists on the platform and 3 on the bridge headed towards the platform. Note that the tourists on the bridge are not allowed to go back without seeing the sights. Suggest a simple solution to avoid deadlocks, which blocks a tourist when entering the bridge (going towards the platform) if there is a possibility of a deadlock. Your solution should be in two steps: (i) a description in English text of your strategy, and (ii) a pseudo-code extension using additional semaphore(s) and/or shared variable(s).

¡¡

C.The idea of program
¡¡

    If you limit the sum of people on bridge and platform to below 8, then it is ok. So simple a question, right?

    D.The major functions

    E.Further improvement

    One problem puzzles me a lot is the sequence of ready queue in Windows, it seems that some thread always gets

    a chance to run even I forced them to sleep. Unfortunately in XP, I cannot use some functions like "SwitchToThread"

    which is available on win 2k.

    F.File listing

    1. main.cpp (main)

    ¡¡

    ¡¡

    file name: main.h

    //#include <iostream>
    #include <windows.h>
    #include <stdio.h>
    //using namespace std;

    void sightSeeing(char* myName);

    unsigned long __stdcall run(void* param);

    const int VisitorNumber=26;
    void* visitors[26];
    int times[VisitorNumber]={0};
    void* bridge;
    void* platform;
    void* mutex;
    int count=0;
    int total=0;
    bool finish=false;

    int main()
    {
    	char name[VisitorNumber];
    	platform=CreateSemaphore(NULL, 5, 5, NULL);
    	bridge=CreateSemaphore(NULL, 3, 3, NULL);
    	mutex=CreateMutex(NULL, false, NULL);

    	for (int i=0; i<VisitorNumber; i++)
    	{
    		name[i]='A'+i;
    		visitors[i]=CreateThread(NULL, 0, run, (void*)(name+i), 0, NULL);
    	}
    	while (count<1000)
    	{
    		SleepEx(0, false);
    	}
    	finish=true;
    	SleepEx(0, false);
    	SleepEx(0, false);
    	SleepEx(0, false);
    	for (i=0; i<VisitorNumber; i++)
    	{
    		printf("visitor %c visits %d \n", 'A'+i, times[i]);
    	}
    	return 0;
    }

    void sightSeeing(char* myName)
    {
    	printf("%c oh...\n", *myName);
    }

    unsigned long __stdcall run(void* param)
    {
    	while (!finish)
    	{
    		WaitForSingleObject(mutex, INFINITE);
    		if (total<7&&times[*(char*)(param)-'A']<60)
    		{
    			total++;
    			count++;
    			ReleaseMutex(mutex);//let others to go

    			//before bridge
    			WaitForSingleObject(bridge, INFINITE);
    			//before platform
    			WaitForSingleObject(platform, INFINITE);
    			//hop on platform
    			ReleaseSemaphore(bridge, 1, NULL);
    			//see ....
    			sightSeeing((char*)param);
    			times[*(char*)(param)-'A']++;
    			SleepEx(0, false);//stay for a while...
    			//SwitchToThread();
    			//go down to bridge
    			WaitForSingleObject(bridge, INFINITE);

    			//
    			ReleaseSemaphore(platform, 1, NULL);
    			ReleaseSemaphore(bridge,1, NULL);
    			//WaitForSingleObject(mutex, INFINITE);
    			total--;
    			SleepEx(0, false);
    			//ReleaseMutex(mutex);
    		}
    		else
    		{
    			ReleaseMutex(mutex);
    			SleepEx(0, false);
    		}
    	}
    	return 0;
    }

    ¡¡

    The input is something like following:

    Here is the result:

    ...

    ...

Q oh...
V oh...
W oh...
X oh...
R oh...
S oh...
C oh...
D oh...
Y oh...
T oh...
U oh...
J oh...
Q oh...
V oh...
W oh...
X oh...
R oh...
visitor A visits 60
visitor B visits 60
visitor C visits 24
visitor D visits 24
visitor E visits 1
visitor F visits 60
visitor G visits 60
visitor H visits 60
visitor I visits 60
visitor J visits 25
visitor K visits 60
visitor L visits 60
visitor M visits 60
visitor N visits 60
visitor O visits 60
visitor P visits 60
visitor Q visits 24
visitor R visits 24
visitor S visits 23
visitor T visits 23
visitor U visits 23
visitor V visits 23
visitor W visits 23
visitor X visits 23
visitor Y visits 22
visitor Z visits 0
Press any key to continue