Capstone C: results and totals
A result that carries the worker that produced it can answer two questions a plain sum cannot: in which order did the work come back, and how much of it did each worker take. The answer to the first changes on every run, and the answer to the second changes with it, because the faster worker takes the next job. This lesson prints both and then the stable part.
The arrival order
The jobs have different delays, so a job that was written later can finish earlier. The result record carries the worker as well as the sum, and the first loop prints the results in the order they arrived in the collection:
using System.Threading.Channels;
Console.WriteLine("results 1.0");
var jobs = new[]
{
new Job(1, 1000, 30),
new Job(2, 500, 10),
new Job(3, 2500, 20),
new Job(4, 1500, 10),
new Job(5, 300, 30),
};
var queue = Channel.CreateBounded<Job>(2);
var results = Channel.CreateUnbounded<JobResult>();
var producer = Task.Run(async () =>
{
foreach (var job in jobs)
{
await queue.Writer.WriteAsync(job);
}
queue.Writer.Complete();
});
var workers = Enumerable.Range(1, 2).Select(worker => Task.Run(async () =>
{
await foreach (var job in queue.Reader.ReadAllAsync())
{
var sum = await Work(job);
await results.Writer.WriteAsync(new JobResult(job.Id, worker, sum));
}
})).ToArray();
var finish = Task.Run(async () =>
{
await Task.WhenAll(workers);
results.Writer.Complete();
});
await producer;
var collected = new List<JobResult>();
await foreach (var result in results.Reader.ReadAllAsync())
{
collected.Add(result);
}
await finish;
foreach (var result in collected)
{
Console.WriteLine($"arrived job {result.Id} from worker {result.Worker}");
}
foreach (var group in collected.GroupBy(result => result.Worker).OrderBy(group => group.Key))
{
Console.WriteLine($"worker {group.Key}: {group.Count()} jobs, sum {group.Sum(result => result.Sum)}");
}
var order = string.Join(", ", collected.OrderBy(result => result.Id).Select(result => $"job {result.Id}"));
Console.WriteLine($"sorted {order}");
Console.WriteLine($"results {collected.Count} total {collected.Sum(result => result.Sum)}");
static async Task<long> Work(Job job)
{
await Task.Delay(job.DelayMs);
var sum = 0L;
for (var i = 1; i <= job.Units; i++)
{
sum += i;
}
return sum;
}
record Job(int Id, int Units, int DelayMs);
record JobResult(int Id, int Worker, long Sum);
dotnet run
echo "status: $?"
results 1.0
arrived job 2 from worker 1
arrived job 3 from worker 1
arrived job 1 from worker 2
arrived job 4 from worker 1
arrived job 5 from worker 2
worker 1: 3 jobs, sum 4377250
worker 2: 2 jobs, sum 545650
sorted job 1, job 2, job 3, job 4, job 5
results 5 total 4922900
status: 0
The ids in the first five lines are 2, 3, 1, 4, 5 and not 1, 2, 3, 4, 5: the two jobs with the shortest delay came back first, and the job with the longest delay, the first one written, came back third.
The distribution
In this run worker 1 took jobs 2, 3 and 4 and worker 2 took jobs 1 and 5. A second run of the same program gave worker 1 jobs 1 and 4 and worker 2 jobs 2, 3 and 5, with the sums 1 626 250 and 3 296 650. Neither run is wrong: a worker takes the next job from the channel when it is free, and which worker is free depends on the delays that came before.
- The distribution is not a work split. A pool splits jobs by whoever is free, and the arithmetic of that is timing, not a plan.
- A pool of two workers gives each worker roughly half of the jobs only when the jobs are alike; the delays here are ten, twenty and thirty milliseconds, which is enough to move a job from one worker to the other.
- GroupBy(result => result.Worker) over a sorted collection is still a grouping by the worker that actually ran the job, so the grouping is honest about the run even though it is not repeatable.
What is stable
Three things do not move between runs: the sorted order of the ids, the count of results and the total of the sums. They are the last two lines of the output above, and they are what a test over this program compares. A test that compares the whole output, including the arrival lines, would fail on most runs and pass on some, which is worse than either.
This is the general rule of a test over a concurrent program: compare what the program promises, not what it happened to print. The promises of the pool are the set of results and their totals; the order and the distribution are the schedule.
The next lesson closes the pool properly: the producer completes, the workers end, the result channel completes, and the program waits for every stage before it prints. A cancelled run is the second half of that lesson.
Exercises
- Run the program five times and collect the distribution of the five jobs in a table.
- Give every job the same delay and see whether the distribution becomes stable.
- Print the result with the highest sum first, and say whether that order is stable.
- Add the delay of the job to the result and compute the busy time of each worker.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why is the arrival order not 1, 2, 3, 4, 5?
Answer
The jobs have different delays and the workers finish whenever they finish
The measured first lines are 2, 3, 1, 4, 5.
-
What decides which worker takes a job?
Answer
Whichever worker is free when the job is taken from the channel
A second measured run split the five jobs the other way.
-
What does this program print?
var sums = new[] { 500500L, 3126250L, 125250L, 1125750L, 45150L }; Console.WriteLine(sums.Sum());Answer
4922900
That is the total of the measured run.
-
Which lines of the output does a test compare?
Answer
The sorted order, the count and the total
The arrival order and the distribution move between runs.
-
What does this program print?
var jobs = new[] { 2, 3, 1, 4, 5 }; Console.WriteLine(string.Join(",", jobs.OrderBy(id => id)));Answer
1,2,3,4,5
OrderBy sorts the ids, which is the stable line of the program.
-
Why does the per-worker sum change between runs?
Answer
The set of jobs each worker took changes with the timing
A second run put jobs 1 and 4 on worker 1 and the other three on worker 2.
-
What does this program print?
var results = new[] { (Id: 1, Worker: 2), (Id: 2, Worker: 1) }; foreach (var group in results.GroupBy(r => r.Worker).OrderBy(g => g.Key)) { Console.WriteLine($"{group.Key}:{group.Count()}"); }Answer
1:1 and 2:1
Two groups of one result each, sorted by the worker.
-
What is the promise of the pool that a test can rely on?
Answer
Every job produced one result and the totals add up
The set and the totals are the contract; the schedule is not.
-
What does this program print?
var total = 0L; foreach (var n in new[] { 500500L, 3126250L }) { total += n; } Console.WriteLine(total);Answer
3626750
Two of the five sums add to 3626750.
-
Why is a test that compares the whole output worse than one that compares a summary?
Answer
It fails on most runs and passes on some, which says nothing about the code
A test that depends on the schedule tests the scheduler.
The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev