10 ms·

How long does it take to make a context switch? (2010)

87 points by majke 10y ago

otabdeveloper1 10y ago
> Applications that create too many threads that are constantly fighting for CPU time (such as Apache's HTTPd or many Java applications) can waste considerable amounts of CPU cycles just to switch back and forth between different threads. Completely wrong. Context switches happen at a set interval in the kernel. Creating more threads won't make context switches happen more frequently, each thread will just get a proportionally smaller share of CPU time. Conceptually, the CPU scheduler can be thought of as a LIFO queue. An interrupt fires at a fixed interval of time and switches to the first ready thread (or process) on the queue. What's more important is the fact that this queue is exactly equivalent to how 'asynchronous' operations are implemented in the kernel. The only difference between creating threads and using async primitives is the thread prioritization algorithm. With threads you're using whatever scheduling heuristics are baked into the kernel, while with async you can roll your own. (And pay the penalty of doing this in usermode.)
- jandrewrogers 10y ago
  This isn't really correct. In many (most?) multithreaded applications a thread will regularly yield, forcing a context switch, long before its kernel time slice expires. In modern systems it is not difficult to have a case where the time spent doing work is less than the time spent yielding to another thread i.e. almost all of the CPU time is spent context switching. This is in significant part a side effect of CPUs becoming much faster. You need to increase the amount of code that is run between potential thread yield points to offset the overhead of a yield or it can generate context switch storms (i.e. almost all time is spent context switching) and throughput will suffer. Modern server architectures take this to its logical conclusion and try to eliminate virtually all context switching, hence the rising prevalence of "process-per-core" software designs.
- wzdd 10y ago
  > Creating more threads won't make context switches happen more frequently This is generally wrong in practice, but for a slightly subtle reason. 1. You can force a context (or thread) switch whenever you like by performing a blocking operation: calling read() for example, or by waiting on a mutex (as this person was doing). There's no more work to be done until the blocking operation completes, so the kernel finds another process (or thread) to run on the now-spare hardware thread. 2. Applications which create a lot of threads or processes tend to use them as IO workers. 3. The IO worker pattern is to block on read(), do some processing, maybe write(), and then go back to blocking. This means that most of the time the worker thread won't be using its complete timeslice. 4. If lots of IO worker threads are continually doing this, you will get a lot of thread switching (or context switching for processes). 5. Thread switching is fast in Linux, but it's slower than a simple syscall, which is what you'd be doing with an async solution.
  - otabdeveloper 10y ago
    Re: your point 1 -- waiting on a mutex happens regardless of whether you're using blocking or non-blocking IO. If your program only ever makes IO system calls and nothing else, then your point might make sense, but this isn't a realistic real-world assumption. Re: your point 3 -- not using the complete timeslice is not a realistic assumption. If you're creating threads then you're presumably doing some little bit of CPU-intensive work and not just copying bytes from one file descriptor to another. You're making terribly silly assumptions about what kind of work servers actually do, and ignoring the real benefit of async solutions. The real benefit is being able to control how threads switch by yourself instead of using the kernel's builtin 'black box' scheduling algorithms. The problem with the 'black box' is that the kernel might decide to penalize your threads for inscrutable reasons of 'fairness' and then you suddenly get inexplicable latency spikes. Of course rolling your own scheduling is an engineering boondoggle and most people just opt for a very primitive round-robin solution. (Which, incidentally, is what you want anyways if you want good latency.) In which case you might as well create a bunch of threads and schedule them as 'real-time' (SCHED_RR in Linux) and get the same result. (Seriously, try it -- benchmark an async server vs a SCHED_RR sync server and see for yourself.)
- chrisseaton 10y ago
  Does the CPU interrupt threads running happily on cores even when there are no other threads which want to run or which have affinity that would allow them to run on that core? But creating more threads will cause each to run slower as their caches are ruined by each context switch aren't they?
  - otabdeveloper 10y ago
    > Does the CPU interrupt threads running happily on cores even when there are no other threads which want to run or which have affinity that would allow them to run on that core? Yes. Even if you are careful to ever run only one process (so: no monitoring, no logging, no VM's, no 'middleware', etc.) and limit the number of threads to strictly equal the number of processors, you still have background kernel threads that force your process to context switch.
    - gpderetta 10y ago
      Tough you can instruct the kernel not to run anything (not even interrupt handlers) on specific cores, except for manually pinned processes.
      - monocasa 10y ago
        At a minimum you still need timer and TLB IPI shootdown interrupts hitting every core, just to have a working SMP system.
        gpderetta 10y ago
        the cpu does need to handle IPI of course but not sure about timers.
  - marcosdumay 10y ago
    Yes, it does interrupt them, but if the kernel decides to keep the same thread there's no context switch. (In other words, there's a penalty, but it is much smaller.) Your conclusion is correct. By creating more CPU hungry threads than you have CPUs you will reduce the total throughput of the computer.
- jabl 10y ago
  No, you're wrong. Or, you're correct as far as you have a bunch of threads doing only CPU-bound work (and even in that case having fewer threads can be useful due to cache effects). But if you have threads that block, then there will be more context switches. Consider something like apache httpd: Worker thread/process A writes to a socket, then the socket buffer fills up before the data has been sent over the network, the process blocks and goes to sleep (before it has used its time quantum and is preempted). CPU scheduler switches to apache worker thread B. B writes to its socket, socket buffer fills, B goes to sleep causing yet another context switch to apache worker C, etc. etc. See? Lots of context switches. Compare this to something like nginx: Worker process A writes to socket A1, socket A1 buffer fills up (errno EAGAIN, but no context switch), A switches to writing to socket A2, etc. Or for that matter consider a multithreaded process that manipulates some shared state. Thread A takes a lock X, and then the scheduler interrupt fires and the CPU scheduler decides to put A to sleep and switch to B. Well, B works for a little while, then tries to acquire lock X which is locked, and thus goes to sleep. CPU scheduler wakes up thread C, which works for a little while, then tries to acquire lock X. Oops, X is locked, so C goes to sleep and the scheduler wakes up thread D. Etc. etc. Again, lots of context switches.
- jsolson 10y ago
  You are incorrect. If you have many threads each doing small amounts of work before blocking, the kernel will happily switch in another runnable thread when the current thread blocks. This is common in workloads that service network IO using a 1:1 thread:client model. It can absolutely be more efficient to retire work for multiple clients from a single thread. Your last paragraph ignores this. It also forgets that in addition to prioritization there is multi-core load balancing to deal with. That can leave runnable threads stranded for whatever the LB interval is (which is independent of the overall scheduler quantum), while a concurrent service queue would allow steady service of all clients from all workers (that said, I actually prefer the siloed model in most cases).
mashmac2 10y ago
Context switch in this article = within a computer and processor, not about psychology
- chrisseaton 10y ago
  Well this is a computer technology new aggregator isn't it? Not a psychology one.
  - OJFord 10y ago
    To be fair, we do frequently talk about 'context switching' in a metaphorical sense of flitting between programming and conversations/meetings, or among different projects. If anything, I think I agree with GP that it's more unusual to see the term used in the 'real' (not metaphorical) sense on the front page.
    - deleted 10y ago
      [deleted]
- TazeTSchnitzel 10y ago
  Humans are several orders of magnitude slower.
luckydude 10y ago
Pretty sure that he's just rediscovering what I did in lmbench back in the early 1990's. All written up and open source (and got best paper in the 1995 Usenix): http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf Edit: which now that I think about it, was over 20 years ago. Reminds me of something a friend (Ron Minnich) said long ago: people rediscover stuff in computer science over and over, nobody wants to read old papers. Or something like that. He said it better, I think it was something like "want to look smart? Just take any 5 year old paper and redo whatever it did, our attention span seems to be very short."
- digi_owl 10y ago
  Everything old is new again it seems. I guess this is a variant of CADT, based on ignorance of the past rather than a chase of shinies.
  - cuspycode 10y ago
    People have always obsessed over "news", since humans are information-hungry by nature. But the modern tech crowd seems to have forgotten that there are two kinds of news: the kind that is objectively new (i.e. recent data), and the kind that is subjectively new (i.e. I didn't know that before). I think the situation is a bit similar to the distinction between objectively established frequencies and subjective Bayesian priors.
- chillydawg 10y ago
  One reason people are reluctant to trust old sources (regardless of how well received they were at the time) is that software, operating systems and hardware all move at lightning pace. I've not read your paper, but I'm willing to bet enough has changed to warrant a new writeup talking about modern systems.
  - luckydude 10y ago
    I very much doubt it. If you read the paper, it took each of the things it could measure (memory, disk, network, etc) and measured bandwidth and latency. Those are pretty basic measurements and I suspect that they will still be interesting 100 years from now and measured in the same way. I'm running the benchmark right now on a modern system just to see what it says. Yep, still works fine: "size=0k ovr=0.90 2 7.63 4 6.51 8 7.78 16 7.07 24 7.78 32 9.02 64 10.35 96 10.49 That says that a hot potato (I send a byte to you, you send it back to me, the time is the round trip for one pair) context switch is ~7 usecs. Do it in a ring with 96 processes and it goes up to ~10 usecs. I think almost 100% of that benchmark is still valid (I say almost because there must be something that has bit rotted in 20+ years but I don't know of anything). It's worth a read. Edit: formatting.
JoeAltmaier 10y ago
On the order of a millisecond. Which seems to me, way too slow in this day and age. The context switch has been a hard wad that chokes algorithms in unexpected ways, that are hard to diagnose. This can be fixed with a different approach to CPU design? Most threads block on a semaphore-thingy or a timer or wait for io completion. If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?) How could this work? Maybe a global semaphore register where you Wait on a mask. Each bit could be mapped to one of those wait-condition. Another opcode would Set the bit. To scale, the CPU would have to have not 2 or 4 hyperthreads but maybe 1000. So every thread in the system could be 'hot-staged' in a Wait, ready to execute, or executing. There would still be cache and tlb issues, but they would be at the same level as any library call. They wouldn't include yards of kernel code messing with stacks and register loads and so on.
- luckydude 10y ago
  Hey, same Joe from Sun? If so, howdy. On my i7-5930K I'm seeing 7-10 usecs, quite a bit better than a millisecond. Linus cares about this stuff, I'd be very surprised if he didn't measure it regularly.
  - JoeAltmaier 10y ago
    Probably thinking of my brother, Rich? usecs are a thousand times better than a ms of course. And a ns is a thousand times better than that!
