The Completely Fair Scheduler

hichetu writes "Kernel trap has a nice summary of what is going on behind the scenes to change the Linux Scheduler. The O(1) Linux scheduler is going to be changed so that it is fair to interactive tasks. You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks."

Comments

Isnt this called Cron ?

[Anonymous Coward]

I thought Linux used Cron as a scheduler ?

Re:Isnt this called Cron ?

[ozamosi]

That is for scheduling background tasks that run once a day (or whatever you set it to)

This is for scheduling CPU resouces in real time. To decide if Firefox or Apache is going to be executed the following split second.

Re:Isnt this called Cron ?

[LiquidCoooled]

Can't we just give the processes weapons and let them decide which follows?

Re:Isnt this called Cron ?

[sphealey]

> Can't we just give the processes weapons and
> let them decide which follows?

That is actually the kind of question that my Operations Research professor (who also did a lot of work in CPU simulation and performance estimating) used to throw onto final exams as the "separate the B+ from the A" question. If your answer was interesting enough he would send you over to one of his Masters candidates to see if it could be taken any further. So I wouldn't count your suggestion out from the start!

sPh

Re:Isnt this called Cron ?

[HerrEkberg]

Just throw this into the kernel and we are good to go.

Re:Isnt this called Cron ?

[Watson Ladd]

Exokernels hand over a lot of the scheduling to the processes themselves.

Re:Isnt this called Cron ?

[Jah-Wren Ryel]

> Can't we just give the processes weapons and
> let them decide which follows?

That is actually the kind of question that my Operations Research professor (who also did a lot of work in CPU simulation and performance estimating) used to throw onto final exams...

Operations Research being closely related to Industrial Engineering, your prof proves the old joke about how IE's are Imaginary Engineers.

Re:Isnt this called Cron ?

[Progman3K]

Yes, that's called psDoom
http://psdoom.sourceforge.net/

Re:Isnt this called Cron ?

[Anonymous Coward]

Coming up with an idea (even if totally made up) and the backing it up with arguments is much harder than memorization and regurgitation and actually backing it up with things having to do with that class shows you have learned something, or at least know about the concepts discussed in the class.

Re:Isnt this called Cron ?

[Lars T.]

So the first scheduled process kills -9 all others - makes scheduling and multi-tasking kinda pointless.

Re:Isnt this called Cron ?

[KDR_11k]

In school they told us exactly that, doesn't matter if your conclusion is wrong if you argue it right.

Re:Isnt this called Cron ?

[sphealey]

That guy was actually the best test writer and overall course designer that I have ever had among all the academic (through a masters) teachers and corporate trainers I have encountered. When you finished his course you received exactly the grade you deserved according to the formal definitions of the grades; as you indicate one didn't receive an A in that class unless one actually _understood_ the material [for the record I was in the B+ group ;-( - which was a correct evalution]. Not surprisingly it also turned out to be one of the most useful classes I ever took as well.

sPh

Re:Isnt this called Cron ?

[theonetruekeebler]

Okay -- Since I'm not allowed to drink beer in class I'll just have to post this from home.

Want to give each process a weapon? Fine. But they have to earn ammunition.

Every time a process gives up its slot, it's given a round of ammunition. It has the option of "shooting" a process ahead of it in the queue, thereby expending a round of ammunition. A shot process must give up its slot in the next round. Whether it loses all its ammo when it respawns remains a research question.

There are two floating point tunable parameters, "accuracy" and "rampage." "Accuracy" is the likelihood that a given shot will actually hit the process it aims at. "Rampage" is the tendency of a process to save up rounds for a while then go on a spree.

Okay, there's a third parameter, "armor," which is the odds of a hit actually becoming an injury. This is meant to protect system processes against luser jobs, and top-level processes against spawned threads.

Of course, the scheduler itself is a boss job that can't be killed, has perfect armor and has infinite ammo.

For the purpose of top and other job monitoring tools we can replace a process's "NICE" score with a "VIOLENCE" score -- an aggregate of their armor, accuracy, rampage tendencies and current ammo supply. We can rename the renice utility to medicate. The important thing about medication is that it eventually wears off, unless you specify the -l (lobotomize) option, which turns the process into a harmless drooling vegetable. Its companion utilities are aim and armor, which tune a job's accuracy and armor class, respectively.

There are two important things about this approach. First, it's probabilistic instead of purely heirarchical. Second, it should give Jack Thompson the screaming heebie jeebies. In fact, I'm going to call this the JTMS scheduler -- the Jack Thompson Murder Simulator Scheduler.

I'm sure this concept can be explored further, but the bar's about to close.

Re:Isnt this called Cron ?

[jd]

It's called Corewars, but nobody has implemented a decent OS in redcode.

Re:Isnt this called Cron ?

[kasperd]

Can't we just give the processes weapons and let them decide which follows?

Wasn't that more or less how scheduling worked in Windows 3.x?

Re:Isnt this called Cron ?

[timelorde]

You know you've been here too long when you can remember when that was first published...

Re:Isnt this called Cron ?

[Eli Gottlieb]

It's funny because it's in hideously bad taste.

In Soviet Russia, processes work out their differences peacefully.

Re:Isnt this called Cron ?

[smittyoneeach]

You mean this was the "old school" where you were graded on the basis of something they used to call "learning".
"Progress" has saved us all of that stress and ambiguity.
Now, you just pay a small mountain of cash for tuition, and walk away with your "A".
It's all about efficiency these days.

Re:Isnt this called Cron ?

[kcbrown]

For the purpose of top and other job monitoring tools we can replace a process's "NICE" score with a "VIOLENCE" score -- an aggregate of their armor, accuracy, rampage tendencies and current ammo supply. We can rename the renice utility to medicate. The important thing about medication is that it eventually wears off, unless you specify the -l (lobotomize) option, which turns the process into a harmless drooling vegetable. Its companion utilities are aim and armor, which tune a job's accuracy and armor class, respectively.

Of course, with such a scheduler, something like the Doom system administration tool (perhaps more like Quake where you can aim vertically as well as horizontally) will become the preferred method of managing the processes on a system.

For one thing, the processes will obviously shoot back, as the process manager itself (which you see as yourself when running it) is a running process, and thus subject to being fired upon by the other processes.

Secondly, a headshot obviously gets you a "lobotomize" effect. This could pose a problem if one of the other processes hits you with a headshot...

Finally, the application of a medpack to an injured process invokes the "medicate" action.

There are a few possible problems with this, of course:

1. When you have two or more system administrators, all running the process manager, the system itself becomes a warzone with innocent processes being killed by the dozen as the administrators go on rampages in their attempts to kill each other for supreme control of the system.
2. Certain weapons, such as the BFG, are powerful enough to take out all but the most heavily armored processes, and since some of them are area effect weapons, a lot of innocent processes will bite the dust as a result of their usage.
3. Lightly-armored processes will need additional protection in the form of fast reflexes to avoid being hit.
4. Eventually the administrators will begin using aimbots and the like. One can see where the resulting arms race will go. Obviously the aimbots will have to run on a different system since otherwise they'll be potential targets.
5. "Spawn camping" takes on a whole new meaning. Newly created processes become very vulnerable compared with running under earlier versions of Linux. Normal users will have an increasingly difficult time starting tasks like OpenOffice and will start to migrate back to Windows or other OSes with clearly inferior schedulers.
6. Due to all of the above, the system will eventually become unusable by anyone but the system administrators. The sysadmins will, of course, say that this is how it should be.

In short, Linux will quickly become the must-have operating system for gamers, but at the expense of the general purpose desktop.

Re:Isnt this called Cron ?

[fishbowl]

>I thought Linux used Cron as a scheduler ?

To be fair, this is one thing that qualifies as jargon.
I expect anyone who claims to have a CS degree to have written three parts of an OS, the Scheduler, the Virtual Memory, and the Filesystem, in one of the classes they took in their senior year.

I don't expect anyone else to know what a scheduler is or what it does.

Essentially, the scheduler is the system process that breaks up all the various programs that want a piece of the CPU, and lets them run. It's the component that makes "multitasking" possible.

There are quite a few issues, and compromises that must be made depending on how a system is used. For example, there are scheduling algorithms that will get a lot of jobs completed in a relatively short time, but will make any interactive processes unusable. And then there are scheduling algorithms that will very efficiently switch between processes making it seem to the user as though multiple programs are running at the same speed as a single program. And then there are algorithms that detect the runtime conditions and adapt.

You got modded up to "funny" so I guess I should have assumed you were trolling.

Re:Isnt this called Cron ?

[Syberghost]

Of course, the scheduler itself is a boss job that can't be killed, has perfect armor and has infinite ammo.

Fascist!

Re:Isnt this called Cron ?

[Profane MuthaFucka]

Russian vodka scheduler? Processes which are not too drunk to run get scheduled. If you receive a network packet, take a drink. If you do a system call, take a drink. If you call sleep(), take TWO drinks. Computer runs like Soviet Union runs, and likes it too.

Re:Isnt this called Cron ?

[BrokenHalo]

Heh. I don't want my kernel's scheduler to be fair. The hell with "fair". "Fair" is for quiche-eaters. I want it to give ME all the resources I need to get whatever I'm doing done before I even think of it. Any other job can just go jump on its head... ;-)

Re:Isnt this called Cron ?

[BrokenHalo]

Just throw this into the kernel and we are good to go.

Just goes to show how suspicious I'm getting of Slashdot lately - my first reaction was to check that "this" wasn't tubgirl.jpg.

Eeurgh. Wish I hadn't thought of that...

Re:Isnt this called Cron ?

[Short Circuit]

