Federico Mengozzi

Parallel, Concurrent, and Distributed Programming in Java Specialization

Concurrent Programming

Rice University

Week 1

Threads

Threads are unit of execution that are scheduled by the operating system. A thread must first be created while specifying the computation that it has to perform and than the its execution can start. When multiple threads are executing it may be the case that thread $t2$ can start execute only after thread $t1$ has complete its computation. In this scenario it’s possible to tell the main thread to wait for $t1$ to finish before starting $t2$ using the join construct.

class TestThread {
    public static void main(String[] args) {

        Thread t1 = new Thread(() -> {
            try {
                System.out.println("Thread t1 start execution");   
                Thread.sleep(100);
                System.out.println("Thread t1 complete execution");   
            } catch (InterruptedException e) {}
        });
        Thread t2 = new Thread(() -> System.out.println("Thread t2 start execution"));
        
        t1.start();
        t2.start();
    }
}

The code above would produce the following output

Thread t1 created
Thread t2 created
Thread t1 complete execution

Using join() would make $t2$ wait for $t1$.

class TestThread {
    public static void main(String[] args) {
        //... 
        t1.start();
        t1.join();
        t2.start();
    }
}
Thread t1 created
Thread t1 complete execution
Thread t2 created

Locks

Locks are construct that allow to avoid data race (multiple threads read/modify/access the same memory location leading to undefined results) by restricting certain operations to one thread at the time.

class Counter {
    private long counter = 0;
    
    void inc() {
        this.counter = this.counter + 1;
    }
    void dec() {
        this.counter = this.counter - 1;
    }
    long get() {
        return this.counter;
    }
}
public class DataRace {
    public static void main(String[] args) {
        
        final Counter c = new Counter(); 
        Thread t1 = new Thread(() -> {
            for(int i=0; i<100; ++i) 
                c.inc();
        });
        Thread t2 = new Thread(() -> {
            for(int i=0; i<100; ++i) 
                c.dec();
        });
        
        t1.start();
        t2.start();
        
        // print only after both threads terminate
        t1.join();
        t2.join();
        
        System.out.println(c.get()); 
    }
}

Every time I run the code I get different results because of concurrent access to the same variable.

Structured Locks

Structured lock are obtained using the synchronized construct. It guarantees that the whole code block is executed by the thread that has the lock on the object.

class Counter {
    //...
    void inc() {
        synchronized (this) {
            this.counter = this.counter + 1;
        }
    }
    void dec() {
        synchronized (this) {
            this.counter = this.counter - 1;
        }
    }
    //...
}

It’s possible to have complete synchronize method by using the synchronized keyword in the method’s signature.

class Counter {
    //...
    void synchronized inc() {
        this.counter = this.counter + 1;
    }
    //...
}

Reference: Guarded block

Unstructured Lock

Unstructured lock provide more flexibility by giving the possibility to lock specific part of the code. Using different lock object it’s possible to set up a more specific lock procedure.

Hand-over-hand locking

When working, for example, with a linked list it possible to work on different node at once. Structured lock would lock the whole list when is enough to lock the node effected by the current computation. The Hand-over-hand locking consist, in the specific case of a linked list, in locking the next node while having the lock on the current node and eventually realising the lock on the current node.

class LinkedList {
    //...
    void operation() {
        while(node != tail){
            nextNode = node.next;
            try {
                doOperation(node);
                nextNode.lock.acquire();
            } finally {
                node.lock.release();
            }
            node = nextNode;
        }
    }
    //...
}
Reentrant locking

Reentrant are useful because if it’s not possible for a thread to obtain a lock it would not wait until it manage to acquire it, but instead it would immediately return allowing to perform other operations.

A specif type of reentrant locking can differentiate between “read” and “write” locking. Read lock are used to access an element to read it without changing its value, this can be done by many thread at one. Write lock guarantees instead that only one thread can access an element in reading mode.

Reference: ReentrantLock, ReentrantReadWriteLock

Liveness

  • Deadlock - Happens when multiple threads are waiting for another thread to perform an action, usually realising a lock. Thread are blocked in a situation where no thread can make any progress.
  • Livelock - Threads often communication with each other and depend on other threads action. When one thread trigger another thread, it may happens that the thread perform an action that again trigger the first thread. Even if thread are not blocked they don’t make any progress.
  • Starvation - Happens when a thread is not able to make any progress because some shared result are often inaccessible.

Dining Philosophers

It’s not trivial to implement the dining philosophers problem using just locks. With structured lock deadlock may occur, because every philosopher would own the lock on its left chopstick (all chopstick would be owned) and none would be able to get the lock on the right chopstick. Using unstructured lock could, on the other hand, cause livelock. With try-lock on left chopstick first and then on the right chopstick it may occur that every philosopher succeeds in getting the lock on the left but fail on the right lock.

