LeetCode - Concurrency - 1114. Print in Order

An example of multiple solutions selected from discuss.

Java

volatile

Using volatile variables reduces the risk of memory consistency errors, because any write to a volatile variable establishes a happens-before relationship with subsequent reads of that same variable. This means that changes to a volatile variable are always visible to other threads. What’s more, it also means that when a thread reads a volatile variable, it sees not just the latest change to the volatile, but also the side effects of the code that led up the change.

volatile has semantics for memory visibility. Basically, the value of a volatile field becomes visible to all readers (other threads in particular) after a write operation completes on it. Without volatile, readers could see some non-updated value.

In programming, an atomic action is one that effectively happens all at once. An atomic action cannot stop in the middle: it either happens completely, or it doesn’t happen at all. No side effects of an atomic action are visible until the action is complete.

  • Reads and writes are atomic for reference variables and for most primitive variables (all types except long and double).
  • Reads and writes are atomic for all variables declared volatile (including long and double variables).

[Java] Simple, yet effective. Using volatile without lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Foo {
    private volatile int flag;

    public Foo() {
        flag = 1;
    }

    public void first(Runnable printFirst) throws InterruptedException {
        for(;;) {
        	if (flag==1) {
        		printFirst.run();
                flag = 2;
                break;
        	}
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
    	for(;;) {
    		if (flag==2) {
    			printSecond.run();
                flag=3;
                break;
    		}
    	}
    }

    public void third(Runnable printThird) throws InterruptedException {
    	for(;;) {
    		if (flag==3) {
    			printThird.run();
                flag = 1;
                break;
    		}
    	}
    }
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 88.93% of Java online submissions for Print in Order.
Memory Usage: 35.9 MB, less than 100.00% of Java online submissions for Print in Order.

Semaphore

Conceptually, a semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, potentially releasing a blocking acquirer. However, no actual permit objects are used; the Semaphore just keeps a count of the number available and acts accordingly.

Semaphores are often used to restrict the number of threads that can access some (physical or logical) resource.

[Java/Go] Implements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.concurrent.Semaphore;

class Foo {
	Semaphore semaphore1 = new Semaphore(0);
	Semaphore semaphore2 = new Semaphore(0);

	public Foo() {

	}

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        semaphore1.release();

    }

    public void second(Runnable printSecond) throws InterruptedException {
    	semaphore1.acquire();
    	printSecond.run();
    	semaphore2.release();

    }

    public void third(Runnable printThird) throws InterruptedException {
    	semaphore2.acquire();
    	printThird.run();
    }
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 89.05% of Java online submissions for Print in Order.
Memory Usage: 35.7 MB, less than 100.00% of Java online submissions for Print in Order.

synchronized

The Java programming language provides two basic synchronization idioms: synchronized methods and synchronized statements.

Unlike synchronized methods, synchronized statements must specify the object that provides the intrinsic lock.

Synchronized statements are also useful for improving concurrency with fine-grained synchronization.

[Java] Basic version with just a synchronized block & a counter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Foo {
	private String mutex = new String("");
	private int counter = 1;

	public Foo() {
	}

    public void first(Runnable printFirst) throws InterruptedException {
    	boolean loop = true;
    	while (loop) {
    		synchronized(mutex) {
    			if (counter == 1) {
    				printFirst.run();
    				++counter;
    				loop = false;
    			}
    		}
    	}
    }

    public void second(Runnable printSecond) throws InterruptedException {
    	boolean loop = true;
    	while (loop) {
    		synchronized(mutex) {
    			if (counter == 2) {
    				printSecond.run();
    				++counter;
    				loop = false;
    			}
    		}
    	}
    }

    public void third(Runnable printThird) throws InterruptedException {
    	boolean loop = true;
    	while (loop) {
    		synchronized(mutex) {
    			if (counter == 3) {
    				printThird.run();
    				++counter;
    				loop = false;
    			}
    		}
    	}
    }
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 89.16% of Java online submissions for Print in Order.
Memory Usage: 36 MB, less than 100.00% of Java online submissions for Print in Order.

CountDownLatch

A synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes.

A CountDownLatch is initialized with a given count. The await methods block until the current count reaches zero due to invocations of the countDown() method, after which all waiting threads are released and any subsequent invocations of await return immediately. This is a one-shot phenomenon – the count cannot be reset.

A CountDownLatch is a versatile synchronization tool and can be used for a number of purposes. A CountDownLatch initialized with a count of one serves as a simple on/off latch, or gate: all threads invoking await wait at the gate until it is opened by a thread invoking countDown(). A CountDownLatch initialized to N can be used to make one thread wait until N threads have completed some action, or some action has been completed N times.

A useful property of a CountDownLatch is that it doesn’t require that threads calling countDown wait for the count to reach zero before proceeding, it simply prevents any thread from proceeding past an await until all threads could pass.

Another typical usage would be to divide a problem into N parts, describe each part with a Runnable that executes that portion and counts down on the latch, and queue all the Runnables to an Executor. When all sub-parts are complete, the coordinating thread will be able to pass through await.

[Java] 7ms CountDownLatch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.concurrent.CountDownLatch;

class Foo {
	private final CountDownLatch L1 = new CountDownLatch(1);
	private final CountDownLatch L2 = new CountDownLatch(1);

	public Foo() {
	}

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        L1.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
    	L1.await();
    	printSecond.run();
    	L2.countDown();

    }

    public void third(Runnable printThird) throws InterruptedException {
    	L2.await();
    	printThird.run();
    }
}

36 / 36 test cases passed.
Runtime: 9 ms, faster than 89.16% of Java online submissions for Print in Order.
Memory Usage: 35.4 MB, less than 100.00% of Java online submissions for Print in Order.

Phaser

A reusable synchronization barrier, similar in functionality to CyclicBarrier and CountDownLatch but supporting more flexible usage.

Methods arrive() and arriveAndDeregister() record arrival. These methods do not block, but return an associated arrival phase number; that is, the phase number of the phaser to which the arrival applied.

Method awaitAdvance(int) requires an argument indicating an arrival phase number, and returns when the phaser advances to (or is already at) a different phase.

Java Phaser solution, very fast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.concurrent.Phaser;

class Foo {
	private Phaser phaser;

	public Foo() {
		phaser = new Phaser(3);
	}

    public void first(Runnable printFirst) throws InterruptedException {
    	phaser.arrive();
    	phaser.awaitAdvance(0);
        printFirst.run();
        phaser.arrive();
        phaser.arrive();

    }

    public void second(Runnable printSecond) throws InterruptedException {
    	phaser.arrive();
    	phaser.awaitAdvance(0);
    	phaser.arrive();
    	phaser.awaitAdvance(1);
    	printSecond.run();
    	phaser.arrive();

    }

    public void third(Runnable printThird) throws InterruptedException {
    	phaser.arrive();
    	phaser.awaitAdvance(0);
    	phaser.arrive();
    	phaser.awaitAdvance(1);
    	phaser.arrive();
    	phaser.awaitAdvance(2);
    	printThird.run();
    }
}

36 / 36 test cases passed.
Runtime: 10 ms, faster than 55.92% of Java online submissions for Print in Order.
Memory Usage: 36 MB, less than 100.00% of Java online submissions for Print in Order.