Fair scheduling using virtual time

[Brendan]

Hi,

Just an extra note - we can quantify "responsiveness".

When the user presses a key (or moves/clicks the mouse or something), if the video is updated within about 30 ms the user won't notice the delay and will think it the OS responded "immediately". If it takes longer than 30 ms the user might notice; and if the delay is excessive (e.g. 100 ms or more) the user will notice and decide that the OS/GUI is "sluggish". The goal is to ensure that the time between receiving the keyboard (or mouse) IRQ and updating the screen is always less than 30 ms (e.g. regardless of how much load the OS is under).

Depending on your OS; the keyboard/mouse driver might do some processing and send something to the "GUI task", the scheduler might do a task switch to the GUI, the GUI might do some processing and send something to the active application, the scheduler might do a task switch to the application, the application might do some processing and send something back to the GUI, the scheduler might do a task switch back to the GUI, the GUI might do some processing and send something to the video driver, and the video driver might do some processing and update the screen. All of that would need to happen in less than 30 ms (including the 3 task switches). Of course (depending on your OS) this can be much worse - for a micro-kernel there'd be more task switches, there might be a "font engine" involved, etc.

Updating the video can be very expensive; especially if the user pressed "alt + tab" or something and everything needs to be redrawn, and especially if we're using a decent/high-resolution video mode, and especially if there's no hardware accelerated video (likely for a hobby OS).

How much of that 30 ms is left over (after all the processing is done) for those "3 or more" task switches?


Cheers,

Brendan

[rdos]

I fail to see the problem. 30ms is a lot of time with a decent maximum timeslice. If you give each task a maximum of 1ms, as I do, it means there could be 30 threads competing for a single-core CPU without the 30ms being exceeded. On a multicore machine, there could be far more.

The only reason why this might be a problem is:
1. The OS uses long timeslices
2. There are many tasks that compete for CPU time without doing anything useful (perhaps doing busy-polling)
3. The GUI is slow and inefficient

[Brendan]

Hi,

I fail to see the problem. 30ms is a lot of time with a decent maximum timeslice. If you give each task a maximum of 1ms, as I do, it means there could be 30 threads competing for a single-core CPU without the 30ms being exceeded. On a multicore machine, there could be far more.

You fail to see the problem, because you fail to understand the difference between a general purpose OS and an embedded system. It's like a small child on a bicycle that can't understand why a truck driver would need to care about gross weight.

For a simple example, let's think about "update the screen". For an embedded system you can pre-scale the font data (if any) and all image data and make sure it's all in the same pixel format as the machine will be using; and "update the screen" ends up being "blit a few bitmaps".

For a general purpose OS, "update the screen" can mean asking the GUI layer to add it's window decorations, scaling hundreds of pictures/icons, rendering thousands of textured polygons, using font data to convert Unicode strings into bitmap data (including scaling, proportional fonts/kerning, anti-aliasing), doing colour conversion (possibly including HDR and/or colour space conversion and/or white point conversion and/or hue shifting for colour blind users) before converting to the video mode's pixel format (possibly including dithering), before blitting anything to display memory.

How much of that 30 ms would you have left over (for your crappy scheduler to waste) if it takes 68 ms to update the screen/s?


Cheers,

Brendan'

[bewing]

It's a very bad idea to assume that end-users are more knowledgeable than software developers and have a better idea of what priorities different things should run at. An OS that requires end-users to constantly mess about with task priorities (e.g. every time any process or thread is started) should have a big splash screen at boot that says "WARNING: We failed to do it right, therefore we expect you to sort out our mess".

One of the main points of having a robust OS is not to blindly trust unknown code, or unknown software developers with important system resources. An OS that gullibly allows software developers to increase arbitrary numbers of userland thread priorities above normal should have a splash screen that says "WARNING: this OS is completely vulnerable to DOS attacks from fatware, malware, and hackers because we failed to do it right."

If you allow a malign software developer to create 500 threads with super-high priority that go into JMP .-2 loops, then you cannot guarantee that 30ms response time.

And, yes, of course the window with the focus should get a priority boost. The user has indicated that they think that window is important, by clicking on it. You don't need anything special to allow users some control. Just keep track of the last few windows and processes that had focus, and give them some temporary priority increases.

[Brendan]

Hi,

It's a very bad idea to assume that end-users are more knowledgeable than software developers and have a better idea of what priorities different things should run at. An OS that requires end-users to constantly mess about with task priorities (e.g. every time any process or thread is started) should have a big splash screen at boot that says "WARNING: We failed to do it right, therefore we expect you to sort out our mess".

