OSDev.org

Hello, i'd like to have your opinion ...

I think that most existing OSes (linux & windows, mainly) have really bad behaviour when the system gets overloaded (i.e. when CPU usage reaches 100%): the user inputs are then ignored for too long, your MP3 player begins to miss some samples, etc...

Now, what i planned to do to solve this in my own OS is to
- have a fully preemptible microkernel (a hardware interrupt can occur and be handled when the system is busy servicing a process A)
- have an event mechanism that will allow the kernel to notify user-level process of some data arrival. A thread that received an event from the kernel will be able to "steal" the CPU time of the current thread (if it was not itself responding to an event).
To prevent badly-written programs to crash the system, a thread that has not replied to the event in one time quantum will be marked as hog and will never get access to the urgent queue again.

So, what do you think of it ? any major flaw you can detect ? Any improvement to propose ?
Any kind of feed-back is welcome ...

aren't there patches to provide pre-emptable processes and low latency kernel functions to the linux kernel? It's just a matter of fine tuning and getting them submitted to the dev kernel.

- Nick

Excuse the facetious reply, but NT already does that: all of the kernel is pre-emptable, apart from interrupt handlers etc. (which do very little work), and the entire I/O model is asynchronous, meaning that a thread can either block (not run at all) or do other work until it is notified of I/O completion.

I know exactly what P.C. is talking about. I have Windows XP and when I run my MP3 player, it's fine... but then I open the task manager, notepad several times, internet explorer several times, MSN messenger... if the system process decides it wants to do something, the music skips...

Pype, all you really need to do, is have a normal scheduler(Interrupts happen anytime anyways - CPU state is completely saved)like Windows or LINUX, but make it so that only some tasks have high priority... keep most others at a low priority. With XP, I can keep Sonique at normal priority, but then bring all other tasks down and it never skips... until the system process kicks in - it's high priority

It's inevitable that, if you load your system, something will stop running some of the time. Remember on a single-CPU system there's no such thing as real multitasking: Sonique will stop running for short periods of time regardless of how loaded the system is.

Of course, the goal is to allow it to run often and long enough to keep the sound card buffers full -- but that is a matter of getting the right scheduling priorities. If some other process (or the system) decides it is more important, or Sonique decides it is less important, then it will skip.

Pype.Clicker wrote: ...
To prevent badly-written programs to crash the system, a thread that has not replied to the event in one time quantum will be marked as hog and will never get access to the urgent queue again.

... any major flaw you can detect ? Any improvement to propose ?
Any kind of feed-back is welcome ...

So...what happens if it's just slow and still Does work [but doesn't respond ] ( many many times this hapens for me ) [ the program that is a hog ] and it is stoped from the scheduler?

I think that the user should deside if it [ the hog program ]should stop/continue the process like in XP.

