From owner-freebsd-hackers Sat Feb 1 13:02:23 1997 Return-Path: Received: (from root@localhost) by freefall.freebsd.org (8.8.5/8.8.5) id NAA09408 for hackers-outgoing; Sat, 1 Feb 1997 13:02:23 -0800 (PST) Received: from pdx1.world.net (pdx1.world.net [192.243.32.18]) by freefall.freebsd.org (8.8.5/8.8.5) with ESMTP id NAA09396 for ; Sat, 1 Feb 1997 13:01:58 -0800 (PST) Received: from suburbia.net (suburbia.net [203.4.184.1]) by pdx1.world.net (8.7.5/8.7.3) with SMTP id NAA04920 for ; Sat, 1 Feb 1997 13:02:43 -0800 (PST) Received: (qmail 10804 invoked by uid 110); 1 Feb 1997 21:00:31 -0000 MBOX-Line: From owner-netdev@roxanne.nuclecu.unam.mx Sat Feb 01 20:27:14 1997 remote from suburbia.net Delivered-To: proff@suburbia.net Received: (qmail 9045 invoked from network); 1 Feb 1997 20:26:51 -0000 Received: from roxanne.nuclecu.unam.mx (132.248.29.2) by suburbia.net with SMTP; 1 Feb 1997 20:26:51 -0000 Received: (from root@localhost) by roxanne.nuclecu.unam.mx (8.6.12/8.6.11) id OAA22043 for netdev-outgoing; Sat, 1 Feb 1997 14:00:30 -0600 Received: from prosun.first.gmd.de (prosun.first.gmd.de [194.95.168.2]) by roxanne.nuclecu.unam.mx (8.6.12/8.6.11) with SMTP id FAA19920 for ; Sat, 1 Feb 1997 05:20:16 -0600 Received: by prosun.first.gmd.de (4.1/SMI-4.1) id AA01923; Sat, 1 Feb 97 12:17:41 +0100 From: leo@prosun.first.gmd.de (Matthias L. Jugel) Message-Id: <9702011117.AA01923@prosun.first.gmd.de> Subject: lockfree datastructures To: netdev@roxanne.nuclecu.unam.mx Date: Sat, 1 Feb 1997 12:17:40 +0100 (MET) X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk Hi folks, a friend of mine forwarded me your interest in lock free data structures. Maybe the following papers will help you: * General Aspects - "Axioms for Concurrent Objects", CMU-CS-86-154 - "Reasoning About Concurrent Objects", CMU-CS-87-176 - "Linearizeability: A Correctness Condition for Concurrent Objects", CMU-CS-88-120 Maurice P. Herlihy, Jeanette M. Wing Dept. of Computer Science, Carnegie-Mellong-Univ. * Methods - "A Methodology for Implementing Highly Concurrent Data Objects", ACM Transactions on Programing Languages and Systems, Vol 15, No 5, Nov 1993 Pages 746-770 - "A Method for Implementing Lock-Free Shared Data Structures", Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, Ottawa, Ont. Canada, pp184-193 G. Barnes, 1995 also: MPI-I-94-120, Apr 1994, Max-Planck-Institut fuer Informatik - "Practical Considerations for nonblocking concurrent objects" Proceedings 13th IEEE International Conference on Distri- buted Systems, IEEE Computer Society Press, pp 264-273 B.N. Bershad, 1993 * Operating Systems - "The Synergy Between Non-Blocking Synchronisation and Operating System Structure", CA 94305-9040 Michael Greenwald, David Cheriton CS Dept, Stanford University - ... There is another paper I have to fetch ... Ok, I hope the papers give you a clue about the problem. From experience and discussion with our own OS builders I get the impression that for most problems a CAS or CAS2 (Compare-And-Swap) is sufficient compared to the proposed methods explained in the papers above. I'd be very interested in any problems and solutions you have in mind, because I am working on the subject in my PhD studies. If someone could give me a more detailled description of the problems you want to solve using non-blocking techniques. Best wishes, Leo. -- Matthias L. Jugel, leo@first.gmd.de GMD - German National Research Centre for Information Technology FIRST - Research Institute for Computer Architecture and Software Technology