Concurrency

Overview

Concurrent Programming: The activity of constructing a program containing multiple processes/threads that execute in parallel.

For example: Consider these 2 pseudo-programs:

   P: counter = 0;
   Q: counter = 1; counter = counter + 1;

The result of P and Q being executed is different depending on whether they are execute sequentially or in parallel.

(Web) Services: while serving a request, new requests can be processed. It is worth doing in order to minimise server latency and improve availability
Real Parallelism: when multiple CPUs are available, it is worthwhile to structure applications such that parallelism can be exploited
I/O handling: even on small modern machines, external devices operate independently from the CPU. Hence, it is a good idea to make I/O a concurrent activity.
Simulation: many real situations can be naturally modelled as a number of independent interacting objects
Component-Based Software: concurrency helps when components must be connected together
Embedded Systems: real-time applications could not exist without concurrency

improve :
- efficiency in program execution using multi-CPU hardware
- CPU utilisation via multi-tasking on a uni-CPU system
some applications are inherently non-deterministic and concurrent
- e.g. embedded traffic lights controller
  - order of program operations is determined by external events
    - e.g. a sensor is triggered by an oncoming vehicle
  - Impossible to predict order of these events
    - e.g. a car comes from the north first, and then one from the east, etc

concurrent programs must interact with each other to share resources or exchange data

synchronisation
- when, how, and with what language abstractions can we synchronise computation events to eliminate unacceptable interleavings, and thus unacceptable outputs
Distribution
- how can we distribute processes among a number of processors and how a process on one processor can interact with another process on a different processor.

Concurrent programs:

are hard to design
- shared resources must be considered
- deadlocks
are hard to test
- too many scenarios (concurrent events may occur in any order)
are hard to debug
- errors are subtle: they might depend on the interaction of threads
require non-trivial reasoning techniques
yield non-deterministic results that show up when
- threads share memory or
- the result may depend on "the order" of execution

Concurrent programs contain 2 or more threads or processes
the program and it's multiple threads/processes are contained within a a single parent process
- the parent process is scheduled as normal. (see Process for details)
- the program's [concurrency|concurrent]] elements each have their own process counter.
  - when the parent process is in the running state, a child is randomly selected to run for a fixed time period
  - if the child has not finished executing when it runs out of time, it is stopped and a thread is randomly selected from the pool of child processes/threads
    - the same child could be randomly chosen more than once in succession
because of the nature of this scheduling
- the execution of children within a concurrent program interleaves.
- the order that instructions are executed in within a concurrent program is non-deterministic: it is not fixed
  - each time the program runs, the order of executed instructions may be slightly different

Processes/Threads behave in 3 ways:
1. fully independent from each other (rare)
2. competing for resources (the usual case)
3. cooperating (processes/threads working together, e.g. the OS)
competing processes engage in inter-thread synchronisation to share resources
- resources can be
  - physical or logical
  - reusable (not destroyed though use. E.g. CPU or memory) or consumable (transient data or signal, destroyed when received)