Created highly revamped EDF test

1 files changed, 119 insertions, 84 deletions

diff --git a/sta.py b/sta.py
index bec8232..1d5c996 100755
--- a/sta.py
+++ b/sta.py
@@ -131,6 +131,13 @@ class Trace:
         else:
             return "({0},{1})".format(record['pid'],record['job'])
 
+    def getTime(record):
+        """Return the time value from a record -- when, or release-time"""
+        if 'when' in record.keys():
+            return record['when']
+        else:
+            return record['release_time']
+
 
 ##################
 # EDF   class    #
@@ -139,77 +146,133 @@ class Trace:
 class EDF:
     """Object representing an EDF test"""
     
-    def __init__(self,trace_files, fudge_factor=0):
+    def __init__(self,trace_files, tick_size=1000000, tolerance=1000000):
         """Create an EDF test"""
         self.trace_files = trace_files
-        self.fudge_factor = fudge_factor
         self.errors = 0
         self.corrects = 0
+        self.runnables = []
+        self.runnings = []
+        self.time = None
+        self.tick_size = tick_size
+        self.tolerance = tolerance
 
     def run_test(self):
         
         #Make the trace, in order
         trace = Trace(self.trace_files)
         trace.sort('when',alt='release_time')
+        trace.iter = trace.iter.__iter__()
 
-        #Runnables list holds released jobs that are not executing
-        self.runnables = []
+        #Find the start time from the SysRelease record
+        while True:
+            record = trace.iter.__next__()
+            if record['type']==10:
+                self.time = record['when']
+                print("Starting time: " + str(self.time))
+                break
 
-        #Runnings list holds jobs that are executing
-        self.runnings = []
+        #Initialize last_record
+        last_record = trace.iter.__next__()
 
-        #Iterate over records
-        for record in trace.iter:
-
-            #Releases
-            if record['type'] == 3:
-                if not self.check_duplicate_release(record):
-                    self.runnables.append(record)
-                    print("{0} became runnable"
-                          .format(Trace.getStr(record)))
-
-            #Switch Tos
-            elif record['type'] == 5:
-                release_record = EDF.pop_job(record, self.runnables)
-                self.runnings.append(release_record)
-                check_tuple = self.check_deadline(release_record)
-                if check_tuple[0] == True:
-                    print("{0} became running (VALID)"
-                          .format(Trace.getStr(record)))
-                    self.corrects += 1
-                else:
-                    print('='*50)
-                    print("{0} became running (INVALID)"
-                          .format(Trace.getStr(record)))
-                    print('Deadline of {0} greater than deadline of {1}' + 
-                          'in the following record:'
-                          .format(release_record['deadline'],
-                                  check_tuple[1]['deadline']))
-                    print(check_tuple[1])
-                    self.print_runnables()
-                    self.print_runnings()
-                    print('='*50)
-                    self.errors += 1
-
-            #Switch Aways
-            elif record['type'] == 6:
-                release_record = EDF.pop_job(record, self.runnings)
-                if release_record:
-                    self.runnables.append(release_record)
-                    print('{0} went from running to runnable'
-                          .format(Trace.getStr(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)
-               print('{0} completed'
-                     .format(Trace.getStr(record)))
-
-        print('Corrects: {0}'.format(self.corrects))
+        #Initialize finished flag
+        finished = False
+        
+        while not finished: 
+
+            #Increment the time
+            self.time += self.tick_size
+            print("-"*50)
+        
+            #Update the model with records that have passed the time 
+            while Trace.getTime(last_record) < self.time:
+                last_record['overtime'] = 0
+                self.update_model(last_record)
+                try:
+                    last_record = trace.iter.__next__()
+                except StopIteration:
+                    finished = True
+                    break
+
+            #Check to see if our invariant is met
+            #1) Find the max deadline in runnings
+            #2) Check against the deadlines in runnables
+
+            #1) Find the max deadline in runnings
+            max_deadline = None
+            for record in self.runnings:
+                if max_deadline==None:
+                    max_deadline = record['deadline']
+                    continue
+                elif record['deadline'] > max_deadline:
+                    max_deadline = record['deadline']
+
+            #2) Check against the deadlines in runnables
+            if max_deadline:
+                for record in self.runnables:
+                    if record['deadline'] < max_deadline:
+                        record['overtime'] += self.tick_size
+                        if record['overtime'] > self.tolerance:
+                            print("INVALID!")
+                            self.print_runnables()
+                            self.print_runnings()
+                            record['overtime'] = -99999999999999999
+                            self.errors += 1
+                        
+        
         print('Errors  : {0}'.format(self.errors))
 
+
+    def update_model(self, record):
+
+        #Releases
+        if record['type'] == 3:
+            if not self.check_duplicate_release(record):
+                self.runnables.append(record)
+                print("{0} became runnable"
+                      .format(Trace.getStr(record)))
+
+        #Switch Tos
+        elif record['type'] == 5:
+            release_record = EDF.pop_job(record, self.runnables)
+            self.runnings.append(release_record)
+            print("{0} became running".format(Trace.getStr(record)))
+            #check_tuple = self.check_deadline(release_record)
+            #if check_tuple[0] == True:
+            #    print("{0} became running (VALID)"
+            #          .format(Trace.getStr(record)))
+            #    self.corrects += 1
+            #else:
+            #    print('='*50)
+            #    print("{0} became running (INVALID)"
+            #          .format(Trace.getStr(record)))
+            #    print('Deadline of {0} greater than deadline of {1}' + 
+            #          'in the following record:'
+            #          .format(release_record['deadline'],
+            #                  check_tuple[1]['deadline']))
+            #    print(check_tuple[1])
+            #    self.print_runnables()
+            #    self.print_runnings()
+            #    print('='*50)
+            #    self.errors += 1
+
+        #Switch Aways
+        elif record['type'] == 6:
+            release_record = EDF.pop_job(record, self.runnings)
+            if release_record:
+                self.runnables.append(release_record)
+                print('{0} went from running to runnable'
+                      .format(Trace.getStr(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)
+           print('{0} completed'
+                 .format(Trace.getStr(record)))
+
+
     def pop_job(record, record_list):
         """Pop a job from a list of jobs"""
         job = record['job']
@@ -221,34 +284,6 @@ class EDF:
                 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"""
-
-        #Set up the variables we will need
-        minDeadline = None
-        lowest_deadline_record = None
-        diff = None
-
-        #Find the minimum deadline in runnables and the associated record
-        for record2 in self.runnables:
-            if minDeadline == None or record2['deadline'] < minDeadline:
-                minDeadline = record2['deadline']
-                lowest_deadline_record  = record2
-
-        #Compute the difference btw. the one we sheduled and the minimum
-        #   in runnables
-        if minDeadline == None:
-            diff = 0
-        else:
-            diff = record['deadline'] - minDeadline
-
-        #Determine if the difference is acceptable
-        if diff <= self.fudge_factor:
-            return (True,lowest_deadline_record)
-        else:
-            return (False,lowest_deadline_record)
-
     def check_duplicate_release(self, record):
         """Make sure we don't get duplicate releases"""
         job = record['job']