platform and bridge
A. First Edition
I am practicing with multi-thread.
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).
If you limit the sum of people on bridge and platform to below 8, then it is ok. So simple a question, right?
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&×[*(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