Transcript Haddad-Javaspaces-Linda - Department of Electrical

JavaSpaces and
Linda Language
Ghaith Haddad
EEL6897
Fall 2007
Walkthrough




Parallel Programming Models
What is Linda?
Linda Model
•
•
•
•
Requirements
Advantages
Compare with MPI
Disadvantages
•
•
TSpaces
Javaspaces
Linda Implementations in Java







•
•
•


Requirements
Complexity
Diagram
In Depth
Example
Transactions
Distributed Events
GigaSpaces
Comparison
Research Projects
References
Demo
Parallel Programming Models



Set of software technologies to express parallel
algorithms and match applications with the
underlying parallel systems[2]
Areas include: applications, programming
languages, compilers, libraries, communications
systems, and parallel I/O
“Roughly” categorized into two kinds of systems:
• Shared-Memory
• Distributed-Memory

Examples: POSIX Threads, MPI, Charm++, Linda,
Oz (programming language)
What is Linda




“Linda is a coordination language for parallel and
distributed processing, providing a communication
mechanism based on a logically shared memory space
called tuple space.” [1]
Developed by David Gelernter and Nicholas Carriero at Yale
University.
Coordination Language: Model, not Grammar!
tuple space
• An implementation of the associative memory paradigm for
parallel/distributed computing
• Structured as a bag of tuples

Tuple Example: ("point", 12, 67),
• Three fields tuple
• 12 and 67 are the x and y coordinates of the point represented
by this tuple
• Similar to struct or object without methods
Tuple Space vs. Associative
Memory[7]


Allow memory items
to be selected by
reference to their
contents rather than
by an address
Every word in the
associative memory is
searched in parallel
against a key held in
the comparand
register which is the
same width as
memory
Linda Model Requirements

The original Linda model requires four
operations that individual workers perform
on the tuples and the tuplespace[3]
• in: atomically reads and removes -consumesa tuple from tuplespace
• rd: non-destructively reads a tuplespace
• out: produces a tuple, writing it into
tuplespace
• eval: creates new processes to evaluate
tuples, writing the result into tuplespace
Linda Model Requirements

The specification of the tuple to be
retrieved makes use of an
associative matching technique
• A subset of the fields in the tuple have their
values specified
• Used to locate a matching tuple in the tuple
space
• Example: in("point", ?x, ?y)is called an antituple
• anti-tuple: Any tuple with the same number
and type of fields
• Anti-tuple is used to
Linda Model Advantages[3]

More orthogonal
• Treats process coordination as a separate
activity from computation.
• Allows processes computing in different
languages and platforms to interoperate using
the same primitives

More general:
• Can subsume various levels of concurrency uni-processor, multi-threaded multiprocessor,
or networked- under a single model.
• Allows a multi-threaded Linda system to be
distributed across multiple computers, or viceversa, without change
Compare with MPI[3]
Message-passing models require
tightly-coupled processes sending
messages to each other in some
sequence or protocol
 Linda processes are decoupled from
other processes, communicating only
through the tuplespace

• a process need have no notion of other
processes except for the kinds of tuples
consumed or produced (data coupling).
Linda Model Disadvantages





The tuple space is unprotected since any
process can access any tuple in it[5]
No hierarchical organization of tuples,
therefore no sense of name scoping[5]
Decreased speed of operations in Linda
systems as compared to MPI systems[3]
At worst, inefficient, and, at best, subject
to unpredictable performance[1]
More disadvantages in[6]
Linda Implementations in Java
TSpaces
 JavaSpaces
 GigaSpaces
 Many Other Research Projects…

TSpaces





IBM’s implementation
"the common platform on which we build links to
all system and application services“[8]
Single server process running on the network
which makes use of a textual configurations file[1]
Transports tuples across the network using the
standard Java object serialization mechanisms
and TCP/IP sockets[1]
New commands can be added relatively easily[1]
TSpaces
JavaSpaces




