Page 1 of 1
Scheduling
Posted: Mon May 10, 2004 1:15 am
by NeowertWithoutLoggingIn
I hear a lot about thread priority, and I undertand the datastructures to implement this. Such as a heap to keep things all nice and sorted. But is there something wrong with giving every task equal time (aside from the blocking ones, who get nothing at the moment). It would make the schedular very simple and very fast to execute. All you would need to do is go from thread to thread. I can think of ways to do this in like 1 - 3 lines of C. Is this called round robin by any chance?
Re:Scheduling
Posted: Mon May 10, 2004 1:46 am
by Solar
Yes, that is round-robin, and no, there's nothing wrong with it -
if you know the limits that will impose on your system.
The idea with thread priorities is that, in a "life" system, you have several things you want to run continuously, but not taking up any significant ressources unless no-one else wants them. Screensavers, garbage collectors, such things. And once a GUI comes into play, chances are you'll want to have the window holding the focus to have highest priority, since that's where the user is working ATM.
Priorities can make a system "smooth" if done right. If screwed up, they can make a system unusable. In any case they make a system more complex. But all modern OS (and all old ones, AFAIK, if they multitask) use them, so that should tell you something.
Re:Scheduling
Posted: Thu May 13, 2004 1:07 pm
by Tim
Practical example: If you're got one thread handling the mouse pointer, you'll want it to have a higher priority than normal. On a pure round-robin system, the mouse thread would only get as much CPU time as any other, so under heavy load the pointer would appear to jump about the screen. On a priority-based system, a high-priority pointer thread could block until the user moved the mouse, at which point it would move the pointer then block again.
Re:Scheduling
Posted: Thu May 13, 2004 9:27 pm
by mystran
Indeed, you will likely want a few priority levels. But I don't think adding a few priority levels is that bad at all. As was suggested in "the other thread" a good idea is to simply create several queues instead of one, and search the queues from highest-priority to lowest every time you need a new task.
Even just adding the priorities, and scheduling threads in priority order without any pre-emption whatsoever is better than nothing, since now your mouse-pointer only has to wait for the timeshare of ONE task to end..
If you DO want pre-emption (as soon as a high-priority thread unblocks, run it instead of the previously-running lower-priority one) then your best bet is to notice that you switch to kernel every time you get an interrupt from hardware, and the only reasons for something unblock are hardware interrupts (if nothing more then timer) and system calls, so every time you might want to pre-empt, you are already in kernel for other reasons.... so, why not check for higher-priority threads when returning from kernel.
It's not that hard after all =)
Re:Scheduling
Posted: Fri May 14, 2004 1:26 am
by Ozguxxx
So is there a solution for assuring this system smoothness via priority queues? I mean I understand the problem but nobody is offering a solution.
Re:Scheduling
Posted: Fri May 14, 2004 2:23 am
by BI lazy
*grmpf* What about havin' yer brain work for a change, eh?
'tis as simple as this:
Code: Select all
thread_queue_t queues[255]; //multilevel queues
thread_t *r; //the process/thread to run.
//here is a code snippet to scan through the queues:
int i=0;
r=NULL;
while(!r&&i<255){
if(queues[i].end!=queues[i].start){ //test: empty?
r=queues[i].start->next;
}
i++;
}
//at last: is r still null; we shove the idle thread to the cpu
if(r==NULL)r=idle;
//in a round robin scheduler:
if(r->time<=0){
queues[r->priority].start->next=queues[r->priority].start->next->next;
r->next=NULL;
queues[r->priority].end->next=r;
queues[r->priority].end=r;
}
A thread of higher priority always preempts a thread of lower priority. Tht's how it works. And you won't need to search: picking queue, removing/reattaching thread is a O(1) operation.
Further you need to ensure, that certain queues of high priority can only be opulated by threads which give up CPU guaranteed. So, Driver threads, SErvices and so forth - highest priorities, user processes and untrusted services: lower priorities.
hth