From: John Kelly on
On Mon, 28 Jun 2010 03:20:41 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk>
wrote:

>John Kelly <jak(a)isp2dial.com> writes:
>
>> [...] It seems that flock() provides an easy solution to
>> the reader writer problem:
>>
>> READER WRITER
>>
>> EX lock gate EX lock gate
>> SH lock data EX lock data
>> unlock gate unlock gate
>> read data write data
>> unlock data unlock data
>>
>>
>> EX == flock() EXCLUSIVE
>> SH == flock() SHARED
>>
>> "gate" and "data" are lockfiles, say in /tmp
>>
>> This prevents writer starvation; while a writer waits for its EX data
>> lock, the gate is still locked, and no other readers or writers can get
>> thru the gate until the writer gets its EX lock and unlocks the gate.
>
>From a cursory reading of what flock guarantees, I don't think that
>writer starvation is prevented.

Readers are not long running tasks. They get what they want, and get
out.

Now say 10 readers and no writers are running. The gate is not locked,
because readers don't keep it locked -- they get their shared lock and
immediately unlock the gate. Along comes a writer. He locks the gate,
and asks for the data lock. But while he's waiting for the data lock,
the gate remains locked, because he needs an EXCLUSIVE lock, and must
wait for it -- but he's already INSIDE the gate, and everyone one else
must wait OUTSIDE.

--> So once a writer asks for his data lock, no one else can jump ahead
of him, because they can't get thru the gate (until he's done) <--

As soon as the running readers finish, the writer gets his EXCLUSIVE
data lock. Then he unlocks the gate, beginning a new cycle.


>Readers piling up on the exclusive gate lock can prevent a writer
>getting to the point where it waits for its data lock.

Readers don't queue on the gate unless a writer is already waiting for a
data lock.


>I don't see any guarantee that a process that has been waiting a long
>time will be granted a lock ahead of processes that have waited for less
>time but I did not read the kernel documentation -- only the man page.

If a group waiting at the gate includes 2 writers and 8 readers, the
next one thru the gate may be random, and thus "unfair." But as long as
it's at least random, eventually one writer will get thru the gate. And
once he's thru the gate, no one else, reader or writer, can jump ahead
of him.

It doesn't matter if the kernel is fair to new arrivals -- as long as
the kernel does not discriminate against writers (how could the kernel
know which is which?), randomness guarantees that another writer will at
some point, get thru the gate.

Thus writers are not starved.


--
Web mail, POP3, and SMTP
http://www.beewyz.com/freeaccounts.php

From: Ben Bacarisse on
John Kelly <jak(a)isp2dial.com> writes:

> On Mon, 28 Jun 2010 03:20:41 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk>
> wrote:
>
>>John Kelly <jak(a)isp2dial.com> writes:
>>
>>> [...] It seems that flock() provides an easy solution to
>>> the reader writer problem:
>>>
>>> READER WRITER
>>>
>>> EX lock gate EX lock gate
>>> SH lock data EX lock data
>>> unlock gate unlock gate
>>> read data write data
>>> unlock data unlock data
>>>
>>>
>>> EX == flock() EXCLUSIVE
>>> SH == flock() SHARED
>>>
>>> "gate" and "data" are lockfiles, say in /tmp
>>>
>>> This prevents writer starvation; while a writer waits for its EX data
>>> lock, the gate is still locked, and no other readers or writers can get
>>> thru the gate until the writer gets its EX lock and unlocks the gate.
>>
>>From a cursory reading of what flock guarantees, I don't think that
>>writer starvation is prevented.
>
> Readers are not long running tasks. They get what they want, and get
> out.
>
> Now say 10 readers and no writers are running. The gate is not locked,
> because readers don't keep it locked -- they get their shared lock and
> immediately unlock the gate. Along comes a writer. He locks the
> gate,

It may not be able to. If the writer requests the exclusive gate lock
while a reader holds it, the writer will (correctly) block. If a second
reader requests it before the first releases it, I don't think the writer
is guaranteed to get it -- the second reader might. This scenario can
be repeated indefinitely as far as I can see. In fact, you address this
key point below so it's probably better if we concentrate on that part.

> and asks for the data lock. But while he's waiting for the data lock,
> the gate remains locked, because he needs an EXCLUSIVE lock, and must
> wait for it -- but he's already INSIDE the gate, and everyone one else
> must wait OUTSIDE.

Yes, the behaviour once a writer requests the data lock is not in
question.

> --> So once a writer asks for his data lock, no one else can jump ahead
> of him, because they can't get thru the gate (until he's done) <--

The key is whether the writer will always get as far as asking for its
data lock.

> As soon as the running readers finish, the writer gets his EXCLUSIVE
> data lock. Then he unlocks the gate, beginning a new cycle.
>
>
>>Readers piling up on the exclusive gate lock can prevent a writer
>>getting to the point where it waits for its data lock.
>
> Readers don't queue on the gate unless a writer is already waiting for a
> data lock.
>
>
>>I don't see any guarantee that a process that has been waiting a long
>>time will be granted a lock ahead of processes that have waited for less
>>time but I did not read the kernel documentation -- only the man page.
>
> If a group waiting at the gate includes 2 writers and 8 readers, the
> next one thru the gate may be random, and thus "unfair." But as long as
> it's at least random, eventually one writer will get thru the gate. And
> once he's thru the gate, no one else, reader or writer, can jump ahead
> of him.

