Project 2 FAQ§

Why does pthread_create fail if I run fjdriver.py?§

To ensure that your pool does not create more threads than requested, the test driver limits the number of threads. The only way to do that is to temporarily reduce the summary limit of threads your user account may have active on the machine you're testing. This method may conflict with other threads or processes you may have running on the same machine, such as internal threads vscode runs (or when you type other commands while the test is running). For this reason, you should run fjdriver.py on a different machine as VScode and you shouldn't engage in running any other commands on the machine where fjdriver.py was started while the tests are running. See the Howto for accessing rlogin for information how to log into a different machine. See Zabbix for current load numbers.

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.

What exactly is the difference between stealing and helping?§

First of, the terms "stealing" and "helping" differ a bit from their usual meaning in English, and on top, "helping" is used in two different contexts. Let’s break it down.

"Stealing" is what idle workers do when looking for work. They first look in the global queue and see if there's a task for them to do. If not, they look in their fellow workers' queues. If they find one, they "steal" it and start working on it. (In real life, if someone takes a task from you that you were supposed to do we probably wouldn’t call it "stealing" - we might call it "helping"? "Stealing" perhaps became the term here to express the fact that we do this without necessarily requiring any consent of the "victim" of the "theft" (the thread whose tasks are "stolen").

As for the term "helping" - there are 2 situations. First, a thread may need the result of a task it had previously put up for stealing (by adding it to its queue). But nobody has stolen it, and now the result is needed. In this case, the worker must take on the task themselves. We call this "helping" - which again is kind of weird, isn't it - the worker is helping themselves here with one of their own tasks, just because nobody was around to "steal it"... Perhaps calling it "helping" is meaningful because it "helps" the greater good of finishing all tasks. This aspect of "helping" is a required feature of your implementation; without it, you'd deadlock as described in Section 2.2 in the handout.

Second, there is a another situation: suppose a worker needs the result of a task it has previously added to its list, but now the task did, in fact, get stolen by another worker, but that other worker is still working on the task. Then what should the first worker do now? It could wait, letting the other worker (the "thief") finish the task, or it could see if it, in turn, could steal tasks from that "thief" worker. By stealing those tasks, it would be helping this worker since presumably these tasks are dependent tasks that must be finished before the thief can complete the actual task our worker is after. This is the second meaning of "helping," and it involves "stealing" - though in this case, we want to steal only from the queue of the "thief" who has stolen our task. This aspect of "helping" is a performance optimization (the pool would work even if you waited instead), and as such I recommend that you implement it last once everything else works.