EDF tester runs to completion. Finds 1925 corrects in g6 and 594 errors.

Needs carefuly examination to root out problems and bugs.

2 files changed, 97 insertions, 70 deletions

diff --git a/run.py b/run.py
index 5533c9f..624acdf 100755
--- a/run.py
+++ b/run.py
@@ -24,17 +24,10 @@ def myEDF():
     test.run_test()
 
 def myTrace():
-    events_trace = sta.Trace(g6_list)
-    events_trace.filter('type!=1')
-    events_trace.filter('type!=2')
-    events_trace.filter('type!=3')
-    events_trace.filter('type!=4')
-    events_trace.filter('type!=8')
-    events_trace.filter('type!=9')
-    events_trace.filter('type!=10')
-    events_trace.sort('when')
-    events_trace.print_count(True)
-    events_trace.print_records()
+    trace = sta.Trace(g6_list)
+    trace.sort('when',alt='release_time')
+    trace.print_count(True)
+    trace.print_records()
 
 def switchToTrace():
     events_trace = sta.Trace(g6_list)
diff --git a/sta.py b/sta.py
index bcaadeb..8c457ae 100755
--- a/sta.py
+++ b/sta.py
@@ -7,6 +7,7 @@
 
 import sys
 import struct
+import copy
 
 ##################
 # Trace class    #
@@ -119,6 +120,9 @@ class Trace:
                       ': ' + str(counts[key]))
         print("")
 
+    def getStr(record):
+        return "({0},{1})".format(record['pid'],record['job'])
+
 
 ##################
 # EDF   class    #
@@ -131,71 +135,101 @@ class EDF:
         """Create an EDF test"""
         self.trace_files = trace_files
         self.errors = 0
+        self.corrects = 0
 
     def run_test(self):
-
-        #Build an in-order list of releases
-        releases = Trace(self.trace_files)
-        releases.filter('type==3')
-        releases.sort('release_time')
-        releases.slice(14,None) #get rid of double record of job 2 release
-
-        #Build an in-order list of switch_tos
-        switch_tos = Trace(self.trace_files)
-        switch_tos.filter('type==5')
-        switch_tos.sort('when')
-
-        #Iterate through releases, making sure the anticipated switch_to comes
-        #   next. The equiv_window allows for simultaneous releases where the
-        #   switch_to does not match the order the releases come in.
-        while len(releases.iter) > 0:
-            next_release = releases.iter.pop(0)
-            switch_to_rank = self.find_switch_to_for_release(next_release, 
-                                                             switch_tos.iter)
-            if switch_to_rank == 0:
-                print("VALID : task " + str(next_release['pid']) + ", job " + 
-                      str(next_release['job']))
-            elif switch_to_rank > 0:
-                if (switch_to_rank < 
-                    self.equiv_window(next_release['release_time'],
-                                      releases.iter)):
-                    print("VALID : task " + str(next_release['pid']) + 
-                          ", job " + str(next_release['job']))
+        
+        #Make the trace, in order
+        trace = Trace(self.trace_files)
+        trace.sort('when',alt='release_time')
+
+        #Runnables list holds released jobs that are not executing
+        self.runnables = []
+
+        #Runnings list holds jobs that are executing
+        self.runnings = []
+
+        #Iterate over records
+        for record in trace.iter:
+
+            #Releases
+            if record['type'] == 3:
+                if not self.check_duplicate_release(record):
+                    self.runnables.append(record)
+                    debug("Added {0} to runnables"
+                          .format(Trace.getStr(record)))
+                    debug(record)
+
+            #Switch Tos
+            elif record['type'] == 5:
+                release_record = EDF.pop_job(record, self.runnables)
+                self.runnings.append(release_record)
+                debug("Added {0} to runnings"
+                      .format(Trace.getStr(release_record)))
+                debug(release_record)
+                if self.check_deadline(release_record):
+                    print("Valid")
+                    self.corrects += 1
                 else:
-                    print("ERROR: Swiched out of order, task " +
-                          str(next_release['pid']) + ", job " + 
-                          str(next_release['job']) + " by " + 
-                          str(switch_to_rank))
+                    print("Invalid")
                     self.errors += 1
-            elif switch_to_rank < 0:
-                print("ERROR: Did not find switch_to for task " + 
-                      str(next_release['pid']) + ", job " + 
-                      str(next_release['job']))
-                self.errors += 1
-            continue
-
-    def find_switch_to_for_release(self, next_release, switch_tos_iter):
-        """Find the switch_to for that corresponds to the next release"""
-        i = 0
-        while i < len(switch_tos_iter) - 1:
-            if self.job_match(next_release,switch_tos_iter[i]):
-                del switch_tos_iter[i]
-                return i
-            i += 1
-        return -1
 
-    def equiv_window(self, time,releases):
-        """Return the number of releases after this one in the release list
-        which have the same release time"""
-        i = 0
-        while releases[i]['release_time'] == time:
-            i += 1
-        return i
+            #Switch Aways
+            elif record['type'] == 6:
+                release_record = EDF.pop_job(record, self.runnings)
+                if release_record:
+                    debug("Removed {0} from runnings"
+                          .format(Trace.getStr(release_record)))
+                    debug(release_record)
+                    self.runnables.append(release_record)
+                    debug("Added {0} to runnables"
+                          .format(Trace.getStr(release_record)))
+                    debug(release_record)
+
+            #Completions
+            elif record['type'] == 7:
+               release_record = EDF.pop_job(record,self.runnings)
+               if not release_record:
+                   release_record = EDF.pop_job(record,self.runnables)
+               debug("Completed {0}, removed from runnings"
+                     .format(Trace.getStr(release_record)))
+               debug(release_record)
+
+        print('Corrects: {0}'.format(self.corrects))
+        print('Errors  : {0}'.format(self.errors))
+
+    def pop_job(record, record_list):
+        """Pop a job from a list of jobs"""
+        job = record['job']
+        pid = record['pid']
+        for record in record_list:
+            if record['job'] == job and record['pid'] == pid:
+                record_copy = copy.copy(record)
+                record_list.remove(record)
+                return record_copy
+        return None
+
+    def check_deadline(self, record):
+        """Check to see if a release record has an equal or earlier deadline
+        than all those that are runnable"""
+        minDeadline = None
+        for record in self.runnables:
+            if minDeadline == None or record['deadline'] < minDeadline:
+                minDeadline = record['deadline']
+        if minDeadline == None or minDeadline >= record['deadline']:
+            return True
+        else:
+            return False 
+
+    def check_duplicate_release(self, record):
+        """Make sure we don't get duplicate releases"""
+        job = record['job']
+        pid = record['pid']
+        for record in self.runnables:
+            if record['job'] == job and record['pid'] == pid:
+                return True
+        return False
 
-    def job_match(self, release, switch_to):
-        """Return True if a release matches a switch_to by job and pid"""
-        return (release['job'] == switch_to['job'] and
-                release['pid'] == switch_to['pid'])
 
 ####################################
 #             Debug                #