My OS Design

[m]

Hi,all.
This is my first post here,and if you're not interested in my introduction,please skip the next paragragh.


I'm a senior school student from China.I'm interested in several programming fields and especially on fire for OS development.I've been watching this site for long.However,under the pressure from China's examination-oriented education mechanism,usually I don't have much time for my development and I used to visit this site as a guest.This is my first post after my registration.Thanks a lot to everyone here,for I've benefitted a lot here.I'm glad that we can communicate with each other from now on.


I started my own OS project long before which is still under construction.I focus so much on the development that I haven't named my OS yet.
Here I want to introduce some main ideas in my OS core.(Some of the similar ideas may have existed already,but please read the following text according to the context.Some definitions and algorithms will come first and the situation in my OS will be specified after them.)

Variable Types
All variables can be either of the 2 types:the Static Variable(SV) and the Dynamic Variable(DV).An SV here refers to a variable with constants only,while a DV refers to a variable with other variables in its expression.For instance,x,y and z are all variables,and x=3,y=x*6 and z=x^2.
Among them x is an SV and both y and z are DVs.
NOTE:the SV is different from the constant in NASM,as a variable's expression can be modified during runtime.In fact,a variable can change its type in this way.

Dynamic Computation Deck(DCD)
the DCD is the environment where the 2 types of variables mentioned above exist during runtime.It's named so because the variables in it can stay "live".Anytime when the value of a variable is wanted(read) by other variables or I/O modules,it's the DCD's mission to return the most updated(sychronized) value of the wanted(read) variable.This is only for the DVs.
For instance,x,y and z are all variables,and x=y*3+7,y=z/5 and z=8,thus y=1.6 and x=11.8.If z is increased by 1(z=9) at some time during runtime,the DCD will update x and y in time so that y=1.8 and x=12.4.Furthermore,if x or y is in the expressions of other DVs such as a DV named w,w will be updated in time as well,etc.,just like a updating chain.

How It Is Implemented(the Algorithm)
The algorithm isn't very complicated but it may be a little difficult to achieve.
When initialized,every variable(both the DV and the SV) is allocated a Notification List(NL) containing the names(not the values or the expressions) of those DVs which have its reference in their expressions.If the value of a variable is modified,the DCD will update all the DVs on the NL of the modified one in time.
However,we have a problem:in the implementation on a real CPU,only one DV can be updated by the DCD at one time.So the Context Queue(CQ) is needed,which holds the DVs that should be updated logically at the same time.When the current DV has been updated,a certain(perhaps not the head one,the reason will be described below) DV at the head of the CQ will be updated.We also need a system parameter called Maximum Delay Number(MDN).This would be useful in such a situation:the same DV appears on the NL more than once.Obviously,to update it in such a short time(at the same logical time)is a waste of time.So if a DV comes to the head of the CQ,the DCD will check if the following MDN items(counted from the 2nd one) in the CQ contain the same DV as the one at the head.If they do,then the DV at the head will be deleted and the DCD will update this DV when the last detected same DV in the first MDN items comes to the head of the CQ(currently the DCD will deal with the one follwing the deleted one),or else the current DV will be updated immediately.
For instance,t,u,v,w,x,y and z are variables,and u=2,v=3,x=3,t=u+v,w=u*x,y=t-u and z=t-9,thus t=5,w=6,y=3 and z=-4.The CQ is set empty and the MDN equals 5.
We can describe the variables NLs as folowing:t(u,v),w(u,x),y(t,u),z(t).The variables in the brackets are the NL items of the variables before the brackets.Suppose u is modified and its current expression is u=v(u=3 currently),then the following events will occrur in the specified order:
1.Because of the fact t(u,v),w(u,x) and y(t,u),both t,w and y should be updated immediately at the same logical time.For the reason mentioned in the paragraph above,the System Scheduler(SS) will select either of them to update.Suppose t is selected,then w and y are put into the CQ(w first).The current CQ is like this:[w,y](The left side is the head).Now t is updated.
2.Because of t's updating and the fact y(t,u) and z(t),y and z should be updated right now.But w is the current head of the CQ,so y and z are put into the CQ.w is deleted from the CQ and is updated.The current CQ is like this:[y,z,y](suppose z was put into the CQ before y according to the SS's decision)
3. The DCD finds y is the head of the queue,follow by a z with another y behind.The second y is now the 3rd item of the CQ.As (3-1)<MDN,the 1st y(which is the head) will be deleted and the DCD will update the 2nd y,after z is updated.So the CQ has changed in such an order:[z,y],[y],[].
So the result should be:u=3,v=3,x=3,t=6,w=9,y=3 and z=-3.

