Local Serializer

Context

Consider an interactive program. To maximize concurrency and responsiveness, operations requested by the user can be implemented as tasks. The order of operations can be important. For example, suppose the program presents editable text to the user. There might be operations to select text and delete selected text. Reversing the order of "select" and "delete" operations on the same buffer would be bad. However, commuting operations on different buffers might be okay. Hence the goal is to establish serial ordering of tasks associated with a given object, but not constrain ordering of tasks between different objects.

Forces

Solution

Sequence the work items using a FIFO (first-in first-out structure). Always keep an item in flight if possible. If no item is in flight when a work item appears, put the item in flight. Otherwise, push the item onto the FIFO. When the current item in flight completes, pop another item from the FIFO and put it in flight.

The logic can be implemented without mutexes, by using concurrent_queue for the FIFO and atomic<int> to count the number of items waiting and in flight. The example explains the accounting in detail.

Example

The following example builds on the Non-Preemptive Priorities example to implement local serialization in addition to priorities. It implements three priority levels and local serializers. The user interface for it follows:

enum Priority {
   P_High,
   P_Medium,
   P_Low
};
 
template<typename Func>
void EnqueueWork( Priority p, Func f, Serializer* s=NULL );

Template function EnqueueWork causes functor f to run when the three constraints in the following table are met.

Implementation of Constraints

Constraint

Resolved by class...

Any prior work for the Serializer has completed.

Serializer

A thread is available.

RunWorkItem

No higher priority work is ready to run.

ReadyPileType

Constraints on a given functor are resolved from top to bottom in the table. The first constraint does not exist when s is NULL. The implementation of EnqueueWork packages the functor in a SerializedWorkItem and routes it to the class that enforces the first relevant constraint between pieces of work.

template<typename Func>
void EnqueueWork( Priority p, Func f, Serializer* s=NULL ) {
   WorkItem* item = new SerializedWorkItem<Func>( p, f, s );
   if( s )
       s->add(item);
   else
       ReadyPile.add(item);
}

A SerializedWorkItem is d