Here is the second chapter excerpt from
JavaSpaces TM
Principles, Patterns, and Practice, recently published by Addison-Wesley as part of
the Jini Technology
Series from Sun Microsystems, Inc. (See Chapter 1 Introduction, for
the first chapter excerpt from this book.
Note from the authors:
JavaSpacesTM is a powerful
JiniTM service that provides a high-level tool
for creating collaborative and distributed applications in Java.
In the book JavaSpaces Principles, Patterns, and Practice, we cover some
simple but powerful frameworks for JavaSpaces applications, including the
command pattern. Using the command pattern, it's possible to implement a
powerful compute server,
consisting of a collection of worker processes each of which repeatedly picks up a task
from the space (that was put there by a master process), calls its execute
method to compute the task, and moves on to the next task. The workers
typically write the results of their task computations back to the space, so the master
process can pick them up.
Chapter 11, excerpted here, reviews the command pattern (which is introduced in Chapter 6 of
the book), and uses it to build a compute server. Then, we have some fun building upon that compute server
to construct
an application that breaks encrypted passwords. Eric Freeman and Susanne Hupfer
You can order
this book from Amazon.com
A Parallel Application
In pioneer days, they used oxen for heavy pulling, and when one ox couldn't
budge a log they didn't try to grow a larger ox. We shouldn't be trying for bigger
computers, but for more systems of computers.
-- Grace Hopper
This chapter builds on the compute server we developed in Chapter 6 and
explores its use in two directions: First, we are going to extend our simple
compute server to make use of a couple of the technologies we covered in the
last few chapters, namely transactions and leases. Then, we are going to
develop a parallel application on top of the server that will allow us to
explore some of the more subtle issues that arise when developing space-based
parallel applications. These issues range from keeping the workers busy with
tasks (yet not overwhelming the space with too many tasks), to the
computation/communication ratio, to cleaning up the space after we use it.
The application we are going to develop is a fun one: breaking password encryption.
Let's get started.
11.1 The Compute Server
Before building our application we are first going to rework the simple compute server
we developed in Chapter 6. At this point you might want to return to that chapter
and quickly review the compute server code.
11.1.1 The Command
Interface Revisited
Recall that all tasks computed by the compute server must implement the
Command
interface, which contains one method, execute
.
To submit a task to a compute server, we create a task entry that implements
the command interface and drop it into the server's bag of tasks. A worker in
the compute server eventually removes this task and invokes its execute
method. The execute
method computes a task and then optionally
returns an entry, which the worker will write back into the space.
Below we present the Command
interface, with a couple of small changes:
public interface Command extends Entry {
public Entry execute(JavaSpace space);
}
First, note that the execute
method now takes a space as a parameter,
which allows tasks to make use of the space within their code. For instance, a
task may want to obtain additional data from the space, return intermediate results
to the space, or communicate with other tasks.
We've also changed the return type of execute
to make it more general.
Rather than returning an entry type of ResultEntry
, we return an
Entry
so that tasks no longer have to subclass the
ResultEntry
class.
11.1.2 The Task
Entry
While we've gotten rid of ResultEntry
, we still have a base
TaskEntry
class, which we first introduced in Chapter 6.
Here is our updated TaskEntry
:
public class TaskEntry implements Command {
public Entry execute(JavaSpace space) {
throw new RuntimeException(
"TaskEntry.execute() not implemented");
}
public long resultLeaseTime() {
return 1000 * 10 * 60; // 10 minutes
}
}
The changes to this class are fairly minimal. The execute
method has
been updated to reflect the new space parameter specified in the
Command
interface, and also to return an Entry
rather than a ResultEntry
. The execute
still throws a runtime exception, thus forcing subclasses to implement the
method. Recall the reason we gave in Section 6.2.1 for defining
TaskEntry
in this manner (rather than defining an abstract class):
It's so the compute server can create a TaskEntry
template and
remove any task from a space. If TaskEntry
where declared
abstract
, then we couldn't use it to instantiate a template.
We've also added one new method, resultLeaseTime
, that is used
to supply a lease time for the result entries that are returned from the
execute
method (and then written back into the space by the
worker). The implementor of the TaskEntry
can override this
method to specify a time other than the default for the results of the
computation to remain in the space.
Now that we've gotten these minor differences out of the way, let's move
on to more interesting changes, starting by reworking the generic worker.
11.1.3 The Generic Worker
To review, the basic operation of the worker is straightforward:
In a loop we take a task entry from the space and invoke its
execute
method. If the method returns an entry then we write it
back into the space (for the master to pick up). We then return to the top of
the loop and begin again.
Our reworked version includes a few enhancements. Here is the code for the
generic worker's run
method:
public void run() {
Entry taskTmpl = null;
try {
taskTmpl =
space.snapshot(new TaskEntry());
} catch (RemoteException e) {
throw new RuntimeException(
"Can't obtain a snapshot");
}
while (true) {
System.out.println("getting task");
Transaction txn = getTransaction();
if (txn == null) {
throw new RuntimeException(
"Can't obtain a transaction");
}
try {
TaskEntry task = (TaskEntry)
space.take(
taskTmpl, txn, Long.MAX_VALUE);
Entry result = task.execute(
space);
if (result != null) {
space.write(
result, txn,
task.resultLeaseTime());
}
txn.commit();
} catch (RemoteException e) {
e.printStackTrace();
} catch (TransactionException e) {
e.printStackTrace();
} catch (UnusableEntryException e) {
e.printStackTrace();
} catch (InterruptedException e) {
try {
txn.abort();
} catch(Exception ex) {
// RemoteException or
//BadTransactionException
// lease expiration will
//take care of the
// transaction
}
System.out.println("
Task cancelled");
}
}
}
The first enhancement is the use of snapshot
. Since we use the
same task template over and over, we go ahead and create a snapshotted version
of the template to avoid re-serialization on every take
operation.
We have also improved the generic worker so that it takes into account
the possibility of partial failure. Let's first step back and examine one
of several scenarios that can occur with partial failure: consider the
case where the generic worker removes a task, starts computing it, and
then partial failure occurs. As a result, the task entry will be lost,
which may have a detrimental effect on a parallel computation.
To make our compute server robust in the face of partial failure, we
use transactions. To create a transaction we make use of the
method getTransaction
, which is shown below:
public Transaction getTransaction() {
TransactionManager mgr =
TransactionManagerAccessor.getManager();
try {
long leaseTime = 1000 * 10 * 60;
//ten minutes
Transaction.Created created =
TransactionFactory.create(
mgr, leaseTime);
return created.transaction;
} catch(RemoteException e) {
e.printStackTrace();
return null;
} catch(LeaseDeniedException e) {
e.printStackTrace();
return null;
}
}
Here we first obtain access to a transaction manager, which is done through
our TransactionManagerAccessor
. We then call
TransactionFactory.create
, passing it a transaction manager and a lease
time of ten minutes. This lease time has the following effect on the task
entry: If a task is not computed within ten minutes then the transaction
is aborted by the transaction manager and the
TaskEntry
is returned to the space (note that our code does
nothing to stop the execute
method if it does not finish in that
time period; we leave this as an exercise to the reader).
If an exception occurs creating the transaction, then the exception is
printed and null
is returned from the call to
getTransaction
; otherwise we return the transaction.
Returning to the generic worker's run
method, when the call to
getTransaction
returns, if a transaction hasn't been created we
throw a runtime exception. Otherwise, we call take
(passing it our snapshotted template and transaction) and wait indefinitely
until it returns a task entry. Once a task entry is returned we call
its execute
method and assign the return value to the local
variable result
. If result
is non-null
,
then we write result
back into the space under the transaction,
with a lease time obtained from calling resultLeaseTime
. By
overriding the resultLeaseTime
method, the designer of a
TaskEntry
can specify how long a result entry should live on a
per-task basis. Finally, once the result is written back into the space,
we commit the transaction.
If any exceptions occur along the way we display the exception and then
continue at the top of the loop. If however, we receive an
InterruptedException
, then we explicitly abort the transaction,
assuming the user has interrupted the computation.
11.1.4 A Generic Master
We are also going to make a few updates to our GenericMaster
class. Recall that our previous version from Chapter 6
called the generateTasks
method to generate a set of tasks and
then called collectResults
to collect any results. To create
your own master process you subclass these two methods and supply the code
to generate tasks and collect results.
In practice it is often the case that generating tasks and collecting
results are two activities that can occur concurrently. Many parallel
(as well as distributed) applications generate small sets of tasks in
phases over time and collect the results from each phase as they become
available. The results from one phase may, in fact, influence the set of
tasks that are generated in the next. It may also be the case that a master
needs to generate so many tasks that the space would be overwhelmed (or
at least resource constrained) in a shared environment; in such a case
the master needs to dole out tasks over time, as previous tasks are
completed, and not all at once. That will be the case with our application,
and we will talk about a technique called watermarking that allows us to
keep workers busy, while minimizing the impact on the space.
Here is the new code for our updated GenericMaster
, which
is designed to allow the generateTasks
and
collectResults
methods to run concurrently:
public abstract class
GenericMaster extends Applet {
protected JavaSpace space;
public void init() {
space =
SpaceAccessor.getSpace();
GenerateThread gThread =
new GenerateThread();
gThread.start();
CollectThread cThread =
new CollectThread();
cThread.start();
}
protected abstract void generateTasks(
);
protected abstract void collectResults(
);
//... writeTask and takeTask
//methods here
}
To allow both methods to work concurrently, we've made a simple alteration
to the GenericMaster
class; rather than successively calling
the two methods, it instead creates two new threads: one that calls
generateTasks
and the other that calls collectResults
.
That concludes our changes to the compute server.
11.2 The Crypt Application
We are now going to develop a parallel application on top of our compute
server. Our application is an exercise in applied cryptography, which
is another way of saying we are going to write an application that
breaks encrypted passwords.
11.2.1 Background
A common method of encrypting passwords, particularly in UNIX
systems, is the use of a one-way encryption algorithm, which takes
the user's password as input and returns the user's encrypted password.
For instance, a password of "secret
" may result in
the output "BgU8DFSLhhz6Q
." One-way functions that work
well for encryption have the property that, given the encrypted version of
a password, it is difficult to compute the inverse of the function to
produce the original password (which makes it hard to guess passwords
from their encrypted form).
The parallel application we are going to be developing will break
passwords through the brute force technique of trying every possible
combination of ASCII characters that make up a password. This
technique works as follows: given a one-way function, let's
call it crypt
, and an encrypted password e
,
we can iterate through every possible ASCII password p
and compute crypt(p)
. We then compare the result of
crypt(p)
with e
, and if the two are equal, then
p
is the password. If not, then we keep trying.
It isn't difficult to enumerate every possible ASCII password; it can be
done by generating a sequence like this:
aaaaaaaa
aaaaaaab
aaaaaaac
.
.
.
zzzzzzzz
with the caveat that characters other than a
-z
can be used for passwords (in general, all
95 printable ASCII characters can be used).
There are, of course, other methods of trying to break passwords. The
most common method is to use a dictionary of words that are then
encrypted and checked against the stored encrypted password. This
technique often works well in practice, because users often choose
common words as passwords. However, it isn't foolproof, because users
may choose passwords that aren't in dictionaries.
Exploring the space of every possible password--not just dictionary
words--can be a very compute-intensive problem (if not intractable
in some cases). Because of this we are going to implement a scaled-down
application that breaks passwords of four characters or less. Even with
four characters, the space of possible passwords would take a standalone
Java application on the order of several hours to compute, which makes a
nice size for our parallel experiments.
Our encrypted passwords are based on the UNIX password encryption
scheme. The garden-variety UNIX algorithm normally takes a password
of eight characters that is prepended by two characters of "salt"--an
arbitrary sequence that is prepended to prohibit simple dictionary
schemes of password breaking. So to encrypt "secret," UNIX
adds two random characters, say "aw" and then encrypts
"awsecret" via a one-way function.
The UNIX crypt
one-way function is provided in a class
called JCrypt
, written by John F. Dumas for the Java
platform, and can be found in the source code for this book. The
details of the class are not important, with the exception of
the crypt
method that we make use of in our code. The
signature for this method is as follows:
public static String crypt(
byte[] password);
The crypt
method is a static method that takes a
password (already prepended with salt) in the form of a byte array
and returns an encrypted version of the password in the form of
a String
.
With this knowledge under our belt, let's design and build the
application. Our application is going to follow the standard
replicated-worker pattern: Given an encrypted password, a master
process enumerates all possible passwords and generates tasks for
the workers to verify whether or not the possible passwords match
the encrypted version. The workers pick up the tasks and do the
verification by the technique mentioned above--they first encrypt
the potential password and then compare it against the encrypted
password. If the two match we've found the password.
11.2.2 The Generic Worker and Crypt Task
The task entry is the heart of the compute server computation--tasks
are written into the space for the GenericWorker
to compute. Because we make use of the command pattern, the
GenericWorker
simply calls each task's execute
method. Even if a worker has never seen a specific subclass of a task
entry before, the space and its underlying RMI transport take care of
the details of shipping the executable behavior to the worker.
Our workers look for tasks of type TaskEntry
. Here we
extend the task entry to create a new task: the CryptTask
.
public class CryptTask extends TaskEntry {
public Integer tries;
public byte[] word;
public String encrypted;
public CryptTask() {
}
public CryptTask(int tries, byte[
] word, String encrypted) {
this.tries = new Integer(tries);
this.word = word;
this.encrypted = encrypted;
}
public Entry execute(JavaSpace space) {
int num = tries.intValue();
System.out.println(
"Trying " +
getPrintableWord(word));
for (int i = 0; i < num; i++) {
if (encrypted.equals(
JCrypt.crypt(word))) {
CryptResult result =
new CryptResult(word);
return result;
}
nextWord(word);
}
CryptResult result =
new CryptResult(null);
return result;
}
}
Let's step through the CryptTask
code. A crypt task holds
three pieces of information: tries
, an integer that
specifies the number of potential passwords each task should
enumerate and try as a possible match against the encrypted
version; word
, a byte array that holds the word with
which to begin the enumeration; and encrypted
, a string
that holds the encrypted password we are trying to break. So each task
is given a starting point (word
) and a number of
enumerations (tries
), to attempt matching words against
the encrypted password (encrypted
). All three values can be
initialized in a crypt task by calling the supplied convenience
constructor.
Next we have the crypt task's execute
method: we
first convert tries
from its wrapper class into a
primitive integer
that is assigned to
num
. The rest of execute
consists of one main
loop that iterates for num
times. Each time through the
loop, we encrypt a word using the JCrypt
class's crypt
method and then compare it against
the encrypted
word. If the two are equal, then we've
broken the password, and we create a CryptResult
object and return it to the Worker
process. The
CryptResult
object is simply an entry that holds the broken
password in the form of a byte array.
If the two are not equal, then we call
nextWord
, which is shown below:
static void nextWord(byte[] word) {
int pos = 5;
for (;;) {
word[pos]++;
if ((word[pos] & 0x80) != 0) {
word[pos--] = (byte) '!';
} else {
break;
}
}
}
The nextWord
method is a static method (as we will see it is
also used by the CryptMaster
) that takes a word in the
form of a byte array and alters the array so that it is set to
the next word in the ASCII sequence. For instance, if we start
at the word "aaaa" and prepend it with the salt
sequence "aw" then the word "awaaaa" looks like
this if we run it through nextWord
a few times:
awaaaa
awaaab
awaaac
.
.
.
awaaa!
awaaba
awaabb
.
.
.
awaa!!
awabaa
awabab
.
.
.
If we take a look at the code for nextWord,
we see that
the method first increments the right-most character. If this character
goes beyond the end of the ASCII sequence (which is the hexadecimal
number 0x80
) then the character is set to
!
(which is the first printable character in the ASCII set),
and the neighboring character to the left is incremented by one.
The test for 0x80
is then repeated on that character;
if equal, the character is also set to !
and the character
to the left of it is incremented. And so on.
If CryptTask
iterates through num
possible
passwords without finding a match, then it falls out of the loop
and returns a result entry that has its word
field set to null
(the result entry consists of one field,
word
, that is used to hold the password when it is found).
To recap, the CryptTask
has instructions to check a fixed
number of potential passwords against the encrypted password. If a
password is found, it is returned in a result entry, but if no password
is found, then a result entry is still returned with its
word
field set to null
(we will see why shortly).
11.2.3 The Crypt Master
Now that we've seen the worker code in detail, let's take a look at the CryptMaster
, which drives the entire
computation. Let's first examine the user interface of the CryptMaster
(shown in Figure 11.1), which will give
us a sense of its operation before we dive into the code details.

Figure 11.1 - The CryptMaster Interface 11.1
Once started, the CryptMaster
encrypts our password and displays it just below the password text entry field.
The compute server will now be asked to figure out what our original password was, given the encrypted version.
To do this, the crypt master begins generating tasks and collecting results until the workers break the password.
During the computation, the right side of the interface provides an information display that shows the total number
of words that have been checked against the encrypted password, the average number of words being computed per minute
by all workers, and the number of tasks in the space waiting to be computed (this is called the "water level," which
we will discuss shortly along with the "high mark" and "low mark" configuration information that appears in the interface).
Below is the skeleton of the CryptMaster
code:
public class CryptMaster extends GenericMaster
implements ActionListener
{
// ... GUI declarations here
private int lowmark;
private int highmark;
private int triesPerTask;
private int waterlevel = 0;
private boolean start = false;
private long startTime;
private String salt;
private String unencrypted;
public void init() {
super.init();
// ... GUI setup here
}
public void actionPerformed(
ActionEvent event) {
if (start) {
return;
}
String msg = null;
salt = saltTextField.getText();
if (salt.equals("")) {
msg = "Supply a salt value";
}
unencrypted =
wordTextField.getText();
if (unencrypted.equals("")) {
msg =
"Supply a word to encrypt";
}
if (unencrypted.length(
) != 4) {
msg =
"Supply a word of" +
"four characters";
}
// JCrypt expects 8 chars
unencrypted = "!!!!" + unencrypted;
try {
triesPerTask = Integer.parseInt(
triesTextField.getText());
} catch (NumberFormatException e) {
msg = "Enter an integer value in
\"Tries per Task\".";
}
try {
highmark = Integer.parseInt(
highTextField.getText());
} catch (NumberFormatException e) {
msg = "Enter an integer value in
\"High Mark\".";
}
try {
lowmark = Integer.parseInt(
lowTextField.getText());
} catch (NumberFormatException e) {
msg = "Enter an integer value in
\"Low Mark\".";
}
if (msg == null) {
start = true;
} else {
showStatus(msg);
}
}
// ... generateTasks() goes here
// ... collectResults() goes here
// ... other helper methods go here
}
CryptMaster
subclasses our GenericMaster
class; this basic skeleton shows where fields are declared
and initialized and where the user interface is set up.
The notable part of this code is the actionPerformed
method, which is called when the "Start" button is clicked.
This method first checks to see if the start
field has already been set to true
(indicating that this method has
been called before), and if so simply returns. Otherwise we check the value of the fields in the user interface
to make sure they contain appropriate values. If they do, we set the value of several fields, including the start
field; otherwise we display an error message in the status area of the applet.
The CryptMaster
interface works as follows: we enter salt and a password (in the first two text entries in the
upper left corner of the interface), and then optionally tweak the parameters below the password text entry,
such as the "tries per task" parameter, which controls how many words each task checks against the encrypted
password. We then click on the "Start" button, which starts the application.
11.2.4 Generating Tasks
Now that our user interface code is out of the way, let's look at how CryptMaster
generates and collects tasks.
Recall that GenericMaster
(which CryptMaster
subclasses) creates two threads, one that calls
generateTasks
and
another that calls collectResults
. Here is the code for
generateTasks
:
public void generateTasks() {
while (!start) {
try {
Thread.sleep(250);
} catch (
InterruptedException e) {
return; // thread told to stop
}
}
startTime = System.currentTimeMillis();
String encrypted = JCrypt.crypt(
salt, unencrypted);
encryptedTextField.setText(
encrypted);
byte[] testWord = getFirstWord();
for (;;) {
if (testWord[1] !=
salt.charAt(1)) {
return;
}
CryptTask task =
new CryptTask(
triesPerTask, testWord,
encrypted);
System.out.println("
Writing task");
writeTask(task);
for (int i = 0; i < triesPerTask;
i++) {
CryptTask.nextWord(testWord);
}
}
}
The generateTasks
method begins by waiting for the start
field to become true
. As we saw in the last section, this field is set to true
when the user clicks on the "Start" button.
Once start
is set to true
, the generateTasks
method sets the startTime
field to the current time and the
encrypted
field to the encrypted version of the password entered in the text entry field (prepended
with salt); then the interface is updated to display the encrypted version. Next the method getFirstWord
is called to obtain the first ASCII sequence (see the complete source code for the method definition),
which gets assigned to the field testWord
; this will be the starting point for enumerating all potential
password matches.
Then we enter the main loop of generateTasks
, which first tests to see if we are at the last word of the ASCII
sequence. Recall from our explanation of the CryptTask's
nextWord
method that the sequence is enumerated by
"incrementing" through the positions of the word from right to left. Here we check the first character of the
password's salt. When this character is no longer the salt character (in other words, when it, too, has been
incremented) then we know we've exhausted all password possibilities.
Next we create a CryptTask
by calling its convenience constructor, supplying the number of tries per task, the
encrypted version of the password, and the starting word to begin testing. We then write the crypt task to the space.
Next we need to update testWord
, so that the next task will begin at the word which is triesPerTask
away from this
task's starting word. To do this we simply call the nextWord
method triesPerTask
times (a very fast operation
compared to doing the password check of each possibility).
That is the basic version of the generateTasks
method, which simply enumerates all possible values and partitions
them into a number of tasks that need to be checked by workers. The task generation is problematic, however, in
that it can generate a very large number of tasks before the password is discovered. In fact, there are over 81 million
possible passwords of length four or less. If we choose a "tries per task" of 1,000 then the master will (in the worst
case) generate over 80,000 tasks. This could have a serious impact on the resources of the space. Let's look at one
way to improve this code.
How many passwords are possible? For a four-character password we need to check just over 81 million potential
passwords. This number comes from the following computation: a password has four character "slots" to be filled,
each of which can hold one of 95 possible ASCII characters (we will assume that passwords of 3 characters or less
are filled with the space character at the end). Because the choice of each slot is independent of the others we obtain
all possibilities by computing 95*95*95*95 = 95^4 = 81,450,625.
How many eight-character passwords are possible?
11.2.5 Improving Space Usage with Watermarking
One observation we can make is that the space needs to hold only enough tasks to keep workers busy. A technique
for keeping a space full enough, yet not too full, is called watermarking. The word watermarking
comes from the two marks often found on shorelines marking high and low tide. Here we choose a high point and
low point, meaning the upper and lower limits on the number of entries we'd like in the space. We fill the space with
entries until it reaches the high mark, and then wait until the number of entries falls below the low mark, at which
point we start filling it with tasks again.
As an illustration of how watermarking works, assume you have a set of ten workers at your disposal. You might
want to set the high and low marks to, say, twelve and twenty respectively. That way you always have at least
enough tasks for all workers but at most twenty entries in the space. Tuning watermarks is more of an art than a
science. In our case we are going to assume that the high and low marks are set when the computation begins and
never change. Often the number of workers varies over time, and the high and low values could be modified
adaptively - but we won't get that sophisticated here.
Let's apply the watermarking principle to our generateTasks
code. Here is a new version of the generateTask's
main
loop, updated to use watermarking:
for (;;) {
waitForLowWaterMark(lowmark);
while (waterlevel < highmark) {
if (testWord[1] !=
salt.charAt(1)) {
return;
}
CryptTask task =
new CryptTask(triesPerTask,
testWord, encrypted);
System.out.println("Writing task");
writeTask(task);
changeWaterLevel(1);
for (int i =
0; i < triesPerTask; i++) {
CryptTask.nextWord(
testWord);
}
}
}
And here are the definitions of a couple helper methods that are used:
synchronized void waitForLowWaterMark(
int level) {
while (waterlevel > level) {
try {
wait();
} catch (InterruptedException e) {
; // continue
}
}
}
private synchronized void changeWaterLevel(
int delta) {
waterlevel += delta;
waterMarkLabel.setText(
"Waterlevel is at " +
waterlevel + " tasks");
notifyAll();
}
Our first addition to the main loop is the call to waitForLowWaterMark
, which causes the method to wait
until the water level is equal to our low watermark (which is specified in the user interface). This is determined by the
waterlevel
field, which is initially set to zero in its declaration.
Next we've inserted an additional loop, which continues as long as the water level is less than the high watermark.
For each task we write into the space we increase the water level by one, until it exceeds the high watermark. As we
will see in the next section, as the results are collected this watermark is decremented. Only when the low watermark
is reached do we begin adding more tasks.
11.2.6 Collecting Results
Now let's look at how results are collected. The code for collectResults
is given below:
public void collectResults() {
int count = 0;
Entry template;
try {
template = space.snapshot(
new CryptResult());
} catch (RemoteException e) {
throw new RuntimeException(
"Can't create a snapshot");
}
for (;;) {
CryptResult result = (
CryptResult)takeTask(template);
if (result != null) {
count++;
triedLabel.setText("Tried " +
(count * triesPerTask) +
" words.");
updatePerformance(
count * triesPerTask);
changeWaterLevel(-1);
if (result.word != null) {
String word =
CryptTask.getPrintableWord(
result.word);
answerLabel.setText("
Unencrypted: " +
word.substring(6));
addPoison();
return;
}
}
}
}
In the collectResults
method we first declare a local variable count
, which will be used to keep a
count of the number of tasks that have been computed. We then create a snapshotted version of the
CryptResult
entry, which will be used as a template to take results from the space. Once again, the result
template does not vary when it is used, so snapshotting the entry is better than reserializing the entry each time we
call take
.
Next we enter the main loop of the method; in this loop we first take a result entry from the space, waiting as long as
necessary. Once we have retrieved a result entry, we increment the count variable and update the information display
of the user interface by printing the total number of words that have been tried against the encrypted password
(computed by count * triesPerTask
). We then update the performance area of the information display by
calling updatePerformance
with the total number of word tries as a parameter. The code for
updatePerformance
is given as follows:
public void updatePerformance(
long wordsTried) {
long now = System.currentTimeMillis(
);
long wordRate = wordsTried / ((
now - startTime) / 1000);
perfLabel.setText(wordRate +
" words per second.");
}
First we get the current time and assign it to now
. Then we compute the average number words computed per
second, which is wordsTried
divided by the number of seconds since CryptMaster began running (which is
((now - startTime)/1000)
). This gives us an average number of words computed per second. We then set
the appropriate label in the information display.
Now, returning to collectResults
, after updating the display we decrement the water level, since we know a
task has been removed and computed. We then check to see if the result entry we retrieved has the cracked
password in it. If result.word
is non-null
, then we have the password and we print it in the information
display.
At this point we are finished, but before we return from collectResults
, we first call addPoison
,
which we describe in the next section.
11.2.7 A Little Poison
The addPoison
method allows us to clean up the space, which is needed because, when a valid password
is found, the space may be left with task entries that no longer need to be computed. There may also be result
entries that need to be cleaned up as well. In the latter case, we can expect leases to take care of removing the
results. However, the disadvantage of leaving the task entries around is that the workers will continue to compute
them, which would be a waste of resources in a shared compute server environment.
One approach to cleaning up task entries is to have the master collect the remaining tasks until none remain. A better
approach is to let the workers clean up the tasks themselves. This can be done using a variant of a barrier (see
Chapter 4), which is referred to as a poison pill. Poison pills work like this: When a task's execute
method is called
by the worker, the task checks to see if a poison pill exists in the space. If one exists, then the task simply returns
(and is therefore not computed), but if no pill exists, the task is computed.
To implement a poison pill we first create a poison entry:
public class PoisonPill implements Entry {
public PoisonPill() {
}
}
As you can see the PoisonPill
is a simple entry, whose only purpose is to act as a barrier in the space.
To make use of the poison pill we also need to alter the execute
method of our CryptTask
entry:
public Entry execute(
JavaSpace space) {
PoisonPill template =
new PoisonPill();
try {
if (space.readIfExists(
template, null,
JavaSpace.NO_WAIT) !=
null)
{
return null;
}
} catch (Exception e) {
; // continue on
}
int num = tries.intValue();
System.out.println("Trying " +
getPrintableWord(word));
for (int i = 0; i < num; i++) {
if (encrypted.equals(JCrypt.crypt(
word))) {
CryptResult result =
new CryptResult(word);
return result;
}
nextWord(word);
}
CryptResult result =
new CryptResult(null);
return result;
}
Here we first look for a poison pill in the space using readIfExists
. If one exists then we skip the
computation and return null
. Otherwise, we compute the entry as normal. When the poison pill exists in the
space, it has a flushing effect on the remaining task entries: Whenever a worker takes a task and calls execute, a
poison pill is found and the method returns immediately, so tasks are removed from the space instead of being
computed.
11.2.8 Exploring Crypt
Finally, our application is complete. Now it is time to fire it up and experiment. As with the previous version of the
compute server we first start up one or more generic workers and then start up the CryptMaster
applet. At
this point you should get a feel for how quickly the words are computed using one machine. If you are using a
garden variety machine, then you should expect to see thousands of words processed per second.
With that benchmark behind you, begin to experiment with adding more machines. Pay attention to how the word
rate increases as processors are added to the computation.
At this point you may want to tweak the "tries per task" parameter. If you collect data across a number of runs, you
should see the effect of computation versus communication. As the tries-per-task parameter is raised, computation
plays a larger role in the runtime behavior; as it is lowered, communication plays a larger role.
If you have access to a large number of machines, you will also want to study the speedup gained with each
new processor. For a reasonable number of processors and a large enough "tries per task" you should expect to see
perfect speedup. Perfect speedup means that if you use n processors you will compute a problem n times as fast as
one processor. However as more and more processors are added, the effect may eventually level off, given
contention for the space resource.
11.3 Summary
In this chapter we've explored not only the mechanics of creating a compute server, but also some of the subtle
issues that arise in building parallel applications. As we've seen, creating a replicated-worker application isn't as
easy as just generating tasks, dropping them into a space, and letting workers compute them. Often we need to
consider the granularity of the tasks as well as the resource constraints of the space in a shared environment.
11.4 Exercises
-
Improve the compute server such that it enforces a strict limit on the time a task can be computed. After that
time, the task is aborted and returned to the space.
-
How intractable is the brute force technique of breaking eight character UNIX passwords (how long would it
take)?
-
Experiment with the tries-per-task parameter and its effect on the running time of the crypt application. Make a
graph of the words computed per second as you vary the tries-per-task. How does "tries per task" affect the
computation/communication ratio?
-
Design and implement an adaptive scheme for watermark values-as workers are added and removed from
the compute server, alter the low and high watermarks to use the space more efficiently.
1As used on this web site, the terms "Java
virtual machine" or "JVM" mean a virtual machine for the Java platform.
About the Authors
Eric Freeman is co-founder and CTO of Mirror Worlds
Technologies, a Java and Jini-based software company. Dr. Freeman previously
worked at Yale University on space-based systems, and is a Fellow at Yale's
Center for Internet Studies. Susanne Hupfer is Director of
Product Development for Mirror Worlds Technologies and a fellow of the Yale
University Center for Internet Studies. Dr. Hupfer previously taught Java
network programming as an Assistant Professor of Computer Science at Trinity
College. Ken Arnold is the lead engineer of the JavaSpaces
product at Sun. He is one of the original architects of the Jini platform and
is co-author of The JavaTM Programming
Language, Second Edition.
Reader Feedback
Tell us what you think of this book excerpt.