Forms part of the Jini system, and so
makes extensive use of the Jini API[9]
Network support is provided by the Java
RMI (Remote Method Invocation)
protocol[10]
Distribution of classes to clients is handled
by the standard Internet hypertext
protocol (HTTP)[1]
Supports the basic Yale Linda operations
(the names differ from the original names
used by the Yale group, but essentially the
same functionality is provided)
JavaSpaces
JavaSpaces – Requirements[1]






a web (HTTP) server (a minimal one is provided
with the Jini/JavaSpaces release)
an RMI activation server (part of the standard
RMI software bundled with Java)
a Jini lookup service (alternatively the RMI
registry service can be used, but this is
discouraged as support for this option may be
discontinued by Sun in the future)
a Jini transaction manager
a JavaSpaces server
Applications are also required to run a security
manager, whether security checking is required
or not
JavaSpaces – Complexity[1]

A typical command line required to run a
JavaSpaces application is as follows
java -Djava.security.policy=
D:\JavaProgs\policy.all
-Doutrigger.spacename=JavaSpaces
-Dcom.sun.jini.lookup.groups=public
-Djava.rmi.server.codebase= http://host/spaceexamples-dl.jar
-cp D:\JavaProgs\spaceexamples.jar;D:\JavaProgs\classes
sun.applet.AppletViewer worker.html
JavaSpaces – Diagram[11]
JavaSpaces – In Depth[11]


All operations are invoked on an object that implements the
net.jini.space.JavaSpace interface.
A space stores entries, each of which is a collection of typed objects that
implements the Entry interface
import net.jini.core.entry.*;
public class MessageEntry
implements Entry {
public String content;
public MessageEntry() { }
public MessageEntry(String content) {
this.content = content;
}
public String toString() {
return "MessageContent: " + content;
}
}
Net.jini.space.JavaSpace
Interface[12]
EventRegistration notify(Entry tmpl, Transaction txn, RemoteEventListener
listener, long lease, MarshalledObject handback)
- When entries are written that match this template notify the given listener
with a RemoteEvent that includes the handback object.
Entry read(Entry tmpl, Transaction txn, long timeout)
- Read any matching entry from the space, blocking until one exists.
Entry readIfExists(Entry tmpl, Transaction txn, long timeout)
- Read any matching entry from the space, returning null if there is currently is
none.
Entry snapshot(Entry e)
- The process of serializing an entry for transmission to a JavaSpaces service
will be identical if the same entry is used twice.
Entry take(Entry tmpl, Transaction txn, long timeout)
- Take a matching entry from the space, waiting until one exists.
Entry takeIfExists(Entry tmpl, Transaction txn, long timeout)
- Take a matching entry from the space, returning null if there is currently is
none.
Lease write(Entry entry, Transaction txn, long lease)
- Write a new entry into the space.

