What will be the next revolution in task execution?

Task execution and scheduling concepts came into limelight with the advent of multi-processing Operating Systems. Unix made processes popular and then SUN made threads popular (the defacto now for task execution). What do you think the next wave will be?

[RFC] How many addresses can you take in C?

Well, I decided that I would post a question and ask for comments. The question is

In the programming language "C", how many times can you take the address of a variable v? So if v is a variable can I use &v, &&v, &&&v, etc? What is the limit to taking addresses?

I think I know the answer and it seems straight forward. Once, I get comments, I will try and illustrate the answer

The Rule of Three or More

I remember learning as a kid, that if a number is divisible by three, then the sum of the digits must be divisible by three. Ever wondered how this rule works and how someone must have discovered it. The proof is really simple and franckly quite amazing. I have been wanting to share it for a long long time now.

Well, lets use this theorem with b=3. Lets take a number 'a' for which we need to figure out divisibility by 3. Lets take an example, say 1021. We can rewrite 1021 as 1x1000+0x100+2x10+1.

Now try using mod 3 for the numbers above (Use Fermat's Little Theorem if you have to - more on that in the blogs to follow).

Any power of 10 mod 3 is 1. 10 mod 3 = 1, 100 mod 3 = 10 mod 3 x 10 mod 3 = 1 x 1 = 1. Thats a simple proof - right?

Now, in our example

1021 mod 3 = 1 mod 3 + 0 mod 3 + 2 mod 3 + 1 mod 3 (remember all powers of 10 mod 3 is 1, hence we are reduced to multiplying the digits with 1)

This is further equal to (1+0+2+1) mod 3 == 1 (Thanks Vinay!).

The proof should be trivial to extend to any generic number, by splitting it into powers of 10 and the digits and summing them up. All powers of 10 mod 3 yeild one, hence we need to use only the sum of the digits mod 3.

If you use a shell

I am sure many of you who use a shell like the bash shell or the korn shell or any other shell for that matter must be power users of it by now. I will probably blog on some fun shell techniques, like the one in this blog.

Korn shell comes with a variant of the "cd" command that very few people are aware of. It is very useful for people who tend to have symmetrical directory hierarchies

Lets assume that you are in a directory structure as shown below

(1) /home/user/programming/drivers/source/cxx

and want to change directories to

(2) /home/user/programming/user_mode/source/cxx

Well, in KSH you can say

"cd drivers user_mode" and it will change from (1) to (2). I love this feature and miss it in the BASH shell, so I wrote my own wrapper (that's why I love *NIX)

function cd
{
case $# in
1) builtin cd $1
return ;;
2) builtin cd ${PWD/$1/$2}
return ;;
*) builtin cd $*
return ;;
esac

}

In fact this version is slightly different from the KSH one, can you spot the difference?

Let me know if you do, I will post your name(s) on this blog

Welcome Sathya to the world of blogging

For all of us who know Sathya N J, lets welcome him to the world of blogging

His first blog is at 360 Yahoo BLOG. I am glad I invited him to 360 yahoo.

Thought for the day

I have been thinking about security for a while. I have come up with a probable law, but I am not sure if it is already well know. Anyway, here goes.

"The More free memory you have on your system, the more your system will be vulnerable to security risks"

Balbir Singh

Stated Mathematically

Security risk is directly proportional to the free memory on your system.

Do you think it makes sense?

I will explain my theory in detail in another posting, sometime later.

Can my blog be audible - part II

I had asked in Can my blog be audible if I can make my blog audible at run time. Well I am glad to say that a 10MB plugin in the Opera Browser enables me to achieve what I want.

After downloading the voice enabler, click on the text and type "v".

Cool! right?

Interesting article to read

By Dijkstra "My recollections of operating system design". The article is hand written and can be found here and the PDF is here

Intermediate Trees

Well, I have Intermediate Tree (IT) output from my tiger compiler. I received some help with the IT generation, but the text output is just not readable. So, what I did was generated a graphical representation using graphviz.

The most difficult thing about IT generation is following static links. I am going to show you the tree and the code that generates it.

/* define a recursive function */
let

/* calculate n! */
function nfactor(n: int): int =
  if  n = 0 
   then 1
   else n * nfactor(n-1)

in
 nfactor(10)
end

and here is the tree

The tree on the right shows the main code

Can you guess what tree the following code will generate

let 

 type any = {any : int}
 var buffer := getchar()

