Bossa, a Framework for Scheduler Development

Eugenia writes "The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems. This article gives you a glimpse of what scheduling development is like by letting you implement your own Linux scheduler thanks to Bossa, a framework for scheduler development."

Comments

Always behind the times...

[grub]

Most commodity computers can only run one process at a time

Ha, with Longhorn 2010XP+++ and Office 2012 I'll be able to have two Clippys simultaneously! Take that, hippy!

Re:Always behind the times...

[JabberWokky]

Unless you change your hardware (or are already running a dual/more processor/processes system of some sort), you aren't. Not with software at any rate.

--
Evan

Let the scheduler algorithm flamewar begin..

[GillBates0]

I see your FIFO scheduler and raise you my Elevator algorithm!

Re:Let the scheduler algorithm flamewar begin..

[sploo22]

Uh, the elevator algorithm is for controlling drive seeks. It makes no sense in the context of a CPU scheduler, unless maybe you're talking about a Turing machine.

Re:Let the scheduler algorithm flamewar begin..

[GillBates0]

if you notice, I referred to a generic scheduler, not a process(or) or disk scheduler in particular.

Moreover, the elevator algorithm just means cycling through a sequence completely in one direction before changing direction. It need not be confined to just disk drive head motion. I can imagine cycling through PIDs in non-decreasing order before reverting to a non-increasing order.

Re:Let the scheduler algorithm flamewar begin..

[AuMatar]

You could, it just wouldn't make much sense. The average wait time would be the same as not switching, but the worst case time would be double.

Re:Let the scheduler algorithm flamewar begin..

[Chmarr]

He said it was a scheduler. He didn't say it was a good scheduler :)

Ordinary users?

[MisterFancypants]

"The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems"

I know some people will take this as flamebait, but I honestly don't mean it to be. However, as long as Linux is in a state where developers think that "ordinary Linux users" have to even care what a scheduler is, Linux will be a failure for mainstream desktop usage.

Users don't care about OS internals. Don't send them to a page explaining OS scheduling, just tell them "All new Linux makes your applications more responsive!". That's all they want to hear.

Seriously.

Re:Ordinary users?

[ErichTheWebGuy]

parent poster is right. one of my wannabe-geek coworkers saw that and asked me, "doesn't evolution take care of your scheduling needs?" I am not joking. True story.

Re:Ordinary users?

[Anonymous Coward]

If you don't want to know what a scheduler is, you don't have to read the article. I don't know what bothers you about this. Nobody is asking the users to write their own scheduler.

Re:Ordinary users?

[Short Circuit]

What the poster meant was that the introduction of the O(1) scheduler, and the benefits to user experience it provided, caused a lot of "ordinary users" to take notice. That doesn't necessarily mean most "ordinary users" know, or even care.

However, for those that do, you'll Soon be able to drop in the latest IO, CPU or 'whatever' scheduler, now being developed independantly from the kernel.

Re:Ordinary users?

[GammaTau]

Users don't care about OS internals. Don't send them to a page explaining OS scheduling, just tell them "All new Linux makes your applications more responsive!". That's all they want to hear.

I don't think the ordinary users (at least the ones you talk about) are readers of Slashdot or OSNews. This is not marketing material you are reading. It would be silly to judge it as such.

Re:Ordinary users?

[slashdot_commentator]

However, as long as Linux is in a state where developers think that "ordinary Linux users" have to even care what a scheduler is, Linux will be a failure for mainstream desktop usage.

Are you suggesting the key to Linux's acceptance on the desktop is what CmdrTaco thinks is newsworthy on a geek website?

That's something of a misnomer, because Malda does not develop linux kernel code. And the developers were not banging his door down insisting that Malda report a story on Bossa. Developers don't give a rat's ass if users know what is a scheduler. But it is nice that their brethren are aware of available kernel development tools, hence the story!

I can't believe so many twits thought this was an insightful comment. More like finding a strawman to pontificate on the Linux community.

Re:Ordinary users?

[DrCode]

Apparently, you've never gotten a woman to go home with you by promising to show her your new scheduler.

(Okay, neither have I, but that's only because I'm married.)

Re:Ordinary users?

[johnnyb]

In that case, it seems to be pretty easy to do so:

you: Honey, do you want to come home and see my new scheduler?

wife: Can you show it to me while I eat the leftover pizza, I'm hungry!

you: Sure, but please pay attention this time, it's really really cool and neat!

wife: That's what you said about your new Perl program, but it just looked like you banged on the keyboard for a couple of hours and held down the shift key.

Re:Ordinary users?

[bro1]

Sure it is not Evolution, it is Outlook that takes care of ordinary users' scheduling needs. :)

Re:Ordinary users?

[djcapelis]

Evolutionary algorithms are a wonderful new field of...

Oh.

Re:Ordinary users?

[syousef]

I tried to say sort of thing on slashdot the other day and got modded troll.

Its refreshing to see that people who get it can be modded up.

Linux is clever, Linux is powerful. Linux is not user friendly on a desktop. Users should not need to know the locations and contents of config files, and be familiar with dozens of command line commands just to do something simple.

Re:Ordinary users?