http://java.sun.com/products/jini/2.1/doc/api/overview-summary.html
JavaSpaces – Example
import net.jini.space.JavaSpace;
public class SpaceClient {
public static void main(String argv[]) {
try {
System.out.println("Searching for a JavaSpace...");
Lookup finder = new Lookup(JavaSpace.class);
JavaSpace space = (JavaSpace) finder.getService();
System.out.println("A JavaSpace has been discovered.");
System.out.println("Writing a message into the spce...");
MessageEntry msg = new MessageEntry();
msg.content = "Hello there";
space.write(msg, null, 60*60*1000);
MessageEntry template = new MessageEntry();
System.out.println("Reading a message from the space...");
MessageEntry result = (MessageEntry) space.read(template,
null, Long.MAX_VALUE);
System.out.println(“Message read is: "+result.content);
} catch(Exception e) {e.printStackTrace();}
}
}
JavaSpaces – Transactions[11]



Package: net.jini.core.transaction
Provides basic atomic transactions that group
multiple operations across multiple JavaSpaces
services into a bundle that acts as a single atomic
operation
Either all modifications within the transactions
will be applied or none will
• regardless of whether the transaction spans one or more
operations or one or more JavaSpaces services


Transactions can span multiple spaces and
participants
A read(), write(), or take() operation that has a
null transaction acts as if it were in a committed
transaction that contained that operation.
JavaSpaces – Distributed Events[14]

Defined in the Jini Technology Core
Platform Specification
• Defines interfaces and requirements placed on
Jini which is capable of sending remote events
• The JavaSapces Specification overrides Jini
specification, it provides more details on how a
JavaSpace implements remote events

A remote event model allows an object in
one JVM to register as a listener to an
object on another JVM
• Example: a JavaSpace can send remote events
when an entry matching a specified template is
written into the space
GigaSpaces[13]

Developed as a commercial implementation of the
JavaSpaces specification, with some features added:
•
•
•
•
Operations on multiple tuples
Updating, deleting and counting tuples
Iterating over a set of tuples matching an anti-tuple
Distributed implementations of the Java Collections List, Set
and Map interfaces
• Message queuing mechanism

Efficient implementation of GigaSpaces
• Buffered writes
• Indexing of tuples (with or without intervention from the
application developer)
• Support for non-Java clients to access GigaSpaces through the
use of the SOAP protocol over HTTP
• Support for web servers to make use of GigaSpaces to share
session information (potentially even between separate web
servers)
Comparison[1]

TSpaces is unique in providing an extensible form of
matching through the ability to add new commands
Research projects

XMLSpaces[15]
• Designed to support the use of XML data in tuples
• Built over TSpaces
• Supports a distributed tuple space model

CO3PS[16]
• "Computation, Coordination and Composition with Petri
net Specifications“

Java-Linda[17]
• a student project at Yale University

eLinda[18]
• A model close to the standard Linda model
• Three Implementations



eLinda1: Fully distributed tuple space
eLinda2: Centralised tuple space, like JavaSpaces, TSpaces
eLinda3: Like in eLinda2, but with “broadcast” tuples
cached on each processing node
References


















[1] Linda implementations in Java for concurrent systems- G. C. Wells1;x, A. G. Chalmers and P. G.
Clayton – © 2003 John Wiley & Sons Ltd.
[2] http://en.wikipedia.org/wiki/Parallel_programming_model
[3] http://en.wikipedia.org/wiki/Linda_%28coordination_language%29
[4] G. Andrews, “ Concurrent Programming: Principles and Practice”, Benjamin/Cummings
Publishing Company, Inc., Redwood City, CA. 1991.
[5] Drucker, R.; Frank, A., "A C++/Linda model for distributed objects," Computer Systems and
Software Engineering, 1996., Proceedings of the Seventh Israeli Conference on , vol., no., pp.3037, 12-13 Jun 1996
[6] Ericsson-Zenith (1992). Process Interaction Models. Paris University
[7] http://www.gigaflop.demon.co.uk/comp/chapt2.htm
[8] IBM. The TSpaces vision. URL: http://www.almaden.ibm.com/cs/TSpaces/html/Vision.html
[9] Sun Microsystems. Jini connection technology. URL: http://www.sun.com/jini
[10] C. Austin and M. Pawlan. Advanced Programming for the Java 2 Platform. Addison-Wesley,
September 2000
[11] http://java.sun.com/developer/technicalArticles/tools/JavaSpaces/index.html
[12] http://java.sun.com/products/jini/2.1/doc/api/net/jini/space/JavaSpace.html
[13] GigaSpaces Technologies Ltd. Gigaspaces. URL: http://www.gigaspaces.com/index.htm , 2001
[14] P. Bishop and N. Warren, JavaSpaces in Practice, Addison-Wesley, 2002
[15] R. Tolksdorf and D. Glaubitz. Coordinating web-based systems with documents in XMLSpaces.
URL: http://flp.cs.tu-berlin.de/~tolk/xmlspaces/webxmlspaces.pdf 2001
[16] T. Holvoet. An Approach for Open Concurrent Software Development. PhD thesis, Department
of Computer Science, K.U.Leuven, December 1997
[17] A. Smith. Towards wide-area network Piranha: Implementing Java-Linda. URL:
http://www.cs.yale.edu/homes/asmith/cs690/cs690.html
[18] G.C. Wells. A Programmable Matching Engine for Application Development in Linda. PhD
thesis, University of Bristol, U.K., 2001
Demo…