With the prevalence of virtualization, it may now be time for a redcode-to-asm compiler. (You'd have to have a thin, very thin kernel for monitoring and scheduling purposes, though.)

Re:Isnt this called Cron ?

[Anonymous Coward]

> Heh. I don't want my kernel's scheduler to be fair. The hell with "fair". "Fair" is for quiche-eaters.
> I want it to give ME all the resources I need to get whatever I'm doing done before I even think of it.
> Any other job can just go jump on its head...

I recommend DOS!

Either that or classic Mac OS - you can completely take over the computer from the OS, which is in fact how MkLinux and A/UX are booted.

Re:Isnt this called Cron ?

[DrSkwid]

> You got modded up to "funny" so I guess I should have assumed you were trolling.
Does "joking" not enter your vocaubulary ?

> I don't expect anyone else to know what a scheduler is or what it does.
This isn't quite http://digg.com/ yet, there are other people on the site that understand computers other than you!

Re:Isnt this called Cron ?

[shaitand]

'Coming up with an idea (even if totally made up) and the backing it up with arguments is much harder than memorization and regurgitation and actually backing it up with things having to do with that class shows you have learned something, or at least know about the concepts discussed in the class.'

Sure. It demonstrates that you've learned something and that you are a quick thinking and creative person. Your writing ability also plays a major role.

Unfortunately, you could learn the material without being creative, quick thinking, or a good writer. If you are this unfortunate sole you just got a lower grade. Grades are supposed to demonstrate understanding of the course material, not how bright you are.

Re:Isnt this called Cron ?

[Khazunga]

Unfortunately, you could learn the material without being creative, quick thinking, or a good writer. If you are this unfortunate sole you just got a lower grade. Grades are supposed to demonstrate understanding of the course material, not how bright you are.

It's a philosophical question, with no correct answer, but I don't think grades should evaluate the understanding of a course. Grades should evaluate the ability to *use* the material of a course. This is beyond understanding. A student who completely understands a course should get a B. An A-level student is one who grasps the course material so well that he builds on it to produce other conclusions.

If you lack skills needed to compound your understanding of the material, tough luck. A B is not a poor grade...

Re:Isnt this called Cron ?

[shaitand]

'Grades should evaluate the ability to *use* the material of a course.'

I disagree. That falls back to a measure of the intellect of the individual. That will play a role after school but you don't go to school to demonstrate your abilities or use material, you go to learn material.

'An A-level student is one who grasps the course material so well that he builds on it to produce other conclusions.'

I agree with that. Someone who has a fully grasp of the material understands it well. As I said, the grade should reflect understanding of the material that you took the course to learn. It should not reflect intellect (beyond that required to understand said material), creativity, etc.

'If you lack skills needed to compound your understanding of the material, tough luck. A B is not a poor grade...'

I never said a student with a more thorough understanding of the material shouldn't get an A. I said the A shouldn't be reserved for the quick thinking creative writer who can make up nonsense on the spot for a test question. The slow methodical student may have greater insight into the material but be less creative.

This is the same faulty logic that leads to essays and papers as a measure of understanding. Papers do demonstrate understanding but they aren't the best tool to do so. If papers are primary method used to measure understanding then you aren't ultimately measuring comprehension of the material, you are measuring writing ability.

Re:Isnt this called Cron ?

[Miseph]

No, in Windows 3.x some of the users got weapons, and none of their computers survived long enough to schedule much of anything.

Re:Isnt this called Cron ?

[Kupek]

It's funny only if you're not in the Computer Science Department at Virginia Tech.

Re:Isnt this called Cron ?

[jgrahn]

Can't we just give the processes weapons and let them decide which follows?

Crom!

Re:Isnt this called Cron ?

[Khazunga]

That falls back to a measure of the intellect of the individual. That will play a role after school but you don't go to school to demonstrate your abilities or use material, you go to learn material.

And herein lies our disagreement. The grade you get in school should reflect your potential once you get out of school into the real world. As an employer, I should be able to rely on a recent graduate's grades to predict the ability to perform. This ability to perform real tasks in the real world calls for a complete evaluation of an individual's intellect. Is it difficult to measure intellect? Yes, very much. Should schools quit trying to do so? Absolutely not.

School grades aren't a contest, with rules providing an equal opportunity environment. They are the evaluation of an individual by the faculty, against the relevant matters he/she will need to perform in the future work environment.

Re:Isnt this called Cron ?

[NateTech]

I've seen some processes (JVM!) that apparently were armed to the teeth and willing to take up the entire CPU at the cost of bringing down the host OS. You underestimate their ability! :-)

Re:Isnt this called Cron ?

[shaitand]

'And herein lies our disagreement.'

Indeed.

'As an employer, I should be able to rely on a recent graduate's grades to predict the ability to perform.'

But the purpose of school or any EDUCATIONAL facility is to educate, not to gauge ability for third parties or to prepare one for the workforce. You might hope that having knowledge will help you get a better job but universities exist for the benefit of the educated, not their future employer. Grades are a way of determining whether or not someone has learned the material well enough to advance, not to convey information to employers or anyone else.

You could make an argument that a trade school could be bent to fit your ideas. Professional certifications and courses from them are also designed to send a message to employers.

University diplomas and the grades that go along with them are simply being misused. Schools exist to better oneself and to convey knowledge. If having knowledge makes you employable its a side-effect. This would be true even if every student chose to better themselves as a means of employment/higher pay whoring. In fact, almost every student goes for that reason and its sad.

Re:Isnt this called Cron ?

[__aaclcg7560]

You could use a grenade to blow up the zombie at the risk of segfaulting the kernel.

Re:Isnt this called Cron ?

[Hal_Porter]

In the Bible Jesus said "Blessed are the meek, for they shall inherit the Earth", and I think He was right.

Applying this to process scheduling, processes that have not run for a long time should be given a priority boost.

Jesus also said "It is easier for a camel to pass through the eye of a needle than for a rich man to enter the kingdom of heaven"

I think in scheduler terms this means that processes which are taking an unfair amount of CPU time should have their priority lowered.

So you see the Holy Bible has lots of inspiration for the writers of OS kernels, not just for people who write text editors.

And now a reading from The Book Of Mead, Chapter 80 Verse x86.

Re:Isnt this called Cron ?

[Filip22012005]

Heh. I don't want my kernel's scheduler to be fair. The hell with "fair". "Fair" is for quiche-eaters. I want it to give ME all the resources I need to get whatever I'm doing done before I even think of it. Any other job can just go jump on its head... ;-) Don't worry, Windows ME will indeed take all available resources.

Re:Isnt this called Cron ?

[Khazunga]

But the purpose of school or any EDUCATIONAL facility is to educate...

And the purpose of education is to provide society with more productive individuals

... not to gauge ability for third parties or to prepare one for the workforce.

If the final objective of education is productivity, the evaluation of the result of education should target the final objective: the expected productivity of an individual.

There are some 'pure' degrees that defy this logic, namely philosophy degrees. Most degrees, though, are meant to result in increased productivity of the student when he's out in the workforce. An engineers' degree should prove that an individual can build a long standing bridge, not that he understands the math behind force propagation. He must understand and *apply* the knowledge. Applying knowledge inevitably calls for abilities not formally taught in school benches. Hence, an engineers grade should reflect his ability to design and build stuff.

Re:Isnt this called Cron ?

[shaitand]

'And the purpose of education is to provide society with more productive individuals'

False, the purpose of education is to benefit oneself. Now if society wants to pay for that education society can have some say, until then it has nothing to do with society.

'If the final objective of education is productivity'

The final objective of education is to be educated. In other words, you learn for the purpose of gaining knowledge, no more, no less.

'An engineers' degree should prove that an individual can build a long standing bridge, not that he understands the math behind force propagation.'

A structural engineers degree should prove that an individual KNOWS HOW to build a long standing bridge and understands how it functions. His grade gives his instructors markers to show how well he is understanding the material as he progresses and whether he is ready to proceed to further instruction. How well he can actually apply said knowledge is something you discover the first time he attempts to apply said knowledge. If you are using a grade as a substitute for actually testing ability you are probably tossing your best candidates. How well an individual can come up with a line of plausible sounding nonsense and phrase it convincingly in a written selection tells you NOTHING about how well that individual can build a bridge. Perhaps the creativity will give you a concept of how pretty a bridge he will design but that is about it.

'Applying knowledge inevitably calls for abilities not formally taught in school benches.'
'There are some 'pure' degrees that defy this logic, namely philosophy degrees.'

There could possibly be a reason for that.

Re:Isnt this called Cron ?

[suckmysav]

If you want that then take a look at Win9x and its non-premeptive scheduling. Ever wonder how a misbehaving app can completely lock a system?

Re:Isnt this called Cron ?

[suckmysav]

And yes, I do realise you were making a joke.

Re:Isnt this called Cron ?

[losec]

Welcome to psdoom !

Re:Isnt this called Cron ?

[Khazunga]

False, the purpose of education is to benefit oneself.

Oh, the lyric view... Ask yourself: How many of medical school students don't plan on recovering the 180k tuition fees applying the knowledge gained in school? The purpose of the majority of courses is to increase productivity of students. If that's the purpose, the grade should reflect students' score in the course purpose.

The rest of your logic is flawed by this false premise.

Re:Isnt this called Cron ?

[shaitand]

'The purpose of the majority of courses is to increase productivity of students.'

Still false. That may be the reason the students have chosen to benefit themselves but what has motivated the students is irrelevant. The students could be going because they desire knowledge, because there is something they want to accomplish, because of some good they hope to do in the world, or good old fashioned greed. None of that changes the purpose of the institution. The institution exists to TEACH the students information.

Re:Isnt this called Cron ?

[Khazunga]

That may be the reason the students have chosen to benefit themselves...

Not 'may be'. That is the reason, for the majority of students, if only because of the pressure created by university fees.

... but what has motivated the students is irrelevant.

Far from irrelevant, it's the drive that sends students to the universities, which is important, because:

None of that changes the purpose of the institution. The institution exists to TEACH the students information.

You leap unfounded to this conclusion out of personal belief. The students motive challenges this affirmation. Universities without students make no sense, so the objective of the university is aligned with that of the students, under penalty of an empty, and thus bankrupt, university. Again, if the objective of the university is to increase productivity, the system output (grades) is correlated to the final objective.

It's simple logic which you have never contradicted, relying instead in faith to support your point. Faith is a poor logic fellow.

Re:Isnt this called Cron ?

[shaitand]

'It's simple logic which you have never contradicted, relying instead in faith to support your point. Faith is a poor logic fellow.'

Hardly, your premises are not valid and therefore the logic that relies on them is invalid. I don't need to depend upon faith because I am correct by default. I am claiming nothing more than that a university is what the dictionary, society, and the universities themselves claim to be; an institution of HIGHER LEARNING. If your logic were proven valid then university would be synonymous with trade school and trade schools would simply offer different classes.

'The students motive challenges this affirmation.'

The students motive is again irrelevant. Further, you have not proven what the students motive is.

"
'That may be the reason the students have chosen to benefit themselves...'

Not 'may be'. That is the reason, for the majority of students, if only because of the pressure created by university fees."

Either it is the reason and every student has the same motivation or it may be the reason. If its the reason for a simple majority then it is 'may be'. Simply restating this is another way doesn't make your point stronger. Not that it matters, because again, the motivation of the students is a strawman argument since the students do not define what a university is.

"
'None of that changes the purpose of the institution. The institution exists to TEACH the students information.'

You leap unfounded to this conclusion out of personal belief."

You are right, except for the unfounded part. I have personal belief in the ability of the dictionary to give me an accurate definition of a word. Like the word university, which is defined by Merriam-Webster as:

1 : an institution of higher learning providing facilities for teaching and research and authorized to grant academic degrees.

Or School:

1 : an organization that provides instruction
2 : Omitted because it defines school when used in a different way, by this definition I am schooling you now.
3 : a source of knowledge

And of course teach, which you seemed to think means something other than imparting knowledge:

1 : to cause to know something

I believe that determining the purpose of a university or school is as simple as looking up the meaning of the words university and school. If we discuss an institution with a different purpose then it isn't a university and a school. Students do not define the words university and school and neither do their motivations. At least they don't define them anymore than the rest of us. Sorry, once again, universities do not exist to make life easy for employers.

'Universities without students make no sense, so the objective of the university is aligned with that of the students'

This is a leap you are making out of personal belief. Universities without students make no sense to you because they are impractical. They are universities just the same. You say a car wash without customers makes no sense. I say a car wash without customers is an entity that exists for the purpose of washing cars. That is what a car wash is. The car wash might have been created because someone hopes a car wash will make them money, and they might adjust the policies of said car wash, even open and close said car wash based upon how well the car wash succeeds in their goal. If the car wash stops washing cars and starts selling peanuts it becomes a peanut vendor, even though the goals of its owners have probably remained the same. Practicality and utility to do not define.

Further, even if universities without students make no sense, that doesn't mean the objective of the university is magically aligned with that of the students. The objective of the university remains the same whether there are any students or not. Like the car wash policies might change to attract students with different objectives, but when the objective of the university changes it will no longer be a university.

'under pena

Re:Isnt this called Cron ?

[Khazunga]

This thread has gone long enough. Let's agree to disagree. I completely understand your position. I believe you are wrong, but can't for the life of me make you see another perspective. I come from a family of teachers, know several universities, both public and private, from the inside. I have taught in one for a few years. Believe me when I say the economic stand is prevalent among universities -- at least in Europe.

The economic stand invalidates lyric positions. The lyric position, the one you defend, does exist. It has its proponents. Universities which followed a lyric view in its market positioning have lost the competitive edge. Having failed to attract top students and investigators, they invariably fall in quality level. Top universities know they must attract top students, so adapt themselves to that requisite.

Last but not least, please re-read M.W. definition of university against my texts. I never state an University isn't an institute of higher learning. I state that the higher learning provided by universities isn't hollow. It has a purpose, which is to add value to the students. That is not the sole purpose, but our discussion was centered in what is measured by a grade in an university course so that's what I focused.

Re:Isnt this called Cron ?

[shaitand]

'I come from a family of teachers, know several universities, both public and private, from the inside. I have taught in one for a few years.'

That makes you part of the problem. It isn't something I would be proud of in your shoes. I am self-employed. I attended a University. The knowledge I gained there makes your appeal to authority in lieu of an argument fairly transparent.

It really isn't much of a surprise. Your stance is essentially that of the conservative party in American politics and usually devolves to nothing but rhetoric in the end. I had a number of fathers (I don't care to explain) one of them firmly believed in the conservative view of economics and life in general. The most valuable piece of wisdom he ever imparted to me was something his father had told him. He said that life was a big game and shekels were how you keep score. When he had a stroke and no longer was able to earn shekels he found out his so called friends were only interested in his shekels and he ultimately died alone.

