From owner-freebsd-smp  Mon Jul 24 13:13:17 2000
Delivered-To: freebsd-smp@freebsd.org
Received: from fw.wintelcom.net (ns1.wintelcom.net [209.1.153.20])
	by hub.freebsd.org (Postfix) with ESMTP id B096737B630
	for <smp@freebsd.org>; Mon, 24 Jul 2000 13:13:12 -0700 (PDT)
	(envelope-from bright@fw.wintelcom.net)
Received: (from bright@localhost)
	by fw.wintelcom.net (8.10.0/8.10.0) id e6OKDCN10331
	for smp@freebsd.org; Mon, 24 Jul 2000 13:13:12 -0700 (PDT)
Date: Mon, 24 Jul 2000 13:13:12 -0700
From: Alfred Perlstein <bright@wintelcom.net>
To: smp@freebsd.org
Subject: atomic queues.
Message-ID: <20000724131311.W13979@fw.wintelcom.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2.4i
Sender: owner-freebsd-smp@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.org

I've been digging through a lot of books looking for an implementation
of atomic queues that I could have sworn I've seen.  So far I haven't
had any luck except for re-implementing them:

enqueue:

do {
  cmpval = list_head;
  mynode->next = cmpval;
} while (compare_and_exchange(&listhead, cmpval, mynode) != cmpval);

The idea is that we read the list head pointer, then we assign our
node to be enqueued's next pointer to the head of the list.

If a compare and exchanges detects that the head node hasn't changed
since we read the list_head and list_head->next then we're safe.
  
dequeue (allocate):

do {
  mynode = list_head;
  newhead = list_head->next;
} while (compare_and_exchange(&listhead, mynode, newhead) != mynode);

We swap the list head with list_head->next but only succeed if list_head
hasn't changed since we read list_head->next.

Does anyone have any references online or pointer to some text that
discuss this?

-- 
-Alfred Perlstein - [bright@wintelcom.net|alfred@freebsd.org]
"I have the heart of a child; I keep it in a jar on my desk."


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-smp" in the body of the message