what i had in mind was a 2-queue dispatcher : a "normal" queue where threads are executed in the scheduler-defined order (using a round-robin scheme : when a thread's time quantum is exhausted, it is sent back to the end of the queue)

in addition, a special 'urgent queue' is set up for events processing, which has precedence on the normal queue (i.e. nothing is served on the normal queue as long as the urgent queue isn't empty)
however, the quantum in the urgent queue is smaller (about 1 clock tick) and threads which exceed that quantum will be sent back to the normal queue *forever* (or at least for a while).

the events scheme is intended for quick response to user input etc, so keeping a hog in the event queue waiting for a user response to the question "stop the hog?" will make the user unhappy because it will be hard for him/her to answer to that response.

Tim Robinson wrote: Excuse the facetious reply, but NT already does that: all of the kernel is pre-emptable, apart from interrupt handlers etc. (which do very little work), and the entire I/O model is asynchronous, meaning that a thread can either block (not run at all) or do other work until it is notified of I/O completion.

yes, but how many times did i see "real-time priority (dangerous)" in a mp3 player ... neither NT nor linux does address the problem of badly-behaved real-time process (and that's what i'd like to have here : a multimedia-real-time process which can be told "run every 2ms to fill in my sound buffer" ... it could also be nice if the kernel was able to see that a real-time event is about to occur and that resource should be kept free when it will occur (but this is likely to be complicated to handle ...)

Well, then you're getting into the domain of real-time systems: "I want the kernel to guarantee that this code will run within the next 2ms and will run for at least 500us". Although there are real-time addons to the NT kernel, to do it properly would likely require a redesign. Real-time capabilities are simply not needed for the majority of systems (thinking about desktop and server machines). Of course, embedded systems (where real-time kernels are most useful) have a different set of requirements.

I'd like to add a nice scheduling tweak I came across in a book on OS design: directed yields.

Consider task A sleeping, waiting for task B to provide a message (or some chunk of data).

B is scheduled for a 100-unit timeslice. After 15 time units, the data is ready, put into the IPC system, and B yields.

Now, depending on the system (priorities, wake-up mechanism etc), it can take quite some time before A is scheduled.

Directed yield means, when B puts the data into the IPC system, it tells the system "I yield to task A", and A gets scheduled immediately, reducing messaging latency to a minimum.

Now, to avoid starvation, A doesn't get a full timeslice, but only the 100 (default) - 15 (what B used up) = 85 time units.

Since B could very well have used those 100 units itself, no "unfairness" is introduced.

I'll leave the concept scetch at that. There are still things to consider here (e.g., applying a penalty on the 85 time units to cater for the scheduling / dispatching, what to do with A's upcoming "standard" timeslice), but I found the raw concept to be intriguing (and will certainly try to implement it in my kernel).

i have implemented a test scheduler that uses this policy for Clicker (yet it rather was "i wake up thread B and yield 5 time units to it, then i want the CPU back for my remaining timeslice"), and it really boosted system interactivity.

However, it is unnatural that "wakeup()" system steal your CPU, thus some of the IPC mechanisms needed to be adjusted to continue working

Hey Solar thats a really good idea with the directed yields.

I was thinking of having different priorities such as:

7 - GUI
6 - Soft Real Time
5-1 - No exciting name for the other levels
0 - Would be the idle process

Different threads at the same priority go in round robin format.

There would be lots of restrictions for threads that want 7 or 6. eg only 1 thread needs to be at 7 assuming there's 1 gui. threads that want level 6 must not use too much cpu, and if the cpu load is getting heavy then if more threads want to upgrade to level 6 they will be denied.

Also if a thread is at say level 5, but is hogging the cpu, the schedular will dump it down a level or 2. Trying to give priority to the less demanding threads.

Of course thats all very vague at the moment.....

tom1000000 wrote: ...only 1 thread needs to be at 7 assuming there's 1 gui.

Erm... certainly you'd want your GUI to be multi-threaded, no?

...threads that want level 6 must not use too much cpu...

One idea from the dynamic feedback scheduling concept is penalizing high-priority threads for using up their timeslice by reducing their priority.

...and if the cpu load is getting heavy then if more threads want to upgrade to level 6 they will be denied.

Be careful: Most threads are started by software. "Denying" a thread basically means breaking the application.

You'd also be inviting the disadvantages of a "hard" real-time system (as load increases, tasks might be denied) with the disadvantages of a non-real-time system (no guarantees).

Also if a thread is at say level 5, but is hogging the cpu, the schedular will dump it down a level or 2. Trying to give priority to the less demanding threads.

That's feedback scheduling in a nutshell.

However, be aware that for some systems - those aimed at computational throughput, like i.e. a rendering station - this is not optimal. They might actually want the CPU hog (rendering engine) to run at high priority.

Basically depends of the type of system you are designing the scheduler for.

@solar: those kind of considerations lead me to beleive that the Scheduler should be a plugin that can be replaced according to system use. For instance, you might have it changing dynamically at applications start/end/switch (in Clicker's sense of application, which should more be seen as a "unit of user's job", or a virtual Desktop that has special properties, behaviour, default tools, etc).

Pype.Clicker wrote: @solar: those kind of considerations lead me to beleive that the Scheduler should be a plugin that can be replaced according to system use.

Sniffing around in Pro-POS' "Big Picture" again, have you?