Concurrency, multi-threading, parallelism. These are all big terms thrown around in the computer-science world. For an outsider it can be quite confusing what these exactly are and how they differ from each other. In this series we’ll cover and dive into concurrency and its applications.

Let’s start by defining what we mean by concurrency.

Introduction

Concurrency, in its very definition is, the fact of two or more events or circumstances happening or existing at the same time.

If we apply this to computer-science, we can see that’s a very natural thing. Executing two or more events at the same time is something we would love. The only problem is that, we can not guarantee safety.

Let’s look at an example.

Simple example

Let’s look at a Java program which increments a simple counter:

In a sequential (non-concurrent) program this would be:

1
public class Counter {
2
    private int counter = 0;
3

4
    public void run() {
5
        int cnt = counter;
6
        counter = cnt + 1;
7
    }
8

9
    public int counter() {
10
        return counter;
11
    }
12
}

1
public class SequentialCount {
2
    public static void main(String[] args) {
3
        Counter counter = new Counter();
4

5
        counter.run();
6
        counter.run();
7

8
        System.out.println(counter.counter());
9
    }
10
}

This program will always print out 2. There’s no doubt in that.

If we now introduce concurrency, we will now run these at the same time, or in parallel, do not confuse this with parallelism. They’re not the same.

So the idea is that we run the block of code we have on independent execution units (so-called threads in Java).

Specifically, in Java, these threads will run on the same counter object. So they will share the global variable called counter.

We, the programmers, don’t have any control in what order these threads will be executed, this is the schedulers job.

1
public class ConcurrentCounter extends Counter implements Runnable {
2
    /*
3

4
    threads will execute run()
5

6
    */
7
}

1
public class ConcurrentCount {
2
    public static void main(String[] args) {
3
        ConcurrentCounter counter = new ConcurrentCounter();
4

5
        Thread t = new Thread(counter);
6
        Thread u = new Thread(counter);
7

8
        t.start();
9
        u.start();
10

11
        try { t.join(); u.join(); }
12

13
        catch (InterruptedException e) {
14
            System.out.println("Interrupted!");
15
        }
16

17
        System.out.println(counter.counter());
18
    }
19
}

If we compile and run this, we necessarily won’t always get the expected answer, 2. In some (rare) cases, we will get the answer 1.

But if there is a risk for failure, why would we even want to write concurrent programs? Well, the answer can be described in three points.

• Abstraction
  • By separating tasks and making sure we don’t have to worry about them. For example downloading multiple files at once.
• Responsiveness
  • We can provide a responsive, user interface by writing concurrent programs. For example, browsing YouTube while downloading files.
• Performance
  • Splitting complex tasks, into smaller, subtasks will greatly increase the pure computer performance.

Let’s also make one thing clear. Concurrency vs Parallelism. Concurrency is “logical parallelism” and parallelism is “physical parallelism”.

Parallelism is about taking advantage of redundant hardware.

Today, concurrency is everywhere, all operating-systems are based on concurrency and making sure things are speedy.

But these speedups aren’t always free.

Amdahl’s law

Amdahl’s law gives us an equation that, given $n$ processors (these are not necessarily physical processors but can be execution units) that can run in parallel.

What’s the maximum speedup we can gain? $$ \text{max speedup} = \frac{1}{(1 - p) + \frac{p}{n}} $$

$p$ is the % of the program that is being run in parallel. By plugging in some arbitrary values we find quickly that, after a certain threshold, more parallelism doesn’t help.

Terminology

Now that we’ve looked at the basics, let’s look at some important terminology.

A process is an independent unit of execution. It’s an abstraction of a running sequential program. This is what the operating system schedules, which process to run.

The scheduler is the system unit that is in charge of the process state. There are 3 states in which a process can be in:

• Ready
  • Ready to be executed, but not allocated to any execution unit.
• Blocked
  • Waiting for an event to happen
• Running
  • Running on some execution unit

A thread is a lightweight process. The actual difference between a process and a thread is fuzzy and implementation specific.

Our definition will be:

Process: Executing units that do not share memory.
Threads: Executing units that share memory.

An important thing to remember is that, threads (or execution units that share memory) communicate via memory. While processes (or execution units that do not share memory) send real messages between the processes themselves.

These models are called, shared memory and distributed memory.

Traces

A trace is an abstraction of concrete executions, these executions being:

• Atomic/linearized
  • The effects of each thread appear as if they happened instantaneously.
• Complete
  • The trace includes all intermediate atomic states.
• Interleaved
  • The trace is an interleaving of each thread’s linear trace (in particular, no simultaneity).

What this means is, the sequence of states gives an execution trace of the concurrent program.

So different traces lead to different results in the program.

Conclusion

This concludes this first part in this series, we’ve only looked at the pure basics and terminology here. In the next part we’ll cover races, locks and semaphores, which are the first real concurrency principles we’ll look at.