What can go wrong
On this page
A task-based program has no statement order to get wrong. It has dependencies instead, and they can be wrong in a few typical ways. This page goes through them with the hashing example of that chapter. Each mistake has a symptom that tells it apart:
| Symptom | Mistake |
|---|---|
| The program makes no progress and uses no processor time | A task waits for ever |
| Wrong results, depending on the order in which tasks run | A dependency is missing |
| Wrong results or crashes only with several threads | Data outside a shared object |
| A crash some time after a task or a function has ended | An object goes away too early |
| Everything stands still while one task works or sleeps | A task blocks or never waits |
A task waits for ever
A sequential program that has nothing left to do ends. A task-based program in which every remaining task waits for something that nobody will provide stays where it is. It does not crash and it uses no processor time; Run simply does not return. There are two ways to get there.
Nobody will signal
A task leaves without handing on what others wait for. In the example, every hash task must release every block, or the reader waits for it for ever. The reader must release an empty block at the end, or the hash tasks wait for the next block for ever. The path that is taken rarely is the dangerous one, and usually that is an error:
// wrong: on an error the task leaves and keeps the block
for (auto block = memory.GetMemory(); block.size != 0; block = memory.GetMemory()) {
if (!Process(block))
return; // the reader waits for this release for ever
memory.ReleaseMemory(block);
}In sequential code, leaving early is harmless: whatever would have followed just does not happen. Here other tasks depend on what the task would have done later. A task has to keep its promises on every path. The end of the data and errors travel through the shared object like the data itself:
bool failed = false;
for (auto block = memory.GetMemory(); block.size != 0; block = memory.GetMemory()) {
failed = failed || !Process(block);
memory.ReleaseMemory(block); // on every path
}This task keeps taking and releasing blocks until the end, so the others can finish. Stopping them early as well is a matter of design: see Errors and shutdown and Cancelling tasks.
Tasks wait in a circle
A task waits for something that only another task provides, while it holds something that task is waiting for:
// wrong: holds the block while it waits for a hash task
auto block = memory.GetMemory();
block.size = file.Read(block.data);
checked.Wait(); // signalled by a hash task once it has seen the block ...
memory.ReleaseMemory(block); // ... which it gets only hereHand on what you hold before you wait for something else. To check a design, draw who waits for whom: tasks and shared objects as points, every wait as an arrow. A circle of arrows is a program that stops.
The example itself looks like a circle: the reader waits for the hashes, and the hashes wait for the reader. It is none, because the reader waits for the hashes of the previous block. What gets it going is the state at the start: every block is free. A ring of waits always needs something to start it, such as a permit or a first block, and forgetting that is a program that stops at its first step.
Finding the task that waits
- In the debugger, pause the program. The Visual Studio extension lists the suspended tasks with their call stacks, so you see which wait each one stands in (Debugging).
- In tests, give the run a time limit, or wait with a timeout where a wait must end soon. A test that fails with a message is worth more than one that never ends.
- On one thread. With a local scheduler, a program that stops does so in every run and at the same place.
A dependency is missing
A task uses something without waiting for it. Here the reader waits for MD5 before it fills the buffer again, but not for SHA-1:
namespace MissingDependency {
void ReadTooEarly(Explicit::Shared& shared, const wchar_t* path)
{
File file;
file.Open(path);
for (;;) {
shared.md5Free.Wait(); // wrong: SHA-1 may not be done with the block yet
shared.size = file.Read(shared.memory);
shared.md5Filled.Release();
shared.sha1Filled.Release();
if (shared.size == 0)
break;
}
file.Close();
}
// ...
} // namespace MissingDependencyWhether this goes wrong depends on the order in which the tasks happen to run. The example runs it with the three tasks added in each of the six possible orders: the hashes are right in four and wrong in two. In the four, SHA-1 happens to get its turn before the reader continues. Nothing in the code says that it must.
Two things make this mistake worse than it looks:
- It hides. A program that passes its test can fail after a change that has nothing to do with the mistake: one more task, another priority, another scheduler.
- With several threads it turns into a data race. On one thread, the same order gives the same result in every run. On several threads, the same mistake shows up now and then.
Test in every order, on one thread
A task-based program is right if its result does not depend on the order in which its tasks run. That can be tested. Run the tasks on a LocalScheduler, add them in different orders and compare each result with a reference:
int wmain(int argc, wchar_t* argv[])
{
// ...
// The same test finds a missing dependency: the hashes are right in some orders and wrong in
// others - on one thread, so in every run alike.
int right = 0;
do {
if (Same(MissingDependency::HashFile(path, order), expected))
++right;
} while (std::next_permutation(order.begin(), order.end()));
std::printf("reader that does not wait for SHA-1: right in %d of %d orders\n", right, orders);
// ...
}The test is cheap and finds a missing dependency in every run. Changing the number of blocks or the block size varies the order further. Move the tasks to worker threads once this test passes.
Data outside a shared object
On a local scheduler, tasks take turns only when one of them waits. Between two waits a task is not interrupted. So two tasks can both change a plain variable, such as a counter of the bytes hashed so far, and it works on one thread.
On worker threads, the two tasks run at the same time and the counter is a data race. Whatever two tasks touch belongs in a shared object that states the rule for it: an atomic counter, a CriticalSection, or one task that owns the data (Semaphores and locks).
The example has no such data. Each block is written by one task and only read after that, and
SharedMemory decides who may do which. That is why the hash tasks could move to worker threads
without a change.
An object goes away too early
Tasks and shared objects must be alive as long as anybody uses them. In a sequential program the scopes take care of that. In a task-based program they do so only if the scope waits for its tasks.
In the example, the objects live in the function that calls Run, and Run returns once all
tasks of the scheduler have ended. With the hash tasks on worker threads this is no longer enough:
Run does not wait for tasks of another scheduler. Without the wait for the
TaskGroup_s, the function would return while the hash tasks still run, and
take the memory, the results and the task objects with it. The crash comes later and somewhere
else.
Wait for every task before anything it uses goes away (Lifetimes and sizing).
A task blocks or never waits
Tasks give way to each other by waiting. A task can fail to do that in two ways:
- It blocks its thread in
ReadFile,Sleep, a mutex orWaitForSingleObject. The thread stops, and with it every task of a local scheduler; a default scheduler has one thread less meanwhile. If the task blocks until another task of the same local scheduler has done something, that never happens. Use the waits of the library and asynchronous I/O instead. - It never waits. A long computation on a local scheduler keeps every other task from running until it is done. Give long work to worker threads, or let it yield now and then.
More order than needed
The opposite mistake is no bug, but it gives away what the paradigm is for: one lock around everything, a task that waits for another one just to be safe, MD5 that waits for SHA-1. The program is right and sequential again. Every wait that is not needed is also one more arrow that can close a circle. State the dependencies the data has, and no others.
A checklist
- Does every task hand on what it takes, on every path, including errors and the end?
- Does a task wait for something while it holds what another task needs?
- What starts each ring of waits?
- Is everything that two tasks touch inside a shared object?
- Is the result the same in whatever order the tasks are added, on one thread?
- Who waits for the tasks of other schedulers before the objects go away?
- Does a task call anything that blocks its thread?