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.13.237.196 with SMTP id w187mr5224271ywe.27.1486845761289; Sat, 11 Feb 2017 12:42:41 -0800 (PST) X-Received: by 10.157.62.29 with SMTP id a29mr1223169otd.5.1486845761250; Sat, 11 Feb 2017 12:42:41 -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!1.eu.feeder.erje.net!feeder.erje.net!2.us.feeder.erje.net!feeder.usenetexpress.com!feeder1.iad1.usenetexpress.com!216.166.98.84.MISMATCH!border1.nntp.dca1.giganews.com!nntp.giganews.com!i7no867051qta.1!news-out.google.com!78ni845itm.0!nntp.google.com!e137no349574itc.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sat, 11 Feb 2017 12:42:40 -0800 (PST) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=24.84.156.122; posting-account=1A2ZjwoAAACv32zkEz8vnPUIVPXwW28q NNTP-Posting-Host: 24.84.156.122 References: <52b3faef-34b7-485f-98fb-6f488692ae9b@googlegroups.com> <74921d6a-8e52-437e-8485-1f0a77bcc0cc@googlegroups.com> <7f2e7b06-d287-437c-835d-c4a9d53ea7e1@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Lock-Free stack in Ada SPARK From: stevenselectronicmail@gmail.com Injection-Date: Sat, 11 Feb 2017 20:42:41 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:33331 Date: 2017-02-11T12:42:40-08:00 List-Id: On Saturday, February 11, 2017 at 11:36:31 AM UTC-8, Jeffrey R. Carter wrot= e: > 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. >=20 > --=20 > Jeff Carter > "Crucifixion's a doddle." > Monty Python's Life of Brian > 82 Jeffrey what you want are wait-free datastructures. In lock-free data struc= tures at any single point in time the system as a whole can progress forwar= d but some particular threads may end up waiting forever. In wait-free data= structures every individual thread can progress forward in a finite amount= of time. Note that there are also wait-free bounded and wait-free populati= on oblivious algorithms which complete for any individual thread in a bound= ed amount of time (proportional to the amount of threads) and just bounded = amount of time respectively. See also http://concurrencyfreaks.blogspot.ca/= 2013/05/lock-free-and-wait-free-definition-and.html