[Feztaa]

Hello, welcome to Slashdot!

This is a geek site. We talk about geek stuff here, like OS schedulers. If you want to hear "new linux makes computer faster!", go read some RedHat marketing materials.

Just because your idea of the "average linux user" doesn't care about OS schedulers doesn't mean we're not allowed to talk about them.

Re:Ordinary users?

[ultranova]

I know some people will take this as flamebait, but I honestly don't mean it to be.

No, you meant it as a troll. And a good work too, +5 insightfull and plenty of replies.

Risin' up, straight to the top
Had the guts, got the glory...

However, as long as Linux is in a state where developers think that "ordinary Linux users" have to even care what a scheduler is, Linux will be a failure for mainstream desktop usage.

Why is it that so many people have a problem understanding the difference between the expressions "have to" and "can" ? The user doesn't have to care about what a scheduler is, but he can learn it and examine the Linux schedulers innards if he so wishes.

I've noticed that Linux brings out this apparent bug in language comprehension in many peoples brains. I constantly hear about how hard it is to learn to edit the dozens of files in the etc directory, yet in the year I've been using Linux (Red Hat 9 in desktop and Debian in my home server) I've only edited a few such files to customize some finer aspects of behaviour. I constantly hear complains about having to use command line, yet I've only used it because for some tasks (such as unpacking a 100+ rar files to directories named after the file) it is a far superior alternative to gui. And so on.

All together now: "Just because the user can do something, doesn't mean that he has to do it."

Users don't care about OS internals. Don't send them to a page explaining OS scheduling, just tell them "All new Linux makes your applications more responsive!". That's all they want to hear.

As Slashdot nominates itself as "news for nerds", it is conceivable that some people here might find OS scheduling algorithms interesting. It might also be conceivable that those who don't care about OS scheduling algorithms might skip the story and read the next one instead.

Besides, isn't giving a feature list containing a litany of incomprehensible technical terms a time-honored way of selling devices, at least to the upper management ?-)

Re:Ordinary users?

[DrCode]

But this is what you might prefer:

wife: Honey, do you remember you promised to get your new scheduler done this weekend?
you: Okay, but I was planning on mowing the lawn.
wife: You used that excuse last week. Now won't you please finish the scheduler? *Starts rubbing geek's shoulders.* You know how smooth-running software makes me feel...

Or:

you: How'r you doing, Honey?
wife: I'm almost done with my new Linux scheduler. It's really hot.
you: *drools*

nanokernel: scheduler

[Doc Ruby]

A really distributable system would include only the scheduler in the kernel, with an "outer" layer of secure (crypto signed, sealed and delivered) APIs for submitting process and data requests, and an "inner" core for hardware access, including CPU, data (storage/network such as ethernet, USB, IDE, RAM, BIOS ROM, etc) and presentation (monitors, keyboards, mice, soundcards, printers, etc). Such a nanokernel would be tiny, highly efficient, and mix/matchable with many other apps and OS'es. Privileges would be part of a comprehensive security model, with IPC filtered through access control, whether within a single memory segment, LAN, or WAN. All domains would be virtualized. And such symmetry and simplicity would set the stage for flexible inter-kernel load balancing and failover.

We're talking open-ended scalability. Security. Performance. Reliability. The OS is no longer just a privileged app, but a smaller, more focused critter, serving apps rather than being served by them. With this new scheduler framework, let a billion nanokernels bloom.

Re:nanokernel: scheduler

[Ignignot]

And you've just created the need for a "sub-kernel" which would do your actual work. We're talking more complexity. More bugs. Less performance. Less security. You haven't made the kernel smaller, you've just pulled a part of it out because you think it'd be cool to hold its beating heart in your hand while it still runs.

Re:nanokernel: scheduler

[sploo22]

You mean an exokernel?

Re:nanokernel: scheduler

[Doc Ruby]

No, those other jobs removed from the nanokernel run as independent apps. We've simplified the architecture, by reducing the inner complexity of the kernel, and moving its functions into the rest of the system. IPC and HW access are the only roles which need unique centralization, even in our "OS" paradigm. That means bugs are easier to identify, with fewer hidden dependencies (they're more overt). And performance is more granular, with less extra functions required to be loaded, and logically considered, to perform a specified task. Better security from the reduced trust among processes and the kernel, with a simpler model for their interoperation.

The kernel is much smaller. The old kernel's functions are distributed in more, optional, dynamically (runtime) includable objects, so they might even be spread among a larger total object population. But that isn't necessary to specific operations, and that can be tuned at runtime, by some of the processes themselves. Just another step down the road away from the monolithic, single-task computer, for increased parallelism and manageability.

Re:nanokernel: scheduler

[Bloater]

> A really distributable system would include only the scheduler in the kernel

No, a kernel doesn't even need to have a scheduler in it. It needs to be able to take instructions to transfer control to another cpu context, and be able to create the necessary page tables, and that's about it.

Re:nanokernel: scheduler

[burki]

it's probably called HURD. and will be ready next year.

Re:nanokernel: scheduler

[sql*kitten]

You are describing the IBM AS/400.

Re:nanokernel: scheduler

