Page 1 of 1
Deadlocks - what arer you doing about them
Posted: Sat Jan 06, 2007 4:15 am
by nitinjavakid
I was reading about deadlocks and found it quite a challenging topic. So, the question is; how are you handling deadlocks in your OS? Are you just ignoring them or using some technique?
Posted: Sat Jan 06, 2007 4:25 am
by Combuster
If an deadlock occurs in userspace, it is the fault of an application. And unless its a driver written by me its none of my business
In the kernel, I use a combination of the following:
- Wait-free code when supported (i.e. avoid the need for locking)
- Resource ordering (which is imo the easiest deadlock preventer existing)
Posted: Sat Jan 06, 2007 4:59 am
by m
Hi.
In theory if any of deadlock conditions(e.g. mutual exclusion) is not reached deadlock cannot occur.Yet there isn't a universal solution for all kinds of cases.So to face different occasions the solution should be specially designed.Here are some examples:
-For memory allocation:you can disable dynamic(runtime) memory allocation feature.That is,all memory is given when a process is initialized,so the requested size is fixed.In this way,deadlock on memory will not occur(because there's no allocation later during execution).
-For processes which are waiting for each other's signal:better to test it dynamicly using 2 tables for each process.The table contains processes it is waiting for.Regular tests will find out if the processes it's waiting for is also waiting for itself.(I'm not quite sure if others are using this link-like method,and also if this will work for a larger loop).
-General-about preemption:preemption can take place during runtime.If 2 processes are deadlocked for each other's resources,you cn make one suspend to free its resource for the other one to go on.When the other one has finished using the resource,you can hand it back to its original owner.(This can easily work for some kinds of resources.For memory,you can page a process out to an external storage to free the memory it takes up.)
Just for you to catch a glimpse...
Posted: Sat Jan 06, 2007 5:09 am
by Combuster
Before i forget, there's an article on the wiki:
Deadlock
Posted: Sat Jan 06, 2007 7:17 am
by nitinjavakid
Thanks a lot!
Re: Deadlocks - what arer you doing about them
Posted: Sun Jan 07, 2007 12:54 am
by carbonBased
nitinjavakid wrote:I was reading about deadlocks and found it quite a challenging topic. So, the question is; how are you handling deadlocks in your OS? Are you just ignoring them or using some technique?
Fixing deadlocks is an entirely huge and variable topic. I agree with m that a targetted approach at fixing each kind is always required.
Finding them is another one which is often difficult -- you're putting your OS through its paces, and all of a sudden it just stops. Why?
I don't know if this will be useful to you, but I've found that a specific debugging property (ie, #ifdef'd code) in my OS has provided me with useful insight. The code is an extremely simple addition to my mutex locks. Translate any indefinite mutex locks (aka, potential deadlocks) to timeout after 30 seconds. If this mutex reaches the timeout state, trace out the error as a deadlocked mutex, and the two thread handles involved (the one that's locked it indefinitly, and the one trying to lock it again).
--Jeff
Posted: Sun Jan 07, 2007 1:26 pm
by Candy
First, provide and promote methods that don't allow permanently locked mutexes. Secondly, ignore any other deadlocks.
I use a define that makes this code do exactly what you think it would:
Code: Select all
void something() {
locked(mutexA) {
// do something
}
}
It doesn't prevent deadlock (problem of logic) but it does prevent forgetting to unlock it / unlocking twice etc. The programmer should be the one taking care of the logic.
On the other hand, promote use of lockless algorithms. For example, most, if not all, mutexes can be replaced by using a compare-and-swap instruction instead. You load the original value, transform it, and then if it's still the same replace it with the calculated value. If not, you try again.
Programmers that make logic errors should be forced to fix them as much as possible. Programmers that have all their logic set right shouldn't be forced to type two commands when one can suffice.