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-10-01]. 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. If any thread is in the middle of running a Task, this should wait for that thread to finish running the task rather than interrupting it. 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 (or below, if you took CoA 2) or the threads spawned by the constructor to run queued tasks consume a lot of compute time while waiting for some condition (e.g. a task finishing or a new task being available) 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. If you have previously taken CoA 2, then as an additional requirement, you must implement the following methods:

    • bool CancelTask(const std:string &name) — stop a task with a particular name from running if it has not already started. This should return true if successful, and false if the task in question has already started running or completed.

      You may assume that this is called instead of calling WaitForTask for a task of the same name.

    • void Pause() — after any currently running tasks complete, temporarily stop the thread pool worker threads from running any tasks. This must not return until after all the worker threads are not running tasks.

    • void Resume() — assuming a previous call to Pause was made, cause the thread pool threads to resume processing tasks.

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

  4. You can use the supplied pool-test program to help test your thread pool implementation. [If you started this assignment before 30 September 2019, make sure you get an updated version of pool-test.cc to avoid sometimes confusing failure reporting.] Note that this is may not be a complete test. For example, it is likely that this test case will not expose various race conditions that might exist in your code, nor will they attempt to determine if your code consumes a lot of CPU time while waiting.

    If you have previously taken CoA 2, then we have supplied a pool-test-coa2-extra.cc which contains some tests for the extra functions you must implement. To use these tests, add it in addition to the supplied pool-test.cc to the Makefile, following the pattern used for pool-test.cc to add additional rules to the Makefile. Like with supplied pool-test, these tests will not completely test the methods you need to implement.

  5. 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 front() and pop_front() 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.