Task-based programming
On this page
- One control flow
- An activity is not a unit
- The order says more than the program needs
- One control flow per activity
- The order is a result
- What is still wrong
- Dependencies belong to the data
- What the paradigm gives
- Programs are assembled
- Where tasks run is a separate decision
- One thread first
- The rules in short
- See also
Most programs start as one control flow: a sequence of statements that puts every step in order. A task-based program is built from tasks: independent activities, each with a control flow of its own, that wait for what they need. The order in which things happen is then no longer written down. It follows from what each task waits for.
The term task-based programming is used in two senses. The common one is about parallelism: split the work into many small tasks and let a scheduler distribute them over threads, as Intel TBB, OpenMP tasks and the .NET Task Parallel Library do. The tutorial works that way, with one task per block. This chapter is about the other sense: building a program from long-lived activities that wait for each other's data. That idea is older and has several names: communicating sequential processes, process networks, flow-based programming, and tasks with protected objects in Ada. The two senses belong together. A program structured the second way is ready to run in parallel the first way, and tasks that can wait serve both.
This chapter explains the paradigm: what one control flow costs, what changes when a program is
split into tasks, and which rules keep the tasks simple. One small program serves as the example
throughout. It reads a file and computes its MD5 and SHA-1 hashes. The code comes from
task-based-programming.cpp, a complete Windows program that runs every version shown here and
checks that all of them compute the same hashes.
The paradigm is not tied to this library. It needs one thing, though: waiting must be cheap. With ConcurrentTasks a task is an ordinary function, and a task that waits holds no thread (Why fibers).
One control flow
A sequential program is a sequence of statements, and the sequence carries everything at once: what is computed, when each step happens and which data each step works on.
namespace Procedural {
Hashes HashFile(const wchar_t* path)
{
std::vector<std::byte> memory(BlockSize);
File file;
file.Open(path);
Hash md5(BCRYPT_MD5_ALG_HANDLE);
Hash sha1(BCRYPT_SHA1_ALG_HANDLE);
for (;;) {
const std::size_t size = file.Read(memory);
if (size == 0)
break;
md5.Update(std::span(memory).first(size));
sha1.Update(std::span(memory).first(size));
}
file.Close();
return {md5.Finish(), sha1.Finish()};
}
} // namespace ProceduralThis is easy to read. It is hard to change, for two reasons, and both come from the single control flow.
An activity is not a unit
A procedural program is made of functions, and functions can be reused: file.Read, md5.Update.
But the program does three activities: reading a file block by block, computing MD5 over
everything that arrives, and the same for SHA-1. An activity is a loop with state that lives from
one round to the next. In the program above, none of the three exists on its own. Each is a line
or two inside a loop that belongs to all of them.
So an activity cannot be taken out, replaced or added without rewriting the loop:
- hash with SHA-256 as well, or without SHA-1,
- read from a socket instead of a file,
- hash the same data in another program, next to other work.
The order says more than the program needs
Statements come one after the other, so a sequential program always states a total order: read, MD5, SHA-1, read, MD5, SHA-1, … The program needs far less. What each step really waits for:
| Step | waits for | because |
|---|---|---|
| read block i | MD5 and SHA-1 of block i−1 | there is only one buffer |
| MD5 of block i | read block i, MD5 of block i−1 | the data; MD5 carries its state from block to block |
| SHA-1 of block i | read block i, SHA-1 of block i−1 | the same for SHA-1 |
read(0) ──► MD5(0) ──► MD5(1) ──► … ──► MD5 finished
│ └─► SHA-1(0) ─► SHA-1(1) ─► … ─► SHA-1 finished
└── buffer free again once MD5(i) and SHA-1(i) are done ──► read(i+1)MD5 and SHA-1 do not wait for each other at all. With a second buffer, the next block could be read while the last one is hashed. But in the code, the order that is needed and the order that just happened to be written look the same. Nothing can tell them apart, so nothing can make use of a second core or a second buffer.
One control flow per activity
Task-based programming gives every activity a control flow of its own: a task. A task is written like a small program. It has its own loop and its own local state, and it runs from its start to its end. Inside, a task is ordinary procedural code. What changes is that there are several control flows instead of one.
Where the sequential program put a step at a certain place in the sequence, a task waits for what the step needs. Waiting is the central operation of the paradigm: it suspends the task until the condition holds, and the scheduler runs another task meanwhile.
In the example, the three activities become three tasks that share the buffer. For each hash there is one signal for "the block is filled" and one for "this hash is done with it", both a Semaphore_s:
namespace Explicit {
// What the three tasks share: one block of memory and, for each hash, a signal that the block is
// filled and one that the hash is done with it.
struct Shared {
std::vector<std::byte> memory = std::vector<std::byte>(BlockSize);
std::size_t size = 0; // bytes in memory; 0: the file has ended
Semaphore_s md5Filled{0};
Semaphore_s sha1Filled{0};
Semaphore_s md5Free{1};
Semaphore_s sha1Free{1};
};
// ...
} // namespace Explicitnamespace Explicit {
// ...
void Read(Shared& shared, const wchar_t* path)
{
File file;
file.Open(path);
for (;;) {
shared.md5Free.Wait(); // both hashes are done with the block
shared.sha1Free.Wait();
shared.size = file.Read(shared.memory);
shared.md5Filled.Release(); // both may hash it
shared.sha1Filled.Release();
if (shared.size == 0)
break;
}
file.Close();
}
void Md5(Shared& shared, std::string& result)
{
Hash md5(BCRYPT_MD5_ALG_HANDLE);
for (;;) {
shared.md5Filled.Wait();
if (shared.size == 0)
break;
md5.Update(std::span(shared.memory).first(shared.size));
shared.md5Free.Release();
}
result = md5.Finish();
}
void Sha1(Shared& shared, std::string& result)
{
Hash sha1(BCRYPT_SHA1_ALG_HANDLE);
for (;;) {
shared.sha1Filled.Wait();
if (shared.size == 0)
break;
sha1.Update(std::span(shared.memory).first(shared.size));
shared.sha1Free.Release();
}
result = sha1.Finish();
}
// ...
} // namespace ExplicitEvery Wait in this code is one entry of the table above. The tasks state the dependencies the
program has, and no others.
The order is a result
Nobody decides when a task runs. The scheduler runs whatever can run:
namespace Explicit {
// ...
// order: the order in which the three tasks are added, e.g. {2, 0, 1}
Hashes HashFile(const wchar_t* path, const std::array<int, 3>& order)
{
Shared shared;
Hashes hashes;
auto read = Task::Create([&] { Read(shared, path); });
auto md5 = Task::Create([&] { Md5(shared, hashes.md5); });
auto sha1 = Task::Create([&] { Sha1(shared, hashes.sha1); });
Task* tasks[] = {&read, &md5, &sha1};
LocalScheduler scheduler;
for (int i : order)
tasks[i]->Schedule(scheduler);
scheduler.Run(); // returns once all three have ended
return hashes;
}
} // namespace ExplicitThe three tasks can be added in any order. The example adds them in all six, and the hashes are the same every time. A task that starts too early, such as a hash before anything is read, waits and lets another task run.
In a sequential program, a wrong order is a wrong program. A task-based program has no order to get wrong. What can be wrong is a dependency: a task that does not wait for something it needs (What can go wrong).
That the result is the same in every order is a property of how these tasks are connected, not of tasks as such. Every block has one writer, and every reader gets the blocks in the order they were written. Networks of this kind are known as Kahn process networks, and they compute the same result under every schedule. Tasks that change the same data in an order that nothing states do not have this property.
Note that all of this runs on one thread. A LocalScheduler runs its
tasks on the thread that calls Run. In the sense of this chapter, task-based programming is
first a way to structure a program. Running tasks in parallel comes later, and it comes without
changing the tasks.
What is still wrong
The tasks know each other. The reader knows that there are two hashes and signals each of them.
Md5 and Sha1 are copies that differ only in the signals they use. A third hash would need two
more semaphores and a change in the reader. The dependencies are stated now, but in the wrong
place.
Dependencies belong to the data
A task does not really depend on another task. It depends on data: the reader needs a block it may fill, a hash needs the next filled block. So the waiting belongs to the object that holds the data, not to the tasks. This is the idea of a monitor: an object that guards its data and makes its callers wait until they may use it.
In the example, that object is SharedMemory. It gives every task a port with two calls:
namespace Hidden {
// ...
class SharedMemory
{
// ...
struct Block {
std::span<std::byte> data;
std::size_t size = 0; // bytes in data
};
class Port
{
public:
Block GetMemory() noexcept { return owner_->Get(*this); }
void ReleaseMemory(const Block& block) noexcept { owner_->Release(*this, block); }
private:
friend class SharedMemory;
SharedMemory* owner_ = nullptr;
std::size_t reader_ = 0; // the reader's index; Writer for the writer
std::size_t next_ = 0; // the number of the block this port uses next
};
// ...
};
// ...
} // namespace HiddenGetMemorywaits for the next block this task may use: a free block for the writer, the next filled block for a reader.ReleaseMemoryhands the block on: from the writer to every reader, and back to the writer once every reader has released it.
How it does that, with two semaphores per reader, is inside the class and no task sees it. The tasks shrink to this:
namespace Hidden {
// ...
void Read(SharedMemory::Port& memory, const wchar_t* path)
{
File file;
file.Open(path);
for (;;) {
auto block = memory.GetMemory();
block.size = file.Read(block.data);
memory.ReleaseMemory(block);
if (block.size == 0)
break;
}
file.Close();
}
// MD5, SHA-1, SHA-256 alike: the algorithm is a parameter
void HashBlocks(SharedMemory::Port& memory, BCRYPT_ALG_HANDLE algorithm, std::string& result)
{
Hash hash(algorithm);
for (auto block = memory.GetMemory(); block.size != 0; block = memory.GetMemory()) {
hash.Update(block.data.first(block.size));
memory.ReleaseMemory(block);
}
result = hash.Finish();
}
// ...
} // namespace HiddenEach task now reads like sequential code: get, work, release. The task says what it does; the shared object says when it may. And there is only one hash task left, with the algorithm as a parameter, because nothing in it names a particular signal any more.
Tip
When a task names another task, or a signal that exists for another task, move that knowledge into the object the two share. The library has such objects ready-made: a pipe between a writer and a reader, queues and stacks, and file stages that read and write in order. Shared objects lists the forms such objects take.
What the paradigm gives
Programs are assembled
A task-based program has one place where it is put together: create the shared objects, create the tasks, run them.
namespace Hidden {
// ...
Hashes HashFile(const wchar_t* path, const std::array<int, 3>& order)
{
SharedMemory memory(1, 2, BlockSize); // one block, two readers: as in the loop
Hashes hashes;
auto read = Task::Create([&] { Read(memory.WriterPort(), path); });
auto md5 = Task::Create([&] { HashBlocks(memory.ReaderPort(0), BCRYPT_MD5_ALG_HANDLE, hashes.md5); });
auto sha1 = Task::Create([&] { HashBlocks(memory.ReaderPort(1), BCRYPT_SHA1_ALG_HANDLE, hashes.sha1); });
Task* tasks[] = {&read, &md5, &sha1};
LocalScheduler scheduler;
for (int i : order)
tasks[i]->Schedule(scheduler);
scheduler.Run();
return hashes;
}
// ...
} // namespace HiddenActivities are units now, as functions are. One more hash is one more port and one more task; the reader and the other tasks stay as they are:
namespace Hidden {
// ...
// One more hash: one more reader and one more task. Read and the other tasks stay as they are.
Hashes HashFileWithSha256(const wchar_t* path, std::string& sha256Result)
{
SharedMemory memory(1, 3, BlockSize);
Hashes hashes;
auto read = Task::Create([&] { Read(memory.WriterPort(), path); });
auto md5 = Task::Create([&] { HashBlocks(memory.ReaderPort(0), BCRYPT_MD5_ALG_HANDLE, hashes.md5); });
auto sha1 = Task::Create([&] { HashBlocks(memory.ReaderPort(1), BCRYPT_SHA1_ALG_HANDLE, hashes.sha1); });
auto sha256 = Task::Create([&] { HashBlocks(memory.ReaderPort(2), BCRYPT_SHA256_ALG_HANDLE, sha256Result); });
LocalScheduler scheduler;
Task* tasks[] = {&read, &md5, &sha1, &sha256};
for (Task* task : tasks)
task->Schedule(scheduler);
scheduler.Run();
return hashes;
}
// ...
} // namespace HiddenWhere tasks run is a separate decision
A task says what it does and what it waits for. It does not say on which thread it runs. That is decided where the program is assembled, and it can be decided last. Here the hash tasks run on the threads of a default scheduler, and eight blocks instead of one let the reader run ahead:
namespace Hidden {
// ...
// The hashes on the threads of a default scheduler, the reader on the local one; with more
// blocks, reading runs ahead of hashing. The tasks are the same.
Hashes HashFileOnWorkers(const wchar_t* path, TC::ITaskScheduler& workers)
{
SharedMemory memory(8, 2, BlockSize);
Hashes hashes;
auto md5 = Task::Create([&] { HashBlocks(memory.ReaderPort(0), BCRYPT_MD5_ALG_HANDLE, hashes.md5); });
auto sha1 = Task::Create([&] { HashBlocks(memory.ReaderPort(1), BCRYPT_SHA1_ALG_HANDLE, hashes.sha1); });
auto read = Task::Create([&] {
TC::Synchronization::TaskGroup_s hashing; // the local scheduler does not see tasks on workers
hashing.AddTask(&md5);
md5.Schedule(workers);
hashing.AddTask(&sha1);
sha1.Schedule(workers);
Read(memory.WriterPort(), path);
hashing.Wait();
});
LocalScheduler scheduler;
read.Schedule(scheduler);
scheduler.Run();
return hashes;
}
} // namespace HiddenRead, HashBlocks and SharedMemory are unchanged. The parallelism was in the program all
along, in the dependencies the tasks state. A scheduler with more threads uses it.
Two details of this version:
- The local scheduler does not know the tasks that run on the workers, so its
Rundoes not wait for them. A TaskGroup_s does. - The reader still blocks its thread in
ReadFile. Reading asynchronously makes that a wait like any other.
One thread first
On a local scheduler, all tasks run on one thread, one after the other. Without other threads the order is the same in every run, the tasks can be stepped through in a debugger, and there are no data races. The structure of a program can be developed and tested that way, and moved to worker threads once it is right. How to find out what is worth running in parallel, and how to measure it, is the subject of the tutorial.
The rules in short
- One task per activity. Whatever has a loop and a state of its own gets a control flow of its own.
- Wait for what you need. A task never relies on the order in which tasks were added or on what another task has probably done by now.
- Tasks meet in shared objects. The object owns the synchronization. A task knows the object's calls and no other task.
- Assemble in one place. Objects, tasks and schedulers are created together, where their lifetimes are visible: a shared object outlives the tasks that use it.
- Decide last where tasks run. First get the dependencies right on one thread, then choose the schedulers.
See also
- Finding the tasks: from a sequential program of your own to tasks, step by step
- Shared objects: the forms in which tasks meet, and what the library has ready-made
- What can go wrong: the mistakes of task-based programs and how to find them
- The tutorial: parallelizing a program step by step, with measurements
- Tasks, Suspend and resume, The scheduler
- Task graphs, Semaphores and locks
- The local scheduler: tasks that run on the calling thread
- LocalScheduler, Semaphore_s, TaskGroup_s