On Mon, 2002-11-04 at 00:39, William Lee Irwin III wrote:
> That would appear to require cycle detection, but it sounds like a
> potential breakthrough usage of graph algorithms in the kernel.
> (I've always been told graph algorithms would come back to haunt me.)
> Or maybe not, deadlock detection has been done before.
For a spinlock it doesn't appear to be insoluble.
Suppose we do the following
For
spin_lock(&foo)
current->waiting = foo;
foo->waiting += current;
If foo is held
Check if foo is on current->locks
If it is then we shot ourself in the foot
Check if any member of foo->waiting is waiting on a lock
we hold (in current->locks)
If it is then we shot ourselves in both feet
When we get the lock
foo->waiting -= current;
foo->held = current;
current->locks = foo;
For
spin_unlock(&foo)
if(current->locks != foo)
We released the locks in the wrong order
remoe foo from current->locks
Alan
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Thu Nov 07 2002 - 22:00:32 EST