Life is not a game, life is absurd but devoid of meaning. There is no goal or purpose unless you make one up. Shekels aren't a very fulfilling goal.

'I state that the higher learning provided by universities isn't hollow. It has a purpose, which is to add value to the students.'

Certainly and I agree with this statement entirely. A University is a hardware store. As a student I go to the University to get a tool knowledge (a wrench). My grade should reflect the quality of the wrench (the knowledge gained in a class). Now I might tell the hardware store that I am working on a certain project and want them to give me the right set of tools, I might not. Once I have the right set of tools I have more capabilities and am therefore more valuable, both to myself and others. I may choose to sell that value to someone else, utilize it for myself, or use my tools to devise and craft yet more tools. What I plan to do with my tools might define which tools I get but it doesn't have any impact on the quality of the individual tools (again, my grade in an individual class).

'I completely understand your position. I believe you are wrong, but can't for the life of me make you see another perspective.'

Non-sense, my understanding of your position has been demonstrated in the process of thoroughly debunking it. It doesn't hurt to recognize how things currently are, to follow the prevalent thoughts that makes them that way, and to be a realist in general. But one should never lose sight of how things should be. After all, all things change and move forward. How do you know which direction to go if you lose sight of the ideal?

Re:Isnt this called Cron ?

[Khazunga]

'I state that the higher learning provided by universities isn't hollow. It has a purpose, which is to add value to the students.'

Certainly and I agree with this statement entirely. A University is a hardware store. As a student I go to the University to get a tool knowledge (a wrench). My grade should reflect the quality of the wrench (the knowledge gained in a class). Now I might tell the hardware store that I am working on a certain project and want them to give me the right set of tools, I might not. Once I have the right set of tools I have more capabilities and am therefore more valuable, both to myself and others. I may choose to sell that value to someone else, utilize it for myself, or use my tools to devise and craft yet more tools. What I plan to do with my tools might define which tools I get but it doesn't have any impact on the quality of the individual tools (again, my grade in an individual class).

My bad. I should have said "It has a purpose, which is to add market value to the students.". You see, western civilizations are capitalist. Most of what we do as a society is driven by the market. Universities are no exception, much as you'd like it to be otherwise.

Is it hollow and unfulfilling? Not if you keep a balance. You are leaning towards a far-left-wing view of the world as much as your father leant towards a far-right perspective.

As any lyric, or left-wing intellectual, you assume you hold the truth (i.e. you know, absolutely, how things should be). You forget three important factors:

1. You probably don't hold the truth. This isn't an attack. I probably don't hold the absolute truth either...
2. Your proposition ("let's all follow my universal view of the truth, pursue abstract knowledge as the ultimate goal") is what is called in engineering a null-feedback system. It provides no correction mechanisms. Null feedback systems, like old gasoline engines, tend to require regular tune-ups under penalty of degraded performance.
3. Market driven systems are exceptional at auto-correction. Markets provide an excellent feedback mechanism with great survival of the fittest cutoffs

When I state that Universities align themselves with the goals of students, it's a view of this market-driven mechanism in actions.

Anyhow, your view of how things should be is, in practice, irrelevant. I could discuss the theory endlessly, defending the need for a market in high-level teaching. In reality, universities are economical institutions, driven by market principles, and pursuing market goals. Hence, my conclusion is valid. Grades should reflect the overall goal of the university: add market value to its students.

Fair?

[alienmole]

If scheduling was completely fair, this would have been a frist ps0t.

Re:Fair?

[Progman3K]

You could have covered two memes at once by asking if Slashdot run Linux

Re:Fair?

[Pseudonym]

On Unix, fair scheduling means that all tasks get equally shitty service.

Smells like Communism

[0xdeadbeef]

Free software: because some processes are more equal than others.

Re:Smells like Communism

[Anonymous Coward]

Yes, each process according to its needs,
each CPU according to its abilities.

Re:Smells like Communism

[Kjella]

And for the capitalist owning the CPUs and giving the processes work: Outlook not so good. Fortunately, our slave laborers are very loyal.

Surprised?

[WombatDeath]

You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks.

No I won't, because I don't know what the hell it means.

Hah! In your face, Taco!

Re:Surprised?

[Eevee]

In computer science, Big O notation is used for the complexity of a task.

Re:Surprised?

[jrschulz]

A scheduler is the piece of software that brings you the illusion of multi-tasking. Because a single processor (with a single core) can only run one process at the same time, the operating system switches the process currently running. And it does this very fast (IIRC up to 1000 times a second in the case of linux).

The scheduler decides which process runs when and has to make sure that no process has to wait in the queue forever without getting his share of CPU time (this is what is called "starving").

Since the scheduler is a program by itself, it has a specific runtime characteristic, usually dependent of the number of programs waiting for their CPU share. The special property of the current scheduler in linux is that its runtime is in fact independent of this number. That's expressed in CS by O(1).

Re:Surprised?

[BiggerIsBetter]

In computer science, Big O notation is used for the complexity of a task.

Meanwhile, outside computer science, Big O faces are used for the completion of a task.

Re:Surprised?

[Anonymous Coward]

Yeah, I know what O(1) means, but I still don't know what "You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks." means.

Re:Surprised?

[rjamestaylor]

I came "inside" to post this very thing. I know what O(1) is, but I cannot understand that sentence at all, even after re-reading it several times.

You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks.

• really too good
• not to have any side-effects
• on fairness
• to all tasks

No idea what that is trying to say.

Re:Surprised?

[Otter]

I think the intended meaning is "Unsurprisingly, the O(1) behavior came at the expense of optimum scheduling."

Re:Surprised?

[adrianmonk]

A scheduler is the piece of software that brings you the illusion of multi-tasking.

I think you mean multiprocessing. Even so, that's not entirely accurate: you can easily have a computer with 64 processors and true multiprocessing, and you would still use a scheduler to assign tasks to the processors.

Re:Surprised?

[howlingmadhowie]

and as you can see, it does it a lot faster than the old windows xp kernel (no surprise there). i wonder what it will be like against vista?

http://widefox.pbwiki.com/Kernel%20Comparison%20Li nux%20vs%20Windows

Re:Surprised?

[Workaphobia]

O(1) is good. It's really good. It is, in fact, too good. Too good to not have sid-effects. Side-effects that affect fairness with respect to other tasks. It's a trade-off, because having the best of both worlds is too good to be true.

Re:Surprised?

[fm6]

A scheduler is the piece of software that brings you the illusion of multi-tasking.

Hardly an illusions. I have dozens of tasks executing on my Pentium IV CPU as I'm writing this. One task is monitoring my keystrokes, another is looking after the ethernet connection, another is updating my display... It's perfectly true that at any given moment only one task has the current instruction. But that doesn't mean other tasks aren't active: they're all just waiting for a resource to come free, which is most of what a task does in any case, even when there are no other tasks.

There is an illusion in multitasking, but it's not multitasking itself. The illusion is that each task proceeds without interruption.

No nitpicks about multiple cores, please: there will always be more tasks than cores.

Re:Surprised?

[bmv]

In computer science, Big O notation is used for the complexity of a task.

Yet in this story posted earlier today, the Big O means something quite different...

Re:Surprised?

[Alizarin Erythrosin]

Meanwhile, in anime, Big O is a giant black mech that occasionally smashes up the city whist engaged in a fight with another mech.

Re:Surprised?

[marcosdumay]

It's more like: "Our O(1) algorithm gives the optimum performance we tried so much to achieve. But when we made it, we discovered that we were persuing the wrong goal."

Re:Surprised?

[instagib]

> there will always be more tasks than cores

Future cellular CPUs will dynamically adapt and create a new core for each process. This means, whatever load you throw at it, the speed remains the same. The scheduler will only create, assign and deactivate cores.

Ok, this was fantasy. Forgive me, I had a lot of coffee today...

Re:Surprised?

[GuyverDH]

Big O can also be used to indicate you've done something right with a member of the opposite sex...

Oh wait, this is slashdot... We're not supposed to know this....

Re:Surprised?

[ArsonSmith]

finally we have a true definition of Irony. To find out that perhaps all process are not created equal.

Re:Surprised?

[bulliver]

Meanwhile, in automotives, Big O is a great place to pick up tires (and possibly pimp your ride...).

Re:Surprised?

[Ixitar]

Don't forget about Matt Helm fighting Big O in The Silencers.

Re:Surprised?

[nosferatu1001]

or the same sex, which is often a complete OoM easier ;)

this is slashdot however, and there it only happens a) with girls and b) in Pr0n movies....

Re:Surprised?

[__aailob1448]

good post. I couldn't have put it better.

SMP and RT capabilities?

[Anonymous Coward]

Will the new scheduler be more efficient at scheduling single processes across a multi-core system?

