From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.129.179.202 with SMTP id r193mr6783102ywh.162.1486905587364; Sun, 12 Feb 2017 05:19:47 -0800 (PST) X-Received: by 10.157.62.29 with SMTP id a29mr1297434otd.5.1486905587324; Sun, 12 Feb 2017 05:19:47 -0800 (PST) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!news.glorb.com!i7no978915qta.1!news-out.google.com!15ni1125itm.0!nntp.google.com!e137no528122itc.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sun, 12 Feb 2017 05:19:47 -0800 (PST) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=2a01:e34:ec05:8e10:e477:c13a:1cf3:2e00; posting-account=21X1fwoAAABfSGdxRzzAXr3Ux_KE3tHr NNTP-Posting-Host: 2a01:e34:ec05:8e10:e477:c13a:1cf3:2e00 References: <52b3faef-34b7-485f-98fb-6f488692ae9b@googlegroups.com> <74921d6a-8e52-437e-8485-1f0a77bcc0cc@googlegroups.com> <7f2e7b06-d287-437c-835d-c4a9d53ea7e1@googlegroups.com> <077a224f-4836-4c05-89f1-3f6fbee61427@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <4ae9745e-6672-4c31-b1e0-3c1139108419@googlegroups.com> Subject: Re: Lock-Free stack in Ada SPARK From: Hadrien Grasland Injection-Date: Sun, 12 Feb 2017 13:19:47 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:33342 Date: 2017-02-12T05:19:47-08:00 List-Id: Le dimanche 12 f=C3=A9vrier 2017 13:49:54 UTC+1, Dmitry A. Kazakov a =C3=A9= crit=C2=A0: > On 2017-02-12 13:26, Hadrien Grasland wrote: > > Le samedi 11 f=C3=A9vrier 2017 20:36:31 UTC+1, Jeffrey R. Carter a =C3= =A9crit : > >> Perhaps someone will enlighten me. > >> > >> All of the lock-free structures that I've looked at involved busy wait= ing on a > >> memory location via an atomic test-and-set/compare-and-swap operation. > >> > >> To my mind, that's an implementation of a lock, and I don't understand= why these > >> are considered lock free. > > > > A lock-free object is an object that can be concurrently manipulated > > by multiple threads, in such a fashion that any thread can fall asleep > > permanently at any point in time without preventing other threads from > > doing useful work. >=20 > As a counterexample consider an atomic integer. Is it lock-free? Not=20 > according your definition, because there might be a thread waiting=20 > integer to become 123 while nobody writes that value there. In this case, the integer itself is lock-free (if a thread stops writing to= it, other threads will still be able to), but the algorithm of the waiting= thread isn't lock-free. This is why I tried to use terminology that puts the focus on objects (i.e.= combinations of data structures and algorithms) rather than data alone. > It is correct to say that synchronization is achieved per busy waiting=20 > on lock-free shared objects. After all there is no other choice, a task= =20 > that cannot continue must either be blocked or else retry. I wouldn't say that this is always the case. For example, consider the foll= owing (admittedly inefficient) algorithm for finding prime numbers in a cer= tain range [1, N]: - Let there be a shared counter C, starting at value 1, a master thread, an= d a pool of N worker threads. - Each worker thread runs on a loop doing the following: * Atomically increment C and check its value X. * Stop if X is greater than or equal to N. * Otherwise, check if X is prime. * If it is, add it to an internal list of primes and start over. - Once all threads are finished, the master thread collects and merges the = intermediate lists of primes of each thread to get the final global list of= primes. In this design, the master thread's algorithm is obviously not lock-free (i= t has to wait for the workers), but the worker thread's algorithms is. No s= pinning is involved when incrementing the atomic counter: the hardware take= s care of all required synchronization for you using some cache trickery. A= nd modern Intel hardware is remarkably scalable in the presence of concurre= nt atomic increments: https://1.bp.blogspot.com/-wVF9DuFkrzk/Tm4nQC-ZNEI/AAAAAAAAABE/MQ6jfEoMc3s/= s1600/atomics.png