Odersky M. Programming in Scala
Подождите немного. Документ загружается.
Section 30.5 Chapter 30 · Actors and Concurrency 621
The best way to ensure that message objects are thread-safe is to only
use immutable objects for messages. Instances of any class that has only val
fields, which themselves refer only to immutable objects, are immutable. An
easy way to define such message classes, of course, is as case classes. So
long as you don’t explicitly add var fields to a case class and ensure the
val fields are all immutable types, your case class will by definition be im-
mutable. It will also be convenient for pattern matching in the partial func-
tions passed to react or receive. You can also use as messages instances
of regular (non-case) immutable classes that you define. Or you can use in-
stances of the many immutable classes provided in the Scala API, such as
tuples, strings, lists, immutable sets and maps, and so on.
Now, if an actor sends a mutable, unsynchronized object as a message,
and never reads or writes that object thereafter, it would work, but it’s just
asking for trouble. A future maintainer may not realize the object is shared
and write to it, thereby creating a hard to find concurrency bug.
In general, it is best to arrange your data such that every unsynchronized,
mutable object is “owned,” and therefore accessed by, only one actor. You
can arrange for objects to be transferred from one actor to another if you like,
but you need to make sure that at any given time, it is clear which actor owns
the object and is allowed to access it. In other words, when you design an
actors-based system, you need to decide which parts of mutable memory are
assigned to which actor. All other actors that access a mutable data structure
must send messages to the data structure’s owner and wait for a message to
come back with a reply.
If you do find you have a mutable object you want to continue using as
well as send in a message to another actor, you should make and send an
copy of it instead. While you’re at it, you may want to make it immutable.
For example, because arrays are mutable and unsynchronized, any array you
use should be accessed by one actor at a time. If you want to continue using
an array as well as send it to another actor, you should send a copy. For
example, if the array itself holds only immutable objects, you can make a
copy with arr.clone. But you should also consider using arr.toList, and
send the resulting immutable list instead.
Immutable objects are convenient in many cases, but they really shine
for parallel systems, because they are the easiest, lowest risk way to design
thread-safe objects. When you design a program that might involve paral-
lelism in the future, whether using actors or not, you should try especially
hard to make data structures immutable.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.5 Chapter 30 · Actors and Concurrency 622
Make messages self-contained
When you return a value from a method, the caller is in a good position to
remember what it was doing before it called the method. It can take the
response value and then continue whatever it was doing.
With actors, things are trickier. When one actor makes a request of an-
other, the response might come not come for a long time. The calling actor
should not block, but should continue to do any other work it can while it
waits for the response. A difficulty, then, is interpreting the response when it
finally does come back. Can the actor remember what it was doing when it
made the request?
One way to simplify the logic of an actors program is to include redun-
dant information in the messages. If the request is an immutable object, you
can even cheaply include a reference to the request in the return value! For
example, the IP-lookup actor would be better if it returned the host name
in addition to the IP address found for it. It would make this actor slightly
longer, but it should simplify the logic of any actor making requests on it:
def act() {
loop {
react {
case (name: String, actor: Actor) =>
actor ! (name, getIp(name))
}
}
}
Another way to increase redundancy in the messages is to make a case class
for each kind of message. While such a wrapper is not strictly necessary in
many cases, it makes an actors program much easier to understand. Imagine
a programmer looking at a send of a string, for example:
lookerUpper ! ("www.scala-lang.org", self)
It can be difficult to figure out which actors in the code might respond. It is
much easier if the code looks like this:
case class LookupIP(hostname: String, requester: Actor)
lookerUpper ! LookupIP("www.scala-lang.org", self)
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 623
import scala.actors.Actor._
import java.net.{InetAddress, UnknownHostException}
case class LookupIP(name: String, respondTo: Actor)
case class LookupResult(
name: String,
address: Option[InetAddress]
)
object NameResolver2 extends Actor {
def act() {
loop {
react {
case LookupIP(name, actor) =>
actor ! LookupResult(name, getIp(name))
}
}
}
def getIp(name: String): Option[InetAddress] = {
// As before (in Listing 30.3)
}
}
Listing 30.6 · An actor that uses case classes for messages.
Now, the programmer can search for LookupIP in the source code, probably
finding very few possible responders. Listing 30.6 shows an updated name-
resolving actor that uses case classes instead of tuples for its messages.
30.6 A longer example: Parallel discrete event
simulation
As a longer example, suppose you wanted to parallelize the discrete event
simulation of Chapter 18. Each participant in the simulation could run as
its own actor, thus allowing you to speed up a simulation by using more
processors. This section will walk you through the process, using code based
on a parallel circuit simulator developed by Philipp Haller.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 624
Overall Design
Most of the design from Chapter 18 works fine for both sequential and par-
allel discrete event simulation. There are events, and they happen at desig-
nated times, processing an event can cause new events to be scheduled, and
so forth. Likewise, a circuit simulation can be implemented as a discrete
event simulation by making gates and wires participants in the simulation,
and changes in the wires the events of the simulation. The one thing that
would be nice to change would be to run the events in parallel. How can the
design be rearranged to make this happen?
The key idea is to make each simulated object an actor. Each event can
then be processed by the actor where most of that event’s state lies. For
circuit simulation, the update of a gate’s output can be processed by the actor
corresponding to that gate. With this arrangement, events will naturally be
handled in parallel.
In code, it is likely that there will be some common behavior between
different simulated objects. It makes sense, then, to define a trait Simulant
that can be mixed into to any class to make it a simulated object. Wires,
gates, and other simulated objects can mix in this trait.
trait Simulant extends Actor
class Wire extends Simulant
So far so good, but there are a few design issues to work out, several
of which do not have a single, obviously best answer. For this chapter, we
present a reasonable choice for each design issue that keeps the code concise.
There are other solutions possible, though, and trying them out would make
for good practice for anyone wanting experience programming with actors.
The first design issue is to figure out how to make the simulation par-
ticipants stay synchronized with the simulated time. That is, participant A
should not race ahead and process an event at time tick 100 until all other ac-
tors have finished with time tick 99. To see why this is essential, imagine for
a moment that simulant A is working at time 90 while simulant B is working
at time 100. It might be that participant A is about to send a message that
changes B’s state at time 91. B will not learn this until too late, because it
has already processed times 92 to 99. To avoid this problem, the design ap-
proach used in this chapter is that no simulant should process events for time
n until all other simulants are finished with time n − 1.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 625
That decision raises a new question, though: how do simulants know
when it’s safe to move forward? A straightforward approach is to have a
“clock” actor that keeps track of the current time and tells the simulation
participants when it is time to move forward. To keep the clock from moving
forward before all simulants are ready, the clock can ping actors at carefully
chosen times to make sure they have received and processed all messages for
the current time tick. There will be Ping methods that the clock sends the
simulants, and Pong messages that the simulants send back when they are
ready for the clock to move forward.
case class Ping(time: Int)
case class Pong(time: Int, from: Actor)
Note that these messages could be defined as having no fields. However,
the time and from fields add a little bit of redundancy to the system. The
time field holds the time of a ping, and it can be used to connect a Pong
with its associated Ping. The from field is the sender of a Pong. The sender
of a Ping is always the clock, so it does not have a from field. All of this
information is unnecessary if the program is behaving perfectly, but it can
simplify the logic in some places, and it can greatly help in debugging if the
program has any errors.
One question that arises is how a simulant knows it has finished with the
current time tick. Simulants should not respond to a Ping until they have
finished all the work for that tick, but how do they know? Maybe another
actor has made a request to it that has not yet arrived. Maybe a message one
actor has sent another has not been processed yet.
It simplifies the answer to this question to add two constraints. First,
assume that simulants never send each other messages directly, but instead
only schedule events on each other. Second, they never post events for the
current time tick, but only for times at least one tick into the future. These
two constraints are significant, but they appear tolerable for a typical simula-
tion. After all, there is normally some non-zero propagation delay whenever
two components of a system interact with each other. Further, at worst, time
ticks can be made to correspond to shorter time intervals, and information
that will be needed in the future can be sent ahead of time.
Other arrangements are possible. Simulants could be allowed to send
messages directly to each other. However, if they do so, then there would
need to be a more sophisticated mechanism for deciding when it is safe for
an actor to send back a Pong. Each simulant should delay responding to a
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 626
Ping until any other simulants it has made requests to are finished processing
those requests. To ensure this property, you would need the simulants to pass
each other some extra information. For now, assume that simulants don’t
communicate with each other except via the simulation’s agenda.
Given that decision, there may as well be a single agenda of work items,
and that agenda may as well be held by the clock actor. That way, the clock
can wait to send out pings until it has sent out requests for all work items at
the current time. Actors then know that whenever they receive a Ping, they
have already received from the clock all work items that need to happen at the
current time tick. It is thus safe when an actor receives a Ping to immediately
send back a Pong, because no more work will be arriving during the current
time tick. Taking this approach, a Clock has the following state:
class Clock extends Actor {
private var running = false
private var currentTime = 0
private var agenda: List[WorkItem] = List()
}
The final design issue to work out is how a simulation is set up to begin
with. A natural approach is to create the simulation with the clock stopped,
add all the simulants, connect them all together, and then start the clock. The
subtlety is that you need to be absolutely sure that everything is connected
before you start the clock running! Otherwise, some parts of the simulation
will start running before they are fully formed.
How do you know when the simulation is fully assembled and ready to
start? There are again multiple ways to approach this problem. The sim-
ple way adopted in this chapter is to avoid sending message to actors while
setting the simulation up. That way, once the last method call returns, you
know that the simulation is entirely constructed. The resulting coding pat-
tern is that you use regular method calls to set the simulation up, and you use
actor message sends while the simulation is running.
Given the preceding decisions, the rest of the design is straightforward.
A WorkItem can be defined much like in Chapter 18, in that it holds a time
and an action. For the parallel simulation, however, the action itself has a
different encoding. In Chapter 18, actions are represented as zero-argument
functions. For parallel simulation, it is more natural to use a target actor and
a message to be sent to that actor:
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 627
case class WorkItem(time: Int, msg: Any, target: Actor)
Likewise, the afterDelay method for scheduling a new work item becomes
an AfterDelay message that can be sent to the clock. Just as with the
WorkItem class, the zero-argument action function is replaced by a message
and a target actor:
case class AfterDelay(delay: Int, msg: Any, target: Actor)
Finally, it will prove useful to have messages requesting the simulation to
start and stop:
case object Start
case object Stop
That’s it for the overall design. There is a Clock class holding a current
time and an agenda, and a clock only advances the clock after it has pinged
all of its simulants to be sure they are ready. There is a Simulant trait for
simulation participants, and these communicate with their fellow simulants
by sending work items to the clock to add to its agenda. The next section
will take a look now at how to implement these core classes.
Implementing the simulation framework
There are two things that need implementing for the core framework: the
Clock class and the Simulant trait. Consider the Clock class, first. The
necessary state of a clock is as follows:
class Clock extends Actor {
private var running = false
private var currentTime = 0
private var agenda: List[WorkItem] = List()
private var allSimulants: List[Actor] = List()
private var busySimulants: Set[Actor] = Set.empty
A clock starts out with running set to false. Once the simulation is fully
initialized, the clock will be sent the Start message and running will be-
come true. This way, the simulation stays frozen until all of its pieces have
been connected together as desired. It also means that, since all of the sim-
ulants are also frozen, it is safe to use regular method calls to set things up
instead of needing to use actor message sends.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 628
A clock may as well go ahead and start running as an actor once it is
created. This is safe, because it will not actually do anything until it receives
a Start message:
start()
A clock also keeps track of the current time (currentTime), the list of
participants managed by this clock (allSimulants), and the list of partic-
ipants that are still working on the current time tick (busySimulants). A
list is used to hold allSimulants, because it is only iterated through, but a
set is used for busySimulants because items will be removed from it in an
unpredictable order. Once the simulator starts running, it will only advance
to a new time when busySimulants is empty, and whenever it advances the
clock, it will set busySimulants to allSimulants.
To set up a simulation, there is going to be a need for a method to add
new simulants to a clock. It may as well be added right now:
def add(sim: Simulant) {
allSimulants = sim :: allSimulants
}
That’s the state of a clock. Now look at its activity. Its main loop alter-
nates between two responsibilities: advancing the clock, and responding to
messages. Once the clock advances, it can only advance again when at least
one message has been received, so it is safe to define the main loop as an
alternation between these two activities:
def act() {
loop {
if (running && busySimulants.isEmpty)
advance()
reactToOneMessage()
}
}
The advancement of time has a few parts beyond simply incrementing the
currentTime. First, if the agenda is empty, and the simulation is not just
starting, then the simulation should exit. Second, assuming the agenda is
non-empty, all work items for time currentTime should now take place.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 629
Third, all simulants should be put on the busySimulants list and sent Pings.
The clock will not advance again until all Pings have been responded to:
def advance() {
if (agenda.isEmpty && currentTime > 0) {
println("
**
Agenda empty. Clock exiting at time "+
currentTime+".")
self ! Stop
return
}
currentTime += 1
println("Advancing to time "+currentTime)
processCurrentEvents()
for (sim <- allSimulants)
sim ! Ping(currentTime)
busySimulants = Set.empty ++ allSimulants
}
Processing the current events is simply a matter of processing all events at
the top of the agenda whose time is currentTime:
private def processCurrentEvents() {
val todoNow = agenda.takeWhile(_.time <= currentTime)
agenda = agenda.drop(todoNow.length)
for (WorkItem(time, msg, target) <- todoNow) {
assert(time == currentTime)
target ! msg
}
}
There are three steps in this method. First, the items that need to occur at the
current time are selected using takeWhile and saved into the val todoNow.
Second, those items are dropped from the agenda by using drop. Finally, the
items to do now are looped through and sent the target message. The assert
is included just to guarantee that the scheduler’s logic is sound.
Given this ground work, handling the messages that a clock can receive
is straightforward. An AfterDelay message causes a new item to be added
to the work queue. A Pong causes a simulant to be removed from the list of
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 630
busy simulants. Start causes the simulation to begin, and Stop causes the
clock to stop:
def reactToOneMessage() {
react {
case AfterDelay(delay, msg, target) =>
val item = WorkItem(currentTime + delay, msg, target)
agenda = insert(agenda, item)
case Pong(time, sim) =>
assert(time == currentTime)
assert(busySimulants contains sim)
busySimulants -= sim
case Start => running = true
case Stop =>
for (sim <- allSimulants)
sim ! Stop
exit()
}
}
The insert method, not shown, is exactly like that of Listing 18.8. It inserts
its argument into the agenda while being careful to keep the agenda sorted.
That’s the complete implementation of Clock. Now consider how to im-
plement Simulant. Boiled down to its essence, a Simulant is any actor that
understands and cooperates with the simulation messages Stop and Ping.
Its act method can therefore be as simple as this:
def act() {
loop {
react {
case Stop => exit()
case Ping(time) =>
if (time == 1) simStarting()
clock ! Pong(time, self)
case msg => handleSimMessage(msg)
}
}
}
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index