[Anonymous Coward]

No, it does sound like he's describing a microkernel (or "nanokernel", ugh) rather than an exokernel. The defining characteristic of an exokernel is that it provides no abstraction at all. It multiplexes hardware, but does not abstract it. There are no OS "system calls" in the traditional sense. There is no message passing; there are no OS provisions at all, really. Your "application" (which is really an operating system) deals with hardware, with the exokernel checking to make sure the device is being multiplexed properly.

The mentioning of "API" or "IPC" or "message" (let alone access control!) entirely excludes any exokernels.

Re:nanokernel: scheduler

[Doc Ruby]

How does that kernel arbitrate competing requests from multiple outboard schedulers? First-come-first-served isn't going to work very well, and is subject to DoS attacks. And how would only a single outboard arbitrating scheduler be identified and enforced?

Re:nanokernel: scheduler

[Otter]

The marketing people can't explain them to you, even if you do share your pizza with them.

Man, where do you work? We need to scrounge focaccia sandwiches and chicken piccata from the marketing and HR leftovers!

Re:nanokernel: scheduler

[MourningBlade]

A really distributable system would include only the scheduler in the kernel, with an "outer" layer of secure (crypto signed, sealed and delivered) APIs for submitting process and data requests, and an "inner" core for hardware access, including CPU, data (storage/network such as ethernet, USB, IDE, RAM, BIOS ROM, etc) and presentation (monitors, keyboards, mice, soundcards, printers, etc). Such a nanokernel would be tiny, highly efficient, and mix/matchable with many other apps and OS'es. Privileges would be part of a comprehensive security model, with IPC filtered through access control, whether within a single memory segment, LAN, or WAN. All domains would be virtualized. And such symmetry and simplicity would set the stage for flexible inter-kernel load balancing and failover.

We're talking open-ended scalability. Security. Performance. Reliability. The OS is no longer just a privileged app, but a smaller, more focused critter, serving apps rather than being served by them. With this new scheduler framework, let a billion nanokernels bloom.

I'll have what the Doc's having, and let me borrow your lighter - I left mine at home.

Re:nanokernel: scheduler

[Doc Ruby]

Why, I'm apparently hitting an AS/400, although I might experiment with an exokernel. Everything's groovy.

Re:nanokernel: scheduler

[johnnyb]

The scheduler can be a privileged/trusted process without being a part of the kernel.

Re:nanokernel: scheduler

[Doc Ruby]

How does that architecture address the security issues in my post, to which you responded? Examples?

Re:nanokernel: scheduler

[Zenikase]

I was under the impression that monolithic kernels, like micro-kernels, do the same job, which is simply to interface with hardware via assorted interfaces and their corresponding drivers (CPU, power management, peripheral buses, block device interfaces, networking, sound, video, etc.). The difference being that monolithic kernels can either have certain (non-critical) interfaces and drivers compiled into the kernel itself or externally as a module, whereas ie, Hurd has fixed modular interfaces to everything that isn't absolutely vital to the OS's basic functionality.

Of course, Linux also has its unclean, rigid scheduler/security model integration, but with Bossa's modular redesign, hopefully that will change.

Re:nanokernel: scheduler

[johnnyb]

Kind of like "init" works on Linux - you specify at boot time a trusted program to be your scheduler, which the kernel runs. As long as your scheduler is well-behaved there are no problems (and it will be well-behaved because YOU wrote it -- or your vendor, as the case may be).

Perhaps I'm not understanding the issues you're raising.

Re:nanokernel: scheduler

[pD-brane]

Parent is correct. Mod up!

Re:nanokernel: scheduler

[pD-brane]

Mod parent up. It's correct.

This is not about an exokernel. As the parent says:

The defining characteristic of an exokernel is that it provides no abstraction at all.

From http://www.pdos.lcs.mit.edu/exo.html:

An exokernel eliminates the notion that an operating system should provide abstractions on which applications are built.

Re:nanokernel: scheduler

[Art Tatum]

Just another step down the road away from the monolithic, single-task computer, for increased parallelism and manageability.

I'm a neophyte at kernel design, so be patient. :-)

How will this effect really high-end performance applications? Specifically, I'm thinking of music applications. The holy grail of desktop music production is a one-box solution. We want a single computing device with enough horsepower to do:

• Realtime synthesis with a wide variety of highly complicated models from various sources (file data, algorithmically generated data, live input from external devices) on a virtually unlimited number of voices
• Realtime processing of external audio or the synthesized audio with a long string of processing modules on a large number of audio streams
• Live multitrack recording of all the above on a large or very large number of tracks
• Keep this stuff in sync down to the sample-level
• Possibly stream all of this over some kind of high-performance network
• Finally, do it all with very high sampling rates (at *least* 96 kHz) and bit-depths (32 bits is a reasonable goal)

Hardly any one of these things can even be done with one computer running a general purpose OS right now (multitrack recording on a relatively large number of tracks is possible with special hardware). How much would a nanokernel approach set us back on the path to this kind of goal?

Re:nanokernel: scheduler

[Doc Ruby]

