is it possible to do "perfect" resource scheduling

[d11in]

...if the scheduler knows exactly what the process will do? like a process is represented by a list or a tree, the scheduler knows the computing depth of this process, "he" also know what the process will do...is it possible to do "perfect resource scheduling??? ::)


best regards

[Solar]

Depends on the definition of "perfect"... and whether you are thinking of a specific ressource (CPU? RAM? I/O? ...?)

Instead of going to answer what I think is your question, would you care to elaborate a bit?

[Pype.Clicker]

anyway, you virtually never know all things that will occur. I'm thinking at missing pages to be swapped in, interrupts from other drivers that may be important to handle, etc.

btw, in hard realtime system, one usually knows the longest possible run for a task and assume the worst case should still meet its deadline, but that's hardly transposable to desktop systems...

[srg]

Out of interest, would a Real Time desktop OS be possible, or are desktop systems too chaotic?

srg

[distantvoices]

Possible it is of course. But what would be the witz of a real time OS for the desktop workstation?

Real Time Operating systems best scale in environments where exact timings are required and a task has to finish in a given time: aeroplane navigation and control, atomic plant control, car control (yes, those little chips sitting in nearby each and every car nowadays - at least in the upper classes - are operating in hard real time - it has no sense delaying abs/ebs triggering until some checking function for the overall system status has given up cpu. It has to happen immediate with the least possible delay. period.)

Now, tell me if one needs real time on the desktop, where various things can happen virtually at the same time: Hard disk triggers IRQ, signaling that job is done, Soundcard triggers IRQ: buffer empty, gimme more data, User moves the mouse around the screen dragging icons - all this orruring concurrently: There is no need for real time but for a system that schedules the task in the right order and takes care of the various concurrencies that can happen, so that each task gets its fair share of cpu and the ressources.

You may want to think about semaphores, mutexes and spinlocks to guard ressources against concurrent access.

stay safe

[Pype.Clicker]

@d11in:
btw, what's your definitiion of 'perfect' ? what should the scheduler exactly achieve ? As there are several tasks that run in parallel and all would prefer to complete as soon as possible, you clearly see that completing all tasks as if they were alone is *not* possible

[Candy]

deadlock avoiding resource scheduling (which amounts to "perfect" since it always finishes) using the bankers algorithm (see your OS dev books)

perfect paging: don't page out, or use the perfect algorithm (which is so computationally expensive that paging itself is cheap)

Realtime desktop system? You don't want it. First of all, realtime != fast, realtime == guarantees. You might want to guarantee your media player always finishes, but I would disadvise it. Realtime systems have huge overhead to make it constant.

[Solar]

Hm, Candy, I have to disagree to some degree.

Especially with a media player, hard real time can be beneficial. You can guarantee that the next block will be read from hard drive in time for it to be displayed, so you won't have frame skips, and you can guarantee that the audio stays in sync.

For a dedicated play-back or recording system, hard real-time is basically a must have.

But, and that's the part most people forget - that implies several things:

1) Your media player must know beforehand how long it will take to display one frame, how many frames / second will be displayed, timings of the video driver, etc. etc. - means, either the whole system (hardware, OS, drivers, all running software, and of course the media player itself) must be tuned for hard real time for it to work.

2) Your media player might run without glitches as long as the overall workload of the system is low, i.e. plenty of ressources are available. At pretty exactly 70% ressource usage (maximum!), a hard real-time system fails. The OS can no longer guarantee the deadlines - the playback might be able to continue successfully without skipping frames, but the system can't guarantee it anymore (which is the very definition of hard real-time). So either you fail completely (aborting the playback), or you continue anyway in a "best effort" - at which point you stop having a "hard" real-time system. In this case, you can just spare yourself the effort (and complexity and requirements and bookkeeping) because it doesn't earn you anything compared to other "best effort" systems like AmigaOS, BeOS, Windows, or (as I have been told) v2.6+ Linux kernels. (Earlier revisions of the Linux kernels were not fully preemptive, which explained the rather abysmal multimedia performance.)

[Candy]

Especially with a media player, hard real time can be beneficial. You can guarantee that the next block will be read from hard drive in time for it to be displayed, so you won't have frame skips, and you can guarantee that the audio stays in sync.

For a dedicated play-back or recording system, hard real-time is basically a must have.

But, on an X86, the overhead is so large that it's nearly useless to do so. You'd leave only 50% cpu when doing that, and you'd get 70% when not forcing everything hard real timed. Still, I do agree that best-effort should be better.

1) Your media player must know beforehand how long it will take to display one frame, how many frames / second will be displayed, timings of the video driver, etc. etc. - means, either the whole system (hardware, OS, drivers, all running software, and of course the media player itself) must be tuned for hard real time for it to work.

Which is exactly the problem. Most lossy formats take either lots of cpu cycles to compress, or don't compress very well. Also, it has to be sure of all the other things it needs (paging?), and that it has 100% preference at the harddisk.

