Simple Stack Lock-gratuit

Question

récemment ont trouvé cette tâche d'entrevue de java concurrency:

Ecrire Empilement simple sans serrure avec deux méthodes: pousser et pop.

J'ai fait la concent:

import java.util.concurrent.atomic.AtomicInteger; 


public class Stack { 
    private AtomicInteger count = new AtomicInteger(-1); 
    private Object[] data = new Object[1000]; 

    public void push(Object o) { 
     int c = count.incrementAndGet(); 
     data[c] = o; 
    } 

    public Object pop() { 
     Object top; 
     int c; 
     while (true) { 
      c = count.get(); 
      if (c == -1) return null; 
      top = data[c]; 
      if (count.compareAndSet(c, c-1)) 
       return top; 
     } 
    } 
} 

Est-il semblable à l'approche était attendue? Ou "pile sans verrou" signifie quelque chose de différent? S'il vous plaît, aidez un débutant java-interview.

Answer 1

Vous avez certainement commencé dans la bonne direction en pensant à l'utilisation des fonctions atomiques et atomiques de Java. Ce serait donc une pile sans verrou, comme dans: il n'y a pas de verrous explicites. Cependant, il n'est pas toujours correct d'accéder simultanément, et il est relativement simple de démontrer que: Imaginez que vos threads push() obtiennent le compte et ajoutent le nouvel élément à la pile (data [c] = o) , et en attendant un fil pop() arrive, obtient le nombre plus élevé, et apparaît ... Quoi? Quoi qu'il arrive d'être en mémoire à cet endroit dans la pile, mais pas l'objet o (parce qu'il n'était pas encore inséré). Et c'est le problème avec les piles verrouillées sans pile, que vous avez deux choses que vous devez théoriquement ajuster, le nombre et le contenu de cette cellule particulière, et vous ne pouvez pas faire les deux atomiquement en même temps temps. Je ne suis pas au courant d'un algorithme de pile back-backed back-array sans verrouillage là-bas.

Il existe des algorithmes de pile à liste liée qui sont sans verrou, car dans ce cas vous pouvez créer un nouveau nœud, lui assigner le contenu et vous n'avez qu'une seule opération à exécuter atomiquement: changer le pointeur supérieur . Si l'argument vous intéresse, le meilleur travail littéraire est celui de Shavit et Herlihy, «L'art de la programmation multiprocesseur», qui décrit de nombreuses structures de données différentes, à la fois sans verrou et à base de verrous. Je ne peux pas trouver de papier décrivant l'algorithme de pile sans verrou "habituel" en détail, bien que Maged Michael le mentionne dans his SMR paper, page 8, point 4.2, et que j'ai fait a C99 implementation moi-même.

Answer 2

Vous pouvez utiliser BlockingQueue Utilisez la méthode put() pour insérer l'élément et la méthode drainTo (Collection c) pour obtenir des éléments. Lisez ensuite les éléments de la fin de c.

Answer 3

public class MyConcurrentStack<T> 
{ 
private AtomicReference<Node> head = new AtomicReference<Node>(); 
public MyConcurrentStack() 
{ 

} 

public void push(T t) 
{ 
    Node<T> n = new Node<T>(t); 
    Node<T> current; 

    do 
    { 
     current = head.get(); 
     n.setNext(current); 
    }while(!head.compareAndSet(current, n)); 
} 

public T pop() 
{ 
    Node<T> currentHead = null; 
    Node<T> futureHead = null; 
    do 
    { 
     currentHead = head.get(); 
     if(currentHead == null) 
     { 
      return null; 
     } 
     futureHead = currentHead.next; 
    }while(!head.compareAndSet(currentHead, futureHead)); 

    return currentHead.data; 
} 

public T peek() 
{ 
    Node<T> n = head.get(); 
    if(n==null) 
    { 
     return null; 
    } 
    else 
    { 
     return n.data; 
    } 
} 

private static class Node<T> 
{ 
     private final T data; 
     private Node<T> next; 

     private Node(T data) 
     { 
      this.data = data; 
     } 

     private void setNext(Node next) 
     { 
      this.next = next; 
     } 
} 

public static void main(String[] args) 
{ 
    MyConcurrentStack m = new MyConcurrentStack(); 
    m.push(12); 
    m.push(13); 
    m.push(15); 

    System.out.println(m.pop()); 
    System.out.println(m.pop()); 
    System.out.println(m.pop()); 
    System.out.println(m.pop()); 
} 
} 

Le code est explicite. S'il vous plaît laissez-moi savoir si quelqu'un a besoin d'explications. L'empilement est formé selon le schéma suivant:

...  ...  ... 
| |-->| | -->| | 
    ...  ...  ... 

^
    | 
current head 

Answer 4

import java.util.Random; 
import java.util.concurrent.atomic.AtomicReference; 

public class LockFreeStack { 

public static void main(String... args) { 
    LFStack<String> stack = new LFStack<String>(); 
    for (int i = 0; i < 10; i++) { 
     Thread t = new Thread(new RandomStackUse(stack)); 
     t.setName("My stack thread " + i); 
     t.start(); 
    } 
} 

private static class LFStack<E> { 
    private volatile AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(); 

    public E peek() { 
     E payload = null; 
     Node<E> oldHeadNode = head.get(); 
     if (oldHeadNode != null) { payload = head.get().payload; } 
     return payload; 
    } 

    public E pop() { 
     E payload; 
     while (true) { 
      Node<E> oldHeadNode = head.get(); 
      if (oldHeadNode == null) { return null; } 
      payload = head.get().payload; 
      if (head.compareAndSet(oldHeadNode, oldHeadNode.next.get())) { break; } 
      //System.out.println("Retry"); 
     } 
     return payload; 
    } 

    public void push(E e) { 
     Node<E> oldHeadNode = new Node<E>(e); 

     while (true) { 
      Node<E> oldRootNode = head.get(); 
      if (oldRootNode != null) { oldHeadNode.next.set(oldRootNode); } 
      if (head.compareAndSet(oldRootNode, oldHeadNode)) { break; } 
      //System.out.println("Retry"); 
     } 
    } 
} 


//to be used as LinkedList chain <Node> => <Node> => <Node> => null 
private static class Node<E> { 
    private E payload; 
    private AtomicReference<Node<E>> next; 

    public Node(E e) { 
     payload = e; 
     next = new AtomicReference<Node<E>>(); 
    } 
} 

public static class RandomStackUse implements Runnable { 
    private LFStack<String> stack; 
    private Random rand = new Random(); 

    public RandomStackUse(LFStack<String> stack) {this.stack = stack;} 

    @Override 
    public void run() { 
     long counter = 0; 
     while (true) { 
      if (rand.nextInt() % 3 == 0) { 
       stack.push(String.valueOf(counter++)); 
       //System.out.println(String.format("%s pushed %d", Thread.currentThread().getName(), counter)); 
      } 
      if (rand.nextInt() % 3 == 1) { 
       String value = stack.pop(); 
       //System.out.println(String.format("%s pop %s", Thread.currentThread().getName(), value)); 
      } 
      if (rand.nextInt() % 3 == 2) { 
       String value = stack.peek(); 
       //System.out.println(String.format("%s peek %s", Thread.currentThread().getName(), value)); 
      } 
     } 
    } 
} 
}