Graduate Program KB

Table of Contents

Why Concurrency?

  • Allows us to do multiple things at the same time.
  • Is a decoupling strategy, allowing us to separate the what from the when.
    • This separation of concerns can drastically improve the throughput and structures of an application.

Myths and Misconceptions

  • Concurrency is hard and if not careful can cause some nasty situations.
  • Common myths and misconceptions:
    • Concurrency always improves performance.
      • Concurrency is only beneficial when large wait times are involved that could be shared between multiple threads and processes.
    • Design does not change when writing concurrent programs.
      • Design of a concurrent algorithm can be vastly different from the design of a single-threaded algorithm.
    • Understanding concurrency issues is not important when working with a container such as a Web or EJB container.
  • Sound Bites (Facts):
    • Concurrency incurs some overhead, both in performance as well as writing additional code.
    • Correct concurrency is complex, even for simple problems.
    • Concurrency bugs aren't usually repeatable, so they are often ignored as one-offs instead of the true defects they are.
    • Concurrency often requires a fundamental change in design strategy.

Challenges

  • There are many different execution paths for threads when executing.
  • Most of them execute correctly but the issue is that some of them don't.
public class X {
    private int lastIdUsed;

    public int getNextId() {
        return ++lastIdUsed;
    }
}
  • Three possible outcomes if we have 2 threads call the method getNextId():
    • Thread one gets the value 43, thread two gets the value 44, lastIdUsed is 44.
    • Thread one gets the value 44, thread two gets the value 43, lastIdUsed is 44.
    • Thread one gets the value 43, thread two gets the value 43, lastIdUsed is 43.
      • This last result happens because the threads "step on" each other.
      • Links back to the execution paths.

Concurrency Defense Principles

Single Responsibility Principle:

  • A given method/class/component should have a single reason to change.
  • Concurrency code should be separated from the rest of the code, unfortunately it is very common that concurrency implementation details are embedded directly into the production code.
  • To consider:
    • Concurrency-related code has its own life cycle of development, change and tuning.
    • Concurrency-related code has its own challenges, which are different from and often more difficult than non-concurrency related code.
    • The number of ways in which mis-written concurrency-based code can fail makes it challenging enough without the added burden of surrounding application code.
    • Keep your concurrency-related code separate from other code where possible.

Corollary - Limit the Scope of Data:

  • As demonstrated earlier two threads modifying the same field of a shared object can interfere with each other, causing unexpected behavior.
  • We can use the synchronize keyword in Java to protect a critical section in the code that uses the shared object.
  • We want to restrict the number of critical sections.
  • The more places shared data can get updated, the more likely:
    • You'll forget to protect one or more of those places, effectively breaking all code that modifies that shared data.
    • There will be duplication of effort required to make sure everything is effectively guarded.
      • Violates DRY, Don't Repeat Yourself Principle.
    • It will be difficult to determine the source of failures, which are already hard enough to find.
  • Recommended to take data encapsulation to heart; severely limit the access of any data that may be shared.

Corollary - Use Copies of Data

  • We can avoid shared data by not sharing the data.
  • Make copies of objects and treat them as read-only.
  • In some cases it could be possible to copy objects, collect results from multiple threads in these copies and then merge the results in a single thread.
  • If using copies of objects allows the code to avoid synchronizing, the savings in avoiding the intrinsic lock will likely make up for the additional creation and garbage collection overhead.

Corollary - Threads Should be as Independent as Possible

  • Each thread should exist in its own world, sharing no data with any other thread.
  • Attempt to partition data into independent subsets that can be operated on by independent threads, possibly in different processors.

Know Your Library

  • Things to consider when writing threaded code in Java 5:
    • Use the provided thread-safe collections.
    • Use the executor framework for executing unrelated tasks.
    • Use the non-blocking solutions when possible.
    • Several library classes are not thread safe.
  • Thread Safe Collections: in java they reside in java.util.concurrent.
    • In Java 5 the ConcurrentHashMap performs better than HashMap in almost all situations.
  • Key Takeaway: Review the classes available to you.
    • In the case of Java 5, become familiar with java.util.concurrent, java.util.concurrent.atomic and java.util.concurrent.locks.

