Sat Jan 11 19:03:49 CET 2020
A scheduler, again.
Blocked tasks are a set.
We have a way to partition it into reading and writing, which is only
necessary to limit the search, but it might be actually simpler to use
a single data structure and iterate around it.
What I'm looking for is a stop condition.
1. Precondition: everything is blocking.
2. Some external read or write happens.
3. Find a corresponding blocked task
3a. There is no task. Add it to the set and go to 1.
3b. There is a corresponding task. Remove it from the set. Run
both tasks and execute 2. for each task.
It is 3b that looks like a binary tree recursion. I.e. the
continuations that just were created will need to be checked if they
unblock anything, because nothing else will cause an unblock.
So the "hot" list of unchecked suspended tasks has a different meaning
than the "cold" list of suspended tasks. It can just as well be
implemented as a stack. It doesn't seem to matter in which order the
tasks are executed.
( I would have had a different life if I understood this earlier.
This is really magnificient. )
So let's make some assumptions:
- The "hot" list can be a stack.
- The "cold" list is fairly implicit. We never need to enumerate. We
just need two operations:
- Given channel id, check if there is a blocked task
- Given channel id with no blocked task, add a task
Because of the "hot" list, there is no need to ever have a channel
data structure that has two blocking tasks.
So the data structure seems quite straightforward:
A channel is a pointer to a blocked task, or NULL.
It is actually possible that there is more than one blocked task,
e.g. a channel can have multiple writers (or multiple readers, but
that only makes sense for a multiprocessor).
To implement multiple blocked tasks on a channel, it seems best to add
a next_k pointer to the k list.
EDIT: I think I have an implementation for just send and receive.
What about select?
Select is a read that can rendez-vous with a whole lot of channels.
Maybe it's simplest to implement only single write and multiple