12th
Discrete Event Simulation with Python Coroutines
I’m building a discrete event simulation tool in Python. When I found out that Python 2.5 supported coroutines, I was excited. The results were less than satisfying. First, a little background.
Discrete Event Simulation
Discrete event simulation is pretty easy. You need an event queue, an environment to act on, and actors to simulate. When an actor wants to do something, they place an event on the queue, and wait. The simulation process the events in the queue according to timestamp (according to the simulated clock). When an event is processed, the operations are performed on the environment, and the actor is informed of the results. Now, discrete event simulations can simulate a very complicated parallel system, but the parallelism is simulated. The event queue is synchronized, and only one event is processed at a time. This wikipedia article provides more detail.
Coroutines are useful in discrete event simulations because they allow the actor to yield control to the event queue every time they place an event in the queue. Coroutines are like threads, but cooperatively schedule themselves. This is desirable, because you don’t have to worry about synchronization issues that arise from threads. There are other benefits as well, such as incredible efficiency gains. See this wikipedia article for more on coroutines.
Network Simulation
My specific problem is simulating a network with hostile actors. I want people to be able to write their own actors. Let’s say that there are three primitives, wait(), ping(), and kill(). This is what I want:
class Pinger(Actor):
def go(self):
self.wait(25)
success = True
while success:
result = self.ping("128.111.41.38")
if result != "success":
success = False
print "Pinger done"
and
class Killer(Actor):
def go(self):
self.wait(100)
self.kill("128.111.41.38")
print "Killer done"
This would let me run two actors in the simulation. One would sleep for a short bit, then ping a machine until a ping failed. The second would sleep for a longer bit, then wake up and kill the target machine.
The Ugly Truth
Unfortunately, the syntax I get is not as nice:
class Pinger(Actor):
def go(self):
self.this_pointer = (yield None)
yield self.wait(25)
success = True
while success:
result = (yield self.ping("128.111.41.38"))
if result != "success":
success = False
print "Pinger done"
and
class Killer(Actor):
def go(self):
self.this_pointer = (yield None)
yield self.wait(100)
yield self.kill("128.111.41.38")
print "Killer done"
What?! The first thing you’ll notice is the absurd first line in go().self.this_pointer = (yield None)
Where did that come from? Well, as the event queue is being processed, it’s important to know who to pass results to. Unfortunately, self refers to the Actor instance, not the coroutine (go()). I found this happy workaround here. One line of ugly code passed on to my users, and I get an effective this pointer. I found another post that said such a mechanism was unnecessary, but I’m a Python n00b, and I wasn’t able to call the stack frame returned using the other technique. Instructions would be nice.
The next thing I take issue with is the mandate that my users explicitly yield. I wanted to push the yield statements into the primitives, but doing so only makes wait(), ping(), and kill() coroutines instead of subroutines within the coroutine go(). This also means that the entire logic of the Actor has to go (HA! pun) in the go() function. There can be no first_part() and second_part(), as those pesky yield statements must be in the body of go(). Nuts.
Complete Listing
Here’s the complete code for my proof-of-concept:
from PriorityQueue import PriorityQueue
class Sim:
def __init__(self):
self.q = PriorityQueue()
self.time = 0
self.nodes = {}
self.actors = []
self.done = False
def add_actor(self, actor):
actor.sim = self
self.actors.append(actor)
def at(self, event):
if event.time < self.time:
print "ERROR, time warp"
else:
self.q.put(event, event.time)
def process(self):
while not self.q.empty():
event = self.q.get()
self.time = event.time
try:
(result, actor) = event.process(self)
actor.send(result)
except StopIteration:
pass
print "Sim done"
def prime(self):
for a in self.actors:
a.prime()
def go(self):
self.prime()
self.process()
class Actor:
def ping(self, who):
self.sim.at(Ping(self.sim.time + 5, self.this_pointer, who))
def kill(self, who):
self.sim.at(Kill(self.sim.time + 5, self.this_pointer, who))
def wait(self, how_long):
self.sim.at(Wait(self.sim.time + how_long, self.this_pointer))
def __init__(self):
"""Somehow get everyone ready"""
self.sim = None
self.this_pointer = None
def prime(self):
g = self.go()
g.next()
g.send(g)
class Node:
def __init__(self):
self.status = "OK"
class Pinger(Actor):
def go(self):
self.this_pointer = (yield None)
yield self.wait(25)
success = True
while success:
result = (yield self.ping("128.111.41.38"))
if result != "success":
success = False
print "Pinger done"
class Killer(Actor):
def go(self):
self.this_pointer = (yield None)
yield self.wait(100)
yield self.kill("128.111.41.38")
print "Killer done"
class Event:
def __init__(self, time, actor):
self.time = time
self.actor = actor
def process(self, sim):
pass
class Wait(Event):
def process(self, sim):
return ("success", self.actor)
class Kill(Event):
def __init__(self, time, actor, target):
Event.__init__(self, time, actor)
self.target = target
def process(self, sim):
if sim.nodes[self.target].status == "OK":
sim.nodes[self.target].status = "DOWN"
print " kill SUCCESS"
return ("success", self.actor)
class Ping(Event):
def __init__(self, time, actor, target):
Event.__init__(self, time, actor)
self.target = target
def process(self, sim):
if sim.nodes[self.target].status == "OK":
print " ping"
return ("success", self.actor)
else:
print " ping FAIL"
return ("failure", self.actor)
if __name__ == "__main__":
s = Sim()
n = Node()
s.nodes["128.111.41.38"] = n
s.add_actor(Killer())
s.add_actor(Pinger())
s.go()
My priority queue is a very slight modification of the one posted here. Anyway, while I was happy to prove that you could build a discrete event simulation tool using Python’s coroutines, I was not happy with the result. As a consequence, I switched to using threads. I’ll post that when I’m done debugging. I have a synchronization issue right now, and I don’t know what things are thread safe by design and what things I need to explicitly synchronize access to.
