Can scheduling be done in userspace?

[Brendan]

Hi,

There is nothing wrong with round-robin, at least not when round-robin is per scheduler queue. In my solution, I have a number of round-robin queues. For ready-to-run threads, there is one queue per priority-level (I have 256 levels, but only use about 16). Each core has it's own set of priority-based queues, and then there are per-system priority queues for threads that have been "kicked" from their core.

If you've got a queue per priority-level (per CPU) then it's not round robin. Most people would call it a "priority scheduler".


Cheers,

Brendan

[wolfram]

I guess that implementation of sheduler in userspace is true idea. But it will suffer from slow contex switching.

If allow loading schedulers to kernel space, there are 2 choices:
1. Load scheduler as part of other kernel code, without defining dedicated address ranges and threads for schedullers. But then we will suffer from limitations of microkernel: languages we can use, memory we can allocate etc.
2. Map schedulers to dedicated addresses in kernel space and execute it as threads. It will allow to run scheduler's thread without flushing TLB. But now scheduler is able to damage kernel memory

It seems there is no fast and secure solution

[NickJohnson]

It seems there is no fast and secure solution

When was the last time a kernel anywhere panicked because the scheduler broke and started overwriting memory? Putting the scheduler in the kernel is not a security/stability concern. The rest of the kernel is far more likely to contain bugs.

[wolfram]

It seems there is no fast and secure solution

When was the last time a kernel anywhere panicked because the scheduler broke and started overwriting memory? Putting the scheduler in the kernel is not a security/stability concern. The rest of the kernel is far more likely to contain bugs.

You speak about OSes with hardcoded schedulers, written in same lang as OS. But the author want to allow user to use it's own schedulers. What if user want to use scheduler written in PHP? Then PHP-interpreter will be load in kernel space, fat interpreter, with all its bugs.

[wolfram]

The idea of userspace schedulers brings up several questions:
1. Should we disable interrupts (or only timer interrupt) while scheduller(s) think about which thread run? (I think yes)
2. What to do, if scheduller (root or middle) crash/freeze?

[gerryg400]

The idea of userspace schedulers brings up several questions:
1. Should we disable interrupts (or only timer interrupt) while scheduller(s) think about which thread run? (I think yes)

Why ? If the scheduler is running in userspace it should be treated like any other process. The kernel should only need to disable interrupts during some critical sections. If the 'userspace' scheduler is given a special environment where it can disable interrupts and have special kernel access then it's not really a userspace scheduler.

2. What to do, if scheduller (root or middle) crash/freeze?

Kill it. If it's in userspace then treat it like any another process.

[NickJohnson]

It seems there is no fast and secure solution

When was the last time a kernel anywhere panicked because the scheduler broke and started overwriting memory? Putting the scheduler in the kernel is not a security/stability concern. The rest of the kernel is far more likely to contain bugs.

You speak about OSes with hardcoded schedulers, written in same lang as OS. But the author want to allow user to use it's own schedulers. What if user want to use scheduler written in PHP? Then PHP-interpreter will be load in kernel space, fat interpreter, with all its bugs.

I know this, but the point is that it's a tradeoff between speed and flexibility, not speed and security.

[wolfram]

The idea of userspace schedulers brings up several questions:
1. Should we disable interrupts (or only timer interrupt) while scheduller(s) think about which thread run? (I think yes)

Why ? If the scheduler is running in userspace it should be treated like any other process.

Why? If the scheduler treated as like any other process (better to say thread. because "process" is meaningless in microkernel OSes), why kernel gives him rights to decide which thread to run? Userspace don't cancel special previlegies.

If the 'userspace' scheduler is given a special environment where it can disable interrupts and have special kernel access then it's not really a userspace scheduler.

Scheduler won't enable/disable interrupts. Interrupt (timer) will be disabled by kernel before switching to scheduler and will be enabled after scheduler tell which thread to run.

2. What to do, if scheduller (root or middle) crash/freeze?

Kill it. If it's in userspace then treat it like any another process.

Ok. If non-root sched crashes, we could pass its child nodes to its parent. But what to do if root sched crash?
And another question: how to recignize that sched freezed?

[gerryg400]

If you have a userspace scheduler, running as a process in its own address space, that scheduler will need read-, and perhaps write-access to the kernel data structures and it will need knowledge of the state of interrupts and the SMP data structures. It will also need to run at a very high priority. You have also suggested that it will need to disable interrupts.

At that point I say that your scheduler is no longer a userspace scheduler and is in fact a kernelspace scheduler running as a kernel thread in an address space that looks a bit like a user address space.

And another question: how to recignize that sched freezed?

Well that's up to the kernel. IMHO, if the kernel can't find a way to kill a userspace process then it should not load it.