Práctica 4 — Spinlocks y primitivas

Programas_P4/unam.fc.concurrent.practica4/src/module-info.java

/**
 * 
 */
/**
 * 
 */
module unam.fc.concurrent.practica4 {
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/ALock.java

package unam.fc.concurrent.practica4;

/*
 * ALock.java
 *
 * Created on January 20, 2006, 11:02 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */


/**
 * Anderson lock
 * @author Maurice Herlihy
 */
import java.util.concurrent.locks.Lock;
import java.util.concurrent.atomic.AtomicInteger;
import java.lang.ThreadLocal;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.TimeUnit;
public class ALock implements Lock {
  // thread-local variable
  ThreadLocal<Integer> mySlotIndex = new ThreadLocal<Integer> (){
    protected Integer initialValue() {
      return 0;
    }
  };
  AtomicInteger tail;
  boolean[] flag;
  int size;
  /**
   * Constructor
   * @param capacity max number of array slots
   */
  public ALock(int capacity) {
    size = capacity;
    tail = new AtomicInteger(0);
    flag = new boolean[capacity];
    flag[0] = true;
  }
  public void lock() {
    int slot = tail.getAndIncrement() % size;
    mySlotIndex.set(slot);
    while (! flag[mySlotIndex.get()]) {}; // spin
  }
  public void unlock() {
    flag[mySlotIndex.get()] = false;
    flag[(mySlotIndex.get() + 1) % size] = true;
  }
  // any class implementing Lock must provide these methods
  public Condition newCondition() {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock(long time,
      TimeUnit unit)
      throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock() {
    throw new java.lang.UnsupportedOperationException();
  }
  public void lockInterruptibly() throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/Backoff.java

package unam.fc.concurrent.practica4;

/*
 * Backoff.java
 *
 * Created on November 19, 2006, 5:43 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */


import java.util.Random;

/**
 * Adaptive exponential backoff class. Encapsulates back-off code
 * common to many locking classes.
 * @author Maurice Herlihy
 */
public class Backoff {
  final int minDelay, maxDelay;
  int limit;           // wait between limit and 2*limit
  final Random random;  // add randomness to wait
  
  /**
   * Prepare to pause for random duration.
   * @param min smallest back-off
   * @param max largest back-off
   */
  public Backoff(int min, int max) {
    if (max < min) {
      throw new IllegalArgumentException("max must be greater than min");
    }
    minDelay = min;
    maxDelay = min;
    limit = minDelay;
    random = new Random();
  }
  
  /**
   * Backoff for random duration.
   * @throws java.lang.InterruptedException 
   */
  public void backoff() throws InterruptedException {
    int delay = random.nextInt(limit);
    if (limit < maxDelay) { // double limit if less than max
      limit = 2 * limit;
    }
    Thread.sleep(delay);
  }
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/BackoffLock.java

package unam.fc.concurrent.practica4;

/*
 * BackoffLock.java
 *
 * Created on January 20, 2006, 11:02 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */


/**
 * Exponential backoff lock
 * @author Maurice Herlihy
 */
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.Condition;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
public class BackoffLock implements Lock {
  private Backoff backoff;
  private Random random = new Random();
  private AtomicBoolean state = new AtomicBoolean(false);  
  private static final int MIN_DELAY = 32;
  private static final int MAX_DELAY = 1024;
  public void lock() {
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY);
    while (true) {
      while (state.get()) {};   // spin
      if (!state.getAndSet(true)) { // try to acquire lock
        return;
      } else {          // backoff on failure
        try {
          backoff.backoff();
        } catch (InterruptedException ex) {
        }
      }
    }
  }  
  public void unlock() {
    state.set(false);
  }
  // Any class implementing Lock must provide these methods
  public Condition newCondition() {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock(long time,
      TimeUnit unit)
      throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock() {
    throw new java.lang.UnsupportedOperationException();
  }
  public void lockInterruptibly() throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/CLHLock.java

package unam.fc.concurrent.practica4;

/*
 * CLHLock.java
 *
 * Created on January 20, 2006, 11:35 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */


import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.Condition;
import java.lang.ThreadLocal;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Craig-Hagersten-Landin Lock
 * @author Maurice Herlihy
 */
public class CLHLock implements Lock {
  // most recent lock holder
  AtomicReference<QNode> tail;
  // thread-local variables
  ThreadLocal<QNode> myNode, myPred;
  
  /**
   * Constructor
   */
  public CLHLock() {
    tail = new AtomicReference<QNode>(new QNode());
    // initialize thread-local variables
    myNode = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return new QNode();
      }
    };
    myPred = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return null;
      }
    };
  }
  
  public void lock() {
    QNode qnode = myNode.get(); // use my node
    qnode.locked = true;        // announce start
    // Make me the new tail, and find my predecessor
    QNode pred = tail.getAndSet(qnode);
    myPred.set(pred);           // remember predecessor
    while (pred.locked) {}      // spin
  }
  public void unlock() {
    QNode qnode = myNode.get(); // use my node
    qnode.locked = false;       // announce finish
    myNode.set(myPred.get());   // reuse predecessor
  }
  
