Differences

This shows you the differences between two versions of the page.

--- calendar [2009/04/26 19:31] – franck
+++ calendar [2009/05/14 21:04] (current) – franck
@@ Line 17: / Line 17: @@
 //Communcations of the ACM//, 51(11):34-39, November 2008.
-<code java>
+A simple example of a concurrent program can be found
-/**
+[[example|here]].
- * An Assignment thread continuously assigns its private value to
- * a shared value.
- */
-public class Assignment extends Thread
-{
-    /** The value shared by all Assignment objects */
-    public static long sharedValue;
-    /** The private value of this Assignment object */
-    private long privateValue;
-    /**
-     * Creates an Assignment object with the given private value.
-     *
-     * @param privateValue the private value of the created Assignment object.
-     */
-    public Assignment(long privateValue)
-    {
-        this.privateValue = privateValue;
-    }
-    /**
-     * Continuously assigns the private value of this Assignment object
-     * to the shared value of all Assignment objects.
-     */
-    public void run()
-    {
-        while (true)
-        {
-            Assignment.sharedValue = this.privateValue;
-        }
-    }
-}
-</code>
-<code java>
-/**
- * A Print thread continuously prints the value of the value shared
- * by all Assignment objects.
- */
-public class Print extends Thread
-{
-    /**
-     * Continuously prints the value of the value shared
-     * by all Assignment objects.
-     */
-    public void run()
-    {
-        while (true)
-        {
-            System.out.println(Assignment.sharedValue);
-        }
-    }
-}
-</code>
-<code java>
-public class Client
-{
-    public static void main(String[] args)
-    {
-        Assignment zero = new Assignment(0);
-        Assignment max = new Assignment(Long.MAX_VALUE);
-        Print print = new Print();
-        zero.start();
-        max.start();
-        print.start();
-    }
-}
-</code>
 ===== March 10 =====
@@ Line 119: / Line 49: @@
 EWD 625.
-In an alternative solution to the dining philosophers, the
+An alternative solution to the dining philosophers can be found
-philosophers share the following.
+[[philosophers|here]].
-<code java>
-int state[];
-semaphore mutex;
-semaphore block[];
-</code>
-N is the number of philosophers.  Each philosopher has
-a unique number between 0 and N-1 and a philosopher's state
-state[i] is either THINKING, HUNGRY or EATING.
-<code java>
-PHILOSOPHER(int i)
-{
-   think;
-   P(mutex);
-   if (state[(i - 1) % N] != EATING && state[(i + 1) % N] != EATING)
-   {
-      state[i] = EATING;
-      V(block[i]);
-   }
-   else
-   {
-      state[i] = HUNGRY;
-   }
-   V(mutex);
-   P(block[i]);
-   eat;
-   P(mutex);
-   state[i] = THINKING;
-   if (state[(i - 1) % N] == HUNGRY && state[(i - 2) % N] != EATING)
-   {
-      V(block[(i - 1) % N]);
-   }
-   if (state[(i + 1) % N] == HUNGRY && state[(i + 2) % N] != EATING)
-   {
-      V(block[(i + 1) % N]);
-   }
-   V(mutex);
-}
-</code>
 ===== March 19 =====
@@ Line 189: / Line 80: @@
 If you come across another source that may be useful, please email it to the instructor.
-<code java>
+A simple example of a concurrent Java program can be found
-/**
+[[printer|here]].
- * A printer prints its name 1000 times.
- *
- * @author Franck van Breugel
- */
-public class Printer extends Thread
-{
-  /**
-   * Initializes this printer with the given name.
-   *
-   * @param name the name of this printer.
-   * @pre. name != null
-   */
-  public Printer(String name)
-  {
-    super(name);
-  }
-  /**
-   * Prints the name of this printer 1000 times.
-   */
-  public void run()
-  {
-    final int NUMBER = 1000;
-    for (int i = 0; i < NUMBER; i++)
-    {
-      System.out.print(this.getName());
-    }
-  }
-}
-</code>
-<code java>
-public class PrinterTest
-{
-  public static void main(String[] args)
-  {
-    new Printer("1").start();
-    new Printer("2").start();
-  }
-}
-</code>
-<code java>
-/**
- * A printer prints its name 1000 times.
- *
- * @author Franck van Breugel
- */
-public class Printer implements Runnable
-{
-  public void run()
-  {
-    final int NUMBER = 1000;
-    for (int i = 0; i < NUMBER; i++)
-    {
-      System.out.print(Thread.currentThread().getName());
-    }
-  }
-}
-</code>
-<code java>
-public class PrinterTest
-{
-  public static void main(String[] args)
-  {
-    Printer printer = new Printer();
-    new Thread(printer, "1").start();
-    new Thread(printer, "2").start();
-  }
-}
-</code>
 ===== March 31 =====
