Ways of Sleeping in Linux Kernel

There are 2-3 different ways of sleeping in Linux Kernel.

The first and simple way of sleeping is to set the state of the current process to either INTERRUPTIBLE or NON_INTERRUPTIBLE and then call schedule. Setting the state to something other than RUNNING is important because only then the kernel will take the process out of running queue. Now that the process is scheduled out, it has to be scheduled back in some way – that is achieved using wake_up(). It takes the task_struct of a process as a parameter. Here is a sample piece of code gotten from Linux Journal:

//Process A:
if(list_empty(&list_head)) {

/* Rest of the code ... */

//Process B:
list_add_tail(&list_head, new_node);

There is one race condition problem in the above piece of code which results in “Lost Wake Up” call. It is as follows: the process checks for some condition and then sets the task state as interruptible and goes on to sleep. There can be a small race condition where the process which fulfills this condition will wake up the process (waking up is just setting the task state to RUNNING and keeping it in run queue) just after the condition is checked for – this results in a situation where the sleeping process has gone to sleep after the waking process has woken it up – this is the lost wakeup problem. The consequences of this can be serious or not. If this is the sleeping process that is going to mark the condition as false and goes on to sleep further, then this lost wake up problem results in the sleeping process remain in that state forever. However, if the condition is satisfied externally, then eventually the condition will become true again and the waking process will wake up the sleeping process. The fix for this is to set the task state before making a check – so if the process goes to sleep, then it will be just kept in the running queue instead of wait queue. schedule() API will keep the process only in the running queue is the task state is running.

One more issue with this form of sleeping is that the waker process has to know the task_struct of the sleeping process. This can become tedious when there is more than one process involved in sleeping. So, another form of sleeping in the kernel is to use wait queues. Here is a sample piece of code that declares a wait queue and keeps itself in the wait queue.

wait_event_interruptible(my_event,  (cond == x));

void my_wake_up(void)
    if (cond == x)
    set_bit(2, &my_flags);

As can be seen in the above piece of code, when we go to wait in a queue, we also pass a condition to be checked against – so the kernel will make sure that this condition is not true before keeping the process in the wait queue. The kernel will change the state of the process and then check the condition and put the process in the wait queue. When it is time, a waker process will come and wake up process on the wait queue – that way, it need not know which process is sleeping, all it knows is the wait queue. Somewhat better than the earlier non-scalable form of sleeping. There is also a API wake_up_all() which will wake up all the processes – this API results in a thundering herd problem if not used properly. However, there are use cases for this too – for example, the problem of multiple readers and one writer can use this API – when the writer has acquired the lock, all the readers will be put in the wait queue – when the writer is done, it can do a wake_up_all() of all the processes in the wait queue. All the readers will successfully acquire the lock.

Another way of sleeping is to sleep for a definite time period. The process can sleep for so many jiffies or it can sleep for so many milliseconds/seconds. Here is a sample code for sleeping in milliseconds.

read_done = 0;
while (read_done == 0) {
  msleep(2); //sleep for a couple of milliseconds.

// Another thread
read_done = 1;

The process does not know how long it is going to take, but is sure that it is not going to take long – so it chose to avoid creating another wait queue and simply used msleep() API to sleep for a millisecond. Sooner or later, the condition becomes true and the process moves forward. This incurs a small overhead on the CPU in terms of context switch etc., but it is a simple design. BTW, if we want to sleep in jiffies, then one can use a schedule_timeout() API. Internally, it is going to add the process to some wait queue and then wake it up when it is time. msleep() also does the same thing.


The World is Getting More Asynchronous

I stumbled upon this fascinating article by Terry Jones on synchronous and asynchronous communication. What fascinated me was the breadth of examples he gave for a/synchronous communications.

Here are some for synchronous communication:

telephone calls, in-person meetings, a parent teaching a child a song, an audience listening to a public lecture or a live concert, buyers and sellers negotiating prices at a market

And here, for asynchronous communication:

the invention of writing,Β Post-it Notes, blog-posts, and what’s more dog pissing on lamp posts. πŸ™‚

Anything that does not involve the source of the communication directly is asynchronous in nature. For example, a bill-board tells us about something that the source (say the ad-owner) wants to say. And technology is playing a very big and prominent role in facilitating the absence of source of the communication. In a sense, this is a revolution.

Synchronous communication is expensive (in terms of the time consumed, energy spent etc.) when compared to asynchronous communication. Moreover, synchronous communication is more centralized. Asynchronous communication is scalable as it is not centralized by its very nature.

The author talks about some FluidDB that embodies this asynchronous notion and how it benefits us all, I am eager to know more about it.

R-RAM the New RAM

Resistive RAM is something that is gaining attention in research now-a-days. While the traditional RAMs – static, dynamic and flash – store the data (i.e. the bit) in the form of charge, R-RAM stores it in the form of resistance – apply some voltage to the “cell” and it increases its resistance and can decrease it as well when voltage is applied in another direction.

What’s the big deal? One thing that stands out is its non-volatility. Other things are less power requirement, faster access times etc. If we get non-volatility in the RAM itself while not compromising other factors – performance, more importantly, then what else we need?

Impressed with Processing

I have just started using Processing just for the fun of it. And the ease with which one can create graphics with Processing is evident straight out of my second program. The program is very simple:

void setup()
  size(120, 480);

void draw()
  if (mousePressed) {
    ellipse(mouseX, mouseY, 40, 40);
  } else {
    ellipse(mouseX, mouseY, 80, 40);

As the mouse moves, one can draw an ellipse or a circle (with a click of it). The code looks very clear and it is very simple – yet it gives a rich experience when executed. I am loving it. πŸ™‚ Next thing, I will persuade my wife to indulge herself in Processing.

What is So Special About Python

Peter Norvig says:

Several students claimed that they had a hard time mapping from the pseudocode in my AI textbook to the Lisp code that Russell and I had online. So I looked for the language that was most like our pseudocode, and found that Python was the best match….I found that Python was very nice for certain types of small problems, and had the libraries I needed to integrate with lots of other stuff, at Google and elsewhere on the net.

And a nugget:

I think that language choice is not as important as all the other choices: if you have the right overall architecture, the right team of programmers, the right development process that allows for rapid development with continuous improvement, then many languages will work for you; if you don’t have those things you’re in trouble regardless of your language choice.

URL Shortening

Well, I am back on this one, after I saw a post on Oreilly Radar.

What could be the shortest possible domain name for a URL shortener? I mean, How many minimum number of letters has to be there? It is 4 – two for the domain suffix of the country and one for dot and one letter of our choice – I mean really our choice. There is a site that keeps a unicode character as its first letter: http://tinyarro.ws/ – the “tinyarro” translates to the “arrow” character and so is one letter. :-). But I wonder, if somebody has to type that, how are they going to do it? What’s more, this website wants us to choose the encoded URL string as well – I would say that is bad. One should not leave too much to the user in this case – the act of entering and re-entering (in case one string is already used up) is time consuming – I doubt whether anybody is interested in spending a minute or two in framing a short URL for the link to be posted – definitely not me!

A short de-tour here: There are websites that tell you – as you type – whether a given domain name is available or not. This one, for example. I wonder at the innovative capabilities of people creating businesses. Any business, in my opinion, has two fundamental questions to ask – a) how do you add value and b) how do you generate revenue. May be for non-web2.0 businesses, a implies b, but in general, for the web 2.0 services, that is not the case. “B” has to be thought out even though “a” is more straightforward. In this case, the value added is the ease with which one can find whether a domain name exists or not. AJAX will tell you on the fly about the status of the same. And what about “b” – put the ads of web hosting service providers, domain name registration helpers etc. That sounds to be a sure shot of making business (at least to me).

So, one part of the race is how to make the domain name shorter and another is how to make the URL encoded string shorter. This is more of a technical problem rather than non-technical.

Let’s consider the problem of doing business with shortened URLs: what is the value add to the end user? – use shortened URLs in your tweets or other space constrained services – other than this there is no use. It may cause more harm than benefit to the end user as the user does not know what s/he is clicking. By the way, the one who adds value and the one who pays for the value are not the end user. πŸ™‚ The end user is just a free user of this service. So, naturally, side effects. πŸ™‚ So, who is adding value to whom? The URL shortener is adding service to the other websites – since the click-o-rama now routes through the shortening service, the URL shortener is in a position to explain how much the web traffic is driven by one particular site – the website owners can consume this information, take it as a feedback or complement and improvise the services offered.

Whether or not, there are good uses of URL shortening, there are definitely evil ones – a spammer can use the service just like anybody else to know whether people are clicking on the links or not. One post talks about ten evil uses for URL shortening. It is not necessary that a spammer rely on the service, the spammer can also use the web logs to figure out the same.

In short the issues with URL shortening are – stability, privacy, security, performance etc.

Promising Solar Energy Transformation

We know of two ways – convert sun light into electricity and into heat. The former is more inefficient, the latter is more leakage prone – i.e. it has to be used immediately or the energy gotten in the form of heat is lost.

MIT now has found another way of transforming solar energy: using chemical reactions. That is, the sun light is absorbed by a chemical, the energy is stored (by the elements going to higher orbits) and then it is released later in the form of heat.

Two things that stand out in this new way are: heat is “storable” without any leakage. The chemical after absorbing the heat can remain like that for years! And secondly, the process is completely irreversible – the chemical can come back to its original state after heat dissipation. Two good, interesting characteristics. Nice discovery!!

However, the glitch – the chemical is made of ruthenium and is quite expensive. But, what scientists found out is the process, structural characteristics – both the statics and dynamics that will help them find similar, cheaper molecules (by running it through the database of millions of chemicals). I hope they do find one!

I find one more glitch – it is like a heavy battery that needs to be taken here and there, unlike the other two solar energy transformers. Also, the molecule should take in energy only in the form of sun light – and not in the form of heat – lest the dissipated heat will be absorbed again (uh, oh! what kind of a thing is that?)

This is one example of funding a research that will make people’s lives (and that of environment’s as well) better. Will see this happening in the planet’s largest democracy?