class SchedulerQueueState

SchedulerQueueState tracks the association with a scheduler and run queue. To

accommodate the different ways a thread can be accessed (i.e. starting from a

thread vs. starting from a run queue), specific locking rules apply to this

member of Thread (i.e. Thread::scheduler_queue_state_).

There are two locks that apply to interactions with the queue state:

1. Thread::lock_ (or the thread's lock): Protects most of a thread's data

members, including the scheduling state (i.e. Thread::scheduling_state_).

Thread::scheduling_state_::curr_cpu_ indicates which CPU and scheduler

the thread is currently associated with.

2. Scheduler::queue_lock_ (or the queue lock): Protects a scheduler's data

members, including the run queue and associated bookkeeping. This lock

also protects the thread's scheduler queue state member while the thread

is associated with a particular scheduler.

When both a thread's lock and a scheduler's queue lock must be held at

the same time, commonly needed during rescheduling and PI operations,

the defined lock order is to acquire the thread's lock before the queue

lock. Fortunately, most operations start from a thread and proceed to

interact with a scheduler (e.g. blocking, unblocking, PI operations),

naturally conforming to the required lock order. However, several

operations start from a scheduler (e.g. finding the next thread to run,

stealing a thread from another CPU), and require some lock juggling to

complete their operations.

Operations that start from a scheduler typically dequeue a thread from a

run queue while holding the queue lock protecting that run queue.

Locking the thread to complete the operation involves releasing the

currently held queue lock, acquiring the thread's lock, and then

acquiring either the same queue lock or a different queue lock.

For example, selecting the next thread to run during a reschedule

involves the following lock juggling sequence:

1. With the local queue lock held, dequeue the next thread to run.

2. Release the queue lock.

3. Acquire the next thread's lock.

4. Re-acquire the local queue lock and continue the reschedule.

Stealing a thread from another CPU involves a similar lock juggling

sequence:

1. With the source queue lock held, dequeue the thread to steal and

(mostly) disassociate it with the source scheduler.

2. Release the source queue lock.

3. Acquire the stolen thread's lock.

4. Acquire the local queue lock, associate the thread with the local

scheduler, and continue the reschedule.

In both cases, since the thread is no longer in a queue after step 1,

it cannot be selected or stolen by another CPU after the queue lock is

released. However, because the thread is not yet locked between steps 2 and

3, an operation starting at the thread and holding the thread's lock could

interleave with the locking sequence. If such an interleaved operation

involves updating the thread's run queue position and/or the associated

scheduler's bookkeeping, care must be taken to avoid double-dequeuing the

thread, updating the wrong scheduler's bookkeeping, or rescheduling the

wrong CPU.

SchedulerQueueState::Disposition is an enumeration of the valid combinations

of a thread's scheduler queue states that may be used in conjunction with the

thread state (i.e. Thread::state()) to determine how the thread and the

associated scheduler can be updated.

The following state combinations may be observed by operations that start at

a thread and hold both the thread's lock and the queue lock:

1. state=RUNNING, disposition=Associated:

Observable when a thread is running. Because the currently running

thread's lock is held over a reschedule, there are no observable

transitional states to deal with in PI and affinity change operations.

Holding the thread lock delays rescheduling and transitioning from RUNNING

to any other state. The thread's scheduling state and scheduler

bookkeeping may be updated by a PI operation or affinity change. The CPU

performing the update is obligated to reschedule the CPU the thread is

running on when the update is complete.

2. state=READY, disposition=Enqueued:

Observable when a thread is waiting in the run queue and is not in the

process of rescheduling.

Holding the queue lock delays the thread from transitioning to RUNNING,

being stolen, or migrated by another CPU. The thread's scheduling state,

scheduler bookkeeping, and scheduler queue state may be updated by a PI

operation or affinity change. The CPU performing the update is obligated

to reschedule the CPU the thread is associated with if the change might

affect the currently running thread.

3. state=READY, disposition=Associated:

Observable when a thread is rescheduling and transitioning from READY to

RUNNING and the lock juggling of the rescheduling CPU races with an

update.

During the reschedule, when the next thread has been dequeued it is

expected to be the next thread to run on the CPU. To complete the

transition, the scheduler releases the queue lock (allowing this

observation from another CPU), acquires the thread lock, and re-acquires

the queue lock.

Holding the thread lock on another CPU delays the completion of the

transition, allowing the effective profile, dynamic parameters, and

scheduler bookkeeping or affinity to be updated.

Note: An update of the thread's effective profile and dynamic parameters

can invalidate the thread as the correct/best choice to run. The CPU

performing the update is obligated to reschedule the CPU the thread is

running on, either unconditionally (current behavior) or conditionally if

another thread should run instead (future optimization).

Likewise, a change to the thread's affinity mask may invalidate the CPU

the thread is about to run on as a viable option. The CPU performing the

update is obligated to reschedule the CPU to cause it to migrate the

thread to viable target.

4. state=READY, disposition=Stolen:

Observable when a thread is being stolen and the lock juggling of

the stealing CPU races with an update from another CPU.

When the thread is being stolen, it is dequeued and removed from the

previous scheduler's bookkeeping. To complete the steal, the source

queue lock is released (allowing this observation from another CPU),

the thread lock is acquired, and the destination queue lock is

acquired. Since the stolen thread will become the currently running

thread on the stealing CPU, rescheduling is unnecessary and can be

omitted in a future optimization.

Holding the thread lock on another CPU delays the steal, allowing the

effective profile and dynamic parameters or affinity mask to be updated.

In this state, the thread is not associated with any scheduler

bookkeeping, but the current CPU of thread is stale. However, holding the

queue lock of the stale CPU allows the CPU performing the update to make a

coherent observation of the stolen_by member, which can be used to

determine if an affinity mask change has invalidated the stealing CPU as a

viable option. The updating CPU is obligated to reschedule the stealing

CPU if it became an invalid option due to the update.

5. state=INITIAL,BLOCKED*,SLEEPING,SUSPENDED,DEATH,

disposition=Unassociated

Observable only by the CPU performing a reschedule that transitions the

current thread from RUNNING to one of the non-runnable states. Since a

reschedule of the current thread occurs with the thread lock held, and

transitioning to a non-runnable state clears the current CPU for the

thread, no other CPU can observe this state while holding the thread's

lock and a queue lock.