|
| |
Modelling request/release of multiple Resource units
(Author: Klaus G. Muller; kgmuller at users.sourceforge.net)
This recipe shows how to program multiple SimPy Resource unit
requests/releases correctly and safely.
There are many modelling scenarios where a process requires multiple units of
a Resource. SimPy's 'yield request'
and 'yield release' statements
only allow requesting or releasing one unit at a time.
The naive approach of just repeated executing a 'yield
request' statement without proper guards (enforcing correct
preconditions) can lead to synchronization problems like deadlocks.
Consider the following situation during the run of a SimPy script with that
naive approach:
|
(in process #1, at time x) |
(in process #2, at time x) |
|
for
i in
range(nrUnitsNeeded): |
for
i in
range(nrUnitsNeeded): |
|
yield
request,self,myResource |
yield
request,self,myResource |
|
yield
hold,self,processingTime |
yield
hold,self,processingTime |
|
for
i in
range(nrUnitsNeeded): |
for
i in
range(nrUnitsNeeded): |
|
yield
release,self,myResource |
yield
release,self,myResource |
Here, two Process instances attempt to request the same number of Resource
units at the same time. If the 'yield
request' statements are executed in an interspersed manner (one from
process #1, one from process #2, one from process #1, etc.), this will lead to
both processes being blocked (deadlocked) if
myResource has just enough units to satisfy the needs of one of the two
processes. You must remember that SimPy makes no guarantees concerning the
execution sequence of simultaneous events!
If one wants to make the allocation of a number of Resource units atomic,
i.e., allocate either all or none of the units requested, one must ensure
multiple exclusion for parallel processes trying to enter the critical region
(the for loop). This can be done
by using a semaphore, a Resource instance with a capacity of 1.
If the number of units is insufficient, a process must not enter the critical
region, but wait and retry when the number of units is sufficient.
These two requirements lead to the following design pattern for secure
multi-unit requests:
semaphoreA=Resource(capacity=1)
. . . .
def
availableA(): return
resA.n>=needA
while
True:
if
availableA():
yield
request,self,semaphoreA ## enough units available, begin atomic transaction
for
i in
range(needA):
yield
request,self,resA
yield
release,self,semaphoreA ## end atomic transaction
break
else:
yield
waituntil,self,availableA
# process now has 'needA' units from Resource resA
Let's apply this pattern in a simple model
scenario: User processes require multiple units from two resources to do their
processing. Here is a program implementation:
#!/usr/bin/env python
__doc__="""
Scenario/Purpose:
To show use of multiple resource units fom multiple resources.
"""
from SimPy.Simulation import *
###########################################################################
### Model components (classes, functions)
###########################################################################
class User(Process):
def __init__(self,name,priority):
Process.__init__(self,name)
self.priority=priority
def use(self):
needA=2
needB=4
processTime=5
def availableA():
return resA.n>=needA
def availableB():
return resB.n>=needB
while True:
if availableA():
yield request,self,semaphoreA ## begin atomic transaction
for i in range(needA):
assert resA.n>0,"Process %s requesting non-available unit at %s"%(self.name,now())
yield request,self,resA,self.priority
yield release,self,semaphoreA ## end atomic transaction
break
else:
yield waituntil,self,availableA
while True:
if availableB():
yield request,self,semaphoreB ## begin atomic transaction
for i in range(needB):
yield request,self,resB,self.priority
yield release,self,semaphoreB ## end atomic transaction
break
else:
yield waituntil,self,availableB
## user now has resources which he needs
yield hold,self,processTime
for i in range(needB):
yield release,self,resB
for i in range(needA):
yield release,self,resA
print "%s: User %s finished"%(now(),self.name)
initialize()
resA=Resource(capacity=5,name="Resource A")
semaphoreA=Resource(capacity=1,name="SemaphoreA")
resB=Resource(capacity=10,name="Resource B")
semaphoreB=Resource(capacity=1,name="SemaphoreB")
resB
for i in range(10):
u=User(name=i,priority=i)
activate(u,u.use())
simulate(until=1000)
Output when run:
5: User 0 finished
5: User 1 finished
10: User 2 finished
10: User 3 finished
15: User 4 finished
15: User 5 finished
20: User 6 finished
20: User 7 finished
25: User 8 finished
25: User 9 finished
|
For a small number of units requested, this approach is acceptable. For
larger numbers (hundred, thousands, . . .), though, its runtime efficiency is
poor -- the multiple request/release statements produce a lot of overhead.
If the user community finds a multi-unit request capability important for
SimPy, it can be implemented efficiently and added to future SimPy versions.
|
