Hmmmm....I like the ideas going around, I like this one, not sure if it's exactly what you meant though. But I like it:
Basically, there are 255 (one byte size number) different task levels, although only the first few really need to be used. It runs one task from each of the levels then goes back and does it again. The whole 'priority' thing is solved by the fact that there are less of, say, task 5 levels, than there are of task 1. So tasks of level 1 would run 1 out of every (NumberOfTaskLevels)*(NumberOfLevel1Tasks).
That means that a task of level 255, if there were no other task levels of 255, would be running 1 out of (NumberOfTaskLevels) time. And if there were 10 tasks at level 0, then they would be running 1 out of (NumberOfTaskLevels)*10 time, or a tenth of the time of the level 255 task. So my algoritham would be:
.. Start X at first task index
A. Go to task X of first level
B. After certain time, stop task
C. Go to first task of next level
D. Goto B until no more task levels left
E. Increase X
So that levels with less tasks in them (usually the higher-priority tasks) will have on average more time.
Does that sound reasonable?
Round-Robin
Re:Round-Robin
Hi,
What if there's ten level 65 threads, two level 64 threads and one level 1 thread? The lowest priority thread would get 10 times more CPU time than any of the higher priority threads, and the two level 64 threads would get 5 times more CPU time than the level 65 threads which are at almost the same priority.
Even for a simple case, where there's one level 222 thread, one level 3 thread and nothing else, there'd be no effective difference between the high priority thread and the low priority thread.
Now imagine you've got 200 threads ranging from level 0 to level 200, and each thread gets 1 mS. If something happens and a high priority level 255 thread becomes ready to run and needs CPU time fast, then it may need to wait for 200 mS before it gets any CPU time. If this high priority thread is updating the video and takes 10 mS to draw windows, draw fonts, update the display memory, etc then it'd actually take 10 time slices with 200 mS delays in between each time slice. In this case it would actually take 2 seconds for the highest priority thread possible to do 10 mS of work.
I guess what I'm saying is that you can not guarantee that threads will have well spread priorities, and therefore can't guarantee that it'll work as intended.
One off the key requirements for "responsive-ness" is that if there's an extremely low priority task running and an extremely high priority task becomes ready to run, then the extremely high priority task pre-empts the extremely low priority task and starts running immediately, and the extremely low priority task does not get any CPU time until the high priority task has finished doing it's job. All modern OSs that I'm aware of satisfy this requirement in some way, yet round robin and this algorithm don't.
Cheers,
Brendan
Sorry, but IMHO no!Cjmovie wrote:Basically, there are 255 (one byte size number) different task levels, although only the first few really need to be used. It runs one task from each of the levels then goes back and does it again. The whole 'priority' thing is solved by the fact that there are less of, say, task 5 levels, than there are of task 1. So tasks of level 1 would run 1 out of every (NumberOfTaskLevels)*(NumberOfLevel1Tasks).
That means that a task of level 255, if there were no other task levels of 255, would be running 1 out of (NumberOfTaskLevels) time. And if there were 10 tasks at level 0, then they would be running 1 out of (NumberOfTaskLevels)*10 time, or a tenth of the time of the level 255 task. So my algoritham would be:
.. Start X at first task index
A. Go to task X of first level
B. After certain time, stop task
C. Go to first task of next level
D. Goto B until no more task levels left
E. Increase X
So that levels with less tasks in them (usually the higher-priority tasks) will have on average more time.
Does that sound reasonable?
What if there's ten level 65 threads, two level 64 threads and one level 1 thread? The lowest priority thread would get 10 times more CPU time than any of the higher priority threads, and the two level 64 threads would get 5 times more CPU time than the level 65 threads which are at almost the same priority.
Even for a simple case, where there's one level 222 thread, one level 3 thread and nothing else, there'd be no effective difference between the high priority thread and the low priority thread.
Now imagine you've got 200 threads ranging from level 0 to level 200, and each thread gets 1 mS. If something happens and a high priority level 255 thread becomes ready to run and needs CPU time fast, then it may need to wait for 200 mS before it gets any CPU time. If this high priority thread is updating the video and takes 10 mS to draw windows, draw fonts, update the display memory, etc then it'd actually take 10 time slices with 200 mS delays in between each time slice. In this case it would actually take 2 seconds for the highest priority thread possible to do 10 mS of work.
I guess what I'm saying is that you can not guarantee that threads will have well spread priorities, and therefore can't guarantee that it'll work as intended.
One off the key requirements for "responsive-ness" is that if there's an extremely low priority task running and an extremely high priority task becomes ready to run, then the extremely high priority task pre-empts the extremely low priority task and starts running immediately, and the extremely low priority task does not get any CPU time until the high priority task has finished doing it's job. All modern OSs that I'm aware of satisfy this requirement in some way, yet round robin and this algorithm don't.
Cheers,
Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
-
distantvoices
- Member
- Posts: 1600
- Joined: Wed Oct 18, 2006 11:59 am
- Location: Vienna/Austria
- Contact:
Re:Round-Robin
Hm. I handle it in that way, that I have system tasks, drivers, services and ordinary round robin processes.
I'm keeping five queues - to express the pyramid of call path execution -> user->service->driver(->systemtask)
Only round robin processes can be preempted due to time expiration. Services preempt round robin processes and run as long as they need to run. Drivers preempt services and too run as long as they need to run. In case an other driver/service gets ready (by a message sent to it) the newly activated task (service or driver) preempts the previously running one and runs as long as it needs to.
This architecture requires lean execution paths in services, drivers and system tasks. It's get a job (receive msg), do it, send a reply eventually, return to receive msg in the main loop. It further requires drivers and services *never* to be caught in long loops - especially drivers need not to loop endlessly somewhere in the middle of the code, as I don't have cpu hog detection currently. cpu hogging drivers - I'd stop them anyways and notify the current user of what's happening.
Stay safe!
I'm keeping five queues - to express the pyramid of call path execution -> user->service->driver(->systemtask)
Only round robin processes can be preempted due to time expiration. Services preempt round robin processes and run as long as they need to run. Drivers preempt services and too run as long as they need to run. In case an other driver/service gets ready (by a message sent to it) the newly activated task (service or driver) preempts the previously running one and runs as long as it needs to.
This architecture requires lean execution paths in services, drivers and system tasks. It's get a job (receive msg), do it, send a reply eventually, return to receive msg in the main loop. It further requires drivers and services *never* to be caught in long loops - especially drivers need not to loop endlessly somewhere in the middle of the code, as I don't have cpu hog detection currently. cpu hogging drivers - I'd stop them anyways and notify the current user of what's happening.
Stay safe!
... the osdever formerly known as beyond infinity ...
BlueillusionOS iso image
BlueillusionOS iso image
-
Cjmovie
Re:Round-Robin
Hmm....What if I have DWORD, that is, unsigned int. That would then be the amount of 'fibers' (parts of threads) running.
Then a task will be either level 1-16. A level 1 task will get one fiber. A level 5 task might get 15 fibers. I spread the fibers out evenly. Then I round robin the fibers. But I will do something else when spreading then out - for instance, 15 / 5 is 3, so I'd group the fibers in sets of 3 to reduce overhead of having to switch back and forth just for one process.
Then I'll let highest-priority (drivers/kernel, level 14-16 I guess) tell the OS the minimum time it must have between it sending an "end" and being able to do more work (in case it's waiting on a floppy or something). If it can fit it that constraint with ONLY hurting regular priority 0-3 (Idle) or for HIGHEST priority like 16, only hurting 1-7 (idle and standard tasks).
Kind of a merge between standard muilti-tasking and real time kernel.
Then a task will be either level 1-16. A level 1 task will get one fiber. A level 5 task might get 15 fibers. I spread the fibers out evenly. Then I round robin the fibers. But I will do something else when spreading then out - for instance, 15 / 5 is 3, so I'd group the fibers in sets of 3 to reduce overhead of having to switch back and forth just for one process.
Then I'll let highest-priority (drivers/kernel, level 14-16 I guess) tell the OS the minimum time it must have between it sending an "end" and being able to do more work (in case it's waiting on a floppy or something). If it can fit it that constraint with ONLY hurting regular priority 0-3 (Idle) or for HIGHEST priority like 16, only hurting 1-7 (idle and standard tasks).
Kind of a merge between standard muilti-tasking and real time kernel.