forked from adrielklein/MM1-QUEUE
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMM1Queue.py
158 lines (141 loc) · 7.27 KB
/
MM1Queue.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
'''
MM1Queue
Created on Feb 16, 2013
@author: adrielklein
This module defines an MM1 Queuing System Simulator. Three class are defined in this module: Request, Controller, and Monitor.
The Request object represents a request which enters the system (gets born), waits in a queue, gets served, and leaves (dies).
Each request object has a record of its birth time, time at which it was serviced, and time at which it was born.
The Controller object is what manages the requests. the controller puts new requests into the queue and services each request
once it is at the front of the queue.
The Monitor object keeps records statistics about the queuing system at various points in time. The monitor gets information
about the system when the controller sends it a snapshot of the system.
So there is one instance of a Controller, one instance of a Monitor, and many instances of a request. The controller continually
creates new requests according to an exponential distributed arrival rate and continually serves the requests according to an exponentially
distributed service rate.
This is a single server queue so there can be at most one request being served at a given time. Incoming requests are served on a first-come
first-serve basis.
'''
from __future__ import division #Required for floating point division.
from heapq import heappush, heappop #Required for heap operations of schedule.
from NumberGenerator import exponentialValue # Required to generate exponentially distributed random numbers
class Controller:
def __init__(self, arrivalRate, averageServiceTime, simulationTime):
self.arrivalRate = arrivalRate
self.serviceRate = 1/averageServiceTime
self.simulationTime = simulationTime
self.time = 0
self.queue = [] # A queue of events waiting to be served
self.beingServed = None # The request being served. None if no request is being served.
self.monitor = Monitor() # Collects information about the state of the queue.
# Schedule is a heap with times as keys and events as values.
# The events will be representing by the following strings:
# "Birth", "Death", and "Monitor"
self.schedule = []
def runSimulation(self, monitorStartingTime):
self.monitorStartingTime = monitorStartingTime
#Add first Birth event to schedule
heappush(self.schedule, (exponentialValue(self.arrivalRate), "Birth"))
#Add first Monitor event to schedule.
heappush(self.schedule, (monitorStartingTime, "Monitor"))
while self.time < self.simulationTime:
#Get the next event from the schedule
pair = heappop(self.schedule)
self.time = pair[0]
event = pair[1]
self.executeEvent(event)
def executeEvent(self,event):
if event =="Birth":
#Create new request and enqueue
newRequest = Request(self.time)
self.queue.append(newRequest)
#Schedule next birth
timeOfNextBirth = self.time + exponentialValue(self.arrivalRate)
heappush(self.schedule, (timeOfNextBirth, "Birth"))
# If queue only has one request and no requests are being served, then
# dequeue the request, start serving request, and schedule death
if len(self.queue) == 1 and self.beingServed == None:
request = self.queue.pop(0)
request.setServiceTime(self.time)
self.beingServed = request
#Schedule a death
deathTime = self.time + exponentialValue(self.serviceRate)
heappush(self.schedule, (deathTime, "Death"))
elif event == "Death":
recentlyDied = self.beingServed
recentlyDied.setDeathTime(self.time)
if self.time > self.monitorStartingTime:
self.monitor.recordDeadRequest(recentlyDied)
self.beingServed = None
# Now there are no requests being served. If queue is empty, do nothing. Otherwise serve next request.
if len(self.queue) != 0:
request = self.queue.pop(0)
request.setServiceTime(self.time)
self.beingServed = request
#Schedule a death
deathTime = self.time + exponentialValue(self.serviceRate)
heappush(self.schedule, (deathTime, "Death"))
else:
#This must be a monitor event
requestsWaiting = len(self.queue)
requestsInSystem = requestsWaiting
if self.beingServed != None:
requestsInSystem += 1
self.monitor.recordSnapshot(requestsWaiting, requestsInSystem)
#Schedule next monitor event.
nextMonitorTime = self.time + exponentialValue(self.arrivalRate/2)
heappush(self.schedule, (nextMonitorTime, "Monitor"))
class Request:
def __init__(self, birthTime):
self.birthTime = birthTime
def setServiceTime(self, serviceTime):
self.serviceTime = serviceTime
def setDeathTime(self, deathTime):
self.deathTime = deathTime
def getWaitingTime(self):
return self.serviceTime - self.birthTime
def getQueuingTime(self):
return self.deathTime - self.birthTime
class Monitor:
def __init__(self):
self.numSnapshots = 0
self.numRequests = 0
self.requestsWaiting = []
self.requestsInSystem = []
self.waitingTimes = []
self.queuingTimes = []
def recordSnapshot(self, requestsWaiting, requestsInSystem):
self.numSnapshots += 1
self.requestsWaiting.append(requestsWaiting)
self.requestsInSystem.append(requestsInSystem)
def recordDeadRequest(self, request):
self.numRequests += 1
self.waitingTimes.append(request.getWaitingTime())
self.queuingTimes.append(request.getQueuingTime())
def printReport(self):
print "Average Requests Waiting: " + str(sum(self.requestsWaiting)/self.numSnapshots)
print "Average Requests In System: " + str(sum(self.requestsInSystem)/self.numSnapshots)
print "Average Waiting Time: " + str(sum(self.waitingTimes)/self.numRequests)
print "Average Queuing Time: " + str(sum(self.queuingTimes)/self.numRequests)
print "Lambda = 50 and Ts = 0.015"
# Get controller ready for a simulation with the given Lambda, Ts, and simulation time of 400.
myController = Controller(50, 0.015, 400)
# Begin the simulation and start monitoring system at time 100.
myController.runSimulation(100)
#Print the results of the simulation
myController.monitor.printReport()
print
print "Lambda = 60 and Ts = 0.015"
# Get controller ready for a simulation with the given Lambda, Ts, and simulation time of 400.
myController = Controller(60, 0.015, 400)
# Begin the simulation and start monitoring system at time 100.
myController.runSimulation(100)
#Print the results of the simulation
myController.monitor.printReport()
print
print "Lambda = 60 and Ts = 0.02"
# Get controller ready for a simulation with the given Lambda, Ts, and simulation time of 400.
myController = Controller(60, 0.02, 400)
# Begin the simulation and start monitoring system at time 100.
myController.runSimulation(100)
#Print the results of the simulation
myController.monitor.printReport()