Completed exercise M8 for embedded

6 files changed, 217 insertions, 13 deletions

diff --git a/sem4/embedded/eksamnen/M8f1.png b/sem4/embedded/eksamnen/M8f1.png
new file mode 100644
index 0000000..0bc006d
--- /dev/null
+++ b/sem4/embedded/eksamnen/M8f1.png
diff --git a/sem4/embedded/eksamnen/M8f2.png b/sem4/embedded/eksamnen/M8f2.png
new file mode 100644
index 0000000..53b8b64
--- /dev/null
+++ b/sem4/embedded/eksamnen/M8f2.png
diff --git a/sem4/embedded/eksamnen/M8f3.png b/sem4/embedded/eksamnen/M8f3.png
new file mode 100644
index 0000000..8153361
--- /dev/null
+++ b/sem4/embedded/eksamnen/M8f3.png
diff --git a/sem4/embedded/eksamnen/M8opg.adoc b/sem4/embedded/eksamnen/M8opg.adoc
new file mode 100644
index 0000000..59f8031
--- /dev/null
+++ b/sem4/embedded/eksamnen/M8opg.adoc
@@ -0,0 +1,116 @@
+= Opgaver til gang 8
+
+== Opgave 1
+
+Given a periodic taskset : T1=4,c1=3,T2=12,c2=2 with relative deadlines d1=4,d2=7
+
+. Examine the taskset w.r.t. schedulability using the exact criterion for DMA scheduling.  Is the taskset EDF schedulable ?
+
+=== Løsning
+
+____
+_Examine the taskset w.r.t. schedulability using the exact criterion for DMA scheduling._
+____
+
+Her kan man se at følgende priority scheme skal bruges.
+
+(T1, T2)
+
+Nu giver det mening at undersøge om dette er feasable.
+For T1 er completion time 3, hvilket er under dens deadline.
+
+For T2.
+
+image::M8f1.png[]
+
+Her kan man se at completion time er 8 hvilket er efter T2's deadline.
+Derfor er DMA ikke feasable.
+
+Dette kan man også se hvis man kører det.
+
+----
+0           3   2   4   7   
+1   |       2   2   3   6   
+2   |       1   2   2   5   
+3   |       0   2   1   4   
+4       |   3   1   4   3   
+5   |       2   1   3   2   
+6   |       1   1   2   1   
+Deadline missed in task 1
+----
+
+____
+Is the taskset EDF schedulable?
+____
+
+Når man kører med EDF kan man se at der ikke er mere arbejde efter LCM.
+
+----
+0           3   2   4   7   
+1   |       2   2   3   6   
+2   |       1   2   2   5   
+3   |       0   2   1   4   
+4       |   3   1   4   3   
+5       |   3   0   3   2   
+6   |       2   0   2   1   
+7   |       1   0   1   0   
+8   |       2   0   4   -1  
+9   |       1   0   3   -2  
+10  |       0   0   2   -3  
+11          0   0   1   -4
+----
+
+== Opgave 2
+
+Given a periodic taskset T1=40,c1=10,d1=20,T2=60,c2=20,d2=30,T3=80,c3=20,d3=80,(milliseconds) where task1 and task2 share data protected by semaphore S.
+Accessing the shared data lasts no more than 10 (time units-mill sec).
+Priority ceiling or immediate ceiling is assumed.
+
+. Is the taskset DMA schedulable ?
+. If the data above are instead shared between task1 and task3, is the taskset then DMA schedulable.
+
+=== Løsning
+
+____
+_Is the taskset DMA schedulable?_
+____
+
+Her bruger jeg den nye formel for at finde completion time.
+
+stem:[C_i = c_i + \sum_{j=1}{i-1}ceil(C_i/T_j) * c_j + B_i]
+
+Ved DMA bliver prioriteten (T1, T2, T3).
+Task 1 kan godt vente på T2, men T2 skal ikke vente på nogen.
+
+----
+C1 = 10 + 10 = 20
+C2 = 20 + ceil(C2/40)*10
+C3 = 20 + ceil(C3/60)*20 + ceil(C3/40)*10
+----
+
+T1 bliver færdig lige inden dens deadline.
+Først plottes C2.
+
+image::M8f2.png[]
+
+Her kan man se at den completer inden dens deadline 30.
+
+Under kan man se at T3 også bliver færdig, når man plotter C3.
+
+image::M8f3.png[]
+
+____
+_If the data above are instead shared between task1 and task3, is the taskset then DMA schedulable._
+____
+
+Her ændres C1 til C3 sig overhovedet ikke, da T1 alligevel skal vente 10.
+
+----
+C1 = 10 + 10 = 20
+C2 = 20 + ceil(C2/40)*10
+C3 = 20 + ceil(C3/60)*20 + ceil(C3/40)*10
+----
+
+== Opgave 3
+
+Implement the example of ex. 2) on JDN's kernel and measure worst case completion times.
diff --git a/sem4/embedded/eksamnen/notes.adoc b/sem4/embedded/eksamnen/notes.adoc
index de9b919..0b33bb7 100644
--- a/sem4/embedded/eksamnen/notes.adoc
+++ b/sem4/embedded/eksamnen/notes.adoc
@@ -181,6 +181,46 @@ ____
 Exercise 1-2
 ____
 
