Scheduling extremely inefficient

[mariuszp]

My OS is working extremely inefficiently, and I think it might be because of how the scheduler works. By inefficnently I mean it takes a few seconds to copy 1-2MB of data (for example when swapping a framebuffer to screen). When a new process is being loaded, it takes a few seconds. In Bochs, fork() is much faster than on real hardware and VirtualBox for some reason, but loading-on-demand and copy-on-writing in the child process (and the parent ofcourse) then takes a long time anyway.

My scheduler is triggered by the PIT, or by system calls. I've been using a setting of 1000 Hz for some time, and it is at that frequency that I get those unacceptable speeds. Changing it to 10 000 Hz causes it to speed up incredibly, then crash at random moments (on 1000 Hz it crashes at random moments too, but much less frequently). At 100 Hz it works much faster in VirtualBox but much slower in Bochs, still with unacceptable speeds in both, it freezes frequently but then unfreezes, as if other processes (that are not writing to stdout) were getting way too much CPU time.

Has anyone else had such strange effects? Could it be resolved by, for example, implementing APIC timing? If there is any code that you need to see just ask, I am completely confused about what might be going on here. If you want to search through the code yourself, the link is in my sig.

Any hints or tips? Thank you.

[eryjus]

Any hints or tips? Thank you.

What I am finding missing from your discussion is the quantum you are giving to each process. If you are executing a process switch on each PIT interrupt, the overhead associated with that is going to kill performance (stated from experience).

As an example, I have 5 set priorities that a process can be scheduled under: 30 for kernel processes, 20 for high priority process, 10 for a normal process, 5 for a low priority process, 1 for the idle process. These priority values are copied to the quantum for each process when it gets the CPU. Therefore, a normal process will be given 10 PIT "clicks" before it is preempted (unless it blocks for some reason).

[Brendan]

Hi,

Any hints or tips? Thank you.

One of the first tests that should be done (for any/all schedulers) is to have a high priority interactive task (e.g. a simple shell) and a low priority CPU hog. When the user presses a key the OS should immediately pre-empt the low priority task and switch to the high priority task, and when the high priority task is finished (e.g. blocked waiting for the next key) the OS should switch back to the low priority task. A scheduler passes this test if it's impossible for the user to determine if the interactive task is the only task that's running (or if there are one or many CPU hogs running in the background) by looking at the interactive task's responsiveness/lag alone (without looking statistics from the scheduler or measuring CPU temperature or something).

If a scheduler fails this test, then it is faulty - either higher priority tasks aren't pre-empting lower priority tasks properly, or there's a design flaw (like, there's no task priorities in the OS design).

Also note that with only one CPU hog the timer does nothing - either the higher priority task runs (until it blocks), or the lower priority task runs (until its pre-empted). This is why it's one of the first tests that should be done (as it can be done before you even bother implementing the timer IRQ, etc).


Cheers,

Brendan

[alexfru]

It's not just the context switching overhead and priorities. One should also consider implementing apps (or libc) appropriately. Apps shouldn't be burning CPU cycles while doing nothing other than waiting for some event/input. If you run 4 apps of the same priority and all they do is sit in an infinite loop, there should be no surprise in that they will leave no more than 1/5th of CPU time to a 5th app. And it may be useful to favor the app that's interacting with the user (active window or receiving keyboard/mouse input).

[rdos]

One of the first tests that should be done (for any/all schedulers) is to have a high priority interactive task (e.g. a simple shell) and a low priority CPU hog. When the user presses a key the OS should immediately pre-empt the low priority task and switch to the high priority task, and when the high priority task is finished (e.g. blocked waiting for the next key) the OS should switch back to the low priority task. A scheduler passes this test if it's impossible for the user to determine if the interactive task is the only task that's running (or if there are one or many CPU hogs running in the background) by looking at the interactive task's responsiveness/lag alone (without looking statistics from the scheduler or measuring CPU temperature or something).

If you design the scheduler with null threads, then this test is automatically done.

[Combuster]

If you design the scheduler with null threads, then this test is automatically done.

Proof wanted.

[rdos]

Any hints or tips? Thank you.

What I am finding missing from your discussion is the quantum you are giving to each process. If you are executing a process switch on each PIT interrupt, the overhead associated with that is going to kill performance (stated from experience).

As an example, I have 5 set priorities that a process can be scheduled under: 30 for kernel processes, 20 for high priority process, 10 for a normal process, 5 for a low priority process, 1 for the idle process. These priority values are copied to the quantum for each process when it gets the CPU. Therefore, a normal process will be given 10 PIT "clicks" before it is preempted (unless it blocks for some reason).

Yes, the quantum would be important, especially if the threads used doesn't block, but rather act as CPU hogs.

What is 10 PIT *clicks"? I use a time-quantum of 1ms, and it doesn't affect performance a lot on modern CPUs.

[rdos]

If you design the scheduler with null threads, then this test is automatically done.

Proof wanted.

Why? If the null thread exists at the lowest priority, and runs as the "default" thread, then if your application that blocks works as it should then any other lower priority thread should work the same.

[Combuster]

So the bottom line is, a null thread has nothing to do with it and you were posting nonsense as usual.

Also, merely having priorities is no guarantee that they get used in the correct fashion to make UI threads act appropriately, so even your new argument, while closer to the truth is bogus as well.

[rdos]

So the bottom line is, a null thread has nothing to do with it and you were posting nonsense as usual.

Also, merely having priorities is no guarantee that they get used in the correct fashion to make UI threads act appropriately, so even your new argument, while closer to the truth is bogus as well.

1. In any sane design, the null thread has bottom priority and is only run when no higher priority (IOW, any other thread) is ready to rum

2. UI threads shouldn't have higher priority than anything else

[Combuster]

I think that's enough proof that you're unable to write an OS that passes Brendan's test.

[bluemoon]

2. UI threads shouldn't have higher priority than anything else

This is a design choice, whereas some people including Apple and Google may decide UI should be responsive (aka perspective performance) than doing actual works.

[Geri]

you should have linked an ISO, so we could debug it.

[mariuszp]

you should have linked an ISO, so we could debug it.

https://github.com/madd-games/glidix/bl ... glidix.iso

Also, indeed, my scheduler does not support priorities, and the PIT is fixed at a frequency of 1000 Hz, even though some processes call yield() to give up their CPU time... but then the next process would get much less CPU time than normal... that does sound like a pretty bad design. And drivers like the IDE driver and the keyboard driver are just hanging there waiting for commands and still getting CPU time.

I'm gonna be adding APIC support and here's a question: if I set APIC to single-shot mode, and that "shot" happens when interrupts are disabled, is it missed or does it get sent as soon as I enable interrupts? What about if interrupts are disabled, the shot happens, then I program the APIC again, and then enable interrupts? (I'll need to do that for calls such as wait() which would need to trigger the scheduler to schedule another task).

(EDIT: I may also add that calling memcpy() while interrupts are disabled also causes the swap to screen to take a few seconds, is that a Bochs problem or could the memcpy() implementation I 'stole' from PDCLib be really bad and I should use "rep stosb" instead?)

[Geri]

is there a 32-bit version available?