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.92.197 with SMTP id q188mr6746587ywb.148.1486902372310;
        Sun, 12 Feb 2017 04:26:12 -0800 (PST)
X-Received: by 10.157.44.136 with SMTP id p8mr1293336otb.20.1486902372269;
 Sun, 12 Feb 2017 04:26:12 -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!q58no971251qte.0!news-out.google.com!78ni1500itm.0!nntp.google.com!e137no515368itc.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Sun, 12 Feb 2017 04:26:11 -0800 (PST)
In-Reply-To: <o7np0i$iu$1@dont-email.me>
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: <c7c7fd16-9302-4ea0-99c0-c6c48c775348@googlegroups.com>
 <52b3faef-34b7-485f-98fb-6f488692ae9b@googlegroups.com>
 <74921d6a-8e52-437e-8485-1f0a77bcc0cc@googlegroups.com>
 <b07ab100-f6c1-4459-9e21-d75dccf9e9b6@googlegroups.com>
 <a2d4b333-4e89-4375-b5cf-68d848a70722@googlegroups.com>
 <7f2e7b06-d287-437c-835d-c4a9d53ea7e1@googlegroups.com>
 <o7np0i$iu$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <077a224f-4836-4c05-89f1-3f6fbee61427@googlegroups.com>
Subject: Re: Lock-Free stack in Ada SPARK
From: Hadrien Grasland <hadrien.grasland@gmail.com>
Injection-Date: Sun, 12 Feb 2017 12:26:12 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Xref: news.eternal-september.org comp.lang.ada:33339
Date: 2017-02-12T04:26:11-08:00
List-Id: <comp.lang.ada>

Le samedi 11 f=C3=A9vrier 2017 20:36:31 UTC+1, Jeffrey R. Carter a =C3=A9cr=
it=C2=A0:
> Perhaps someone will enlighten me.
>=20
> All of the lock-free structures that I've looked at involved busy waiting=
 on a=20
> memory location via an atomic test-and-set/compare-and-swap operation.
>=20
> To my mind, that's an implementation of a lock, and I don't understand wh=
y these=20
> are considered lock free.

A lock-free object is an object that can be concurrently manipulated by mul=
tiple threads, in such a fashion that any thread can fall asleep permanentl=
y at any point in time without preventing other threads from doing useful w=
ork.

A spinlock is not a lock-free object because if the thread holding the lock=
 falls asleep, any other thread that needs to manipulate the spinlock is un=
able to make progress.

If you want an example of a lock-free object, consider Linux's Read-Copy-Up=
date (RCU) mechanism, which is used to implement concurrent data structures=
 that are read frequently but mutated rarely:

- The RCU data structure is accessed indirectly through a pointer.
- To access the data, a thread performs an atomic read on the pointer, then=
 uses that pointer to read the data in a non-atomic fashion.
- To mutate the data, a thread does the following:
    * Access the data structure as above
    * Make a copy of it, and adjust the copy as needed
    * Try to replace the pointer to the old structure with the pointer to t=
he new structure using an atomic compare-and-swap operation
    * If that fails, someone replaced the data structure under our feet: lo=
ad the new data structure and try to perform our modifications again.

This algorithm is lock-free because threads that read data don't step on ea=
ch other, and any thread which attempts to mutate the data can fall asleep =
at any point in time before the final compare-and-swap without preventing o=
ther threads from making progress.