+Se ./M8opg.adoc
+
+TODO lav arduino ting
+
+=== Noter
+
+_Earliest Deadline First_ eller *EDF* er hvor man tager den med deadline der er
+tættest på _t_.
+
+Dette gør man dynamisk hvilket giver en højere runtime cost end en fixed priority såsom *DMA*.
+
+_Hvis man kan finde et feasable schedule er *EDF* også feasable._
+
+_Hvis deadlines er lig perioder er taskset schedulable med *EDF* hvis stem:[U \leq 1]._
+Dette kaldes også for *utilization criterion.
+
+*Priority Ceiling*, er hvis en task stem:[\tau] prøver at lock en locked task, arver stem:[\tau{}_l] prioriteten.
+Her er det først når en højere task prøver at lock at den lavere task arver.
+
+Dette har forskellige egenskaber, hvis man kan garantere at alle task laver nested locking.
+
+- No deadlocks possible
+- En task venter max duration af critical region for lavere task.
+
+*Immediate Ceiling* er mere leightweight, da man istedet siger at hvis en task
+locker en lock, vil den arve den højst mulige potentielle perioritet.
+Også selvom der ikke er nogen der venter på den.
+
+Denne har samme egenskaber men behøver ikke lige så meget overhead.
+
+I et non-preemtive system, vil dette ikke betyde så meget, da ressources bliver
+unlocked igen i execution perioden for en task.
+
+Hvis man har _round_robin_, _static_ eller _dynamic_ scheduling er der ikke nogle prioriteter man kan bruge.
+Derfor bruger man _Static Ressource Priority Ordering_ hvor man bruger priorities når der sker ressource locking.
+
+- Hvis man bruger _static priority_ bestemmer man STPO før.
+- Hvis man bruger _round robin_ her kigger man på worsk case analysis.
+- Hvis man bruger _EDF_ her det svært at lave analysis.
+
 == H5 module 9
 
 ____
diff --git a/sem4/embedded/eksamnen/schedsolver.rb b/sem4/embedded/eksamnen/schedsolver.rb
index c75b52b..333739f 100755
--- a/sem4/embedded/eksamnen/schedsolver.rb
+++ b/sem4/embedded/eksamnen/schedsolver.rb
@@ -28,7 +28,7 @@ class Scheduler
   end
 
   def printState(index, state)
-    print index.to_s().ljust(4, ' ')
+    print (index).to_s().ljust(4, ' ')
     @tasks.length.times do |i|
       print state[:task] == i ? "|" : " "
       print " "*3
@@ -80,7 +80,11 @@ class Scheduler
   end
 
   def calcNextState(index)
-    curtask = nextTask(index)
+    curtask = nil
+    # We should not run at the begining
+    if index > 0
+      curtask = nextTask(index)
+    end
     new = {:task => curtask, :remain => []}
     @tasks.each_with_index do |task, i|
       # Check for deadline miss
@@ -105,25 +109,36 @@ class Scheduler
     return new
   end
 
-  def run(runtil=nil)
+  def runtiltask(task)
     printHeader()
-
-    # Run LCM times
-    lcm = @tasks[0][:period]
-    @tasks.drop(1).each do |task|
-      lcm = task[:period].lcm(lcm)
-    end
-    (0..lcm).each do |i|
+    (0..).step do |i|
       new = calcNextState(i)
       @states << new
 
       printState(i, new)
 
-      if runtil && new[:remain][runtil] == 0
+      if new[:remain][task] == 0
         break
       end
     end
   end
+
+  def run(runtil = nil)
+    if !runtil
+      # Run LCM times
+      runtil = @tasks[0][:period]
+      @tasks.drop(1).each do |task|
+        runtil = task[:period].lcm(runtil)
+      end
+    end
+
+    runtil.times do |i|
+      new = calcNextState(i)
+      @states << new
+
+      printState(i, new)
+    end
+  end
 end
 
 def taskFromString(str)
@@ -181,17 +196,45 @@ class RmaSched < Scheduler
   end
 end
 
+class EdfSched < Scheduler
+  def nextTask(index)
+    smallestTask = nil
+    closestDead = nil
+
+    @tasks.each_with_index do |task, i|
+      if @states.last and @states.last[:remain][i] == 0
+        next
+      end
+
+      deadline = task[:deadline] - (index % task[:period])
+
+      if !smallestTask or deadline < closestDead
+        smallestTask = i
+        closestDead = deadline
+      end
+    end
+
+    return smallestTask
+  end
+end
+
 options = {}
 OptionParser.new do |opts|
   opts.on("-f", "--taskfile FILE", "Load tasks from FILE") do |f|
     options[:taskfile] = f
   end
   opts.on("--until-done TASK", "Run until TASK finishes") do |task|
-    options[:runtil] = Integer(task)
+    options[:runtiltask] = Integer(task)
+  end
+  opts.on("--until TIME", "Run til specified time") do |time|
+    options[:runtil] = Integer(time)
   end
   opts.on("--sched-rma", "Schedule using rma") do
     options[:sched] = RmaSched.new()
   end
+  opts.on("--sched-edf", "Schedule using edf") do
+    options[:sched] = EdfSched.new()
+  end
   opts.on("--sched-fixed PRIO", "Schedule using fixed priority list PRIO") do |prio|
     prio = prio.split(",")
     prio.map! {|p| Integer(p) }
@@ -228,4 +271,9 @@ else
   sch = Scheduler.new()
 end
 sch.loadtasks(tasks)
-sch.run(options[:runtil])
+
+if options[:runtiltask]
+  sch.runtiltask(options[:runtiltask])
+else
+  sch.run(options[:runtil])
+end