Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #2259
| From | Stephen Fuld <SFuld@alumni.cmu.edu.invalid> |
|---|---|
| Newsgroups | comp.programming.threads, comp.programming, comp.arch |
| Subject | Re: About lockfree and waitfree... (2nd try) |
| Date | 2014-04-25 13:39 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <ljeh5f$m3l$1@dont-email.me> (permalink) |
| References | <lif821$inj$1@news.albasani.net> <lj97cc$hfk$1@dont-email.me> <lj994h$n3c$1@needham.csi.cam.ac.uk> <87y4yu654p.fsf@GraySage.COM> <ljbg2r$9na$1@needham.csi.cam.ac.uk> |
Cross-posted to 3 groups.
On 4/24/2014 10:02 AM, Nick Maclaren wrote: > In article <87y4yu654p.fsf@GraySage.COM>, Chris Gray <cg@GraySage.COM> wrote: >> >>> Yes :-) Simply getting distinct sequences of keys with each thread's >>> sequence sequential is easy, but not very useful. Your description >>> is correct, but incomplete, because there is also the requirement >>> for sequential consistency. And some (many?) algorithms that want >>> numbers of that form want them consistent with memory accesses. >> >> I promised myself I wouldn't post on this group, since I'm not qualified, but >> I've been thinking about this one. I too am a software guy. > > Don't worry - few of us are - indeed, I am about as unqualified in > IT (in a formal sense) as anyone, being of an era when we learnt > by being dropped in the deep end :-) > >> What exactly does "sequential consistency" mean? Does it mean that successive >> reads of the TAN facility return a strict counting sequence of values? If so, >> then I certainly can't see any kind of realistic solution. > > No. It means that separate threads see sequences of numbers that > could have been produced from a single server returning monotonically > increasing values. > > http://en.wikipedia.org/wiki/Sequential_consistency I have been thinking more about this. Based on the ideas given in the above reference I believe that my proposal does this as well as is theoretically possible. Consider a concrete example, Let's assume there are 64 cores, each with its own copy of the counter register and that they are synchronized to sub 1 ns. and that they count at the rate of 1 ns. So 1 ns is the "quantum" or granularity of the information. Thus any process reading one of the registers receives a value in ns plus 6 extra low order bits (from the id), that, to all intents are to it, random. I think we agree that if two processes on different cores read values and they are separated by say several nanoseconds, there is no problem. We know which came first. A question arises if two processes read their respective registers within the same ns, and get the same high order value, but different low order bits due to the id. The results are unique, but since they are below the granularity of the counter, we don't know which came first, that is, process 1 could have been at a nanosecond plus .25ns and process two at a nanosecond plus .75. It is possible that the id numbers will be such that process two's value will actually be lower than process one's value, and this would violate sequentiality. But I maintain that, short of an infinitely precise clock, obviously impossible, two processes could read the read the clock within the same granularity and get the same number. But below the granularity it is impossible to know which came first, so the choice is arbitrary. Thus the choice imposed by the id is as good as any other, and has the advantage of enforcing uniqueness. What am I missing? I should also note that I don't doubt that there are algorithms that need something more, I maintain that there are useful scenarios for which my proposal is entirely adequate. These include, for example, transaction numbers in a database system. The requirement is for uniqueness and they occur say several hundred thousand times per second. The exact sequential order, down to sub nanoseconds is not really needed. -- - Stephen Fuld (e-mail address disguised to prevent spam)
Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 19:54 -0700
Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:38 -0700
Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:47 -0700
Re: About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 22:56 -0700
Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 14:08 -0700
Re: About lockfree and waitfree... "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 14:23 -0700
Re: About lockfree and waitfree... Ivan Godard <ivan@ootbcomp.com> - 2014-04-14 16:27 -0700
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-14 16:29 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-15 10:04 -0700
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-15 10:34 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-17 16:35 -0700
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 17:04 -0700
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-18 09:54 +0100
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-18 02:31 -0700
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-18 11:56 +0100
Re: About lockfree and waitfree... (2nd try) rpw3@rpw3.org (Rob Warnock) - 2014-04-18 11:26 +0000
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-18 13:30 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:25 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:31 -0700
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-21 14:53 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 14:21 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 14:36 -0700
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-22 15:30 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-05-01 00:48 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-05-25 13:16 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-21 14:34 -0700
Re: About lockfree and waitfree... (2nd try) Robert Wessel <robertwessel2@yahoo.com> - 2014-04-21 16:42 -0500
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-21 15:02 -0700
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-22 09:05 +0100
Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-22 09:27 -0700
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-22 09:45 -0700
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-22 18:08 +0100
Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-23 12:08 -0700
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-23 20:32 +0100
Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-23 13:21 -0700
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-23 21:51 +0100
Re: About lockfree and waitfree... (2nd try) Chris Gray <cg@GraySage.COM> - 2014-04-24 10:53 -0600
Re: About lockfree and waitfree... (2nd try) nmm@needham.csi.cam.ac.uk (Nick Maclaren) - 2014-04-24 18:02 +0100
Re: About lockfree and waitfree... (2nd try) Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2014-04-25 13:39 -0700
Re: About lockfree and waitfree... (2nd try) "Chris M. Thomasson" <no@spam.invalid> - 2014-04-22 22:08 -0700
Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-17 21:15 -0400
Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-17 21:25 -0400
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 19:17 -0700
Re: About lockfree and waitfree... (2nd try) George Neuner <gneuner2@comcast.net> - 2014-04-18 00:46 -0400
Re: About lockfree and waitfree... (2nd try) Ivan Godard <ivan@ootbcomp.com> - 2014-04-17 18:52 -0700
Re: About lockfree and waitfree... aminer <aminer@toto.net> - 2014-04-13 22:54 -0700
csiph-web