Know Your Execution Methods

  • There are different ways to partition behavior in a concurrent application.
  • Here are some common definitions before discussing them:
    • Bound Resources: Resources of a fixed size or number used in a concurrent environment. Examples include database connections and fixed size read/write buffers/
    • Mutual Exclusion: Only one thread can access shared data or a shared data resource at a time.
    • Starvation: One thread or a group of threads is prohibited from proceeding for an excessively long time or forever. For example, always letting fast-running threads through first could starve out longer running threads if there ius no end to the fast-running threads.
    • Deadlock: Two or more threads waiting for each other to finish. Each thread has a resource that the other thread requires and neither can finish until it gets the other resource.
    • Livelock: Threads in lockstep, each trying to do work but finding another "in the way". Due to resonance, threads continue trying to make progress but are unable to for an excessively long time or forever.

Producer-Consumer

  • One or more producer threads create work and place it in a buffer or queue.
  • One or more consumer threads acquire that work from the queue and complete it.
  • This queue is a bound resource.
  • Producers must wait for free space in the queue before writing and consumers must wait until there is something in the queue to consume.
  • Producers write to the queue and signal that the queue is no longer empty.
  • Consumers read from the queue and signal that the queue is no longer full.
  • Both potentially wait to be notified when they can continue.
// The producer produces integers from 0 to 9, and the consumer consumes these integers.
// The buffer size is set to 5. The producer produces items at an interval of 1 second,
// while the consumer consumes them at an interval of 2 seconds, simulating different processing times.
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ProducerConsumer {

  private static final int BUFFER_SIZE = 5;

  public static void main(String[] args) {
      BlockingQueue<Integer> buffer = new ArrayBlockingQueue<>(BUFFER_SIZE);

      Thread producerThread = new Thread(() -> {
          try {
              for (int i = 0; i < 10; i++) {
                  Thread.sleep(1000); // Simulate time to produce an item
                  buffer.put(i); // Produce item and put it in the buffer
                  System.out.println("Produced " + i);
              }
          } catch (InterruptedException e) {
              e.printStackTrace();
          }
      });

      Thread consumerThread = new Thread(() -> {
          try {
              for (int i = 0; i < 10; i++) {
                  Thread.sleep(2000); // Simulate time to consume an item
                  int item = buffer.take(); // Consume item from the buffer
                  System.out.println("Consumed " + item);
              }
          } catch (InterruptedException e) {
              e.printStackTrace();
          }
      });

      producerThread.start();
      consumerThread.start();

      try {
          producerThread.join();
          consumerThread.join();
      } catch (InterruptedException e) {
          e.printStackTrace();
      }
  }
}

Readers-Writers

  • When we have a shared resource that serves as a source of info to read and to write to, throughput can be an issue.
  • Writers tend to block many readers for a long time, causing throughput issues.
  • The challenge is to balance the needs of the readers and writers.
  • A simple strategy makes writers wait until there are no readers before allowing the writer to perform an update. If there are continuous readers however, the writers will be starve. On the other hand, if there are frequent writers and they are given priority, throughput will suffer.
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

class ReadersWriters {
  private final ReadWriteLock lock = new ReentrantReadWriteLock();
  private int resource = 0;

  public void readResource() {
      lock.readLock().lock();
      try {
          System.out.println("Reader " + Thread.currentThread().getName() + " reads: " + resource);
      } finally {
          lock.readLock().unlock();
      }
  }

  public void writeResource(int newValue) {
      lock.writeLock().lock();
      try {
          resource = newValue;
          System.out.println("Writer " + Thread.currentThread().getName() + " writes: " + newValue);
      } finally {
          lock.writeLock().unlock();
      }
  }
}

