diff options
| -rw-r--r-- | sem4/embedded/eksamnen/M8f1.png | bin | 0 -> 31196 bytes | |||
| -rw-r--r-- | sem4/embedded/eksamnen/M8f2.png | bin | 0 -> 38443 bytes | |||
| -rw-r--r-- | sem4/embedded/eksamnen/M8f3.png | bin | 0 -> 38125 bytes | |||
| -rw-r--r-- | sem4/embedded/eksamnen/M8opg.adoc | 116 | ||||
| -rw-r--r-- | sem4/embedded/eksamnen/notes.adoc | 40 | ||||
| -rwxr-xr-x | sem4/embedded/eksamnen/schedsolver.rb | 74 |
6 files changed, 217 insertions, 13 deletions
diff --git a/sem4/embedded/eksamnen/M8f1.png b/sem4/embedded/eksamnen/M8f1.png Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 |
