Re-implemented EDF test with new stragety. Not tested yet, but a lot of progress has been made.

3 files changed, 105 insertions, 163 deletions

diff --git a/README b/README
index 4be61b3..16450df 100644
--- a/README
+++ b/README
@@ -10,21 +10,12 @@ 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
 #############################
 
-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.
+Need to account for situation where there is a tie in deadline which spans the
+topN category.
+
+Might think about adding in hooks, so you do the trace, then add in the hook to
+see the state at the place you're curious about.
diff --git a/run.py b/run.py
index 7ae3f53..42cf27b 100755
--- a/run.py
+++ b/run.py
@@ -6,8 +6,8 @@ import sta
 ######################################
 
 def main():
-    myEDF()
-    #myTrace()
+    #myEDF()
+    myTrace()
     #switchToTrace()
     #releaseTrace()
     #oneCPU()
@@ -27,6 +27,7 @@ def myEDF():
 def myTrace():
     trace = sta.Trace(g6_list)
     trace.sort('when',alt='release_time')
+    trace.filter('type==2')
     trace.print_count(True)
     trace.print_records()
 
diff --git a/sta.py b/sta.py
index 3d76031..3add6ec 100755
--- a/sta.py
+++ b/sta.py
@@ -146,168 +146,118 @@ class Trace:
 ##################
 
 class EDF:
-    """Object representing 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"""
+    def __init__(self,trace_files, tolerance=150000, N=4):
         self.trace_files = trace_files
-        self.errors = 0
-        self.runnables = []
-        self.runnings = []
-        self.time = None
-        self.tick_size = tick_size
         self.tolerance = tolerance
+        self.jobs = []
+        self.N = N #number of cores
+        self.now = 0
 
     def run_test(self):
-        """Run an EDF test"""
-        
-        #Make the trace, in order
         trace = Trace(self.trace_files)
         trace.sort('when',alt='release_time')
-        trace.iter = trace.iter.__iter__()
-
-        #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
-
-        #Initialize variables needed for the algorithm
-        last_record = trace.iter.__next__()
-        finished = False
-        
-        #Increment the time, update the model, and check the invariant
-        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 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']
+        for record in trace.iter:
+            
+            #Update now
+            if 'when' in record:
+                self.now = record['when']
+            elif 'release_time' in record:
+                self.now = record['release_time']
+
+            #Process record
+            if record['type'] == 3:
+                if self.is_duplicate_release(record): continue
+                job = EDF.Job()
+                job.deadline = record['deadline']
+                job.release_time = record['release_time']
+                job.job = record['job']
+                job.pid = record['pid']
+                self.jobs.append(job)
+                print('{0}: {1} was released'.format(self.now,job.get_name()))
+            elif record['type'] == 5:
+                job = self.get_job(record['pid'],record['job'])
+                if job:
+                    job.running = True
+                else:
+                    continue
+                print('{0}: {1} was switched to'
+                      .format(self.now,job.get_name()))
+            elif record['type'] == 6:
+                job = self.get_job(record['pid'],record['job'])
+                if job:
+                    job.running = False
+                else:
+                    continue
+                print('{0}: {1} was switched away'
+                      .format(self.now,job.get_name()))
+            elif record['type'] == 7:
+                job = self.get_job(record['pid'],record['job'])
+                if job:
+                    self.jobs.remove(job)
+                else:
+                    continue
+                print('{0}: {1} completed'
+                      .format(self.now,job.get_name()))
+            else:
                 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:
-            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)))
-
-        #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']
-        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_duplicate_release(self, record):
+
+            #Sort jobs by deadline
+            self.jobs = sorted(self.jobs,key=lambda job: job.deadline)
+
+            #Check for inversions (and end-of inversions) in the top N jobs
+            for job in self.jobs[0:self.N]:
+                job.topN = True
+                if job.running == False:
+                    if job.inversion_start_time==0:
+                        job.inversion_start_time=self.now
+                elif job.running == True:
+                    if job.inversion_start_time > 0:
+                        self.check_error(job)
+                        job.inversion_start_time = 0
+
+            #Check for end-of-inversions in the other jobs
+            for job in self.jobs[self.N:]:
+                if job.topN == True:
+                    job.topN = False
+                    self.check_error(job)
+
+    def check_error(self, job):
+        if job.inversion_start_time == 0: return
+        if self.now - job.inversion_start_time > self.tolerance:
+            print(' ' * 16 + job.get_name() + 
+                  ' was inverted for {0} time units,'
+                  .format(self.now - job.inversion_start_time))
+            print(' '*26 + 'since {0}'.format(job.inversion_start_time))
+            job.inversion_start_time = 0
+
+    def get_job(self, pid, job):
+        for x in self.jobs:
+            if x.pid == pid and x.job == job:
+                return x
+
+    def is_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:
+        for x in self.jobs:
+            if x.job == job and x.pid == pid:
                 return True
         return False
 
-    def print_runnables(self):
-        """Print the runnable jobs"""
-        print("Runnable jobs:")
-        for record in self.runnables:
-            print('{0}, Deadline: {1}'.format(Trace.getStr(record,
-                                                           omitTime=True),
-                                              record['deadline']))
-
-    def print_runnings(self):
-        """Print the runnable jobs"""
-        print("Running jobs:")
-        for record in self.runnings:
-            print('{0}, Deadline: {1}'.format(Trace.getStr(record,
-                                                           omitTime=True),
-                                              record['deadline']))
-
+    class Job:
+        def __init__(self):
+            self.release_time = 0
+            self.deadline = 0
+            self.job = 0
+            self.pid = 0
+            self.running = False
+            self.topN = False
+            self.inversion_start_time = 0
+
+        def get_name(self):
+            return '({0},{1})'.format(self.pid,self.job)
 
 ####################################
 # Types for binary data conversion #