How to organize threads in an SMP scheduler

[Owen]

Set the IOAPIC(s) and PCI MSI devices to deliver interrupts to the lowest priority core and then set CR8 so that task priorities are taken into account.

[rdos]

Set the IOAPIC(s) and PCI MSI devices to deliver interrupts to the lowest priority core and then set CR8 so that task priorities are taken into account.

CR8 is only available in 64-bit mode, so this is not interesting for my project.

[Brendan]

Hi,

Set the IOAPIC(s) and PCI MSI devices to deliver interrupts to the lowest priority core and then set CR8 so that task priorities are taken into account.

CR8 is only available in 64-bit mode, so this is not interesting for my project.

CR8 (in long mode) is just an alias for the local APIC's TPR (Task Priority Register). In all CPUs that have local APICs, the TPR can still be accessed directly like any other local APIC register.


Cheers,

Brendan

[FlashBurn]

For that there is the TPR (task priority register), where you say which priority the current task has and then you send the IRQs with lowest priority and the cpu with the lowest TPR (and some other things, have a look at the manuals) gets the IRQ.

[rdos]

OK, this should fit into the concept, even though changing TPR is kind of an expensive operation. I could place the code in the LoadUnlockScheduler for SMP only (which then needs to be changed to an indirect call), then I won't need to burden non-SMP targets with this. I also think I need to save the last priority so I only set TPR when it has changed.

I've now changed the signal code to use a per-thread spinlock (and it is actually faster on both SMP and non-SMP now, and with less code run with cli). I've also removed the spinlock for the wakeup-list which is no longer needed, and I've replaced the lock/unlock-calls with cli and sti instead. I've also removed the load-balancer and the fixing of threads to cores.

[rdos]

Most of the updated design has now been implemented (except kerrnel critical sections that don't work with a private lock), and it scales beatifully. When the messaging test is run with 2 cores, performance nearly doubles (but the senders that use the network stack suffer from starvation). With 3 cores, performance seems to increase a little bit, but not much. This is probably due to the use of a single receiver. However, when the GUI test is run at the same time as the messaging test, the messaging test performance equally well as without the extra load, and the GUI test also runs at normal speed.

There are also no crashes with high load and 3 cores, which is the best part. I think this is the design I'll stick to. It just needs some tweaking to optimize load. In the current tests I let 35% of the wakeups go to the global ready-queue, but this figure should be tuned to achieve good load-balancing.

[rdos]

I've used 45 incremental releases in order to find the code that fails on the new critical section data-type. Turns out one device-driver didn't use the InitSection macro to initialize the variables, but did it itself, and thus failed to initialize the spinlock. But there is at least one more problem before kernel critical sections can use a local spinlock instead of a global, but I will eventually find it.

[rdos]

OK, so now critical sections uses a local spinlock per object instead, and it seems to work. The stress test with 4 cores on an AMD Athlon worked pretty well, until a scheduler-lock failed (see another thread about this). I'll do more tests to see if I can reproduce this problem or not.

[rdos]

The AMD Athlon survived 8 hours of the most extensive test with 4 cores. I had two instances of the GUI test + one instance with the message test running two receivers and 8 local + 8 networkstack senders per receiver. Some of the senders crashed in the runtime-library, but none of the failures were related to the SMP scheduler.

I also looked at the TPR (Task Priority Register), and found it a little bit too restricted. This is because it also factors-in running ISRs. It would be hard to do much useful with only 16 levels, and with ISRs occupying some of the lower levels (level 4 and 5). The only possible levels would be null-task, normal task, and above normal priority. The scheduler has 256 levels, but only some 10 levels are actually used, and all normal threads are created with the same priority.

[Owen]

It depends upon how your priority levels work. In my case, interrupt and application priorities are the same - so a priority 5 application wins against a priority 4 interrupt. Indeed, interrupts just cause a thread to be woken up.

To me at least, it makes sense for (e.g.) the Real Time Audio Service mixer thread to run at a higher priority than the NIC IRQ handler

[Brendan]

Hi,

The AMD Athlon survived 8 hours of the most extensive test with 4 cores. I had two instances of the GUI test + one instance with the message test running two receivers and 8 local + 8 networkstack senders per receiver. Some of the senders crashed in the runtime-library, but none of the failures were related to the SMP scheduler.

Cool

I also looked at the TPR (Task Priority Register), and found it a little bit too restricted. This is because it also factors-in running ISRs. It would be hard to do much useful with only 16 levels, and with ISRs occupying some of the lower levels (level 4 and 5). The only possible levels would be null-task, normal task, and above normal priority. The scheduler has 256 levels, but only some 10 levels are actually used, and all normal threads are created with the same priority.

The TPR is an 8-bit register split into a 4-bit priority and a 4-bit sub-priority. By ignoring the 4-bit priority and only using the 4-bit sub-priority, you get 16 levels to use as an "IRQ hint". Maybe one level for "CPU is idle and wants IRQs", 8 levels corresponding to thread priorities (32 thread priorities per level), one level corresponding to "CPU acquired a kernel spinlock", and one level for "CPU is trying to cool down, don't send me IRQs unless you have to". That leaves 5 levels for anything else you can think of.

and all normal threads are created with the same priority.

Linux is like that too - normal threads all have the same priority, and there's a long history if idiotic hacks that never fix the problem and only hide some of the symptoms some of the time. It's also one of the reasons why Windows is able to make Linux look like an unresponsive joke for GUI apps (X is the other reason). Note: "able to" doesn't necessarily imply "does" - there's plenty of stupid/unresponsive applications on Windows, but it's not the scheduler/kernel's fault.


Cheers,

Brendan

[Owen]

Annoyingly, however, the sub-class is not exposed in CR8.

[Brendan]

Hi,

Annoyingly, however, the sub-class is not exposed in CR8.

It is a bit funny. I'm not too sure if AMD are planning to get rid of the sub-class one day, or if they've got some other plans for the remaining 60 "reserved" bits in CR8.

Fortunately, the full TPR register is still present and usable in the local APIC itself on AMD CPUs.


Cheers,

Brendan

[rdos]

Aparently, the IOAPIC does not have the destination shorthand bits of IPIs, and instead have only the physical/logical destination modes. I suppose that in order to deliver an interrupt using the "lowest priority" delivery-mode, I need to use the logical destination mode, and setup the related registers in the local APIC. Is this correct (manuals are not clear on this point)?

[Brendan]

Hi,

Aparently, the IOAPIC does not have the destination shorthand bits of IPIs, and instead have only the physical/logical destination modes. I suppose that in order to deliver an interrupt using the "lowest priority" delivery-mode, I need to use the logical destination mode, and setup the related registers in the local APIC. Is this correct (manuals are not clear on this point)?

The IO APIC never sends IRQs to itself, so there's no need for it to support the "send to self" shorthand, and no need to distinguish between "send to all including self" and "send to all excluding self". That only leaves "send to all CPUs", which (for xAPIC) can be done in physical destination mode by using a destination of 0xFF. Neither shorthand nor physical destination mode should be used for "lowest priority delivery" though.

Logical destinations are different. The basic idea is that it sends the IPI to each CPU where "( DFR & LDR & IPI_destination != 0) && (~DFR & LDR == ~DFR & IPI_destination)". For xAPIC, by carefully choosing how you use bits in the LDR you can do some fairly powerful things.


Cheers,

Brendan