Help on Making a good Scheduler

[ashishkumar4]

I want your help to judge and analyze my scheduler for advantages/disadvantages regarding the scheduler I made today which I an gonna discuss here.
My Scheduled algorithm is called via PIT Timer tuned to ~20000Hz(atleast I set the timer to that). The algorithm is a pretty mix up of round robin and what I think is 'lottery scheduling'. When a task is made, its given
number of ticks=((((a randomly generated number)%(max possible tasks - total tasks)+priority of task from 1to 6)*(priority of task from 1 to 6))/5
that means, the task can take this much number of ticks for cpu usage. at every tick (at every call to my handler/scheduler) it is decremented. When this value reaches to 0, the scheduler switched to the next task. The tasks are a linked list of structures with the last struct pointing to first one as:
task1->task2->task3.....->taskn->task1.....
when the ticks reaches to 0 and task switch needs to take place, the scheduler saves the old task and its state in a global task pointer 'old_task' and takes the next task from the linked list and saves it as current_task (current_task=old_task->next) just like round robin. while task switching, the old task is again assigned another 'number of ticks' exactly like it was while creating the task. this is used the next time that task is called by the scheduler. This way, its probabilistically guaranteed that roughly every task gets called without significant overhead with cpu usage depending of its priority. I don't know wether it has any advantage over round robin with priority scheduling or not but I wanted to know as I made it (or has been made before?). My Pseudo-Random number generator uses RTC as a seeder and an algorithm similar to the one provided by the wiki (modified though).
Please let me know if this idea is whole crap indeed :p Though it works great but... I don't know in long run...
Thanks

[ashishkumar4]

Made Another scheduler, Replaced the round robin thing with another lottery scheduling. I take out a random number between 1 to total tasks when the tick assigned to last task is decremented down to 1 that is the last tick after which task swithing has to take place. Then at the next interrupt, the task is switched to the task having that random number as its process id and is assigned a time slice using the same technique discussed above. to counter the workload, I made it use the same random number that I used to take out the lottery. This way I implemented a Hybrid lottery scheduling with priorities and insignificant loss in performance. Please analyze this method too for advantages/disadvantages :/

[Brendan]

Hi,

Made Another scheduler, Replaced the round robin thing with another lottery scheduling. I take out a random number between 1 to total tasks when the tick assigned to last task is decremented down to 1 that is the last tick after which task swithing has to take place. Then at the next interrupt, the task is switched to the task having that random number as its process id and is assigned a time slice using the same technique discussed above. to counter the workload, I made it use the same random number that I used to take out the lottery. This way I implemented a Hybrid lottery scheduling with priorities and insignificant loss in performance. Please analyze this method too for advantages/disadvantages :/

Imagine there's an extremely important task (e.g. GUI that was unblocked because the user pressed a key) and 10 unimportant tasks (that just do things like optimise memory in the background) and 30 "medium importance" tasks (maybe they're compiling code or finding prime numbers or something).

