In my program, I'm currently using two large datastructures (a tree and a linked list) which are heavily dependant on each other. The tree's nodes contain pointers to the linked list's nodes.
Both datastructures have to update each other whenever a change occurs in either of them.
(jpeg diagram attached)
The multithreading:
There are some object instances M1, M2, M3 & M4 which are part of some thread instances. Any of these modules from any of these threads might decide to make a change to any of the nodes of the datastructures.
My issue is that when one thread is busy making changes to any node of the database, all the other threads have to wait, because if they try to change any part of the database, everything will get messed up because both databases are dependant on each other.
To avoid such thread waiting, which section of the architecture/design would you recommend that I change? and how?
I expected the diagram to have abit more and got a laugh when it said just 'extremely large data structure' 1+2 and some arrows, but I guess it is enough anyway.
Obviously, you have to break the link between the two data structures somehow. That's all there is to it. Just like your diagram is simple, so is the problem. Your issue is that doing that might be very difficult or even impractical, but without a detailed knowledge of what it's actually DOING it's impossible for us to say exactly how to do it better. Probably you need to have one single data structure that's more suited to...whatever it is that's going on, but it's probably something very complicated that might be too much to ask forumgoers to spend hours or days sorting out for you.
If that's impossible, try separating into multiple locks, on a section by section basis (or whatever). It won't help as much as a more thorough solution but it can speed things up a lot under OSes that support spinlocks.
@code_carnage:
I want to change the design. That's why I asked how it could be done better.
@originalfamousjohnsmith:
Thanks for replying. The diagram was intentionally kept simple because it's the design that I need to change. Nothing else.
Spinlocks are definitely not an option.
Actually, locks are something I'm trying to avoid altogether.
The problem is:
The algorithm for my problem has several layers of datastructures, with each of the higher layers having pointers to the lower levels, so that you can traverse from a higher level to any lower level.
It could have been implemented as one single data structure, but I've shown it as two separate boxes (layers) because I wanted it to be implemented in such a way that if a layer is first implemented as a linked list, later I should be able to change the linked list implementation with a tree implementation.
The trouble is:
There are plenty of threads which can access any layer of the datastructure at any time.
The layers are compulsory, but using multiple processors/cores doesn't make sense if the threads have to wait because of locks on the datastructure.
Isn't there any way/design to keep the locks useage to a minimum? I assume the major change would have to take place in the datastructure design.
Isn't there any way/design to keep the locks useage to a minimum? I assume the major change would have to take place in the datastructure design.
Sure, there's a million ways, but we'd have to know exactly what you are doing to make that judgement.
It's almost certain you can't get away with lockless programming in a case like this. It sounds like you have multiple readers and multiple writers problem, which always leads to a lot of contention (go ahead and look it up). If you can limit any part of this you can gain a lot - that is, limit to one writer and you gain a huge amount over the general anything goes atmosphere you have now.
Well I can't reveal how I'm implementing it, but your suggestion gave me an idea which just might work out.
It's been helpful to brainstorm about this idea. Thank you so much for your time and help
* The Best Reasons to Target Windows 8
Learn some of the best reasons why you should seriously consider bringing your Android mobile development expertise to bear on the Windows 8 platform.
Reply With Quote
Originally Posted by sd9