function readint(any: any) : int =
 let var i := 0
     function isdigit(s : string) : int = 
    ord(buffer)>=ord("0") & 
         ord(buffer)<=ord("9")
     function skipto() =
       while buffer=" " | buffer="\n"
         do buffer := getchar()
  in skipto();
     any.any := isdigit(buffer);
     while isdigit(buffer)
       do (i := i*10+ord(buffer)-ord("0"); 
            buffer := getchar());
     i
 end

 type list = {first: int, rest: list}

 function readlist() : list =
    let var any := any{any=0}
        var i := readint(any)
     in if any.any
         then list{first=i,rest=readlist()}
         else nil
    end

 function merge(a: list, b: list) : list =
   if a=nil then b
   else if b=nil then a
   else if a.first < b.first 
      then 
       list{first=a.first,rest=merge(a.rest,b)}
      else 
       list{first=b.first,rest=merge(a,b.rest)}

 function printint(i: int) =
  let function f(i:int) = if i>0 
      then (f(i/10); 
        print(chr(i-i/10*10+ord("0"))))
   in if i<0 then (print("-"); f(-i))
      else if i>0 then f(i)
      else print("0")
  end

 function printlist(l: list) =
   if l=nil then print("\n")
   else (printint(l.first); print(" "); 
       printlist(l.rest))

   var list1 := readlist()
   var list2 := (buffer:=getchar(); 
                   readlist())


  /* BODY OF MAIN PROGRAM */
 in printlist(merge(list1,list2))
end

Well, the tree could take up a whole room, so here is the
condensed version


If you find too many long left/right subtrees, well they are due to static links. The language is tiger, see Andrew Appel's Home Page for more details

WARNING: The IT have not been checked for correctness, I can only hope they are correct.

Blog(net)working

I am really happy about the fact that the number of blogs are growing very rapidly these days. The December 2004 communications of ACM has a great article on the distribution of blogs worldwide. That also means that many of my friends and in-turn their friends have blogs. Almost all of us maintain a set of links on the sidebar linking blogs of our friends. Even though I have not directly spoken to them for sometime now, I get to know what they are upto through their blogs. I like of think of it as Blogworking, instead of networking we have Blogworking. Get it?

Lets keep up the Blogworking.

Please Welcome!

Two college friends of mine, added to the "Blogs of friends of mine" on the sidebar.

Harsha K
Karthik

Wondering What I Have Been Upto?

I have not been updating my blog as frequently as I used to, of late. I have a good excuse, well I am busy with something and I am also working on finishing the tiger implementation. I have learnt many interesting things and I cannot wait to share them here.

A Brief History of GUI

There is great article at ARS Technica. I loved it!

C++ Evolution

If you are interested in the evolution of C++, see these links

1. C++ Evolution Issues
2. C++ STL WishList

Can my blog be audible?

I am exploring techniques to make my blog audible, yes audible!

Unfortunately, I do not own the blog server and hence do not have access to any technology on the server side. I will be forced to implement something at the client end. Does anybody know of a good technology to help me make my blog audible?

Let me know if you do or any suggestions you have

Return Addresses

Andrew Appel states that return addresses were earlier pushed on the stack by the function call instruction. Data shows that it is faster and easier to pass the return addresses in a register. This has two advantages

1. It keeps the memory traffic down
2. It avoids building in any particular stack discipline into the machine

This is certainly true for MIPS, ARM, etc. For the Intel IA32 platform see Notes on Translating Three-Address Code to Assembly Code for the X86.

The return address is still stored on stack. Generally the ENTER, LEAVE and RET instructions are used for stack manipulation. Gcc uses CALL, LEAVE and RET.

The Composite Pattern

The Design Patterns (Gang of Four) book explains the composite pattern. See Composite Pattern

One example of a composite pattern is a file in a filesystem/directory hierarchy. The figure below shows a probable implementation of a filesystem hierarchy using the composite pattern

First Analysis of Swap Space

When I was learning to configure my first Dynix/Ptx system, I was told by a senior team member to ensure that the swap is at least twice the memory size. I asked him what was the logic behind that, he said, it was a rule of thumb. In the time to come, I would learn the some reasoning behind it. I would at this point recommend “Modern Operating Systems, by Andrew S. Tanenbaum”. He uses Don Knuth’s Fifty Percent Rule as the basis for his analysis. Let me explain the Fifty Percent Rule first

The simple explanation of the rule follows. In the state of equilibrium

1. Half the number of memory operations are allocations, the other half is freeing
2. For the half that is freeing, half of those operations result in holes being merged (contiguous ones)

This tells us that the ratio of holes to allocated blocks is fifty percent.

In the state of equilibrium there are half as many holes as total allocated blocks. A hole is referred to as a available memory (free memory). If the total allocated memory in blocks is n then the number of holes is n/2.

The total available blocks is 3n/2 and available blocks is n/2. The ratio of free memory to total available memory (assuming block sizes are equal) comes to 1/3. So if you have 256MB of RAM on your system and want it to be available free for the next task you want to run, then you must allocate a swap size of 512MB, so that the ratio of 1/3 is held.

There are of course complications to this simple rule or calculation that I explained above. I will try and explain some of those complexities in the next series of swapping articles.