Introduction to Concurrency

Definitions

The Concrete

Program
The source code for a process or processes.
Process
A unit of program execution as seen by an operating system. Processes tend to act like they are the only thing running. A process has its own address space, file handles, security attributes, threads, etc. The operating system prevents processes from messing with each other.
Thread
A sequential flow of control within a process. A process can contain one or more threads. Threads have their own program counter and register values, but they share the memory space and other resources of the process.
Multiprogramming/Multiprocessing
Concurrent execution of several programs on one computer.
Multithreading
Execution of a program with multiple threads.

The Abstract

Concurrency
The state of several instruction sequences executing at the same time (in real or abstract parallelism). These "threads of control" can communicate via shared memory or message passing.
Distribution
Concurrency in which all communication is via message passing (useful because shared memory communication doesn't scale to thousands of processors).

The Pragmatic

Concurrent Programming
Solving a single problem by breaking it down into concurrently executing processes or threads.
Shared Resource
An entity used by more than one thread but one that (usually) can only be operated on by one thread at a time.
Synchronization
The act of threads agreeing to coordinate their behavior in order to solve a problem correctly. (This usually means that thread A will block and wait until thread B performs some operation.)

Why Study Concurrency?

Examples of Concurrency

Is this stuff hard?

Well, yeah. Concurrent programming is harder than sequential programming because concurrent programming is about writing a bunch of communicating sequential programs. You end up with a bunch of problems that don't exist in sequential programs:

Concerns

The field of concurrent programming is concerned with

Modeling

We need a formal way to talk about concurrent programming so that we can analyze requirements and design and implement correct and efficient algorithms. One of the most useful models used in reasoning about concurrent programs is the non-realtime interleaved execution model. This is:

The study of interleaved execution sequences of atomic instructions, where each of the instructions execute in a completely arbitrary but finite amount of time.

In this model we can make no assumptions at all about the relative speeds of the individual instructions, or how malicious or anal a scheduler might be. Since instructions take arbitrary time, there can be a lot of possible interleavings.

Example: Suppose thread-1 has instruction sequence [A B C] and thread-2 has sequence [x y]. Then we have to consider:

   [A B C x y]
   [A B x C y]
   [A B x y C]
   [A x B C y]
   [A x B y C]
   [A x y B C]
   [x A B C y]
   [x A B y C]
   [x A y B C]
   [x y A B C]
Exercise: Write out all interleavings of two threads, the first with sequence [A B C] and the second with [x y z].

The number of interleavings for two threads, one with m instructions and one with n instructions is (m+n)n — which you probably know is (n+m)!/n!m!.

Exercise: How many interleavings are possible with n threads where thread i has ki instructions?

Granularity

Systems can be classified as to the level of concurrency that can be expressed or implemented.

Instruction Level

Most processors have several execution units and can execute several instructions at the same time. Good compilers can reorder instructions to maximize instruction throughput. Often the processor itself can do this.

Example: On the old Pentium microprocessor, the instruction sequence 
    inc ebx
    inc ecx
    inc edx
    mov esi,[x]
    mov eax,[ebx]

would be executed as follows:

    Step       U-pipe            V-pipe
    -----------------------------------------
      0        inc ebx           inc ecx
      1        inc edx           mov esi, [x]
      2        mov eax, [ebx]

Modern processors even parallelize execution of micro-steps of instructions within the same pipe.

Statement Level

Many programming languages have syntactic forms to express that statements should execute in sequence or in parallel. Common notations:

Pascal-style Occam-style Algebraic 
    begin
       A;
       cobegin
          B;
          C;
       coend
       D;
       cobegin
          E;
          F;
          G;
       coend
    end

    SEQ
       a
       PAR
          b
          c
       d
       PAR
          e
          f
          g


    a ; b || c ; d ; e || f || g

Procedure Level

Like threads in Java or Perl, tasks in Java, native Win32 threads, or most threading libraries like pthreads. Threads are spawned to run a function or method.

Program Level

Usually the responsibility of the operating system, which runs processes concurrently.

Most programming languages give you the ability to spawn processes from your program.

In Java

    Runtime.getRuntime().exec(commandline);

In C, using the Win32 API

    CreateProcess(security_attributes, stack_size, &function, param, activation,
        &thread_id);
Exercise: Show how to spawn a new process using the Unix system calls execve with fork.)

Scheduling

Generally you'll have M processors and N threads. If M < N you need a scheduler to interleave execution. A thread can be in one of several states; one example is:

threestatesched.png

(Note: Win32 threads have six states; we'll see them later.)

Communication

The threads of control must communicate with each other. The two main ways to communicate:

Synchronization

Threads sometimes have to coordinate their activities. Suppose two threads A and B are trying to make a $100 deposit. They both execute the sequence:

  1. move the current value of the account into a register
  2. add 100 to the register
  3. write the value of the register back into memory

If A executes its first statement and then B executes its first statement before A finishes its third statement, one of the deposits gets lost. There are dozens of programming paradigms to make sure threads can synchronize properly to avoid these problems.

Support for Concurrency

Many have argued whether a language should have direct support for concurrency and distribution or whether such support should come from a library.

Library or O.S. based Language-Intrinsic 
   .
   .
   .
   int t1, t2;
   .
   .
   .
   t1 = createThread(myFunction);
   .
   .
   .
   start(t1);
       // now t1 runs in parallel
       // with the function that
       // called start().
       // Termination is
       // asynchronous, though
       // joining can be done with
       // a library call.

   procedure P is
      .
      .
      .
      task T;
      .
      .
      .
   begin   -- T activated implicitly here
      .
      .
      .    -- T and P execute in parallel
      .
      .
   end P;  -- T and P terminate together

Advantages:

  • Because different languages have different models of concurrency, language interfacing (multi-lingual development) may be easier.
  • A specific language model may not fit well with a particular O.S.
  • O.S. standards (e.g. POSIX) exist anyway, so perhaps portability might be likely.

Advantages:

  • Code likely to be more reliable and maintainable since constructs are high level.
  • Lots of different operating systems exist, so code may be more portable.
  • An embedded computer might not even have an operating system.

Correctness

Concurrent programs have to be correct for all possible interleavings. Natrually this makes testing more complicated, but it can be done.