One of the main points of having a robust OS is not to blindly trust unknown code, or unknown software developers with important system resources. An OS that gullibly allows software developers to increase arbitrary numbers of userland thread priorities above normal should have a splash screen that says "WARNING: this OS is completely vulnerable to DOS attacks from fatware, malware, and hackers because we failed to do it right."

You don't need to blindly trust unknown code - it's very easy to have limits. For example, you could just give each process a "max. thread priority" that is set when the process is spawned/forked; where the child process' max priority must be equal to or lower than the parent process' max. thread priority, and where a process can't change it's own max. thread priority.

To be perfectly honest; I'm surprised that you were unable to think of anything like this yourself before posting.


Cheers,

Brendan

[rdos]

For a simple example, let's think about "update the screen". For an embedded system you can pre-scale the font data (if any) and all image data and make sure it's all in the same pixel format as the machine will be using; and "update the screen" ends up being "blit a few bitmaps".

For a general purpose OS, "update the screen" can mean asking the GUI layer to add it's window decorations, scaling hundreds of pictures/icons, rendering thousands of textured polygons, using font data to convert Unicode strings into bitmap data (including scaling, proportional fonts/kerning, anti-aliasing), doing colour conversion (possibly including HDR and/or colour space conversion and/or white point conversion and/or hue shifting for colour blind users) before converting to the video mode's pixel format (possibly including dithering), before blitting anything to display memory.

My GUI is in between. It uses true-type fonts to write text, and has abilities to do dithering and similar. It also uses double-buffered video, mostly because new LFB-hardware cannot tolerate reading real video-memory. OTOH, the GUI does not including windowing, and the kernel does not support windowing at all, rather exports a generic graphics API that an application can use to create typical GUIs with. Therefore, there is no foreground/background concept either. An application always runs in full-screen mode. However, several applications can run at the same time, but only one is visible at the time. The others works against a virtual screen.

How much of that 30 ms would you have left over (for your crappy scheduler to waste) if it takes 68 ms to update the screen/s?

If the update takes 68 ms you've lost regardless of how smart your scheduler is.

In the usage-cases I have, there will never be any threads that do busy-polling, or waste lots of CPU-time in the background, unless I run some of my own ill-behaved test-apps that are aimed to use as much CPU time as possible. Therefore, when a user event happens, there is usually no load that increase response-time, and if there is, it would not compare to 30 threads all trying to get as much time as possible. In fact, I've run the terminal application with several of the ill-behaved test programs I have in the background, and it doesn't affect response-times in a way that is noticable.

[rdos]

It's a very bad idea to assume that end-users are more knowledgeable than software developers and have a better idea of what priorities different things should run at. An OS that requires end-users to constantly mess about with task priorities (e.g. every time any process or thread is started) should have a big splash screen at boot that says "WARNING: We failed to do it right, therefore we expect you to sort out our mess".

One of the main points of having a robust OS is not to blindly trust unknown code, or unknown software developers with important system resources. An OS that gullibly allows software developers to increase arbitrary numbers of userland thread priorities above normal should have a splash screen that says "WARNING: this OS is completely vulnerable to DOS attacks from fatware, malware, and hackers because we failed to do it right."

Good point. It's this situation modern OSes try to protect themselves against with sandboxes and other complex mechanisms that slows the system down. In fact, it can be claimed that the penalty of giving developpers an wide-open door into the OS, and allow it to be abused, is a need to create an extra layer (usually with virtualizing and/or interpreted languages) which in the end results in much worse performance than the original "dumb" scheduler.

[rdos]

You don't need to blindly trust unknown code - it's very easy to have limits. For example, you could just give each process a "max. thread priority" that is set when the process is spawned/forked; where the child process' max priority must be equal to or lower than the parent process' max. thread priority, and where a process can't change it's own max. thread priority.

OK, so now you want to go in the same direction as Microsoft when you start to discover the problems of developpers abusing your system? You will end up with letting developpers working in an interpreted language that doesn't have any of the "features" your scheduler wanted to give developpers in the first place.

[Brendan]

Hi,

You don't need to blindly trust unknown code - it's very easy to have limits. For example, you could just give each process a "max. thread priority" that is set when the process is spawned/forked; where the child process' max priority must be equal to or lower than the parent process' max. thread priority, and where a process can't change it's own max. thread priority.

OK, so now you want to go in the same direction as Microsoft when you start to discover the problems of developpers abusing your system? You will end up with letting developpers working in an interpreted language that doesn't have any of the "features" your scheduler wanted to give developpers in the first place.

A simple round robin scheduler is immune to the "single very high priority task hogging all CPU time" problem, but it's not immune to the "fork bomb" problem, and you'd want something to prevent a malicious process from deliberately creating too many threads and/or child processes to guard against that.

