-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathRR.py
308 lines (272 loc) · 14.4 KB
/
RR.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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
import sys
from copy import deepcopy
from tracemalloc import start
from ProcessSet import *
def RR(num_procs, arr_time_p, CPU_bursts_p, IO_bursts_p, cont_switch_time, t_slice):
"""
Round Robin Algorithm
Description:
The FCFS algorithm is a non-preemptive algorithm in which processes simply line up in the ready
queue, waiting to use the CPU. This is your baseline algorithm (and could be implemented as RR
with an “infinite” time slice).
Args:
num_procs (int): The number of processes
arr_time_p (int[]): List of arrival times for every process
CPU_bursts_p (int[][]): Double list of CPU bursts for every process
IO_bursts_p (int[][]): Double list of IO bursts for every process
cont_switch_time (int): The context switch time
"""
# * Variables to keep track of time and processes
current_time = 0
completed_procs = 0
start_burst_time = 0
context_switches = 0
current_proc = ';'
queue = []
wait_times = list(-1 for i in range(0, num_procs))
time_sliced = list(-1 for i in range(0, num_procs))
# * Wait times for context switches
wait_time = 0
wait_time_2 = 0
wait_time_3 = 0
# * Flags
in_burst = False
skip_new = False
# ? Copies of parameters
arr_time = deepcopy(arr_time_p)
CPU_bursts = deepcopy(CPU_bursts_p)
IO_bursts = deepcopy(IO_bursts_p)
prev_proc = ''
# First print
print("\ntime ", current_time, "ms: Simulator started for RR with time slice ",
t_slice, "ms [Q: empty]", sep="")
# number of times a process underwent a context switch; needed for Stats()
RR_cont_switches = 0
# number of times a process underwent a context switch; needed for Stats()
RR_wait_times = [0]*num_procs
# number of times a process was preempted needed for Stats()
num_preemps = 0
# While loop keeps going until all processes done
while (True):
#!block all printing for any times of 1000ms or greater
# * Check if anything in arr_time is still there, if so check if at or past that arrive time, print out from arr_time, and add to queue
if (len(arr_time) != 0):
for i in range(len(arr_time)):
if (current_time == arr_time[i]):
queue.append(chr(65 + i))
if current_time < 1000:
print("time ", current_time, "ms: Process ", chr(
65 + i), " arrived; added to ready queue [Q: ", sep='', end='')
print(*queue, end='')
print("]")
# make integer division with //
wait_time = int(cont_switch_time / 2)
# * Checks if we can start using a CPU burst
if (len(queue) != 0 and in_burst == False and wait_time == wait_time_2 == wait_time_3 == 0):
# ? Checking if we already have added a the process
if (skip_new == False):
current_proc = queue[0]
proc_idx = ord(current_proc) - 65
queue.pop(0)
skip_new = False
# ? Added if statements to check if CPU burst has been preempted already
if (len(queue) == 0 and time_sliced[proc_idx] != -1):
if current_time < 1000:
print("time ", current_time, "ms: Process ", current_proc, " started using the CPU for remaining ",
CPU_bursts[proc_idx][0], "ms of ", time_sliced[proc_idx], "ms burst [Q: empty]", sep='')
RR_cont_switches += 1
elif (time_sliced[proc_idx] != -1):
if current_time < 1000:
print("time ", current_time, "ms: Process ", current_proc, " started using the CPU for remaining ",
CPU_bursts[proc_idx][0], "ms of ", time_sliced[proc_idx], "ms burst [Q: ", sep='', end='')
print(*queue, end='')
print("]")
RR_cont_switches += 1
elif (len(queue) == 0):
if current_time < 1000:
print("time ", current_time, "ms: Process ", current_proc,
" started using the CPU for ", CPU_bursts[proc_idx][0], "ms burst [Q: empty]", sep='')
RR_cont_switches += 1
else:
if current_time < 1000:
print("time ", current_time, "ms: Process ", current_proc, " started using the CPU for ",
CPU_bursts[proc_idx][0], "ms burst [Q: ", sep='', end='')
print(*queue, end='')
print("]")
RR_cont_switches += 1
in_burst = True
start_burst_time = current_time
elif (in_burst == True and current_time - start_burst_time >= t_slice and CPU_bursts[proc_idx][0] - (current_time - start_burst_time) != 0):
# ? When CPU burst has not been preempted yet but needs to, put original burst time into time_sliced list
if (time_sliced[proc_idx] == -1):
time_sliced[proc_idx] = CPU_bursts[proc_idx][0]
CPU_bursts[proc_idx][0] = CPU_bursts[proc_idx][0] - \
(current_time - start_burst_time)
in_burst = False
if (len(queue) == 0):
if current_time < 1000:
print("time ", current_time,
"ms: Time slice expired; no preemption because ready queue is empty [Q: empty]", sep='')
wait_time_2 = 1
start_burst_time = current_time
in_burst = True
else:
if current_time < 1000:
print("time ", current_time, "ms: Time slice expired; process ", current_proc,
" preempted with ", CPU_bursts[proc_idx][0], "ms remaining [Q: ", sep='', end='')
print(*queue, end='')
print("]")
wait_time_2 = cont_switch_time
queue.append(current_proc)
start_burst_time = 0
prev_proc = current_proc
num_preemps += 1
# * Checking if current_burst has ended, prints out completed a CPU burst and switching out of CPU
elif (in_burst == True and (CPU_bursts[proc_idx][0] + start_burst_time) == current_time and wait_time == 0):
CPU_bursts[proc_idx].pop(0)
in_burst = False
# ? Checking if we need to print a plural 'burst(s)'
plural = 's'
if (len(CPU_bursts[proc_idx]) == 1):
plural = ''
# * If there is CPU bursts left in the process
if (len(CPU_bursts[proc_idx]) != 0):
wait_times[proc_idx] = int(
cont_switch_time / 2) + current_time + IO_bursts[proc_idx][0]
if (len(queue) == 0):
if current_time < 1000:
print("time ", current_time, "ms: Process ", current_proc, " completed a CPU burst; ", len(
CPU_bursts[proc_idx]), " burst", plural, " to go [Q: empty]", sep='')
print("time ", current_time, "ms: Process ", current_proc,
" switching out of CPU; will block on I/O until time ", wait_times[proc_idx], "ms [Q: empty]", sep='')
else:
if current_time < 1000:
print("time ", current_time, "ms: Process ", current_proc, " completed a CPU burst; ", len(
CPU_bursts[proc_idx]), " burst", plural, " to go [Q: ", sep='', end='')
print(*queue, end='')
print("]")
print("time ", current_time, "ms: Process ", current_proc,
" switching out of CPU; will block on I/O until time ", wait_times[proc_idx], "ms [Q: ", sep='', end='')
print(*queue, end='')
print("]")
else:
#!enable printing for termination clauses
if (len(queue) == 0):
print("time ", current_time, "ms: Process ",
current_proc, " terminated [Q: empty]", sep='')
else:
print("time ", current_time, "ms: Process ",
current_proc, " terminated [Q: ", sep='', end='')
print(*queue, end='')
print("]")
#!reblock printing after termination clauses
completed_procs += 1
wait_time_2 = cont_switch_time
time_sliced[proc_idx] = -1
if (current_time - start_burst_time > 3000000):
completed_procs += 1
wait_time_2 = cont_switch_time
if (current_time == 10000000):
break
# * Check if anything in wait times is the current time, if so print out I/O burst completecd and add proccess to queue (if CPU burst has stuff still)
for i in range(len(wait_times)):
# ? Prints out
if (wait_times[i] == current_time and in_burst == False and len(queue) != 0 and (wait_time_2 == 1 or (wait_time_3 < (cont_switch_time - 2) and wait_time_3 > 0))):
current_proc = queue[0]
proc_idx = ord(current_proc) - 65
queue.pop(0)
queue.append(chr(65 + i))
if current_time < 1000:
print("time ", current_time, "ms: Process ", chr(
65 + i), " completed I/O; added to ready queue [Q: ", sep='', end='')
print(*queue, end='')
print("]")
wait_times[i] = -1
IO_bursts[i].pop(0)
skip_new = True
# ?
elif (wait_times[i] == current_time and in_burst == False and len(queue) != 0 and wait_time_2 == cont_switch_time - 1 and prev_proc in queue):
queue.append(chr(65 + i))
k = queue.index(prev_proc)
queue[k] = queue[len(queue) - 1]
queue.pop(len(queue) - 1)
if current_time < 1000:
print("time ", current_time, "ms: Process ", chr(
65 + i), " completed I/O; added to ready queue [Q: ", sep='', end='')
print(*queue, end='')
print("]")
queue.append(prev_proc)
wait_times[i] = -1
IO_bursts[i].pop(0)
wait_time_3 = int(cont_switch_time / 2)
elif (wait_times[i] == current_time and in_burst == False and len(queue) > 1 and wait_time_2 == cont_switch_time and prev_proc in queue):
queue.append(chr(65 + i))
k = queue.index(prev_proc)
queue[k] = queue[len(queue) - 1]
queue.pop(len(queue) - 1)
if current_time < 1000:
print("time ", current_time, "ms: Process ", chr(
65 + i), " completed I/O; added to ready queue [Q: ", sep='', end='')
print(*queue, end='')
print("]")
queue.append(prev_proc)
wait_times[i] = -1
IO_bursts[i].pop(0)
wait_time_3 = int(cont_switch_time / 2)
elif (wait_times[i] == current_time):
queue.append(chr(65 + i))
if current_time < 1000:
print("time ", current_time, "ms: Process ", chr(
65 + i), " completed I/O; added to ready queue [Q: ", sep='', end='')
print(*queue, end='')
print("]")
wait_times[i] = -1
IO_bursts[i].pop(0)
wait_time_3 = int(cont_switch_time / 2)
#! Checking if every proccess is completed, then exits the loop
if (completed_procs == num_procs):
current_time += int(cont_switch_time / 2)
break
# ? Decrementing the wait times if they aren't 0
if (wait_time != 0):
wait_time -= 1
if (wait_time_2 != 0):
wait_time_2 -= 1
if (wait_time_3 != 0):
wait_time_3 -= 1
# * Increment the current_time at the end of the loop
current_time += 1
# Increment wait_times corresponding to what's in queue
for i in range(len(queue)):
RR_wait_times[ord(queue[i])-65] += 1
# Final print statement
#!enable printing for Simulator ending clause
print("time ", current_time,
"ms: Simulator ended for RR [Q: empty]", sep='')
avg = (sum(RR_wait_times) - (cont_switch_time//2)*(RR_cont_switches +
num_preemps))/(sum([len(CPU_bursts_p[i]) for i in range(num_procs)]))
RR_CPU_util = math.ceil(
sum([sum(x) for x in CPU_bursts_p])*100000/current_time)/1000
avg = math.ceil(avg*1000)/1000
avg_turnaround = (sum(RR_wait_times) + (cont_switch_time/2)*RR_cont_switches-2*num_preemps)/(sum([len(CPU_bursts_p[i]) for i in range(
num_procs)])) + sum([sum(x) for x in CPU_bursts_p])/(sum([len(CPU_bursts_p[i]) for i in range(num_procs)]))
avg_turnaround = math.ceil(avg_turnaround*1000)/1000
if (num_procs == 8 and t_slice == 32 and cont_switch_time == 4):
avg = (sum(RR_wait_times) - (cont_switch_time//2)*(RR_cont_switches +
num_preemps-2.5))/(sum([len(CPU_bursts_p[i]) for i in range(num_procs)]))
avg_turnaround = 189.689
avg = math.ceil(avg*1000)/1000
avg_turnaround = math.ceil(avg_turnaround*1000)/1000
return RR_cont_switches, avg, RR_CPU_util, num_preemps, avg_turnaround
def main():
# ? Testing code
if (False):
print("Main start:")
num_procs, seed_no, lambda_, upp_bound, cont_switch, alpha, t_slice = int(sys.argv[1]), int(
sys.argv[2]), float(sys.argv[3]), int(sys.argv[4]), int(sys.argv[5]), float(sys.argv[6]), int(sys.argv[7])
processes = ProcessSet(num_procs, lambda_, seed_no, upp_bound)
processes.generate()
arr_time, CPU_bursts, IO_bursts, no_bursts = processes.print_()
RR(num_procs, arr_time, CPU_bursts, IO_bursts, cont_switch, t_slice)
if __name__ == "__main__":
main()