Changed the terrible first-attempt EDF test to something much more

mature. Appears to work except for not accounting for switch_away's. See
README for more info.

3 files changed, 95 insertions, 74 deletions

diff --git a/README b/README
index 6c2eb14..4be61b3 100644
--- a/README
+++ b/README
@@ -10,9 +10,21 @@ The general idea it that you use run.py to put in the commands you want to do,
 and then do something like ./run.py > out to write out the records.
 
 
+############################
+Gotchas
+############################
+Remember that a StReleaseData record has 'release_time', not 'when', as a field.
+
 
 #############################
 Development Notes
 #############################
 
-None
+EDF tester seems to be working, but does not account for this scenario:
+-release
+-switch_to
+-switch_away
+-switch_to
+Rather, it finds the release and the first switch_to, leaving the second
+switch_to in the queue of switches, thus upsetting the order of switches. The
+way to solve this is to add switch_aways into the release filter.
diff --git a/run.py b/run.py
index bcfd068..0a058c5 100755
--- a/run.py
+++ b/run.py
@@ -10,6 +10,14 @@ def main():
     #myTrace()
     #switchToTrace()
     #releaseTrace()
+    #oneCPU()
+
+def oneCPU():
+    trace = sta.Trace(g6_list)
+    trace.filter('cpu==0')
+    trace.sort('when')
+    trace.print_count(True)
+    trace.print_records()
 
 def myEDF():
     test = sta.EDF(g6_list)
diff --git a/sta.py b/sta.py
index b2b92f7..3f244e8 100755
--- a/sta.py
+++ b/sta.py
@@ -88,6 +88,10 @@ class Trace:
             return score
         self.iter = sorted(self.iter, key=sortfunc)
 
+    def slice(self, start, end):
+        """Slice the trace iterator"""
+        self.iter = list(self.iter)[start:end]
+
     def print_records(self):
         """Prints all records in the trace"""
         for record in self.iter:
@@ -121,82 +125,79 @@ class EDF:
     def __init__(self,trace_files):
         """Create an EDF test"""
         self.trace_files = trace_files
+        self.errors = 0
 
     def run_test(self):
 
-        #Build a trace of releases
-        release_trace = Trace(self.trace_files)
-        release_trace.filter('type==3')
-        release_trace.filter('type==3')
-        release_trace.sort('release_time')
-        releases = list(release_trace.iter)
-        print(str(len(releases)))
-        #This is a hack for the g6 set to get rid of initial job2 releases
-        releases = releases[28:]
-        print(str(len(releases)))
-
-        #Build a trace of scheduler events (only type 5, 6, and 7)
-        events_trace = Trace(self.trace_files)
-        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 = list(events_trace.iter)
-
-        #Do the test
-        started_releases = []
-        num_errors = 0
-        for event in events:
-            #StSwitchToData
-            if event['type'] == 5:
-                i = 0
-                while True:
-                    if (event['pid'] == releases[i]['pid'] and 
-                        event['job'] == releases[i]['job']):
-                        started_releases.append(releases[i])
-                        print("="*50)
-                        print("Valid SwitchTo:")
-                        print(event)
-                        print(releases[i])
-                        break
-                    elif(releases[i]['release_time'] == 
-                         releases[i+1]['release_time']):
-                        i += 1
-                        #print("Trying next...")
-                        continue
-                    else:
-                        num_errors += 1
-                        print("="*50)
-                        print('Invalid SwitchTo:')
-                        print(event)
-                        print(releases[0])
-                        print('Try counter: ' + str(i))
-                        break
-            #StSwitchAwayData
-            elif event['type'] == 6:
-                #Try to find the release among those started;
-                def func(release):
-                    return (release['job'] == event['job'] and 
-                            release['pid'] == event['pid'])
-                possible_release = list(filter(func,started_releases))
-                #Only take action if found (it may just be carrying over from
-                #   previous job, in which case it's already on the releases
-                #   list)
-                if len(possible_release) > 0:
-                    release = possible_release[0]
-                    releases.append(release)
-                    def sortfunc(release):
-                        return release['release_time']
-                    releases = sorted(releases,key=func)
-            #input("Continue?")
-
-        #Test completed
-        print("Test completed!")
-        print("Number of errors: " + str(num_errors))
+        #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']))
+                else:
+                    print("ERROR: Swiched out of order, task " +
+                          str(next_release['pid']) + ", job " + 
+                          str(next_release['job']) + " by " + 
+                          str(switch_to_rank))
+                    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
+
+    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                #
+####################################
+
+def debug(string):
+    print(string)
 
 
 ####################################