How do you ensure that the important task gets CPU time immediately (and the user isn't stuck waiting for 10 days for the GUI to respond to key presses)?


Cheers,

Brendan

[ashishkumar4]

my giving it more ticks (tickets) so that probability of it being executed and it being executed for enough time is really high?
or does it also implies that my first scheduler was better? please sir you left me confused :/

[Brendan]

Hi,

my giving it more ticks (tickets) so that probability of it being executed and it being executed for enough time is really high?
or does it also implies that my first scheduler was better? please sir you left me confused :/

If 1000 low priority tasks have 2 tickets each, how many tickets would you have to give a very high priority task to guarantee that it will get CPU time immediately, and how many bits of RAM are needed to store this number?

Note: My answer to the first part of the question is "4 tickets". This answer is wrong because I didn't feel like getting anything correct and used a random number instead.


Cheers,

Brendan

[ashishkumar4]

:/ I am not doing it the exact way lottery scheduling is done (or I don't got it right what you meant :p )
I do this:
when a task is created, its given a special unique number like serial number (1,2,3,4,5... max tasks). I then give it a time slice based on a random number generated from 1 to 35555 and doing some multiplication, division with the number of tasks present and the priority of the task. Though the time slice is random, higher priority tasks get more time slice(that's for sure, based on my function). Now just before the time slice runs out and the time to switch tasks comes, at the last decrement of time slice, a random lottery is taken out from the numbers ranging from 1 to total number of tasks present (1,2,3,4... max tasks). The task which has this as its serial number comes to play. Now here a true lottery scheduling with priorities would take this lottery based on 'tickets' assigned to tasks and high priority task being assigned more tickets with more memory consumed. But mine dosent does that. Every task has equal probability to occur and thus your concern isn't here. But about your previous concern of higher priority task probably not getting chance is I think minimized because IF it comes to play, it would get a lot of time to complete. Now here, if it would have been simple round robin, however the more time slice assigned to a high priority task be, it would still not stand a chance to get the CPU until all the other tasks after it in the queue are executed. But with this way, there is an equal likely hood that the high priority task which just occurred would occur again as soon as its time slice ran out. I know this sounds crap but I tested it with 6 idle infinite while loop tasks (I know, that's a lot less number of tasks), assigning every task these priorities : task1=3,task2=2,task3=1,task4=5,task5=4,task6=3.
I ran it several times and the result on every run was the same:
In the time interval of 1 second, On average, the task which got the most of the CPU time was task4 (which printed 4) and the next was task 5 with task 1,task6 getting almost equal time while task3 almost not being seen (though it executed which I got to know after I made every other task print blank spaces instead of this one). So I think statistically this conditions should be met.

But still, I would be glad if you help me make this and shed some light on the weakness of this :p
And also, If this method is not good one, please tell so that I can use the original round robin with priorities scheduler
thanks :p

[embryo2]

Though it works great but... I don't know in long run...
Thanks

In long runt it's your goal that determines the result. If your goal is just to create "some" scheduler, then it works for you. But there could be other goals. For example - somebody could need real time response from an OS. Somebody else doesn't need the quick response, but wants to schedule tasks on as many processors as available. So, the goal determines your scheduler requirements. And next, after you have a clear goal in mind and managed to infer the requirements, only then you can create really useful (for you) scheduler.

So, you should answer:
1. What's your goal?
2. What scheduler requirements it imposes?
3. What algorithm can do the job while being constrained by the requirements?

It seems you haven't answered even the first question.

[ashishkumar4]

That's a very innovative way of solving a problem lol :p
You are right, I haven't even set my goals, till now I was trying to make Just An OS that works. Will think about this, thanks

[Brendan]

Hi,

Let me start from the start...

Imagine you've got 2 tasks. One is a very high priority GUI task. It spends most of its time waiting for something to happen. When something happens (e.g. user presses a key) it needs to figure out what to do and will mostly just forward the key press to the active application. What matters here is latency - how long between the task being unblocked and getting CPU time. How much CPU time it's given is mostly irrelevant, but not quite. Because it's very high priority it would be able to gobble all the CPU time, so you want to give it some sort of limit to guard against that. Basically; "high priority" means very low latency and limited/short time slices.

The other task is very low priority. It grinds away in the background for days, soaking up CPU time that wouldn't be used for anything else. If it blocks for some reason (e.g. waiting for file IO) and then unblocks (the data arrives) it doesn't matter much how quickly it gets CPU time after unblocking because it's not very important anyway. However, these tasks tend to do lots of processing (of lots of data), and every task switch messes up CPU caches, TLBs, etc, and makes them less efficient. Basically; "low priority" means high latency and long time slices.

Imagine there's 256 different priority levels; ranging from high priority (very low latency, limited/short time slices) to medium priority (medium latency, medium time slices) to very low priority (high latency, long time slices).

Now let's think about how to ensure high priority tasks get the very low latency they need. When something causes a high priority task to unblock, you want to compare the unblocked task's priority to the priority of whatever task is currently running. If the high priority task is higher priority then you want to do a task switch immediately. You don't want to wait 1000 ms for 100 less important tasks to finish their time slices. You don't want to wait for 10 ms for one less important task to finish its time slice. You don't even want to wait for 1 ms for the next timer IRQ to come along. You want a task switch immediately.

When a medium/low priority task is unblocked, and is higher priority than the currently running thread, it doesn't really matter if you do the task switch immediately and it's probably better to wait (and reduce the number of task switches).

Imagine there's 256 different priority levels; where the highest 128 priority levels will pre-empt lower priority tasks immediately, but the lowest 128 priority levels don't. That would work reasonably well. We could make it a little nicer though. For example, (assuming 0 is the highest priority) you could do "if( unblocked task's priority * 1.25 < currently running task's priority) { pre-empt the currently running task }".

Now, look at your scheduler. For high priority tasks (that need very low latency, but don't need large time slices) you do nothing to give them low latency and instead you give them large time slices? For low priority tasks (that don't need low latency, but do need large time slices) you give them small time slices?

Finally, there's this: Note: My answer to the first part of the question is "4 tickets". This answer is wrong because I didn't feel like getting anything correct and used a random number instead.

For scheduling; there is a "right" answer (or at least, an answer that gives the behaviour you've intended). If you're using a random number for anything, then you're not even trying to get the "right" answer. You're crossing your fingers and hoping that Murphy's law isn't going to bite you in the butt. User presses a key, and the worst possible case is that the GUI is repeatedly "very unlucky" and never gets CPU time. It probably will, sooner or later, maybe; but that's nowhere near close to a guarantee that it will get CPU time immediately.


Cheers,

Brendan

[ashishkumar4]

Ohk, Thanks sir, I got it what you meant. I need to prioritize things. But sir still I have one last doubt. that I had a preconception that more the CPU time a task gets, more is it executed and thus a higher task ought to get more time slice. But then why it isn't like so? And the formula you gave, thanks to you, I would be putting these things right into my scheduler. And also sir, I need your help on one more topic of mine ( no one helped till now) : http://forum.osdev.org/viewtopic.php?f=1&t=30118 Please sir, help me here as well

[FallenAvatar]

Ohk, Thanks sir, I got it what you meant. I need to prioritize things. But sir still I have one last doubt. that I had a preconception that more the CPU time a task gets, more is it executed and thus a higher task ought to get more time slice. But then why it isn't like so?

The idea is that higher priority tasks often, but not always, take less time. This is because most tasks with high priorites are ones the user is interacting with and due to the general UI Event Loops that are in use, they spend most of their time waiting.

Think about a standard UI form the user is interacting with. They might click their mouse to focus an input element, then 500ms later start typing at 1 character per 100-250ms. The UI is likely able to respond to those events and update its elements to render those changes in a few ms or less. Meaning a majority of the time is spent waiting for the next user input.

The same can be said for server tasks. Take a web server for instance. There is a lot of time spent waiting on the hard drive to load the files and a lot of time waiting on the network stack to send and receive packets. The majority of time is spent waiting, and when an event happens, the task quickly (in a short burst) handles the event and goes back to waiting for the next event to handle.

- Monk

[ashishkumar4]

ok I finally got all this. But now I am in trouble :/ now how to make a good scheduler? I don't have any more ideas :/ means neither round robins nor lottery scheduling seems to fulfill the requirements. Please help me make a good algorithm. Thanks

[MollenOS]

I use a multilevel feedback queue with 60 priority levels for each cpu, try googling "Multilevel Feedback Queue" and research that, it should fulfill what you want

[ashishkumar4]

There is a problem now. If my scheduler becomes just slightly more heavy, it fails to work. Means if I add even a single extra conditional statement in my sscheduler, it fails. Now without them, How can I implement multilevel feedback scheduling? :/ I don't know why its happening but if the scheduler becomes just slightly more laggy, the OS crashes :/ Please give me some code for the SIMPLEST POSSIBLE MULTILEVEL Scheduler with it taking less time them even round robins scheduling. Please help

[MollenOS]

Perhaps you should find out why it's failing instead? Your scheduler shouldn't fail no matter how how long it is, even though it should not be long.