The problem is ensuring that the scheduler running outside the kernel process could be replaced by a "hostile" scheduler. But I suppose that the child could use the same signed API access that I mention to ensure authenticated process access. Do you have any examples of existing kernels using your architecture?

Re:nanokernel: scheduler

[johnnyb]

HURD is close, but I don't think it goes quite as far as having the scheduler outside the kernel. Haven't looked at it in years, though.

Scheduler Development?

[Anonymous Coward]

I thought everone was using MS project. No?

Re:Scheduler Development?

[Doctor Faustus]

Well, we've just been covering schedulers in my operating systems class, and we did Gantt charts of the processes. I was a little startled by that.

I hope I'm not alone when I ask...

[Anonymous Coward]

What the hell is a scheduler?

Re:I hope I'm not alone when I ask...

[Timesprout]

Depends how you pronounce it. If you pronounce it properly then it a vital part of the OS determining how the various running processes interact with the system, resources and each other. If you use the American pronunciation then its something KDE are probably working on to organise your time.

Re:I hope I'm not alone when I ask...

[The Analog Kid]

What a Scheduler is.

Re:I hope I'm not alone when I ask...

[AuMatar]

A scheduler is a part of the OS which decides what process has access to a given resource at a given time. The main scheduler is the process scheduler, which allocates which process gets to use a CPU right now. There's also schedulers for disk access, sending ethernet packets, and anything else that can only be accessed 1 at a time.

Re:I hope I'm not alone when I ask...

[Waffle Iron]

What the hell is a scheduler?

The scheduler is the person on your project team who, after each week's schedule slips, tapes together the latest updated Gantt chart printouts into long banners and hangs them the walls.

Re:I hope I'm not alone when I ask...

[vadim_t]

It's the part of the OS that determines what task to run.

The problem is this: You want to run tasks A, B, and C, and need to do it in the most optimal way possible.

The simplest way is FIFO, like say, DOS. If A starts first, then A runs until completion, then B starts. This is bad for many reasons, like that if A gets stuck for any reason nothing gets done, and that while A is waiting for input the free resources can't be used for anything else.

A simple way of multitasking would be simply alternating between A, B and C every fixed interval. But that's not very good either, perhaps B doesn't need to do any processing now, and only wastes time, while C could really use that.

A better way is to do it by priorities, but then you need to find a good way of calculating this priority.

One of the reasons there's so much talk about them is that most become slower when you have more tasks. Most of the simple ones need to examine every running task to determine what should run now, and if you want to launch 10000 processes at once, that's not good. O(1) schedulers are a solution for that, because they use algorithms that always take the same amount of time to execute, irregardless of whether there's 3 or 10000 tasks. That doesn't mean a simpler scheduler wouldn't work faster for 10 tasks, though.

The other problem is how to determine how to distribute CPU time. Say, for servers you mostly want fast and fair3o determine which processes are interactive, and which are on the background and won't mind some interruption.

Re:I hope I'm not alone when I ask...

[vadim_t]

I think I'll have to submit a KDE bug then, Konqueror's (it says it should be "Conqueror's"!) spell checker didn't complain about that.

Re:I hope I'm not alone when I ask...

[Fweeky]

irregardless == regardless.

"Coined in the United States in the early 20th century, it has met with a blizzard of condemnation for being an improper yoking of irrespective and regardless and for the logical absurdity of combining the negative ir- prefix and -less suffix in a single term"

Re:I hope I'm not alone when I ask...

[mabinogi]

No, it's just that British English is more modern.

American English is still left in the 17th centuary...which is why they missed out on the time when it became fashionable to spell everything as if it were french, even it it's not French - like favour, colour, etc...

But that's also why American pronounciations probably refelect the original origins of words more than British, Australian & New Zealand pronounciations...

Re:who cares

[vijaya_chandra]

what the hell
I hope you are trying to be funny
haven't read the article but am damn sure this isn't like the 'Schedule tasks' or the simple 'Prioritise Background services over Applications' option that you find in windows

Reverting back

[AntiPasto]

Are we back to "better scheduling?" ... I thought that was a mainframe technology struggle...........

I hope ...

[The-Bus]

I hope this succeeds, then gets improved upon in a second version. How cool would it be to be a part of the next project called... "Bossa Nova"?

Re:I hope ...

[JabberWokky]

That's the schedualer for PBS documentaries.

--
Evan

Re:I hope ...

[Doctor Faustus]

I hope this succeeds, then gets improved upon in a second version. How cool would it be to be a part of the next project called... "Bossa Nova"?

But that would have to be a rewrite from scratch.

Interrupts

[LordMyren]

I have a sneaking support its poor interrupt handling which makes my ALSA skip like Riverdance every time i start a file copy in mid song.

Even buffering the full song, it still skips. I've tried XMMS, moosic, mpg321. I've sought ever high priority trick i can. No matter what I try, start that file copy and WHAMO, instant pain and suffering.

Myren

Re:Interrupts

[plam]

Have you turned on DMA for your hard drive? (hdparm -d 1 /dev/hda).

Re:Interrupts

[cr0sh]

hdparm has to honestly be one of the most undelooked at tools for increasing performance in a Linux system. Everything will get a boost from using hdparm - just remember to update your /etc/rc* scripts to reinstate your choices on reboot. A good document for hdparm can be found here:

Speeding up Linux Using hdparm

Re:Interrupts

[cr0sh]

Did you even read the hdparm paper I linked to?

If you had, you will see that in most Linux installations, the hdparm parameters are set to represent the lowest common denominator of PC installations. In other words, most distributions ship with the hard drive settings so that you can install it on a circa 1992 hardware, and it will work out of the box. You have to tweak it from there.

Generally, on a new install of Linux, your buffered disk reads will be around ~4 MB/sec - even if you have the latest motherboard ultraATA/66 EIDE etc wazoo out the back - still, only 4 MB/sec.

Now, one would think this would be enough for MP3 playback, but when you are copying files while playing back the MP3 - priority likely goes to the file copy, not to the application. I don't know why this is, but I would wager it has to do with the fact the linux, out of the box, is a server system - with multimedia tacked on afterward. All of this can be tweaked, but in the end, data copy speed for core OS functions are going to get the most priority, not sound. At any rate, anything on the linux box having to do with the disk system (which is almost anything) will benefit from using hdparm to boost it to proper levels.

With proper use (for your hardware - don't just try this willy-nilly, because hdparm can be used to "force" settings that older hardware may not like, leading to data corruption), hdparm can take that 4 MB/sec number and turn it into 20 MB/sec or more. This is going to help everything. Application startup time is reduced dramatically. Directory listings and searching take less time. Hopefully, the extra speed will allow more time for the sound subsystem to keep its buffer full and not allow underruns leading to "skips".

Re:Interrupts

[cr0sh]

I understand what you are saying - in the long run, it won't matter - at some point you are going to have enough apps accessing the drive and other issues (ie, scheduling/resource management) are going to hit you.

But for simple stuff (ie, MP3 playing on XMMS while copying a bunch of files in a terminal, perhaps), not having the parameters properly set (ie, leaving them at default) may be causing the problem (for the original poster) *now* - if he isn't aware of hdparm.

A lot of people still don't know about hdparm, furthermore most new users of linux don't know that when they do an install (on most distros), the parameters are set for LCD systems, not optimized for current hardware configurations (which I think is a good thing, but to a new user it makes everything look slow).

Re:Interrupts

[MarcQuadra]

I have to agree with cr0sh. You're thinking about things a bit too simplistically.

Imagine that hdparm HASN'T been set properly, your drive reads don't appear to be slow or hog the CPU, and you're happy. But when things get 'hairy' and your'e doing a full-blast copy and trying to play an MP3 (which only needs about 1MB/minute) things are getting all choked-up. I'll bet this wouldn't happen if...

hdparm -A1 -a64 -c1 -d1 -m16 -u1 -W1 /dev/hda

(that reads:

enable hardware lookahead, enable 64-sector software precaching, enable 32-bit controller-cpu IO, enable DMS (less interrupts), move 16 sectors (8K) at a time instead of 1, unmask other IRQs while doing disk stuff (probably YOUR problem), and enable writes to be committed to the drive buffer instead of disk.

)

My guess is that your disk access is throwing a LOT of interrupts because you haven't set hdparm right and the sound card is starving for attention behind the wall of data. This wouldn't show up as an overtaxed drive or an overtaxed CPU but it WOULD affect your playback.

I've got an ancient 10GB IDE drive here and I can play MP3s back smoothly while opening OpenOffice.org AND copying files up to the server at 100Mbits/sec. You don't have 'scheduler' issues, your system is like a racecar running 87-octane gas.

HEY TACO "hold its beating heart in your hand"

[nusratt]

Taco, it just struck me that the mod system is seriously remiss in not having a way to mod a post as being "Eloquent". It's really something different from "Interesting", isn't it.
(It would also be nice to be able to search comments by mod-type.)

I wish I could use it here:
"You haven't made the kernel smaller, you've just pulled a part of it out because you think it'd be cool to hold its beating heart in your hand while it still runs."

while(1) loops

[vijaya_chandra]

10 penguins for anyone who can suggest a scheduler that taxes the stupid newbie programs with

while(1);

(/me too is a newbie)

Re:while(1) loops

[ultranova]

10 penguins for anyone who can suggest a scheduler that taxes the stupid newbie programs with

while(1);

Doesn't the scheduler in Linux 2.6 already prefer IO bound applications over CPU bound ones ?

Re:Pfffft!

[Bloater]

heh, I've still got TWO of them, one of them can even play *four* notes at a time, making a scheduler completely unnecessary.

Wake me up before you go, go......

Re:eeek (OT)

[vijaya_chandra]

From the article

If one's job is to develop scheduling algorithms, then one shouldn't have to hack kernel code.

Exactly to bring back people like you

Re:who cares

[CaptainTux]

besides they already have this for windows

Ummm, you *do* realize that we're not talking about scheduling like the Windows Task Scheduler right?

infinite loops

[vijaya_chandra]

The Bossa DSL is more constrained than C or C++ in that, for example, pointers (known for being the cause of many bugs) are absent and infinite loops can't be defined.

The part about infinite loops would be interesting as you can always shoot yourself in the foot in a zillion ways

For eg: a stupid like me might write something like

do blahblahblah while f(pid1) is less than f(pid2)

where f(x) isn't effected by blahblahblah() and f(x) is less than f(y) when x is less than y

Re:infinite loops

[whitis]

The Bossa DSL is more constrained than C or C++ in that, for example, pointers (known for being the cause of many bugs) are absent and infinite loops can't be defined.

The omega incomplete domain-specific language (DSL) is not a feature, its a bug. Turing machines have more smarts. The last thing I would want when writing a scheduler is some broken language that interferes with what I can do. If you can't be trusted with pointers and loops, you don't have any business writing a scheduler. Yes, you can lock up the machine easily with an infinite loop in the scheduler (or almost anywhere else in the kernel). But you can also lock up the machine simply by excluding certain processes from the run queue. For example, lets suppose we write a buggy scheduler that only lets a single process run. The system is dead. Now, suppose that I want to incorporate a task in the scheduler that every 100 time slices takes a slice for itself to analyse each process to determine what kind of scheduling coefficients should be used for that process. Ooops, Requires a loop. Can't get there from here. At least in this particular example one could steal a few CPU cycles each timeslice to do the caclulations and it would probably scale better but there are probably algorithms that might benifit from having them. There could be a case made that avoiding loops in a scheduler is a good thing (since it is likely to lead to implementations that don't scale well) but prohibiting them is not a good thing. Likewise, pointers are a very useful tool. If they have implemented a list manipulation toolkit that handles most of the pointers for you, that is a good thing but eliminating the ability to handle pointers is a bad thing. Sophisticated schedulers might want to do things like launch their own priviledged subprocesses which monitor performance.