-A solution to the readers-writers problem using semaphores in Java.
+Implementations in Java of the reader-writers problem can be
-First, a Reader.
+found [[readers-writers|here]].
-<code java>
-package semaphore;
-import java.util.Random;
-import java.util.concurrent.Semaphore;
-/**
- * A reader.
- *
- * @author Franck van Breugel
- */
-public class Reader extends Thread
-{
-  private static int readers = 0;
-  private static final Semaphore mutex = new Semaphore(1);
-  /**
-   * Initializes this reader.
-   */
-  public Reader()
-  {
-    super();
-  }
-  /**
-   * Reads.
-   */
-  public void run()
-  {
-    try
-    {
-      Reader.mutex.acquire();
-      Reader.readers++;
-      if (Reader.readers == 1)
-      {
-        Writer.writer.acquire();
-      }
-      Reader.mutex.release();
-      // read
-      Reader.mutex.acquire();
-      Reader.readers--;
-      if (Reader.readers == 0)
-      {
-        Writer.writer.release();
-      }
-      Reader.mutex.release();
-    }
-    catch (InterruptedException e) {}
-  }
-}
-</code>
-Then, a Writer.
-<code java>
-package semaphore;
-import java.util.Random;
-import java.util.concurrent.Semaphore;
-/**
- * A writer.
- *
- * @author Franck van Breugel
- */
-public class Writer extends Thread
-{
-  public static final Semaphore writer = new Semaphore(1, true);
-  /**
-   * Initializes this writer.
-   */
-  public Writer()
-  {
-    super();
-  }
-  /**
-   * Writes.
-   */
-  public void run()
-  {
-    try
-    {
-      Writer.writer.acquire();
-      // write
-      Writer.writer.release();
-    }
-    catch (InterruptedException e) {}
-  }
-}
-</code>
-And finally an app.
-<code java>
-package semaphore;
-/**
- * This app creates a number of readers and writers.
- *
- * @author Franck van Breugel
- */
-public class ReadersWriters
-{
-  /**
-   * @param args[0] numbers of readers.
-   * @param args[1] number of writers.
-   */
-  public static void main(String[] args)
-  {
-    try
-    {
-      int readers = Integer.parseInt(args[0]);
-      int writers = Integer.parseInt(args[1]);
-      for (int i = 0; i < writers; i++)
-      {
-        new Writer().start();
-      }
-      for (int i = 0; i < readers; i++)
-      {
-        new Reader().start();
-      }
-    }
-    catch (Exception e)
-    {
-      System.out.println("Usage: java ReadersWriters < number of readers> <number of writers>");
-    }
-  }
-}
-</code>
-Below, we present another solution to the readers-writers problem.
-<code java>
-/**
- * This class represents a database.  There are many
- * competing threads wishing to read and write.  It is
- * acceptable to have multiple processes reading at the
- * same time, but if one thread is writing then no other
- * process may either read or write.
- */
-public class Database
-{
-  private int readers; // number of active readers
-  /**
-   * Initializes this database.
-   */
-  public Database()
-  {
-    this.readers = 0;
-  }
-  /**
-   * Read from this database.
-   */
-  public void read(int number)
-  {
-    synchronized(this)
-    {
-      this.readers++;
-    }
-    // read
-    synchronized(this)
-    {
-      this.readers--;
-      if (this.readers == 0)
-      {
-        this.notifyAll();
-      }
-    }
-  }
-  /**
-   * Writes to this database.
-   */
-  public synchronized void write(int number)
-  {
-    while (this.readers != 0)
-    {
-      try
-      {
-        this.wait();
-      }
-      catch (InterruptedException e) {}
-    }
-    // write
-    this.notifyAll();
-  }
-}
-</code>
 ===== April 2 =====
