Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!zorba!dtynan
From: martin@mwtech.UUCP (Martin Weitzel)
Newsgroups: comp.unix
Subject: Re: UNIX pipe bug
Keywords: pipe,UNIX
Message-ID: <3667@zorba.Tynan.COM>
Date: 4 Jul 90 01:10:11 GMT
References: <3589@zorba.Tynan.COM> <3640@zorba.Tynan.COM>
Sender: dtynan@zorba.Tynan.COM
Reply-To: uunet!relay.EU.net!mwtech!martin (Martin Weitzel)
Organization: MIKROS Systemware, Darmstadt/W-Germany
Lines: 74
Approved: dtynan@zorba.Tynan.COM

In article <3640@zorba.Tynan.COM> idall@augean.ua.OZ.AU (Ian Dall) writes:
>In article <3589@zorba.Tynan.COM> machala@vlsic2.csc.ti.com (Chuck Machala) writes:
>>
>> I have run into a problem with UNIX pipes deadlocking. Seems there's
>> a bug in pipe. MAN says "Should more than 4096 bytes be neccessary
>> in any pipe among a loop of processes, deadlock will occur." That's 
>> what we have, a loop of processes which deadlock; however, it dead-
>> locks with NO bytes in the pipe.

If you define "deadlock" as the situation where several processes
wait for some event that can only be generated by someone who is
allready waiting, many of such situations may arise if processes
are connected thru pipelines.

Especially with named pipes, the order of opening two pipes for two
way communication is crucial, because the first open may have to wait
for the partner (also know as "rendevouz principle"). Hence two
processes that want a two-way path using two named pipes must do
the open just in the opposite order (one must open the read side
first, the other the write side - of course, with regard to the
*name* of the pipes, they must use the same order.)

An other famous example is a pipe create in the conventional manner
by the pipe system call or a named pipe opend for read and write.
(BTW: Such an open would not have to wait, which seems natural
beacause a read end and a write end are immediatly available, but
IMHO this feature is undocumented.) If the process now tries to
read until end of file but "forgets" to close its own write side
it will never see end of file, because there's still a potential
writer - the reading process!

If more than two process communicate thru pipes, there should be a
*very* thorough design to prevent the chance for casual deadlocks.
Bascially, there are two techniques: The first is acquiring and
releasing all resources in exactly the same order. If this is done
by all concurrently running processes, it's not so hard to prove
that there can occur no deadlocks. The second approach is to use
timeouts. (Hint: You can add timeouts in a very clean way thru
daemon process, which now and then write something to the pipes.
Of course, the reading processes must be able to sort out the dummy
messages.)

Now lets come to this:
>I have seen this.
>
>mknod PIPE1 p
>cat ~/.login | tee PIPE1 | wc | cat - PIPE1
>

The reason for the deadlock is relatively easy to detect here.
Start this program in the background (add an & at the end) and
then try ">PIPE1" and "<PIPE1". The first will do nothing,
but act as a possible "writer" for a short moment, the second
will do similar but as "reader". You will note that the first
will also hang, but the second will unlock the whole thing.
So it's obvious that the deadlock in the above example was caused
by a writer that had non potentioal reader.

A little thought will confirm this. Before "tee" will write any
bytes to its output, it must open PIPE1 - and wait for a reader.
On the other side, "cat" waits for EOF from its standard input.
Because there is a possible writer, "wc", "cat" can not proceed
and open PIPE1 for reading. Hence there's a deadlock.

The smallest failing case where this condition occurs is

	tee PIPE1 | cat - PIPE1

so if you want to play a little bit and look how you can this
bring to run, use the above one. (Playing a litte bit with named
pipes at shell level before using them in programs may pay later,
when you design your programs.)
-- 
Martin Weitzel, email: martin@mwtech.UUCP, voice: 49-(0)6151-6 56 83