|
| |
Typical model scenario: a process requests a resource and wants to
leave before acquiring the resource, e.g. because the wait gets too long
("timeout reneging") or because it could get quicker service by another resource
with a shorter queue ("conditional reneging").
Problem: SimPy passivates processes waiting for a resource. Waiting
processes therefore cannot take any decisions, such as reneging.
A solution approach: One solution is to associate another process with
a waiting process which can take the decision to renege, remove that process
from the waiting queue and reactivate the process.
Implementation
This approach will be demonstrated by two examples, one for timeout reneging
and one for conditional reneging.
Timeout reneging example
The scenario is simple: Resource customers arrive and request the
resource. after a period of patience time units, a process waiting for a
resource reneges (leaves the queue). Here is the code:
001 #! /usr/local/bin/python
002 """ Example for reneging with timeout.
003 Customers leave a queue when they have not been served after
004 a certain time.
005 """
006 from SimPy.Simulation import *
007
008 class Requestor(Process):
009 def gotResource(self,resource):
010 """Tests whether the resource has been acquired"""
011 result=self in resource.activeQ
012 # If this process got the resource
013 if result:
014 #Acquired, so cancel alarm
015 self.cancel(self.al)
016 else:
017 #not acquired, so get out of queue, renege
018 resource.waitQ.remove(self)
019 if resource.monitored:
020 resource.waitMon.observe(len(resource.waitQ),t=now())
021 return result
022
023 def setAlarm(self,delay):
024 """Activates the Alarm process"""
025 self.al=Alarm("Alarm")
026 activate(self.al,self.al.wakeup(delay=1,whom=self))
027
028 def use(self,resource,patience):
029 """The process which requests a resource and reneges when it has
030 not acquired it within a certain time"""
031 self.setAlarm(delay=patience)
032 yield request,self,resource
033 if self.gotResource(resource):
034 print "%s +++ %s got resource"%(now(),self.name)
035 yield hold,self,2
036 yield release,self,resource
037 print "%s --- %s released resource"%(now(),self.name)
038 else:
039 print "%s <<< %s reneged"%(now(),self.name)
040
041 class Alarm(Process):
042 """The trigger process which reactivates a process
043 when the reneging delay time has passed"""
044 def wakeup(self,delay,whom):
045 yield hold,self,delay
046 reactivate(whom)
047 yield hold,self
048
049 initialize()
050 res=Resource(capacity=3,monitored=True)
051 for i in range(6):
052 r=Requestor("Requestor %s"%i)
053 activate(r,r.use(resource=res,patience=1))
054 simulate(until=20)
Output:
0 +++ Requestor 0 got resource
0 +++ Requestor 1 got resource
0 +++ Requestor 2 got resource
1 <<< Requestor 3 reneged
1 <<< Requestor 4 reneged
1 <<< Requestor 5 reneged
2 --- Requestor 0 released resource
2 --- Requestor 1 released resource
2 --- Requestor 2 released resource
|
Explanation: Each of the six Requestor (line 008) instances has
a use process which requests a resource res (l. 050)
which has a capacity for serving three processes at the same time. A
Requestor process is prepared to wait at most patience (=1) time
units for the resource. When requesting the resource (l. 032), it starts (l.
031) an Alarm.wakeup process (l. which reactivates the Requestor
process after patience time units (l. 044). When the Requestor.use
process gets reactivated (l. 033), there are two possibilities
 | It has acquired the resource (self.gotResource(resource)==True,
l. 033) before the timeout. It has to cancel the Alarm.use
process. gotResource has already done that: After determining that
the resource was acquired (self in resource.activeQ, l. 011), it
cancels the Alarm.use process (l. 015). |
| It has timed out after patience time units and reneges.
gotResource already has taken the waiting process out of the queue (l.
018) and, in case the res resource is monitored, records the change
in wait queue length in the monitor (l. 020). |
The output shows that only the first three Requestor.use processes
acquire the resource. The next three all time out and renege.
Conditional reneging example
The scenario for this example is that there are two equivalent
resources. Resource customers arrive and queue for the first resource. When the
queue in the other resource is shorter than the number of waiting processes
ahead of them in the first queue, they renege and request the other resource.
001 #! /usr/local/bin/python
002 """Example for conditional reneging.
003 Customers change queues when less people in other queue
004 than number ahead of them in current queue.
005 """
006 from SimPy.Simulation import *
007
008 class Requestor(Process):
009 def gotResource(self,resource):
010 """Tests whether self got the requested resource"""
011 result=self in resource.activeQ
012 # result is True if self got the resource
013 if result:
014 #self got resource, so cancel trigger process
015 self.cancel(self.al)
016 else:
017 #trigger process fired before self got resource,
018 #get out of queue (renege)
019 resource.waitQ.remove(self)
020 if resource.monitored:
021 resource.waitMon.observe(len(resource.waitQ),t=now())
022 return result
023
024 def setReneger(self,condProc):
025 """Activates the reneging trigger process"""
026 self.al=ConditionalReneger("CondReneg")
027 activate(self.al,self.al.wait(condProc,self))
028
029 def use(self,resource,otherResource):
030 """The process requesting a resource and reneging when queue for
031 other resource shorter"""
032 self.otherResource=otherResource
033 self.resource=resource
034
035 def renegeCondition():
036 """return True, if nr ahead of self greater or equal nr in other queue"""
037 if self in self.resource.waitQ:
038 return len(self.otherResource.waitQ)<self.resource.waitQ.index(self)
039 else:
040 return False
041
042 self.setReneger(renegeCondition)
043 yield request,self,resource
044 print now(),"waitQ resource:",[x.name for x in self.resource.waitQ],\
045 "waitQ otherResource:",[x.name for x in self.otherResource.waitQ]
046 if self.gotResource(resource):
047 print "%s +++ %s got resource"%(now(),self.name)
048 yield hold,self,2
049 yield release,self,resource
050 print "%s --- %s released resource"%(now(),self.name)
051 else:
052 print "%s <<< %s reneged"%(now(),self.name)
053 yield request,self,self.otherResource
054 print now(),"waitQ resource:",[x.name for x in self.resource.waitQ],\
055 "waitQ otherResource:",[x.name for x in self.otherResource.waitQ]
056 print "%s %s got otherResource"%(now(),self.name)
057 yield hold,self,2
058 yield release,self,self.otherResource
059
060 class ConditionalReneger(Process):
061 """The trigger process which reactivates another process when the
062 reneging condition is True"""
063 def wait(self,condProc,whom):
064 yield waituntil,self,condProc
065 reactivate(whom)
066 yield hold,self
067
068 initialize()
069 res=Resource(capacity=1,monitored=True)
070 resOther=Resource(capacity=1,monitored=True)
071 for i in range(6):
072 r=Requestor("Requestor %s"%i)
073 activate(r,r.use(resource=res,otherResource=resOther),at=i*0.25)
074 simulate(until=10)
Output:
0 waitQ resource: [] waitQ otherResource: []
0 +++ Requestor 0 got resource
0.5 waitQ resource: ['Requestor 1', 'Requestor 2'] waitQ otherResource: []
0.5 <<< Requestor 2 reneged
0.5 waitQ resource: ['Requestor 1'] waitQ otherResource: []
0.5 Requestor 2 got otherResource
0.75 waitQ resource: ['Requestor 1', 'Requestor 3'] waitQ otherResource: []
0.75 <<< Requestor 3 reneged
1.25 waitQ resource: ['Requestor 1', 'Requestor 4', 'Requestor 5'] waitQ otherResource: ['Requestor 3']
1.25 <<< Requestor 5 reneged
2 --- Requestor 0 released resource
2 waitQ resource: ['Requestor 4'] waitQ otherResource: ['Requestor 3', 'Requestor 5']
2 +++ Requestor 1 got resource
2.5 waitQ resource: ['Requestor 4'] waitQ otherResource: ['Requestor 5']
2.5 Requestor 3 got otherResource
4 --- Requestor 1 released resource
4 waitQ resource: [] waitQ otherResource: ['Requestor 5']
4 +++ Requestor 4 got resource
4.5 waitQ resource: [] waitQ otherResource: []
4.5 Requestor 5 got otherResource
6 --- Requestor 4 released resource
|
Explanation: This example has the same structure as the timeout
example. The main difference is that the trigger process associated with
Requestor instances here fires based on a wait until condition (l. 064).
The condition for the wait until is encoded in method
renegeCondition
(l. 035) which returns
True if the number of waiting processes in the first queue ahead of self is
greater or equal the length of the other queue.
The output shows the changing from one queue to another based on queue length
(e.g. Requestor 2 at time 0.5).
|