On another not[e], when are we going to be able to build a default kernel capable of low latency I/O for A/V work?

Re:SMP and RT capabilities?

[paulbd]

since about 2.6.18, the default kernel build is capable of supporting relatively low latencies for SCHED_FIFO tasks. Ingo's RT patch still takes the cake (on the right hardware, sub-msec latencies with almost hard real time reliability), and more and more of his RT patch makes it into the mainline kernel with each passing month or two.

I/O prioritisation

[Doug Neal]

Linux really doesn't need a new process scheduler. What it could really do with is I/O prioritisation. Windows now has it, so there's no excuse. CPU power is fairly abundant these days so managing its usage is less of an issue than it used to be, but I/O bandwidth is often in short supply and I/O-bound applications can choke a system and make interactive processes a pain in the ass to use. I'd like to see some way of reserving and limiting bandwidth to particular devices for particular processes. And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy... as far as I know, the system calls don't even exist in the kernel to do this yet.

Re:I/O prioritisation

[tepples]

And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy... as far as I know, the system calls don't even exist in the kernel to do this yet. Windows has this to an extent. I press Ctrl+Shift+Esc to open Windows Task Manager, then View > Select Columns... > turn on Page Faults Delta, and I see the penalty for sticking with the 6-year-old paid-for PC that I still use.

Re:I/O prioritisation

[Anonymous Coward]

> What it could really do with is I/O prioritisation.
ionice. Available since 2005-08-28.

> And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy

I agree, that would be nice.

Re:I/O prioritisation

[hackstraw]

Linux really doesn't need a new process scheduler. What it could really do with is I/O prioritisation. Windows now has it, so there's no excuse.

