Odersky M. Programming in Scala
Подождите немного. Документ загружается.
Section 30.6 Chapter 30 · Actors and Concurrency 631
trait Simulant extends Actor {
val clock: Clock
def handleSimMessage(msg: Any)
def simStarting() { }
def act() {
loop {
react {
case Stop => exit()
case Ping(time) =>
if (time == 1) simStarting()
clock ! Pong(time, self)
case msg => handleSimMessage(msg)
}
}
}
start()
}
Listing 30.7 · The Simulant trait.
Whenever a simulant receives Stop, it exits. If it receives a Ping, it responds
with a Pong. If the Ping is for time 1, then simStarting is called before the
Pong is sent back, allowing subclasses to define behavior that should happen
when the simulation starts running. Any other message must be interpreted
by subclasses, so it defers to an abstract handleSimMessage method.
There are two abstract members of a simulant: handleSimMessage and
clock. A simulant must know its clock so that it can reply to Ping messages
and schedule new work items. Putting it all together, the Simulant trait is
as shown in Listing 30.7. Note that a simulant goes ahead and starts running
the moment it is created. This is safe and convenient, because it will not
actually do anything until its clock sends it a message, and that should not
happen until the simulation starts and the clock receives a Start message.
That completes the framework for parallel event simulation. Like its
sequential cousin in Chapter 18, it takes surprisingly little code.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 632
Implementing a circuit simulation
Now that the simulation framework is complete, it’s time to work on the
implementation of circuits. A circuit has a number of wires and gates, which
will be simulants, and a clock for managing the simulation. A wire holds
a boolean signal—either high (true) or low (false). Gates are connected
to a number of wires, some of which are inputs and others outputs. Gates
compute a signal for their output wires based on the state of their input wires.
Since the wire, gates, etc., of a circuit are only used for that particular
circuit, their classes can be defined as members of a Circuit class, just as
with the currency objects of Section 20.9. The overall Circuit class will
therefore have a number of members:
class Circuit {
val clock = new Clock
// simulation messages
// delay constants
// Wire and Gate classes and methods
// misc. utility methods
}
Now look at each of these members, one group at a time. First, there are the
simulation messages. Once the simulation starts running, wires and gates
can only communicate via message sends, so they will need a message type
for each kind of information they want to send each other. There are only
two such kinds of information. Gates need to tell their output wires to change
state, and wires need to inform the gates they are inputs to whenever their
state changes:
case class SetSignal(sig: Boolean)
case class SignalChanged(wire: Wire, sig: Boolean)
Next, there are several delays that must be chosen. Any work item scheduled
with the simulation framework—including propagation of a signal to or from
a wire—must be scheduled at some time in the future. It is unclear what the
precise delays should be, so those delays are worth putting into vals. This
way, they can be easily adjusted in the future:
val WireDelay = 1
val InverterDelay = 2
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 633
val OrGateDelay = 3
val AndGateDelay = 3
At this point it is time to look at the Wire and Gate classes. Consider wires,
first. A wire is a simulant that has a current signal state (high or low) and a
list of gates that are observing that state. It mixes in the Simulant trait, so it
also needs to specify a clock to use:
class Wire(name: String, init: Boolean) extends Simulant {
def this(name: String) { this(name, false) }
def this() { this("unnamed") }
val clock = Circuit.this.clock
clock.add(this)
private var sigVal = init
private var observers: List[Actor] = List()
The class also needs a handleSimMessage method to specify how it should
respond to simulation messages. The only message a wire should receive is
SetSignal, the message for changing a wire’s signal. The response should
be that if the signal is different from the current signal, the current state
changes, and the new signal is propagated:
def handleSimMessage(msg: Any) {
msg match {
case SetSignal(s) =>
if (s != sigVal) {
sigVal = s
signalObservers()
}
}
}
def signalObservers() {
for (obs <- observers)
clock ! AfterDelay(
WireDelay,
SignalChanged(this, sigVal),
obs)
}
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 634
The above code shows how changes in a wire’s signal are propagated to any
gates watching it. It’s also important to pass the initial state of a wire to
any observing gates. This only needs to be done once, when the simulation
starts up. After that, gates can simply store the result of the most recent
SignalChanged they have received. Sending out the initial signal when the
simulation starts is as simple as providing a simStarting() method:
override def simStarting() { signalObservers() }
There are now just a few more odds and ends about wires. Wires need
a method for connecting new gates, and they could use a nice toString
method:
def addObserver(obs: Actor) {
observers = obs :: observers
}
override def toString = "Wire("+ name +")"
That is everything you need for wires. Now consider gates, the other major
class of objects in a circuit. There are three fundamental gates that would be
nice to define: And, Or, and Not. All of these share a lot of behavior, so it is
worth defining an abstract Gate class to hold the commonality.
A difficulty in defining this Gate class is that some gates have two input
wires (And, Or) while others have just one (Not). It would be possible to
model this difference explicitly. However, it simplifies the code to think of
all gates as having two inputs, where Not gates simply ignore their second
input. The ignored second input can be set to some dummy wire that never
changes state from false:
private object DummyWire extends Wire("dummy")
Given this trick, the gate class will come together straightforwardly. It
mixes in the Simulant trait, and its one constructor accepts two input wires
and one output wire:
abstract class Gate(in1: Wire, in2: Wire, out: Wire)
extends Simulant {
There are two abstract members of Gate that specific subclasses will have
to fill in. The most obvious is that different kinds of gates compute a dif-
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 635
ferent function of their inputs. Thus, there should be an abstract method for
computing an output based on inputs:
def computeOutput(s1: Boolean, s2: Boolean): Boolean
Second, different kinds of gates have different propagation delays. Thus, the
delay of the gate should be an abstract val:
val delay: Int
The delay could be a def, but making it a val encodes the fact that a partic-
ular gate’s delay should never change.
Because Gate mixes in Simulant, it is required to specify which clock
it is using. As with Wire, Gate should specify the clock of the enclosing
Circuit. For convenience, the Gate can go ahead and add itself to the clock
when it is constructed:
val clock = Circuit.this.clock
clock.add(this)
Similarly, it makes sense to go ahead and connect the gate to the two input
wires, using regular method calls:
in1.addObserver(this)
in2.addObserver(this)
The only local state of a gate is the most recent signal on each of its input
wires. This state needs to be stored, because wires only send a signal when
the state changes. If one input wire changes, only that one wire’s state will
be sent to the gate, but the new output will need to be computed from both
wires’ states:
var s1, s2 = false
Now look at how gates respond to simulation messages. There is only one
message they need to handle, and that’s the SignalChanged message indi-
cating that one of the input wires has changed. When a SignalChanged
arrives, two things need to be done. First, the local notion of the wire states
need to be updated according to the change. Second, the new output needs to
be computed and then sent out to the output wire with a SetSignal message:
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 636
def handleSimMessage(msg: Any) {
msg match {
case SignalChanged(w, sig) =>
if (w == in1)
s1 = sig
if (w == in2)
s2 = sig
clock ! AfterDelay(delay,
SetSignal(computeOutput(s1, s2)),
out)
}
}
Given this abstract Gate class, it is now easy to define specific kinds of gates.
As with the sequential simulation in Chapter 18, the gates can be created as
side effects of calling some utility methods. All the methods need to do
is create a Gate and fill in the appropriate delay and output computation.
Everything else is common to all gates and is handled in the Gate class:
def orGate(in1: Wire, in2: Wire, output: Wire) =
new Gate(in1, in2, output) {
val delay = OrGateDelay
def computeOutput(s1: Boolean, s2: Boolean) = s1 || s2
}
def andGate(in1: Wire, in2: Wire, output: Wire) =
new Gate(in1, in2, output) {
val delay = AndGateDelay
def computeOutput(s1: Boolean, s2: Boolean) = s1 && s2
}
In the case of Not gates, a dummy wire will be specified as the second input.
This is an implementation detail from the point of view of a caller creating a
Not gate, so the inverter method only takes one input wire instead of two:
def inverter(input: Wire, output: Wire) =
new Gate(input, DummyWire, output) {
val delay = InverterDelay
def computeOutput(s1: Boolean, ignored: Boolean) = !s1
}
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 637
At this point the library can simulate circuits, but, as described in Chap-
ter 18, it is useful to add a wire-probing utility so that you can watch the
circuit evolve. Without such a utility, the simulation would have no way to
know which wires are worth logging and which are more like implementa-
tion details.
Define a probe method that takes a Wire as an argument and then prints
out a line of text whenever that wire’s signal changes. The method can be
implemented by simply making a new simulant that connects itself to a spec-
ified wire. This simulant can respond to SignalChanged messages by print-
ing out the new signal:
def probe(wire: Wire) = new Simulant {
val clock = Circuit.this.clock
clock.add(this)
wire.addObserver(this)
def handleSimMessage(msg: Any) {
msg match {
case SignalChanged(w, s) =>
println("signal "+ w +" changed to "+ s)
}
}
}
That is the bulk of the Circuit class. Callers should create an instance
of Circuit, create a bunch of wires and gates, call probe on a few wires
of interest, and then start the simulation running. The one piece missing is
how the simulation is started, and that can be as simple as sending the clock
a Start message:
def start() { clock ! Start }
More complicated circuit components can be built from methods just as
it was explained previously in Chapter 18. For instance Listing 30.8 shows
again the half adder and full adder components that were already introduced
then. Their implementation stays is the same, but as a small variation they
are now packaged in a trait, named Adders, whereas in Chapter 18 they
were contained in an abstract class. Because the trait is marked as extend-
ing Circuit, it can directly access members of Circuit such as Wire and
orGate. Using the trait then looks like this:
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 638
trait Adders extends Circuit {
def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
val d, e = new Wire
orGate(a, b, d)
andGate(a, b, c)
inverter(c, e)
andGate(d, e, s)
}
def fullAdder(a: Wire, b: Wire, cin: Wire,
sum: Wire, cout: Wire) {
val s, c1, c2 = new Wire
halfAdder(a, cin, s, c1)
halfAdder(b, s, sum, c2)
orGate(c1, c2, cout)
}
}
Listing 30.8 · Adder components.
val circuit = new Circuit with Adders
This circuit variable holds a circuit that has all of the methods of Circuit
and all of the methods of Adders. Note that with this coding pattern, based
on a trait instead of a class, you set the stage to provide multiple component
sets. Users mix in whichever component sets they plan to use, like this:
val circuit =
new Circuit
with Adders
with Multiplexers
with FlipFlops
with MultiCoreProcessors
Trying it all out
That’s the whole framework. It includes a simulation framework, a circuit
simulation class, and a small library of standard adder components. Here is
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.6 Chapter 30 · Actors and Concurrency 639
a simple demo object that uses it:
object Demo {
def main(args: Array[String]) {
val circuit = new Circuit with Adders
import circuit._
val ain = new Wire("ain", true)
val bin = new Wire("bin", false)
val cin = new Wire("cin", true)
val sout = new Wire("sout")
val cout = new Wire("cout")
probe(ain)
probe(bin)
probe(cin)
probe(sout)
probe(cout)
fullAdder(ain, bin, cin, sout, cout)
circuit.start()
}
}
This example creates a circuit that includes the Adders trait. It immediately
imports all of the circuit’s members, thus allowing easy accesses to methods
like probe and fullAdder. Without the import, it would be necessary to
write circuit.probe(ain) instead of just probe(ain).
The example then creates five wires. Three will be used as inputs (ain,
bin, and cin), and two will be used as outputs (sout, cout). The three input
wires are given arbitrary initial signals of true, false, and true. These
inputs correspond to adding 1 to 0, with a carry in of 1.
The probe method gets applied to all five externally visible wires, so
any changes in their state can be observed as the simulation runs. Finally the
wires are plugged into a full adder, and the simulation is started. The output
of the simulation is as follows:
Advancing to time 1
Advancing to time 2
signal Wire(cout) changed to false
signal Wire(cin) changed to true
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 30.7 Chapter 30 · Actors and Concurrency 640
signal Wire(ain) changed to true
signal Wire(sout) changed to false
signal Wire(bin) changed to false
Advancing to time 3
Advancing to time 4
Advancing to time 5
Advancing to time 6
Advancing to time 7
Advancing to time 8
Advancing to time 9
Advancing to time 10
signal Wire(cout) changed to true
Advancing to time 11
Advancing to time 12
Advancing to time 13
Advancing to time 14
Advancing to time 15
Advancing to time 16
Advancing to time 17
Advancing to time 18
signal Wire(sout) changed to true
Advancing to time 19
Advancing to time 20
Advancing to time 21
signal Wire(sout) changed to false
**
Agenda empty. Clock exiting at time 21.
As expected, with inputs of 1, 0, and 1 (true, false and true), the outputs
are a carry of 1 and sum of 0 (cout is true, and sout is false).
30.7 Conclusion
Concurrent programming gives you great power. It lets you simplify your
code, and it lets you take advantage of multiple processors. It is therefore
unfortunate that the most widely used concurrency primitives, threads, locks,
and monitors, are such a minefield of deadlocks and race conditions.
The actors style provides a way out of the minefield, letting you write
concurrent programs without having such a great risk of deadlocks and race
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index