WorkStealingQueue

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

pt.queues
Class WorkStealingQueue<E>

java.lang.Object
  pt.queues.WorkStealingQueue<E>


Type Parameters:: E - The type of elements held in this collection

All Implemented Interfaces:: java.lang.Iterable<E>, java.util.Collection<E>, java.util.concurrent.BlockingQueue<E>, java.util.Queue<E>

Direct Known Subclasses:: FifoLifoQueue

public class WorkStealingQueue<E>
extends java.lang.Object
implements java.util.concurrent.BlockingQueue<E>
extends java.lang.Object
implements java.util.concurrent.BlockingQueue<E>

An implementation of a work-stealing queue. Elements are added and removed from the queue using a work-stealing policy.

Elements are added to a thread's local queue, and removed from a thread's local queue using a last in first out (LIFO) policy. If no elements exist in the thread's local queue, an element is stolen using a first in first out (FIFO) policy from another thread's local queue.

Consequently, the "head of the queue" in the context of the WorkStealingQueue refers to the element according to this work-stealing schedule. In other words, "head of the queue" for the thread when it takes from its own local queue refers to the same end where elements are added (i.e. the LIFO end). Similarly, the "head of the queue" for a stealing thread refers to the opposite end of the of the victim's queue (i.e. the FIFO end).

Author:: Nasser Giacaman, Oliver Sinnen

Field Summary
`protected int`	`capacity`
`protected int`	`chunksize`
`protected static int`	`HALF`
`protected java.util.concurrent.ConcurrentHashMap<java.lang.Long,java.util.concurrent.LinkedBlockingDeque<E>>`	`localDeques`
`protected java.util.concurrent.atomic.AtomicInteger`	`remainingCapacity`
`protected static int`	`sleep_amount_milli`

Constructor Summary
`WorkStealingQueue()` Create an empty WorkStealingQueue with maximum capacity and chunksize of 1.
`WorkStealingQueue(java.util.Collection<? extends E> c, int chunksize)` Create a WorkStealingQueue that contains the specified collection of elements and specified chunksize.
`WorkStealingQueue(int capacity, int chunksize)` Create an empty WorkStealingQueue with the specified capacity and chunksize.

Method Summary

boolean add(E e)

boolean addAll(java.util.Collection<? extends E> c)

protected java.util.ArrayList<E> asList()

protected E attemptToStealNonRandom()

protected E attemptToStealRandom()

void clear()

boolean contains(java.lang.Object o)

boolean containsAll(java.util.Collection<?> c)

int drainTo(java.util.Collection<? super E> c)

int drainTo(java.util.Collection<? super E> c, int maxElements)

E element()

boolean isEmpty()

java.util.Iterator<E> iterator()

boolean offer(E e)

boolean offer(E e, long timeout, java.util.concurrent.TimeUnit unit)

E peek()

E poll()

E poll(long timeout, java.util.concurrent.TimeUnit unit)

protected E pollLocalQueue()

void put(E e)

int remainingCapacity()

E remove()

boolean remove(java.lang.Object o)

boolean removeAll(java.util.Collection<?> c)

boolean retainAll(java.util.Collection<?> c)

int size()

E take()

java.lang.Object[] toArray()





<T> T[]

toArray(T[] a)

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

Methods inherited from interface java.util.Collection
`equals, hashCode`

Field Detail

HALF

protected static final int HALF

See Also:: Constant Field Values

sleep_amount_milli

protected static final int sleep_amount_milli

See Also:: Constant Field Values

localDeques

protected java.util.concurrent.ConcurrentHashMap<java.lang.Long,java.util.concurrent.LinkedBlockingDeque<E>> localDeques

remainingCapacity

protected java.util.concurrent.atomic.AtomicInteger remainingCapacity

capacity

protected int capacity

chunksize

protected int chunksize

Constructor Detail