elimination-backoff-stack.java/Exchanger.java at master · moocf/elimination-backoff-stack.java · GitHub

History

80 lines (73 loc) · 2.41 KB

Raw

import java.util.concurrent.*;

import java.util.concurrent.atomic.*;

// Exchanger is a lock-free object that permits two threads

// to exchange values, within a time limit.

class Exchanger<T> {

AtomicStampedReference<T> slot;

static final int EMPTY = 0;

static final int WAITING = 1;

static final int BUSY = 2;

// slot: stores value and stamp

// EMPTY: slot has no value.

// WAITING: slot has 1st value, waiting for 2nd.

// BUSY: slot has 2nd value, waiting to be empty.

public Exchanger() {

slot = new AtomicStampedReference<>(null, 0);

}

// 1. Calculate last wait time.

// 2. If wait time exceeded, then throw expection.

// 3. Get slot value and stamp.

// 4a. If slot is EMPTY (no value):

// 4b. Try adding 1st value to slot, else retry 2.

// 4c. Try getting 2nd value from slot, within time limit.

// 5a. If slot is WAITING (has 1st value):

// 5b. Try adding 2nd value to slot, else retry 2.

// 5c. Return 1st value.

// 6a. If slot is BUSY (has 2nd value):

// 6b. Retry 2.

public T exchange(T y, long timeout, TimeUnit unit)

throws TimeoutException {

long w = unit.toNanos(timeout); // 1

long W = System.nanoTime() + w; // 1

int[] stamp = {EMPTY};

while (System.nanoTime() < W) { // 2

T x = slot.get(stamp); // 3

switch (stamp[0]) { // 3

case EMPTY: // 4

if (addA(y)) { // 4

while (System.nanoTime() < W) // 4

if ((x = removeB()) != null) return x; // 4

throw new TimeoutException(); // 5

}

break;

case WAITING: // 7

if (addB(x, y)) // 7

return x; // 7

break;

case BUSY: // 8

break; // 8

default:

}

throw new TimeoutException(); // 2

}

// 1. Add 1st value to slot.

// 2. Set its stamp as WAITING (for 2nd).

private boolean addA(T y) { // 1, 2

return slot.compareAndSet(null, y, EMPTY, WAITING);

}

// 1. Add 2nd value to slot.

// 2. Set its stamp as BUSY (for 1st to remove).

private boolean addB(T x, T y) { // 1, 2

return slot.compareAndSet(x, y, WAITING, BUSY);

}

// 1. If stamp is not BUSY (no 2nd value in slot), exit.

// 2. Set slot as EMPTY, and get 2nd value from slot.

private T removeB() {

int[] stamp = {EMPTY};

T x = slot.get(stamp); // 1

if (stamp[0] != BUSY) return null; // 1

slot.set(null, EMPTY); // 2

return x; // 2

}

elimination-backoff-stack.java/Exchanger.java at master · moocf/elimination-backoff-stack.java · GitHub

Uh oh!

Expand file tree

Breadcrumbs

Exchanger.java

Latest commit

History

Breadcrumbs

Exchanger.java

File metadata and controls