public class ReadersWritersExample {
  public static void main(String[] args) {
      ReadersWriters readersWriters = new ReadersWriters();

      // Readers
      for (int i = 0; i < 5; i++) {
          Thread readerThread = new Thread(() -> {
              while (true) {
                  readersWriters.readResource();
                  try {
                      Thread.sleep(1000); // Simulating reading time
                  } catch (InterruptedException e) {
                      e.printStackTrace();
                  }
              }
          });
          readerThread.start();
      }

      // Writers
      for (int i = 0; i < 2; i++) {
          Thread writerThread = new Thread(() -> {
              int value = 1;
              while (true) {
                  readersWriters.writeResource(value);
                  try {
                      Thread.sleep(2000); // Simulating writing time
                  } catch (InterruptedException e) {
                      e.printStackTrace();
                  }
                  value++;
              }
          });
          writerThread.start();
      }
  }
}

Dining Philosophers

  • If you imagine a bunch of philosophers around a table.
  • Each philosopher has a fork to their left and there's a bowl of pasta in the middle.
  • A philosopher can only eat when they have a fork in each hand.
  • When a philosopher finishes eating they put both forks down.
  • You can see the issue, sometimes a philosopher will be waiting for another philosopher to finish eating before they can because they need a fork.
  • Replace philosopher with threads and forks with resources.
  • Unless carefully designed systems that compete in this way can experience deadlock, livelock.
import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
  private int id;
  private Semaphore leftFork;
  private Semaphore rightFork;

  public Philosopher(int id, Semaphore leftFork, Semaphore rightFork) {
      this.id = id;
      this.leftFork = leftFork;
      this.rightFork = rightFork;
  }

  public void run() {
      try {
          while (true) {
              think();
              eat();
          }
      } catch (InterruptedException e) {
          e.printStackTrace();
      }
  }

  private void think() throws InterruptedException {
      System.out.println("Philosopher " + id + " is thinking");
      Thread.sleep((long) (Math.random() * 1000)); // Simulate thinking
  }

  private void eat() throws InterruptedException {
      leftFork.acquire();
      rightFork.acquire();

      System.out.println("Philosopher " + id + " is eating");
      Thread.sleep((long) (Math.random() * 1000)); // Simulate eating

      leftFork.release();
      rightFork.release();
  }
}

public class DiningPhilosophers {
  private static final int NUM_PHILOSOPHERS = 5;

  public static void main(String[] args) {
      Semaphore[] forks = new Semaphore[NUM_PHILOSOPHERS];
      Philosopher[] philosophers = new Philosopher[NUM_PHILOSOPHERS];

      // Initialize forks
      for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
          forks[i] = new Semaphore(1);
      }

      // Create philosophers
      for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
          Semaphore leftFork = forks[i];
          Semaphore rightFork = forks[(i + 1) % NUM_PHILOSOPHERS];
          philosophers[i] = new Philosopher(i, leftFork, rightFork);
          philosophers[i].start();
      }
  }
}

Takeaways

  • Most concurrent problems will likely be a variation of one of the above.
  • Learn these basic algorithms and understand these solutions.

Beware Dependencies Between Synchronized Methods

  • Dependencies between synchronized methods cause subtle bugs in concurrent code.
  • Avoid using more than one method on a shared object.
  • In times when you have to use more than one method on a shared object, here are three ways to make the code correct:
    • Client-based locking: Have the client lock the server before calling the first method and make sure the lock's extent includes code calling the last method.
    • Server-based locking: Within the server create a method that locks the server, calls all the methods, and then unlocks. Have the client call the new method.
    • Adapted Server: create an intermediary that performs the locking. This is an example of server-based locking, where the original server cannot be changed.

Keep Synchronized Sections Small

  • The synchronized keyword introduces a lock.
  • All sections of code guarded by the same lock are guaranteed to have only one thread executing through them at any given time.
  • Locks are expensive because they create delays and add overhead, so we want to avoid using synchronize where possible.
  • Keep synchronized code as small as possible.

Writing Correct Shut-Down Code Is Hard

  • Some programs run indefinitely and some need to be shut down after a certain period of time.
  • Graceful shutdowns can be difficult, a common problem is deadlock, with threads waiting for a signal that never comes.
  • Think about shutdown early and get it working early. It's going to take longer than you expect. Review existing algorithms because this is probably harder than you think.
  • A common example may be:
    • Parent spawns in children processes.
    • 2 of these children are a producer / consumer pair.
    • Parent signals all children to shutdown.
    • Consumer is waiting for something from producer.
    • Producer has been shut down by parent.
    • Consumer is in a blocked state waiting for producer so doesn't receive shutdown signal from parent.
    • Parent can't shut down.

