“volatile” – 2: Memory Models

Whenever a talk begins about the “volatile” constructs in programming languages, the chat goes all the way to “Memory Models“. Unless one is familiar with the concept of the memory models, it will be hard to grasp the concept of “volatile” inner workings.

It is already known that “volatile” is about the threading operations. As the name implies, it is about volatile variables that may be subject to change between thread calls (in a nutshell this sentence describes the motivation behind it). But what it really is always behind the closed doors of compilers, CPUs, CPU caches, main memories etc. So what happens when a multithreaded code with shared variables runs or compiled?

Usually with higher level languages (especially that are first compiled to an intermediate byte code) developers need not to give much attention to these details. Because the platforms that will later compile this byte code to the native language of the machine in that the code runs (JIT Compilers, Native Image Generators [NGENs]) give assurance on the behavior of the underlying hardware and of the compiler that will compile the higher level language to byte code or to the machine code. This assurance is what we call the “Software Memory Model“. So a developer could write one code, and by the magic of the byte code, it will run on many processor architectures without fine tuning. On the software side, it is a contract between the developer and the software platform provider. “Hardware Memory Model”, on the other side, is an assurance from the hardware platform provider to the software platform provider for code execution in hardware.

As it can be seen, the concept of “memory model” is twofold. The first one is according to the developer point view. It is how a developer sees a memory model. The software platform provider is responsible to obey by it. On the hardware side, the second one, the manufacturers also define memory models for their processors. So it becomes a contract between the software platform provider and the hardware platform provider. Let us first go over hardware memory models and try to understand what they really are.

Hardware Memory Models

Strong Memory Models (older models of processors)

(This is something I have made up to draw the distinction between the memory models.) “Strong Memory model” name can be given to the memory models that were used before. The code that is given to the processor is executed as is. No reordering, no optimization, and no cache coherency (cache coherency: in multi-processed systems caches holding the copy of the same variable from the memory). What is written to the cache is directly will be available to other threads no matter in which processor they execute on (If a single processor system, which most of them were, then no worries on the cache coherency). What is read from the cache will be up-to-date one. So no optimization that will change the behavior of the code will occur.

Weak Memory Models (newer models of processors)

Weak memory model is an attempt to improve the performance of software [1]. In this model, CPU is given the freedom to reorder [3] or optimize the program sequences (that reside in memory) whenever it sees fit. If a reorder is at hand and if it will not break the real execution order of the code, then a reorder could be implemented. So, what this means is the processor is not giving any assurance on the order of code but in the overall execution. This is what it is called the “as-if-sequential” execution. The overall effect of the software would be the same and the user or the developer will see the execution as if completed in the same order. Also some other optimization of code could occur and the CPU will honor the optimization if it will not break the overall execution effect.

The Ups and Downs of the Both Systems

Strong memory model are easy to be developed in and has less performance characteristics. It is this feature that lead to the weak memory models. CPU would reorder or optimize the code if it sees some optimization is ahead.

The Hardware Structure That Gives Way to Race Conditions

For the sake of simplicity, we first assume that we have a system of one processor having only one level of cache system. Then we will talk about what happens when the system is made up with two of those processors.

In this system, cache always is up-to-date (if no mapped I/O operation occurs). Because there is only one cache then we cannot talk about cache coherency problems. The only problem that will surface will be the reordering operation in multithreaded applications. If a thread is reading a variable, it is seeing this from the cache value and because there is no other cache (or CPU) that will change this variable in the main memory, then the operations will be safe according to the last value of the variable. Multithreaded applications, in this type of systems, must take cautions on memory reordering problems, though. What can be done to overcome the memory ordering in these systems? Memory Barriers can be used to overcome this reordering. In that, volatile can be expensive but for the sake of portability for other platforms, they can be suitable

If the system is made of two processors and two caches (each one for a CPU), then a variable will have the danger of being manipulated by more than one thread executing on different CPUs. If a thread is executing on the CPU1 and writing to Cache1, and another thread is executing on CPU2 and writing on Cache2, the same variable could have two different values on two different caches at the same time. Of course, the cache value will be written to the main memory but the timing of it could lead to race conditions. The value may be changed long before another thread is trying to access the variable which it read from the local CPU cache. In this situation, cache coherency protocols [2] take the action for the consistency of the caches in a shared memory model. This consistency model can be applied in many ways to many processor architectures. For example, Intel x86 processors, writes are always volatile, meaning if you are writing to a variable, the cache will be invalidated and the value will be written to the memory at once.

Software Memory Models

