I just noticed that the #define BUSY is buggy. This should make it clearer:
#define ONES (~((unsigned int)0) ) /* all 1-bits */ #define BUSY (~(ONES >> 1) ) /* the high bit */ > From [email protected] Tue Mar 26 13:31:30 2013 > To: [email protected] > Subject: [ast-developers] Forgot to add ast_developers (FIFO with > compare&Switch) > > 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 _______________________________________________ ast-developers mailing list [email protected] http://lists.research.att.com/mailman/listinfo/ast-developers
