Motivation
As a part of our college's OS course activity, we had to study the scheduler using in an OS, and create an info-graphic on them.
My group focused on XNU scheduler.
This article contains what all I learnt about the XNU Scheduler.
XNU is Not Unix.
Introduction to QoS
XNU implements QoS - Quality of Service.
In windows, the processes have to define a numerical priority level, and then the kernel gives them processor based on that.
MacOS takes that a step further.
In MacOS, the threads self-label themself with a QoS class. Basically, the threads label themself according to their intent. And the kernel gives the thread priority based on that class.
This is called intent based scheduling.
Based on this, the priorities are mapped. There are 0-127 priority bands.
EDF mentioned in the above diagram means Earliest Deadline first. This is the algorithm that handles tasks on the Deadline based real time band.
Imagine you're watching a movie on your PC. You want it to have smooth frames, no glitches, and minimal buffering. This means that the OS should guarantee that real time tasks should be smooth and with minimal to none lag.
Apple Silicon and XNU scheduler
The XNU Scheduler is specifically tailored for Apple Silicon hardware. It is optimized to seamlessly work for Apple Silicon. Unlike other OS like Windows or Linux, which are designed to be work on multiple devices, Apple's approach of tailoring it to just their own hardware does make a difference.
Since it was designed alongside Apple hardware, it can utilize the hardware efficiently and optmize it very well.
In 2020, Apple Silicon introduced P cores and E cores into their chips.
These are mostly used to maximize performance and battery optimization.
This is the idea-
P cores are fast, but use more power. So, high QoS tasks go here
E cores are slower, but use lesser power. So, low QoS or tasks where speed isnt important can come here.
XNU Scheduler manages these cores, efficiently distributing tasks amongst them, and maximizing speed while saving power.
Adaptive Time slicing
XNU scheduler implements Dynamic time Quantas.
In case of an interactive thread, which deals with real time managing, the slice is small.
For a CPU-bound thread, which benefits from longer uninterrupted execution, a larger slice is given.
When the system is under load, the time quantas may be shrunk to ensure performance real time.
Thus, MacOS shrinks or grows slices based on system load and thread behavior.
Time Coalescing
MacOS groups threads with similar wake up timings, and wakes them up at 1 time instead of 10 different times.
For example, you have 5 thread with timings - 101, 99, 97, 103, 110 (ms)
MacOS would group them and wake them up together at 100ms.
That's the idea.
Quick info on CFS Scheduler
The completely fair Scheduler that was used in Linux primarily focuses on ensuring that the CPU time for each task is "fair".
A high priority task should get more CPU than a low priority task.
Note: Linux uses the EEVDF Scheduler now, adopted in Linux 6.6. I still need to read about it. I'll post a separate article about it later.
The CFS scheduler schedules on basis of vruntime value for each process.
This value is calculated using
the weight of the process is calculated using the nice value.
The nice value assigns priority to the process. It ranges is from -20 to +19, with -20 having highest priority.
Δexec is the actual real time the process ran (in nanoseconds) on the CPU.
Mini Experiment
I wanted to observe QoS in real time, to understand the philosophy of it, and connect with it better.
So, I decided to observe the outcome of a labelled process using nice values in linux
This command creates 5 processes - with different nice values all executing a bash script with an endless while loop. The display name is set according to the QoS class the thread correlates to.
| QoS class | nice value |
|---|---|
| QOS_USER_INTERACTIVE | -19 |
| QOS_USER_INITIATED | -10 |
| QOS_DEFAULT | 0 |
| QOS_UTILITY | 10 |
| QOS_BACKGROUND | 19 |
this means that a user interactive class should get more CPU time - since it has greater priority than a backgrount task.
nice -n -19 bash -c 'exec -a QOS_USER_INTERACTIVE bash -c "while true; do :; done"' &
nice -n -10 bash -c 'exec -a QOS_USER_INITIATED bash -c "while true; do :; done"' &
nice -n 0 bash -c 'exec -a QOS_DEFAULT bash -c "while true; do :; done"' &
nice -n 10 bash -c 'exec -a QOS_UTILITY bash -c "while true; do :; done"' &
nice -n 19 bash -c 'exec -a QOS_BACKGROUND bash -c "while true; do :; done"' &
and then we give it some stress ✨
stress-ng --cpu 8 --timeout 60s
and then I monitored them using htop
the result was as i expected!
user interactive and user initiated process get higher cpu% throughout the experiment. the background and utility process get the least cpu time.
I have sorted the list according to the CPU%, to increase visibility.
now. i know this "experiment" isn't really doing anything, honestly. i'd basically created 5 processes assigned them a name and priority similar to how the different QoS classes.
however, doing this mini experiment was fun, and gave me an idea of how it works.
After learning all this, I was super excited and wanted to immediately work on a mini project - creating a simulation of the xnu scheduler within linux environment.
XNU's source is on GitHub (apple/darwin-xnu) but replicating its behavior meaningfully requires the hardware it was designed around.
Now i am not completely sure of this project scope, nor how exactly I want to do this... but designing a custom kernel seems fun. plus, getting to study the different scheduling strategies used by linux, windows and mac is a fun idea. I would like to understand linux's design decisions behind the eevdf scheduler, and read the code too.
Author's note
These notes were actually created way back in April. They needed just slight editing before they were ready to post, however exams came and so did the slump. :') So, I couldn't post.
College started :')
I did manage to do a lot of random fun stuff during my vacation, I'll post about it soon :)
Extra
I had notebooklm generate a small infographic on this topic. It's the cutest thing ever, plus, it also explains each part so beautifully, I'm so in love with this poster. It's adorable.
I just had to add this.
Top comments (0)