Remember an obsolete language called Pascal? Pascal tried to use an Orwellian Newspeak approach to making poor programmers into mediocre programmers by taking away the means to express dangerous ideas. It also turned excellent programmers into mediocre programmers. I remember when it seemed like the majority starting projects were using Pascal but I also noticed over the heydey of Pascall that the majority of projects that were succesfully completed were written in C. I also remember when a simple change (at least in C) to a Pascal program doubled the size of the program and had a substantial negative impact on its maintainability.

Another analogy is Javascript. The core language (ECMAscript) is deliberately so weak that about the worst thing you can do is waste cpu cycles with an infinte loop. It was deliberately weak because it was intended to run code provided by untrusted users. Then they incorporated access and control over the behavior of the browser giving the scripts the ability to take over the screen, steal private information, and perform cross domain hacks. There have been something like 500 security holes reported in Javascript. Well, DML is kinda like that. The language is so weak that you can't hurt yourself until you actually give it control over process scheduling, its original intended purpose. At which point it becomes trivially easy to crash the machine. DSL is like an unloaded gun, it gives you a false sense of security.

The Bossa DSL schedulers could be rewritten - almost line for line - in a subset of C with the Bossa list handling tools. If you wanted the illusion of safety that DSL provides, you could restrict yourself to that subset. If, on the other hand, you were an expert programmer, the full language is availible. And you don't polute the kernel tree with the implementation of an entirely unnecessary language.

Now, they have done some good things here. Loadable scheduler modules. Separating queue linked list handling from the actual kernel code. Defining an event based API. Allowing for more than one scheduler. And abstracting the scheduling enough that you could write a user space test pro

Re:infinite loops

[schwaang]

Gadzooks, man. I don't have time to read the book you just posted, but I'll tell you one thing DSL shows is how lacking C is in expressing Finite State Machines.

Like 15 years ago IBM had a language called FAPL which was cool at expressing FSMs -- totally useful for describing commmunications protocols or, in this case, scheduling protocols.

But FAPL would probably make you sh*t bricks after your palpitations over DSL.

PS -- I'll bet you're not really precluded by DSL from scheduling a task every 100 bogons to re-prioritize the queue. But don't look into it any further without adjusting your meds first.

Re:eeek (OT)

[slashjames]

Working with semaphores and locks... *shudder* keep the bad man away!!

Just remember that it's those semaphores, mutexes, and locks that allow multi-threaded applications work. A class that is supposed to be "thread safe" but isn't will make your life rather... interesting.

MOD PARENT UP

[Anonymous Coward]

This guy gets it. MisterFancypants is just looking for excuses to complain. The article never implied that ordinary users should care about, or even know about, scheduling. What it says is that scheduling algorithms are important for ordinary users. There is a world of difference between these two statements.

Re:MOD PARENT UP

[Anonymous Coward]

Yup. Looking at your posting history you're in need of it..

Re: locks &semaphores, "nothing I hated more"

[nusratt]

"Working with semaphores and locks... *shudder* keep the bad man away!!"
http://slashdot.org/comments.pl?sid=11388 0&cid=964 7043

Actually, it's quite interesting. It forces you to conceptualize with a certain kind of rigor, and to code with particular vigilance for potential deadlocks, race-conditions, and mis-serialization of resource-updates.

I can't tell you the number of times that I've read or listened to a description of a design or architecture, and immediately said "uh-oh", to the surprise and dismay of developers who really should know better.