Other Features That May Infuence the Algorithm
In order to prevent one variable's calculation's taking up too much time,I combine this algorithm with some other multitasking mechanisms such as the Round-Robin.And in order to make the algorithm more effective,the DVs should be updated only when it's being wanted by other DVs which are being wanted,or it's being wanted(read) by the I/O modules or the users or something else.The phrase "in time" used above just refers to this.

The Scope of My Implementation
The 2 types of variables(the SV and the DV) are one kind of runtime object in my OS,namely the Idx[Calc.](Idx is short for Index,and there're 3 types of Idxes in my OS,they are similar to the thread but still have difference.I'll post later to specify them in detail).It has a serial code(like the expression,however,it's binary code) and an external data(like the value) basically.
In summary,the DV is a little like the function returning value in C,but it's scheduled dynamically to achieve the sychronization(updating).



This post mainly contains the basic theory of the most important ideas in my OS core.I'll post later to show you more description about the detailed things in my OS,mainly on the Idx.

I really want to hear your voice on this post,no matter you support my ideas or not.All comments are always welcomed.And you can contact me by E-mail if you want.

Thanks in advance if you can read it and reply.

[carbonBased]

What you've described (to me) sounds more like a programming language/configuration scheme then an OS design. I like the concept, but I'm anxious to hear how this ties in with your OS -- ie, what would these variables typically be used for? How would applications, drivers/kernel modules, etc, utilize them?

Coupled with an interrupt setup, I could see this being very useful for device drivers, etc. For example, a serial port driver's buffer may be based on the baud rate (for the sake of an example)... writeBuffer = (1/baudRate)*1024. As the baud rate decreases, the buffer will increase.

This will only be entirely effective, however, if the serial port driver is notified every time the baud rate changes (this is where the example isn't so great, as the serial port driver will *obviously* know when the baud rate changes, as it would have been the one to change it, but... bare with me ). To accomplish this, I think you'd also want a form of callback/event mechanism whenever a variable changes. Maintain a list of listeners/callbacks that are interested whenever the state of a variable changes and notify them with the new value.

I'm curious to know if this fits in with your vision, or if I'm skewing your original intentions. Please provide more higher-level detail

Thanks,
Jeff

[Brendan]

Hi,

Hmm - so far it sounds very similar to a post made about 2 weeks ago by Candy...

I guess the next question is, why not implement it as a library to save yourself the trouble of writing an OS?


Cheers,

Brendan

[Candy]

I've posted my code, you can try it if you like. It's PD so if you want to build an OS around it...

[m]

Hi,all.

I've posted my code, you can try it if you like. It's PD so if you want to build an OS around it...

Special thanks for your code.It's really effective.I'll post later to show some other features I've found in both your and my ideas.

I just put the continued part of this post here.

Brendan wrote:

Hi,

Hmm - so far it sounds very similar to a post made about 2 weeks ago by Candy...

I guess the next question is, why not implement it as a library to save yourself the trouble of writing an OS?

So first of all,thank you for providing that post for me.I proberbly missed it.My idea just came in the same way as Candy's,but still different and has something more beyond it.For example,my algorithm seems to be more optimized(please take some time to read it again).What is more will be described below.

But both Brendan and carbonBased think that my idea just sounds like something that is closely related to a language or a libary or something rather than an OS core.

Here I'm telling you something more specific on this idea in my OS core.(Do refer to my first post to look up some defined concepts.)

Overview
My OS is a multitasking and macrokernel one with all programs/procedures existing in either of the 2 type:the System Console(SC) &its related tasks and the Idx(Index).

the SC & the Idx
The SC and the Idx plays a similar role as the thread does in other OSes--They're both the form in which a program/procedure exist during runtime.But in my OS,the Idx is only for user-level program/procedure while the SC is for the OS core(and there's only one SC exists while thousands of Idx are allowed to exist at the same time).Generally speaking,the SC is just like a runtime environment for the Idxes(just like the JRE,but there's a multitasking mechanism between the SC and the Idxes and the Idxes are completely compiled),thus it's just the relation between the DCD and the variables.The SC tries to keep all the Idxes in it live(newest).

the 2 Types of Idxes
2 types of Idxes are defined in my OS core:the Calculation Idx(Idx[Calc.]) and the Input/Output Idx(Idx[I/O]).One type of Idx can ONLY do what its type of Idx can do.(In other words,its type can never be changed during runtime.)
the Idx[Calc.]
This type of Idx mainly consists of these sections below(it's legal if an Idx[Calc.] doesn't have a serial code or a temp data section):
-An external value
-A temp data section(for its internal use)
-A serial code(used to calculate its value as an expression does)
This type of Idx is just the implementation of the variable(both the SV and the DV) mentioned in my first post.The serial code is right its "expression" while the external value is just its "value".The serial code may want to involve some other Idx[Calc.]'s value for its calculation.This can be done by calling a specific system interrupt(the only interrupt this type of Idx can call),and the interrupt will let the requested Idx[Calc.] update its value(if necessary,for some occasions it dosen't need updating) and return what the calling Idx[Calc.] requests in its temp data section.If this Idx[Calc.] has finished its calculation,it's ready to update the external value,etc.Similar things will keep happening in the entire period of a set of Idxes'(both types) execution.(A set of Idxes is known as a Idx Unit,see its definition below.)
the Idx[I/O]
According to its name,you may guess it's usage--it's used to exchange data between the Idxes' values in the RAM and I/O devices.Because of the limitation of my OS drivers,it can only communicate with these three types of I/O devices:the keyboard,the video system and the virtual storage(when it's for the I/O use,it can ONLY be an INPUT device,this will be explained later).Every Idx[I/O] can ONLY be one of the 3 types.
For the output-only Idx[I/O],it can ONLY call the system interrupts related to the video system to display what it would like on the SCreen.It has:
-A temp data section(for internal use)
-A serial code(to organise what to output)
For the input-only Idx[I/O],it can only operate the keyboard and the virtual storage for input.
To input BINARY data from the keyboard or the virtual storage using a system interrupt,the following will be done by the calling Idx[I/O]:
1.Decide what to input(if you want to know more about this,please contact me).
2.Decide where to put the input BINARY data.This can be done by providing an unallocated Idx[Calc.] name,and the input BINARY will be the external value of the referred Idx[Calc.],and this Idx[Calc.] has neither a temp data section nor a serial code.In this way other Idxes can access the input data in a uniform way.
Things come similarly if an input-only Idx[I/O] wants to put NEW Idxes into the SC during runtime,directly from the virtual storage.If the related system call is called and executed,ALL the sections of the Idx with referred unallocated name will be filled with ALL the sections of the Idx which is input,a little like to input BINARY data.Then the filled Idx will work normally as other existing Idxes do.

