Concurrency and Parallelism

Concurrency
> Click or hit Control-Enter to run Example.main above

First, we have to declare our class to accept type parameters:

// T is a type parameter that can be used throughout our class
public class SimpleLinkedList<E> {
  // get returns a reference of type E
  public E get(int index) {
  }
  // set takes a reference of type T as its second argument
  public void set(int index, E value) {
  }
}

To help understand how generics work you can imagine the compiler rewriting them when it compiles your code.

public class List<E> {
  public E get(int i) {
  }
  public void set(int i, E value) {
  }
}
List<String> list = new List<>();

public class List {
  public String get(int i) {
  }
  public void set(int i, String value) {
  }
}
List list = new List<>();

public class SimpleLinkedList<E> {
  class Item {
    E value;
    Item next;
    Item(E setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private int currentSize;

public SimpleLinkedList() { }

public SimpleLinkedList(E[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      this.add(0, array[i]);
    }
  }

public void add(int index, E toAdd) {
    if (index == 0) {
      start = new Item(toAdd, start);
      currentSize++;
      return;
    }
    Item previousItem = getItem(index - 1);
    if (previousItem == null) {
      return;
    }
    Item newItem = new Item(toAdd, previousItem.next);
    previousItem.next = newItem;
    currentSize++;
  }

public E remove(int index) {
    E toReturn;
    if (index == 0) {
      toReturn = start.value;
      start = start.next;
      return toReturn;
    }
    Item previousItem = getItem(index - 1);
    toReturn = previousItem.next.value;
    previousItem.next = previousItem.next.next;
    return toReturn;
  }

public E get(int index) {
    Item item = getItem(index);
    if (item == null) {
      return null;
    } else {
      return item.value;
    }
  }

public void set(int index, E toSet) {
    Item item = getItem(index);
    if (item != null) {
      item.value = toSet;
    }
  }

public int size() {
    return currentSize;
  }

protected Item getItem(int index) {
    if (index < 0 || index >= currentSize) {
      return null;
    }
    int currentIndex = 0;
    for (Item current = start; current != null; current = current.next) {
      if (currentIndex == index) {
        return current;
      }
      currentIndex++;
    }
    return null;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleLinkedList<Integer> simpleList = new SimpleLinkedList();
    for (int i = 0; i < 10; i++) {
      simpleList.add(0, i);
    }
    System.out.println(simpleList.size());
    for (int i = 0; i < 5; i++) {
      simpleList.remove(i);
    }
    System.out.println(simpleList.get(0));
  }
}

> Click or hit Control-Enter to run Example.main above

Because it’s about to get more interesting…

> Click or hit Control-Enter to run Example.main above

The compiler knows all about the relationship between different types, and so it can help us ensure that our generic classes receive appropriate type parameters.

<T extends S>: type T extends class S or implements interface S
<T extends S & U & V>: type T extends or implements S, U, and V

> Click or hit Control-Enter to run Example.main above

Just like classes, interface definitions can use type parameters:

public interface SimpleList<E> {
  public E get(int index);
  public void set(int index, E element);
  public void add(int index, E element);
  public E remove(int index);
  public int size();
}

I’ve elided many of the details of working with generics. Review the official documentation to learn more.

But here’s one of the more obvious things that doesn’t work the way you’d want:

public class LastTen<T> {
  private T[] values;
  private List<T> listOfValues;
  LastTen() {
    value = new T[10]; // You can't create an array of a generic type
    // As a solution you can use a collection type like a list
    listOfValues = new ArrayList<T>(); // This works
  }
}

All processors create the illusion of parallelism by rapidly switching between multiple programs.

Why does this work? Because you are slow.

Assuming a 1 GHz processor:

15 ms "rule of thumb": 15,000,000 clock cycles!
40 ms based on 25 frames-per-second for "smooth" video: 40,000,000 clock cycles!
100 ms was the rule for old telephone systems, the delay point after which human conversation patterns start to break down: 100,000,000 clock cycles!

Today even your phone has multiple cores. So we have both:

Real parallelism: your phone is actually doing multiple things at once
Illusory parallelism: each core is still rapidly switching between programs to create the illusion of more parallelism.

public class Example {
  private static void process() {
    for (int i = 0; i < 20000000L; i++);
  }
  public static void main(final String[] unused) {
    long startTime = System.nanoTime();
    for (int i = 0; i < 4; i++) {
      process();
    }
    System.out.println((System.nanoTime() - startTime) / 1000000.);
  }
}

So far all of the code we’ve written this semester only does one thing at a time.

Sometimes we call this single-threaded, for reasons that will make sense shortly.

> Click or hit Control-Enter to run Example.main above

Java allows us to create a separate thread of execution using the Thread class.

Each Thread executes separately, and threads may run in parallel on different cores if possible.
Each Thread can access the same program variables as other threads.

public class Example implements Runnable {
  public void run() {
    System.out.println("Hello!");
  }
  public static void main(final String[] unused) {
    Thread t = new Thread(new Example());
    t.start();
  }
}

When we create a Thread we need to give it something to do—a function as an entry point. (Remember main?)

We do this by having our class implement Runnable and provide a public void run() method.

> Click or hit Control-Enter to run Example.main above

> Click or hit Control-Enter to run Example.main above

Java has multiple methods for controlling and communicating with Thread objects:

thread.start(): begin executing a Thread
thread.join(): wait for a Thread to complete
thread.interrupt(): interrupt a Thread, causing an InterruptedException to be thrown

> Click or hit Control-Enter to run Example.main above

> Click or hit Control-Enter to run Example.main above

> Click or hit Control-Enter to run Example.main above

You hear the terms parallelism and concurrency used together a lot, but each has a specific meaning:

Parallelism: multiple things are happening at the same time
Concurrency: multiple parts of your program can make progress at the same time
Watch this talk by Googler Rob Pike if you want to clear up this distinction

Parallelism is important if your program spends a lot of time computing—but most programs don’t.

They spend a lot of time waiting for other things to happen:

Waiting for the user to enter some input
Waiting for a read from the disk to complete
Waiting for some data from the network
Waiting for your web API call to complete

If your program is concurrent, something useful can happen even while you’re waiting for something else.

On Android there is a single user interface (UI) thread responsible for handling input like clicks.

If that thread get stuck waiting, the entire UI becomes unresponsive.
Which is why you need to do slow things using a background task—or, in the case of Volley, using its queue.
This way the UI thread stays responsive even while slow operations like network requests are being completed.

> Click or hit Control-Enter to run Example.main above

> Click or hit Control-Enter to run Example.main above

> Click or hit Control-Enter to run Example.main above

A race condition or race hazard is the behavior of an electronics, software, or other system where the output is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when events do not happen in the order the programmer intended.

Thread 1 Thread 2

Thread 1	Thread 2
`currentAccountBalance = 1000`
	`currentAccountBalance = 1000`
	`currentAccountBalance -= 10`
	`accountBalance = 990`
`currentAccountBalance -= 10`
`accountBalance = 990`

currentAccountBalance = 1000

currentAccountBalance -= 10

accountBalance = 990

currentAccountBalance -= 10

accountBalance = 990

One programming technique to avoid race conditions is to use a lock:

Once one Thread grabs a lock no other threads can use the lock.
We then do our operation on the shared variable or resource.
And then drop the lock so that other threads can acquire it.

`// grab lock`
	`// grab lock`
`currentAccountBalance = 1000`
`currentAccountBalance -= 10`
`accountBalance = 990`
`// release lock`
	`currentAccountBalance = 990`
	`currentAccountBalance -= 10`
	`accountBalance = 980`
	`// release lock`

// grab lock

currentAccountBalance = 1000

currentAccountBalance -= 10

accountBalance = 990

// release lock

currentAccountBalance = 990

currentAccountBalance -= 10

accountBalance = 980

// release lock

// Only one `Thread` can run this method at once on each object
public synchronized void withdraw() {
    int currentAccountBalance = accountBalance;
    System.out.println(currentAccountBalance);
    currentAccountBalance -= 10;
    if (currentAccountBalance < 0) {
      // throw Exception
    }
    accountBalance = currentAccountBalance;
  }

Java has a special keyword called synchronized that allows us to easily add a lock to any existing method.

// Only one `Thread` can run this method at once on the entire class
public static synchronized void withdraw() {
    int currentAccountBalance = accountBalance;
    System.out.println(currentAccountBalance);
    currentAccountBalance -= 10;
    if (currentAccountBalance < 0) {
      // throw Exception
    }
    accountBalance = currentAccountBalance;
  }

> Click or hit Control-Enter to run Example.main above

Concurrency encourages a Thread free for all, while locking makes them get in line.

> Click or hit Control-Enter to run Example.main above

Our final project fair will be Thursday 12/13/2018 from 5–9PM.

Participation is optional but worth 1% extra credit.
We’ll start with project demos and judging in Siebel from 5–8PM. You’ll receive an email assigning your group to a room or space.
We’ll be selecting some of the best projects to feature at the fair in lab this week.
Then we’ll move to Foellinger for a final awards presentation and announcements.

The third and final midterm starts tomorrow. Good luck!
I have office hours MWF from 10AM–12PM in Siebel 2227. Please stop by!
Remember to provide feedback on the course using the anonymous feedback form.
I’ve started to respond to existing feedback on the forum.

Review: Class Type Parameters

Compiling Generic Classes

Original and Rewritten List

Questions So Far?

Bounded Type Parameters

Generic Interfaces

Generic Gotchas

Questions About Generics?

Originally: Single-Core Processors

But Then How Could You Use Multiple Applications At Once?

The Illusion

But Look Closer…

And Even Closer…

The Illusion of Parallelism

Human Perceptual Limitations

Today: Multicore Everywhere

Today’s Reality: Both Real and Illusory Parallelism

Single-Threaded

But We Have Multiple Cores!

Parallelism In Java

But What Is a `Thread` To Do?

`Runnable`s

Controlling Threads

Concurrency v. Parallelism

Why Concurrency Is Important

Android Aside

But Concurrency Can Create Problems…

Race Condition

Account Example: No Locking

Locks

Account Example: Locking

Java `synchronized` Keyword

Java `synchronized` Keyword

However, Locking Degrades Concurrency

Questions About Concurrency or Parallelism?

Fair Announcements

Announcements

Review: Class Type Parameters

Compiling Generic Classes

Original and Rewritten List

Questions So Far?

Bounded Type Parameters

Generic Interfaces

Generic Gotchas

Questions About Generics?

Originally: Single-Core Processors

But Then How Could You Use Multiple Applications At Once?

The Illusion

But Look Closer…​

And Even Closer…​

The Illusion of Parallelism

Human Perceptual Limitations

Today: Multicore Everywhere

Today’s Reality: Both Real and Illusory Parallelism

Single-Threaded

But We Have Multiple Cores!

Parallelism In Java

But What Is a Thread To Do?

Runnables

Controlling Threads

Concurrency v. Parallelism

Why Concurrency Is Important

Android Aside

But Concurrency Can Create Problems…​

Race Condition

Account Example: No Locking

Locks

Account Example: Locking

Java synchronized Keyword

Java synchronized Keyword

However, Locking Degrades Concurrency

Questions About Concurrency or Parallelism?

Fair Announcements

Announcements

But Look Closer…

And Even Closer…

But What Is a `Thread` To Do?

`Runnable`s

But Concurrency Can Create Problems…

Java `synchronized` Keyword

Java `synchronized` Keyword