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