I found some introductory material on the reader writer problem and
semaphores at:

http://greenteapress.com/semaphores/

and I want to code a reader writer solution in C, using POSIX semaphores
on Linux (for multiple processes, not threads).

In his book, Downey mentions weak and strong semaphores.  Anyone know if
POSIX semaphores are weak or strong on Linux?


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

On Sun, 20 Jun 2010 20:17:17 +0000, John Kelly <jak@isp2dial.com> wrote:

> Anyone know if POSIX semaphores are weak or strong on Linux?

I found some Apache docs

http://httpd.apache.org/docs/2.0/misc/perf-tuning.html

that say Apache implements a serialization mutex with flock(), 
sysvsem, or posixsem -- but if using POSIX semaphores:

> The semaphore ownership is not recovered if a thread in the process
> holding the mutex segfaults, resulting in a hang of the web server.

Ugh.

So I guess semaphores are better for multi threads in a single process,
than they are for multi process apps.  If a process is killed or dies in
a critical section, a semaphore can remain in a locked state.

I hear SYSV semaphores have a rollback capability in case of abnormal
termination, but I also hear they have some undesirable qualities too,
such as performance and system limitations.

So if Apache prefers flock(), I wondered why not use it in place of
POSIX semaphores.  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.

If a process dies or is killed, the kernel cleans up its file locks, and
I don't have to worry about them.

It seems the only other question is performance, semaphores vs. flock().

A quick test of lock/unlock with flock() ran 770,000 loops per second; a
loop of post/wait with semaphores ran 2,700,000 loops per second, so the
semaphore was about 4 times faster.  But considering that semaphores can
leave a multi process app hung, I think flock() performance will be fine
for my purposes.

I also compared the two on a faster server box which runs a different
linux kernel version; flock ran about the same speed, but the semaphore
loop ran an order of magnitude faster.  Strange.

Nevertheless, I think I'll use flock(), and let the kernel worry about
lock cleanup.


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

John Kelly <jak@isp2dial.com> wrote:
<snip>
> It seems the only other question is performance, semaphores vs. flock().

flock() will be slower because it's a pure kernel interface, whereas the
fast-path for semaphore and mutex implementations can be done all in
userspace.

Now, perhaps if someone reimplemented Linux's flock() with a vsyscall....

<snip>
> Nevertheless, I think I'll use flock(), and let the kernel worry about
> lock cleanup.

If it becomes a problem you can always optimize later. You can compose
something like a read/write semaphore using process-shared POSIX mutex or
barrier interfaces. However, even here you're not necessarily guaranteed
100% reliability; though some implementations are capable of releasing a
process' locks, it often depends on the process' memory not having a corrupt
heap.

On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern
<william@wilbur.25thandClement.com> wrote:

>flock() will be slower because it's a pure kernel interface, whereas the
>fast-path for semaphore and mutex implementations can be done all in
>userspace.
>
>Now, perhaps if someone reimplemented Linux's flock() with a vsyscall....

I thought a vsyscall was just a faster interface to a syscall.  Is that
what you mean?


>> Nevertheless, I think I'll use flock(), and let the kernel worry about
>> lock cleanup.

>If it becomes a problem you can always optimize later.

Should not be a problem in my app.  I have Apache processes reading a
MySQL database, but they don't remember what they learned, they ask the
same question again and again.

Instead, I want them to look for the answer in a BerkeleyDB first.  If
the answer is not there, they will ask a special server, via sockets, to
find the answer in the MySQL database.  The special server then writes
the MySQL answer to the BerkeleyDB, and notifies the Apache process to
look again.

So as answers accumulate in the BerkeleyDB "directory," the number of
MySQL lookups will approach zero.  The BerkeleyDB will provide a quicker
"process local" lookup without context switch.

The reader locks will still occur on each http request, but the flock()
calls will be insignificant in relation to my overall server load.  I
just wanted to have a rough idea of the relative performance of flock()
vs. semaphores, to avoid potential performance pitfalls.


>You can compose something like a read/write semaphore using process-shared
>POSIX mutex or barrier interfaces. However, even here you're not necessarily
>guaranteed 100% reliability

Trying to make semaphores 100% reliable for a multi process app may not
be impossible, but it looks like more work than I want to do.



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

John Kelly <jak@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 piling up on the exclusive gate
lock can prevent a writer getting to the point where it waits for its
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.

<snip>
-- 
Ben.

On Mon, 28 Jun 2010 03:20:41 +0100, Ben Bacarisse <ben.usenet@bsb.me.uk>
wrote:

>John Kelly <jak@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
 

John Kelly <jak@isp2dial.com> writes:

> On Mon, 28 Jun 2010 03:20:41 +0100, Ben Bacarisse <ben.usenet@bsb.me.uk>
> wrote:
>
>>John Kelly <jak@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.

John Kelly <jak@isp2dial.com> writes:
> On Mon, 28 Jun 2010 03:20:41 +0100, Ben Bacarisse <ben.usenet@bsb.me.uk>
> wrote:
>
>>John Kelly <jak@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.

On Mon, 28 Jun 2010 13:59:42 +0100, Ben Bacarisse <ben.usenet@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
 

On Mon, 28 Jun 2010 15:46:14 +0200, Rainer Weikusat
<rweikusat@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
 

