Multicore Programming - Lab 2

Download the archive of pre-filled code for this lab.

Let’s start with a quick tour of threads management in Java.

Concurrent counter in Java

Exercise In exo1_compteur/ you will find the code of a concurrent counter. Read it to learn how to start a thread in Java, either by implementing the interface Runnable or through an anonymous function. Do you still remember what a concurrent access (data race) is? Run the program to refresh your memory.

Your mission: explore different approaches to avoid such data races. Each time, define a new class that implements Compteur.

  1. CompteurMutex : use a mutex (see lesson last week). Java’s Lock interface documentation is your friend.
  2. CompteurAtomic: use an atomic integer
  3. CompteurCAS: use the compareAndSet method of atomic integers.
  4. CompteurSynchronized: prefix the declaration of method incr with the keyword synchronized.

Monitor concept

A monitor is a program structure invented by Per Brinch Hansen and Tony Hoare that first appeared in the Concurrent Pascal language. Although the idea was therefore not originally formulated in the object paradigm, it can be described simply as an object in which the methods (declared synchronizedin Java) execute in critical section. So there is an implicit mutex associated with the object. A monitor also has a condition variable associated with this mutex. This is a new synchronization primitive that we now need to talk about.

Before explaining how it works, let’s try to give an implementation of a semaphore without condition variable. A semaphore is a positive and blocking atomic counter: on the one hand, it can be incremented atomically (release), and on the other hand, it can be atomically decremented (acquire). Acquire is blocking: the value after decrement must remain positive or zero. In particular, a semaphore can be used as a lock: with a value of 1, the lock is free, and with a value of 0, the lock is taken. This is another very classic synchronization primitive available in the standard Java library, see java.util.concurrent.Semaphore , and as often we will redefine it simply for educational purposes.

interface Semaphore {
    void set(int initValue);
    void acquire(); // <- blocking!
    void release();
}

class LockSemaphore<S extends Semaphore> implements Lock {
    private final S s;
    LockSemaphore(S s){ 
        this.s = s;
        s.set(1);
    }
    public void lock() { s.acquire(); }
    public void unlock() { s.release(); }
    // [...]
    // cheating a bit, there would be other methods to implement
}

Exercise : Complete the code in exo2_semaphore/SemaphoreAtomicInteger.java and give an implementation of a semaphore with a AtomicInteger. Run and verify that your implementation is correct.

Would we want to implement a semaphore using a monitor, without knowing the condition variables, we could have naively written this

class SemaphoreNaif implements Semaphore {
    private int val;
    SemaphoreNaif(int initValue){ val = initValue;}
    synchronized void release(){ val++; }
    synchronized void acquire(){
        while( val < 1 );
        val--;
    }
}

Question Do you see why this is such a bad idea?

Now back to condition variables. A condition variable allows a thread, in the middle of a critical section, to wait. When it starts waiting, a thread treleases the lock to allow another thread to take it, and falls asleep. Later, another thread, in the middle of the critical section, can signal the condition variable. This signaling thread then wakes up one (notify) or all (notifyAll) waiting threads. The signaller retains the lock, the awakened thread(s) are just put back into the lock queue. When they acquire the lock, they will resume the critical section right after the wait where they fell asleep. If no thread was asleep at the time of the signal, the signal is lost. To implement a semaphore, we can therefore define the monitor as follows.

class SemaphoreMonitor implements Semaphore {

    private int val;
    private final int init;

    SemaphoreMonitor(int initValue){ init = val = initValue; }

    synchronized void release(){
        val++;
        if ( val == 1 ) notifyAll();
    }

    synchronized void acquire(){
        while ( val < 1 ) wait();
        val--;
    }

    int getInit() { return init; }
}

Questions :

Loop parallelization

One of the benefits of threads is that they can improve the performance of a program when it is executed on a multicore machine (in other words, almost any machine today). There are several “patterns” of code parallelization that you need to know, we are going to focus for the moment on the simplest of them, loop parallelization, and we are going to do it on a very simple problem, the counting of the number of occurrences of a given value in an array.

Exercise

  1. Run and read the code in the exo3_nbOccurs/.

  2. Implement the method nbOccursParallel2 that calculates the number of occurrences using two threads that share the first and second half of the array. Run and verify that the result is correct and the speedup reasonable.

  3. Implement the method nbOccursParallelN that calculates the number of occurrences using N threads. Execute and verify that the result is correct and the speedup reasonable (beware, thread creation is expensive, you will be far from a speedup of N).

  4. Re-implement the method nbOccursParallelNusing an ExecutorService and ArrayLista Future .