The first language to define a software memory model was Java (It will be the subject of another article). Because Java made a promise to the developers that if you have written one code then this code will work in every platform Java runs on. But hardware platforms are different when it comes to memory management. Every platform had its own memory model. What Java did this time was to implement its own memory model which Java would promise to the developers that if you write code according to this memory model, it would work everywhere [4].  Later on, other programming languages implemented their own memory models, including C # [5].

 

Conclusion

Now that we have learned what a memory model is, then we are ready to go on the java concept of volatile and its bitter history. See you on the next article…

References

1-Weak Ordering – A New Definition

http://www.cs.utexas.edu/users/dburger/teaching/cs395t-s08/papers/13_weak.pdf

2-The Performance and Scalability of Distributed Shared Memory Cache Coherence Protocols, Chapter 2: Cache Coherence Protocols, Mark Heinrich Ph.D. Dissertation Computer Systems Laboratory Stanford University October 1998

http://www.csl.cornell.edu/~heinrich/dissertation/ChapterTwo.pdf

3-Chapter 8.2 Memory Ordering, Chapter 11 Cache Control, Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3A

http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html

4- Chapter 17.4 Memory Model, the Java Language Specification Third Edition, James Gosling, Bill Joy, Guy Steele, Gilad Bracha

http://docs.oracle.com/javase/specs/jls/se5.0/jls3.pdf

5- Volatile keyword in C# – memory model explained

http://igoro.com/archive/volatile-keyword-in-c-memory-model-explained/

A Tribute to Tony Hoare

Tony Hoare (aka C.A.R. Hoare, age 78) is one the pioneer in the computer science field and the creator of the QuickSort algorithm. Also, he is the man behind the Z specification language, CSP (Communicating Sequential Processes) concurrent programming model (like dining philosophers problem) and Hoare logic (correctness of software).

He is also the creator of the Elliott ALGOL compiler (and implementation of ALGOL 60).

He currently works as a principle researcher (after decades of academic career) at Microsoft Research, Cambridge, England [1].

Here is a couple of quotes from him:

1-I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. In recent years, a number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965 [2].

2-“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult” [3].

3-“[About Algol 60] Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors [4].

5-Science  vs. Engineering [5]

Science Engineering
long-term short-term
idealism compromise
certainty adequacy
perfection risk
generality specificity
separation amalgamation
unification diversity
originality best practise
formality intuition
correctness dependability

6-“concurrent programs wait faster”[6].

 

References:

1-http://research.microsoft.com/en-us/people/thoare/
2-http://qconlondon.com/london-2009/speaker/Tony+Hoare
3-The 1980 ACM Turing Award Lecture
4-http://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf
5-http://research.microsoft.com/en-us/people/thoare/scienceandengineering.pptx
6-http://research.microsoft.com/en-us/people/thoare/concurrentprogramswaitfaster.ppt

Plate Tectonics: Expanding Earth or Moving Plates?

Recently, in the History Channel there was a documentary named “How the Earth Was Made”. This documentary was about the movement of the earth’s crust and the explanations around the “Plate Tectonics” theory. It was a two season series that in each episode, looked at some mysterious or unexplained earth structures and tried to explain them with the “Plate Tectonics” theory.

It is an incredible subject. According to this theory, earth’s crust is made up from distinct plates. These plates are in motion. Imagine that the plates are moving, bumping to each other and creating mountains and changing the world climate.

Just watch the documentary and you will learn a lot from it, at least some explanations for the geography that seem unbelievable to the naked eye.

We can give examples of the movement and the effects of it. Plate tectonics explains the Himalaya Mountain Ranges with the moving plates. According to it, the Indian Subcontinent once was together with the African Plate and after they separated, it crushed to the Asian Plate. Two plates are now pressing each other. From this the Himalaya Mountains are born. The pressure still continues and the Everest is still rising up a couple inches a year.

It also explains some of the earthquakes and the creation of the volcanoes in the Belt of Fire or elsewhere. The concept of a hot point is a curious thing  which caused the creation of Hawaiian Islands.

According to the theory, what makes the plates move is the inner pressure of the molten rocks, the magma.

If you think that way, everything seem to fit perfectly.

But there is another theory. Instead of the moving plates, this theory tries to explain the changes in the earth’s crust with the Expanding Earth theory. According to it, the process of the changes are the result of the expanding earth.

Check out

Expanding Earth and the Pangaea Theory
http://www.youtube.com/watch?v=3HDb9Ijynfo

and

Plate Tectonics and the Expanding Earth
http://www.geologynet.com/tectonics1.htm

“volatile” – 1: C#

