> From kpv Tue Mar 26 11:50:24 2013
> To: [email protected]
> Subject: Re: [ast-developers] Using compare and swap for pointers to
> implement fifo queue?
> It's hard to implement an unbounded queue with cas using any sort of linked
> list.
> This is because because you will likely need a doubly linked list to get
> constant
> time insert/delete but the cas op can update only one pointer at a time.
> However, if you know in advance that the max size of the queue at any given
> time
> cannot exceed M, then, off the top of my head, you can use an array of size M
> and
> do something like the below (WARNING: code made up on the fly and untested).
> A quick note is that, on a time sharing system, the below while(1) loops can
> cause
> the kernel to increase priority for a thread/process unnecessarily. This would
> skew the overall performance of all concurrent threads/processes. The current
> ASO library (hopefully available soon in a new AST distribution) provides a
> few
> simple primitives to cause a thread to yield as necessary to balance
> workloads.
> Good luck,
> Phong
-----------CUT HERE----------------------------
#define BUSY (~(~((unsigned int)0 >> 1)) ) /* this is the high bit of an int
*/
#define M The_max_queue_size_goes_here
Obj_t *Queue[M]; /* this is the queue. Obj_t is the object type
*/
unsigned int Head = 0; /* the queue is empty whenever Head == Tail
*/
unsigned int Tail = 0;
void insert(Obj_t* obj)
{
unsigned int head, newhead;
while(1)
{ if((head = Head) & BUSY ) /* some inserter is busy inserting */
continue;
/* try to reserve current Head location to insert "obj" */
if((newhead = head+1) == M)
newhead = 0;
newhead |= BUSY;
/* this asocasint can fail if another concurrent insertion gets
the space first */
if(asocasint(&Head, head, newhead) != head)
continue;
/* succeed in reserving the space, now insert the object */
Queue[head] = obj;
/* remove the BUSY bit to tell that insertion is done */
asocasint(&Head, Head, Head&~BUSY);
return;
}
}
Obj_t* delete()
{
unsigned int head, tail, newtail;
Obj_t *obj;
while(1)
{ head = Head;
if((tail = Tail) == (head & ~BUSY) ) /* queue is empty */
return (Obj_t*)0;
if((newtail = tail+1) == M)
newtail = 0;
/* some insertion at current "tail" is being done, so wait */
if(newtail == (head&~BUSY) && (head&BUSY) )
continue;
obj = Queue[tail]; /* extract object at current tail position */
/* this asocasint() can fails if some other concurrent deletion
happens first */
if(asocasint(&Tail, tail, newtail) == tail)
return obj;
}
}
----------CUT HERE---------------------------------------------------
> > From [email protected] Tue Mar 26 05:39:01 2013
> > To: ast-users <[email protected]>,
> > [email protected], Glenn Fowler
> > <[email protected]>
> > Subject: Re: [ast-developers] Using compare and swap for pointers to
> > implement fifo queue?
> > On Wed, Mar 20, 2013 at 4:50 PM, Simon Toedt <[email protected]> wrote:
> > > Apologies for my lack of knowledge, but how can a fifo queue be
> > > implemented with just a compare and swap for pointers?
> > Does anyone know a method to implement this with just a single compare
> > and swap operation for pointers? I'm not sure whether this is even
> > theoretically possible.
> > Simon
> > _______________________________________________
> > ast-developers mailing list
> > [email protected]
> > http://lists.research.att.com/mailman/listinfo/ast-developers
_______________________________________________
ast-developers mailing list
[email protected]
http://lists.research.att.com/mailman/listinfo/ast-developers
