SharedDeque (Jikes RVM API)

java.lang.Object
- org.mmtk.utility.deque.Deque
- - org.mmtk.utility.deque.SharedDeque

Direct Known Subclasses:

SortSharedDeque
```
public class SharedDeque
extends Deque
```
This supports unsynchronized enqueuing and dequeuing of buffers for shared use. The data can be added to and removed from either end of the deque.

Field Summary

Fields
Modifier and Type	Field and Description
`private int`	`arity` Number of words per entry
`private int`	`bufsenqueued`
`private int`	`completionFlag` Completion flag - set when all consumers have arrived at the barrier
`private static boolean`	`DISABLE_WAITING`
`protected Address`	`head` Head of the shared deque
`private Lock`	`lock`
`private String`	`name` The name of this shared deque - for diagnostics
`private static Offset`	`NEXT_OFFSET`
`private int`	`numConsumers` # active threads - processing is complete when # waiting == this
`private int`	`numConsumersWaiting` # threads waiting
`private static Offset`	`PREV_OFFSET`
`private RawPageSpace`	`rps` Raw page space from which to allocate
`protected Address`	`tail` Tail of the shared deque
`private static long`	`TIMEOUT_PERIOD`
`private static boolean`	`TRACE`
`private static boolean`	`TRACE_BLOCKERS`
`private static boolean`	`TRACE_DETAIL`
`private static long`	`WARN_PERIOD`

Fields inherited from class org.mmtk.utility.deque.Deque
BUFFER_MASK, BUFFER_SIZE, HEAD_INITIAL_VALUE, LOG_PAGES_PER_BUFFER, META_DATA_SIZE, NEXT_FIELD_OFFSET, PAGES_PER_BUFFER, TAIL_INITIAL_VALUE, USABLE_BUFFER_BYTES

Constructor Summary

Constructors
Constructor and Description

SharedDeque(String name, RawPageSpace rps, int arity)

Constructors
Constructor and Description
`SharedDeque(String name, RawPageSpace rps, int arity)`

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`(package private) Address`	`alloc()`
`void`	`assertExhausted()`
`private boolean`	`checkDequeLength(int length)` Check the number of buffers in the work queue (for debugging purposes).
`private void`	`clearCompletionFlag()` Clear the completion flag.
`void`	`clearDeque(int arity)`
`private boolean`	`complete()`
`private Address`	`dequeue(boolean waiting, boolean fromTail)` Dequeue a block from the shared pool.
`(package private) Address`	`dequeue(int arity)`
`(package private) Address`	`dequeue(int arity, boolean fromTail)`
`(package private) Address`	`dequeueAndWait(int arity)`
`(package private) Address`	`dequeueAndWait(int arity, boolean fromTail)`
`(package private) void`	`enqueue(Address buf, int arity, boolean toTail)` Enqueue a block on the head or tail of the shared queue
`int`	`enqueuedPages()`
`(package private) void`	`free(Address buf)`
`(package private) int`	`getArity()`
`protected Address`	`getNext(Address buf)` Get the "next" pointer in a buffer forming the linked buffer chain.
`protected Address`	`getPrev(Address buf)` Get the "next" pointer in a buffer forming the linked buffer chain.
`private void`	`lock()` Lock this shared queue.
`void`	`prepare()` Prepare for parallel processing.
`private void`	`prepare(int consumers)` Prepare for parallel processing where a specific number of threads take part.
`void`	`prepareNonBlocking()` Prepare for processing where pop operations on the deques will never block.
`void`	`reset()`
`private void`	`setCompletionFlag()` Set the completion flag.
`private void`	`setHead(Address newHead)`
`private static void`	`setNext(Address buf, Address next)` Set the "next" pointer in a buffer forming the linked buffer chain.
`private void`	`setNumConsumers(int newNumConsumers)`
`private void`	`setNumConsumersWaiting(int newNCW)`
`private void`	`setPrev(Address buf, Address prev)` Set the "prev" pointer in a buffer forming the linked buffer chain.
`private void`	`setTail(Address newTail)`
`private void`	`spinWait(boolean fromTail)` Spinwait for GC work to arrive
`private void`	`unlock()` Release the lock.

