From 122f457226f54ad23b7cd138512502e430e704dc Mon Sep 17 00:00:00 2001 From: Mac Mollison Date: Sat, 13 Mar 2010 12:12:37 -0500 Subject: Further restructuring to create 'unit_trace' pkg The unit_trace folder should be placed in /usr/local/lib/pythonX.Y/site-packages. This makes unit-trace submodules available from anywhere on the system. --- unit_trace/gedf_test.py | 163 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 163 insertions(+) create mode 100644 unit_trace/gedf_test.py (limited to 'unit_trace/gedf_test.py') diff --git a/unit_trace/gedf_test.py b/unit_trace/gedf_test.py new file mode 100644 index 0000000..8457901 --- /dev/null +++ b/unit_trace/gedf_test.py @@ -0,0 +1,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,record.when,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 -- cgit v1.2.2