Probability

• Quicksort worst case probability (\(n = 5\))?
• Choose first or last element in group of 5.
• Then: choose first or last in group of 4.
• Then: choose first or last in group of 3.
• etc.

Thread object

• java.util.Thread object (JVM Thread)
• When the JVM thread is created, the JVM allocates stack memory, creates the program counter, and asks the OS to create an OS thread.

Context switching

• Too many threads running: time-slicing.
• OS schedules each thread to run for short “slices” of CPU clock
• Then pause a thread and then run another thraed.
• Threads are paused / unpaused somewhat randomly.
• Context-switching: when the OS switches from one thread to another.
  • The context is the state of the thread (Prog Counter / stack memory).

Race Condition

• Why does this program not work?
• There is a race condition
  • When the behavior of a program depends on which instructions go first.
• What’s the race condition?

Incrementing

++counter;

Not just one instruction! Actually:

temp = counter;
temp2 = temp + 1;
counter = temp2;

Video

Creating Threads

Earlier: created Threads directly. Don’t ever do that. Creating a thread involves:

• allocating memory for the thread’s stack frame (for method invocations in that thread)
• allocating a program counter (points to the instruction that the processor is executing)
• an actual OS thread is created (corresponding to the Java “Thread” object)
• All threads share heap memory

Thread tradeoffs

Some tradeoffs should be thought about:

• If we do everything in one thread (or very few threads), we might not be able to take advantage of parallelization.
• If we create too many threads?
• So what should we do?

Thread Pools / Executors

Thread pools: re-use threads that were already created.

• Create a (possibly fixed) set of “worker threads”.
• When “tasks” come in, pick off the next available thread and use it.
• If no threads are available, add to a “task queue”
• When a thread finishes working, it goes back into the pool
  • Threads in the “pool” that are not doing anything: sleeping.

Executor framework

There is a framework for this in Java: Executor and ExecutorService objects:

ExecutorService pool = Executors.newFixedThreadPool(5);
pool.execute(someRunnableObject);

This is very flexible – many possible “execution” policies. See Java Concurrency in Practice.

Aside: Simple HTTP Server

• Let’s look at a simple HTTP server.
• Waits for a connection, responds with some HTML then pauses.
  • (Simulates “working” for a bit.)
  • What happens if another connection comes in at the same time?
  • Can we add in concurrency to handle the problem?

Problem

• Philosophers can eat and think
• Think until right fork is available, then pick it up.
• Think until left fork is available, then pick it up.
• Then eat until full, and put both down.
• Repeat.
• Problem?

Deadlock

A deadlock is when several processes / threads are all waiting for each other to finish working before they can do their work.

State

In general, what is most worrisome is state.

• A class which only uses immutable objects, or does not have any state variables, is thread-safe. (Example: “stateless servers”)
• You might opt to only allow one thread to access a state variable (don’t share it across threads).
• You might need to use synchronization whenever accessing a state variable.

Synchronization Primitives

• OS: synchronization primitives: semaphores, mutexes, etc.
• Not all available in high-level languages.
• Prior to Java 5: synchronized keyword.

Synchronized

public synchronized void add(T item) {
  ...
}
public synchronized T get(int i) {
  ...
}

• Thread 1: calls “add”
• Thread 2: calls “get”
• What happens?

Vectors

A Vector is like an ArrayList, with all of its methods synchronized. Is the following code thread-safe?

// ensures that there is exactly one "item" object in the vector v
public void addIfNotFound(Vector<T> v, T item) {
    if (!v.contains(item)) {
        v.add(item);
    }
}

Adding to LinkedList

See ListRaceCondition. What happens when we run the code? Play around with the type of “Executor” we use (single vs multithreaded).

LinkedList Code

add calls the following:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

• This is extremely non-thread safe.
• Not meant to be!
• Draw out race condition.

Next Week

• Reminder: no meeting on Thursday.
• Next week:
• Synchronized Collections
• CopyOnWriteArrayList
• Producer-Consumer pattern
• HashMap race condition
• ConcurrentHashMap

Reminders

• Project 3 due tonight!
• Still left (after project 3)
  • HW 4 (due 4/25)
  • Presentation 3 (next Monday)
  • Final Project: presentation + paper (meet with your groups and pick a topic by the end of the week).
  • Rubrics will be up soon.