Testing Threaded Code

  • Good testing doesn't guarantee correctness, but it can minimise risk.
  • Write tests that have the potential to expose problems and then run them frequently, with different programmatic configurations and system configurations and load. If tests ever fail, track down the failure. Don't ignore a failure just because the tests pass on a subsequent run.
  • Some more fine-grained recommendations:
    • Treat spurious failures as candidate threading issues.
    • Get your non-threaded code working first.
    • Make your threaded code pluggable.
    • Make your threaded code tunable.
    • Run with more threads than processors.
    • Run on different platforms.
    • Instrument your code to try and force failures.

Treat Spurious Failures as Candidate Threading Issues

  • Threaded code can cause things to fail that "simply can't fail".
  • Assume that "one-offs" don't exist.
  • Do not ignore system failures.

Get Your Non-Threaded Code Working First

  • Make sure your code outside of threads works.
  • This generally means (in Java) creating Plain Old Java Objects (POJOs) that are called by your threads.
    • The POJOs are not thread aware, and can thus be tested outside of the threaded environment.
    • The more of the system that you can place in such POJOs, the better.
  • Don't try to chase down non-threading bugs and threading bugs at the same time.
  • Make sure your code works outside of threads first.

Make your Threaded Code Pluggable

  • Write the concurrency supporting code such that it can be run in several configurations:
    • One thread, several threads, varied executes.
    • Threaded code interacts with something that can be both real or a test double.
    • Execute with test doubles that run quickly, slowly, variable.
    • Configure tests so they can run for a number of iterations.
  • Make your thread-based code especially pluggable so that you can run it in various configurations.

Make Your Threaded Code Tunable

  • Getting the right balance of threads requires trial and error.
  • Find ways to time the performance of your system under different configurations.
  • Allow the number of threads to be easily tuned.
  • Consider allowing self-tuning based on throughput and system utilization.

Run with More Threads Than Processors

  • Things happen when the system switches between tasks.
  • To encourage task swapping, run with more threads than processors or cores.
  • The more frequently you task swap, the more likely you'll encounter code that is missing a critical section or causes a deadlock.

Runs on Different Platforms

  • Different operating systems have different threading policies.
  • You should run your threaded code on all target platforms early and often.

Instrument Your Code to Try and Force Failures

  • Concurrent bugs can be hard to find due to the fact that very few pathways out of the many thousand of possible pathways through a vulnerable section actually fail.
  • We can try and force these errors by adding calls to methods like Object.wait(), Object.sleep(), Object.yield(), and Object.priority().
    • Each of these methods can affect the order of execution, thereby increasing the odds of detecting a flaw.
  • There are 2 options ofr code instrumentation:
    • Hand-coded.
    • Automated.

Hand-Coded

  • Insert calls like wait(), sleep(), yield(), and priority().
public synchronized String nextUrlOrNull() {
    if(hasNext()) {
        String url = urlGenerator.next();
        Thread.yield(); //inserted for testing
        updateHasNext();
        return url;
    }
    return null;
}
  • The yield call will change the execution pathway taken by the code and possibly cause the code to fail where it did not fail before.
  • Problems with this approach:
    • You have to manually find appropriate places to do this.
    • How do you know where to put the call and what kind of call to use?
    • Leaving such code ina production environment unnecessarily slows the code down.
    • It's a shotgun approach. You may or may not find flaws, odds are not in your favour.
  • Dividing system up into POJOs makes this easier.

Automated

  • Could use tools like Aspect-Orientated Framework, CGLIB, or ASM to programmatically instrument code.
public class ThreadJigglePoint {
    public static void jiggle() {

    }
}
  • We can then add calls to this in various places.
  • You could have different implementations of jiggle, one for production and one that randomly selects methods in development phase to try and weed out errors.
  • Use jiggle strategies to ferret out errors.

Return