Tasks, concurrency, and inter-process communication
Posted: Tue Aug 18, 2015 3:23 pm
I've written parallel software before, and I really like the thread pool pattern. There is one execution thread per processor core and a queue of tasks, and each thread processes away at the queue of tasks. I feel that it is a superior model for parallel processing than the alternative, which is to create one thread per component (what if you have more cores than components? what about threads that block?)
A task is a piece of work - it doesn't need to be run continuously. It does something and then quits. Examples of tasks:
- Handle a mouse click or key press.
- One one update of the game loop (e.g. the timer could trigger this 60 times a second), which could then spawn a subtask to update each of the dynamic objects in the game world.
- Write some bytes to a file.
- Ray trace a tile.
- One iteration of a "parallel for" loop.
It's a great when you have a single application in focus that is trying to use all CPU resources (a ray tracer, a video game, etc.) On existing operating systems when you try to mix multitasking and the thread pool pattern, you end up with multiple thread pools. So, I've been thinking for a while - would it be possible to have a thread pool at the OS level, and a global queue of tasks?
The more I've been thinking about this, I've wondered if it would be possible to eliminate the abstraction of threads completely, and describe all code as a series of tasks. Most programs are event based, so tasks will be spawned when events occur, and that is how programs will execute code. Starting a program can be considered an event, and so the initialisation logic runs as a task. A timer firing x times a second in a real time application can be considered event which runs a task. You can describe everything worth using processor time as a task.
Tasks are also much more lightweight than threads - creating a task is as simple as adding a message to the end of a queue rather than creating a thread by allocating a page and setting up a stack and registers.
Each processor core essentially runs a loop:
task.run() is essentially a function call into the body of the task. (In reality, task.run() is slightly more complicated - it will skip the task if the process is no longer running, switch to the address space, set up the parameter list - but still very light weight.)
For such a system to work we can't have blocking tasks, which means that all IO has to be done asynchronously. I feel that Node.js has done a great job at bringing asynchronous IO mainstream (example.) In my system, readFile() spawns a task to read the file, and once the file is loaded, another task is spawned with the loaded file passed in as a parameter. There should be no reason a task should consume CPU processing time just idling and waiting.
We also have to handle long running tasks which could potentially make the system unresponsive. There are two reasons a task takes a long time to run: 1) A programming bug and we get stuck in a loop, or 2) A long running algorithm that isn't divided up into sufficiently fine grained sub tasks. It would be very easy to detect if a task is taking more than one time slice (set a flag every time the timer interrupt is called, clear it every time you start processing another task, and if the flag already set when you enter the interrupt timer you know the currently running task has taken more than one time slice), and I can think of two ways to handle this:
1. Simply kill the task. Tasks are supposed to be light weight and it forces good programming practice to increase the granularity of your tasks.
2. Turn the long running task into a thread and preemptively schedule it like a traditional thread.
There's also the matter of forcing developers to write concurrency-safe code by at least being aware that tasks may be executed concurrently. I don't think this is an unreasonable request - I'm making my own applications programming language, so if they're going to have to learn a new language to use my system, they may as well pick up good habits from the start by forcing them to write concurrent, asynchronous, event-based code. As long as I provide a language that makes it very natural to do this.
In my standard library I'll provide developers with, I think it'll be useful to provide some types to simplify their lives. Such as:
- A consecutive queue. This will be a queue that will have a handler that is called when an item is added to the queue, however only one copy of the handler will be executed at once in sequence, even though you can add items to the queue concurrently. This will make it possible to write algorithms that will handle events that may occur concurrently, but you only want to handle them one at a time.
- A barrier. A handler is called when the barrier reaches 0. Developers can use this when they want to process many items in parallel, but then want to run a piece of code once all items have finished executing.
Tasks can also be the basis of inter-process communication.
Very much like how a mouse event will create a task in your process to handle the event, you can also create a task to run in another process. This will be the primary means of inter-process communication. Every running process will have a list of handlers. This list of handlers will essentially be a list of functions and their parameters. The parameters to these functions will be in a binary format similar to a protocol buffer message.
In my language, I will have a special kind of interface that you can cast processes to, and all you can add to these interfaces are function calls which take a protocol buffer message as an argument. Then at run time, you can attempt to cast a process to an interface:
This will queue a task in the other process:
You can also use a consecutive queue on top of this if you want to process messages one at a time.
What are your thoughts?
A task is a piece of work - it doesn't need to be run continuously. It does something and then quits. Examples of tasks:
- Handle a mouse click or key press.
- One one update of the game loop (e.g. the timer could trigger this 60 times a second), which could then spawn a subtask to update each of the dynamic objects in the game world.
- Write some bytes to a file.
- Ray trace a tile.
- One iteration of a "parallel for" loop.
It's a great when you have a single application in focus that is trying to use all CPU resources (a ray tracer, a video game, etc.) On existing operating systems when you try to mix multitasking and the thread pool pattern, you end up with multiple thread pools. So, I've been thinking for a while - would it be possible to have a thread pool at the OS level, and a global queue of tasks?
The more I've been thinking about this, I've wondered if it would be possible to eliminate the abstraction of threads completely, and describe all code as a series of tasks. Most programs are event based, so tasks will be spawned when events occur, and that is how programs will execute code. Starting a program can be considered an event, and so the initialisation logic runs as a task. A timer firing x times a second in a real time application can be considered event which runs a task. You can describe everything worth using processor time as a task.
Tasks are also much more lightweight than threads - creating a task is as simple as adding a message to the end of a queue rather than creating a thread by allocating a page and setting up a stack and registers.
Each processor core essentially runs a loop:
Code: Select all
while(true) {
if(Task task = task_queue->get_next())
task.run();
else
__asm("hlt");
}
For such a system to work we can't have blocking tasks, which means that all IO has to be done asynchronously. I feel that Node.js has done a great job at bringing asynchronous IO mainstream (example.) In my system, readFile() spawns a task to read the file, and once the file is loaded, another task is spawned with the loaded file passed in as a parameter. There should be no reason a task should consume CPU processing time just idling and waiting.
We also have to handle long running tasks which could potentially make the system unresponsive. There are two reasons a task takes a long time to run: 1) A programming bug and we get stuck in a loop, or 2) A long running algorithm that isn't divided up into sufficiently fine grained sub tasks. It would be very easy to detect if a task is taking more than one time slice (set a flag every time the timer interrupt is called, clear it every time you start processing another task, and if the flag already set when you enter the interrupt timer you know the currently running task has taken more than one time slice), and I can think of two ways to handle this:
1. Simply kill the task. Tasks are supposed to be light weight and it forces good programming practice to increase the granularity of your tasks.
2. Turn the long running task into a thread and preemptively schedule it like a traditional thread.
There's also the matter of forcing developers to write concurrency-safe code by at least being aware that tasks may be executed concurrently. I don't think this is an unreasonable request - I'm making my own applications programming language, so if they're going to have to learn a new language to use my system, they may as well pick up good habits from the start by forcing them to write concurrent, asynchronous, event-based code. As long as I provide a language that makes it very natural to do this.
In my standard library I'll provide developers with, I think it'll be useful to provide some types to simplify their lives. Such as:
- A consecutive queue. This will be a queue that will have a handler that is called when an item is added to the queue, however only one copy of the handler will be executed at once in sequence, even though you can add items to the queue concurrently. This will make it possible to write algorithms that will handle events that may occur concurrently, but you only want to handle them one at a time.
- A barrier. A handler is called when the barrier reaches 0. Developers can use this when they want to process many items in parallel, but then want to run a piece of code once all items have finished executing.
Tasks can also be the basis of inter-process communication.
Very much like how a mouse event will create a task in your process to handle the event, you can also create a task to run in another process. This will be the primary means of inter-process communication. Every running process will have a list of handlers. This list of handlers will essentially be a list of functions and their parameters. The parameters to these functions will be in a binary format similar to a protocol buffer message.
In my language, I will have a special kind of interface that you can cast processes to, and all you can add to these interfaces are function calls which take a protocol buffer message as an argument. Then at run time, you can attempt to cast a process to an interface:
Code: Select all
IVideoDriver driver = get_process(_some_pid) as IVideoDriver;
if(driver != null)
driver.set_screen_resolution(SetResolutionParams(1024, 768));
Code: Select all
void setResolution(SetResolutionParams p) {
// task!
}
What are your thoughts?