What In The Hell Are Race Conditions and Locks

In the context of parallel or concurrent programs, you will often hear the term race condition. This describes a problem when two pieces of code try to modify the same variable (or other location in memory).

Race conditions can be notoriously difficult to find, reproduce and debug.

To start with we have a variable a that is set to 7. I’ll show you what can happen, step-by-step, when two pieces of code try to use and modify that variable.

Both a = a + 35 and a = a – 10 will execute “at the same time”. I have “at the same time” in scare quotes because we don’t really know what “at the same time” means. Computers process instructions sequentially, this means that one operation has to come before the other. Let’s see how that can play out…

From looking at the code in the beginning, you may have guessed that the value of a after these operations would be 42, and that was indeed the intent. However, because of the race condition the value of a ended up being -3. Not at all what we wanted!

Probably the most common way to handle race conditions is to use locks. Here’s how the above process would look using locks…

Locks prevent race conditions by making sure that only one piece of code can access a memory location at any time. Locks can become very complicated to manage and are themselves the source of many bugs. Consider what would happen if some piece of code did not unlock the memory it was modifying! Or worse, did not lock it in the first place, in which case we fall back to the race condition.

Locks are not the only way to handle race conditions (though they are the most common). Another way to handle race conditions is to use immutable variables. This means that no code is allowed to change the value of a. Immutable variables will be the subject of another WITH article, so I won’t explain them here.

GOTO Table of Contents

Advertisements

What In The Hell | Basic Numeric Data Types (Char, Integer, Short, Signed)

Numbers are an abstract idea. A concept that can only be approximated in reality. To illustrate this concept a little better, take out some paper and write down the answer to 1/3.

Are you done? How could you be? Whatever you wrote down I could make a better by adding another 3 at the end, or another trillion 3’s at the end. How about the biggest number you can think of? Any number you can write down I can make better by adding one more digit.

So you can see that we have to put some limits somewhere. The limits that we put on numbers in a computer correspond to the amount of memory it takes to represent those numbers.

To understand this, we need to know a little bit about computer memory. Computers store information in bits. A bit is a binary number (1 or 0) that represents the on or off state of the memory. Since a single bit is often too little to use effectively, computer memory is organized into blocks of 8 bits called bytes.

The 8 bit byte can represent the numbers 00000000 through 11111111 in binary, which is 0 to 255. Your computer’s memory is organized into a big row of bytes.

Each address above refers to one byte. A char is one byte. However, what do we do when we need a number bigger than 255? We have to use more than one byte. A number that is 2 bytes can represent a number from 0 to 65,535 and is called a short int.

A 4 byte number (32 bit) could represent 0 to 4,294,967,295 and is called an int or integer.

An 8 byte number (64 bit) could represent 0 to 18,446,744,073,709,551,615 and is called a double.

Another way to look at the basic numeric types is as names for sizes of memory.

What happens when we want negative numbers?

Let’s go back to the char or the single byte. A char can represent 256 values and only 256 values, so to get negative numbers we need to give up some of the positive ones. In fact we’ll give up exactly half of the positive ones and represent the numbers -128 through 127.

When we want to represent negative numbers we use a signed type. Unsigned types represent only positive numbers and 0. Any of char, short int, int or double can be signed or unsigned and each follows the split in half rule.

What about the decimal point?

Numbers with a decimal point in them are called floating point numbers. An entire book can probably be written about floating point numbers as they can become quite complicated. A future WITH article will cover floating point numbers in more detail.

* The size of each char, int, etc can vary depending upon the hardware. This article used common sizes for a 32 bit architecture.
* Teaching Tip: Write down numbers on a whiteboard/paper and measure them with a ruler. Imagine each inch is a block of memory. How many different numbers can you store in one block? How about two or four? What would you name those blocks so you could talk about them with other people? Bonus: how many blocks does it take to write a character?

GOTO Table of Contents

What In The Hell Is Recursion

GOTO Table of Contents

 

Recursion is often a feared and dreaded word among new computer scientists. Most see it as a mystical process that they have no hope of understanding. Others loudly proclaim that they’ve been programming for years and have never needed recursion, mostly because they see it as a mystical process that they have no hope of understanding.

However recursion is actually pretty straightforward. And that’s a good thing, because there are a lot of problems that have very elegant recursive solutions. We’ll cover some of those when we learn about tree algorithms and sorting in future WITH articles.

For now we’re going to focus on the basics of recursion. Recursive functions are most often used as a form of loop and for this article we’ll use one of the most basic loops; counting. We’re going to describe a process of printing all the numbers from 0 to infinity. Without recursion you would probably write something similar to the following.

def count(n):
  while 1:
    print n
    n = n + 1
count(0)
0
1
2
...

Next we’ll look at the recursive solution.

def count(n):
  print n
  count(n+1)
count(0)
0
1
2
...
998
RuntimeError: maximum recursion depth exceeded

The above code should be pretty self-explanatory, but I’ll explain it a little bit anyway. The function count has only two instructions. First print n to the screen, then call count with n + 1 as the argument. So when we call count(0) it should print 0 then call count(1) which will print 1 then call count(2)…

You probably noticed the error in the above output. We’re going to ignore that for the moment and move on from trying to count to infinity. Let’s just count to 5. To tell when we’ve hit 5 we’ll need to check the value of n each time count is called.

def count(n):
  if n < 5:
    print n
    count(n+1)
count(5)
0
1
2
3
4

