-
Notifications
You must be signed in to change notification settings - Fork 1
/
task_scheduler
executable file
·159 lines (137 loc) · 5.94 KB
/
task_scheduler
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
#! /usr/bin/python
import sys
from optparse import OptionParser
import re
running_task_list = []
ready_task_list = []
waiting_task_list = []
finish_event_list = []
task_length_dict = {}
task_children_dict = {} #each item in it is a <task_id, children_list>
task_dependency_list_dict = {} #each item in it is a <task_id, dependency_list>
#each task should contains the task id, task length, task dependency
#keep tracking waiting_task_list, once the task is ready (all its dependency is ready), put it into ready_task_list;
def initialize_struct(filename):
real_cost = 0
with open(filename) as task_file:
for line in task_file:
first_space = line.find(' ', 0)
task_id = line[:first_space]
second_space = line.find(' ', first_space + 1)
task_length = line[first_space + 1:second_space]
real_cost += int(task_length)
task_length_dict[task_id] = task_length
right_brace = line.find(']', second_space + 1)
task_dependency = line[second_space + 2:right_brace]
task_dependency = task_dependency.replace(' ', '')
task_dependency_list = task_dependency.split(',')
if task_dependency_list == ['']:
task_dependency_list = []
task_dependency_list_dict[task_id] = task_dependency_list
for dependency in task_dependency_list:
if dependency in task_children_dict:
task_children_dict[dependency].append( task_id)
else:
task_children_dict[dependency] = [task_id]
waiting_task_list.append(task_id)
return real_cost
def insert_finish_event_list(task_id, finish_time):
global finish_event_list
if len(finish_event_list) == 0:
finish_event_list = [{str(finish_time):task_id}]
else:
pos = 0
while len(finish_event_list) > pos and finish_time >= int((finish_event_list[pos]).keys()[0]):
pos = pos + 1
finish_event_list.insert(pos, {str(finish_time):task_id})
#check each task in waiting_task_list, to see whether its ready to be put into ready_task_list
#then check each task in the ready_task_list, check whether there are idle machines to run it
#then jump the time to the first item in finish_event_list
def schedule_tasks(machine_number):
running_machines = 0
current_time = 0
max_used_machines = 0
while waiting_task_list:
iterator = 0
waiting_to_ready_tasks = []
while iterator < len(waiting_task_list):
task_id = waiting_task_list[iterator]
if not task_dependency_list_dict[task_id]:
ready_task_list.append(task_id)
iterator = iterator + 1
for item in ready_task_list:
if item in waiting_task_list:
waiting_task_list.remove(item)
# print "\nAt time %d:" % current_time
while running_machines < machine_number and len(ready_task_list) > 0:
first_ready_task = ready_task_list.pop(0)
# print "Start to run task %s, the task length is %s." % (first_ready_task, task_length_dict[first_ready_task])
first_ready_task_length = task_length_dict[first_ready_task]
insert_finish_event_list(first_ready_task, current_time + int(task_length_dict[first_ready_task]))
running_task_list.append(first_ready_task)
running_machines += 1
if running_machines > max_used_machines:
max_used_machines = running_machines
# print "task_children_dict", task_children_dict
# print "task_length_dict", task_length_dict
# print "task_dependency_list_dict", task_dependency_list_dict
# print "running_task_list", running_task_list
# print "ready_task_list", ready_task_list
# print "waiting_task_list", waiting_task_list
# print "finish_event_list", finish_event_list
#jump the time to the first item in finish_event_list
if len(finish_event_list) > 0:
current_time = int((finish_event_list[0]).keys()[0])
next_finish_event_time = current_time
while len(finish_event_list) > 0 and next_finish_event_time == current_time:
first_finish_event = finish_event_list[0]
finish_task_id = first_finish_event[str(current_time)]
# print "Finish task %s at time %d" % (finish_task_id, current_time)
running_task_list.remove(finish_task_id)
running_machines -= 1
finish_event_list.pop(0)
if finish_task_id in task_children_dict:
for item in task_children_dict[finish_task_id]:
if finish_task_id in task_dependency_list_dict[item]:
task_dependency_list_dict[item].remove(finish_task_id)
if len(finish_event_list) > 0:
next_finish_event_time = int((finish_event_list[0]).keys()[0])
else:
break
return (current_time, max_used_machines)
def main():
#Problem: extension support incremental download
parser = OptionParser(usage="usage: %prog [options] taskfile",
version="%prog 1.0")
parser.add_option("-m", "--machines",
action="store",
default="1",
help="The number of machines, you can provide a number, or a list of numbers like '3, 4, 5'")
(options, args) = parser.parse_args()
filename = sys.argv[-1]
machines_args = options.machines
machines_args = re.sub( '\s+', '', machines_args).strip() #remove all the whitespaces within the inputs option
if machines_args == '':
machine_list = []
else:
machine_list = machines_args.split(',')
for machine_number in machine_list:
machine_number = int(machine_number)
real_cost = initialize_struct(filename)
(execution_time, max_used_machines) = schedule_tasks(machine_number)
total_cost = machine_number * int(execution_time)
idle_cost = total_cost - real_cost
wastage = float(idle_cost) / total_cost
print "\nScheduling results (machine number = %d):" % machine_number
print "Real cost (sum of task lengths): %d" % (real_cost)
print "Machine Number: %d" % machine_number
print "Execution time: %s" % execution_time
print "Total cost (machine number * execution time): %d" % (total_cost)
print "Idle cost (total cost - real cost): %d" % idle_cost
print "Wastage (idle cost / total cost): %5.4f" % wastage
if max_used_machines < machine_number:
print "Max used machines = %d, which is less than the machine number(%d)" % (max_used_machines, machine_number)
else:
print "Max used machines = machine number = %d" % max_used_machines
if __name__ == "__main__":
main()