  // any class that implements lock must provide these methods
  public Condition newCondition() {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock(long time,
      TimeUnit unit)
      throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock() {
    throw new java.lang.UnsupportedOperationException();
  }
  public void lockInterruptibly() throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  
  static class QNode {  // Queue node inner class
    public boolean locked = false;
  }
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/CounterAtomic.java

package unam.fc.concurrent.practica4;

import java.util.concurrent.atomic.AtomicInteger;

/*
    Programa 1: Contador linealizable no bloqueante, utiliza
    primitivas: getAndIncrement y get
*/
public class CounterAtomic {
    private AtomicInteger count;
    public CounterAtomic() {
        this.count = new AtomicInteger(0);
    }
    public int increment() { //return the last value
        return count.getAndIncrement();
    }
    public int getValue() { //return the value
        return count.get();
    }
    

}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/MCSLock.java

package unam.fc.concurrent.practica4;

/*
 * MCSLock.java
 *
 * Created on January 20, 2006, 11:41 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */
    

import java.util.concurrent.locks.Lock;
import java.util.concurrent.atomic.AtomicReference;
import java.lang.ThreadLocal;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.TimeUnit;

/**
 * Mellor-Crummy Scott Lock
 * @author Maurice Herlihy
 */
public class MCSLock implements Lock {
  AtomicReference<QNode> queue;
  ThreadLocal<QNode> myNode;
  public MCSLock() {
    queue = new AtomicReference<QNode>(null);
    // initialize thread-local variable
    myNode = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return new QNode();
      }
    };
  }
  public void lock() {
    QNode qnode = myNode.get();
    QNode pred = queue.getAndSet(qnode);
    if (pred != null) {
      qnode.locked = true;
      pred.next = qnode;
      while (qnode.locked) {}     // spin
    }
  }
  public void unlock() {
    QNode qnode = myNode.get();
    if (qnode.next == null) {
      if (queue.compareAndSet(qnode, null))
        return;
      while (qnode.next == null) {} // spin
    }
    qnode.next.locked = false;
    qnode.next = null;
  }
  
  // any class implementing Lock must provide these methods
  public Condition newCondition() {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock(long time,
      TimeUnit unit)
      throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock() {
    throw new java.lang.UnsupportedOperationException();
  }
  public void lockInterruptibly() throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  
  static class QNode {     // Queue node inner class
    boolean locked = false;
    QNode   next = null;
  }
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/RunSpin.java

package unam.fc.concurrent.practica4;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import unam.fc.concurrent.practica4.*;

/*
Programa 2: Programa para medir el tiempo de: 
//      Lock lock = new TASLock();
//      Lock lock = new TTASLock();
//      Lock lock = new BackoffLock();
//      Lock lock = new MCSLock();
//      Lock lock = new ALock(numberThreads);
//      Lock lock = new ReentrantLock();
//      Lock lock = new CLHLock();
//      CounterAtomic (No necesita candados, ya es consistente)
*/

public class RunSpin {
    static int counter = 0;
    
    public static int increment() {
        return counter++;
    }
    
    
    private static int task(Lock lock) {
        try {
            lock.lock();
            increment();
        }finally {
            lock.unlock();      
        }
        return counter;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Future<Integer>> futures = new ArrayList<Future<Integer>>();
        int numberThreads = 11;
        ExecutorService executor = Executors.newFixedThreadPool(numberThreads);
//      CounterAtomic counter = new CounterAtomic(); // Descomentar para probar el contador atomico
//      Lock lock = new TASLock();
//      Lock lock = new TTASLock();
//      Lock lock = new BackoffLock();
        Lock lock = new MCSLock();
//      Lock lock = new ALock(numberThreads);
//      Lock lock = new ReentrantLock();
//      Lock lock = new CLHLock();
        
        long startTime = System.nanoTime();//Start time
        for(int i = 0; i < 400; i++) {
            futures.add(executor.submit(() -> task(lock))); 
//          futures.add(executor.submit(() -> counter.increment())); // Descomentar para probar el contador atomico
        }
        executor.shutdown();
        
        for (int i = 0; i < futures.size(); i++) {
            while(!futures.get(i).isDone()){}; // Comprobar que todas las tareas terminen
        }
        long endTime = System.nanoTime();//Finish time
        
        
        System.out.println("Program took " +
                (endTime - startTime)*0.000001 + "ms, Count result: " + counter) ; //En milisegundos
    }
    

}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/TASLock.java

package unam.fc.concurrent.practica4;

/*
 * TASLock.java
 *
 * Created on January 20, 2006, 10:48 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */


import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
/**
 * Test-and-set lock.
 * @author Maurice Herlihy
 */

public class TASLock implements Lock {
  AtomicBoolean state = new AtomicBoolean(false);
  public void lock() {
    while (state.getAndSet(true)) {} // spin
  }
  public void unlock() {
    state.set(false);
  }
  // Any class that implements Lock must provide these methods.
  public Condition newCondition() {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock(long time,
      TimeUnit unit)
      throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock() {
    throw new java.lang.UnsupportedOperationException();
  }
  public void lockInterruptibly() throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
}

Programas_P4/unam.fc.concurrent.practica4/src/unam/fc/concurrent/practica4/TTASLock.java

package unam.fc.concurrent.practica4;

/*
 * TTASLock.java
 *
 * Created on January 20, 2006, 10:59 PM
 *
 * From "Multiprocessor Synchronization and Concurrent Data Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */

/**
 * Test-and-test-and-set lock
 * @author Maurice Herlihy
 */
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
public class TTASLock implements Lock {
  AtomicBoolean state = new AtomicBoolean(false);
  public void lock() {
    while (true) {
      while (state.get()) {};  // spin
      if (!state.getAndSet(true))
        return;
    }
  }
  public void unlock() {
    state.set(false);
  }
  // Any class that implements Lock must provide these methods.
  public Condition newCondition() {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock(long time,
      TimeUnit unit)
      throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
  public boolean tryLock() {
    throw new java.lang.UnsupportedOperationException();
  }
  public void lockInterruptibly() throws InterruptedException {
    throw new java.lang.UnsupportedOperationException();
  }
}