Version 1 (modified by constantin.rosoiu, 14 years ago) (diff)
  • added architecture



In a work-stealing scheduling policy, each of the worker threads involved maintains a pool of ready tasks to be executed, and executes tasks by removing them from this pool. The process of creating tasks is dynamic, each tasks that gets created is being added to the pool of the creating worker. While trying to get a task from it's own pool the worker discovers the pool is empty, it will pick another worker (the victim) and it will remove a task from it's associated pool, essentially stealing a task (thus becoming a thief). This type of scheduling is very efficient because the idle worker threads (i.e. the threads that do no useful work) do the load balancing.



The allocator is based on the buddy allocation scheme. The heap is divided into buckets, each bucket containing chunks of the same size. The buckets are initially empty and chunks are added to the buckets whenever memory is released, in order to reuse it. When a caller asks for a memory block of size sz, the allocator will round the requested size to the nearest power of two greater than the size. This is done to minimize the number of buckets needed. It will then look in the corresponding bucket to see if there are recycled chunks of memory of the requested size available to be reused. If so, the allocator will remove a chunk from the corresponding bucket and it will return it to the client. If there are no more chunks available, the allocator will use the heap to retrieve a chunk from it.


The workqueue is based on the recent work of Chase and Lev Dynamic Circular WorkStealing Deque that was "ported" to a non-garbage-collected, non-memory-modeled, plain-old C.


The workqueue has a contiguous space to hold available tasks, so it has a bottom and a top. Three operations can be executed on it:

  • push() which adds a task into the workqueue at the top,
  • pop() which removes a task from the top of the workqueue and
  • steal() which removes a task from the bottom of the workqueue.

Not all operations are available to every thread. The push() and pop() methods can be called only by the owner thread, so only the owner has access to the top of the workqueue. The steal() operation can only be executed by other threads apart the owner thread, so only other threads work with the bottom of the workqueue.


There is a distinction between the logical and the physical indices: the logical indices are stored in the top and bottom variables and the physical ones are calculated by applying the modulus operator versus the arrays size. The size of the array itself is kept in the cyclic array object. Local push() and pop() operations are performed by changing the value of bottom, while stealing is done by incrementing top by one.