Didn’t mean to get sucked back into this thread but can’t resist.
while (1)
{
lock(a)
manipulate(A); // A is protected by A
lock(b);
manipulate(B);
manipulate_some_more(A); // A still locked for good reasons
unlock(B);
unlock(A);
// time passes
lock(b);
mung(B);
lock(a);
mung(A, B); // both locked
unlock(a);
unlock(b);
}
This code may be safe if it can be guaranteed that there is never
concurrent executions of this code and that all other parts of the
driver that access these locks (these must exist or there is no reason
to have locks at all) only ever lock one at a time.
BUT!!!
This is all academic. Drivers change and evolve over time and
deadlocks, especially if there frequency is very rare (don’t show up
while debugging) are very nasty. Writing code like this is a ticking
time bomb waiting to go off and hurt you (or someone else) really
badly (usually long after you have forgotten what you did) and it is
just not necessary. It is just too easy to rewrite the code as follows:
while (1)
{
lock(a)
manipulate(A); // A is protected by A
lock(b);
manipulate(B);
manipulate_some_more(A); // A still locked for good reasons
unlock(B);
unlock(A);
// time passes
lock(a);
lock(b);
mung(B);
mung(A, B); // both locked
unlock(b);
unlock(a);
}
A is now always locked before B. The locking order can be documented
in the code where the locks are defined (probably the driver
extension). Yes, there is a small inefficiency because A is locked
sooner that it needs to be but it is a small price (if not, redesign)
to pay for driver robustness.
Robert Newton
Right time to say sorry to put such a topic and probably managed to steal cyles from you folks !!.
The second part of my question was “Information thoery”. As per my record, Shanon was the father of this and first coined entropy. He found that a third order approximation of random source of alphabet really produce lot of english words, there were basic research to trap encrypted signals …
-pro
Tony Mason wrote:
Actually, deadlocks are a well-known CS topic. There are (in essence)
TWO ways of handling deadlocks: detection or avoidance.
In a deadlock detection system, the ability to detect a deadlock is an
inherent part of the system. When a deadlock is detected a corrective
action is taken to break the deadlock. For example, in a transactional
system, one transaction is forced to abort and this allows the other to
continue. Such systems are really essential when we have large, complex
interaction schemes where there is no agreement upon cooperation. This
is a very common solution in the database world, for instance, where
random new applications can be written to access various records of
various tables and lock them.
In a deadlock avoidance system, the order of lock acquisition is modeled
in a hierarchy (or more formally a directed acyclic graph). Since there
is a canonical order for lock acquisition, there is no possibility of
deadlock (assuming correct implementation).
Now, what would be really cool is a way to express this
locking hierarchy in code and to have each lock acquisition
be able to ASSERT() that it was correct.
(I know I keep bumping up against the need to be able to ASSERT()
that I, as the current thread or processor, either own or don’t
own a given lock… but that is kind of just the first piece of
the problem.)
Not quite a deadlock detection system, but better than ‘you know
the rules…’
> Now, what would be really cool is a way to express this
locking hierarchy in code and to have each lock acquisition
be able to ASSERT() that it was correct.
Doesn’t DV do this? I’d find it much more useful to have a compile-time
analysis of locking-order & similar stuff 
Regards,
Paul Groke
Joseph Galbraith
Gesendet von: xxxxx@lists.osr.com
29.10.2004 22:19
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: Re: [ntdev] Locks and Deadlocks
Tony Mason wrote:
> Actually, deadlocks are a well-known CS topic. There are (in essence)
> TWO ways of handling deadlocks: detection or avoidance.
>
> In a deadlock detection system, the ability to detect a deadlock is an
> inherent part of the system. When a deadlock is detected a corrective
> action is taken to break the deadlock. For example, in a transactional
> system, one transaction is forced to abort and this allows the other to
> continue. Such systems are really essential when we have large, complex
> interaction schemes where there is no agreement upon cooperation. This
> is a very common solution in the database world, for instance, where
> random new applications can be written to access various records of
> various tables and lock them.
>
> In a deadlock avoidance system, the order of lock acquisition is modeled
> in a hierarchy (or more formally a directed acyclic graph). Since there
> is a canonical order for lock acquisition, there is no possibility of
> deadlock (assuming correct implementation).
Now, what would be really cool is a way to express this
locking hierarchy in code and to have each lock acquisition
be able to ASSERT() that it was correct.
(I know I keep bumping up against the need to be able to ASSERT()
that I, as the current thread or processor, either own or don’t
own a given lock… but that is kind of just the first piece of
the problem.)
Not quite a deadlock detection system, but better than ‘you know
the rules…’
- Joseph
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
xxxxx@tab.at wrote:
>Now, what would be really cool is a way to express this
>locking hierarchy in code and to have each lock acquisition
>be able to ASSERT() that it was correct.
Doesn’t DV do this? I’d find it much more useful to have a compile-time
analysis of locking-order & similar stuff
Well, I’m not sure what it DV does… does it have deadlock
detection?
I’m pretty sure it can’t do what I’m asking though, because
I haven’t told it anything about my locking hierarchy.
What I want is an ASSERT() the first time someone tries
to acquire the lock out of order (before the deadlock
doesn’t occur because I got unlucky.)
I agree a compile-time tool would by cool… but I wasn’t
sure that was even possible. I’m pretty sure the ASSERT()
is possible, I’m just not sure it is possible to make
it simple enough to be usable.
DV has deadlock detection. It recoeds the order of locks taken, and if you
try to use a different order it screams.
–
Don Burn (MVP, Windows DDK)
Windows 2k/XP/2k3 Filesystem and Driver Consulting
Remove StopSpam from the email to reply
“Joseph Galbraith” wrote in message news:xxxxx@ntdev…
> xxxxx@tab.at wrote:
> >>Now, what would be really cool is a way to express this
> >>locking hierarchy in code and to have each lock acquisition
> >>be able to ASSERT() that it was correct.
> >
> >
> > Doesn’t DV do this? I’d find it much more useful to have a compile-time
> > analysis of locking-order & similar stuff
>
> Well, I’m not sure what it DV does… does it have deadlock
> detection?
>
> I’m pretty sure it can’t do what I’m asking though, because
> I haven’t told it anything about my locking hierarchy.
>
> What I want is an ASSERT() the first time someone tries
> to acquire the lock out of order (before the deadlock
> doesn’t occur because I got unlucky.)
>
> I agree a compile-time tool would by cool… but I wasn’t
> sure that was even possible. I’m pretty sure the ASSERT()
> is possible, I’m just not sure it is possible to make
> it simple enough to be usable.
>
> - Joseph
>
Don Burn wrote:
DV has deadlock detection. It recoeds the order of locks taken, and if you
try to use a different order it screams.
Wow… I stand corrected then. I’m glad I’m running with DV on
for my development
Thanks,