As you can see from these examples, a recursive function is simply a function that calls itself. Let’s look at another recursive solution to counting. This time we’re going to use a list of the numbers 0 through 4 and print each number in the list.

def print_list(lst):
  if lst:
    print lst[0]
    print_list([1:])
print_list(range(5))
0
1
2
3
4

In this code we print the first element in the list, then call print_list with the rest of that list from the 2nd element on. Here’s a diagram of the process to make it a bit more clear.

When writing recursive code it is important to include a stopping condition, which was the empty list in the code above. If you don’t include a stopping condition, your code will enter an infinite loop.

 

Tail-Call Optimization

One problem with recursive code is that most programming languages translate recursive code into something very similar to the diagram above.

Let’s go back to trying to print to infinity again and look at the error when we run the code. Depending on how many lines your terminal logs you may not see this.

993
994
995
996
997
998
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in print_infinity
  File "<stdin>", line 3, in print_infinity
  File "<stdin>", line 3, in print_infinity
  File "<stdin>", line 3, in print_infinity
  ...
  RuntimeError: maximum recursion depth exceeded

Since most languages, Python included, see recursive code exactly like the diagram above, try to imagine how big our diagram would have to be to represent a 1,000! Eventually the language simply runs out of memory to store this huge diagram or it hits a set limit to prevent that from happening.

Let’s take a look at another example, countdown. This function simply counts down from a number, n to 1.

def countdown(n):
  if n:
    print n
    countdown(n-1)
countdown(5)
5
4
3
2
1

Each time Python sees countdown(n-1) it makes a new function call. Because Python is lexically scoped, the function call creates a new frame to hold the bindings and arguments. When the next countdown(n-1) is evaluated a new frame is created inside the last frame. Then again, and again, until it looks like the code below, each new level of indentation is a new frame within the previous frame.

countdown(5)
  print 5
  countdown(4)
    print 4
    countdown(3)
      print 3
      countdown(2)
        print 2
        countdown(1)
          print 1
          countdown(0)

From looking at the code above, it doesn’t make much sense why any language would do this. However if you switch the code for countdown around a little bit, it starts to make sense.

def countdown(n):
  if n:
    countdown(n-1)
    print n

All we did was switch the countdown and print lines, but let’s see how that changes the execution of this function.

countdown(5)
1
2
3
4
5

This version of countdown doesn’t countdown at all! In fact it counts up. To see why, let’s examine the execution of this function.

countdown(5)
  countdown(4)
    countdown(3)
      countdown(2)
        countdown(1)
          countdown(0)
          print 1
        print 2
      print 3
    print 4
  print 5

And a longer, but more descriptive version…

countdown(5)
  if 5:
    countdown(5 - 1)
      if 4:
        countdown(4 - 1)
          if 3:
            countdown(3 - 1)
              if 2:
                countdown(2 - 1)
                  if 1:
                    countdown(1 - 1)
                    print 1
                print 2
            print 3
        print 4
    print 5

In this scenario there is a print instruction after the call to countdown. This means that the language must evaluate countdown before printing the number. The only way to do this is to create a tree structure as depicted above and keep it all in memory until the function has finished executing.

Some languages like Scheme perform tail-call optimization (TCO), also known as tail-call elimination. If the recursive function call is the last thing you do in the function body, there cannot be anymore instructions to perform after the call. Because it is guaranteed that none of the information from the initial frame is needed, there is no reason to keep it around by nesting new frames in it. In other words tail-call optimization transforms a recursive definition into an iterative one.

Language support for tail-call optimization varies widely. Some languages, like Scheme, guarantee that recursive function calls in the tail position will run in constant space. While on the lower end of the spectrum is a compiler like gcc that may run tail calls in constant space, even though the C standard does not support TCO.

Languages that guarantee tail-call optimization generally use recursion as the main form of looping. Because of this function calls in these languages are usually highly optimized.

Here are tail-call optimized versions of count and countdown in Scheme. Notice how the recursive calls are the last calls that are executed in the body.

(define (count n)
  (print n)
  (count (+ n 1)))

(define (countdown n)
  (if (= n 0)
    (print n)
    (begin
      (print n)
      (countdown (- n 1)))))
(countdown 3)
3
2
1
0
(count 0)
1
2
3
...

 

Mutually Recursive Functions

This is the classic example of a mutually recursive function. These two functions together will determine whether a number is even or odd. Take a minute to look at the code and try to figure out for yourself how it works.

def even(n):
  if n == 0: 
    return True
  else: 
    return odd(n-1)

def odd(n):
  if n == 0: 
    return False
  else: 
    return even(n-1)
even(4)
#===> True
odd(4)
#===> False
odd(3)
#===> True

Because everyone likes a good sports analogy let’s imagine two kids playing catch. One kid is named Even and the other is named Odd. Even starts with the ball in his hand and they throw the ball back and forth until they lose count. If Even has the ball last, they threw the ball an even number of times. If Odd has the ball last, they threw the ball an odd number of times. When they finish playing, the kid with the ball screams “I got it!” and the game ends.

The mutually recursive function above works the same way. even subtracts 1 from the number and throws it to odd. odd also subtracts 1 from the number and throws it back to even. When the number reaches 0 the last function to have the number returns, #t if even is the last to have it and #f if odd is the last to have it.

We’ve already learned that a recursive function creates a loop by calling itself. Mutually recursive functions create a loop by calling each other. Like recursive functions, mutually recursive functions must check for some condition to prevent an infinite loop.

GOTO Table of Contents