Programming a mutex in Java

Question

I'm new to Computer Science and I'm reading a book which introduces threads and mutexes. I've tried programming a mutex in Java which seems to work most of the time but every so often it won't.

In my code, the critical section adds on the numbers 1 to 10 to a static variable j which results in 55 (if j starts at 0). If I run three threads at the same time through the critical section, I get random final values of j which makes sense.

But with the mutex below, most of the time I get a final j value of 165 (55*3) which is what I want but on occasions, I get random values of j. Can someone have a look at my code and see what's going on? Thanks!

public class Mythread extends Thread {

    private static int j = 0;
    private static int mutex = 0;  // Initial value of the mutex is 0;

    @Override
    public void run() {


        while (test_and_set(mutex) == 1) {

            // wait here if mutex is 1
            System.out.println("Thread waiting..");
        } 

        for (int i = 1; i <= 10; i++) { // Start of Critical section 
            j += i;                     // 

        }
        System.out.println(j);       // End of Critical section 
                                     // Should add on 55 to j if one thread is running through the CS

       mutex = 0; // Thread that has finished the CS sets the mutex to 0.

    }

    public static int test_and_set(int oldMutexValue) {
        if (mutex == 0) {
            mutex = 1;
        }
        return oldMutexValue;
    }


}

public class Test1 {




    public static void main(String[] args) {

        Mythread thread1 = new Mythread();
        Mythread thread2 = new Mythread();
        Mythread thread3 = new Mythread();
        thread1.start();
        thread2.start();
        thread3.start();

    }



}

Answer 1

(1) Your test_and_set() function looks like its supposed to emulate a hardware instruction of the same name that used to be implemented in many computer architectures. But what is test_and_set() supposed to return? Hint: It should tell the caller whether or not the caller "won" the mutex.

(2) There's a bigger problem with your test_and_set(): It's not atomic. If you've wondered why a computer that has "test" instructions and "set" instructions also needs to have a test_and_set (a.k.a., TAS) instruction, it's because the TAS instruction is atomic. I'm guessing you need to learn more about what that means (see 4, below).

(3) TAS is archaic. Modern computers implement something called Compare and Swap or Compare and Set (CAS) which is more powerful. If you want to learn how modern synchronization algorithms work, you should be using CAS instead of TAS.

The Java standard library has a real, really-atomic, CAS function that you can call: It's java.util.concurrent.atomic.AtomicInteger.CompareAndSet(...). http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicInteger.html

(4) You probably should not be trying to learn how to write synchronization functions/objects until you have more experience using them. What gives you away is that you did not synchronize your test_and_set() function. If you didn't know to do that, then you don't have much experience writing multi-threaded code.

Learn how to use synchronization objects first. http://docs.oracle.com/javase/tutorial/essential/concurrency/ Then you can worry about how they are implemented.

Answer 2

You're creating a race condition and using a spinning lock. Spinning locks are not recommended in Java. Consider the following:

One thread begins executing while the other two wait. The other two threads wait. The other two threads now both set the mutexes at the same time and both begin executing, giving you an odd value of J because they're both altering it simultaneously.

To fix:

Implement the Java synchronized methodology. Synchronized is Java's internal method of handling thread-safety and control. No spinning locks!

Change your MyThread to the following:

public class MyThread extends Thread {
private static int j = 0;

public void run() {
    synchronized(this) {
        for (int i = 1; i <= 10; i++) {
            j += i;
        }
    }
    System.out.println(j);
}

Synchronized can surround any critical portions of code that could result in race conditions, simultaneous altering of data, etc. Note the lack of a specific lock. Note that synchronized takes its own object as a parameter, as you are synchronizing control over this object, but you can just as easily take other objects as a parameter, if desired, giving you more flexibility over when things lock down.

The rest of your code will run identically!

Hope this helps!

Answer 3

There is java.util.concurrency.Semaphore class for your task:

package test;

import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;

public class MyThread extends Thread {
    private static int j = 0;
    private static final Semaphore mutex = new Semaphore(1, true);

    @Override
    public void run() {
        try {
            while (!mutex.tryAcquire(100, TimeUnit.MILLISECONDS)) {
                System.out.println("Thread waiting.");
            }
        }
        catch (InterruptedException e) {
            System.out.println("Thread interrupted.");
            return;
        }

        try {
            for (int i = 1; i <= 10; i++) { // Start of Critical section
                j += i;                     //

            }
            System.out.println(j);       // End of Critical section
            // Should add on 55 to j if one thread is running through the CS
        }
        finally {
            mutex.release(); // Thread that has finished the CS sets the mutex to 0.
        }
    }
}