What is the Idx Unit(IU)
The IU is a set of Idxes needed in a certain computation task.It will be read into the SC from the virtual storage(file system) when a computation task is launched.Every Idx in the IU can save its all sections which is in its last-updated state.
NOTE:My current OS is only expected to be a runtime environment for the Idxes,so it isn't able to modify(e.g.,creating new Idx,deleting Idx,etc.) the existing Idxes.

the Idxes' Writing-Back
In fact,according to the concepts introduced above,every Idx can only write ITSELF and can only READ others.When a task is terminated or an Idx is no longer used,the Idx can call a system interrupt to save its sections before being terminate itself.

Why name it Idx
This is mainly for how an Idx is named.Their names are just like the Internet's domain name and is just a REFERENCE to a certain Idx[Calc.].For instance,we have an Idx[Calc.] named "singers",then we can create another one named "singers.the_beatles" referring to the subject of a certain Idx[Calc.] having something to do with the Beatles or "singers.john_denver" related to something else.Still we can have a 3rd one named "singers.the_beatles.hey_jude" pointing to an Idx[Calc.] related to the song Hey Jude.
However,it's not only a TREE,because we can have another Idx[Calc.] named "hey_jude.author" to refer to the one about the Beatles.In this way ONE Idx[Calc.] can be referred in more than one name,according to the RELATIONSHIP of the application.
This naming method can avoid the naming space conflict somehow and easy to understand.However,it's beyond only a protocol.It is part of the syntax to request values for mass data accessing.For example,"purchases.(?.purpose==gift).price" will return the prices of the purchases which are bought as a gift,so you don't need to pass an absolute name as a parameter.