A simple "highest priority thread that can run does run" scheduler is immune to the "fork bomb" problem (e.g. a process can have 50 million low priority threads and it doesn't really matter), but it's not immune to the "single very high priority task hogging all CPU time" problem, so you'd want to limit thread priorities to guard against that.

The thing is, it's impossible to create a scheduler that is immune to both of these problems at the same time. If you're going to allow untrusted code to be executed, then you have to have at least one limit (and maybe more if you combine several techniques), regardless of how the scheduler works. This has nothing to do with interpreted languages at all.

Of course an embedded system might not allow untrusted code to be executed, and therefore might not need to worry about things like this. An embedded system might not need to worry about a large number of things that a general purpose OS has to worry about. Someone developing an embedded system might even come to a forum where most people are writing general purpose OSs and say things that only make sense for embedded systems (but seem silly to the majority of people, who aren't writing embedded systems); simply because they've never needed to understand a large number of things that a general purpose OS has to worry about.

Another one of those "large number of things an embedded system developer might not need to understand" is portability issues. For example, if a general purpose OS supports several different architectures (e.g. 32-bit 80x86, 64-bit 80x86 and ARM), then allowing executables to use some sort of portable byte-code (e.g. CIL used by .NET) to avoid the need for application developers to provide a different native version of their application for each different architecture (while also avoiding the need for application developers to provide "easy to rip off" source code) can make a lot of sense. Of course there are choices that need to be made when you start considering the use of portable byte-code (e.g. managed or unmanaged; compiled when installed, compiled while running or interpreted; etc) and a lot of different opinions about the advantages/disadvantages of each of these choices.


Cheers,

Brendan

[FallenAvatar]

I just wanted to chime in and agree with brendan.

I have been browsing these forums (and the Wiki) for literally years (6+, I'm only 24 ) and have completed the basic osdev checklist (environment set up, booting, running my code, etc. I followed JamesM's tutorials but converted it to c++ w/namespaces.) And I have to say, the recent "appearance" of rdos, and his "My OS is perfect" ideology, is hilarious. Every time I see a comment from him, i read it just to see how off topic, or close minded it is.

rdos: You do not write a general purpose hobby OS. You write a commercial OS targeted to an extremely small (laughably small) subset of computers. STOP giving advice. You clearly don't have the general populace in mind (which is fine! just stop acting like you do.) And move on to something more important (to you, or this forum as a whole, doesn't matter.)

- Monk

P.S. Sorry to flame....but damn......

[gravaera]

People need to stop hatin on my boy RDOS...I co-sign all of his statements. RDOS threads always deliver \o/

[Antti]

[...]

I have not been here so long but I think that rdos posts make this forum more interesting. Not that I agree with rdos. Please keep posting rdos but remember that you do not have to stick to your viewpoint. I think that people are allowed to change their opinions as time goes by.

[bewing]

You don't need to blindly trust unknown code - it's very easy to have limits.

Part of the point is that each of your objections has workarounds, too, y'know?

[OSwhatever]

This thread got a little bit OT but now I have investigated a little bit more about this subject and I've come up with a design that might work.

Previously my kernel used a per processor run queue of threads. This works well for thread scheduling but when scheduling entire processes this method becomes difficult as there might more threads belonging to the process you are going to swap out. The goal is that processes should have a fair amount of time slice regardless of how many threads that runs in the process. Each process should also have a time slice per priority, meaning a thread running at priority 5 will not eat up the time slice of a thread running at priority 10.

The per processor run queue was removed and placed into the process structure instead so that each process has their own run queues, one for each priority. A global red black tree was added in order to help scheduling of the processes. The key consist of first the priority and the insert time of the first thread in the thread run queue so that the tree is ordered first by priority and then insert time. This way when you search for the minimum element you get the process with the thread with highest priority and was inserted earliest. If the process was preempted, it is inserted into the tree but with a new insert time based on the current time.

In order for a processor to fins the next job it must first search for the process to run, remove the element from the tree, remove the first thread in the queue, update the tree element so that it gets the new insert time of the new first thread, insert the tree element again if necessary.

This method is significantly slower that the previous as each search for a new thread require a search, a remove and an insert to the red black tree if any thread was found. The tree is global and therefore it puts a limit of how many processors the tree can serve before there is too much congestion. For large number of CPUs, the processors should be divided into clusters.

The advantages are that you a lot of freedom adding and exploring different scheduling algorithms by changing how the red black tree key works. Thread preemption as well as process preemption work naturally. It is easy to find a second thread belonging to the same process in the case of multi threading CPUs.

A global tree also helps thread migration but this might not always be optimal and I'm not sure how solve this if I want to retain a preempted thread on one particular CPU. I've played with the thought that each CPU has their own tree but in this case it will be difficult to keep the consistency and the information synched.