Deadlock Error in Mutually Concurrent Go Routines

[Arpssss]

I have three concurrent go routines like below,

func Routine1() {
mutex1.Lock()

do something

mutex2.Lock()
mutex3.Lock()
send int to routine 2
send int to routine 3
* Print Something *
mutex2.Unlock()
mutex3.Unlock()

receive ints
do something

mutex2.Lock()
mutex3.Lock()
send int to routine 2
send int to routine 3
Print Something
mutex2.Unlock()
mutex3.Unlock()

do something
receive ints
mutex1.Unlock()
wg.Done()
}

func Routine2() {
mutex2.Lock()

do something

mutex1.Lock()
mutex3.Lock()
send int to routine 1
send int to routine 3
Print Something
mutex1.Unlock()
mutex3.Unlock()

do something
receive ints

mutex1.Lock()
mutex3.Lock()
send int to routine 1
send int to routine 3
Print Something
mutex1.Unlock()
mutex3.Unlock()

do something
receive ints
mutex2.Unlock()
wg.Done()
}

func Routine3() {
// same structure as routine 1 & 2
}
func main() {
wg.Add(3)
go Routine1()
go Routine2()
Routine3()
wg.Wait()
}

This logical code gives deadlock situation every time. Actually, when
it runs, just execute print statement of routine 1 (statement between
* marks) manytimes (though my print statement is only one) and gives
deadlock error. Can anybody inform me what is wrong with the code
logic. Thanks.

NB. For more info, code can be found here, http://play.golang.org/p/pW6aXryUaK,
where only line number 290 is executing. The original code which
contains no error, can be found here play.golang.org/p/UL3rj8DJRk. I
just add lock and unlock to them. Thanks.

I want to add another point: in the code of play.golang.org/p/
UL3rj8DJRk, you can find outputs of various print statements like
this: process [number] sends [int] to process [number] at [time nano
seconds]. However, as the result of three concurrent routines,
sometimes the print statement is not executing properly (means not
printing whole, there is some thing inserted by another print like
process [number] sends [int] to process [number] at process [number]).
Can any body help me how to manage this ?

[Arup Ghosh]

[Maxim Pimenov]

Here is a simple scenario:

1) Routine1 locks Lock1

2) Routine2 locks Lock2

3) Routine3 locks whatever

Now

Routine1 needs Lock2 which is held by Routine2 to proceed

Routine2 needs Lock1 which is held by Routine1 to proceed

These two are in a deadlock, and the third is unlikely to help this situation if 

it is "// same structure as routine 1 & 2", that is if it first tries to Lock() all three locks and only

then to Unlock() them.

Also, please next time provide us with an example that is less than 871 lines long.

[⚛]

On Dec 2, 12:07 pm, Arpssss <arupghoshb...@gmail.com> wrote:
> NB. For more info, code can be found here,http://play.golang.org/p/pW6aXryUaK,

> where only line number 290 is executing. The original code which
> contains no error, can be found here play.golang.org/p/UL3rj8DJRk. I
> just add lock and unlock to them. Thanks.

I do not understand the purpose of why you are using locks like this.
What are those locks supposed to be protecting?

[Arpssss]

Sorry Maxim, actually my original question is
http://stackoverflow.com/questions/8373329/issue-with-mutual-execution-of-concurrent-go-routines.

[Arpssss]

For understanding it, I want to refer on my original post
http://stackoverflow.com/questions/8373329/issue-with-mutual-execution-of-concurrent-go-routines.
Thanks for reply.

[Kyle Lemons]

As was suggested on SO, rewrite this without locking.  Exclusion locks (including when you're using a channel as a lock) are very hard to reason about, and there are some very complicated rules that you have to follow if you're trying to avoid deadlock, even with very "simple" actors.  If you find yourself using more than one mutex, you probably need to rethink something.  For one such example, see the Dining Philosophers Problem.  Part of what I enjoy most about writing Go code is that I can model my problem by using channels and goroutines and, in almost every case, completely avoid locks.

Reread the SO comments, especially jnml, to better understand how to refactor this with goroutines.  Basically, define the "ownership" of your data, and pass that ownership around with the data itself.  You can also make separate goroutines outside of the three above which retain "ownership" and instead service requests to read and modify the data.

[Kyle Lemons]

You are quite correct but for even if simple example I can not find
the proper solution how to implement this. For example,
http://play.golang.org/p/jJDY8LFkKu this code.  Here I want to put two
prints and sending event inside mutex (for routine 1) thus routine 2
can't interrupt it. Possible solution found is,
http://play.golang.org/p/-uoQSqBJKS. However, it gives deadlock error.
Can you help me how to solve http://play.golang.org/p/-uoQSqBJKS code
problem.

I honestly can't tell what this is supposed to be doing.  As I said, don't use mutexes (unless you *really* know what you're doing) in Go.  It looks like you're somehow trying to ensure that only one of the goroutines is running at a time (to make them alternate back and forth), but this is not really what you should be doing at all.  Define your actors such that they don't *care* what the other actors are doing or when, and communicate back and forth when necessary.  This will make your programs much more scalable, robust, and easy-to-write (not to mention -debug).

[Dmitry Vyukov]

If goroutines lock several mutexes at a time, then they need to lock
them in a consistent order. For example, never lock mutex2 before
mutex1, and never lock mutex3 before mutex2 and mutex1. The rule will
force you to either extend critical sections to the whole goroutines
or use a single mutex.