Introduction
Cooperative concurrency has been gaining momentum in Web applications over the past decade. Node.js uses it. It's been impl...
For further actions, you may consider blocking this person and/or reporting abuse
A nice overview to the differences in multitasking. I'd like to add a few points though:
Thank you, yes, for eg NGINX runs a worker process per cpu core as you describe (nginx.com/blog/inside-nginx-how-we...). And as you point out, it does have to deal with blocking 3rd party dependencies, including the os (nginx.com/blog/thread-pools-boost-...).
Re thread switching, I looked at this article which seems to indicate it takes in the range of microseconds. What do you think?
blog.tsunanet.net/2010/11/how-long...
Microseconds sounds right. I wrote a context switcher in ARM in college, and know the switching itself tends to be pretty run of the mill as performance goes, just moving stuff between memory locations, so it's mostly memory bound. However, a context switch implies a scheduler run, and then you're additionally incurring scheduler run time on the CPU. The scheduler then has to access the data structure the kernel keeps to track schedulable entities (threads in Linux, I think).
Now, you're switching to a kernel context and filling the L1 with kernel memory, then run the scheduler, then switch to the new user context and filling the L1 with the new user memory.
Just thinking about it this way, you're easily going to hit microseconds on a typical context switch.
We need to be careful about what we're measuring and comparing. A "context switch" will happen anytime you make an OS call, this includes the IO functions I mentioned. There is definitely overhead in this alone, even if we don't get into scheduling.
For a thread switch there will be more overhead, as Zuodian mentions. On Linux, or any OS, I don't think the actual process selection takes much time (these aren't complex data structures). The switching of page/privilege tables possibly.
But, here's an important aspect. When you switch to a new thread you have different memory pointers and your caches, especially the L0/L1 levels may not have that data in memory. This causes new loads to be requested. This will also happen if you have green threads and switch in user space, since your cooperative "threads" also have different memory.
Without a concrete comparison of use-cases written in both approaches I still think it'd be hard to say whether the actual context/thread switch is a significant part of the problem.
That's a good point that we should compare apples to apples.
In a very rough way, it seems that the difference in performance between NGINX and Apache (with worker/event model) suggests that preemptive multitasking has enough overhead to make a significant difference. NGINX can handle at least twice the number of requests per second.
Why that happens is less clear to me. Is context switching a thread significantly slower than context switching in-process? Do both have the same effect on the CPU cache? If that doesn't make enough of a difference, maybe there's something else going on.
I think threads/processes are preempted in Linux something like every 1-10 milliseconds in CFS, so that's a fixed, guaranteed cost. I wonder if maybe the frequency of context switching is significantly lower with a cooperative approach, since we only context switch voluntarily, usually because of I/O. There wouldn't be any context switching at all between tasks while they're using the CPU. Could that be the difference?
This suggests that might be the case:
When you change from one user process to another, the virtual page table must change since each process has its own virtual address space. That's the main thing I can think of that makes in-process context switches faster.
You're right in a sense; a cooperative event loop avoids OS-managed context switches entirely by running all tasks in the same thread context. So the only time that event loop has to give up CPU time to the OS is when the OS preempt the entire event loop thread, or some task in the event loop performs a system call. It's a technicality, but Linux will still preempt the event loop periodically to run other user processes, handle interrupts, and run kernel threads. The event loop just keeps all the tasks that it owns from fragmenting into multiple user threads.
This is a good point, though I think in Linux at least, it only applies to actual process switching. That is, if we're switching between threads that are all running under the same process (as would be the case for Apache process running on a given core), I believe the memory isn't switched out the way it is when we switch from one process to another. I am not familiar with the details though, just that heap memory is generally shared, so I may be missing something.
I would encourage finding some reading material on operating systems if you're interested in this kind of stuff, I personally love it. Here is the one my OS professor wrote.
Oh and in that time, the kernel can run its own kernel threads as needed.
The reason context switches are slow isn't because of the amount of stuff the CPU has to do, it has a lot more to do with memory access. Each thread has its own stack space and registers saved in memory, and the system has to swap cache lines in L1, and most likely L2, cache on every context switch, hence the slowdowns. You can imagine how thread-specific memory access patterns can make that worse if one is not careful.
Very nice description :), I would like to add what I consider to be important factors in the choice of multi-tasking models: complexity and predictability.
Pre-emptive multi-tasking systems require the programmer to deal with shared state very carefully, ensuring consistency and avoiding deadlocks - we humans are not always very good at this, especially so in unfamiliar languages, and this complexity is likely to result in issues, then there is the fun of trying to debug a multi-threaded app - this is the old adage that 'threads are hard'.
In addition, pre-emptive systems are generally not predictable as to when the pre-emption will occur in an execution path, which can often be a problem when time critical work (eg: local hardware interaction) is taking place, leading to locked execution blocks, priority management and other strategies that increase complexity, defeat the pre-emption and reduce it's inherent safety mechanism.
Co-operative multi-tasking does not suffer from threaded-programming complexities, nor does it have unpredictable task interruptions - debugging is a relative joy, and execution hogs are likely to be easily detected at run time. It does introduce new ways of thinking about a program (ie: event driven), especially if the chosen language does not support keywords such as async/await, and typically requires more state to be managed than the procedural code used in a threaded design.
I feel both have their place: I wouldn't consider a co-operative OS where there are a significant number of applications, any of which could go wrong in unpredictable ways, but neither would I wish to debug the kernel; I have used a co-operative model in an environment where my team have full control of the code (a microcontroller in this case), needing minimal complexity to reduce the chance of human error and predictable execution. One can also apply this to an application within a process atop a pre-emptive OS, ie: the NGiNX example.
Thank you for your comments!
This is a good point. With some applications - certainly most Web apps - there is no real-time communication among threads. In that case it's luckily not an issue. There may be communication mediated by something like a database that all the threads can access, but those semantics are much simpler than the programmer having to deal with shared memory manually.
That's a cool example. Especially if there's only one physical CPU/core, the simplicity of doing an event loop makes sense to me. I suppose in the case of multiple cores, one could implement a message passing system between threads and continue using an event model, though having to implement that from scratch sounds like it could be a lot of work. Was the microcontroller code done in C? Or would you have to drop down all the way into assembly?
Good point on delegating thread synchronisation / communication to an existing trusted system (like a DB), although that still leaves room for pain (eventual consistency anyone?).
The MCU design was for a tiny 8-bit Freescale device on a satellite, so one core, little RAM (6k) and bare metal coding in C, with a couple of lines of ASM to issue the WAIT instruction. Also zero opportunity for code fixes once launched - we did 2 years of testing!
That's really cool! If you have a chance to write it up as an article at some point, I for one would love to read it!
I really should do that - although ITAR prevented us publishing the source code when we did the work (en.wikipedia.org/wiki/Internationa...) it might be ok now.. the joys of regulation!
Having done a few talks for radio hams I'll probably write that up as an article for the satellite team website (funcube.org.uk) and syndicate it here :)
I may be over my head but I think Nginx, HAProxy and other proxies don't implement cooperative concurrency, but a Thread Pool with a max number of workers in their config file. They don't have a scheduler or a context switching, but I may confuse things.
The other day I was reading this related article if anyone is interested eli.thegreenplace.net/2018/measuri... I stumble upon it because it has a Go test as a comparison.
I believe the core architecture in NGINX is the use of cooperative concurrency with an event loop. Each worker process (one per CPU core) implements the event loop based on nonblocking I/O.
nginx.com/blog/inside-nginx-how-we...
NGINX does have thread pools to deal with the problem of dependencies that are not non-blocking though.
nginx.com/blog/thread-pools-boost-...
Oh I see, so the event loop is inside each worker.
I haven't got that deep, I was only touching the subject was I was learning the Worker Pool pattern as I study Go and distributed systems.
So thanks a lot for the info!
PS: the urls are broken (leading ":")
Oops - links fixed!
I'll chime in to point to Erlang for curiosity.
Erlang's VM, BEAM, implements preemptive scheduling. It lives in a single OS process and spawns a scheduler (thread) per CPU core (default, but configurable) and the processes (not OS, but user-land) are fully preemptive and has non-blocking IO with dedicated schedulers.
Erlang achieves full preemption by having complete memory isolation in the process and handling all side-effects through messages. It's a pretty unique runtime compared to others like Go and Node.js and it results in a bunch of benefits such as high availability, fault-tolerance, high concurrency and non-blocking garbage collection.
Thanks @rhnonose ! I have a question:
How does this work? By 'processes' I think you are referring to the functions that do work inside of Erlang, kind of like coroutines in Python's asyncio, is that right? If so, how can they be preempted?
Update: I was curious enough to look into this, and how it works is kind of interesting:
happi.github.io/theBeamBook/#CH-Sc...
The Erlang VM runs an event loop that implements cooperative concurrency. In that respect it's conceptually very similar to how Node.js and NGINX work. However, every time we call a function in Erlang, the VM has the option to run a different task instead. That's the sense in which it is preemptive. I guess I'd call this this "pseudo-preemptive."
I'm not certain, but I suspect that from the point of view of performance, it is probably pretty close to cooperative concurrency, since context switching still happens within an OS thread, only at well defined switching points like function calls, and only if the VM thinks it's time to do so (via reduction counting). The overhead ought to be similar to what Node.js does when we call an
asyncfunction withawaitin JavaScript.What about tight loops? Well, since the only way to loop in Erlang is via recursion, that just doesn't apply. The one area where this can be a problem is with native code. If we call native code from Erlang, we have to be very careful with it, since it isn't bound by the same restrictions as the Erlang language and VM. A poorly written native module could in fact hang the VM.
I'd just like to add a subtlety to the horizontal scaling issue in server side.
On the server, concurrent event loops help you scale horizontally, and large applications never run a small number of event loops. So if one event loop crashes, the server application still chugs along running all the other event loops. If we go even bigger, each server instance then is hardened against other instances crashing. So in this sense, you're hardening bigger chunks of an application to random crashes since your application is also bigger.
It seems like the addendum here has a lot of answers. I’d think that the difference between a more CPU bound OS and the I/O bound Node etc. show pretty well why one might go extinct in one context and be adequate in another.
Unless I’m off with this logic?
I think that's a good point. In an OS, many applications (like Web browsers, word processors) are also I/O bound, but you're right, it's an important use-case to support applications that just want to use as much of the CPU as possible. So preemption makes a lot of sense from that perspective alone.
I think even in a world where all applications were I/O bound though, we'd still want the OS to be preemptive - the fragility of any single application being able to break everything just seems untenable.
Just learned from Andrew Clark that React's experimental Concurrent Mode is built on cooperative concurrency.
PepoG