-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithms.py
101 lines (89 loc) · 2.51 KB
/
algorithms.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
def first_come_first_serve(data):
arrival_time = []
index = 0
for i in data:
arrival_time.append([i['at'], i['id'], index])
index += 1
arrival_time.sort()
curr_time = 0
for val in arrival_time:
if data[val[2]]['at'] > curr_time:
curr_time += data[val[2]]['at'] - curr_time
curr_time += data[val[2]]['bt']
data[val[2]]['ct'] = curr_time
return data
def round_robin(data, tq):
rr = []
index = 0
curr_time = 0
flag = True
for dct in data:
rr.append([dct['at'], dct['bt'], index])
index += 1
while flag:
for i in range(len(rr)):
bt = rr[i][1]
if bt != 0 and rr[i][0] < curr_time or curr_time == 0:
if bt > tq:
rr[i][1] -= tq
curr_time += tq
else:
rr[i][1] = 0
curr_time += bt
data[rr[i][2]]['ct'] = curr_time
flg = True
for i in rr:
if not i[1] == 0:
flg = False
if flg:
flag = False
return data
def shortest_job_first(data):
sjf = []
index = 0
curr_time = 0
for dct in data:
sjf.append([dct['bt'], dct['at'], index])
index += 1
sjf.sort()
while sjf:
for val in sjf:
if val[1] <= curr_time:
curr_time += data[val[2]]['bt']
data[val[2]]['ct'] = curr_time
sjf.remove(val)
return data
def shortest_remaining_time(data):
def find_min_rt_arrived(curr_time, lst):
lst.sort(key=lambda x: x[1])
for i in lst:
if curr_time >= i[0]:
return i[2], True
def all_done(lst):
for i in lst:
if i[1] != 0:
return False
return True
def reduce_bt(indx, lst):
for i in range(len(lst)):
if lst[i][-1] == indx:
lst[i][1] -= 1
if lst[i][1] == 0:
del lst[i]
return lst, True
return lst, False
srtf = []
indx = 0
curr_time = 0
for dct in data:
srtf.append([dct['at'], dct['bt'], indx])
indx += 1
srtf.sort()
while not all_done(srtf):
index, has_arrived = find_min_rt_arrived(curr_time, srtf)
if has_arrived:
curr_time += 1
srtf, is_done = reduce_bt(index, srtf)
if is_done:
data[index]['ct'] = curr_time
return data