From: John Kelly on 27 Jun 2010 23:27 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 28 Jun 2010 08:59 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 28 Jun 2010 09:46 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 28 Jun 2010 10:05 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 28 Jun 2010 10:25 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
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 4 Prev: pthreads and signal handler Next: ANN: Seed7 Release 2010-06-20 |