What is this?

This is an implemenation of Lock-free Work-stealing Deque written in C.

There are a number of tasks
Tasks are the same number of task queues as CPUs
A `worker’ has a task queue
A worker pops/pushes tasks from its own task queue
A worker takes tasks from other workers
`Pop’/`push’ accesses the bottom of task queues
`Take ’ accesses the top of task queues

This is a part of my project in Google Summer of Code 2011.

Features

Task queue is implemented as `unbound circular array’, which doesn’t have start and end points and expands when the size is less than the number of tasks.
There are already some implementation of Lock-free Work-stealing Deque. But one written in C is not so common. Unlike some languages like Java, the support of `volatile’ variable is limited in C. This implementation covers it by using memory barriers.
This uses compare-and-swap (CAS) instruction instead of mutex lock.

Compile and Test

All files (except this README ;-) ) is required to build.
Compile the deque source and unit tests.
```
make
    
```
To test the deque, just type
```
make TEST_gsoc_taskqueue
    
```
You can see the number of CPUs used in test and calculation time by
```
./test_gsoc_taskqueue > /dev/null
    
```
If you also want to test circular array, type
```
make TEST_gsoc_task_circular_array
    
```
Note that it will fail if you use 32-bit CPUs.

Or if you want to test all of them,
```
make test
    
```
`make clean’ to clean the directory.

Welcoming Your Comments

I appreciate any of your advice and comments. Feel free to contact me on twitter @laysakura .

Reference

The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit / Morgan Kaufmann
Dynamic Circular Work-Stealing Deque. David Chase, David Chase