Methods inherited from class org.mmtk.utility.deque.Deque
bufferEnd, bufferFirst, bufferLast, bufferLast, bufferLastOffset, bufferOffset, bufferStart

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - DISABLE_WAITING
```
private static final boolean DISABLE_WAITING
```
    See Also:
    
    Constant Field Values
  - NEXT_OFFSET
```
private static final Offset NEXT_OFFSET
```
  - PREV_OFFSET
```
private static final Offset PREV_OFFSET
```
  - TRACE
```
private static final boolean TRACE
```
    See Also:
    
    Constant Field Values
  - TRACE_DETAIL
```
private static final boolean TRACE_DETAIL
```
    See Also:
    
    Constant Field Values
  - TRACE_BLOCKERS
```
private static final boolean TRACE_BLOCKERS
```
    See Also:
    
    Constant Field Values
  - name
```
private final String name
```
    The name of this shared deque - for diagnostics
  - rps
```
private final RawPageSpace rps
```
    Raw page space from which to allocate
  - arity
```
private final int arity
```
    Number of words per entry
  - completionFlag
```
private volatile int completionFlag
```
    Completion flag - set when all consumers have arrived at the barrier
  - numConsumers
```
private volatile int numConsumers
```
    # active threads - processing is complete when # waiting == this
  - numConsumersWaiting
```
private volatile int numConsumersWaiting
```
    # threads waiting
  - head
```
protected volatile Address head
```
    Head of the shared deque
  - tail
```
protected volatile Address tail
```
    Tail of the shared deque
  - bufsenqueued
```
private volatile int bufsenqueued
```
  - lock
```
private final Lock lock
```
  - WARN_PERIOD
```
private static final long WARN_PERIOD
```
    See Also:
    
    Constant Field Values
  - TIMEOUT_PERIOD
```
private static final long TIMEOUT_PERIOD
```
    See Also:
    
    Constant Field Values
- Constructor Detail
  - SharedDeque
```
public SharedDeque(String name,
                   RawPageSpace rps,
                   int arity)
```
    Parameters:
    
    name - the queue's human-readable name
    
    rps - the space to get pages from
    
    arity - the arity (number of words per entry) of this queue
- Method Detail
  - getArity
```
final int getArity()
```
    Returns:
    
    the arity (words per entry) of this queue
  - enqueue
```
final void enqueue(Address buf,
                   int arity,
                   boolean toTail)
```
    Enqueue a block on the head or tail of the shared queue
    
    Parameters:
    
    buf - the block to enqueue
    
    arity - the arity of this queue
    
    toTail - whether to enqueue to the tail of the shared queue
  - clearDeque
```
public final void clearDeque(int arity)
```
  - dequeue
```
final Address dequeue(int arity)
```
  - dequeue
```
final Address dequeue(int arity,
                      boolean fromTail)
```
  - dequeueAndWait
```
final Address dequeueAndWait(int arity)
```
  - dequeueAndWait
```
final Address dequeueAndWait(int arity,
                             boolean fromTail)
```
  - prepare
```
public final void prepare()
```
    Prepare for parallel processing. All active GC threads will participate, and pop operations will block until all work is complete.
  - prepareNonBlocking
```
public final void prepareNonBlocking()
```
    Prepare for processing where pop operations on the deques will never block.
  - prepare
```
private void prepare(int consumers)
```
    Prepare for parallel processing where a specific number of threads take part.
    
    Parameters:
    
    consumers - # threads taking part.
  - reset
```
public final void reset()
```
  - assertExhausted
```
public final void assertExhausted()
```
  - alloc
```
final Address alloc()
```
  - free
```
final void free(Address buf)
```
  - enqueuedPages
