deadlock detection problem mysql/php problem
here my problem:
i am developing a web application allowing you to create modules(a piece of code to execute) and execute them. One particularity about the application is that you can make compositions of modules. i.e. a module can be composed of several other modules. I have designed a scenario below so that you can understand more easily:
i have 8 modules: 1,2,3, 4,5,6,7 and 8
I have my initial setup (Scenario 1)
http://forums.codeguru.com/
Module 1 is composed of module 2 and 3.
Module 2 is composed of module 4 and 6.
Module 5 is composed of module 1 and 7.
Module 8 is composed of module 5
Execute module 1:
Now,e.g., if i execute module 1... it will execute module 2 + module 3.
As module 2 is composed of module 4 and 6, the latters will also be executed.
This is the execution chain. In the diagram, the left hand side shows all the modules that are actually executed
http://postimage.org/image/5cspmguc/
The problem
In scenario 1, everything is ok and executes smoothly... but in scenario 2, i add module 5 to module 1.
When you execute module 1, it will execute module 2, 3 and 5. As module 2 is a composition, it will also executes module 4 and 6 found in module 2. And as module 5 is a composition too, it will execute module 1 and 7 found in 5.
The problem is that the module 1 found in module 5. It will also execute.... you can see that this will result in an infinte loop!!! kind of a deadlock!
same thing happens in scenario 3 where i add module 8 to module 1. Module 8 has module 5 as child and the latter has module 1 as child. This will also result in a deadlock!!
What is the solution??
My problem is how to detect such deadlocks?? When i am composing module 1, e.g., i should not be given the option to add module 5 or module 8 as they would cause a deadlock....
In my interface, when i am composing/editing a module, i am giving a list of all modules available (1,2,3,4,5,6,7,8) which i can click and add to the module i am composing/editing. I need to filter/hide all the modules that will cause a deadlock.
database structure
Below is my database structure:
http://imageshack.us/photo/my-images/840/tablesq.png
The values in the tables are for scenario 1.
and i am using javascript/html, php and mysql. I have idea how to efficiently detect these deadlocks... can it be done all in a query? (e.g. when i am editing module 1, i write a query to fetch only modules that will not cause deadlocks)
Your advices and tips are most welcomed.. thx for reading this lengthy topic.
Re: deadlock detection problem mysql/php problem
just realised i haven't attached the pics properly; here they are:
1. scenarios
http://postimage.org/image/5cspmguc/
2.database
http://imageshack.us/photo/my-images/840/tablesq.png
Re: deadlock detection problem mysql/php problem
Quote:
Originally Posted by
yeahman45
My problem is how to detect such deadlocks?? When i am composing module 1, e.g., i should not be given the option to add module 5 or module 8 as they would cause a deadlock....
Strictly you don't have a deadlock. That terms is used for a certain concurrency problem.
To avoid cycles you must ensure that compositions always stay a DAG (Directed Acyclic Graph). So when a composition is defined it should be a DAG. And when it's changed you need to establish that it's still a DAG otherwise you must reject the change.
http://en.wikipedia.org/wiki/Directed_acyclic_graph
http://allisons.org/ll/AlgDS/Graph/DAG/