OSDev.org

Hi,
In Kinetic theory of gases we have the concept of an Ideal gas, In Thermodynamics we have the concept of an ideal engine ( whose efficiency is theoretical maximum limit achievable ).Similarly, can't we have a reference operating system ?.We can mathematically define the specification of this operating system,eg we can specify that it operates on Turing Machine M ( standardized for the Reference operating system ) and it supports the following functions and so on.. .( Still to be thought about )

Well, you might ask what is the use? Its quite simple, you mathematically prove that a scheduling algorithm you developed works better than the scheduling algorithm developed by Mr X in certain cases or how much better it is compared to the reference OS.Although it is only of theoretical use,it would be nice to support your ideas mathematically.

{ Apologies in advance for poor English and everything ...}
--Thomas

Turing machines are about computability and not speed, Scheduling is all about response times. In this case, there are numerous O(1) schedulers (which is mathematically optimal), but the perceived effect or sometimes even their actual functioning speed is different.

By any chance, ever wondered why most people use a O(n²) algorithm for sorting?

By any chance, ever wondered why most people use a O(n²) algorithm for sorting?

Answer for the curious or who came here via search: because the worst case is not equal to the average case. Quicksort (for example) is n² worst case, n lg(n) average/best case. (for time, not space.)

The complete answer: in the average case it executes faster than other sorter algorithms, including all the textbook algorithms with the "better" n·log·n worst case.

For some things at least, references can't be defined in this area. As an example, if you see a complete OS as a human-machine interface that helps the user getting things done with its hardware, you will sooner or later encounter the usability quality criteria. But there is no such thing as an absolute reference of usability, since it depends on the user goal, experience of computing, etc...

This might be a bit of nitpicking, though.

Hi,
I used the term Turing machine for more precision, multi tape random access turning machines represent the modern day computer to some extent.The problem I find is that there is no precise definition for what defines an operating system, some books give the definition as a resource manger . Others give the picture as an extended machine (something which I am interested in ).The idea is to use queuing theory to formalize thread / processor interaction.I admit that I have to present a things in a more formalized way.I shall post more on latter point of time when I have actually thought through it completely.

Quick sort gives worst case performance - O(n^2) when the data is already sorted { if you follow the text book algorithm as such } , which is hardly the case with real data which can be in any arbitrary order on which it gives good performance ( n * log n).

I would like to thank both Combuster and Neolander for their inputs .


{ Excuse my poor English and lack of clarity in this case }
--Thomas

Combuster wrote:The complete answer: in the average case it executes faster than other sorter algorithms, including all the textbook algorithms with the "better" n·log·n worst case.

Of course, the sane person uses introsort

Thomas wrote:Well, you might ask what is the use? Its quite simple, you mathematically prove that a scheduling algorithm you developed works better than the scheduling algorithm developed by Mr X in certain cases or how much better it is compared to the reference OS.

This is not difficult to do at all. Actually, all depends on how narrow your case is.
The real challenge is figure out math formula for specific scheduling algo to use at the moment for a specific user under specific circumstances while using decent time interval for such formula to make a difference in speed increase.

Thomas wrote:Kinetic theory of gases we have the concept of an Ideal gas, In Thermodynamics we have the concept of an ideal engine

There is another problem according to my belief - the ideal stuff is a lie(physics, chemistry or programming) because it constantly changes, but the 'ideal' changes much faster in CPUs rather than physics. So during your life span concepts of physics may change only once while in the area of programming changes happen much more often. In reality however, the 'ideal' is only limited by human imagination.

The Ideal gas laws do not constantly change. They're an established approximation - for most conditions, they provide a very good estimate of the real situation, and one can use them to calculate various information to quite high precisions.

Nobody claims that the ideal gas law is perfect - an ideal gas doesn't exist. For a start, an ideal gas doesn't undergo phase transitions - but every real material can be turned into a liquid or solid!

You can consider an ideal gas equivalent to a Turing Machine, or a perfect resistor or capacitor: Something which doesn't exist, but provides a very good model or reference standard to compare against.

Hi,
Sorry to awaken this thread after a long time . But some one else has done good work in this area, I would like you guys to take a look at this book by Ian D Craig. http://www.amazon.com/Formal-Models-Ope ... 1846283752

There are good arguments in this book on why such a reference model can very well be justified.


--Thomas