How do you think this kind of core architecture?
Can you comment on this and give some advice?

[m]

In this reply,I want to specify some features I've found in either Candy's code or my idea and some notes about my version.I'll use the phrase Dynamic Variable(DV) as the core term of this topic.

-The DV,in fact,is the dynamic version of the function with a returned value(such as C's,or the method in Java or something).So if we see further,we can use a SERIAL CALCULATION FUNCTION's internal implementation to replace the EXPRESSION we used in the definition DV.(However,it might not be easy to archieve with a high-level language.In my personal view,the best way to archieve all the DV's features is to add the multitasking program/procedure scheduling mechanism and this would be possible to be put into an OS core.)

-Candy's implementation has much to do with OO mechanism.This can be good to understand and can reduce the annoying net-like analysis in my version.But it SEEMS to be limited in some way(you can refer to Candy's code,it may help you understand this more clearly).

-The so-called DV is just the version of THREAD in my OS.They seems to be data if you only look at the DV's interface,but it's LIVE,based on the environment and its internal code(calculation method).The value of it is NOT ONLY the BASIC DATA TYPE in some languages(for example,the integer,the floating,the double,etc).They are pure binary form created by user(in other words,it's an allocated data block which can be filled with anything),but they're sure to be dynamic.

And I know some of you are not sure about the executing SPEED.YOU'RE RIGHT!I've been take measures to make the algorithm more efficient step by step.The optimization may include to recalculate only when the DV's value is needed by other DVs or is requested by the output module,etc.

[Crazed123]

Just a tip: if you want us to know what you're talking about, please use standard operating system jargon. Those specialized lexicons exist to clarify your ideas!

[Candy]

In this reply,I want to specify some features I've found in either Candy's code or my idea and some notes about my version.I'll use the phrase Dynamic Variable(DV) as the core term of this topic.

I quite agree on the term, I've used the acronym dyn<> for the variable wrapper (and dyn_c<> for wrapping a generic dynamic something).

-The DV,in fact,is the dynamic version of the function with a returned value(such as C's,or the method in Java or something).So if we see further,we can use a SERIAL CALCULATION FUNCTION's internal implementation to replace the EXPRESSION we used in the definition DV.(However,it might not be easy to archieve with a high-level language.In my personal view,the best way to archieve all the DV's features is to add the multitasking program/procedure scheduling mechanism and this would be possible to be put into an OS core.)

I see a DV as an object-oriented assignment, where you don't want to perform a current assignment but a continual assignment. I'm considering adding one more bit, requirements on variables and on derived variables. Using mathematics you can inform the upper layers of transformed limits cropping them where applicable. That way you can determine for variables within which reach they actually mean something and what the valid reach is for them. That's a useful thing in a UI design, where you want to assign the width of a text box compared to the window size, but no smaller than X. That implies a minimum width for the window itself. You can also apply this for mathematical equations. It would allow for instance converging recursive functions, where together with the request for the value a series of checks on the possible value would be sent along. That way, a recursive function would receive an ever reducing window of possible values which would converge to the actual value, which would then be passed back for calculation (and end up with itself). At the moment, it's not right to add a recursive call since your program will recurse infinitely (and crash). My computer performs the infinite loop in a mere 0.1 second, indicating the speed gain Linux has achieved over the past few years (it used to take 5 seconds ).

-Candy's implementation has much to do with OO mechanism.This can be good to understand and can reduce the annoying net-like analysis in my version.But it SEEMS to be limited in some way(you can refer to Candy's code,it may help you understand this more clearly).

How do you think it's limited? If you do see a point where it's limited, how do you avoid that?

-The so-called DV is just the version of THREAD in my OS.They seems to be data if you only look at the DV's interface,but it's LIVE,based on the environment and its internal code(calculation method).The value of it is NOT ONLY the BASIC DATA TYPE in some languages(for example,the integer,the floating,the double,etc).They are pure binary form created by user(in other words,it's an allocated data block which can be filled with anything),but they're sure to be dynamic.

I'm not convinced how you want to model common applications using this model. Can you elaborate, or do you wish to target a nongeneric audience?

And I know some of you are not sure about the executing SPEED.YOU'RE RIGHT!I've been take measures to make the algorithm more efficient step by step.The optimization may include to recalculate only when the DV's value is needed by other DVs or is requested by the output module,etc.

Just for the record, I've taken a few measures to not slow stuff down. All compound constructions directly refer to the next compound instruction, not to a handle. All compound instructions use a pointer, not a vector. Changing a variable also changes the functions in which they're used (and doesn't leave the old one floating around). No variables are recalculated until the last moment. When a variable changes, it sends out change requests that are only forwarded if the object itself didn't already shout out a change without being requested for its value (so if it changes twice between requesting the value, it's not calculated twice).

[Candy]

Just a tip: if you want us to know what you're talking about, please use standard operating system jargon. Those specialized lexicons to clarify your ideas!

That's a bit hard, since we're not talking about an OS thing per se. It's more of a talk about variables that aren't assigned a value but an expression, and for which you can at all times request the current value. Their value is dependant on the expression and can be calculated, but isn't a fixed value assigned at any given time.

I'm still not sure on how to model a full OS on it but I think you might be able to do it. If properly analysed and implemented, you might be able to make a dynamic distributed calculation network. It's more of a blink-factor I think than actual use, but I'm not sure it has no use. It might have a few uses we can't even think of

[Crazed123]

You mean a runtime evaluator that can take program state into account?

Code: Select all

(progn
  (define x 10)
  (define y '(+ x 3))
  (eval y *current-environment*))

==> 13

[Candy]

sorta, but without all the brackets

[Tyler]

It seems to me to be a little like a macro... but at run time... i would love to see a pratical application for it though... this level of freedom with variables could be highly useful.

[Crazed123]

I've coded a Lisp interpreter that does this, but I've never found a way to make the idea work for a compiled language. Due to that, the interpreted version takes a long time to run even simple programs.

However, it is *massively* powerful in terms of available semantics. That seems like a pattern for Lispy and symbolic stuff.

m, you have ideas on how to make environment-aware code compile and run with decent speed?

[m]

Hi.

Candy wrote:

-Candy's implementation has much to do with OO mechanism.This can be good to understand and can reduce the annoying net-like analysis in my version.But it SEEMS to be limited in some way(you can refer to Candy's code,it may help you understand this more clearly).

How do you think it's limited? If you do see a point where it's limited, how do you avoid that?

THANK YOU again for asking this question because it WAKES me up somhow(please just ignore what I wrote about it because I didn't take something extensible into consideration when I took a quick look at your code at first).

I've found some similar points of our ideas.But there is one REALLY BIG difference.It is the GRANULARITY.Candy's granularity is the components which build up a function while that of mine is just a funtion WITH A RETURNED VALUE,which is not dividable.

So in this way,Candy's implementation can be used more freely.Because the basic units of Candy's version,existing in the form just like common variables,can make up functions(I mean methods) by COMBOUNDING.This is wise,I think.

But what I originally thought was that the DVs could be regarded as TINY THREADS and that my OS would provide the UNIT,which consists of a set of DVs and dynamic I/O modules(NOTE:the I/O modules can be developed in the same way as that of the DV) for a certain task, as the form of the PROCESS.And the task is the application and is controlled by the system console.Multitasking will work in the level of both the DVs and the tasks(units).

Now I considering combining them together.The result may be a system SERVICE(perhaps more specificly,a customized interrupt) for this function.The user-level programs have to apply for the naming space and the memory for a DV by calling the service if necessary.Then the requested DV will be generated(by allocating the space and the rights of reading and writing it for the user program) and managed by the system and accessed by the user programs.

However,in this method,some of the original features of my version may be lost.For example,the system has to have a more complicated writing-protection,which may lower the efficiency,because a traditional thread/process may have more than one DVs(In the FIRST version,the tiny thread can work in the SAME way as the DV with a MATHMATIC expression does,which is that every DV can only modify itself and ONLY BY DOING THIS can it influence other DVs).

[Candy]

I think I like this thing

I'm going to spend the night to make it compile with GCC 4.1.1 with all things C++0x has to offer (I'm thinking of right-hand references and variadic templates) and I'll then add a generic apply() function and an assign_if() function.

I just now thought up, you can probably use it with strings as well. The impossible operators (-, *, /) won't be compiled in if you don't use them due to the nature of templates. That way, you can make dynamic strings. I'm going to have to try that once to see what it does, but I think I'll be wrapped up in all-new unknown compiler errors for the night .