Scheduling Algorithms in Microkernels

[iammisc]

I've come to the point where there is a notable size difference when I change the time slice allocated in my simple round robin scheduler. The problem with my current scheduler is that when a process's time slice is over it gets a new one automatically(10 clock ticks) regardless of whether it's been hogging cpu. This means that a process interrupted by a lot of key presses can basically get 0 cpu time. I just wanted to know what the different scheduling algorithms are that are tailored for microkernels. If you could provide a list of pros and cons of each scheduling algorithm that would really help me make a decision on which to use.

Right now, I'm thinking of a running list and expired list much like the linux O(1) scheduler because that will guarantee that all processes get an even amount of cpu time. The problem is that the keyboard driver will probably be in the expired list when most of the keypresses come.

Thanks for all the help.

[distantvoices]

This ain't difficult, I reckon.

the keyboard driver f. ex. , despite being a task of its own - if I understand correctly - is bound to block, waiting for the notification of the IRQ-handler (be it a call, be it a message placed on its queue and waking it up, be it putting some parameter and scheduling the task for run)

I've solved this by having priority queues. Then, the configuration of a task decides how it is scheduled - be it real time, service or round robin (with any priority that doesn't cross the realm of system tasks)

Round robin tasks are prone to starve in this scheme of things.

YOu can of course do it the linux way with running & expired list, but make sure that tasks you need to have execute run, regardless of stuff hanging in the expired queue. (I think, that's done by that negative nice-value. them kernel tasks always get cpu time first)

stay safe

[lukem95]

i was going to post a similar topic to this, but i might as well continue this one.

i was also thinking about when a task was wasting its CPU time, and possible ways to detect this and skip it in the scheduler.

[distantvoices]

give them cpu-hogs a penalty so they are of lower priority than the io bound tasks.

so in case something wants to process io-gathered stuff, it gets an early turn, and cpu-hogging stuff will be placed below in order not to hinder responsiveness.

[lukem95]

ok this is my plan for now (open to suggestions )

round-robin style (with a twist), as this is easiest to implement;
have 4 priorities: low, med, high & sys;
each of these have a seperate slice of time, e.g. 3ms for low, 5 for med, 10 for high, 15 for sys;
the priority is chosen based on amount of keystrokes/other i.o. interupts recieved during its timeslice and also CPU usage (can't think how ill find this one out);

i'm also contemplating having a higher number of high priorities chosen compared to low, but i can't think of a good way to do this.

[deadmutex]

ok this is my plan for now (open to suggestions )

round-robin style (with a twist), as this is easiest to implement;
have 4 priorities: low, med, high & sys;
each of these have a seperate slice of time, e.g. 3ms for low, 5 for med, 10 for high, 15 for sys;
the priority is chosen based on amount of keystrokes/other i.o. interupts recieved during its timeslice and also CPU usage (can't think how ill find this one out);

i'm also contemplating having a higher number of high priorities chosen compared to low, but i can't think of a good way to do this.

That almost sounds like a Multilevel Feedback Queue.

You can initially set the priorities to a "default" priority and lower the priority based on the amount of timeslices that are used up before preemption. If a process' timeslice is used up, then it has its priority lowered. If a low priority process waits in the run queue for a long time, then it may have its priority increased. Instead of allocating more time for higher priority processes, I think it would be better to allocate less time. Since high priority processes need to run as soon as possible, they shouldn't be penalized if another high priority process hogs the CPU. Shorter timeslices mean less wait time for other processes. Even though higher priority processes get less CPU time, they will always run before lower priority processes. So if there are 1,000 low priority processes and 1 high priority process, the high priority process will always run before the ones with low priorities as long as the high priority process is in the run queue. If a new process is added to the run queue with an even higher priority than the currently executing process, then the current process is preempted and the new process will get CPU time.

There is more overhead to this form of scheduling than just doing round robin, but this method gives preference to short processes and I/O bound processes. You might also want to look into "Virtual Round Robin Scheduling"