18.1. Concurrency

Book

Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, Doug Lea. Java Concurrency in Practice, 2006, Addison-Wesley Professional, ISBN 0321349601.

Read it at O'Reilly

Concurrency

We often need to run several programs at the same time, e.g.,

• streaming a video on Chrome,
• coding on IntelliJ,
• video conferencing on Teams,
• synching your files on the cloud with Dropbox,
• reading a pdf on Acrobat.

Have you ever wondered how that works?

How do you make pasta?

Sequentially?

Concurrently?

Scheduling: Sequential vs Concurrent

Sequential scheduling:

• Dependent computations are those that must be executed in a specific order to produce correct results.
• Up to now, all the programs we developed in this course worked in a sequential way.

Concurrent scheduling:

• Independent computations are those that can be executed in an arbitrary order with the same outcome.
• A computation can advance without waiting for all other computations to complete.
• A computation can be constrained based on interactions between computations.
• Minimizing dependencies while preserving correctness is a central problem.
• Concurrent programming means factoring a program into independent modules or units of concurrency.
• Units of concurrency:
  • tasks,
  • processes,
  • threads,
  • actors...

Definitions from https://slikts.github.io/concurrency-glossary.

Execution: Serial vs Parallel

Serial execution:

• is executing computations one-at-a-time.
• Concurrent processes can be executed on one core
  • by pseudo parallelism, that is,
  • by interleaving the execution steps of each process via time-sharing slices.
  • Only one process runs at a time, and if it does not complete during its time slice, it is paused, another process begins or resumes, and then later the original process is resumed.
  • Only one process is executed at any instant.

Parallel execution

• is executing multiple computations at the same instant.
• Concurrent processes can be executed in multiple cores.
  • This enables true parallelism,
  • on separate processors of a multi-processor machine, with the goal of speeding up computations.

Definitions from https://slikts.github.io/concurrency-glossary

Concurrency

Pseudo parallelism: concurrent scheduling and serial execution.

True parallelism: concurrent scheduling and parallel execution.

Concurrency

• Task scheduling: concurrent vs sequential
• Task execution: parallel vs serial
• Example: cooking pasta, 2 tasks scheduled concurrently, i.e.,
  • boiling pasta,
  • preparing sauce.
• Consider two tasks T1 and T2.
  • If T1 must be executed before T2, they are sequential and serial.
  • If T1 can be executed before T2 or vice versa, they are concurrent and serial.
  • If T1 and T2 are executed simultaneously, they are concurrent and parallel.

Concurrency level

Concurrency can take place on many levels, e.g.,

• at a low-level, on a hardware,
• at the level of operating system, i.e.,
  • process,
  • thread,
• or on worldwide networks.

Shared resources

The main challenge in concurrent programming is concurrency control, i.e.,

• ensuring correct communication between concurrent executions and
• coordinating access to resources shared among concurrent executions.

Here is an example of a bug caused by an improper handling of a shared resource.

• We have two threads.
• Each thread executes one line, pauses, and the other thread resumes.

boolean withdraw(int withdrawal) {
  if (balance >= withdrawal) {
    balance -= withdrawal;
    return true;
  } 

  return false;
}

Thread 1:

balance = 500
step 1: withdraw(300)
step 3: true (line 2)
step 5: balance = 200 (line 3)

Thread 2:

balance = 500
step 2: withdraw(350)
step 4: true (line 2)
step 6: balance = -150 (line 3)

Thread 2 actually bypassed the if statement that prevent overdrafting the account. To prevent the occurrence of such an issue, we need to coordinate the execution of these threads!