Shared State

The design of concurrent software that shares data is based on the idea that threads can access the same data, and that data can be modified by any thread.

An example of a language that uses this model is Java.

We have two challenges to solve:

  • The secure access to shared data. What mechanisms can we use to ensure threads safely access shared data?

  • The coordination between threads. How can we manage the execution order of threads, synchronize them when needed, and manage their interactions?

Secure access

If all threads have read-only access, no problem. The problem is when there is simultaneous read and write access.

There are two problematic situations: thread interference and data consistency.

Thread interference

Interference occurs when two operations, running on different threads, but acting on the same data, are intertwined. This means that the two operations consist of multiple steps and the step sequences overlap. This phenomenon is also called race condition.

For example: The increment operation of a counter consists of reading the current value, incrementing it, and writing the new value. If two increment operations are executed simultaneously, the final result may be erroneous.

The solution is to synchronize access to the shared data, making each operation run atomically.

Data consistency

The problem is that two operations, running in different threads, but acting on the same data, do not see the changes that have been made to the data. This is because threads have a local copy of the shared data, and changes made by other threads are not seen.

For example, if one thread changes the value of a boolean variable and another thread reads the value, it may not see the change. This is because the compiler can optimize the code, and not read the value of the variable every time it is used, but instead saves it in a register. This prevents the thread from seeing changes made by other threads.

Strategies

Possible strategies to manage simultaneous access to shared data are: confinement, immutability, thread-safe types and synchronization.

  • Containment. Do not share the variable between threads.
  • Immutability. Make shared data immutable. All fields in the class must be final.
  • thread-safe data type. We encapsulate shared data in an existing data type with security that performs coordination.
  • Synchronization. Use synchronization to prevent threads from accessing at the same time by setting critical sections of code: pieces of code that access shared data and must be executed atomically.

Coordination

When designing your concurrent software flow, ask yourself these questions:

  1. You need to understand the solution to the problem. Usually, it starts from the sequential solution, to find the concurrent one.
  2. Consider whether can be parallelized. Some problems are inherently sequential.
  3. Think about the parallelization opportunities that dependencies between data allow. If there are no dependencies, we can decompose them and parallelize them.
  4. Find the places where the solution consumes the most resources, as candidates for parallelization.
  5. Decompose the problem into tasks, to see if these can be executed independently.

Here are some mechanisms available in different languages to coordinate threads:

  • Create one or more tasks that will be executed in parallel.
  • Let one thread wait for another to complete (join).
  • That a thread notifies another that it has completed a task (notify).
  • That a thread waits for another to notify it that it has completed a task (wait).
  • For a thread to send an interrupt signal to another thread (interrupt).

Liveness of a multithreaded system

An application's liveness is its ability to run on time. The most common problems that can disrupt this vitality are:

  • The deadlock: two or more threads are deadlocked forever, waiting for each other. It can happen if two threads block resources they need waiting for others to be free, which never will be.
  • Starvation: the perpetual denial of the resources needed to process a job. An example would be the use of priorities, where the threads with the highest priority are always served, and the others never are.
  • Livelock is very similar to deadlock, but threads do change their state, although the deadlock is never unlocked.

When a client makes a request to a server, the server must obtain exclusive access to the necessary shared resources. Correct use of critical sections will allow the system to have better vitality when the request load is high.