The bankers algorithm seems to be a pretty simple algorithm, essentially what you do is have some defined amount of resources, and then you kick off a bunch of threads, now if there are resources left, the thread can run and do it's thing, but if there are no resources, the thread must wait.
Deadlock
The key here we need to ensure is that there is no possibility of a deadlock. A deadlock occurs when two processes are waiting on each other to run. This can happen if we lock the mutex to try to see if we have resources, and then we don't let it go if the resource doesn't exist. For example the following situation would produce a deadlock.
1. thread 1 locks the mutex, gets the last resource, and unlocks the mutex.
2. thread 2 locks the mutex, no more resources exist so, thread 2 waits for resources, (not unlocking the mutex).
3. thread 1 is finished doing it's work, and needs to return the resources. It trys to get the mutex, it's blocked until thread 2 is done, but thread 2 won't give up the lock until thread 1 is finished.
This can be avoided by forcing thread 2 to lock the mutex, check for resources, unlock mutex, then check again if needed by doing it all over again. Now when thread 2 locks the mutex, and thread 1 tries to lock it, thread 2 releases it shortly later, and then thread 1 gets it, finally the next time thread 2 comes to lock the mutex, it now has resources and can run. See? Deadlock resolved!
Additional Thoughts
Reading up on the bankers algorithm on wikipedia, it defines that each thread should declare how many system resources it will eventually need, and if the number of resources it needs is more then the system has remaining it must wait until the resources are available, since my implementation only requests one resource at a time, I didn't see the need to declare how many it would use. But my understanding of this is that the thread has itself a max number of instances allowed, so it has a max that it needs to check on. So essentially there are two resources each thread needs to handle, a system and a local, if it exceeds the local, this is an error condition, so it needs to be handled appropriately, if it exceeds the system, again it's an error and needs to be handled appropriately.
 |
| Bankers Algorithm Running |
I hope you enjoyed the information! Let me know if you have any questions!Customers are coming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Doin Something Time Consuming..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Customer Created..............Waiting until all customers are gone..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Doin Something Time Consuming..............Time to go home..............
Can you post your code on it ? I will try to learn some from it!
ReplyDelete