[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

RE: [PATCH] Robust and Real-time Mutexes in NPTL

> From: Carlo Wood <carlo alinoe com>
> I am having some ideas to detect possible dead-locks *before*
> they actually happen.  I don't think I will have time to
> actually implement this though, so I thought I might run the
> idea past you; perhaps you are interested to write an
> implementation for this.

> ...

> So, basically one would need to make a list of all locks
> involved and assign an 'ordering' to them.  If thread '1'
> locks X and then locks Y, then we could "define" that X < Y.
> When later another thread first locks Y and then X, we notice
> that it is no longer possible to define an ording for the
> mutexes and barf.

We do this already; it is done at the kernel level; it has
to change a wee bit (to allow enabling/disabling it) but
basically is that: when you are about to block waiting for
a lock, the ownership list is walked, the owner of the lock
you are waiting for; if that owner is waiting, the owner of
the lock he is waiting for, and so on, until the owner is
not waiting for any locks (green light) or it points back 
to you--deadlock.

The only issue with this is that it is a O(N) algorithm,
and there is no way to go around that, like it or not;
hopefully, in most correct designs, that N is going to be
low, so it should not be of big importance; still, it needs
to be switchable.

It gets to be funnier when you allow tasks to be waiting
on more than a mutex at the same time (similar to what 
FUTEX_FD did), so that's why I am not even considering that,
and AFAIK, nobody but NGPT is using it right now, so I don't
plan to implement it.

> The REAL challenge is to make this work with arbitrary
> priority mutexes }:-).

This is where rwlocks mutate from being something stupidly
simple to be a nightmare (not to talk about priority inhe-
ritance _or_ robust rwlocks). I have been working on this
for maaaany months already and I still have to find some-
thing completely satisfactory (for example, the actual 
kernel code is a mess--it needs a whole rehaul in design
and concept). Not to talk about finding a sollution that
Ulrich considers acceptable (actually he is something like
my yardstick for messiness...if he doesn't dismiss something,
then you can start to consider it might be on the right

> Since this has everything to do with robustness, I hope I
> interested you.


Iñaky Pérez-González -- Not speaking for Intel -- all opinions are my own (and my fault)

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]