In a time of increasing processor parallelism, this is a skill-set which must be mastered by anyone who truly aspires to become (or remain) a serious professional-level developer. It's not just for kernel-hackers.

schedulers as modules

[rsd]

Using a plugin^Mmodule interface to load schedulers at runtime wouldn't generate
a performance impact in the scheduler? (as opposed to have the scheduler compiled
inside the kernel).

I AFAIK, the scheduler has to be as compact (optimized) as possicible to reside as long as possible
in the cpu's cache. This way it can check the memory pages map as fast as possible to [de]allocate,
switch process as fast as possible.

Using a module scheduler, wouldn't make it have to derreference each function address each time
each function is called?
And probably sometimes derreferencing derreferences few times to get the correct address?

Couldn't this hurt performance?

I agree that loading an efficient scheduler to handle a situation better than the defalt scheduller would
compensate for that, but still...

Re:schedulers as modules

[pkhuong]

If the modules are binary, the point is moot. If they're not, remember that a DSL can often encode the same functionality in less space (interpreter+data) than machine language. As you pointed out ourself, cache hitrate are extremely important, so by having less data to cache (and less new instructions to decode), the interpreter can probably be very competitive, or maybe even better than a binary.

Java has a different approach to scheduling

[soroka]

The problem of multimedia apps running smoothly affects not only OS kernels, but also things like Java machine. Since Java is taking more serious tasks nowadays from streaming media in handhelds to (they say) NASA Mars rovers.

With Real Time Java a programmer can request explicit timing guarantees, by direct interaction with the scheduler. Just derive your threads from javax.realtime.RealtimeThread (if it is implemented in your version of Java :)

Re: locks &semaphores, "nothing I hated more"

[firelord84]

It frightens me when so many "programmers" or "software engineers" seem to be frightened by or even oblivious to concurrency problems. This should be a fundamental skill anyone writing software should have. Are there schools out there not teaching these basic concepts somewhere in their degree program?

Jar Jar Binks, the scheduler framework

[gc8005]

Sorry, but the name Bossa immediately invokes thoughts of Jar Jar Binks, as in : "Yousa Bossa. Jar Jar Binks thinka massa need a process."

Re:who cares

[angulion]

Either way---say what you will, but windows has always been more responsive on the desktop.

And Linux has been more responsive in the server-room. A server doesn't even need a desktop.
A desktop user like you might not care if your scheduler degrades after you have 800 processes running, but I can assure you people dealing with large server systems does.
Windows is in large part more responsive on the desktop since it is in part intergrated into the kernel - the downside being that what would be a application crash can bring down the whole OS. Also you have less privilege separation. (windows desktop is "unsafe" area, but that is another story).

(What directX equivalent is there on Linux?)

OpenGL, SDL, OpenAL for starters. Guess what they all can do that DirectX can't?! Yepp, run on different systems and architectures, be it Linux, Windows or a Mac.

If Linux developers don't stop diddling around with something that was solved years ago, Linux will just go away.

Linux developer base is quite large and the developers like to "diddle" around to find the best/most effective solution, not the one that takes the least amount of time to make, like it often tends to be when deadlines are pushed in companies.

Linux doesn't even have a program that can do half of what programs like dreamweaver can do.

I admit that there is nothing quite like dreamweaver for Linux, but I'm convinced that Quanta can do more than half. :P Anyway, as Linux gets more acceptance, programs like Dreamweaver will eventually be ported.. what will you say then?

For the developer, what app is as integrated as Visual Studio? KDevelop? Pshaw.

Are there any development tools that is more restricted to one platform and project management than VS?
KDevelop and Anjuta might not be as integrated, but they can use CVS, SubVersion etc. and compile on Linux even for Windows (or the other way around). Oh, and they are free.

I'm not flaming you---but the article. Users don't give a shit about schedulers if there's no applications with them.

No, not at all :P
You know, there are alot of people that acctually are interested in kernel-schedulers, allthough they do not tend to be your average desktop user.
More over, one place where schedulers matter most, ie. in servers, there is absolutely no shortage of applications on Linux.. I'd more like to say there is a shortage of applications in this are for Windows, if anything.

Re:Linux has proven you wrong

[shaitand]

I think I'll take the reboots every few years over the 20-30% "minimal" performance loss that comes along with your academic microkernel tyvm.

Re:who cares

[shaitand]

In a way it is... in the same way that writing a custom iptables script is like checking the box to enable software firewall on this connection in windows ;)

Re: locks &semaphores, "nothing I hated more"

[Achoi77]

Wow, I'm definately out of my league here. In the class I was referring to above, our prof made us create a pseudo os that would be able to handle multithreaded apps that my prof made up. The last app he made had multiple consumers, multiple producers, multiple resources, and totally inane production/consumption restrictions. My team was one of three (out of 24) that got that last one working perfectly. In any case it was very unpleasant experience (I suppose the time limit didn't help either).

In my experience semaphore programming can get really really complicated, and if they didn't have to, I'm sure a lot of other programmers out there would rather not work with them either. I'll leave that up to the really smart people. :-)

Re:eeek (OT)

[eman_2112]

