Multithreading matrix multiplication in Java

Question

i'm trying to build a program for multiplying two matrices (A[a,b], B[c,d]) using a*d threads (that will be used to print the sum of one index in the finished matrix), for this purpose, i'm using a 'monitor' class that will be used as a controller to synchrosize between the threads, 'multiplier' class to represent the single thread and a main program class. My idea is that the threads will have their calculations, and when thread(0,0) will print his sum, he will signal the next in line. For some reason after printing the first index - all the threads stay in waiting mode and won't test my condition. Could you look at my code and tell me where is my mistake?

Monitor class:

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

final class Monitor {
    private Lock lock;
    int index;
    Condition cond; 
    public Monitor () {
        lock = new ReentrantLock();
        cond = lock.newCondition();
        this.index = 0;
    }

    public synchronized void finished(int x, double sum) throws InterruptedException {
        lock.lock();
        if(index != x) {
            while(index != x) cond.await();
            System.out.printf("%9.2f ",sum);
            index++;
            lock.unlock();
            cond.signalAll();
          }
        else {
            System.out.printf("%9.2f ",sum);
            index++;
            try { lock.unlock(); }
            catch (java.lang.IllegalMonitorStateException e) {};
            try { lock.unlock(); }
            catch (java.lang.IllegalMonitorStateException e) {};
        }
        if(index % 5 == 0) System.out.println();
    }
}

Multiplier:

public class Multiplier extends Thread {
    private int index;
    private double [] vectorOne;
    private double [] vectorTwo;
    private Monitor monitor;
    private double sum;

    //constructor
    public Multiplier(int index, Monitor monitor,double [] vectorOne,double [] vectorTwo) {
        this.index = index;
        this.monitor = monitor;
        this.vectorOne = vectorOne;
        this.vectorTwo = vectorTwo;
    }

    public void VecMulti() {
        sum = 0;
        for (int i = 0 ; i < vectorOne.length ; i++) 
            sum += vectorOne[i] * vectorTwo[i];
    }

    public double getSum() {
        return sum;
    }

    public void run() {
        VecMulti();
        try {
            monitor.finished(index, sum);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Main class:

public class MatrixMultiTest {
    public static void main(String[] args) {
        Monitor monitor = new Monitor(3*5);
        Matrix A = Matrix.random(3,4);
        Matrix B = Matrix.random(4,5);
        System.out.println("Matrix No1");
        A.show();
        System.out.println();
        System.out.println("Matrix No2");
        B.show();
        System.out.println();
        System.out.println("Multi Matrix");

        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 5; j++) {
                Multiplier myThr = new Multiplier(i*5+j,
                        monitor,A.getRow(i),B.getCol(j));
                myThr.start();
                try {
                    myThr.join();
                } catch (InterruptedException e) {
                //  TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
    }
}

Answer 1

The finished() method is riddled with problems:

• The first problem is the synchronized keyword. It must be removed. With this keyword, if the first entering thread has a non-zero index, the program will deadlock - the thread will forever be parked waiting for the condition to signal, which will never come, because no other thread can enter the finished() method.

• The second fault lies with the else block:

else {
    System.out.printf("%9.2f ",sum);
    index++;
    try { lock.unlock(); }
    catch (java.lang.IllegalMonitorStateException e) {};
    try { lock.unlock(); }
    catch (java.lang.IllegalMonitorStateException e) {};
}

It never invokes cond.signalAll(), so after the thread with index=0 gets through, others will stay parked forever.

• The third problem is that in if(index != x) {.. block, cond.signalAll() and lock.unlock() come in wrong order:

lock.unlock();
cond.signalAll();

Condition's signalAll() method documentation states:

An implementation may (and typically does) require that the current thread hold the lock associated with this Condition when this method is called. Implementations must document this precondition and any actions taken if the lock is not held. Typically, an exception such as IllegalMonitorStateException will be thrown.

These two lines of code must be switched in order, or an IllegalMonitorStateException will be thrown.

A working version of the method can look something like this:

public void finished(int x, double sum) throws InterruptedException {
    try {
        lock.lock();
        while (index != x) {
            cond.await();
        }
        System.out.printf("%9.2f ", sum);
        index++;
        cond.signalAll();
    } finally {
        lock.unlock();
    }
    if (index % 5 == 0) System.out.println();
}

---

Funny enough, the code provided by OP actually works even with all these faults, but only due to this block of code in the MatrixMultiTest class:

try {
    myThr.join();
} catch (InterruptedException e) {
//  TODO Auto-generated catch block
    e.printStackTrace();
}

Every thread is created and then started and joined sequentially, thus only one thread ever tries to acquire the implicit lock on the synchronized finished() method at any moment in time, and i*5+j index value ensures that the threads acquire this implicit lock in order of their index: 0, 1, 2 etc. It means that inside the method, index is always equal to x, and every thread goes through else block in finished(), allowing the program to complete execution. cond.await() is actually never invoked.

If the join block is removed, then some values might get printed, but the program will eventually deadlock.