Transcript JavaSpace-ex-slides - Network and Systems Laboratory

Contents
•
•
•
•
•
•
Distributed data structures
Different implementations
First example: bank transactions
JavaSpaces concepts
Replicated-worker pattern
Second example: Mandelbrot set
1
Distributed data structures
• “A distributed data structure is a data structure
that can be accessed and manipulated by
multiple processes at the same time”
• In most distributed systems are hard to achieve
• Message passing (CORBA) or RMI (remote
method invocation) in Java are good examples
2
Ordinary systems
• Ordinary systems tend to barricade
data structures behind one central
manager
• Attempting to parallelize across more
than one machine faces to a
bottleneck
• Multiple processes can’t access the
data in a concurrently way
3
JavaSpace solution
• JavaSpaces solve this problem
with a different approach
• Data structures are represented
as collection of objects than can
be independently accessed in a
concurrent manner
• Processes no longer wait in line
4
First example
• Bank transactions
• Two bank tellers are making a deposit to the
same bank account at the same time.
• A deposit consist in 3 different operations
– Looking up
– Modifying
– Setting the account’s value
5
First example
• Problems arise in this scenario:
– The bank account value is $200
– The two Bank tellers want to deposit respectively $100
and $50
– Bank teller #1 looks up the balance of $200
– Bank teller #2 looks up the balance and reads $200 too,
since bank teller #1 hasn’t completed the deposit yet
– Bank teller #1 performs the deposit and records a
balance of $300
– Bank teller #2 performs the deposit and records a
balance of $250
6
First example
• The bank account has been corrupted
• The problem occurs because updating the bank
balance is not an atomic operation
• To solve the problem updating a shared value
needs to be an atomic operation
• With JavaSpaces we get this atomicity “for free”
7
First Example
• Pseudocode for the bank transaction
SharedVar template = new SharedVar(“bank account”);
SharedVar result = (SharedVar) space.take(template, null,
Long.MAX_VALUE);
result.value = new Integer(result.value.intValue() + 100);
space.write(result, null, Lease.FOREVER);
• The race condition can’t occur here, since only
one process can “own” the bank account at the
same time
8
First Example
• Isn’t production ready yet
• What append if one bank teller removes the Entry
that describes the bank account and fails to return
it for a program crash or a network down?
• Luckily there are several ways to improve our
code. We’ll see that topics later…
9
JavaSpace concepts
• Topics that especially shine in JavaSpaces
• Processes involved in the computation no longer
wait in line, they can work on independent pieces
of data at the same time, as long as they don’t
“step on each others toes”
• Every program written having JavaSpaces in mind
should implement this concept tightly
10
JavaSpaces concepts
• The program data has to be broken in several (and
smaller) pieces, allowing two or more processes to
use the program data simultaneously
11
JavaSpace concepts: example
• Imagine now that two process are accessing the
same array at two different locations at the same
time
• There are two different way to do this in
JavaSpaces
• The first is the „classic“ implementation
• The second is „JavaSpaces-approved“ and
improves the parallelization
12
JavaSpace concepts: 1 code
• Pseudocode
public class array1 implements Entry {
public int data[];
public array1() {};
}
• The array is defined as a “continuous” memory
area
• Only one process can “own” the array-Entry at the
same time
13
JavaSpace concepts: 1 code
• The first process grabs the array, works with it and
puts it back
• The second process can begin to work only after
the end of the first process, even if they were
interested in different pieces of data
14
JavaSpaces concepts: 2 code
• Pseudocode
public class array2 implements Entry {
public int data;
public int offset;
public array2() {}
}
• The array is composed of several integer-Entries
15
JavaSpaces concepts: 2 code
• The two process work on different pieces of data
at the same time
• The tasks don’t wait for a resource that can be
shared
16
Replicated-worker pattern
• This pattern is designed to solve intensive
computation problems in terms of smaller tasks
that can be computed concurrently
• This pattern involves
– one Master, along with
– any number of workers
17
Replicated-worker pattern
• The Master takes a problem, divides it up into
smaller tasks and deposit them into the space
• The workers spend their lives waiting for tasks,
removing them from the space, computing them
and writing the results back into the space
• The Master collects then the tasks’ results and
combine them into a meaningful overall solution
18
Replicated-worker pattern
• Pseudocode for the Master:
public class Master {
for (int i = 0; i < totalTasks; i++) {
Task task = new Task(…);
space.write(task, …);
}
for (int i = 0; i < totalTasks; i++) {
Result template = new Result(…);
Result result = (Result)space.take(template, …);
//… combine results
}
}
19
Replicated-worker pattern
• The master iterates through all the tasks that need
to be computed creating an Entry for each and
writing it into the space
• The master iterates again, this time removing as
many result entries from the space as there were
tasks and combining them into some meaningful
form
20
Replicated-worker pattern
• Pseudocode for the workers:
public class Worker {
for (;;) {
Task template = new Task(...);
Task task = (Task)space.take(template, ...);
Result result = compute(task);
space.write(result, ...);
}
}
21
Replicated-worker pattern
• A worker repeatedly removes a task from the
space, computes it, and writes the result of the
computation back into the space, where it will be
picked up by the master process
22
Second example
• Mandelbrot Set
• The problem consists mainly in the computation
of an image, following a specific mathematical
formula
• We are interested in the nature of the problem,
where each pixel can be computed independently
of all the rest
• JavaSpaces solves this problem very cleanly
23
Second example: Master
• The master generates a task for each scanline that
need to be displayed writing it to the space
• It then “sleeps” waiting for the workers to do their
job
• It finally collects the result (in whatever order it
finds them) and combine them drawing the result
to the screen
24
Second example: Master
• First iteration
(building tasks)
• Second iteration
(combine them)
25
Second example: Workers
• Each worker repeatedly removes a task from the
space, computes the color values for the scanline
represented by the task and writes the result back
to the space for the master to pick up
26