I dunno. Linux has has some changes recently in the scheduling department, and an O(1) process scheduler can only be "a good thing". Recently, the I/O block layer got a new scheduler (linky http://kerneltrap.org/node/7637). Regarding other I/O prioritization, I can't say with authority that this is needed or not.

Maybe all of these things are related, but in my selfish world, I want Linux to scale better. Scaling well beyond 64 CPUs or cores, but I believe this is a much greater task than ~60 hours of coding. It took a while before Linux got SMP clean, and today SMP is normal, not something that reserved for servers. The monolithic high clockrate CPU is dead, and this has been overtaken by multi-core processors, and more than one of them inside of one box. In my eye, this is where all OSes should be focusing their attention.

Re:I/O prioritisation

[JohnFluxx]

I'm the author of the kde task manager thing. It would be interesting to add a view for I/O. If you find out how to do it code wise, let me know :-)

Re:I/O prioritisation

[Stephen Williams]

And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy

I'd love something like that.

There's a way of logging I/O; it's pretty rough-and-ready, not really suitable for permanent use, but can be handy for figuring out what keeps causing a laptop HDD to spin up, for example. As root, do:

echo 1 >/proc/sys/vm/block_dump

I/O is then logged to the kernel ring buffer, and can be retrieved with dmesg. The entries look like:

pdflush(138): WRITE block 1161864 on dm-4
pdflush(138): WRITE block 0 on dm-3
pdflush(138): WRITE block 524328 on dm-3
pdflush(138): WRITE block 786952 on dm-3
pdflush(138): WRITE block 786960 on dm-3

When you've finished, do

echo 0 >/proc/sys/vm/block_dump

as root to turn it off again.

Like I said, very rough-and-ready, nowhere near as nice as a proper I/O top would be, but there it is.

-Stephen

Re:I/O prioritisation

[Anonymous Coward]

Linux has had I/O prioritization for a few years now. There are a couple of I/O schedulers adapted to different workloads (deadline, anticipatory, fair, no op) that can be set globally or per block device. The default scheduler since 2.6.18 is cfq (the "fair" one) and it supports manual prioritization too (using the "ionice" command).

In fact, I don't think Linux has ever suffered from the same I/O problems that people often complain about in Windows.

Re:I/O prioritisation

[jhines]

If i remember correctly VMS used to give a job a temporary priority boost, upon completion of the IO for just this reason, to get it to the top of the cpu queue and get it going again.

Re:I/O prioritisation

[jawtheshark]

Now, page faults are indeed a form of I/O, but a page fault is technically seen just the fact that some memory required isn't in physical memory. I don't think the parent poster was talking about that. One of the most common reasons for page faults are simply that a block of memory has been swapped to disk, and then suddenly it is required, and as such the block of memory needs to be read into the physical memory.

I'd say: add some memory to that box of yours.

You can read up on it here

Re:I/O prioritisation

[DaleGlass]

atop seems to have support for disk monitoring, but it requires a kernel patch:

http://www.atconsultancy.nl/atop/kernpatch.html

Re:I/O prioritisation

[ppc_digger]

I agree, that would be nice.
Don't you mean "that would be ionice"?

Re:I/O prioritisation

[wild_berry]

Version 3 of the Completely Fair Queueing IO scheduler was put into the mainline Linux Kernel in 2.6.13 and has been the default IO scheduler since 2.6.18. Jens Axboe, who wrote and maintains it, says that CFQ "has also grown more advanced features such as IO priority support, allowing a user to define the IO priority of a process with ionice, similar to CPU scheduling." in an interview at KernelTrap (http://kerneltrap.org/node/7637).

Re:I/O prioritisation

[tepples]

I'd say: add some memory to that box of yours. I know that. But do they make PC133 anymore?

Re:I/O prioritisation

[Anonymous Coward]

I read an article somewhere on Sun's site about I/O scheduling in SunOS, but unfortunately I can't find it now. I'll try to summarize it. The basic point was that when a task wants to write data, it can typically hand that data off to the kernel and then keep running. That means that it's making best use of system resources, since it will use the processor (for example) while the kernel writes to the disk in the background. When a task wants to read data, however, it usually can't do anything until the data's read from disk. So what SunOS will do is schedule I/O unfairly, prioritizing reads over writes, to minimize the amount of time that tasks spend blocked. (My experience is that it will even aggressively swap out pages to expand the write cache.) I wish I could find that article, I seem to remember it having some interesting nitty-gritty details about the way this is actually implemented, as well as some benchmarks from a customer.

Re:I/O prioritisation

[tokul]

CPU power is fairly abundant these days so managing its usage is less of an issue than it used to be,

Remember that when multiuser system starts choking due to unoptimized process handling code. Linux can run on setups that differ from your single user workstation.

Re:I/O prioritisation

[makomk]

Linux has has some changes recently in the scheduling department, and an O(1) process scheduler can only be "a good thing".

Which, presumably, is why they're thinking of taking out its current O(1) process scheduler and replacing it with an O(log(n)) one?

Re:I/O prioritisation

[$RANDOMLUSER]

I'd say: add some memory to that box of yours.

That assumes that the loader is going to try to bring the whole program into memory at load time, which is almost never the case. It completely ignores the notion of working sets, or how they change over the lifetime of a process. As an example, why should a program keep its "open all files" code in memory once all the files are opened? Vomit Making System loaded the first page of a program (the entry point) and forced the program to demand in other (512 byte) pages as required. Picking a (code) page to discard was simply done LRU. The working set size was an OS tunable parameter which was affected by things like average number of users, average process size, average process runtime, etc.

Re:I/O prioritisation

[Mike McTernan]

iostat is probably an easier way to achieve similar output.

It still doesn't break it down by task though, so not really the iotop people are looking for.

Re:I/O prioritisation

[Kjella]

I see ionice isn't installed by default on Debian etch, but found it in the schedutils package. However, I still don't see how to use it in a useful way. For example, I would like to load kplayer with high priority on both CPU and IO, every time I run it (i.e. every time I start the process). I understand I can dig out the process ID, open up a terminal, renice and ionice it, but is there any way to make it run that way by default?

Re:I/O prioritisation

[dropadrop]

This is absolutely true. Nothing is more annoying then trying to do a low priority but large & stressing disk operation on a host where there are small high priority disk operations active all the time. Currently the low priority task will be handled like the others, causing everything important to a grinding halt.

Re:I/O prioritisation

[Endymion]

speaking of fairness in I/O and windows...

I know most unix flavors have had proper elevator-scheduling I/O for a long time, and you can hear it on the disks - it's fairly rare to hear hard random thrashing. When I tried similar tasks on windows, it's always doing some really nasty back-and-forth seeking, slowing everything way down.

Does windows even use a sane elevator I/O yet?

Re:I/O prioritisation

[Animats]

Linux really doesn't need a new process scheduler. What it could really do with is I/O prioritisation.

QNX has that, which is essential for real-time work.

QNX has the advantage that I/O, like almost everything else in QNX, is done via inter-process message passing operations. The message passing system uses priority queues, and so requests to file systems and devices get handled in priority order. So resource managers (file systems, device drivers, etc.) don't have to explicitly handle priorities; it's done for them. Some resource managers, like disk handlers, process multiple requests at a time so they can reorder them to optimize access, but network devices and such are FIFO at the resource manager level and priority ordered at the message level.

The end result is that you can compile or surf the web on a system that's also doing real time work without interfering with the real time tasks.

Re:I/O prioritisation

[Doug Neal]

Remember that when multiuser system starts choking due to unoptimized process handling code. Linux can run on setups that differ from your single user workstation. I know this all too well and had this in mind in my original post, most of my Linux work is on servers (although I do have a Linux workstation) - being able to reserve/restrict I/O and CPU per user or better still per website and database would be like, totally useful.

Re:I/O prioritisation

[myz24]

Sure do
http://www.mwave.com/mwave/DeepSearch.hmx?scriteri a=pc133&ALL=y&TP=7

Re:I/O prioritisation

[Kjella]

Read the manpage? Know nice?

nice -n -19 ionice -c 1 kplayer

Yes. Yes. But those of us that don't live in the 1980s, launch media files by double-clicking on them in Konqueror, not dropping to a shell to write an obscure command so start a media player, so I can browse with it and open the file from there. Hell, I don't think I can do that even via the file association menu in KDE, where I can add additional arguments. But this looks like I need to run "nice" instead of "kplayer". Also I wouldn't want to do that on every association either even if it's better than doing it every time I want to play something. Overall, a perfect technical solution that completely fails to be usable for the enduser. Not that is comes as any surprise...

Re:I/O prioritisation

[Wonko the Sane]

You could make a wrapper script... not exactly user-friendly for most people however. Unless your distro does it for you ahead of time.

Re:I/O prioritisation

[Anonymous Coward]

VAX/VMS had it way back. The SYSMON application was the bees-knees. You could/can get I/O per process, see the files open per process, I/O to each individual file, I/O to a disk, which processes were doing I/O to a disk and which processes were doing I/O to a file. Some of that required a little system programming, but the important thing - the data structures - were all there, and very nicely designed. UNIX/Linux was/is primitive by comparison. Sigh. No doubt I'll get flamed by someone who has never done system programming under VMS, especially not on VMS clusters, where the I/O came from multiprocessor CPUs clustered together - 4 processors per box, 8 boxes and 8 HSCs. Ahh memories.

Re:I/O prioritisation

[Breakfast Pants]

A one line script does the trick, name it kplayer and put it in ~/bin (and put ~/bin at the top of your $PATH):

#!/bin/sh
nice -n -19 ionice -c 1 /usr/bin/kplayer

Re:I/O prioritisation

[jawtheshark]

Yup: www.kahlon.com

I'm a satisfied customer there...

Re:I/O prioritisation

[AaronW]

Been there since the 2.6.13 kernel with the CFQ I/O scheduler.

ionice -h
Usage: ionice [OPTIONS] [COMMAND [ARG]...]
Sets or gets process io scheduling class and priority.

-n Class data (typically 0-7, lower being higher prio)
-c Scheduling class
1: realtime, 2: best-effort, 3: idle
-p Process pid
-h This help page

Re:I/O prioritisation

[AaronW]

I thought the Linux kernel automatically bumped up the priority of any task that makes use of audio and at least video capture. I also thought that a real-time CPU priority task got I/O priority as well, but I could be wrong here.

Re:I/O prioritisation

[JonXP]

And Vista has it completely. Just start up the Resource Monitor (either via the start menu, or the button on the task manager) and you can see all your I/O statistics, as well as several other computer health stats.

Re:I/O prioritisation

[AaronW]

It should be possible to get the source code to ionice and look at that. The other big thing I would like to see in the task manager is the ability to identify which window belongs to which task.
Look at the source code to ionice at ftp://ftp.kernel.org/pub/linux/utils/util-linux/te sting/util-linux-2.13-pre7.tar.bz2
It contains code to set and get the IO nice properties.

Re:I/O prioritisation

[brezel]

don't forget arguments :)

#!/bin/sh
nice -n -19 ionice -c 1 /usr/bin/kplayer $@

Re:I/O prioritisation

[asninn]

There's some folks working on scaling, too. ;) I wonder where I'll get a 4096 CPU machine, though...

Re:I/O prioritisation

[jawtheshark]

I understand... It's been a while since my operating system classes. Now, it's clear that upon loading a program there will be page faults. Only preloading will work there, but in essence you just avoid "page-faults" by doing them earlier.

However, with the oodles of RAM everyone has, I don't see a problem keeping the working sets large and only reduce them when the RAM is completely used. Many techniques are remnants of the memory-starved machines we had back in the day.

Re:I/O prioritisation

[Degrees]

Thanks for the link to that article - that was great.

As far as I/O prioritization goes, one of the things old mainframes have that we still don't have in the microcomputer world is high-throughput I/O channels. 64 CPU cores is nice, but getting them to chew through 60 TB of data quickly really requires some planning to open up the I/O channels and keep those channels full.

Obviously, I expect that the slowest part of the system will be the I/O channel - not the process scheduler. With that new I/O block scheduler you mentioned, I could be wrong.

Re:I/O prioritisation

[Dion]

Please, take a look at atop.

It needs a kernel patch to do the sexy things, but it makes sense to use the same patches, as everybody who worries about io performance will be installing the atop patches

http://www.atconsultancy.nl/atop/kernpatch.html

Re:I/O prioritisation

[matt me]

What it could really do with is I/O prioritisation. Bandwidth is often in short supply and I/O-bound applications can choke a system and make interactive processes a pain in the ass to use. I'd like to see some way of reserving and limiting bandwidth to particular services for particular uses. Are you talking about the internet? Avast you scurvy opponent of net neutrality!

Re:I/O prioritisation

[DamnStupidElf]

QNX has the advantage that I/O, like almost everything else in QNX, is done via inter-process message passing operations. The message passing system uses priority queues, and so requests to file systems and devices get handled in priority order. So resource managers (file systems, device drivers, etc.) don't have to explicitly handle priorities; it's done for them. Some resource managers, like disk handlers, process multiple requests at a time so they can reorder them to optimize access, but network devices and such are FIFO at the resource manager level and priority ordered at the message level.

Yeah, and then a priority inversion killed the Mars Rover (I think that's what it was). With standard scheduling, things would have just slowed down, but wouldn't have hung the whole system.

Re:I/O prioritisation

[dotgain]

If you want me to go on arguing, you'll have to pay for another five minutes.

Re:I/O prioritisation

[arivanov]

Exactly.

While there is enough stats for CPU, stats for IO are considerably more arcane and harder to understand. To add insult to injury some of them are fs dependant or dependant on underlying hardware and drivers. For example the cursed fixed size tables for "stat" do not cover half of the IDE subsystem along with most Compaq/HP RAID controllers. So presenting a graphical view for a user to make decisions on IO priority will be considerably more difficult.

Re:I/O prioritisation

[tepples]

However, with the oodles of RAM everyone has, I don't see a problem keeping the working sets large and only reduce them when the RAM is completely used. Many techniques are remnants of the memory-starved machines we had back in the day. Handheld devices are still memory-starved.

Re:I/O prioritisation

[TuringTest]

If your GUI requires you to associate application icons with complex technical commands in order to play smoothly, then something is very wrong with it.

Re:I/O prioritisation

[Handyman]

In fact, this functionality is pretty darn useless. (I should know, I got it into 2.6. :-) ) For read I/O it's okay, but for write I/O it sucks. The thing is, what's logged is the actual I/Os, which are generally done by pdflush (if the modifying process doesn't use fsync, which it usually doesn't), and kjournald if you're using ext3. The only thing that's logged otherwise is that a process dirties an inode, but that doesn't tell you how many pages it's modified. You get something like

process syslogd dirtied inode daemon.log
process Y dirtied inode some_other_file1
process Z dirtied inode some_other_file2

followed by 300 writes by pdflush, which only specify a device and a block number, not a file name. There's no way you can find out for each of the 300 writes whether it was caused by the "syslogd", X or Z process. So there's no way you can count the amount of write I/O that a process has done.

Re:I/O prioritisation

[jawtheshark]

Handheld devices also run applications and operating systems that were desigend for them....

Re:I/O prioritisation

[tepples]

Then why can't I run a handheld OS and handheld apps on a laptop and get blazing fast performance? Why must PC apps be so bloated?

Re:I/O prioritisation

[Animats]

Actually, that was the Mars Pathfinder. It was running VxWorks, and the effect of the priority inversion was that the stall timer would trip and reset the whole system. The problem was that VxWorks, like QNX, lets you turn off "priority inheritance" on a mutex. This is usually a bad decision, but that was done on the Mars Pathfinder, and created the possibility of a livelock.

So they uploaded a patch to change that mutex to "priority inheritance on", and it worked consistently thereafter.

Re:I/O prioritisation

[ThisNukes4u]

Umm, which mars rover are you talking about? The only ones I know used VXWorks, not QNX

Re:I/O prioritisation

[jawtheshark]

Architectural differences my guess. Do you know a handheld with a x86 processor? I do not.

Besides, bloated? I used to run slackware on an P120/32Meg RAM with 2.4 kerel and WindowMaker. Ran just fine, which I couldn't say about Windows 95. (This was a while ago, when Windows 95 was still current) Heck, I used to run OS/2 Warp 3 on 486DX2-66/8Meg RAM and it ran infinetly better than Windows 95 on that machine.

You can choose the amount of bloat. Take Debian base, and add a lightweight Window Manger (like fluxbox, WindowMaker and many others) and just the applications you need.

My server is an AMD64 2800+ with 512Meg RAM. Do you want to know how much memory it uses? I'll tell you "Memory: Real: 38M/131M act/tot Free: 358M Swap: 0K/512M used/tot". It runs OpenBSD/amd64. You call 38Meg used bloated?

My workstation is an AMD Athlon MP (2 CPUs) with 4Gig RAM. Debian testing with gnome and some apps. Idle it uses a mere 200Meg. That said, WinXP used ~120Meg after bootup on the same machine...

You choose the bloat, my friend.... It's all up to you.

Re:I/O prioritisation

[nih]

pdflush(138): WRITE block 1161864 on dm4 cool, a task scheduler that plays quakeworld!

Re:I/O prioritisation

[JohnFluxx]

What do you think about the other poster's suggestion on doing it how ionice does it? Would that still be fairly meaningless / misleading?

Re:I/O prioritisation

[WhiteWolf666]

Hmmm?

The man page for ionice

Here's a quote:
NOTES
Linux supports io scheduling priorities and classes since 2.6.13 with the CFQ io scheduler.


The support is there in the kernel. There's a basic set of userspace utilities to handle it. There are some issues to be worked out (you have to be root or have the setuid on to change priorities), and there isn't an automatic daemon to do it for you, and these isn't a top kind of utility, but the kernel level support is there for it.

Re:I/O prioritisation

[eta526]

This is exactly how I had to do it in Windows XP. I have an application that eats too much CPU while doing a certain batch process, so I start it in low priority mode to allow interactive processes to respond.

echo on
start /belownormal program.exe
exit

I just keep that batch file in the directory for my program and have two shortcuts, one to my batch script and one directly to the program. I never did figure out how to get PowerDVD to start in Realtime mode when I pop in a CD either, nor could I get a shortcut to simply run the start command to start my apps at a given priority level. If XP can't do it cleaner than by running a script, I wouldn't necessarily expect Linux to, but I would be happy if it did.

Re:I/O prioritisation

[tepples]

Now, page faults are indeed a form of I/O, but a page fault is technically seen just the fact that some memory required isn't in physical memory. There are several other kinds of I/O that the NT kernel accounts for and that the user can turn on in Windows Task Manager's Select Columns.

Re:I/O prioritisation

[QuoteMstr]

nice -n -19 ionice -c 1 /usr/bin/kplayer "$@"

Quoting the $@ is necessary to ensure that file names with spaces are passed as single words.

Re:I/O prioritisation

[jawtheshark]

Go take a look at "Start" - "Programs" - "Administrative Tools" - "Performance". Bazillions of options to monitor I/O. Beats the Task Manager by miles.

You really think I don't know what I/O is and how varied it is.

Re:I/O prioritisation

[DrSkwid]

> The monolithic high clockrate CPU is dead, and this has been overtaken by multi-core processors,

dead, hahah just you wait Johnny.

The King is dead!

Re:I/O prioritisation

[g1zmo]

Better or worse than ${@}?

Re:I/O prioritisation

[QuoteMstr]

${X} is exactly the same as $X for any X, including @. You almost always want to use "$@".

Re:I/O prioritisation

[g1zmo]

I thought it was functionally equivalent to quotes wrt spaces in the variable's value. I'm no expert.

Re:I/O prioritisation

[Breakfast Pants]

Nope, I used to think that as well.

argv.py:

#!/usr/bin/python
import sys
print sys.argv

test.sh:

#!/bin/bash
a="1 2 3"
./argv.py $a
./argv.py ${a}

Re:I/O prioritisation

[g1zmo]

Huh? I'm talking about ${a} versus "$a".

credit goes to Con Kolivas

[phrasebook]

This new scheduler may have 'Ingo Molnar' written all over it but I'll be giving the credit to ck!

Re:credit goes to Con Kolivas

[Anonymous Coward]

Perhaps if we had more 'ego maniacs' like Ingo, stuff would work better?

I don't think your characterization is fair, I read the entire thread and all I see is someone doing his job.

Re:credit goes to Con Kolivas

[wellingj]

But like it or not, Linux is going to go more places with Ingo's Real Time additions that without it.

Re:credit goes to Con Kolivas

[Wonko the Sane]

CFS vs SD isn't decided yet. Con is still releasing new versions as the people testing it find new bugs. Not to mention that SD is in the mm- tree and CFS isn't (yet)

Re:credit goes to Con Kolivas

[jb.cancer]

Well, yes & no. It really was Con's RSDL that got ppl looking seriously into changing the mainline scheduler (there already being several out-of-mainline alternatives like nicksched, etc.)

Con's scheduler seemed to work better at higher workloads than the mainline, by just trying to distribute load evenly and not trying pretty interactivity tricks. But several ppl did say it didn't perform well for certain X client workloads. That's when Ingo's CFS was posted.

There really is 2 alternatives Ingo's CFS & Con's SDL that's being simultaneously tested by the kernel developers now, and none is accepted into mainline.

So it wouldn't be fair to say that CFS is *the* next Linux scheduler. It could be SDL as well.

Re:credit goes to Con Kolivas

[Anonymous Coward]

Yeah right. doing his job.. Take all the credits. Diss other people's ideas, reimplement them and claim innovation. That used to define the Microsoft notion of innovation.

I don't know any of these guys and never dealt with them on any level.

i'd like to give credit to Con Kolivas for the general approach here:
he has proven via RSDL/SD that 'fair scheduling' is possible and that it results in better desktop scheduling. Kudos Con!

--- linux.orig/kernel/sched.c
+++ linux/kernel/sched.c
@@ -16,6 +16,7 @@
  * by Davide Libenzi, preemptible kernel bits by Robert Love.
  * 2003-09-03 Interactivity tuning by Con Kolivas.
  * 2004-04-02 Scheduler domains code by Nick Piggin
+ * 2007-04-15 Con Kolivas was dead right: fairness matters! :)
  */

Ingo admitting he was wrong and giving full credit to someone else for the idea is not consistent with my view of an egomaniac. If you have other issues, slashdot may not be the best place to resolve them.

Re:credit goes to Con Kolivas

[jd]

What might work better is to use both. In the same way that we already split tasks into fifo, realtime and normal levels, we might want to subdivide the normal into standard and massive, where massive uses the more scalable of the schedulers and standard uses the more generally applicable.

I have a very strong suspicion that highly scalable schedulers are going to be needed - particularly when threads within a process have been migrated to other nodes or when running heavy loads on the top-end SMP clusters (16-way SMP with 4-core CPUs is not trivial). On the other hand, you absolutely don't want these kinds of cases to reduce the efficiency of the mainstream scheduler for mainstream work.

The obvious solution is to go from 3 bands to 4. If the O(1) scheduler is superior in cases that neither of the replacements is good at, then go to 5 bands.

Optimizations leading to less optimized code

[suv4x4]

It's a very interesting phenomenon.

After enough number of iterations trying to optimize a software program to do everything very well compared to the base "naive" solution, you end up with an OS that does everything poorly.

It's counterintuitive, but we see it it every day around us.

Re:Optimizations leading to less optimized code

[tomstdenis]

What are you smoking? This is supposed to be an improvement on the O(1) scheduler which was an improvement on the previous scheduler.

I don't know about you but my 2.6 based box runs just fine, certainly no slower than my previous 2.4 boxes, and it packs a lot more features, drivers and other internal changes/improvements.

Re:Optimizations leading to less optimized code

[Chandon Seldon]

After enough number of iterations trying to optimize a software program to do everything very well compared to the base "naive" solution, you end up with an OS that does everything poorly.

That's blatantly false. Sure, there are tradeoffs. There are also cases where a better algorithm is an outright win 100% of the time.

O(1) - what a huge misnomer

[Anonymous Coward]

Doing a constant time reevaluation for n processes is still O(n) whether you do it individually or at once. Granted you don't have a pause as all processes are reevaluated but the amount of work the scheduler does is NOT independent of the # of processes.

Re:O(1) - what a huge misnomer

[Watson Ladd]

Actually the Linux scheduler is O(1). Processes are placed on O(1) queues, and the oldest processes on each queue are compared to each other. The number of queues is fixed, so Linux only has 5 nice levels. This is a scheduler because newer processes on a queue do not deserve the time more then the processes ahead of them.

Re:O(1) - what a huge misnomer

[pclminion]

I was going to agree with you but you're wrong. Process priority is the sum of an intrinsic priority and another value which increments as time goes on, in order to ensure that EVERY process can run at least SOME of the time. This means that at every scheduling pass, all of these dynamic priorities must be updated. That's OBVIOUSLY O(n).

Re:O(1) - what a huge misnomer

[Anonymous Coward]

I think what it really means is that the time to select a job is O(1) time whenever the scheduler is called. And this doesn't seem to be unintuitive for me. Plus that's totally reasonable: in any time-sharing system where you have a time-slice, you have an unbounded amount of times that the scheduler is called. All you can possibly hope for is that each time the scheduler is called, it gives you a job in constant amount of time. (You cannot expect that to be sub-constant, really.)

Re:O(1) - what a huge misnomer

[ASBands]

If you want a good description of the old way it works (which is what you're talking about), [PDF Warning] here it is. As this PDF describes, the 2.4.x kernel uses a O(n) fast algorithm for choosing the next task, going through the array of tasks to re-evaluate them. The the Linux 2.6.x scheduler recalculates timeslices as each task uses up its timeslice. In this fashion, the kernel should always know the most important thread, it is simply the next element. Granted, you are doing the same amount of work, but the pauses for re-evaluation are spread out so that you don't get long lapses where nothing important happens.

Re:O(1) - what a huge misnomer

[ookabooka]

I don't know. . .take something simple like FIFO (first in first out). The "scheduler" in that scenario does very little and would definitely be a O(1) algorithm since nothing is evaluated and it just keeps a list of who asked for attention first. I'm not familiar with the scheduler in question so I can't say for sure what it is, but if it evaluates 1 process every context switch, that is O(1) with regards to switching tasks as it is independent on how many processes exist. Overall if you have n jobs and you want to know how much overhead the scheduler adds, then yes it adds O(n) because it has to run at least n evaluations (it would probably be something higher unless each processes terminated after being run). Consequently if it evaluated all processes on context switches it would be O(n) for the individual switch and O(n^2) total overhead. . . .God I hate my Operating Systems class.

Re:O(1) - what a huge misnomer

[Watson Ladd]

No. You are wrong. It looks O(n) unless you notice that the processes back on the queue ran more recently then the ones at the front. Therefore they have lower priority then the ones at the front, so we only need to worry about the processes at the front of the queues. To evaluate these priorities we just store the last time they ran, and then subtract from the current time, then add that to the inherent priority.

Re:O(1) - what a huge misnomer

[ASBands]

Here's how Linux 2.6.x task scheduler works:

• A "runqueue" keeps track of all essential tasks assigned to a given CPU [Queue is O(1) efficient]
• Each runqueue contains two priority arrays, the active and the expired. As a task completes, it is moved (during the move, the new timeslice is calculated - the point of debate and largest fundamental change to the task scheduler) [Moving from static array to static array is O(1) efficient]
• When the active priority array is finished, the expired array becomes the active array [Swapping 2 pointers is O(1) efficient]
• The priority arrays are of fixed length 140, as that is the amount of priority levels Linux has [O(140) = O(1)]

The point of debate comes if two threads have the same priority, in which case they are put on a round robin in the priority array. However, the confusion comes in that the execution is O(n) (which makes sense if you think about it), but the scheduler itself handles these at O(1) efficiency.

Re:O(1) - what a huge misnomer

[xenocide2]

It seems like the difference is that people call it an O(1) scheduler to reflect the fact that all the work required to be done at the end of a timeslice (record keeping, picking a new process etc) is done in constant time, and people arguing for O(n) are referring to the cost to schedule all processes. Nobody's saying they can find a schedule for n processes without looking at all of them.

How does this work?

[Watson Ladd]

I would love to know how the algorithm actually works. Is this just a new data structure for organizing the processes, or is there other stuff involved?

The Multics scheduler always seemed very nice

[Anonymous Coward]

On Multics, tasks that used up their CPU were put in a lower priority run queue and tasks that didn't use up their CPU time were put into a higher priority run queue.

So interactive tasks naturally floated to the top and compute bound tasks naturally sank.

(Anyone remember Multics?)

Re:The Multics scheduler always seemed very nice

[Hognoxious]

I used Multics, but I thought it prioritised the tasks by how thick the cards were.

Re:The Multics scheduler always seemed very nice

[ScrewMaster]

Actually, no ... it was by the weight of the card stack.

Re:The Multics scheduler always seemed very nice

[Guy Harris]

I used Multics, but I thought it prioritised the tasks by how thick the cards were.

I guess that explains the slow response I got - I mostly used Multics from an IBM 2741, so I didn't have any cards.

What I really want

[Anonymous Coward]

I want a nice-like utility that works for more than just CPU time. I want to be able to do hddnice -5 firefox and networknice -7 pr0ndownloader. Why can't the principles of nice work for various forms of I/O scheduling as well as CPU scheduling? Does anyone know of a Unix that has these sorts of things. I just hate it when my system is unresponsive because some process, which is niced into all get out, is swapping like crazy, and is allowed to do so because "it's not using CPU time". Bah!

Re:What I really want

[bersl2]

See ionice.

It's a crude program, but it does prioritize I/O like nice does for CPU time.

Ring-0

[TiCL]

Can't we just give the processes weapons and let them decide which follows?

Ring-0 motherfucker! Do you use it?

Re:Ring-0

[maxwell demon]

Ring-0 motherfucker! Do you use it?

One ring to rule them all ...

Re:This is communism!

[Anonymous Coward]

This sort of scheduler is more suited for desktops, where you want everything to react responsively at the cost of lower throughput.

mod parent up

[bakuun]

Good explanation of the scheduler, and what significance it has that it is O(1). (as opposed to some other complexity, where the scheduler would take longer and longer to execute the more processes there are in the queue).

Would have modded up myself if I had the points to do it.

I love this.

[Progman3K]

FTA:
>> [...] the core scheduler got smaller by more than 700 lines:

Someone who I respect tremendously once said
"Perfection is attained when you remove everything that is not essential"

I have to agree

Re:I love this.

[wellingj]

Wasn't that Bruce Lee?

Re:I love this.

[fimbulvetr]

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. ~Antoine de Saint-Exupéry

Re:I love this.

[Paul Crowley]

Antoine de Saint-Exupéry:

Il semble que la perfection soit atteinte non quand il n'y a plus rien à ajouter, mais quand il n'y a plus rien à retrancher.

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.

The Mother of All Comp-Sci Flame Wars

[mosel-saar-ruwer]

GP: Can't we just give the processes weapons and let them decide which follows?

P: That is actually the kind of question that my Operations Research professor (who also did a lot of work in CPU simulation and performance estimating) used to throw onto final exams as the "separate the B+ from the A" question. If your answer was interesting enough he would send you over to one of his Masters candidates to see if it could be taken any further. So I wouldn't count your suggestion out from the start!

Behold: The Mother of All Possible Comp Sci Flame Wars: The Darwinistically Selected Genetic Algorithms -vs- the Intelligently Designed Algorithms.

Bumper Stickers $4.95; T-Shirts $19.95:

$DEITY does not play dice with the Turing Machine.

Re:The Mother of All Comp-Sci Flame Wars

[passthecrackpipe]

hahahahaha - thanks that made me laugh out loud

Re:The Mother of All Comp-Sci Flame Wars

[rnj]

A friend of mine was involved in the early days of an experiment of self-selected algorithms. In fairly short order the OS figured out the fastest way to "finish" a backup was to snap the tape.

Re:And that relates to "fairness" how?

[Rakshasa Taisab]

It doesn't, it relates to the particular implementation used in Linux, which has a constant complexity. The new scheduler uses RB-trees, which would make it O(log(N)) for insertion.

Completely fair?

[tji]

No, I think I'll wait for the unbelievably fair scheduler, or perhaps the ridiculously fair scheduler.

Re:Completely fair?

[JFMulder]

I'll wait for the ludicrously fair one.

Re:Completely fair?

[Wolfrider]

I'm still waiting for the LUDICROUSLY fair scheduler!
 
// ...LONE STAR!!!!

Re:And that relates to "fairness" how?

[wellingj]

The current O(1) schedule is not entirely fair to attain so named O(1) performance. That's how jackass.

Re:O(1) - what a huge misnomer - INCORRECT

[ArbitraryConstant]

You are incorrect because the act of scheduling the next process to run requires constant time regardless of how many processes there are. The O(1) refers to this, correctly.

The reason this is important, and the reason they are worried about the act of scheduling the next process rather than time complexity over all N processes, is that if scheduling the next process were not constant time, the percentage of time spent scheduling the next process would grow larger as you added more processes. That's fine if you're on a desktop system and you go from 100 to 200, but as the number starts getting large on (say) big servers, you start running into a situation where all your CPUs are perpetually tied up trying to figure out what process to run next.

O(n) time over N processes is not a problem; you've either got the CPUs or you don't. If you don't, then your performance will suck for reasons that are your own fault. If you do have enough CPUs, then the time spent scheduling will remain in step with the time spent running the processes, and this is fine. However, if the time spent scheduling grew, every time a process was scheduled, across all CPUs, then your $50000 server would be worthless because it wouldn't be able to handle the workloads you intended for it. All those expensive CPUs would sit there figuring out what process to run rather than running it.

So, it is NOT a misnomer. It accurately describes the portion of the problem that the developers are concerned with. It's O(n) over n processes, and that's great because it means you can get to n without breaking down.

Re:And that relates to "fairness" how?

[ResidntGeek]

Fairness has absolutely nothing to do with algorithmic complexity. O(1) means the scheduler runs in the same amount of time, every time, and says nothing about how fair the scheduling is. Jackass.

Interactive tasks

[Zarhan]

For this reason, I've been using Con Kolivas' patches to replace the scheduler. http://members.optusnet.com.au/ckolivas/kernel/ - very helpful especially if you don't have the fastest computer around. Also seems to help a bit with I/O - if my hard drive is trashing for whatever reason, interactive stuff still remains reasonably responsive. Or at least it doesn't make my mouse cursor skip...

Even so, I'd prefer to have IO better scheduled - ionice doesn't really seem to work at least for me.

Wait wait wait! What about fixing disk IO first?

[Anonymous Coward]

There's a huge thread about broken disk IO in kernels > 2.6.17.
http://forums.gentoo.org/viewtopic-t-482731.html

How about fixing that first?

I've noticed all kinds of new schedulers coming out of the woodwork in 2.6. Optional kernel preemption. And also changes to the default timer (250 instead of 100, etc.). These are choices like I've never had in Linux before. Should be good, right?

But at a higher level there's been such brokenness.
K3B CD burning broke in 2.6.8 and wasn't fixed until 2.6.10.
Firewire performance (for me) started fluctuating after ~2.6.7. Although grabbing DV over firewire doesn't take much CPU time, for some reason having video preview enabled during capture may/may not cause dropped frames (on a modern amd64! pathetic!) depending on kernel version.
And the promise of 2.6 being responsive and feeling interactive under heavy load? Also ended after 2.6.7 for me.
Recent kernels, like 2.6.18, seem to take minutes to balance tasks out. Playing video during heavy CPU usage? For me it gives priority to everything else BUT the new video process for about 30 seconds. (CFM or anticipatory scheduler)

So I'm not sure if we should be welcoming all this new "choice" with scheduler-du-jour or try to give us a good default choice that actually works right first.

The new Linux scheduler must be intelligent

[linuxIsLife]

To be smarter the new Linux scheduler will use artificial neural networks and for speed-up it will be written in Lisp.

O(1) too good. Surprise?

[ozone_sniffer]

You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks. No I won't. AFAIK, O(1) is generally too good for any algorithm that does something useful, given the size of your input varies (n processes). With an input of size n, O(n^k) is generally (i.e. not considering a specific algorithm) acceptable, O(n) is generally good, O(log n) is generally very good and O(1) is generally suppa-duppa doubleplusgood.

Re:O(1) too good. Surprise?

[ozone_sniffer]

Ugh, size n or less, I mean.

Re:O(1) too good. Surprise?

[Eli Gottlieb]

As I read above, only the get_next_process() function is actually O(1). Another O(1) algorithm runs when each process is preempted (or yields) to calculate its next priority, which the kernel uses to place that process in a sorted queue. When it needs a new process, it calls get_next_process(), which simply dequeues the next process from the sorted queue. So even though the total work over the life of the system is O(n) for n processes, the work done to save one old process and load one new process is O(1) [save] + O(1) [load].

Re:O(1) too good. Surprise?

[ozone_sniffer]

Righto. In this case, O(1) is just good enough, then.

Re:Linux is fading away

[cortana]

What's the vertical axis represent?

PSDoom (Doom process manager)

[Alwin Henseler]

Good job sending all those /.ers over there, it will be the mother of all process fights on that poor server now. Sysadmins battling their way through hordes of zombies and monster processes, with ammo (ehm.. mem,cpu) running lower and lower until they're out, just as another wave of uglies comes out of nowhere...

Linux "iostat"

[Anonymous Coward]

http://linux.inet.hr/iostat_utility.html

Re:Well duh

[Anonymous Coward]

Obviously O(1) is a bad choice. Nice to see Linux learning something from Windows here.

Actually I find the Windows (XP, haven't tried Vista yet) scheduler to be quite horrible especially with regards to interactivity. One resource hog and things pretty much come to a standstill. IMO it's worse than O(1) and no comparison to Con's staircase.

Fair schedulers are for the weak

[hcdejong]

Klingon multitasking systems do not support "time-sharing". When a Klingon program wants to run, it challenges the scheduler in hand-to-hand combat and owns the machine.

(from here)

Re:And that relates to "fairness" how?

[GrievousMistake]

You fail at reading comprehension. Let's rephrase: The current scheduler runs in O(1) time. To do this, it uses an algorithm that sometimes isn't optimal; that is, it isn't entirely fair.
The relation between fairness and algorithmic complexity, is that you may sacrifice fairness to get a lower complexity.
This is just rephrasing GP, I don't know shit enough about schedulers to comment on the actuall algorithms.

Re:This is communism!

[Brandybuck]

At the risk of being called a troll, I'm running a FreeBSD desktop, and the GUI is very responsive. Significantly more so than Windows on the same machine, and slightly more so than on Linux.

Re:Well duh

[someone300]

O(1) just means that it doesn't lower in performance for the more processes that are running. In other words, scalable. This is good, and the current kernel does have modes for interactivity and server workloads, they're just not as good as this new scheduler. As I understand it, the scheduler in Linux has been better than the one in Windows for a good while now.

This is very impressive

[Animats]

I'm impressed. I did some work on CPU dispatching on a mainframe system in the distant past, and we were never able to beat O(log n) on an ordered dispatch queue. The obvious implementation is O(n); getting to O(log n) requires a tree, and I want to see how they got to O(1).

This stuff really matters now. If we're going to have 80-CPU multiprocessors, all the main operating system algorithms have to be near O(1), or the scale-up is a lose.

Re:This is very impressive

[Anonymous Coward]

They cheated.

Internally, the kernel only has five priority levels. Each one is a queue, and it compares among all of them to determine which task to run, but it only compares the head of the queue. So it's O(5), which is of course O(1), but if it supported an arbitrary number of priority levels (which IMO it should) then it would become O(n) again.

Re:This is very impressive

[Watson Ladd]

They cheated. Instead of having a real priority queue Linux places each process into one of a bunch of smaller queues each one with a different priority. Then scheduling requires looking a the processes that are at the head of the fixed number of small queues.

Re:This is very impressive

[DragonWriter]

Internally, the kernel only has five priority levels. Each one is a queue, and it compares among all of them to determine which task to run, but it only compares the head of the queue. So it's O(5), which is of course O(1), but if it supported an arbitrary number of priority levels (which IMO it should) then it would become O(n) again.

Well, its O(n) in the number of priority levels, not the number of processes; conceptually, this arrangement with any number of priority levels should still be constant time with respect to the number of processes.

Re:This is very impressive

[DragonWriter]

With any fixed number, sure, this is O(1) with respect to the number of processes.

Well, yeah, that's what I meant.

But as soon as you do something as eminently reasonable as, say, allowing floating-point priorities, or allowing the full range of a 32 or 64-bit integer as a priority, it breaks and you go back to O(log n) priority queues.

Well, using a bigger finite range of priorities doesn't stop you from using a fixed array of queues and staying O(1), though presumably the bigger the number of queues the slower your O(1) system is going to be, to the point where for large priority ranges, so your O(log n) method may be better for reasonable numbers of processes even though it ultimately scales worse with the number of processes. Of course, changes in how computers are used may change what a "reasonable number" of processes is dramatically, so what is best depends on how important it is to have a wide range of priorities, and what you're doing with the system.

Re:Linux is fading away

[maxwell demon]

Possible explanation: More people know about Linux now, so there's less need to Google to learn about it.
Alternative explanation: People have less problems now using Linux, so they google less for solutions on Linux problems.
Third explanation: Linux documentation got substantially better, so people have less need to use Google as a substitute.
Fourth explanation: The larger density of Linux installations comes with a larger density of Linux experts, so people are more likely to consult their local Linux guru than Google.

Pick your favorite choice or make up yet another explanation.

Yes, those explanations are all completely made up, but so was the explanation you had in mind.

Re:This is communism!

[maxwell demon]

Well, a true Darwinian scheduler would have to measure user happyness. Linux kernels all around the net would share and try different scheduling policies. Then they measure the happyness of the user. The algorithms running on the machines with the most happy users get an evolutionary advantage.

You want Trickle

[flyingfsck]

There is something like that to balance ethernet traffic: http://www.linux.com/article.pl?sid=07/04/06/15162 52

You can do the same with iptables and route2, see the advanced routing howto on tldp.org.

Einstein

[flyingfsck]

said with his fine wit: 'A thing should be as simple as possible, but no simpler'.

Re:O(1) - what a huge misnomer - INCORRECT

[ivan256]

The reason this is important, and the reason they are worried about the act of scheduling the next process rather than time complexity over all N processes, is that if scheduling the next process were not constant time, the percentage of time spent scheduling the next process would grow larger as you added more processes.

Of course there's every possibility that your O(1) scheduling algorithm takes as long to run as the O(log(n)) algorithm, or even the O(n^2) algorithm for the typical number of processes running on your system... Ideally, you'd use the best scheduling algorithm for the job and the number of processes, and you'd change on the fly when the number of processes increased or decreased such that the current algorithm was no longer the most efficient.

We rarely see the charts that compare the O(1) scheduler with the O(whatever) schedulers that get proposed over a range of process counts though... Maybe that's because linux_kernel is an all text forum.

Honestly, if there weren't so many credit whores in the non-commercial linux kernel development world, you'd think there would be hundreds of schedulers in the kernel. There's really no reason not to have many, dynamically loaded schedulers. They're easy to write, easy to test, and every CS student writes one at some point.

Re:This is communism!

[SoulDrift]

This is communism!

This... is... SPARTA!

(sorry)

Re:Linux is fading away

[MrHanky]

You can't buy a Big Linux hamburger.

Re:And that relates to "fairness" how?

[eta526]

O(log(N)) for insertion, but that only occurs when a new task is created. The scheduler's complexity would be calculated based on how long it takes to choose what process to allow to execute next.

Ok, here's the plan.

[jd]

Tux and I will drive over with large quantities of booze and herrings. You sneak round the back with the schedulers.

OQO anyone?

[tepples]

Do you know a handheld with a x86 processor?

There is OQO, but it is by no means the only such product. Poqet PC, an early PDA, had an 8088 processor. Bandai WonderSwan is a handheld video game system with an 8086 clone. Tablet PCs, including the compact XO laptop/tablet designed by OLPC, have newer CPUs using the x86 architecture. But even if handhelds do tend to prefer ARM CPUs over x86 CPUs, why aren't the same Windows Mobile apps available recompiled for traditional Windows OS?

You can choose the amount of bloat. Take Debian base, and add a lightweight Window Manger (like fluxbox, WindowMaker and many others) and just the applications you need.

But can one choose the level of bloat on the Windows OS that came preinstalled on a machine? Or do you have to switch operating systems and run the risk of losing compatibility with paid-for hardware? I guess I know why Dell plans to reintroduce Windows XP Service Pack 2 as an option on newer machines, as it can be slimmed down further than Microsoft's latest offering.

Re:OQO anyone?

[jawtheshark]

Okay, now I didn't know about the OQO. The others with 8086 and 8088 are out of the question as they aren't even capable of multitasking. I knew that "in the old day" there were PC-compatible handhelds like the Atari Portfolio which I actually owned. Tablet PC's are no handhelds, they are full PC's in another form factor. As for the OLPC, you can't get one and it runs a non Windows operating system in the first place, bringing us exactly back to what I said in the last post.

Compiling an app for a certain OS is simply not enough. You can't just take source from one architecure and expect it to compile on another... especially if we are talking about hardware limited machines. If it were that easy, there would be no development kits for PC to develop for Windows Mobile. That and Microsoft doesn't want you to use PocketPC Word instead of Microsoft Word even if the limited features suit your needs.

But can one choose the level of bloat on the Windows OS that came preinstalled on a machine?

Not really, Microsoft obviously don't want to give you that kind of control. Do also keep in mind that switching operating systems often means "obsoleting hardware". It doesn't matter if it's from Windows to Windows or from Windows to Linux or even from Linux to Windows. I have a PCMCIA SCSI card that has no drivers from the current versions of Windows, but works fine under Linux. There were a lot of people that lost their (parallel port) scanners during the 98 to XP switch because of lack of drivers. I have a few network cards that do not work in XP either (mostly ISA, but hey, I'm a packrat).

There is alway nLite, but that won't help you with a preinstalled machine.

All in all, I think you're starting to show bad faith. I've given you replies to all your questions, but you never seem satisfied and you just strengthen the requirements. If you really want to run 6 year old hardware, act accordingly. Otherwhise just run to your local store and buy a new machine. I bought a nice laptop just three months ago (before the release of Vista) for a mere 799€. A month later the same laptop was 695€. Not all too shabby for a Turion X2/1Gig RAM/120Gig harddisk. Sure Integrated graphics, but the thing won't be playin games anyway) Came with XP Media Center Edition. You can have much cheaper if going for a desktop.

Re:OQO anyone?

[drinkypoo]

Some more: 486 handtop called the Dauphin, with a full-VGA display, and the Tandy/Casio/GRiD Zoomer/Z-PDA-7000/GRiDPad 2390 which had an NEC V20 (8086 chip.) Both of them are quite old now. The Dauphin was pretty big for a handheld, but it is handheld. Had a radio pen with batteries (no wacom technology.) Ran Pen Windows (3.x) The Zoomer was the size of a paperback and ran PC-GEOS.

Re:"Stolen idea"? (comments below TFA)

[rta]

I'm rather curious myself. It certainly doesn't look like a "stolen idea" in any straight forward manner. Judging from the article it looks more like a power-play.

Mr. Molnar looks to be employing an approach of "establishing facts on the ground". That is, instead of asking people (the list) to comment on his IDEA for doing something he went ahead and did it and presented the patch set. This switches the discussion from "is this an interesting avenue for inquiry?" to "what specific thing can you point out that is wrong with this thing ?". I've seen this in the corporate world all the time and it's considered the mark of someone who "gets things done" and "moves the ball forward".

Often it actually IS a good thing and prevents teams of people from getting bogged down in endless discussion without ever producing anything of worth. On the flip side it annoys the heck out of people if it's used to short-circuit debate, one-up others etc.

In this case Mr. Molnar's argument that he's just putting something forth for discussion and this was the fastest way to do it rings kind of hollow to me. Clearly he had been opposing similar, and less desruptive, propositions for years and had been using his position of relative authority to keep them out of the kernel.

Further, the argument that Linux shouldn't have pluggable schedulers I also find curious. For example it already has pluggable io schedulers that you can choose with boot time parameters AND change on a live system through the /sys fs. Yes the process scheduler is a biger deal, but it would have no impact on most users, it would make things easier for others, and would make things harder for few, if any.

Mr. Trovalds chimes in with a "free market" argument and says that he likes competition and competitiveness.

In the end is Mr. Molnar pulling a power play or is Mr. Kolivas being "whiny" ? My suspicion is the former. As I mentioned above, i don't find compelling the distinctions he draws between his current work and the work he'd rejected previously. Then again i've been accused of too often siding with the underdog.
(note: i don't have anything to do with linux development though i've been a linux user for ~13 years and a software engineer for 10).

(On a grander note, this whole question of the balance between competition and cooperation I personally find very difficult to deal with. Both extremes are bad: no competition = no innovation. hyper-competition = some sort of dystopian Ferengi scenario. Guess i should go read Adam Smith... or something)

Obligatory Soviet Russia...

[jwiegley]

In Soviet Russia processes schedule YOU!

Re:Isnt this called Cron?^H^H^H^H^H^H Tron?

[Jac_no_k]

This reminds me of a movie called Tron.

Schedulers these days I dunnu...

[Nefarious Wheel]

It's all data structures and interrupts nowdays laddie! Data structures and interrupts. Why back in my day we had nice chrome-plated algorithms and fat polling intervals and liked it!

You pesky young folk who think yer flash ram is better than good old reliable ferrite donuts have at with ye! We had disk drives that could pull yer filings out from two feet away on a max seek. Do ya get technology like that nowdays? Do ya? Nuuuuu.....

Mind ye what we had for an OS scheduler was a smiling polish gennelmun who wore too much after shave, and he was a bit much, but we knew which program ran after which we did! Off with ye now, come back when you have a *real* algorithm.

(Walks away muttering at his shoes)

Re:Linux is fading away

[Khazunga]

Bah, it's so easy...

Re:Well duh

[drsmithy]

Actually I find the Windows (XP, haven't tried Vista yet) scheduler to be quite horrible especially with regards to interactivity. One resource hog and things pretty much come to a standstill. IMO it's worse than O(1) and no comparison to Con's staircase.

Windows NT's scheduler is (and always has been) O(1).

(Can't say I've ever had a problem with its scheduling either - then again, I haven't used a single processor Windows machine in anger since about 1998, so I don't have a lot of experience with how it handles single-processor machines.)

Re:Linux is fading away

[the_womble]

In addition a lot of Ubuntu users do straight to the Ubuntu wiki or forums and search there first. The same probably happens with other distros that have good communities

Re:Linux is fading away

[Reverend528]

maybe people just search by the name of the distro.

Solaris

[kildurin]

Why does this seem so much like the Fair Share Schedular in Solaris 10? I think I know where they are getting there clues from. http://www.princeton.edu/~unix/Solaris/troubleshoo t/schedule.html

Re:Linux is fading away

[SnarfQuest]

Third explanation: Linux documentation got substantially better, so people have less need to use Google as a substitute.

Documentation? We don't need no stink'n documentation! Real men don't read documentation!

Have you ever met someone who actually read the documentation before asking questions about a software product? Rare, that is.

Winelib

[tepples]

You can't just take source from one architecure and expect it to compile on another Then how do apps compiled against Winelib manage to work on non-x86 architectures?

especially if we are talking about hardware limited machines. A lot of cross-platform PC/console games use the same game logic code (though not the same graphics engine) across all platforms. Likewise, LOCKJAW uses the same game logic on the PC, GBA, and DS versions.

That and Microsoft doesn't want you to use PocketPC Word instead of Microsoft Word even if the limited features suit your needs. So in other words, "because proprietary software is still popular."

There were a lot of people that lost their (parallel port) scanners during the 98 to XP switch because of lack of drivers. But Microtek refused to help the SANE maintainers make drivers for numerous ScanMaker scanner models while Microtek was still making and selling them. Unfortunately, there isn't yet much of a Free hardware movement.

Otherwhise just run to your local store and buy a new machine. I would if I had money to move to a town that had jobs.

Re:Winelib

[jawtheshark]

I'm going to stop arguing with you... You do not seem to react to reason.

Look at my sig. I have found P-IV class machines with 512Meg RAM in a dumpster. Totally spyware infested, but that isn't a problem for you is it? You can replace your hardware with hardware that you find in a fucking dumpster. That is as in for 0$.

Re:Solaris FSS

[davecb]

It's not a similar implementation, but it's very much an elegant instance of a very similar idea.

--dave

Re:Well duh

[someone300]

Great comeback, but in all seriousness, O(1) translates to constant time for a varying number of processes. O(n) increases depending on n in a linear fashion. So on, etc.