Project 2 FAQ§

Can I implement the fork-join pool with a single lock and condition variable?§

Yes, but not for full credit. In general, when developing multithreaded code, the approach is to start with a coarse-grained approach and to refine it as necessary for performance. You could do the same for your implementation.

A fork-join pool with a single lock that protects all queues and futures works. Note that such a pool will even provide parallelism (and parallel speedup), particularly for coarse-grained tasks such as the independent tasks in our sort benchmarks (quicksort and mergesort). The reason is that the serialization due to the single lock takes places only during operations related to the thread pool. Threads executing tasks will spend most of their time outside the thread pool code, not holding the single lock (this assumes, of course, that your implementation properly drops the lock upon leaving your code and reacquires upon reentering your code).

We also include some benchmarks where the tasks submitted aren't coarse-grained. These benchmarks serve to measure the overhead of your thread pool as the task size gets smaller.

Nevertheless, especially if you're uncertain about your approach, a first draft implementation that uses a single lock may be a good idea. This would allow you, for instance, to test the logic of your worker and global queue, as well as the logic for helping, with much less risk of failure due to data races or atomicity violations.

How do I tell if a submission via thread_pool_submit is internal or external?§

Internal submissions are made by worker threads during the execution of other tasks. External submissions are made by threads outside the thread pool that do not currently process tasks. Use a thread-local variable, which will have different values depending on which thread is accessing it. For external threads, which will not set this variable, it will have a value of 0 (NULL if it's a pointer). For worker threads, set the variable to a suitable value that will help you process the submitted task.

In C11, use _Thread_local If you implement a work sharing approach, this distinction is moot.

Where are other examples of FJ programs I could port?§

Check out the benchmarks that are part of the JSR-166 project which maintains Java 8's FJP.

Will there ever be tasks on the local queue when a worker thread is idle?§

No, or at least not for our fully-strict benchmarks. Tasks may be on the local queue when a worker is busy working on a task (namely, the subtasks that this worker spawned off while working on this task and which haven't been stolen by other workers), but once a worker finishes the task it's working on, those subtasks will be gone from the queue - either because they've been stolen, or because the worker finished them as part of helping.

This is guaranteed because in our benchmarks, any task that's spawned during the execution of a task will be joined (by calling future_get) before the task returns. For instance, a sorting task that consists of partitioning an array into halves and sorting those, then merging them, will not return until both halves are sorted.

This means you don't have to implement this case, either. You can assert that when a worker wakes up that there are no tasks on its queue.