Approaches to realtime Linux [LWN.net]

Approaches to realtime Linux

Posted Oct 12, 2004 21:26 UTC (Tue) by Quazatron (guest, #4368)
Parent article: Approaches to realtime Linux

As a non-programmer, I'd very much like to see LWN run a simple article explaining the differences between semaphores, mutexes, spinlocks, etc.
I really like to read about kernel programming, but those structures are a complete mistery to me.

to post comments

Quick and dirty guide to locking primitives

Posted Oct 12, 2004 23:29 UTC (Tue) by aya (guest, #19767) [Link] (1 responses)

Locking is all about not letting multiple processes do the same thing at the same time. For
example, say there's some code where every time it gets executed, it increments a counter
somewhere. Let's also say that to increment the counter, first you have to read its value,
then you have to add one to it, then you have to write it back. So, it's a three step process.
That means anyone incrementing the counter could be interrupted (preempted) in the
middle. If two processes are trying to increment the counter at the same time, something
like this could happen (in theory):

* process A reads the counter (counter = 1) and is interrupted
* process B reads the counter (counter = 1), adds one to it, and stores it back, then is
interrupted (counter now = 2)
* process A adds one to the value of the counter that IT read and stores it back (counter
now = 2 instead of 3)

Since process A had read the counter before process B stored the new value, it writes back a
wrong value. You can protect operations like this by using locks. in this case, to increment
the counter, you'd have to have control over a lock. You take the lock, do all the counter
incrementing, then release it. Since only one process is allowed to have control over the
lock, and our rules say you have to have control over the lock to increment the counter, the
above situation would look like this:

* process A takes the lock and reads the value of counter (counter = 1), and is interrupted
* process B tries to take the lock, but fails; it gets interrupted while waiting for the lock to
be released by process A
* process A finishes incrementing the counter (counter = 2), releases the lock, and gets
interrupted a little while later
* process B tries to take the lock again, succeeds, and increments the counter to 3, releases
the lock, then gets interrupted

Since the lock ensures that counter access is mutually exclusive among processes - that is,
only one process can do it at once - locks are often called mutexes. Also, any piece of code
that requires mutually exclusive access is called a critical section. In this case, incrementing
the counter is our critical section.

There are two basic kinds of lock in Linux: spinlocks and semaphores. The major difference
is how they handle waiting for locks to be released. Spinlocks sit in a loop, continually
checking the value of the lock to see if another process has taken it. Once another process
releases the lock, it can continue. This is simple, but wastes CPU time - if processes only
hold locks for a very short time, spinlocks are okay. Semaphores, on the other hand, put a
process to sleep if it tries to take a lock held by another process, and wake up the waiting
process when the lock gets released.

You may also want to read Rusty's Unreliable Guide to Locking. It's fairly old, but the basic
concepts are valid.
http://www.kernel.org/pub/linux/kernel/people/rusty/kerne...

Quick and dirty guide to locking primitives

Posted Oct 13, 2004 9:24 UTC (Wed) by Quazatron (guest, #4368) [Link]

That was very helpful, thank you!

The Parable of the Dining Programmers

Posted Oct 13, 2004 4:50 UTC (Wed) by maney (subscriber, #12630) [Link]

Five programmers sit around a circular table. Each programmer spends his life alternatively hacking and eating. In the center of the table is an assortment of sushi and accompanying dishes. By the rules of the house style guide, a programmer needs two chopsticks to eat a piece of sushi. Unfortunately, as programming is not so well paid as managing, the programmers can only afford five chopsticks. One chopstick is placed between each pair of programmers, and they must each use only the sticks to his immediate right and left.

For the rest of the details in slightly altered form, google(dining philosophers).