1 files changed, 163 insertions, 0 deletions

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