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 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Lock-Free stack in Ada SPARK Date: Sun, 12 Feb 2017 15:57:40 +0100 Organization: Aioe.org NNTP Server Message-ID: 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> <4ae9745e-6672-4c31-b1e0-3c1139108419@googlegroups.com> NNTP-Posting-Host: BYuA7L7MRjuLLjcoGHOBxw.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: news.eternal-september.org comp.lang.ada:33343 Date: 2017-02-12T15:57:40+01:00 List-Id: On 2017-02-12 14:19, Hadrien Grasland wrote: > Le dimanche 12 février 2017 13:49:54 UTC+1, Dmitry A. Kazakov a écrit : >> On 2017-02-12 13:26, Hadrien Grasland wrote: >>> Le samedi 11 février 2017 20:36:31 UTC+1, Jeffrey R. Carter a écrit : >>>> Perhaps someone will enlighten me. >>>> >>>> All of the lock-free structures that I've looked at involved busy waiting 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. >> >> As a counterexample consider an atomic integer. Is it lock-free? Not >> according your definition, because there might be a thread waiting >> 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. Being lock-free must be a property of an object. > 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. Integer is such an object with operations read and write. It can be lock-free, e.g. with pragma Atomic in effect or not when encapsulated in a protected object or handled by a monitor task. All this has nothing to do with any algorithm that may deploy this integer. >> It is correct to say that synchronization is achieved per busy waiting >> on lock-free shared objects. After all there is no other choice, a task >> that cannot continue must either be blocked or else retry. > > I wouldn't say that this is always the case. For example, consider > the following (admittedly inefficient) algorithm for finding prime numbers > in a certain range [1, N]: > > - Let there be a shared counter C, starting at value 1, a master thread, and 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 (it has to wait for the workers), but the worker thread's > algorithms is. They are not if atomic increment is not, e.g. handled by a monitor task. Nor are they lock-free at the point they must hand their lists over to the main task. The point stands, if synchronization is needed, you either wait or retry. Being lock-free does not mean no synchronization, without synchronization there is no concurrent decomposition. Lock-free means a certain method of synchronization. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de