OSDev.org

Hi, OSDev.org!

I'm starting to work on a scheduler. I decided to implement a kind of multilevel feedback queue. But I'm not sure, whether it's better to schedule all threads in the kernel or let processes schedule their time slices the way they want?

Thanks in advance!

Hi,



To schedule threads properly you need to know:

• If the thread is higher or lower priority than other threads (that may belong to completely different processes)
• The current state (load, temperature) of all CPUs (including CPUs your process isn't using)
• If something is about to happen that will make your decision redundant (e.g. another higher priority thread that belongs to a different process will wake up before you finish the task switch)

If a process has the information needed, then you're probably written an exo-kernel by accident. Otherwise, letting a process do its own scheduling is like letting the children manage a kindergarten's finances.


Cheers,

Brendan

On the other hand, processes can know a lot more about their threads than the kernel can. The traditional kernel-schedules-threads situations leads to a lot of hacky workarounds when processes have a more interesting concurrency model than just priorities and I/O.

You might be interested in scheduler activations- they are kind of a bust in traditional monolithic kernels that already do thread scheduling (a few BSDs and Linux investigated and abandoned them), but they are kind of a hybrid between your two options that might be good to try in a new kernel. Instead of creating threads, processes just let the kernel know how much parallelism they have available (this could be tied into the priority system as well). Then, instead of directly running threads, the kernel just pokes the process with information on why it's giving it a core to run on (I/O completion, new time slice, etc.) and the process decides what to do with that information. Threads are entirely in user-space.

For what it's worth, I tend to perform my own "thread" management when I write in userspace. Probably a bad idea, since I can only take advantage of one core, but in the days when desktop CPUs only had a single core the system worked nicely, as I had complete control over what tasks I performed and in what order I performed them. By managing one's own threads, once can avoid a lot of annoying race conditions that otherwise require hackish workarounds (I'm thinking right now about that SDL-based game I'm writing, and the timer callback runs in a separate thread so to avoid a race condition with the keypress handler I have to make the callback post a user event to the event loop and then perform the "real" operation in the event handler).

Sounds more like you are trying to ignore the host OS methods of dealing with User Interaction. (Or you don't know how to queue events yourself)

- Monk

That's exactly my point: I shouldn't have to queue my own events just to get around a race condition caused by OS-level multithreading. And before you shoot me for writing a keypress handler, remember that this is a game where I need to be able to detect actual key-down and key-up events to implement e.g. continuous movement of a character, and I'm using SDL where handling keypress events manually is the standard way to do things; needless to say these are SDL events, not low-level hardware events, so it's not like I'm writing a PS/2 driver to run in userspace lol.

It can be done. Only it has to be one (one process for ps/2 and send messages to other process).

I know that one *can* write a PS/2 driver in userspace, but what I was saying is that I acknowledge that that is a bad idea (since it is generally better to use the OS-provided keyboard interface).

Why not write a good driver in user space? How it works OS based on a microkernel?

I am talking about "mainstream" OSes like Linux or Windows.

I recently made a complete redesign of my scheduler. First, I let threads migrate randomly between core queues and a global queue, but this tended to always cluster dependent threads on the same core, which is often a bad solution. Not to mention that I failed to find some important bugs in the SMP kernel.

My new solution instead connects every thread to a specific core. At thread creation time, all threads will be run on BSP. Then I have a special scheduler thread that tries to balance load between cores by moving threads between cores.

Previously, I also moved IRQs between cores, but in the current solution I instead let all IRQs go to the BSP, and then I mark threads that are directly activated from IRQs as "non-movable" so the scheduler will keep those on the BSP.

Additionally, I've also provided a hook so usermode processes themselves can move specific threads to a specific core.

A very important design decision is how to move threads between cores and activating threads from another core without global spin-locks. I solved this by posting all threads that are activated in a special queue in the core the thread is bound to. This queue does need a per-core spinlock, but it will only be taken when activating threads from another core, and not in the normal scheduling process. This also needs an IPI, which was a really delicate thing because it tended to overload the kernel stack under unfavorable conditions.

The tests I've run with the new scheduler suggests it works pretty well in spreading the load. Temperature issues also become less important if the load is balanced between cores. As long as they are of the same type, which I assume in my design. Light-weight (IO-bound) threads will typically end up on BSP, where they have faster interaction with hardware because IRQs alway originate on the BSP. Threads that use a lot of CPU-time will typically be spread and moved between AP-cores.