# Design Document

This document describes the underlying design decisions of a task system that supports asynchronous task execution and dependency tracking.

## Terminology

- Task: the work represented by a single call to `runTask`.
- Unclaimed: when no proletariat has committed to finishing the task.
- Claimed: when a proletariat has committed to finishing the task.
- Incomplete: when a proletariat has not finished the task.
- Complete: when a proletariat has finished the task.
- Job: the work represented by `num_total_tasks` calls to `runTask`.
- Unclaimed: when any of its tasks are unclaimed.
- Claimed: when all of its tasks are claimed.
- Incomplete: when `num_complete_tasks` is not equal to `num_total_tasks`.
- Complete: when `num_complete_tasks` is equal to `num_total_tasks`.
- Bourgeoisie (thread): the thread that calls `runAsyncWithDeps` and `sync`.
- Proletariat (threads): a thread in the thread pool that powers that task system and actually does work

## Data Structures

### `job_dags`

The `job_dags` data structure keeps track of all the jobs that the task system is currently working on. The entries in `job_dags` represent jobs that can be done immediately and have no reliants.

std::list<IJob *> job_dags;
std::mutex job_dats_mutex;

### `job_directory`

This data structure maps a job ID to the address of the corresponding job object in memory _if the job is incomplete_. If the job is complete, then `job_directory` will map its job ID to `nullptr`. The main purpose of `job_directory` is to facilitate the addition of new jobs to the task system by making it easy to local reliants.

std::vector<IJob *> job_directory;
std::mutex job_directory_mutex;

### `proletariat`

The proletariat threads are part of a thread pool of size `num_threads`. The proletariats are spawned in the TaskSystem constructor and

## Functions

### `runAsyncWithDeps()`

The bourgeoisie calls this function in order to tell the task system that there is a new job that needs to be done. Concretely, what happens under the hood is:

1. An `IJob` object O is created on the heap to represent this new job.
1. The `runnable` field is copied from the first argument.
2. The `num_total_tasks` field is copied from the second argument.
2. If there are no reliants, then the O is added to the back of `job_dags`.
3. If there are reliants, then for each reliant R:
1. Use `job_directory` to check is R is complete.
2. If R is complete, then do nothing.
3. If R is incomplete, then add O to R's dependents and R to O's reliants.

### `sync()`

The bourgeoisie calls this function in order to efficiently wait until all the jobs it previously registered with `runAsyncWithDeps` have been completed.

## Classes

### `IJob`

The `IJob` class is perhaps the most important class in our task system. It represents work that has been added to the task system `runAsyncWithDeps` and work that needs to be completed by the proletariats. It can be connected to other `IJob` objects to represent complex dependencies between work.

class IJob {
    /* The runnable for this job. */
    IRunnable* runnable;
    /* How many tasks are part of this job. */
    int num_total_tasks;
    /* What is the next unclaimed task (incremented BEFORE work is done). */
    int next_unclaimed_task = 0;
    std::mutex next_unclaimed_task_mutex;
    /* How many tasks have been completed (incremented AFTER work is done). */
    int num_complete_tasks = 0;
    std::mutex num_complete_tasks_mutex;
    /* Jobs that depend on this job. */
    std::unordered_set<IJob *> dependents;
    /* Jobs that this job depends on */
    std::unordered_set<IJob *> reliants;
}

## Summary

When new jobs are added with a call to `runAsyncWithDeps`, a new `IJob` object is created storing the appropriate information. The new `IJob` is appended to the job directory. If there are no dependencies, the `IJob` is added to the `job_dags` worker queue. If there are dependencies, these are added to the `IJob` as reliants and for each reliant, the new job is added to its set of dependents.

When the `job_dags` worker queue is empty, all proletariat threads are put to sleep. When there is work to do, each proletariat should be doing meaningful work to maximize throughput (ie executing a task, preparing to execute a task, or documenting the completion of a task). All proletariats execute tasks for the current job at the top of the `job_dags` queue until all tasks associated with that job are claimed. Once all tasks for a job are claimed, that job is popped off of `job_dags` and the proletariats move on to the next job. The last thread to complete a task for a job is in charge of removing fulfilled dependencies and, if appropriate, pushing dependents onto `job_dags`.

When `sync` is called by the bourgeousie thread, that thread is put to sleep until the `job_dags` queue is empty and the last task for the last job is marked as completed. Then the bourgeousie thread returns.

## Development Plan

1. Implement the system using only one proletariat thread - no synchronization
2. Spawn two proletariat threads - using synchronization
3. Debug and submit

## Miscellaneous

-