That's fr*gg*n hard to do.

2) Your media player might run without glitches as long as the overall workload of the system is low, i.e. plenty of ressources are available. At pretty exactly 70% ressource usage (maximum!), a hard real-time system fails. The OS can no longer guarantee the deadlines

BULL. Pure BS. You're forgetting some decades of development.

The limit is slightly above 70% when using the way-too-old RMS policy. When you use EDF you can reach 99.9% load and still make it. I just can't see why you can't see it.

In this case, you can just spare yourself the effort (and complexity and requirements and bookkeeping) because it doesn't earn you anything compared to other "best effort" systems like AmigaOS, BeOS, Windows, or (as I have been told) v2.6+ Linux kernels. (Earlier revisions of the Linux kernels were not fully preemptive, which explained the rather abysmal multimedia performance.)

abysmal multimedia performance? Why didn't I notice that? My hard-realtime-thread of cd burning at 8x on an M2 233 didn't hitch below 95% buffer level on a 2.4 kernel (an early one even). Also, viewing DVD's never slows... don't see your point as why it would be so bad.

[Solar]

BULL. Pure BS. You're forgetting some decades of development.

Ho, ho, take it easy!

The limit is slightly above 70% when using the way-too-old RMS policy. When you use EDF you can reach 99.9% load and still make it. I just can't see why you can't see it.

(To those not into the subject, RMS -> Rate Monotonic Scheduling, EDF -> Earliest Deadline First.)

I'll pick up the book and quote as soon as I get home.

abysmal multimedia performance? Why didn't I notice that? My hard-realtime-thread of cd burning at 8x on an M2 233 didn't hitch below 95% buffer level on a 2.4 kernel (an early one even). Also, viewing DVD's never slows... don't see your point as why it would be so bad.

Oh come on. I saw people running 8x burners on their 680x0 Amigas, and the DVD viewing on a 233 MHz machine I'll only believe when I've seen it with my own eyes.

That being said, I don't say that every computer running Linux is doing a bad job at any given multimedia task. I just say that other OS'es (and I don't exactly mean Windows here either) are doing a much better job at it. AmigaOS probably being the most extreme example, BeOS and others a close second.

[Candy]

abysmal multimedia performance? Why didn't I notice that? My hard-realtime-thread of cd burning at 8x on an M2 233 didn't hitch below 95% buffer level on a 2.4 kernel (an early one even). Also, viewing DVD's never slows... don't see your point as why it would be so bad.

Oh come on. I saw people running 8x burners on their 680x0 Amigas, and the DVD viewing on a 233 MHz machine I'll only believe when I've seen it with my own eyes.

That being said, I don't say that every computer running Linux is doing a bad job at any given multimedia task. I just say that other OS'es (and I don't exactly mean Windows here either) are doing a much better job at it. AmigaOS probably being the most extreme example, BeOS and others a close second.

Ok, point taken . I was comparing my computer with linux to my computer with windows, and in THAT comparison linux was unbeatable in terms of deadlines. I never burnt on AmigaOS or anything else, so I couldn't tell... BeOS didn't even support my video card so I never got a good look at it.

PS: the dvd playing was on a duron, not that 233mhz box. I was long happy to be able to burn cds on it .

PPS: Windows (2k, xp) doesn't keep up at 12x cdrom burning on a 1200mhz duron with dedicated IDE channel... or is that just me?

[eth]

perfect resource scheduling would be to ignore /usr/local/bin/pico's attempt to load a 32mb file in memory taking up 90mb total in an 128mb machine, of which half are already taken by the kernel and the gui, leading to aggressive swapping on a pre-historic ide drive, when all you wanted to do is edit the first page

[Solar]

What you're imagining is not perfect ressource scheduling, but artificial intelligence with the ability of precognition...

If that's an actual problem of yours, there are editors that allow editing without loading the whole file. I don't know for any Linux-native editors, but UltraEdit does that quite well on the Windows platform (and it runs in Wine, too).

[d11in]

Depends on the definition of "perfect"... and whether you are thinking of a specific ressource (CPU? RAM? I/O? ...?)

Instead of going to answer what I think is your question, would you care to elaborate a bit?

don't look at register level for this. for example: your program is written in lisp, that's evaluated in primitive functions (one program step) and translated in a binary tree (list). now the scheduler knows the tree (that's what the program will do/ the scheduler knwows exactly when a program requires an io operation or something other). there are multiply programs (trees) which the scheduler analyses and choose the fittest program next.

[Pype.Clicker]

will it really know ?
i mean if i write

Code: Select all

(if some_condition read-from-disk do-something-else)

All the scheduler can know is that there are chances i try to read things from the disk, but it still ignores if the condition will be true or false nor if reading will require a disk I/O access or if it will hit some cache ...

Moreover, what will the 'goal' of the scheduler be ? even if it can predict that a disk I/O is going to be needed in the next time quantum, what can it do out of it ?