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
|
###############################################################################
# Description
###############################################################################
# G-EDF Test
###############################################################################
# Imports
###############################################################################
import copy
###############################################################################
# Public Functions
###############################################################################
def gedf_test(stream):
# Two lists to model the system: tasks occupying a CPU and tasks eligible
# to do so. Also, m = the number of CPUs.
eligible = []
on_cpu = []
m = None
# Time of the last record we saw. Only run the G-EDF test when the time
# is updated.
last_time = None
for record in stream:
if record.record_type != "event":
if record.record_type == "meta" and record.type_name == "num_cpus":
m = record.num_cpus
continue
# Check for inversion starts and ends and yield them.
# Only to the check when time has moved forward.
# (It is common to have records with simultaneous timestamps.)
if last_time is not None and last_time != record.when:
errors = _gedf_check(eligible,on_cpu,last_time,m)
for error in errors:
yield error
# Add a newly-released Job to the eligible queue
if record.type_name == 'release':
eligible.append(Job(record))
# Move a Job from the eligible queue to on_cpu
elif record.type_name == 'switch_to':
pos = _find_job(record,eligible)
job = eligible[pos]
del eligible[pos]
on_cpu.append(job)
# Mark a Job as completed.
# The only time a Job completes when it is not on a
# CPU is when it is the last job of the task.
elif record.type_name == 'completion':
pos = _find_job(record,on_cpu)
if pos is not None:
on_cpu[pos].is_complete = True
else:
pos = _find_job(record,eligible)
del eligible[pos]
# A job is switched away from a CPU. If it has
# been marked as complete, remove it from the model.
elif record.type_name == 'switch_away':
pos = _find_job(record,on_cpu)
job = on_cpu[pos]
del on_cpu[pos]
if job.is_complete == False:
eligible.append(job)
last_time = record.when
yield record
###############################################################################
# Private Functions
###############################################################################
# Internal representation of a Job
class Job(object):
def __init__(self, record):
self.pid = record.pid
self.job = record.job
self.deadline = record.deadline
self.is_complete = False
self.inversion_start = None
self.inversion_end = None
def __str__(self):
return "(%d.%d:%d)" % (self.pid,self.job,self.deadline)
# G-EDF errors: the start or end of an inversion
class Error(object):
def __init__(self, job, eligible, on_cpu):
self.job = copy.copy(job)
self.eligible = copy.copy(eligible)
self.on_cpu = copy.copy(on_cpu)
self.record_type = 'error'
if job.inversion_end is None:
self.type_name = 'inversion_start'
else:
self.type_name = 'inversion_end'
# Returns the position of a Job in a list, or None
def _find_job(record,list):
for i in range(0,len(list)):
if list[i].pid == record.pid and list[i].job == record.job:
return i
return None
# Return records for any inversion_starts and inversion_ends
def _gedf_check(eligible,on_cpu,when,m):
# List of error records to be returned
errors = []
# List of all jobs that are not complete
all = []
for x in on_cpu:
if x.is_complete is not True:
all.append(x)
all += eligible
# Sort by on_cpu and then by deadline. sort() is guaranteed to be stable.
# Thus, this gives us jobs ordered by deadline with preference to those
# actually running.
all.sort(key=lambda x: 0 if (x in on_cpu) else 1)
all.sort(key=lambda x: x.deadline)
# Check those that actually should be running
for x in range(0,min(m,len(all))):
job = all[x]
# It's not running and an inversion_start has not been recorded
if job not in on_cpu and job.inversion_start is None:
job.inversion_start = when
errors.append(Error(job, eligible, on_cpu))
# It is running and an inversion_start exists (i.e. it it still
# marked as being inverted)
elif job in on_cpu and job.inversion_start is not None:
job.inversion_end = when
errors.append(Error(job, eligible, on_cpu))
job.inversion_start = None
job.inversion_end = None
# Check those that actually should not be running
for x in range(m,len(all)):
job = all[x]
# It actually is running. We don't care.
# It isn't running, but an inversion_start exists (i.e. it is still
# marked as being inverted)
if job not in on_cpu and job.inversion_start is not None:
job.inversion_end = when
errors.append(Error(job, eligible, on_cpu))
job.inversion_start = None
job.inversion_end = None
return errors
|
