Cleaned up EDF code

1 files changed, 51 insertions, 52 deletions

diff --git a/sta.py b/sta.py
index 1d5c996..3d76031 100755
--- a/sta.py
+++ b/sta.py
@@ -121,6 +121,8 @@ class Trace:
         print("")
 
     def getStr(record,omitTime=False):
+        """Return the representation of a record in the format
+        time: (task, job)"""
         time = None
         if 'when' in record:
             time = record['when']
@@ -144,13 +146,25 @@ class Trace:
 ##################
 
 class EDF:
-    """Object representing an EDF test"""
+    """Object representing an EDF test
     
-    def __init__(self,trace_files, tick_size=1000000, tolerance=1000000):
-        """Create an EDF test"""
+    The strategy is to create a model of runnable and running tasks, which is
+    updated and checked against an invariant every tick_size time units
+    
+    The invariant is that every running task much have an earlier deadline
+    than every runnable task; an error message is not generated until the
+    invariant is false for more than a specified number of ticks (given by
+    'tolerance')"""
+    
+    def __init__(self,trace_files, tick_size=1000000, tolerance=1):
+        """Create an EDF test.
+        
+        tick_size = check the invariant every tick_size units of time
+        
+        tolerance = number of tick_size time units which can pass before
+            a false invariant triggers an error message"""
         self.trace_files = trace_files
         self.errors = 0
-        self.corrects = 0
         self.runnables = []
         self.runnings = []
         self.time = None
@@ -158,6 +172,7 @@ class EDF:
         self.tolerance = tolerance
 
     def run_test(self):
+        """Run an EDF test"""
         
         #Make the trace, in order
         trace = Trace(self.trace_files)
@@ -172,12 +187,11 @@ class EDF:
                 print("Starting time: " + str(self.time))
                 break
 
-        #Initialize last_record
+        #Initialize variables needed for the algorithm
         last_record = trace.iter.__next__()
-
-        #Initialize finished flag
         finished = False
         
+        #Increment the time, update the model, and check the invariant
         while not finished: 
 
             #Increment the time
@@ -193,37 +207,41 @@ class EDF:
                 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
-                        
+            
+            #Check the invariant
+            self.check_invariant()
         
         print('Errors  : {0}'.format(self.errors))
 
 
+    def check_invariant(self):
+        """Check the invariant: the earliest deadline in runnables should be
+        later than the latest deadline in runnings"""
+
+        #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']
+
+        #Check against the deadlines in runnables
+        if max_deadline:
+            for record in self.runnables:
+                if record['deadline'] < max_deadline:
+                    record['overtime'] += 1
+                    if record['overtime'] > self.tolerance:
+                        print("INVALID!")
+                        self.print_runnables()
+                        self.print_runnings()
+                        record['overtime'] = -99999999999999999
+                        self.errors += 1
+
     def update_model(self, record):
+        """Update our model of the system: running tasks ('self.runnings') and
+        runnable tasks ('self.runnable')"""
 
         #Releases
         if record['type'] == 3:
@@ -237,24 +255,6 @@ class EDF:
             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:
@@ -272,7 +272,6 @@ class EDF:
            print('{0} completed'
                  .format(Trace.getStr(record)))
 
-
     def pop_job(record, record_list):
         """Pop a job from a list of jobs"""
         job = record['job']