If this is the case then why don't CPU schedulers try to keep single threads running on the CPU instead of context switching?
I've seen this for example encoding AAC audio. I have an 8-core system but the encoder is single-threaded but the Windows scheduler still spreads the process out over 8 CPUs. Wouldn't it be better to stick on 1 core causing cache hits to be higher?
- Your AAC encoder runs UN CPU #1.
- Your AAC encoder stalls on I/O.
- The scheduler picks some other thread to run on CPU #1.
- The I/O request completes.
- A third thread, running on CPU #2, blocks.
- Your AAC encoder is the first waiting thread.
Should the scheduler:
- run your AAC encoder on CPU #2?
- run your AAC encoder on CPU #1,
and move the program happily running there to #2?
- wait until CPU #1 becomes available before running your AAC encoder again?
Keep in mind that 'the program happily running there' could very well be my AAC encoder.
Variations include the case where, by the time your I/O completes, CPU's #1 and #3 are available, but #1 is asleep. Should the scheduler wake it, so that your thread can stay on the CPU?
Your AAC encoder may be the most important process alive for you, but how is the scheduler to know that?
(Running processes you deem important at a nice level might help, but I do not know enough about current schedulers to know about that)
"On client versions of Windows, threads run by default for 2 clock intervals; on server systems, by default, a thread runs for 12 clock intervals"
The windows scheduler also is aware of the GUI, and raises priority of threads handling the user interface. Some things the kernel and/or user mode code do:
"Threads that own windows receive an additional boost of 2 when they wake up because of windowing activity such as the arrival of window messages . The windowing system (Win32k .sys) applies this boost when it calls KeSetEvent to set an event used to wake up a GUI thread ."
"Client versions of Windows also include another pseudo-boosting mechanism that occurs during multimedia playback . Unlike the other priority boosts, which are applied directly by kernel code, multimedia playback boosts are actually managed by a user-mode service called the MultiMedia Class Scheduler Service (MMCSS), but they are not really boosts—the service merely sets new base priorities for the threads as needed"
There are too many workloads to consider and not enough methods to balance them all to make everyone happy. At least in Linux there were already quite a few major changes and tons of little tweaks, each tweak can improve one benchmark and cause another untested benchmark to fail.
Sounds like a good reason to delegate scheduling to user space. If one size doesn't fit all, then let user space programs choose what works best for them.
But scheduling "hinting" sure, like saying "ok, keep this thread to one processor only"
Still, some of these configs may cause some kind of 'denial of service' on the system if misused (like the 'nice' command), so they're usually limited.
Scheduling my processes could certainly be done by me(my user land). It certainly shouldn't let me schedule your processes, but it could be hierarchical with first or second level scheduling in the kernel with the exact process run determined by local user space.
I've seen and used solutions of user-level threads (aka green threads, aka coroutines) to do just that. It works. It's a lot of work to get right even for a very specific use-case.
In the past the power management on Linux was done by a user-space program, I'm not sure why that was changed.
Userspace programs already can choose what very vague preferences they have, using the taskset (processor affinity), nice and ionice commands.
But the main problem is that workloads are very complex, and often changing. A single userspace program is not even aware of other programs running on the machine, nor how the user thinks they should be prioritised.
If you are compiling something, do you want to to finish ASAP or a bit slower in the background without desktop sluggishness? What priority should a minimised browser window have at the same time? What if that browser window is also playing music from youtube?
At the moment, the scheduling hints that users can figure out is marking some processes as low-priority background tasks. Optimal scheduler tuning is too complex, because starting or quitting any application can completely change the optimal resource usage, and users only have a vague idea of what they expect from the scheduler ("everything should be fast").
This is good for some applications but in be general case it doesn't solve the problem since the user processes can choose policies that interfere with each other and lead to overall lower performance. This is a fascinating topic where computer architecture meets algorithms meets game theory.
> If this is the case then why don't CPU schedulers try to keep single threads running on the CPU instead of context switching?
The scheduler in the kernel does do this if possible. In order to maximize the chances of a process waking up to warm caches, the scheduler always attempt to wake up the process in the core that was most recently running it. If that core is not available then it tries another core on the same package before it tries other packages (if there are many cpu packages).
However, the kernel has other real world priorities than just trying to keep a single process throughput as high as
possible. It must also be fair to the other processes while keeping the current consumption low and as many cpu cores powered off as possible.
Because the kernel has to work with different workloads ranging from low-end not-so-smart phones with a battery to a supercomputer with it's own nuclear power plant, there are compromises to be made. There's also a lot of compile time and runtime configuration options you can use to tweak the kernel to your particular workload.
This is the Completely Fair Scheduler (CFS) that was introduced in the 2.6 Kernel. It basically does round-robin scheduling with variable time quanta based on niceness/priority. Here is a good overview of the RBTree implementation it uses:
I don't know how this deals with distributing tasks across multiple processors however; the basic idea was to improve on the fairly naive runqueue implementation in 2.4 and prior.
The kernel will try to keep each process running on the same CPU. If one process is using a lot of CPU, it won't (shouldn't) generally switch it around just to keep the CPUs evenly busy.
I've seen this for example encoding AAC audio. I have an 8-core system but the encoder is single-threaded but the Windows scheduler still spreads the process out over 8 CPUs. Wouldn't it be better to stick on 1 core causing cache hits to be higher?