Now I agree with this but that was not my understanding of your
argument. I thought you were arguing for the more usual deterministic
freedom from starvation. That's usually how the problem is posed.

It is usually better to have an algorithm that is deterministically
rather than stochastically starvation free. One reason for this is that
actual implementations find it hard to be genuinely random. If you are
only guaranteed that the probability of a writer waiting an infinite
time is zero when the choice is truly random, then you probably don't
have that guarantee in practise. Flock probably isn't required to be
genuinely random -- it would be a burden on implementations.

Conversely, implementations do find it easy to be deterministic so, for
example, if the documentation guarantees that locks are granted in the
order in which they are requested you are home and dry. I did not see
such a guarantee, hence my comments.

> It doesn't matter if the kernel is fair to new arrivals -- as long as
> the kernel does not discriminate against writers (how could the kernel
> know which is which?), randomness guarantees that another writer will at
> some point, get thru the gate.
>
> Thus writers are not starved.

--
Ben.
From: Rainer Weikusat on
John Kelly <jak(a)isp2dial.com> writes:
> On Mon, 28 Jun 2010 03:20:41 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk>
> wrote:
>
>>John Kelly <jak(a)isp2dial.com> writes:
>>
>>> [...] It seems that flock() provides an easy solution to
>>> the reader writer problem:
>>>
>>> READER WRITER
>>>
>>> EX lock gate EX lock gate
>>> SH lock data EX lock data
>>> unlock gate unlock gate
>>> read data write data

[...]

>>I don't see any guarantee that a process that has been waiting a long
>>time will be granted a lock ahead of processes that have waited for less
>>time but I did not read the kernel documentation -- only the man page.
>
> If a group waiting at the gate includes 2 writers and 8 readers, the
> next one thru the gate may be random, and thus "unfair." But as long as
> it's at least random, eventually one writer will get thru the gate. And
> once he's thru the gate, no one else, reader or writer, can jump ahead
> of him.
>
> It doesn't matter if the kernel is fair to new arrivals -- as long as
> the kernel does not discriminate against writers (how could the kernel
> know which is which?), randomness guarantees that another writer will at
> some point, get thru the gate.
>
> Thus writers are not starved.

It should be noted that this is an attempt to weasel-word around the
fact that the scheme outlined above provides no guarantees wrt writer
starvation [because the person who invented is convinced that such
problems 'will never happen']. In particular, 'randomness' does not
provide anything here because, as Donald Knuth once put it, an
infinite sequences of ones is a perfectly random result of rolling an
actual dice.
From: John Kelly on
On Mon, 28 Jun 2010 13:59:42 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk>
wrote:


>> Now say 10 readers and no writers are running. The gate is not locked,
>> because readers don't keep it locked -- they get their shared lock and
>> immediately unlock the gate. Along comes a writer. He locks the
>> gate,
>
>It may not be able to. If the writer requests the exclusive gate lock
>while a reader holds it, the writer will (correctly) block. If a second
>reader requests it before the first releases it, I don't think the writer
>is guaranteed to get it -- the second reader might. This scenario can
>be repeated indefinitely as far as I can see.

True, a writer is not guaranteed to get it on the next iteration. But
that's irrelevant. Randomness guarantees bounded time. Next iteration
is less important than bounded time.


>> If a group waiting at the gate includes 2 writers and 8 readers, the
>> next one thru the gate may be random, and thus "unfair." But as long as
>> it's at least random, eventually one writer will get thru the gate. And
>> once he's thru the gate, no one else, reader or writer, can jump ahead
>> of him.
>

>Now I agree with this but that was not my understanding of your
>argument. I thought you were arguing for the more usual deterministic
>freedom from starvation. That's usually how the problem is posed.

>It is usually better to have an algorithm that is deterministically
>rather than stochastically starvation free.

Why? If the kernel grants locks in FIFO order, my solution could be
called deterministic. If OTOH, the kernel grants locks in random order,
then my solution could be called stochastic.

But either way, it works. What's the difference?


>If you are
>only guaranteed that the probability of a writer waiting an infinite
>time is zero when the choice is truly random, then you probably don't
>have that guarantee in practise. Flock probably isn't required to be
>genuinely random -- it would be a burden on implementations.

If not random, or FIFO, then what else can it be? How can the kernel
possibly discriminate against writers?


>Conversely, implementations do find it easy to be deterministic so, for
>example, if the documentation guarantees that locks are granted in the
>order in which they are requested you are home and dry. I did not see
>such a guarantee, hence my comments.

This is an interesting topic, and I appreciate your examination of my
argument for errors. But so far, I still don't see any.



--
Web mail, POP3, and SMTP
http://www.beewyz.com/freeaccounts.php

From: John Kelly on
On Mon, 28 Jun 2010 15:46:14 +0200, Rainer Weikusat
<rweikusat(a)mssgmbh.com> wrote:

>> Thus writers are not starved.

>It should be noted that this is an attempt to weasel-word around the
>fact that the scheme outlined above provides no guarantees wrt writer
>starvation [because the person who invented is convinced that such
>problems 'will never happen']. In particular, 'randomness' does not
>provide anything here because, as Donald Knuth once put it, an
>infinite sequences of ones is a perfectly random result of rolling an
>actual dice.

The only snake eyes I fear are the human kind.


--
Web mail, POP3, and SMTP
http://www.beewyz.com/freeaccounts.php