John Kelly <jak@isp2dial.com> writes:

> On Mon, 28 Jun 2010 13:59:42 +0100, Ben Bacarisse <ben.usenet@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.

John Kelly <jak@isp2dial.com> writes:
> On Mon, 28 Jun 2010 13:59:42 +0100, Ben Bacarisse <ben.usenet@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.

Randomness guarantees nothing. That's why it is called
RANDOMness. You are (likely) confusing this with pseudo-randomness,
which is based on mathematical functions which generate sequences of
output numbers with particular statistical properties. Eg, it is
'guaranteed' that a long enough sequence of output values produced by
a 'good' PRNG will contain all possible single values an equal number
of times. But this is not guaranteed for any actually random sequence
of any finite length. 

[...]

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

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. 

[...]

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

Your 'argument' is based on hand-waiving and the assertion that "shit
won't happen".

On Mon, 28 Jun 2010 17:12:25 +0100, Ben Bacarisse <ben.usenet@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
 

On Mon, 28 Jun 2010 18:36:16 +0200, Rainer Weikusat
<rweikusat@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
 

John Kelly <jak@isp2dial.com> writes:
> On Mon, 28 Jun 2010 18:36:16 +0200, Rainer Weikusat
> <rweikusat@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.

On Mon, 28 Jun 2010 19:49:23 +0200, Rainer Weikusat
<rweikusat@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
 

On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern
<william@wilbur.25thandClement.com> wrote:

>flock() will be slower because it's a pure kernel interface, whereas the
>fast-path for semaphore and mutex implementations can be done all in
>userspace.

Updating a semaphore must be an atomic operation.  How can two unrelated
user tasks compete for the same semaphore, without help from the kernel?


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

John Kelly <jak@isp2dial.com> wrote:
> On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern
> <william@wilbur.25thandClement.com> wrote:

> >flock() will be slower because it's a pure kernel interface, whereas the
> >fast-path for semaphore and mutex implementations can be done all in
> >userspace.

> Updating a semaphore must be an atomic operation.  How can two unrelated
> user tasks compete for the same semaphore, without help from the kernel?

Using shared memory. They'd need help from the kernel, certainly,
specifically ensuring that the relevant page has the proper characteristics
for mutually visible atomic operations. For example, BSDs provide the
MAP_HASSEMAPHORE flag to mmap(2), and Linux specifies PROT_SEM for
mprotect(2).

John Kelly <jak@isp2dial.com> wrote:
> On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern
> <william@wilbur.25thandClement.com> wrote:

> >flock() will be slower because it's a pure kernel interface, whereas the
> >fast-path for semaphore and mutex implementations can be done all in
> >userspace.
> >
> >Now, perhaps if someone reimplemented Linux's flock() with a vsyscall....

> I thought a vsyscall was just a faster interface to a syscall.  Is that
> what you mean?

I believe vsyscalls operate on a kernel-shared data structure, but on second
thought it may just be shared read-only.

On Wed, 30 Jun 2010 11:28:57 -0700, William Ahern
<william@wilbur.25thandClement.com> wrote:

>John Kelly <jak@isp2dial.com> wrote:
>> On Mon, 21 Jun 2010 13:07:46 -0700, William Ahern
>> <william@wilbur.25thandClement.com> wrote:
>
>> >flock() will be slower because it's a pure kernel interface, whereas the
>> >fast-path for semaphore and mutex implementations can be done all in
>> >userspace.
>
>> Updating a semaphore must be an atomic operation.  How can two unrelated
>> user tasks compete for the same semaphore, without help from the kernel?
>
>Using shared memory. They'd need help from the kernel, certainly,
>specifically ensuring that the relevant page has the proper characteristics
>for mutually visible atomic operations. For example, BSDs provide the
>MAP_HASSEMAPHORE flag to mmap(2), and Linux specifies PROT_SEM for
>mprotect(2).


I found this:

* * *

http://en.wikipedia.org/wiki/Mutual_exclusion

In a computer in which several processors share memory, an indivisible
test-and-set of a flag could be used in a tight loop to wait until the
other processor clears the flag. The test-and-set performs both
operations without releasing the memory bus to another processor. When
the code leaves the critical section, it clears the flag. This is called
a "spinlock" or "busy-wait."

And this:

http://en.wikipedia.org/wiki/Test-and-set

A lock can be built using an atomic test-and-set instruction as follows:

function Lock(boolean *lock) {
    while (test_and_set (lock) == 1)
      ;
}

The calling process obtains the lock if the old value was 0. It spins
writing 1 to the variable until this occurs.

* * *

I never thought of using an assembly language spinlock from user space.
Seems like that would avoid kernel calls altogether, whether "fast-path"
or not.



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

On Wed, 30 Jun 2010 21:52:29 +0000, John Kelly <jak@isp2dial.com> wrote:

>I never thought of using an assembly language spinlock from user space.
>Seems like that would avoid kernel calls altogether, whether "fast-path"
>or not.

Hmm ...

What if process A grabs the lock, starts working his critical section,
and along comes process B who spins, waiting to get the lock.

And what if B has higher priority than A?  A starves, B spins, but can't
get the lock, because A can't complete his critical section while B hogs
the CPU.



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