CSCE 314 Lecture 36

« previous | Wednesday, November 30, 2011 | next »

Java Atomic Transactions

import java.util.concurrent.atomic.AtomicInteger

public class NonblockingCounter {
    private AtomicInteger value;

    public int getValue() {
        return value.get();
    }

    private void increment() {
        int v;
        do { v = value.get(); }
        while (!value.compareAndSet(v, v+1));
    }
}

value.compareAndSet() updates value to v+1 atomically, so it cannot be interrupted.

Atomic operations lead to approach of transactions

read a value, perform a computation, commit transaction to shared data. If update fails, start over and redo computation (repeat until success).

"lock-free" concurrent algorithms take a lot of expertise and time.

Almost any code can be placed in a transaction.

Figure out how to change

lock(l); dostuff; unlock(l)

into

atomic { dostuff; }

at compile-time

Example: Nonblocking stack

public class ConcurrentStack<E> {
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();

    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldhead;
        do {
            oldHead = head.get();
            newHead.net = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead, newHead);  // test that oldHead still points to head (i.e. stack hasn't been updated)
        return oldHead.item;
    }

    static class Node<E> {
        final E item;
        node<E> next;

        public Node(E item) { this.item = item; }
    }
}