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>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20000724131311.W13979>