- j_s 10y ago
  Cue the comment from the 10+ year old vaporware Mill architecture's team... :)
- belovedeagle 10y ago
  > If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?) Uh, how do you think the kernel does it? Of course there's a CPU instruction for it - at least in modern ISAs like AArch64, but I can only assume it must have been tacked onto x86 too somehow or another. One reason that it's implemented in the kernel is to interact well with the scheduler: it's all well and good for a user space process to spinlock (with some kind of enter-low-power-state instruction), but it's going to be spinning until the timer comes around and kicks it back to the kernel anyways unless the other side of the lock just happens to be scheduled on a different core simultaneously. Even worse, if a thread is holding a spinlock and it gets unscheduled, now everyone else who wants to acquire that lock will waste their timeslices spinning away for nothing. The only way to avoid this would be for threads to be able to tell the OS "don't unschedule me" (much like the kernel masks interrupts during critical sections), but that would allow any such process to not only DOS the rest of the system, it could allow any such process to hang the system entirely. That's not to say it can't be done properly, but the easy and perhaps even correct way to do it is OS-managed semaphores. > not 2 or 4 hyperthreads but maybe 1000. So every thread in the system could be 'hot-staged' And of course this is what hyperthreads are, but where exactly do you plan on putting 1MB of architectural state while you're not using it? You're lucky if you have an L2 that big, but let's think... moving architectural state to the L2, that sounds a lot like... yes, correct! OS threads! If we want to rescue your suggestion back into the realm of feasibility, what you're saying is we should implement the OS (with features like scheduler-aware semaphores and thousands of ready threads) in hardware to make things like moving 1MB of architectural state to and from an L2 cheaper (and that we should have larger L2s so it's not incredibly wasteful to use 1MB on architectural state of non-executing threads). There's a reason we implement OSes in software, though, even with all the associated costs.
bogomipz 10y ago
The author states: >"In practice context switching is expensive because it screws up the CPU caches (L1, L2, L3 if you have one, and the TLB – don't forget the TLB!)." How does a context switch "screw up" the L1 through L3 caches? Yes when there is context switch the TLB gets flushed and the kernel then needs to "walk" the page tables which is expensive and yes I can see the L1 needing to flush some lines but is that really screwing up the L1, L2 and L3 caches, the later two being fairly large these days?
- JoeAltmaier 10y ago
  Its understood that different threads, especially in different processes, will quickly rewrite the caches to suit their own needs. Returning to a thread, especially after any additional delay, threads will find their own data essentially gone. Its always going to create better cache utility if a thread can run to completion before a switch.
- gpderetta 10y ago
  The biggest cache trashing on a thread switch are possibly the lines containing the thread stack which are very unlikely to be shared between threads. Also thread are likely to be working on distinct data. BTW, TLB doesn't need to be flushed on a thread switch, only on a process switch, and even then more modern systems can tag TLB entries by process id, reducing the need for flushing.
  - bogomipz 10y ago
    I should have specified I was talking about a process context switch not a thread. >"The biggest cache trashing on a thread switch are possibly the lines containing the thread stack which are very unlikely to be shared between threads. Also thread are likely to be working on distinct data." Sure, I don't think they are every shared are they? >"BTW, TLB doesn't need to be flushed on a thread switch, only on a process switch, and even then more modern systems can tag TLB entries by process id," Indeed and this often gets left out of the discussion, its not mentioned in the blog post certainly. I believe on x86-64 this is called ASID and on ARM chips its TPID.
bogomipz 10y ago
The author also seems to be loose with specifying "context switches" where there is a difference between a context switch between two threads which shares everything except a stack and a context switch between two processes that have separate address spaces. Did anyone else find that odd?
- mfukar 10y ago
  Context: Linux.
  - nkurz 10y ago
    Could you expand your response? I presume you are saying that since in Linux processes and threads are "the same" there is no need to distinguish whether the process being switched in shares the same address space. Does this mean that there is a missed optimization on Linux to preserve some virtually-addressed caches and tables when switching to thread/process that shares the same address space? Or that the terminology is correct, but that Linux already makes the possible optimization?
    - mfukar 10y ago
      > I presume you are saying that since in Linux processes and threads are "the same" there is no need to distinguish whether the process being switched in shares the same address space. That's right. Threads share everything but their stack. > Does this mean that there is a missed optimization on Linux to preserve some virtually-addressed caches and tables when switching to thread/process that shares the same address space? I'm not entirely sure I understand your question. What scenario do you have in mind?
    - bogomipz 10y ago
      Its just a smart ass comment with no real value. Yes the Linux scheduler doesn't differentiate between threads and processes(see NPTL vs LWP) However I was pointing out that although the kernels just schedules "tasks" instead of threads and processes it is far more efficient to schedule threads than processes on some processors - example pre-ARMv6 didn't use address space tags on its TLB so a context switch to a different process required the whole whole TLB to be flushed which means the kernel will need to walk the page table to get the translations for the physical pages for the newly scheduled process.

87 points by majke 10y ago

> Applications that create too many threads that are constantly fighting for CPU time (such as Apache's HTTPd or many Java applications) can waste considerable amounts of CPU cycles just to switch back and forth between different threads. Completely wrong. Context switches happen at a set interval in the kernel. Creating more threads won't make context switches happen more frequently, each thread will just get a proportionally smaller share of CPU time. Conceptually, the CPU scheduler can be thought of as a LIFO queue. An interrupt fires at a fixed interval of time and switches to the first ready thread (or process) on the queue. What's more important is the fact that this queue is exactly equivalent to how 'asynchronous' operations are implemented in the kernel. The only difference between creating threads and using async primitives is the thread prioritization algorithm. With threads you're using whatever scheduling heuristics are baked into the kernel, while with async you can roll your own. (And pay the penalty of doing this in usermode.)

jandrewrogers 10y ago
This isn't really correct. In many (most?) multithreaded applications a thread will regularly yield, forcing a context switch, long before its kernel time slice expires. In modern systems it is not difficult to have a case where the time spent doing work is less than the time spent yielding to another thread i.e. almost all of the CPU time is spent context switching. This is in significant part a side effect of CPUs becoming much faster. You need to increase the amount of code that is run between potential thread yield points to offset the overhead of a yield or it can generate context switch storms (i.e. almost all time is spent context switching) and throughput will suffer. Modern server architectures take this to its logical conclusion and try to eliminate virtually all context switching, hence the rising prevalence of "process-per-core" software designs.
wzdd 10y ago
> Creating more threads won't make context switches happen more frequently This is generally wrong in practice, but for a slightly subtle reason. 1. You can force a context (or thread) switch whenever you like by performing a blocking operation: calling read() for example, or by waiting on a mutex (as this person was doing). There's no more work to be done until the blocking operation completes, so the kernel finds another process (or thread) to run on the now-spare hardware thread. 2. Applications which create a lot of threads or processes tend to use them as IO workers. 3. The IO worker pattern is to block on read(), do some processing, maybe write(), and then go back to blocking. This means that most of the time the worker thread won't be using its complete timeslice. 4. If lots of IO worker threads are continually doing this, you will get a lot of thread switching (or context switching for processes). 5. Thread switching is fast in Linux, but it's slower than a simple syscall, which is what you'd be doing with an async solution.
- otabdeveloper 10y ago
  Re: your point 1 -- waiting on a mutex happens regardless of whether you're using blocking or non-blocking IO. If your program only ever makes IO system calls and nothing else, then your point might make sense, but this isn't a realistic real-world assumption. Re: your point 3 -- not using the complete timeslice is not a realistic assumption. If you're creating threads then you're presumably doing some little bit of CPU-intensive work and not just copying bytes from one file descriptor to another. You're making terribly silly assumptions about what kind of work servers actually do, and ignoring the real benefit of async solutions. The real benefit is being able to control how threads switch by yourself instead of using the kernel's builtin 'black box' scheduling algorithms. The problem with the 'black box' is that the kernel might decide to penalize your threads for inscrutable reasons of 'fairness' and then you suddenly get inexplicable latency spikes. Of course rolling your own scheduling is an engineering boondoggle and most people just opt for a very primitive round-robin solution. (Which, incidentally, is what you want anyways if you want good latency.) In which case you might as well create a bunch of threads and schedule them as 'real-time' (SCHED_RR in Linux) and get the same result. (Seriously, try it -- benchmark an async server vs a SCHED_RR sync server and see for yourself.)
chrisseaton 10y ago
Does the CPU interrupt threads running happily on cores even when there are no other threads which want to run or which have affinity that would allow them to run on that core? But creating more threads will cause each to run slower as their caches are ruined by each context switch aren't they?
- otabdeveloper 10y ago
  > Does the CPU interrupt threads running happily on cores even when there are no other threads which want to run or which have affinity that would allow them to run on that core? Yes. Even if you are careful to ever run only one process (so: no monitoring, no logging, no VM's, no 'middleware', etc.) and limit the number of threads to strictly equal the number of processors, you still have background kernel threads that force your process to context switch.
  - gpderetta 10y ago
    Tough you can instruct the kernel not to run anything (not even interrupt handlers) on specific cores, except for manually pinned processes.
    - monocasa 10y ago
      At a minimum you still need timer and TLB IPI shootdown interrupts hitting every core, just to have a working SMP system.
      - gpderetta 10y ago
        the cpu does need to handle IPI of course but not sure about timers.
- marcosdumay 10y ago
  Yes, it does interrupt them, but if the kernel decides to keep the same thread there's no context switch. (In other words, there's a penalty, but it is much smaller.) Your conclusion is correct. By creating more CPU hungry threads than you have CPUs you will reduce the total throughput of the computer.
jabl 10y ago
No, you're wrong. Or, you're correct as far as you have a bunch of threads doing only CPU-bound work (and even in that case having fewer threads can be useful due to cache effects). But if you have threads that block, then there will be more context switches. Consider something like apache httpd: Worker thread/process A writes to a socket, then the socket buffer fills up before the data has been sent over the network, the process blocks and goes to sleep (before it has used its time quantum and is preempted). CPU scheduler switches to apache worker thread B. B writes to its socket, socket buffer fills, B goes to sleep causing yet another context switch to apache worker C, etc. etc. See? Lots of context switches. Compare this to something like nginx: Worker process A writes to socket A1, socket A1 buffer fills up (errno EAGAIN, but no context switch), A switches to writing to socket A2, etc. Or for that matter consider a multithreaded process that manipulates some shared state. Thread A takes a lock X, and then the scheduler interrupt fires and the CPU scheduler decides to put A to sleep and switch to B. Well, B works for a little while, then tries to acquire lock X which is locked, and thus goes to sleep. CPU scheduler wakes up thread C, which works for a little while, then tries to acquire lock X. Oops, X is locked, so C goes to sleep and the scheduler wakes up thread D. Etc. etc. Again, lots of context switches.
jsolson 10y ago
You are incorrect. If you have many threads each doing small amounts of work before blocking, the kernel will happily switch in another runnable thread when the current thread blocks. This is common in workloads that service network IO using a 1:1 thread:client model. It can absolutely be more efficient to retire work for multiple clients from a single thread. Your last paragraph ignores this. It also forgets that in addition to prioritization there is multi-core load balancing to deal with. That can leave runnable threads stranded for whatever the LB interval is (which is independent of the overall scheduler quantum), while a concurrent service queue would allow steady service of all clients from all workers (that said, I actually prefer the siloed model in most cases).

mashmac2 10y ago

Context switch in this article = within a computer and processor, not about psychology

chrisseaton 10y ago
Well this is a computer technology new aggregator isn't it? Not a psychology one.
- OJFord 10y ago
  To be fair, we do frequently talk about 'context switching' in a metaphorical sense of flitting between programming and conversations/meetings, or among different projects. If anything, I think I agree with GP that it's more unusual to see the term used in the 'real' (not metaphorical) sense on the front page.
  - deleted 10y ago
    [deleted]
TazeTSchnitzel 10y ago
Humans are several orders of magnitude slower.

luckydude 10y ago

Pretty sure that he's just rediscovering what I did in lmbench back in the early 1990's. All written up and open source (and got best paper in the 1995 Usenix): http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf Edit: which now that I think about it, was over 20 years ago. Reminds me of something a friend (Ron Minnich) said long ago: people rediscover stuff in computer science over and over, nobody wants to read old papers. Or something like that. He said it better, I think it was something like "want to look smart? Just take any 5 year old paper and redo whatever it did, our attention span seems to be very short."

digi_owl 10y ago
Everything old is new again it seems. I guess this is a variant of CADT, based on ignorance of the past rather than a chase of shinies.
- cuspycode 10y ago
  People have always obsessed over "news", since humans are information-hungry by nature. But the modern tech crowd seems to have forgotten that there are two kinds of news: the kind that is objectively new (i.e. recent data), and the kind that is subjectively new (i.e. I didn't know that before). I think the situation is a bit similar to the distinction between objectively established frequencies and subjective Bayesian priors.
chillydawg 10y ago
One reason people are reluctant to trust old sources (regardless of how well received they were at the time) is that software, operating systems and hardware all move at lightning pace. I've not read your paper, but I'm willing to bet enough has changed to warrant a new writeup talking about modern systems.
- luckydude 10y ago
  I very much doubt it. If you read the paper, it took each of the things it could measure (memory, disk, network, etc) and measured bandwidth and latency. Those are pretty basic measurements and I suspect that they will still be interesting 100 years from now and measured in the same way. I'm running the benchmark right now on a modern system just to see what it says. Yep, still works fine: "size=0k ovr=0.90 2 7.63 4 6.51 8 7.78 16 7.07 24 7.78 32 9.02 64 10.35 96 10.49 That says that a hot potato (I send a byte to you, you send it back to me, the time is the round trip for one pair) context switch is ~7 usecs. Do it in a ring with 96 processes and it goes up to ~10 usecs. I think almost 100% of that benchmark is still valid (I say almost because there must be something that has bit rotted in 20+ years but I don't know of anything). It's worth a read. Edit: formatting.

JoeAltmaier 10y ago

On the order of a millisecond. Which seems to me, way too slow in this day and age. The context switch has been a hard wad that chokes algorithms in unexpected ways, that are hard to diagnose. This can be fixed with a different approach to CPU design? Most threads block on a semaphore-thingy or a timer or wait for io completion. If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?) How could this work? Maybe a global semaphore register where you Wait on a mask. Each bit could be mapped to one of those wait-condition. Another opcode would Set the bit. To scale, the CPU would have to have not 2 or 4 hyperthreads but maybe 1000. So every thread in the system could be 'hot-staged' in a Wait, ready to execute, or executing. There would still be cache and tlb issues, but they would be at the same level as any library call. They wouldn't include yards of kernel code messing with stacks and register loads and so on.

luckydude 10y ago
Hey, same Joe from Sun? If so, howdy. On my i7-5930K I'm seeing 7-10 usecs, quite a bit better than a millisecond. Linus cares about this stuff, I'd be very surprised if he didn't measure it regularly.
- JoeAltmaier 10y ago
  Probably thinking of my brother, Rich? usecs are a thousand times better than a ms of course. And a ns is a thousand times better than that!
j_s 10y ago
Cue the comment from the 10+ year old vaporware Mill architecture's team... :)
belovedeagle 10y ago
> If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?) Uh, how do you think the kernel does it? Of course there's a CPU instruction for it - at least in modern ISAs like AArch64, but I can only assume it must have been tacked onto x86 too somehow or another. One reason that it's implemented in the kernel is to interact well with the scheduler: it's all well and good for a user space process to spinlock (with some kind of enter-low-power-state instruction), but it's going to be spinning until the timer comes around and kicks it back to the kernel anyways unless the other side of the lock just happens to be scheduled on a different core simultaneously. Even worse, if a thread is holding a spinlock and it gets unscheduled, now everyone else who wants to acquire that lock will waste their timeslices spinning away for nothing. The only way to avoid this would be for threads to be able to tell the OS "don't unschedule me" (much like the kernel masks interrupts during critical sections), but that would allow any such process to not only DOS the rest of the system, it could allow any such process to hang the system entirely. That's not to say it can't be done properly, but the easy and perhaps even correct way to do it is OS-managed semaphores. > not 2 or 4 hyperthreads but maybe 1000. So every thread in the system could be 'hot-staged' And of course this is what hyperthreads are, but where exactly do you plan on putting 1MB of architectural state while you're not using it? You're lucky if you have an L2 that big, but let's think... moving architectural state to the L2, that sounds a lot like... yes, correct! OS threads! If we want to rescue your suggestion back into the realm of feasibility, what you're saying is we should implement the OS (with features like scheduler-aware semaphores and thousands of ready threads) in hardware to make things like moving 1MB of architectural state to and from an L2 cheaper (and that we should have larger L2s so it's not incredibly wasteful to use 1MB on architectural state of non-executing threads). There's a reason we implement OSes in software, though, even with all the associated costs.

bogomipz 10y ago

The author states: >"In practice context switching is expensive because it screws up the CPU caches (L1, L2, L3 if you have one, and the TLB – don't forget the TLB!)." How does a context switch "screw up" the L1 through L3 caches? Yes when there is context switch the TLB gets flushed and the kernel then needs to "walk" the page tables which is expensive and yes I can see the L1 needing to flush some lines but is that really screwing up the L1, L2 and L3 caches, the later two being fairly large these days?

JoeAltmaier 10y ago
Its understood that different threads, especially in different processes, will quickly rewrite the caches to suit their own needs. Returning to a thread, especially after any additional delay, threads will find their own data essentially gone. Its always going to create better cache utility if a thread can run to completion before a switch.
gpderetta 10y ago
The biggest cache trashing on a thread switch are possibly the lines containing the thread stack which are very unlikely to be shared between threads. Also thread are likely to be working on distinct data. BTW, TLB doesn't need to be flushed on a thread switch, only on a process switch, and even then more modern systems can tag TLB entries by process id, reducing the need for flushing.
- bogomipz 10y ago
  I should have specified I was talking about a process context switch not a thread. >"The biggest cache trashing on a thread switch are possibly the lines containing the thread stack which are very unlikely to be shared between threads. Also thread are likely to be working on distinct data." Sure, I don't think they are every shared are they? >"BTW, TLB doesn't need to be flushed on a thread switch, only on a process switch, and even then more modern systems can tag TLB entries by process id," Indeed and this often gets left out of the discussion, its not mentioned in the blog post certainly. I believe on x86-64 this is called ASID and on ARM chips its TPID.

bogomipz 10y ago

The author also seems to be loose with specifying "context switches" where there is a difference between a context switch between two threads which shares everything except a stack and a context switch between two processes that have separate address spaces. Did anyone else find that odd?

mfukar 10y ago
Context: Linux.
- nkurz 10y ago
  Could you expand your response? I presume you are saying that since in Linux processes and threads are "the same" there is no need to distinguish whether the process being switched in shares the same address space. Does this mean that there is a missed optimization on Linux to preserve some virtually-addressed caches and tables when switching to thread/process that shares the same address space? Or that the terminology is correct, but that Linux already makes the possible optimization?
  - mfukar 10y ago
    > I presume you are saying that since in Linux processes and threads are "the same" there is no need to distinguish whether the process being switched in shares the same address space. That's right. Threads share everything but their stack. > Does this mean that there is a missed optimization on Linux to preserve some virtually-addressed caches and tables when switching to thread/process that shares the same address space? I'm not entirely sure I understand your question. What scenario do you have in mind?
  - bogomipz 10y ago
    Its just a smart ass comment with no real value. Yes the Linux scheduler doesn't differentiate between threads and processes(see NPTL vs LWP) However I was pointing out that although the kernels just schedules "tasks" instead of threads and processes it is far more efficient to schedule threads than processes on some processors - example pre-ARMv6 didn't use address space tags on its TLB so a context switch to a different process required the whole whole TLB to be flushed which means the kernel will need to walk the page table to get the translations for the physical pages for the newly scheduled process.