Page 5 of 7
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 5:39 am
by Combuster
No, the last two pages are about how *your* different solution is better (t'was your point of view, of course) and how everyone disagree with you on that point. And you still claim you know better than everybody else.
First stage of grief...
... denial.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 5:45 am
by Griwes
berkus wrote:Griwes wrote:No, the last two pages are about how *your* different solution is better (t'was your point of view, of course) and how everyone disagree with you on that point. And you still claim you know better than everybody else.
Are you seriously planning to outperform rdos on defending his only correct solution?
I tried, at least
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 6:18 am
by AlfaOmega08
Well, it wasn't my intent to provoke a war on this thread... anyway I just want to say that IT WORKS... Thanks to all your suggestions (Brendan's expecially) I managed to write a fairly decent scheduler. I can finally write random "a", "b" and "c" from different thread. Each thread goes to sleep for some ms, and it works so good I can't believe... Here's my design (hope this isn't the beginning of another world war):
- The scheduler is multilevel feedback queue like, using 16 queues. Internally each queue is just plain RR.
- There is only one sleep queue per CPU. It's implemented like a priority queue, using as sorting parameter the WakeupTicks (from HPET). So each time I just have to compare only the first thread from the queue with the HPET's main counter.
- Each thread inherits a "Base Priority" from it's process. The Base Priority is assigned accordingly the process kind. The kind is given from the process itself (I'm a daemon, I'm a GUI program, I'm just crunching numbers).
- The CurrentPriority of a thread scales down each time the thread consumes it's whole time slice (5 ms). Anyway it can never get lower than the BasePriority. When the thread starts the CurrentPriority is 15.
- When a thread blocks waiting for I/O it's CurrentPriority goes up by 1 (actually when it waits on a semaphore). I hope this enhances responsiveness.
- WIP: when a thread is found starved on a low priority queue for a long time (2, 3 seconds??) it's priority is boosted to 15, it's given double time slice, and then gets back to it's original priority. (suggested from Win XP scheduler)
- In future when GUI will be ready, windows with focus will have a higher base priority.
For CPUs balancing I will probably use a high priority thread that is activated once each # seconds that will take care of balancing (AFAIK this is the method used by linux).
I also read that linux CPU schedulers GRAB threads from other CPU's queues (when they're idle) instead of pushing to other CPUs (when they're busy), or using a global queue. This also implies that the idle CPU checks other CPUs. What about this method?
I'm just so happy I can't tell...
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 7:34 am
by Yoda
rdos wrote:No, all USER tasks have the same default priority.
The following example (from the book of Robert Love "Linux Kernel Development") demonstrates the broken logic of such scheduling approach.
We have network driver that is
not from user space and hence has higher priority. The top half of driver (IRQ service routine) leaves most of work (not to disable interrupts for a long time) for the bottom half of driver. The bottom half is scheduled (with top priority, as mentioned). It works, and at that time new network packet arrives, top half schedules the task for bottom half again. DDOS attack may be? Slow PC in network with heavy load? Doesn't matter. With bad scheduler the system will stop respond because all that it will do is to execute postponed interrupts without allowing user space application to react on them or even to react on ALL user input, including system shutdown or disabling overloaded network subsystem.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 8:52 am
by rdos
Yoda wrote:rdos wrote:No, all USER tasks have the same default priority.
The following example (from the book of Robert Love "Linux Kernel Development") demonstrates the broken logic of such scheduling approach.
We have network driver that is
not from user space and hence has higher priority. The top half of driver (IRQ service routine) leaves most of work (not to disable interrupts for a long time) for the bottom half of driver. The bottom half is scheduled (with top priority, as mentioned). It works, and at that time new network packet arrives, top half schedules the task for bottom half again. DDOS attack may be? Slow PC in network with heavy load? Doesn't matter. With bad scheduler the system will stop respond because all that it will do is to execute postponed interrupts without allowing user space application to react on them or even to react on ALL user input, including system shutdown or disabling overloaded network subsystem.
That's just a bad network stack. My network stack does not use the top-half/bottom-half approach, rather has a thread for handling network packets. The only thing the network IRQ does is to send a signal to the network thread to wake it up. The network handling thread does have above-normal priority, but it doesn't do user-level callbacks or anything like that. It typically sends the packets to the TCP/IP socket or queues them on the remote-IPC protocol.
And I know I have no problem with continous network traffic as I've tested to run my IPC-test apps over IP letting many threads on different computers send as many messages as the can. The system never becomes overloaded or unresponsive, and doesn't even come close to becoming overloaded.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 12:34 pm
by Combuster
Lock requested to prevent this stupidity from spreading.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 12:50 pm
by rdos
I just uploaded the proof that the CPU will not become overloaded even in the presence of continous network traffic from a local network to "what do your OS look like".
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 12:51 pm
by Yoda
rdos wrote:That's just a bad network stack.
That's NOT question of network stack or any other particular subsystem. I just showed you
practical example of scheduling flaw when tasks with higher priority prevent execution of lower priority tasks and that will prevent the normal functioning of the whole system. But it seems that you believe in infallibility of your opinion, so I'm going to sleep according to the Combuster's recommendation
.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 12:58 pm
by bluemoon
rdos wrote:That's just a bad network stack.
Please elaborate how bad linux's network stack is. I really want to know and learn.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 1:04 pm
by rdos
I'm not denying that such things could happen with fixed priority scheduling. It is the responsibility of the writers of system device-drivers to make sure that scheduling algorithms does not make the system unresponsive, like in the example of the Linux network stack. It is even possible that using a gigabit switch instead of the 100Mbit switch I used for the performance test could make the system malfunction, although I suspect it will start losing packets rather than bringing down the whole system.
Besides, what is the alternative, and why would those alternatives garantee that the system will not malfunction under heavy network load?
After all, if you let the network server thread in my design have the same priority as ordinary user tasks, this might result in packet overruns in the network card, which gives really nasty effects when the NIC needs to be reset and packets needs to be resent.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 1:19 pm
by bluemoon
It's like saying I provide a string library but I do not check for NULL, it's the programmer's responsibility to ensure no exceptional case.
While I agree part of this idea, it's usually not work in reality and the responsibility shift toward the "provider" instead of "user".
And in rare case a driver developer would know/care much about scheduling (or other in-deep kernel stuff), if they kind enough to write(port) drivers to your OS.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 1:32 pm
by Yoda
rdos wrote:Besides, what is the alternative, and why would those alternatives garantee that the system will not malfunction under heavy network load?
The alternative is described in that book too. The solution is to provide some guaranteed amount of CPU time (for example, 10%) for other tasks too.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 1:40 pm
by rdos
bluemoon wrote:And in rare case a driver developer would know/care much about scheduling (or other in-deep kernel stuff), if they kind enough to write(port) drivers to your OS.
In the case of writing network drivers for RDOS, people have no choice of how to implement them. They must make the IRQ signal the network stack (an oslevel call), and the network server thread is created in the network stack, not directly by a particular NIC implementation. Therefore, I even have a choice to change priority and add new scheduling algorithms for any present or future NIC drivers without breaking them. But I won't do that unless the current design seem problematic. It is even possible to use the top/bottom half approach of Linux/Windows without breaking NIC drivers.
OTOH, the physical disc drivers do create their server threads themselves, and decides their priorities.
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 1:47 pm
by Griwes
rdos wrote:In the case of writing network drivers for RDOS
Re: Multitasking, SMP & Timers
Posted: Tue May 22, 2012 1:51 pm
by rdos
Yoda wrote:rdos wrote:Besides, what is the alternative, and why would those alternatives garantee that the system will not malfunction under heavy network load?
The alternative is described in that book too. The solution is to provide some guaranteed amount of CPU time (for example, 10%) for other tasks too.
OK. That seems reasonable, but what is "other tasks"? All user level tasks, or some particular user level task?
One method that could garantee that all threads are executed regulary is to temporarily increase priority of unexecuted tasks every second or so. That doesn't need to be done in realtime in the scheduler, rather can be achieved with a high priority kernel thread that regulary scans for starved tasks and boosts them.