@@ Line 476: / Line 108: @@
 [[http://www.cs.kent.ac.uk/projects/ofa/jcsp/|Communicating Sequential Processes for Java]]
-<code java>
+Examples of JCSP can be found [[csp|here]].
-public class Process implements CSProcess
-{
-  private ChannelOutput verhoog;
-  private ChannelOutput prolaag;
-  public Process(ChannelOutput verhoog, ChannelOutput prolaag)
-  {
-    super();
-    this.verhoog = verhoog;
-    this.prolaag = prolaag;
-  }
-  public void run()
-  {
-    this.prolaag.write(null);
-    // critical section
-    this.verhoog.write(null);
-  }
-}
-</code>
-<code java>
-public class Semaphore implements CSProcess
-{
-  private int value;
-  private AltingChannelInput verhoog;
-  private AltingChannelInput prolaag;
-  public Semaphore(int value, AltingChannelInput verhoog, AltingChannelInput prolaag)
-  {
-    super();
-    this.value = value;
-    this.verhoog = verhoog;
-    this.prolaag = prolaag;
-  }
-  public void run()
-  {
-    final int ALTERNATIVES = 2;
-    final int V = 0;
-    final int P = 1;
-    final Guard[] guard = new Guard[ALTERNATIVES];
-    guard[V] = this.verhoog;
-    guard[P] = this.prolaag;
-    final boolean[] precondition = new boolean[ALTERNATIVES];
-    precondition[V] = true;
-    final Alternative alternative = new Alternative(guard);
-    while (true)
-    {
-      precondition[P] = this.value > 0;
-      switch (alternative.select(precondition))
-      {
-        case V:
-          this.verhoog.read();
-          this.value++;
-          break;
-        case P:
-          this.prolaag.read();
-          this.value--;
-          break;
-      }
-    }
-  }
-}
-</code>
-<code java>
-public class Main
-{
-  public static void main(String[] args)
-  {
-    Any2OneChannel verhoog = Channel.any2one();
-    Any2OneChannel prolaag = Channel.any2one();
-    Semaphore semaphore = new Semaphore(1, verhoog.in(), prolaag.in());
-    Process one = new Process(verhoog.out(), prolaag.out());
-    Process two = new Process(verhoog.out(), prolaag.out());
-    CSProcess[] process = { semaphore, one, two };
-    Parallel parallel = new Parallel(process);
-    parallel.run();
-  }
-}
-</code>
 ===== April 16 =====
-Concurrent implementations of the following interface.
+Four concurrent implementations of a stack can be found
+[[stack|here]].
-<code java>
-/**
- * A Stack.
- */
-public interface Stack<T>
-{
-  /**
-   * Removes the top element from this stack and returns it.
-   *
-   * @return the top element of this stack.
-   * @throw Exception if this stack is empty.
-   */
-  public T pop() throws Exception;
-  /**
-   * Pushes the given element onto this stack.
-   *
-   * @param the element to be pushed onto this stack.
-   */
-  public void push(T element);
-}
-</code>
-In each implementation of the above interface we will exploit the class Node.
-<code java>
-/**
- * A node of a linked list.
- */
-public class Node<T>
-{
-  private T element;
-  private Node<T> next;
-  /**
-   * Initializes this node with the given element and next node.
-   *
-   * @param element the element stored in the node.
-   * @pre. element != null
-   * @param next the next node in the list.
-   */
-  public Node(T element, Node<T> next)
-  {
-    this.element = element;
-    this.next = next;
-  }
-  /**
-   * Returns the element of this node.
-   *
-   * @return the element of this node.
-   */
-  public T getElement()
-  {
-    return this.element;
-  }
-  /**
-   * Returns the next node.
-   *
-   * @return the next node.
-   */
-  public Node<T> getNext()
-  {
-    return this.next;
-  }
-  /**
-   * Sets the next node to the given node.
-   *
-   * @param node the new next node.
-   */
-  public void setNext(Node<T> next)
-  {
-    this.next = next;
-  }
-}
-</code>
-In the first implementation, we simply lock the whole stack when we pop or push an element.
-<code java>
-public class First<T> implements Stack<T>
-{
-  private Node<T> top;
-  public First()
-  {
-    this.top = null;
-  }
-  public synchronized T pop() throws Exception
-  {
-    if (this.top == null)
-    {
-      throw new Exception();
-    }
-    else
-    {
-      T element = this.top.getElement();
-      this.top = this.top.getNext();
-      return element;
-    }
-  }
-  public synchronized void push(T element)
-  {
-    this.top = new Node<T>(element, this.top);
-  }
-}
-</code>
-In the second implementation, we lock the top node when we pop or push an element.
-<code java>
-public class Second<T> implements Stack<T>
-{
-  private Node<T> top;
-  public Second()
-  {
-    this.top = null;
-  }
-  public T pop() throws Exception
-  {
-    Node<T> node;
-    synchronized (this.top)
-    {
-      if (this.top == null)
-      {
-        throw new Exception();
-      }
-      else
-      {
-        node = this.top;
-        this.top = this.top.getNext();
-      }
-    }
-    return node.getElement();
-  }
-  public void push(T element)
-  {
-    Node<T> node = new Node<T>(element, null);
-    synchronized (this.top)
-    {
-       node.setNext(this.top);
-       this.top = node;
-    }
-  }
-}
-</code>
-The third implementation does not use any locking. We exploit the class AtomicReference.
-<code java>
-import java.util.concurrent.atomic.*;
-public class Third<T> implements Stack<T>
-{
-  private volatile AtomicReference<Node<T>> top;
-  public Third()
-  {
-    this.top = new AtomicReference<Node<T>>();
-  }
-  public T pop() throws Exception
-  {
-    Node<T> node;
-    do
-    {
-      node = this.top.get();
-      if (node == null)
-      {
-        throw new Exception();
-      }
-    }
-    while (!this.top.compareAndSet(node, node.getNext()));
-    return node.getElement();
-  }
-  public void push(T element)
-  {
-    Node<T> node = new Node<T>(element, null);
-    do
-    {
-      node.setNext(this.top.get());
-    }
-    while (!this.top.compareAndSet(node.getNext(), node));
-  }
-}
-</code>
-Also the fourth implementation does not use any locking. This time we exploit the class AtomicReferenceFieldUpdater.
-<code java>
-import java.util.concurrent.atomic.*;
-public class Fourth<T> implements Stack<T>
-{
-  private volatile Node<T> top;
-  private static final AtomicReferenceFieldUpdater<Fourth<T>, Node<T>> topUpdater
-    = AtomicReferenceFieldUpdater.newUpdater(Fourth.class, Node.class, "top");
-  public Fourth()
-  {
-    this.top = null;
-  }
-  public T pop() throws Exception
-  {
-    Node<T> node;
-    do
-    {
-      node = this.top;
-      if (node == null)
-      {
-        throw new Exception();
-      }
-    }
-    while (Fourth.topUpdater.compareAndSet(this, node, node.getNext()));
-    return node.getElement();
-  }
-  public void push(T element)
-  {
-    Node node = new Node<T>(element, null);
-    do
-    {
-        node.setNext(this.top);
-    }
-    while (Fourth.topUpdater.compareAndSet(this, node.getNext(), node));
-  }
-}
-</code>
 ===== April 21 =====
@@ Line 833: / Line 144: @@
 Willem Visser, Klaus Havelund, Guillaume Brat, SeungJoon Park and Flavio Lerda. [[http://dx.doi.org/10.1023/A:1022920129859|Model Checking Programs]]. //Automated Software Engineering//, 10(2): 203-232, April 2003.
-More information about Java PathFinder can be found
-[[jpf:start|here]].
 ===== May 7 =====
+More information about Java PathFinder can be found
+[[jpf:start|here]].
 ===== May 12 =====
+Information about handling native code with Java PathFinder can be found
+[[jpf-native:start|here]].
 ===== May 14 =====