Should each CPU's Local APIC timer interrupt at different phase?

[songziming]

I'm thinking about APIC timer interrupt on SMP hardware, is it worthy to make timer of each CPU fire at different time?

Let me explain, say we have 4 CPUs, and system clock rate is 1Hz, so:

• 0s 000ms, CPU 0 timer interrupt!

• 0s 250ms, CPU 1 timer interrupt!

• 0s 500ms, CPU 2 timer interrupt!

• 0s 750ms, CPU 3 timer interrupt!

• 1s 000ms, CPU 0 timer interrupt!

• 1s 250ms, CPU 1 timer interrupt!

• ...you get the idea

The benefit is: we need to perform task scheduling in timer ISR, and scheduler needs locking. If all CPU calls scheduler at same time we'd have lock contention and that hurts performance. Making timer ISR as far as possible is safer.

I think we can use an external reference clock source (like PIT or HPET) to setup. Set reference clock frequency at (sys_main_freq*cpu_count), like 4Hz in previous example, and broadcast this interrupt to all CPU (via IOAPIC). Start the reference clock, each CPU skips first X interrupt (where X is the CPU-index), and start its APIC timer. After the last CPU done, stop the reference clock, and resyncing finish.

What's your idea? Do you know any other OS have similar design?

[bellezzasolo]

I'm thinking about APIC timer interrupt on SMP hardware, is it worthy to make timer of each CPU fire at different time?

Let me explain, say we have 4 CPUs, and system clock rate is 1Hz, so:

• 0s 000ms, CPU 0 timer interrupt!

• 0s 250ms, CPU 1 timer interrupt!

• 0s 500ms, CPU 2 timer interrupt!

• 0s 750ms, CPU 3 timer interrupt!

• 1s 000ms, CPU 0 timer interrupt!

• 1s 250ms, CPU 1 timer interrupt!

• ...you get the idea

The benefit is: we need to perform task scheduling in timer ISR, and scheduler needs locking. If all CPU calls scheduler at same time we'd have lock contention and that hurts performance. Making timer ISR as far as possible is safer.

I think we can use an external reference clock source (like PIT or HPET) to setup. Set reference clock frequency at (sys_main_freq*cpu_count), like 4Hz in previous example, and broadcast this interrupt to all CPU (via IOAPIC). Start the reference clock, each CPU skips first X interrupt (where X is the CPU-index), and start its APIC timer. After the last CPU done, stop the reference clock, and resyncing finish.

What's your idea? Do you know any other OS have similar design?

My question is why not reduce lock contention by affinitising threads to CPUs? Each CPU can have its own dedicated queue, which is lock free. Then a shared task to balance the load.

Also, lock free algorithms exist, which wouldn't be too contended between a scheduler invocation and one dedicatted balancing task.

[songziming]

My question is why not reduce lock contention by affinitising threads to CPUs? Each CPU can have its own dedicated queue, which is lock free. Then a shared task to balance the load.

Also, lock free algorithms exist, which wouldn't be too contended between a scheduler invocation and one dedicatted balancing task.

There's always shared data / code, like a global ready-queue, lowest priority CPU, load balancer, etc.

And lock-free algorithms also use atomic instructions, also causes cache-bouncing.

[thewrongchristian]

My question is why not reduce lock contention by affinitising threads to CPUs? Each CPU can have its own dedicated queue, which is lock free. Then a shared task to balance the load.

Also, lock free algorithms exist, which wouldn't be too contended between a scheduler invocation and one dedicatted balancing task.

There's always shared data / code, like a global ready-queue, lowest priority CPU, load balancer, etc.

The point is, with local mostly per CPU run queues, busy CPUs can remain scheduling process on their local run queue without interacting with other CPU and their run queues, and with no locks, and only periodically do you need to run code that does need to touch all the run queues across all the CPUs to re-balance the load. The period could be as short as a 1 second or even less, something that barely registers on a human perception scale (in terms of noticing imbalances in CPU load) but would make a massive difference in locking and cache behaviour on each CPU.

If CPUs are not busy, then casting around for a process to run from a global run queue is no big deal, we're not bust anyway.

So in the average case (not busy) you're no worse off, and in the worst case (all CPUs busy) you're considerably better off, exactly when you ned it.

And lock-free algorithms also use atomic instructions, also causes cache-bouncing.

But see above. If run queues are not shared, the atomic ops will not impact other CPUs as much anyway. And in fact, if the run queue is local to a CPU, it can be modified just by disabling interrupts and making the change. Also, a process on CPU0's run queue is unlikely to be in the cache of CPU1, so an atomic instruction will have little to no impact on CPU1 even if it is needed (such as balancing from a global run queue.)

The other benefit of lock free algorithms is that they're inherently fast for the subset of cases they make sense. To update a data structure without lock free algorithms, you have to lock the structure (which will necessarily include atomic ops anyway), make the structure update, then unlock the structure. More instructions, more memory references.