|
| |
Note: SimPy provides event
signalling. The following is only shown to demonstrate how easy SimPy extension
is.
Typical model scenario: a process activates several other processes
and can only continue when a certain state has been reached by one or more of
these processes. An example: a simulation of a PERT (Program
Evaluation Review Technique) network of interdependent activities.
Problem: SimPy only has two process-to-process signaling constructs,
namely activate/reactivate and
interrupt. Both are low-level and do not
allow waiting processes to respond only to specific signals without extra user
programming, as they do not carry a parameter giving the reason for the
activation or interrupt. This user programming can be error-prone and may lead
to undesirable tight coupling between processes.
A solution approach: One inter-process signaling approach used in e.g.
operating systems is by setting and waiting for events. A SimPy
extension with events would require an API extension with capabilities
like set (signal an event), wait (wait for an event, for mass
release of waiting processes) and queue (wait for an event in a queue,
for release of processes one-by-one in some order, e.g. FIFO). All these calls
must be atomic, i.e., they must be executed completely and without interruption
when called. Otherwise, inconsistent system states could occur.
In SimPy, events could be implemented with new yield verbs or with
constructs like:
if hasNotOccurred(thisEvent):
waitFor(thisEvent); yield passivate, self
The second form is also atomic, as processes execute all code between
yield statements without interruption by other processes.
An experimental implementation: in the experimental implementation
below, I have chosen for the second form, as this avoids cluttering the yield
set of verbs. Events are named instances of a class
with two lists, one for the set of processes waiting for the event and
one for the FIFO queue of events queuing for the event. An event can be
set, waited for or queued for by the methods
set, wait, and
queue, respectively.
wait and queue return
True when a process has to wait for the event to
occur, in which case the process must passivate itself. Events are cleared
whenever wait or queue
are called. set reactivates all the processes in
the event's waits list and the first process in
its queues queue.
#!/usr/bin/env python
# Events.py
from SimPy.Simulation import *
class Event:
"""Class implementing named events==signals for synchronization of processes.
Not to be confused with events as in discrete _event_ simulation!
Provides for semaphores and also for mass-reactivation of processes after event.
"""
def __init__(self,name):
self.name=name
self.waits=[] #set of processes waiting for event
self.queues=[] #FIFO queue for processes waiting for semaphore
self.occurred=False
def set(self):
"""Produces a signal;
Set this event if no process waiting or queuing;
reactivate all processes waiting for this event;
reactivate first process in FIFO queue for this event
"""
if not self.waits and not self.queues:
self.occurred=True
else:
#schedule activation for all waiting processes
for p in self.waits:
reactivate(p)
self.waits=[]
if self.queues:
#Activate first process in queue to enter critical section
p=self.queues.pop(0)
reactivate(p)
def wait(self,proc):
"""Consumes a signal if it has been sent,
else process 'proc' waits for this event.
Return value indicates whether process has to wait.
"""
if not self.occurred:
self.waits.append(proc)
return True
else:
self.occurred=False
return False
def queue(self,proc):
"""Consumes a signal if it has been sent;
else process 'proc' queues for this event
Return value indicates whether process has to queue.
"""
if not self.occurred:
self.queues.append(proc)
return True
else:
self.occurred=False
return False |
Sample application demo program
The following program shows with three different models how the event
constructs can be used.
The first model (Pavlov's) shows the repeated simultaneous activation of any
number of processes (here: 4 dogs) by another process (Pavlov, the bell ringer)
through an event (bell).
The second model (PERT) is a fragment from a potential PERT simulation where
one process (the TotalJob instance) waits for the completion of a number of
parallel processes (Activity instances) of different duration.
The third model (Intersection) shows the use of events as semaphores for
critical sections. Cars arriving at random times at a US-style 4-way stop
intersection are synchronized by an event (intersectionFree) FIFO-style so that
at any one time, at most one car is in the intersection.
(This model could of course be cleanly implemented with the intersection as a
Resource instance.)
#!/usr/bin/env python
#testEvents.py
from SimPy.Simulation import *
from Events import *
""" Pavlov's drooling dogs.
Scenario: Four dogs wait for the bell to ring and start to drool
when their hear it.
"""
class BellMan(Process):
def ring(self):
while True:
bell.set()
print "%s %s rings bell"%(now(),self.name)
yield hold,self,5
class PavlovDog(Process):
def behave(self):
while True:
if bell.wait(self):
yield passivate,self
print "%s %s drools"%(now(),self.name)
initialize()
bell=Event("bell")
for i in range(4):
p=PavlovDog("Dog %s"%(i+1))
activate(p,p.behave())
b=BellMan("Pavlov")
activate(b,b.ring())
print "\n Pavlov's dogs"
simulate(until=10)
"""PERT simulation.
Sneraio: A job takes 10 parallel activities of different duration
to complete before it is done.
"""
class Activity(Process):
def __init__(self,name):
Process.__init__(self,name)
self.event=Event("completion of %s"%self.name)
allEvents.append(self.event)
def perform(self):
yield hold,self,random.randint(1,100)
self.event.set()
print "%s Event '%s' fired"%(now(),self.event.name)
class TotalJob(Process):
def perform(self,allEvents):
for e in allEvents:
if e.wait(self):
yield passivate,self
# not waiting for any events anymore -- all events were set
print now(),"All done"
import random
initialize()
allEvents=[]
for i in range(10):
a=Activity("Activity %s"%(i+1))
activate(a,a.perform())
t=TotalJob()
activate(t,t.perform(allEvents))
print "\n PERT network simulation"
simulate(until=100)
"""Traffic intersection as critical region.
Scenario: 20 cars crossing a US-style four-way stop intersection
are simulated. On such intersections, only one car is allowed
on the intersection. The others have to wait until the intersection
is clear. They cross in FIFO order.
"""
class Car(Process):
def drive(self):
if intersectionFree.queue(self): #does car have to queue for intersection?
# yes; car process has been queued
print "%s %s waiting to enter intersection"%(now(),self.name)
yield passivate,self #Process waiting in queue
# process out of queue
# Intersection free, enter . .
### Begin Critical Section
yield hold,self,1 #drive across
print "%s %s crossed intersection"%(now(),self.name)
### End Critical Section
intersectionFree.set()
initialize()
intersectionFree=Event("Intersection")
intersectionFree.set()
arrtime=0.0
for i in range(20):
c=Car("Car %s"%(i+1))
activate(c,c.drive(),at=arrtime)
arrtime+=0.2
print "\n Critical section/semaphore"
simulate(until=100)
OUTPUT:
Pavlov's dogs
0 Pavlov rings bell
0 Dog 1 drools
0 Dog 2 drools
0 Dog 3 drools
0 Dog 4 drools
5 Pavlov rings bell
5 Dog 1 drools
5 Dog 2 drools
5 Dog 3 drools
5 Dog 4 drools
10 Pavlov rings bell
10 Dog 1 drools
10 Dog 2 drools
10 Dog 3 drools
10 Dog 4 drools
PERT network simulation
10 Event 'completion of Activity 4' fired
25 Event 'completion of Activity 7' fired
31 Event 'completion of Activity 1' fired
37 Event 'completion of Activity 10' fired
48 Event 'completion of Activity 3' fired
76 Event 'completion of Activity 2' fired
92 Event 'completion of Activity 5' fired
93 Event 'completion of Activity 6' fired
94 Event 'completion of Activity 8' fired
100 Event 'completion of Activity 9' fired
100 All done
Critical section/semaphore
0.2 Car 2 waiting to enter intersection
0.4 Car 3 waiting to enter intersection
0.6 Car 4 waiting to enter intersection
0.8 Car 5 waiting to enter intersection
1.0 Car 6 waiting to enter intersection
1.0 Car 1 crossed intersection
1.2 Car 7 waiting to enter intersection
. . . . (some output removed
. . . .
14.0 Car 14 crossed intersection
15.0 Car 15 crossed intersection
16.0 Car 16 crossed intersection
17.0 Car 17 crossed intersection
18.0 Car 18 crossed intersection
19.0 Car 19 crossed intersection
20.0 Car 20 crossed intersection
|
Download
If you want to experiment with these experimental constructs yourself,
download here:
|
