05 Introduction to Threads and Synchronization (Part III)

Lecture from: 04.03.2024 | Video: Video ETHZ

A Brief History of Computer Graphics: Fluid Simulation

The “Genesis Effect” sequence in Star Trek II: The Wrath of Khan was an early example of CGI.

Over time, advances in computing power and algorithms have enabled the simulation of increasingly complex fluid dynamics. Researchers can simulate physics for tens or hundreds of millions of particles.

A typical particle-based fluid simulation involves these steps:

1. Compute Particle Neighborhoods: Determine which particles are near each other.
2. Update Per-Particle Densities and Pressures: Calculate density and pressure based on the neighborhood.
3. Compute Forces: Calculate forces acting on each particle (e.g., pressure gradient force, viscosity).
4. Update Velocities and Positions: Integrate forces to update particle velocities and positions.

Each of these steps are well suited for parallel execution because the calculation for each particle is mostly independent from all the others.

Other simulation approaches exist, such as grid-based methods (e.g., Eulerian simulations).

More recently, machine learning (ML) techniques have been applied to fluid simulation. Researchers in profs groups have developed methods for real-time simulation with over 2 million particles.

Another area of research is stylization. The goal is to take a source fluid simulation and stylize it using different particle types to create custom animations.

The stylized simulation should maintain the overall temporal evolution and artistic style of the original. These techniques are of great interest to animation studios like Disney and Pixar.

Another active research area is reconstructing 3D models from video. For example, NeuralVolumes (Lombardi, 2019) reconstructs a 3D representation of a scene from video captured from a single viewpoint.

Threads

Let us continue with threads…

Thread Safety, Liveness, and Performance Hazards

Thread Safety: Ensuring that “nothing bad ever happens” in any possible interleaving of threads. This is often difficult to achieve.

Liveness: Ensuring that “eventually something good happens.” Threads can introduce liveness hazards (e.g., deadlock).

Performance: Multithreading can introduce performance bottlenecks (context switching, loss of locality, synchronization overhead).

Correctness of Parallel Programs

Until now, we just saw bad interleaving, but there other problems that can happen too. Program correctness depends on certain program properties being fulfilled. Examples of such safety properties:

• Absence of data races
• Mutual exclusion
• Linearizability
• Atomicity
• Schedule-deterministic behavior
• Absence of deadlock
• Custom invariants

To ensure correctness, we need to synchronize the interaction of parallel threads.

synchronized

Threads may share data (objects, global variables). The programmer is responsible for avoiding bad interleavings through explicit synchronization. Java provides synchronization primitives.

Intrinsic Locks: Every Java object has an internal lock (also called a monitor lock).

synchronized Operations: Lock the object; while locked, no other thread can successfully acquire the same lock.

General Guideline: Access shared memory under a lock.

Synchronized Methods

• synchronized method: Locks on the this object.
• synchronized static method: Locks on the class object.

A synchronized method acquires the lock, executes, and then releases the lock. This is useful for methods that are entirely critical sections. A synchronized method guarantees mutual exclusion.

Counter example using a synchronized method:

Generally, as a thumb rule, synchronize the getter and setters of any shared variables.

Synchronized Blocks

synchronized (object) { ... } uses the given object as a lock. A synchronized method is syntactic sugar for a synchronized block on this.

Synchronized blocks enforce mutual exclusion with respect to a specific object. Every Java object can act as a lock.

Locks

Java has internal locks (intrinsic locks) and external locks (in java.util.concurrent.locks). External locks are less easy to use but provide more sophisticated locking mechanisms.

Locks Are Recursive (Reentrant)

A thread can acquire a lock that it already holds.

Examples: Synchronization Granularity

This example shows the trade-off between synchronizing an entire method (simpler but potentially less efficient) and synchronizing only the critical parts (more complex but potentially more efficient).

Examples: Synchronization with Different Locks

Using different locks for different data allows for greater concurrency.

Examples: Synchronization with Static Methods

A synchronized static method locks on the class object, not on any particular instance.

Interleavings: Examples

Shows two possible interleavings when synchronized is used:

Shows a bad interleaving when not using synchronized:

Synchronized on different objects does not prevent interleaving:

Synchronized and Exceptions

If an exception is thrown within a synchronized block, the lock is released before the exception propagates. However, any side effects that occurred before the exception are not reverted.

Implementation of synchronized in Java

Java’s synchronized is implemented using native OS primitives and low-level CPU instructions (e.g., compare-and-swap on x86, LL/SC on IBM Power). The exact implementation varies by OS and architecture. Future lectures will cover the specific low-level instructions behind synchronized.

Brief History: Objects, Monitors & Memory Models

• Objects & Monitors:

  • Simula 67 (1960s) introduced objects.
  • 1970s: Monitors (synchronization concept) emerged, later adopted by Java in 1995.
  • OOP Growth: Smalltalk → Eiffel → C++ → Java → many more.

• Memory Models:

  • Java 1995: First mainstream memory model but too vague.
  • Java 2004: Improved model with clearer guarantees.
  • C/C++11 (2011): Introduced a more complex but powerful memory model.
  • Ongoing: C/C++ models under revision for better performance and correctness.

wait, notify, notifyAll

The producer-consumer pattern involves a producer thread putting items into a shared buffer and a consumer thread taking items out. For simplicity, we’ll assume an unbounded buffer (no capacity limit). Consumption is only possible if the buffer is not empty.

Example

Producer-Consumer: v1 (initial, flawed version):

Problems with v1:

1. The buffer could be emptied between isEmpty() and remove().
2. Buffer operations (add(), remove()) might be interleaved at the bytecode level, corrupting the buffer’s internal state.

Producer-Consumer: v2 (adds synchronization, introduces deadlock):

Adding synchronized(buffer) blocks addresses the previous problems but introduces a new one: deadlock.

Deadlock scenario:

Continued next time…

Continue here: 06 Parallel Architectures - Parallelism on the Hardware Level