Prev: pthreads and signal handler
Next: ANN: Seed7 Release 2010-06-20
From: Ben Bacarisse on 28 Jun 2010 12:12
John Kelly <jak(a)isp2dial.com> writes:

> 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.

"True" randomness guarantees that the probability of an infinite wait is
zero, but "bounded time" usually means that there is some finite bound.
Provided we both understand the meaning of your claim that "randomness
guarantees bounded time" I am happy. For many people, the possibility
of an unbounded wait (even when lim P(wait > x) -> 0 as x -> oo) is not
enough. If it meets your needs, then the only issue whether flock can
possibly be truly random.

>>> 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.

Yes, then there is no issue at all. Do you know if this is the case
either on you platform or in general?

> 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?

The unbounded wait (with lim P(wait > x) -> 0 as x -> oo) is not always
acceptable. The problems caused by a pseudo-random granting of locks
can be worse, in part because is almost impossible to analyse such an
implementation.

>>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?

What if it is LIFO? Yes, a decidedly unlikely choice, but if the
programmer is expected to be able to reply on the order in which locks
are granted, I think the specification should say so. Since it doesn't,
I'd rather assume the worst rather than the best!

>>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.

I was pointing out a problem with the algorithm, not your argument.

Your subsequent arguments about it make assumptions that obviously suit
your situation but which I'd be wary of. If you are happy to assume
that the order in which locks are granted won't be pathological, and you
are content with the unbounded waits that a random (or, worse, a
pseudo-random) choice can produce then there is no problem with your
argument.

--
Ben.
From: John Kelly on 28 Jun 2010 12:40
On Mon, 28 Jun 2010 17:12:25 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk>
wrote:

>> Why? If the kernel grants locks in FIFO order, my solution could be
>> called deterministic.
>
>Yes, then there is no issue at all. Do you know if this is the case
>either on you platform or in general?

Unknown.


>> 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?
>
>The unbounded wait (with lim P(wait > x) -> 0 as x -> oo) is not always
>acceptable.

Agreed.


>> If not random, or FIFO, then what else can it be? How can the kernel
>> possibly discriminate against writers?
>
>What if it is LIFO? Yes, a decidedly unlikely choice, but if the
>programmer is expected to be able to reply on the order in which locks
>are granted, I think the specification should say so. Since it doesn't,
>I'd rather assume the worst rather than the best!

>I was pointing out a problem with the algorithm, not your argument.

>Your subsequent arguments about it make assumptions that obviously suit
>your situation but which I'd be wary of. If you are happy to assume
>that the order in which locks are granted won't be pathological, and you
>are content with the unbounded waits that a random (or, worse, a
>pseudo-random) choice can produce then there is no problem with your
>argument.

You are right, it's not a universal solution.

But it suits my reader/writer application, and for suitable problems,
it's simple and easy to implement.


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

From: John Kelly on 28 Jun 2010 12:52
On Mon, 28 Jun 2010 18:36:16 +0200, Rainer Weikusat
<rweikusat(a)mssgmbh.com> wrote:

>> But either way, it works.

>It doesn't. If lock requests were granted randomly, any
>individual request could remain unserved for any arbitrarily long time
>interval. That's not very probable, but another property of random
>sequences is that occurence of any possible sequence is equally
>improbable.

Like Downey says in his book:

"In part, starvation is the responsibility of the scheduler. Whenever
multiple threads are ready to run, the scheduler decides which one or,
on a parallel processor, which set of threads gets to run. If a thread
is never scheduled, then it will starve, no matter what we do with
semaphores."

Your head's so far in the clouds, I would not ask you to solve any down
to earth practical problems.


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

From: Rainer Weikusat on 28 Jun 2010 13:49
John Kelly <jak(a)isp2dial.com> writes:
> On Mon, 28 Jun 2010 18:36:16 +0200, Rainer Weikusat
> <rweikusat(a)mssgmbh.com> wrote:
>
>>> But either way, it works.
>
>>It doesn't. If lock requests were granted randomly, any
>>individual request could remain unserved for any arbitrarily long time
>>interval. That's not very probable, but another property of random
>>sequences is that occurence of any possible sequence is equally
>>improbable.
>
> Like Downey says in his book:
>
> "In part, starvation is the responsibility of the scheduler. Whenever
> multiple threads are ready to run, the scheduler decides which one or,
> on a parallel processor, which set of threads gets to run. If a thread
> is never scheduled, then it will starve, no matter what we do with
> semaphores."
>
> Your head's so far in the clouds, I would not ask you to solve any down
> to earth practical problems.

And you are so much guaranteed to react with (pretty pointless)
insults whenever someone tries to help you to understand something
that you're close to being a textbook example of 'an idiot': Someone
who is soo goddamn cocksure to already know and understand everything
that he never learns how to do anything except chasing the colourful
figment of his own imagination.

Consequently, the absolutely last thing one should let you do is
'solve down-to-earth practical problems' since you're guaranteed to
screw up and screw up and screw up yet again, all because of Your
Infallibility.

Pointless flame in response to a pointless flame, I'll admit that.
From: John Kelly on 28 Jun 2010 14:14
On Mon, 28 Jun 2010 19:49:23 +0200, Rainer Weikusat
<rweikusat(a)mssgmbh.com> wrote:

>> Your head's so far in the clouds, I would not ask you to solve any down
>> to earth practical problems.

>And you are so much guaranteed to react with (pretty pointless)
>insults whenever someone tries to help you to understand something

I listened carefully to Ben. The difference is, he wanted to help.


>Pointless flame in response to a pointless flame, I'll admit that.

You OTOH, like to show how smart you are and put other people down. If
there's one thing I can't abide, it's arrogant pseudo intellectuals.


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

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: pthreads and signal handler
Next: ANN: Seed7 Release 2010-06-20