```
public final int enqueuedPages()
```
  - dequeue
```
private Address dequeue(boolean waiting,
                        boolean fromTail)
```
    Dequeue a block from the shared pool. If 'waiting' is true, and the queue is empty, wait for either a new block to show up or all the other consumers to join us.
    
    Parameters:
    
    waiting - whether to wait to dequeue a block if none is present
    
    fromTail - whether to dequeue from the tail
    
    Returns:
    
    the Address of the block
  - spinWait
```
private void spinWait(boolean fromTail)
```
    Spinwait for GC work to arrive
    
    Parameters:
    
    fromTail - Check the head or the tail ?
  - setNext
```
private static void setNext(Address buf,
                            Address next)
```
    Set the "next" pointer in a buffer forming the linked buffer chain.
    
    Parameters:
    
    buf - The buffer whose next field is to be set.
    
    next - The reference to which next should point.
  - getNext
```
protected final Address getNext(Address buf)
```
    Get the "next" pointer in a buffer forming the linked buffer chain.
    
    Parameters:
    
    buf - The buffer whose next field is to be returned.
    
    Returns:
    
    The next field for this buffer.
  - setPrev
```
private void setPrev(Address buf,
                     Address prev)
```
    Set the "prev" pointer in a buffer forming the linked buffer chain.
    
    Parameters:
    
    buf - The buffer whose next field is to be set.
    
    prev - The reference to which prev should point.
  - getPrev
```
protected final Address getPrev(Address buf)
```
    Get the "next" pointer in a buffer forming the linked buffer chain.
    
    Parameters:
    
    buf - The buffer whose next field is to be returned.
    
    Returns:
    
    The next field for this buffer.
  - checkDequeLength
```
private boolean checkDequeLength(int length)
```
    Check the number of buffers in the work queue (for debugging purposes).
    
    Parameters:
    
    length - The number of buffers believed to be in the queue.
    
    Returns:
    
    True if the length of the queue matches length.
  - lock
```
private void lock()
```
    Lock this shared queue. We use one simple low-level lock to synchronize access to the shared queue of buffers.
  - unlock
```
private void unlock()
```
    Release the lock. We use one simple low-level lock to synchronize access to the shared queue of buffers.
  - complete
```
private boolean complete()
```
    Returns:
    
    whether the current round of processing is complete
  - setCompletionFlag
```
private void setCompletionFlag()
```
    Set the completion flag.
  - clearCompletionFlag
```
private void clearCompletionFlag()
```
    Clear the completion flag.
  - setNumConsumers
```
private void setNumConsumers(int newNumConsumers)
```
  - setNumConsumersWaiting
```
private void setNumConsumersWaiting(int newNCW)
```
  - setHead
```
private void setHead(Address newHead)
```
  - setTail
```
private void setTail(Address newTail)
```

Class SharedDeque

Field Summary

Fields inherited from class org.mmtk.utility.deque.Deque

Constructor Summary

Method Summary

Methods inherited from class org.mmtk.utility.deque.Deque

Methods inherited from class java.lang.Object

Field Detail

DISABLE_WAITING

NEXT_OFFSET

PREV_OFFSET

TRACE

TRACE_DETAIL

TRACE_BLOCKERS

name

rps

arity

completionFlag

numConsumers

numConsumersWaiting

head

tail

bufsenqueued

lock

WARN_PERIOD

TIMEOUT_PERIOD

Constructor Detail

SharedDeque

Method Detail

getArity

enqueue

clearDeque

dequeue

dequeue

dequeueAndWait

dequeueAndWait

prepare

prepareNonBlocking

prepare

reset

assertExhausted

alloc

free

enqueuedPages

dequeue

spinWait

setNext

getNext

setPrev

getPrev

checkDequeLength

lock

unlock

complete

setCompletionFlag

clearCompletionFlag

setNumConsumers

setNumConsumersWaiting

setHead

setTail