-
Notifications
You must be signed in to change notification settings - Fork 3
/
n-MM1K.py
184 lines (152 loc) · 6.53 KB
/
n-MM1K.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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
# -*- coding: utf-8 -*-
"""
Created on Sat May 30 2020
Module for n*M/M/1/K queue problem, with the assumption that each queue share the same pool.
@author: Almas Fauzia
Gregorius Aria Neruda
Rayhan Naufal Ramadhan
"""
import random
import queue
import math
import csv
import sys
class Event:
def __init__(self, eventType, queue_label):
self.eventType = eventType
self.rate = CDF_inverse(random.random())
self.queue_label = queue_label # denotes which M/M/1
# if eventType == arrival, rate is the time needed until the next customer arrives
# if eventType == service, rate is the time needed for server to serve the customer that is in it
def decrease_rate(tempEvent, listOfEvents):
for event in listOfEvents:
event.rate -= tempEvent.rate
# writer.writerow([f'[Time: {str(time)}] Remaining {event.eventType} time in Queue {event.queue_label}: {str(event.rate)}'])
return listOfEvents
# function to calculate rate from exponential distribution
def CDF_inverse(CDF):
return -1 * math.log(1-CDF) / exp_dist_lambda
def init_queue(queue_label):
global custArrive
global custServiced
global time
global n
global i
global listOfEvents
i += 1
custArrive = i
queues[queue_label].put_nowait(custArrive)
n -= 1
writer.writerow(
[f'[Time: {str(time)}] Customer{str(custArrive)} is entering Queue {queue_label}.'])
newEvent = Event('arrival', queue_label)
listOfEvents.append(newEvent)
# writer.writerow([f'[Time: {str(time)}] Next {newEvent.eventType} for Queue {queue_label} in {str(newEvent.rate)}'])
custServiced = queues[queue_label].get_nowait()
servers[queue_label].put_nowait(custServiced)
writer.writerow(
[f'[Time: {str(time)}] Customer{str(custServiced)} is being served in server (Queue {queue_label}).'])
newEvent = Event('service', queue_label)
listOfEvents.append(newEvent)
# writer.writerow([f'[Time: {str(time)}] Next completed {newEvent.eventType} for Queue {queue_label} in {str(newEvent.rate)}'])
def start_queue(queue_label, temp):
global custArrive
global custServiced
global time
global n
global i
global listOfEvents
global haventArrived
global dropped
if temp.eventType == 'arrival':
i += 1
custArrive = i
time += temp.rate
listOfEvents.remove(temp)
# if the arrival happens because of other than haventArrived situation
if not haventArrived:
listOfEvents = decrease_rate(temp, listOfEvents)
newEvent = Event('arrival', queue_label)
try:
queues[queue_label].put_nowait(custArrive)
writer.writerow(
[f'[Time: {str(time)}] Customer{str(custArrive)} is entering Queue {queue_label}.'])
# if there is no queue, the new customer will be straight to the server
if queues[queue_label].qsize() == 1 and not servers[queue_label].full():
custServiced = queues[queue_label].get_nowait()
servers[queue_label].put_nowait(custServiced)
writer.writerow(
[f'[Time: {str(time)}] Customer{str(custServiced)} is being served in server (Queue {queue_label}).'])
except Exception:
writer.writerow(
[f'[Time: {str(time)}] Queue is full, Customer{str(custArrive)} is dropped from Queue {queue_label}.'])
dropped.append(custArrive)
else:
time += temp.rate
newEvent = Event('service', queue_label)
listOfEvents.remove(temp)
listOfEvents = decrease_rate(temp, listOfEvents)
custServiced = servers[queue_label].get_nowait()
writer.writerow(
[f'[Time: {str(time)}] Customer{str(custServiced)} is leaving Queue {queue_label}.'])
# if the next customer have arrived, the next customer is entering the server
if not queues[queue_label].empty():
custServiced = queues[queue_label].get_nowait()
servers[queue_label].put_nowait(custServiced)
writer.writerow(
[f'[Time: {str(time)}] Customer{str(custServiced)} is being served in server (Queue {queue_label}).'])
listOfEvents.append(newEvent)
# if (newEvent.eventType == 'arrival'):
# writer.writerow([f'[Time: {str(time)}] Next {newEvent.eventType} for Queue {queue_label} in {str(newEvent.rate)}'])
# else:
# writer.writerow([f'[Time: {str(time)}] Next completed {newEvent.eventType} for Queue {queue_label} in {str(newEvent.rate)}'])
n -= 1
haventArrived = False
def main():
for i in range(QUEUES):
queues.append(queue.Queue(QUEUE_SIZE))
servers.append(queue.Queue(1))
init_queue(i)
while n > 0:
# restore events
for event in eventsOnHold:
eventsOnHold.remove(event)
listOfEvents.append(event)
# take the first coming event from queue
temp = sorted(listOfEvents, key=lambda event: event.rate)[0]
# search for an arrival event if temp is service event but the next customer have not arrived yet
while (temp.eventType == 'service') & (queues[temp.queue_label].empty()) & (servers[temp.queue_label].empty()):
# writer.writerow([f'[Time: {str(time)}] Next customer have not arrived yet in Queue {temp.queue_label}.'])
haventArrived = True
eventsOnHold.append(temp)
listOfEvents.remove(temp)
temp = sorted(listOfEvents, key=lambda event: event.rate)[0]
start_queue(temp.queue_label, temp)
if __name__ == '__main__':
try: # Global variables
# maximum number of customers inside queue (K-1), set to `0` if infinite
QUEUE_SIZE = int(sys.argv[2])
# number of M/M/1 queues (n)
QUEUES = int(sys.argv[1])
exp_dist_lambda = 0.5
custArrive = 0
custServiced = 0
n = 50 # number of events
i = 0 # customer id
time = 0
dropped = []
queues = []
servers = []
listOfEvents = []
eventsOnHold = [] # list to store events on-hold
haventArrived = False
# build .csv file to save the log
file = open('logN-MM1K.csv', 'w', newline='')
writer = csv.writer(file)
main()
except IndexError:
print("One or more arguments is missing \n")
print("usage: python ./n-MM1K.py <n> <K> \n")
print("- c : number of M/M/1 queues")
print("- K : maximum number of customers in queue (excluding customer being served) \n")
sys.exit(1)