Shared objects
On this page
In a task-based program, tasks do not know each other. They meet in shared objects that hold the data and own the waiting. A task calls the object and may be suspended there; another task's call lets it go on.
There are only a few forms of such objects, and they come back in every program. This page lists them. For each form it answers the three questions that describe a shared object:
- Who waits, and for what?
- Who wakes the task that waits?
- How does the end get through, so that no task waits for ever?
| Tasks that meet | Form | Ready-made |
|---|---|---|
| one writer, one reader, a stream of bytes | A stream | SpscVirtualMemoryPipe |
| one writer, several readers of the same data | Blocks with several readers | – (the SharedMemory of this chapter) |
| many producers, many consumers, separate items | A channel | BoundedPointerQueue and Semaphore |
| tasks that finish in any order, one that needs their results in order | An ordered join | WaitableTask, TaskGroup_s, OrderedFileWriter |
| a reader that must not run ahead of the rest | A ring | Semaphore_s |
| one task that waits for several to end | A group | TaskGroup, TaskGroup_s |
| many tasks that wait for one thing to happen | A gate | ManualResetEvent, WaitableTask |
| many tasks, a resource for a few | A limited resource | Semaphore, CriticalSection |
A stream between two tasks
One task produces bytes, one consumes them, and the bytes have an order. This is the connection between two stages of a pipeline.
- Who waits: the consumer, for the next bytes.
- Who wakes: the producer, when it releases what it has written.
- The end: the producer marks the end of the stream, on every path. The consumer then gets no more memory and leaves its loop.
// Writes count samples into the stream, block by block, straight into the stream's
// memory.
void WriteSamples(IWriteSequentialMemory& out, std::size_t count) noexcept
{
// announce the size first (also for an empty stream)
out.Initialize(count * sizeof(Sample));
constexpr std::size_t PerBlock = 4096; // samples per block
for (std::size_t first = 0; first < count; first += PerBlock) {
const std::size_t n = std::min(PerBlock, count - first);
// the next bytes of the stream
std::byte* data = out.RequestWriteMemory(n * sizeof(Sample));
if (data == nullptr)
break;
for (std::size_t i = 0; i < n; ++i) {
const Sample sample = TakeSample(first + i);
std::memcpy(data + i * sizeof(Sample), &sample, sizeof(Sample));
}
out.ReleaseWriteMemory(n * sizeof(Sample)); // publish them to the consumer
}
out.SetEndOfStream(); // always, also after an error
}The object is a pipe. Both sides work in the pipe's own memory, so nothing is copied on the way.
Blocks with several readers
One task writes blocks, and several tasks each read every block. The readers do not take the blocks away from each other. Each sees all of them, at its own pace.
- Who waits: each reader for the next block it has not seen; the writer for a block that all readers are done with.
- Who wakes: the writer wakes every reader when it releases a block. The last reader to release a block wakes the writer.
- The end: an empty block, which travels to every reader like the data.
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 HiddenEvery task gets a port of its own, and the port remembers where that task stands. This is the
SharedMemory of Thinking in tasks. The library has
no class for this form; the one of the example is short, and it shows what such an object is made
of: a count per reader for "blocks ready for you" and one for "blocks you gave back".
A channel of items
Any number of tasks hand items to any number of other tasks. An item goes to one of the receivers, whichever comes first. This is how work is distributed, and how requests reach a pool of workers.
- Who waits: a receiver, for an item; a sender, for room.
- Who wakes: each side wakes the other with a permit of a semaphore.
- The end: it does not come by itself, because no task knows whether another one will still send. Somebody who knows has to say so: a stop item per receiver, or the owner cancels the receivers.
// A fixed pool of items circulates between two queues: free items and items with
// work. There are never more than PoolSize items, so a queue with PoolSize slots
// can never overflow - by construction, not by luck. Each queue has a semaphore
// that counts its items.
// a power of two: it is also the queue capacity
constexpr std::size_t PoolSize = 256;
class Channel
{
public:
bool Initialize() noexcept
{
if (!free_.Initialize(PoolSize) || !work_.Initialize(PoolSize))
return false;
for (WorkItem& item : pool_)
free_.Enqueue(&item);
freeCount_.Release(PoolSize);
return true;
}
WorkItem* AcquireFree() noexcept { return Take(freeCount_, free_); }
void Post(WorkItem* item) noexcept { Put(workCount_, work_, item); }
WorkItem* Receive() noexcept { return Take(workCount_, work_); }
void Recycle(WorkItem* item) noexcept { Put(freeCount_, free_, item); }
private:
static void Put(Semaphore& count, BoundedPointerQueue<WorkItem>& queue,
WorkItem* item) noexcept
{
queue.Enqueue(item); // first the item, then the permit that announces it
count.Release();
}
static WorkItem* Take(Semaphore& count,
BoundedPointerQueue<WorkItem>& queue) noexcept
{
count.Wait(); // suspends the task until an item is there
// The permit guarantees an item, but Dequeue can see the queue as empty for
// a moment while another task takes the head item: just try again.
WorkItem* item;
while ((item = queue.Dequeue()) == nullptr)
TC::YieldTask();
return item;
}
std::vector<WorkItem> pool_ = std::vector<WorkItem>(PoolSize);
BoundedPointerQueue<WorkItem> free_;
BoundedPointerQueue<WorkItem> work_;
// Several tasks wait on each semaphore: the multi-waiter variant.
Semaphore freeCount_;
Semaphore workCount_;
};Two details of this object are worth keeping. The items circulate, from the free queue to the work queue and back, so their number is fixed and no queue can overflow. And the item is queued before its permit is released: a permit always means that an item is there (Producer/consumer, Queues and stacks).
An ordered join
Tasks work on parts in parallel and finish in any order. One task needs the results in the order of the parts, for example to write them to a file.
- Who waits: the collecting task, for part i, then for part i+1.
- Who wakes: the end of the task that worked on that part.
- The end: the collector knows the number of parts, or it finds an end mark where the next part would be.
The waiting is part of the task object itself. A WaitableTask can be waited for, and a loop over the tasks in the order of the parts is the join (Tutorial 3). Where the task object is reused, a TaskGroup_s per part does the same:
// One slot of the ring: a block on its way from the reader through a transform task
// to the writer.
struct Slot;
class TransformTask : public TC::Tasks::Task
{
public:
Slot* slot = nullptr;
void Run() noexcept override;
};
struct Slot {
std::vector<std::uint8_t> input = std::vector<std::uint8_t>(BlockSize);
std::vector<std::uint8_t> output = std::vector<std::uint8_t>(BlockSize);
std::uint64_t offset = 0;
ByteCount size = 0; // 0: the end of the input
TransformTask transform;
// the writer waits here for this slot's block
TC::Synchronization::TaskGroup_s transformed;
};
void TransformTask::Run() noexcept
{
for (ByteCount i = 0; i < slot->size; ++i)
slot->output[i] = Transform(slot->input[i], slot->offset + i);
}For files, OrderedFileWriter is this form ready-made: copy tasks fill in parts of the output in any order, and a writer task writes the finished front (Streaming large files, Ordered output).
A ring that bounds the work
A reader could run far ahead of the tasks that process its blocks, and fill the memory with blocks that wait. A ring gives the program a fixed number of slots. Each slot carries one block through all stages and is then free again.
- Who waits: the reader, for a free slot; the writer, for the next slot that has been started.
- Who wakes: the writer frees a slot when its block is written; the reader announces a slot when it has filled it.
- The end: a slot with no data, which the writer finds in its place in the order.
A ring is two counts, free slots and started slots, each a Semaphore_s with one waiter. Together with the ordered join above it is the whole frame of a pipeline with a parallel middle (Task graphs, Tutorial 6).
A group
One task starts several others and goes on when all of them have ended. This is the join of fork-join, and it is also how a scope makes sure that nothing it owns is still in use.
- Who waits: the task that started the others.
- Who wakes: the last task that ends.
- The end: is what the group is for.
int main()
{
// ...
// Fork/join from main: eight tasks, one group.
constexpr std::uint64_t n = 8'000'000;
RangeTask parts[8];
TC::Synchronization::TaskGroup_s group;
for (std::uint64_t i = 0; i < 8; ++i) {
parts[i].Set(n * i / 8, n * (i + 1) / 8);
group.AddTask(&parts[i]); // before the task is added to the scheduler
scheduler->AddTask(&parts[i]);
}
group.Wait(); // passes once all eight have exited
std::uint64_t total = 0;
for (auto& part : parts)
total += part.Sum();
// ...
}A task is counted into the group before it is started. Otherwise the wait could pass between the two (Waiting for tasks, Wait for a group).
A gate
Several tasks need one thing that happens once: the settings are loaded, a connection is up, the program may start. Before it has happened they wait; afterwards nobody waits any more.
- Who waits: every task that comes before the event.
- Who wakes: whoever makes it happen, all waiting tasks at once.
- The end: the gate stays open. A gate that may never open needs a second way out, such as a flag that is set before the gate is opened anyway.
int main()
{
// ...
// A start gate: every task waits until main opens it.
ManualResetEvent gate;
auto runner = [&gate]() noexcept {
gate.Wait(); // any number of waiters
Work();
};
auto a = TC::Tasks::Task::Create(runner);
auto b = TC::Tasks::Task::Create(runner);
auto c = TC::Tasks::Task::Create(runner);
auto d = TC::Tasks::Task::Create(runner);
TC::Synchronization::TaskGroup_s runners;
TC::Tasks::Task* tasks[] = {&a, &b, &c, &d};
for (TC::Tasks::Task* task : tasks) {
runners.AddTask(task);
scheduler->AddTask(task);
}
gate.Set(); // resumes all waiting tasks; later Waits pass at once
runners.Wait();
// ...
}If the thing is the result of a task, the task itself is the gate: any number of tasks can wait for a WaitableTask and read its result afterwards (Events).
A limited resource
Many tasks want something that serves only a few at a time, or only one: three connections, one log file, a structure that must not be changed by two tasks at once.
- Who waits: a task that finds no permit.
- Who wakes: a task that gives its permit back.
- The end: there is none to pass on. What matters is that a permit comes back on every path, which a scope guard does:
// At most three downloads at a time; further callers suspend until a slot is free.
class Downloader
{
public:
void Download(const Item& item) noexcept
{
// Wait: suspends the task until a permit is free
SemaphoreLock slot(slots_);
Transfer(item);
} // ~SemaphoreLock: Release of the permit
private:
Semaphore slots_{3}; // three permits, any number of waiting tasks
};With one permit this is a lock, and for data that two tasks change the library has CriticalSection. Keep in mind what a lock gives: one at a time, in no particular order (Semaphores and locks).
Questions for an object of your own
When none of the forms fits, the object is built from the same primitives. The questions from the top of this page, and three more, make up its design:
- Who waits, who wakes, how does the end get through? Write the answers into the comment of the class. If an answer is missing, a task will wait for ever one day.
- What is the state at the start? A ring starts with all slots free, a channel with all items in the free queue. An object whose counts all start at zero has nobody who can take the first step.
- How many tasks wait at the same place? If it is always one, such as the reader or the writer, the single-waiter variants are cheaper and can wait with a timeout.
- Who owns the object? It must outlive every task that uses it. It belongs where the tasks are started and waited for (Lifetimes and sizing).
The object can be assembled from semaphores, events and queues, as SharedMemory and the channel
are. If it needs a wait of its own kind,
Custom primitives shows how to write one.