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

[Carl Ritson]

Hi Zach,

> 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?

The offset points to the tail in the bitmap (and migration window),
the offset is stored in each batch to indicate it is in the migration
window.  The offset stored in a batch is cleared when a batch is
removed from the migration window, so it acts a check against race
conditions (the offset can then be used to update the bitmap
appropriately).  The order of all these operations is critical to
avoiding race conditions.

The bitmap itself is for performance, the algorithms can be written
without it, but it would require testing all the migration window
array elements, rather than using a bit search instruction on the
window state word.

Does that help at all?

Cheers,

Carl