6.4.3 Signal-Theft Limit Counter Design

Figure: Signal-Theft State Machine
\resizebox{2in}{!}{\includegraphics{count/sig-theft}}

Figure [*] shows the state diagram. The state machine starts out in the IDLE state, and when add_count() or sub_count() find that the combination of the local thread's count and the global count cannot accommodate the request, the corresponding slowpath sets each thread's theft state to REQ (unless that thread has no count, in which case it transitions directly to READY). Only the slowpath, which holds the gblcnt_mutex lock, is permitted to transition from the IDLE state, as indicated by the green color. The slowpath then sends a signal to each thread, and the corresponding signal handler checks the corresponding thread's theft and counting variables. If the theft state is not REQ, then the signal handler is not permitted to change the state, and therefore simply returns. Otherwise, if the counting variable is set, indicating that the current thread's fastpath is in progress, the signal handler sets the theft state to ACK, otherwise to READY.

If the theft state is ACK, only the fastpath is permitted to change the theft state, as indicated by the blue color. When the fastpath completes, it sets the theft state to READY.

Once the slowpath sees a thread's theft state is READY, the slowpath is permitted to steal that thread's count. The slowpath then sets that thread's theft state to IDLE.

Quick Quiz 6.38: In Figure [*], why is the REQ theft state colored blue? End Quick Quiz

Quick Quiz 6.39: In Figure [*], what is the point of having separate REQ and ACK theft states? Why not simplify the state machine by collapsing them into a single state? Then whichever of the signal handler or the fastpath gets there first could set the state to READY. End Quick Quiz

Paul E. McKenney 2011-12-16