Subj : Re: Challenge: Multithreading & Synchronization To : comp.programming.threads From : doug Date : Wed May 18 2005 07:27 pm "Uenal Mutlu" <520001085531-0001@t-online.de> wrote in message news:d6fqq3$522$00$1@news.t-online.com... > "doug" wrote >> >> "Uenal Mutlu" wrote in message >> > "Sergei Organov" wrote >> >> "Uenal Mutlu" writes: >> >> >> Your challenge would be good, and I might even do it myself, *if*: >> - I didn't know you were just asking so you can turn around and say 'but >> look, my program already does it!' > > Which "my" program? > Do you mean the deadlock detector program? It has nothing to do with that. It seems your deadlock detector is the perfect program to analyse this piece of code/junk. However, I'd hope the output from the fully completed program would be 'error: program fucked. please rewrite sensibly, and this time, TAKE YOUR TIME'. > >> - I thought your program was useful beyond the extremely simple programs >> it >> is designed for (i.e. the example you've given, which doesn't allow for >> flow >> of control, dynamically generated objects, or collections of objets at >> the >> same 'rank'). > > If that's so important to you then why not simply add the functionality > you want or need, since you have the source. Or why not simply write your > own? > If I understand your requirements right then IMO all of them are already > possible. > Only the last one "collections of objects at the same 'rank'" I don't > understand well. We have written our own, much better, system. But, unlike you, who seems to think you have the answers to it all, we "stood on the shoulders of giants" and copied people smarter than we are. Take one project I work on. We have this functionality built into the product, in code - it's done at runtime. It can be disabled via configuration. The runtime sema4 checker monitors usage of all sychronisation primitives in the system. (We use an 'isolation layer' for each operating system, and wrap the basic sync primitives up to a standard interface. Thus SEMACQ becomes pthread_mutex_lock on *nix and EnterCriticalSection on win32. All macro'd, so transparent from a PoV of performance. It's then an easy matter to add hooks to the runtime sema4 checker). The checker is used to do two important things: - whenever a semaphore is created, it's class and rank are registered with the checker (e.g. ControlBlockSema4, rank 4) - whenever acquire/release is performed, the checker scans the locks currently held by that thread, and ensures the new acquire obeys the hierarchy (with respect to all semaphores in the same class) This is not bulletproof - it will not detect all deadlocks. The fact that it's done at runtime in a dynamic system, and the fact that the code acts differently (timing differences) when the checker is disabled, means that it's not rock solid. However, the alternative, static analysis, is just impossible on a system of this size. This is a common thing to do in carrier-class servers. It's all over the web. The fact you don't recognise it should say something. The last part, semaphores of the same rank, is a more complex idea. Say you have an array of control blocks, or CBs. These are dynamically generated, so there's no way to construct a semaphore hierarchy/ruleset/whateveryouwanttocallit a priori. Each has a semaphore, which you must hold while manipulating the CB. Now, say you have an operation that requires you to transfer the contents of one CB to another. So, you need to grab two CBs. But there's no hierarchy here that will be safe - this is complicated, and takes a long time to explain, so I won't here. The essence is that, even with a simple ordering such as CB address in memory, you cannot prevent deadlock. In a pathalogical case, you can build a chain of dependencies, blocking threads in teh chain, which grows until your system dies from thread exhaustion. At best, this pathalogical case will result in performance degradation. Even so, it's not good enough. The solution is to introduce a 'control semaphore' for the class. If you want to acquire one of the CBs, you must first grab the control sema4. Then you grab the CB (or as many CBs as you want), then you release the control sema4. Then you work on the CB, then your release it's sema4. If, while working you find you need to access another CB, you must drop the lock on the current CB. In its simplest form, you've introduced another semaphore to the hierarchy (in teh same class as the CB sema4s), above the individual CB semaphores (which are all at the same level), and added an interface rule - "you MUST acquire the CB control sema4 before acquiring an individual CB sema4. On of the points I think you miss is that hierarchical locking allows for tree structures (and sometimes, even more complicated graph structures). > >> By the way, i'm still waiting for your pseudocode implementation of a >> recursive mutex that doesn't use memory barriers on lock() if it already >> owns the semaphore. I don't think it an be done, but I'm keeping an open >> mind! > > I've been busy with other stuff, like this one :-) > I'll try to answer when I find some free time. > > > ok, ok, this is not supposed to be a flamefest, and some of us are getting a bit tetchy with you, I admit. But try to walk before you run. We ask you questions, or point out problems, and you seem to ignore them. The problem is that we're pointing out problems in your *basic* assumptions. Instead of stopping, stepping back, and thinking for a second, you sideline the issue, and keep forging ahead using incorrect bases for your conclusions and (admittedly rare) arguments. As I said again, let's start again, from the beginning. Show me pseudocode for a recursive mutex. Please don't ignore people's questions in posts! Doug .