Subj : Re: Deadlock theorem To : comp.programming.threads From : doug Date : Tue May 03 2005 10:07 pm "doug" wrote in message news:vVQde.23650$Cq2.9246@fe2.news.blueyonder.co.uk... > Lots here - search for DGC > > "Uenal Mutlu" <520001085531-0001@t-online.de> wrote in message > news:d58at0$b22$04$1@news.t-online.com... >> "doug" wrote >>> 'fraid not, it was something I was taught at Uni. >>> >>> You've had a long conversation above with David and Joe, and I won't >>> repeat >>> any of it, but I'm afraid I agree with them. Your solution may work, >>> but >>> it's too complicated for general use. As David points out, you have to >>> know >>> the entire history of a thread and the locks it has obtained and >>> released. >>> This is simply impossible in real life (one of the projects I work on >>> has a >>> few hundred threads, three milion lines of code, and several thousand >>> semaphores - we use a runtime 'semaphore hierarchy checker' (in debug >>> builds) to ensure acquires follow the hierarchy). >> >> No, you just need to make a list of all your shared objects and >> do the lockings in each thread always in the same sequence >> (the most intuitive would be "top-down"). Example: >> >> List of objects: >> o1 >> o2 >> o3 >> o4 >> o5 >> >> In any of the threads the objects must be locked in the >> same sequence (here using top-down): >> >> thread1: wants to use o2 and o5 >> o2.Lock(); >> o5.Lock(); >> >> thread2: wants to use o1 and o5 >> o1.Lock(); >> o5.Lock(); >> >> thread3: wants to use all >> o1.Lock(); >> o2.Lock(); >> o3.Lock(); >> o4.Lock(); >> o5.Lock(); >> >> thread4: wants to use o5 and o2 >> o2.Lock(); >> o5.Lock(); >> >> thread5: wants to use just o2 >> o2.Lock(); >> >> thread6: wants to use o3, o5, o1 >> o1.Lock(); >> o3.Lock(); >> o5.Lock(); >> >> >> Following this schema no deadlock will happen ever. >> I wonder why you see this schema to be too complicated. >> It's IMO so simple to follow and apply. >> > > > DGC: > Dunno mate. I think you're just describing a hierarchy. Look at what > you've done above. It is nothing more than hierarchical locking. > o1->o2->o3->o4->o5. A very simple one (a completely unbalanced tree), but > still a hierarchy. > > It seems to me that *you're* the one complicating things. > >>> Your addition of rule C doesn't change anything for me. I see it an >>> unnecessary, when it would be covered by rule a) - i.e. always grab in >>> the >>> same order. This implies releasing anything any sema4 higher in the >>> hierarchy. >> >> Hmm. not true, neither for "higher" nor "lower" in the hierarchy. >> Ie. there is no such requirement. If one can be locked then it >> will be, this is independent of the "hierarchy". >> >> The objects are locked automatically in the most efficent way >> for the least necessary time (ie. no object is locked unnecessarily >> (and by this blocking other threads) compared to other methods >> of locking a group of objects). That is: a group locking is performed >> by locking items in the group individually. IMO this individual locking >> method is faster than to lock just the group container. >> > > DGC: > A sema4 hierarchy (or locking hierarchy) in its simplest form is a tree. > Semaphores in distinct subtrees have no direct relationship with each > other, and hence are not subject to the locking hierarchy (w.r.t. each > other). > > You've missed this in your reading/thinking of the concept/pattern. > >>> Your rule (c) would have us discard all semaphores. >>> To my mind, the result will be less efficient (due to more releases and >>> acquires) and more complicated (due to having to fit the program locking >>> to >>> your artificial constraints) than the well known method. >> >> This might look so but in practice it isn't if Lock() and Unlock() are >> fast implementations (using atomic counter aka fast InterlockedOps). > > DGC: > Is this supposed to be portable? You're making up excuses/reasons now > after the fact. Please stop. Didn't mean to be so short. Long day. My apologies. Pls ignore. > >> >>> Don't mean to rain on your parade - it's good you're thinking about how >>> to >>> extend/change/enhance existing ideas. But you should also be totally >>> familiar with existing concepts. Grep for "hierarchical locking" on >>> google >>> and have a scan of a few links. >> >> Thx, I did so. It is definitely not hierarchical locking. >> >> > > .