Volatile constructs are primitive thread synchronization constructs in the .Net platform. The main usage of them can be listed as:
  1. Disable the optimisation intended for single threaded applications, which most of the compilers assume. Meaning, they are flags for the compilers instructing them not to optimize the code according to the single threading.
  2. Disable caching in hardware, either in a thread variable or in a CPU register.
  3. Behave as a memory barrier construct (this will be explained later in this article).
1-Disabling the Optimisations
(to make the optimisations work, compile your code with “/platform:x86″  and “/optimize+” switches)
Take a look at the following code (taken from “CLR Via C#” 3rd Edition, Jeffrey Richter)
private static void OptimizedAway() { 
   // Constant expression is computed at compile time resulting in zero  
   Int32 value = (1 * 100) – (50 * 2);  
   // If value is 0, the loop never executes 
   for (Int32 x = 0; x < value; x++) {  
       // There is no need to compile the code in the loop since it can never execute 
      Console.WriteLine(“Jeff”); 
   } 
}
Compiler will see
Int32 value = (1 * 100) – (50 * 2);  
and will convert this to
Int32 value = 0;
and because the value is zero, then the “for” statement will not work, so the compiler will remove the code (optimize away).
There may be many situations like this. To tell the compiler no to implement this one must define the variable “value” “volatile“.
2-Disable the Caching
When a variable is declared to be volatile, when ever its value is read or written, it will be done via the main memory. So the caching mechanism will be disabled, i.e., the CPU registers. It will be the up-to-date fresh value from the real place it resides, the main memory. Because of this, volatile fields are slow in respect to other type of variable access.
3-Behave as a Memory Barrier
volatile” keyword, in C#, is a shorthand for Thread’s “VolatileWrite” and “VolatileRead” methods.
Compilers (even CPU) can order the execution of a program different than the one indicated by the programmer. This is OK in most situations or in a single threaded application. But in some situation, you need your codes to be executed in the same order you entered. This is where a memory barrier comes in to the picture. Let us see by examples:
[Wikipedia Sample]
Processor #1:
 while f == 0
  ;
 //A- Memory Barrier required here
 print x;
Processor #2:
 x = 42;
 //B- Memory Barrier required here
 f = 1;
if any of the operations are executed out of the order by the compiler or by the CPU, then the result will be quite unexpected. To disable this, memory barrier should be used.
In C# three constructs provides this feature and they are
public sealed class Thread {  
   public static  void  VolatileWrite(ref  Int32 address,  Int32 value);   
   public static  Int32 VolatileRead(ref  Int32 address);  
   public static  void  MemoryBarrier(); 
}
a-Thread.VolatileWrite
In the above example, if I write Thread.VolatileWrite in places indicated, I would ensure that, this code (Thread.VolatileWrite) will work in the place I intended to. And any operations that I wrote before will work before this code (Thread.VolatileWrite). But the operations written before does not necessarily must be in the same order I have written them.
b-Thread.VolatileRead
It is similar to write construct with only one difference. This is a read construct and the operations after that will execute after the code (Thread.VolatileRead). Still, Thread.VolatileRead will execute at the point where I intended it.
c-MemoryBarrier
It is somewhat the combination of the two above mentioned methods. It does not read or write any variables but it will execute at the same point the program intended and the calls before it will work before it and the calls after it will work after it.

“static” Keyword in Programming Languages

Many programming languages have integrated the notion of “static” into their nomenclature. Most of the “Object Oriented“ languages have integrated it as “class variable” (as opposed to instance variable).

Now, if we want to describe the notions of class and instance variables we would say a class variable is instantiated when first a type is referenced via the static members or when first instance is created (.Net and Java is like that) or type is loaded into the memory (C\C++ is like that). An instance variable, on the other hand, is created when any of the class constructors is called.

There is also the notion of “static class constructor“s. In .Net you would create one as:

sealed class MyObj
{
      static MyObj()
      {
            //Access static members and initiate
      }
}

In Java, this is accomplished with “static block“s. It is the same as its .Net counterpart, only the syntax is different.

final class MyObj
{
      static
      {
            //Access static members and initiate
      }
}

In C\C++, it is a bit different tough. “static” is either a “storage class” definition or is the same as above. If it modifies a variable in the top level (out side of any function call and any “class” definition) then the variable it defines will be visible to the file only. There no similarity to the “static” word in the other languages for this use. For example, below is a header file, named “myinclude.h”:

#ifndef _MYINCLUDE_H_
#define _MYINCLUDE_H_

static uint mynumber = 0;

#endif

In this file, “mynumber” will only be visible to this file and the files that include “myinclude.h”.

On the other hand, in C++, if a “static” variable is defined inside of a “class” then it is the same usage with C# or Java.

struct Request {
      static int count;
}

Open Source Community: Their Life Style and Mentality

If you are familiar with the “open source” movement, you already must know Richard Stallman. The man behind the “copyleft” (as opposed to copyright) paradigm. They advocate the idea of a software being free of any charge, either in using or in distributing.

Also legendary Linus Torvalds: The man behind the most spread operating system after Microsoft’s.

Of course, we cannot individually count each one of them, for they contribute to the open source projects from all over the world. But this writing is not about the individual men that brought about the revolution, it is about the mentality that gives them great power.

SQLite is a very small (really! You can can call it “tiny”) relational database management system. It is wide spread because of its performance and small memory footprint. If you ask me I would say it is miraculously simple and powerful. How did they do it? Just check the code. All the things that make up a system is inside that four megabytes of code. Be it the parser, be it the statement compiler.. All there.

Here is a small comment from the head of every code file it contains:

/*
** 2005 February 15
**
** The author disclaims copyright to this source code. In place of
** a legal notice, here is a blessing:
**
** May you do good and not evil.
** May you find forgiveness for yourself and forgive others.
** May you share freely, never taking more than you give.
**
*************************************************************************

Wow! That is something comes out of the mouth of a saint!

This is just a sample of the behaviour.

Open Source Community loves animals. Most of the software names or any other names they give are animal names.

-GNU is the name of the project that Richard Stallman started to make an open sourced operating system. Until now it was the driving force behind the open source movement.

-The mascot of the Linux operating system is a cute Penguin.

-FireFox, FireBird etc. are Mozilla (oops!) Foundation’s open source products. Other products include SeaMonkeyBugzilla, Thunderbird.

-Hodoop was the name of the toy elephant of Doug Cutting‘s (one of the men behind Hadoop) son. Related to Hadoop; Pig, Hive, ZooKeeper :) ..

You can increase this list beyond books.

Now that we saw they like animals, now let us see what other things they like.

When Java was first being developed, it had the name Oak. Because of the oak tree just outside of the office they worked. Later it was changed to Java (this is what they say in “Learning Java” by Patrick Niemeyer & Jonathan Knudsen) because of the coffee they consumed much during development.

Also Java has a notion of “bean” (as in magic bean). A sort of term used for component based development. But, hey! this is a plant name.

Also, my favourite name “swing“. It is also a Java related name and man, it is a nice name.

So, I am saying as they say:

May you do good and not evil.
May you find forgiveness for yourself and forgive others.
May you share freely, never taking more than you give.

Alexander: The Protector of Men

You will see the name “Alexander” no matter on which culture group you are in. Alexander, Iskender or Sikandar are all relatives if you feel like me.

I always wandered why this name is so popular. Is it because of the Alexander the Great? Or is it because of some other relation to the name?

Three “Alexander”s in three cultures I can count for now:

The First

Alexander the Great was a multicultural person. His good behaviour, even to his enemies, made him popular in the regions he conquered. For example, after the Battle of Issus (currently the place is in Hatay/Turkey – ask for Issus Ruins for the city. The place where the war was made is still under debate but should be near to Issus ruins, for, the battle was named after her) Darius III even left his household and fled from the battle field. Alexander treated them as if they still are royal.

Wherever he conquered, he conducted marriages between his soldiers and the locals. Even he married to a local princes.

I think this alone made him successful in his conquest. Hellenistic civilisation was the result of this manners.

This is the great legacy of Alexander the Great.

The Second

In Judaic (for some) and Islamic culture, you will come up with the name Dhul-Qarnayn. Many will call him “Iskandar-i Dhul-Qarnayn”. In the Old Testament (in the Book of Daniel 8:20, as being said by some) and in the Qur’an, we will find references to him. In Qur’an, the incredible journey he took is told much like the ones Alexander the Great had taken. He is famous with the name “Iskandar”. This is also interesting. Because of this, many believed the two are the same: Alexander the Great and Dhul-Qarnayn. You can join on this debate on the web.

The Third

Skanda (Murugan) is also of interest in the Indian subcontinent.

Conclusion

The identity of the first Alexander is obvious, the others are in debate.

From these notes what I can deduce is if we think out of the pronunciation, the meaning will give us hints: “The Protector of Men”. With this, all three (many more may exist) can make sense. It was the meaning they had in common, not the Greek word itself. And we know, Hellenistic culture once ruled over the known world and this may be the reason why the word itself is used for.