[CCC DEV] Question on atomic run queue operations in the CCSP wait-free scheduler.

[Zachary Williams]

*TL;DR*: I have questions about the wait-free aspects of
Carl's CCSP scheduler, specifically on the window
state word.


Hi All,

I am working on porting (perhaps not the best word as
I am implementing from scratch) Carl's CCSP
work-stealing, wait-free scheduler to the tvm. I currently
have a library that performs work stealing with batches
however it uses pthread mutex to lock run queues, and
so it is not wait-free. Being that the next logical step is
to add wait-free-ieness, I have a few questions on how
this is done in CCSP.

When performing enqueueing and dequeueing on a
logical processor, how is the window represented in
the window state word?

I guess my confusion is in how the offset section ties in,
I am assuming it is used to determine if a batch being
enqueued belongs in the window, but is just the offset
representing where in the bit map the head (or tail) of the
run queue is? And how does the offset section of the
window state word correspond with the stored offset of
each batch?

Thanks for your time and help.


I am trying to understand the run queue
algorithms in Carl's paper:
http://www.cs.kent.ac.uk/pubs/2009/2928/index.html

If you need/want to check it out, my code
is available at:
https://projects.cs.kent.ac.uk/projects/kroc/trac/browser/kroc/branches/par-tvm/runtime/libtvmsched



Thanks in advance,
Zach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.concurrency.cc/pipermail/developers/attachments/20120217/f44b541a/attachment.htm>