Not knowing what "semaphores, mutexes, and locks" are in a scheduler, I still have to ask how a scheduler can make a "'threadsafe' but isn't" class be "safe"?

Elove the scheduler naturally

[kentsin]

I hope I coule use Generate algorithms to find out the best scheduler for the system.

Re:Elove the scheduler naturally

[MarcQuadra]

Well if the 'genetic' algorithms produce anything like me or my cat, you'll be waiting a LONG time for anything to get done. Four billion years of evolution and all I did today was lay in the sun.

When this is new

[rfc1394]

Any errors that occur, all that will be able to be said is, "Blame it on the Bossa Nova." (Long groan follows.)

Re:Linux has proven you wrong

[stor]

Each time you reboot for a kernel upgrade, academics have proven Linux wrong.

OK so explain Windows NT.

Cheers
Stor

Confused

[The Grassy Knoll]

The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems. This article gives you a glimpse of what scheduling development is like by letting you implement your own Linux scheduler thanks to Bossa, a framework for scheduler development.

I'm a bit confused... Is this about scheduling??

Re: locks &semaphores, "nothing I hated more"

[firelord84]

I will agree with you there. Concurrency problems can get very complicated. So long as you are aware of the problem you've won half the battle. From your past experience you should be well prepared to handle future concurrency problems that arise.

realisitic audio processing

[Doc Ruby]

The smaller, more "agile" nanokernel could offer better interrupt handling and more granular CPU/memory accesses, therefore keeping more accurately on a realtime track. But for high-throughput realtime signal processing, another computing model is probably more appropriate: truly parallel logic arrays.

True parallelism means the that clock rates don't have to be jacked up to millions of times the rate of the events being processed (eg. 100s of GHz for 10s of KHz audio), just to ensure that thousands of thousands of instructions might be performed on hundreds of sequential tasks required to appear simultaneous. Routers already use FPGAs to handle these kinds of tasks, running at 100s of MHz on 10s of MHz of packets (eg. OC-192 routing). Once software development tools are high-level enough to allow many music-literate programmers write studio software, some winners will float to the top. The recent development of uCLinux for the MicroBlaze "soft processor" running on a Xilinx FPGA, with extra gates to spare, offers a really exciting platform for the transition. Why not get started porting your favoring Linux sound tools to uC/MB, and strike up the band?

Impact of scheduling on threads

[ThePhin]

Xavier Leroy is one of the authors of Ocaml, an efficient (within 2x of C) variant of the ML functional programming language. In the Caml-list mailing list recently, he had this to say about scheduling:

The 2.6 Linux kernels changed the behavior of sched_yield() in a way that causes the unfairness you observed. Other threaded applications are affected, including Open Office (!). My belief is that it's really a bug in 2.6 kernels and that the new behavior of sched_yield(), while technically conformant to the POSIX specs, lowers the quality of implementation quite a lot.

(I seem to remember from my LinuxThreads development days that this isn't the first time the kernel developers broke sched_yield(), then realized their error.)

The question I'm currently investigating is whether the call to sched_yield() can be omitted, as it's just a scheduling hint. Initial experiments suggested that this would hurt fairness (in Caml thread scheduling) quite a lot on all platforms other than Linux 2.6. More careful experiments that I'm currently conducting suggest that it might not be so bad. One can also play games where sched_yield() isn't called if there are no other Caml threads waiting for the global Caml mutex.

So at least one class of user is forced to be aware of the scheduler, to refer to another poster's assertion that users shouldn't even need to know...

Re:Impact of scheduling on threads

[Bloater]

> So at least one class of user is forced to be aware of the scheduler, to refer to another poster's assertion that users shouldn't even need to know...

For some info on sched_yield:

Sched_yield is intended to allow a non-preemtive system to give other processes a go. You call it when you are using the cpu in a long running calculation. You *ought* to use it in every such case. A smart pre-emptive scheduler will ignore it, and a dumb non-pre-emptive one will round robin to another process.

While it should not be used to simply spin with a 0-overhead delay inserted, there is little difference between spinning and simply being very conscientious.

A spinning process that's checking the completion status of a parallel task should preferably be recognised as such and given CPU like any CPU bound task (since it should have just blocked instead). A CPU bound task that is being concientious for the sake of non-pre-emptive systems should be treated, similarly, just like any other CPU bound task. OpenOffice.org and Ocaml have to wait too long for their next CPU quantum, but that's because they are CPU bound tasks and it's their own fault.

The bug was in past versions of Linux where, although it was pre-emptive, sched_yield was allowed some power - it should have been ignored in user-space and the scheduler decided what gets CPU and when. Depending on that bug is also a bug and the mis-users deserve everything they get.

Re:Impact of scheduling on threads

[Bloater]

My post is self contradictory :)

Actually, it's not self contradictory since I didn't claim that Linux does not now withdraw a CPU quantum... It was just wrong. However, the process will only lose its CPU slot if there is something else that needs the CPU, so the current Linux scheduler is not wholly crap, just a bit crap.

one question

[dedalus2000]

Does this mean there will be a realtime Linux that's not just a kernel running on top of a small proprietary realtime kernel like rtLinux currently is?