changelog:

Your Task

  1. Implement a thread pool, which runs tasks across a fixed number of threads. Each of these threads should take tasks from a queue and run them, waiting for new tasks whenever the queue is empty. Your thread pool will start tasks in the order they are submitted and also support waiting for a particular task submitted to thread pool to complete. Each task in the thread pool will be identified by a name.

    Your implementation must start threads once when the thread pool is created and only deallocate them when the Stop() method is called. You may not start new threads each time a task is submitted.

    Your thread pool should follow the interface defined in the header file pool.h in our skeleton code [Last updated 2019-02-15]. This interface has two classes, one called Task representing tasks to run an done called ThreadPool representing the thread pool itself. You may additional add methods and member variables to these classes for your implementation.

    The Task class must have the following methods:

    • Task(), virtual ~Task() — constructor and virtual destructor

    • virtual void Run() = 0 — pure virtual (i.e. abstract) method overriden by subclasses. This will be run by threads in the thread pool when a task is run.

    The ThreadPool class must have the following methods:

    • ThreadPool(int num_threads) — constructor, which takes the number of threads to create to run queued tasks.

    • void SubmitTask(const std::string &name, Task *task) — function to submit (enqueue) a task. The task can be identified by name in future calls to WaitForTask(). After the task completes, the ThreadPool must be deallocate it as with delete task.

      You may assume that for a particular ThreadPool object, SubmitTask will be called only with the name of a task that has not already been submitted and for which WaitForTask has not already been called.

      This method should return immediately after adding the task to a queue, allocating additional space for the queue if necessary. It should never wait for running tasks to finish and free up space to store additional pending tasks.

    • void WaitForTask(const std::string &name) — wait for a particular task, not returning until the task completes. Note that this method may be called any time after the task is submitted, including after it has already finished running.

      You may assume that WaitForTask is called exactly once per submitted task.

    • void Stop() — stop the thread pool, terminating all its threads normally. After this returns, all resources for the threads in the thread pool should be deallocated.

    Every method of the ThreadPool class except for the Stop() method may be called from any thread, including from one of the tasks in submitted to the thread pool. The Stop() method may be called from any thread except one that was created by the thread pool.

    Your implementation must support multiple ThreadPool objects being used at the same time, so you should not use global variables.

    In no case may any of the methods above consume a lot of compute time while waiting for some condition (e.g. a task finishing) to become true. A thread that needs to wait should arrange to be put into a sleeping/waiting state until the condition is likely true.

  2. Your submission should include a Makefile which produces a statically linked library libpool.a, like our skeleton code does.

  3. You can use the supplied pool-test program to help test your thread pool implementation. Note that this is may not be a complete test. In particular, it is likely that this test case will not expose various race conditions that might exist in your code.

  4. Produce a .tar.gz file of your submission like the one make submit will produce and submit to the submission site.

Hints

General advice

  1. The producer/consumer pattern we discussed in lecture is very useful for this assignment.

  2. You can use the C++ standard library’s deque or list as a queue, using push_back() to insert elements onto the queue; and back() and pop_back() to remove elements from the queue.

    Alternately, you could write your own queue with a linked list, or dynamic array.

  3. You will need to use some synchronization mechanism to manage the queue of waiting tasks and manage reporting when tasks finish. Probably this will either be mutexes and condition variables (what I used in my implementation) or semaphores.

Example of Usage

  1. To use the ThreadPool class you create, a user would create a subclass of Task that implements the Run() method that performs an operation they want to add to the queue of operations to do:

    class ComputeSumTask : public Task {
public:
    ComputeSumTask(int *sum_destination, int *array_to_sum, int array_size) {
        this->sum_destination = sum_destination;
        this->array_to_sum = array_to_sum;
        this->array_size = array_size;
    }

    void Run() {
        int sum = 0;
        for (int i = 0; i < this->array_size; ++i) {
            sum += this->array_to_sum[i];
        }
        *this->sum_destination = sum;
    }
        
    int *sum_destination,
    int *array_to_sum;
    int array_size; 
};

    Notice that the Task subclass can (and typically would) contain member variables. Then, submit a bunch of instances of this class for each thing they wanted to do in parallel

    int arrayA[ARRAY_SIZE], arrayB[ARRAY_SIZE];
int sum_of_A, sum_of_B;
ThreadPool pool(num_threads);
    
pool.SubmitTask("sum arrayA", new ComputeSumTask(&sum_of_A, arrayA, ARRAY_SIZE));
pool.SubmitTask("sum arrayB", new ComputeSumTask(&sum_of_B, arrayB, ARRAY_SIZE));
...

    and finally wait for the tasks to complete before stopping the thread pool:

    pool.WaitForTask("sum arrayA");
pool.WaitForTask("sum arrayB");

pool.Stop();

Some Pthreads Resources

  1. The official documentation at http://pubs.opengroup.org/onlinepubs/9699919799/.

  2. The lecture slides on pthreads, pthread_mutexes, pthread_conds, etc.

  3. Chapters 27-31 of Operating Systems: Three Easy Pieces

  4. This tutorial from LLNL.