To solve the problem it’s enough to make a philosopher to lock the right chopstick first.

Week 2

Critical section

It’s sometimes useful to rise the abstraction level when developing a concurrent program. The construct isolated it’s used to refer to section of code that must be executed in mutual exclusion.

It’s easy to create pseudo-code using isolated construct that concern different object, for example isolated(A, B) is used to define a code section that must be executed while having a lock on the object A and B. When the intersection between the object in different isolated construct is empty, those code sections can execute in parallel.

  • isolated(A, B) and isolated(A, C) can’t execute in parallel because both need the mutual exclusion on A
  • isolated(A, B) and isolated(C, D) can execute in parallel

Parallel Spanning Tree

makeParent(parent, child){
    if(child.parent == null){
        child.parent = parent
        return true
    }
    return false
}

compute(p) {        // add vertex p to the spanning tree
    for each node c in G[p] {
        if(makeParent(v, c)){
            compute(c)
        }
    }
}

This could cause a data race when multiple thread are checking the parent of node “child”, to avoid that it enough to used isolated(child), that means to access the node in mutual exclusion. This technique, to first check the value and only then set another value it’s the compare-and-set pattern.

Atomic variables

Atomic variables are particular variable that behave as if each operation on them was executed having the lock on the object. Java’s atomic variables provide different operations: compareAndSet(x, y), getAndAdd(x).

Reference: Atomic package

Read-write isolation

When several threads works on a data structure that is not thread-safe it’s possible to exploit the characteristics of the operations. Reading operations don’t modify the structure, for that reason it’s possibile to execute as many reading as wished. On the other hand, a write operation, would change the structure and for that reason only one thread can perform this operation at a given moment.

Reference: ReadWriteLock

Week 3

Actors

Another model in concurrent programming is the actor model. Each thread is an actor that receive and react only to messages that makes the actor perform some operations on its local state. An actor has a local state, mailbox (the container for the messages) and some methods.

Reference: Akka actors library

Sieve of Eratosthenes algorithm

Actors allow to implement what is called pipeline parallelism. In the Eratosthenes algorithm used to find prime numbers it’s possible to have a pipeline of actors that checks for different prime numbers. In this way each actor filter a number, if the number it’s found to not be prime by an actor such number is discarded, otherwise it is sent to the next actor. In addition, the pipeline can grow dynamically.

Week 4

Optimistic Concurrency Control

This pattern require to obtain the value of a specific object, calculate the new value and before setting the updated value it’s mandatory to first check if value is the same as the previous and only then updating the value (using an atomic compareAndSet(x) operations).

class AtomicInteger {
    public int get();
    public void set(int x);
    public void compareAndSet(int v, int x);

    public getAndAdd(int x){
        while(true){
            int curr = this.get();
            int newValue = curr + x;
            if(this.compareAndSet(curr, newValue)){
                return curr;
            }
        }
    }
}

Linearizability

When implementing a concurrent data structure it’s important that the operations can be proven to be linearizable. That means that it’s possible to find a correct mapping in time where the operations took place and lead to a consistent result. For example, let’s say that on a concurrent queue thread $t1$ perform a enqueue operation inserting $x$ and also thread $t2$ perform a enqueue inserting $y$ and after that a dequeue operation. It’s possible, given the concurrency that $x$ is enqueued before $y$ but it’s also possible that $y$ in enqueued first. What it’s not possible is that the dequeue return neither $x$ or $y$. Since the dequeue op happens after at least one enqueue in thread $t2$, at least $y$ should be present.

Minimum Spanning Tree

It’s possible to implement a concurrent MST algorithm by augmenting Boruvka’s algorithm. The basic algorithm require to have the set of vertices $V$ and a set of connected vertices $W$. Then for each vertex $v \in V$, add $v$ to $W_1 \subseteq W$ and find the edge with the smallest weight from $v$ to $u \not\in W_1$. Each set $W_i$ represent a subtree of the minimum spanning tree. In the worst case, after the first iterations there will be $V$ subtree, each of size $1$, after the second there will be $\frac{V}{2}$ of size $2$ and finally, after the $\log V$-th iteration there will be $1$ subtree of size $V$ (the MST). Since on every iterations the algorithm execute $E$ operations (check at most all edges) the total running time will be $O(E\log V)$.

It’s possible to use multiple threads to extract a new vertex from $V$ provided that the two threads works on different vertices. If the edge found by thread $t1$ connect $v1$ to $u1$ and the edge found by thread $t2$ connect $v2$ to $u2$, a data race arise if $u1 = u2$. To solve the problem, it’s possible to use try-lock (Java’s ReentrantLock) first on $v$ and then only if $v$ is locked, on $u$. If a thread fail to obtain the lock on $u$ then the lock on $v$ must be released to avoid deadlock.

Go to top