diff options
Diffstat (limited to 'sem4/embedded/eksamnen')
| -rw-r--r-- | sem4/embedded/eksamnen/M7opg.md | 0 | ||||
| -rw-r--r-- | sem4/embedded/eksamnen/notes.md | 161 | ||||
| -rwxr-xr-x | sem4/embedded/eksamnen/schedsolver.rb | 185 |
3 files changed, 346 insertions, 0 deletions
diff --git a/sem4/embedded/eksamnen/M7opg.md b/sem4/embedded/eksamnen/M7opg.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/sem4/embedded/eksamnen/M7opg.md diff --git a/sem4/embedded/eksamnen/notes.md b/sem4/embedded/eksamnen/notes.md new file mode 100644 index 0000000..450740a --- /dev/null +++ b/sem4/embedded/eksamnen/notes.md @@ -0,0 +1,161 @@ + +## J1 module 1 + +> Show code and explain for 1,4,5,6 (design and impl ISR, time based debouncing, tick routing, limitations) + +TODO med arduino. +Og debouncer. + +### Noter + +Findes forskellige slags realtime afhængig af hvor vigtigt det er at man laver +sin opgave inden for deadline. + +- **Hard** er når en manglende deadline tæller som en system fejl. +- **Firm** nogle deadlines på gerne misses, men disse resultater vil være ubrugelige. +- **Soft** et resultat er ikke nær så meget værd hvis det er forsent, men kan stadig bruges. + +## H1 module 2 + +> Exercise 1-11 + +See ../emb_m2/emb_m2.ino + +TODO med arduino + +### Noter + +**Q-format** er hver man dedikere nogle af bits til decimaler. +Det er derfor ikke *floating* point. + +**Floating points** er decimal tak med en floating point. +Her har man kun et bestemt tal betydende cifre. + +TODO læs op på error calculus. +Totalt uforståeligt i slides. + +Der findes forskellige måder at have negative tal på. + +- Signed + Her bruger man MSB til at betyde sign. + Når den er 1 er det et minutal. + Problemet er at der nu er 2 nuller. +- 1's komplement + Ligesom *signed* men når det er negativt er alle bits flippet. + Dette gør det meget lettere at lave matematik på det. + Her er stadig det problem at der er 2 nuller. +- 2's komplement + Ligesom *1.s komplement* men negative har 1 lagt til. + Dette betyder at der kun er 1 nul værdi. + +## H2 module 3 + +> Exercise 4-7 + +TODO lav det her på arduino. + +### Noter + +To forskellige hoved protokoller. + +- ASCII + Let at læse at læse for en person. + Det er nemmere at seperere felter. + Bare ikke særlig efficient. +- Binary + Inviklet af seperere felter, da data felter kan indeholder delimiters. + Mere efficient. + +Findes fire forskellige structurelle elementer. + +- Sequence + Flere elementer efter hinnanden. +- Alternation + Enten den ene eller anden type element. +- Repetition + Lister af det samme elemtn +- Abstraction + Structure og egne data typer. + +**Haming distance** er hvor mange bits er forskellige mellem to bit sekvenser. + +**Haming distance of protection code** hvor langt der er imellem to sekvenser +der stadig er korrekte. +Dette kan man kande for *HD*. + +- Hvis *HD* er større end *n* kan man detect *n* bit errors. +- Hvis *HD* er større end *2n* kan man fixe *n* bit errors. + +Fletcher *HD* er 2 så man kan detect en bit fejl. + +## J2 module 4 + +> Show LED13 blink code and explain program. + +> Explain interrupt + +> Lack of control maybe bq of non-interruptable ISRs + +> Procesmodel: running,ready,blocked + +> semaphore wait and signal + +## J3 module 5 + +> What is a semaphore, show code from above and eplaing critical region setup + +## J4 module 6 + +> Show code for and explain message queues as a buffering tool. + +## J5 module 6.5 + +> Exercise 1 in part3 on page295 (Pdf is on moodle) + +## H3 module 7 + +> Exercise 4-5 + +### Noter + +**Scheduling** er når flere opgaver eller jobs skal time shares på en CPU. +Et **Schedule** er plan for hvordan disse opgaver skal have tid. +Et schedule er **feasable** hvis alle jobs kan køres imellem deres readytime og +deadline. + +Der findes forskellige kategorier. + +- Fixed schedules + Jobs kører på tidspunkter man har bestemt for forhånd. + Og dette kører bare i loop. + Dette er ret simpelt og effektivt men ikke særlig fleksibelt. + + Her behøver man kun lave en plan hen til LCM eller Least Common Multiple af + tasks periods. +- Round robin + Fixed tidsrum er delt ud mellem jobs periodisk. + Simpelt og fleksiblet men ikke effekttivt. +- Fixed priority + Det er altid jobbet med højeste prioritet der kører. + Dette er simpelt og fleksibelt, men kun middelt effektivt. +- Dynamic priority + Her bruger man andre regler til at bestemme hvem der kører. + Dette giver de bedste resultater men er også mere komplekst. + +Utilization er *completion time* dividere med *period*. +Man kan definere CPU utilization som: + +$$ +U = \sum_{i=1}^N \frac{c_i}{T_i} +$$ + +*Rate Monotonic Scheduling* eller **RMA** er når man giver task med lav periode +højere prioritet. + +## H4 module 8 + +> Exercise 1-2 + +## H5 module 9 + +> All exercises diff --git a/sem4/embedded/eksamnen/schedsolver.rb b/sem4/embedded/eksamnen/schedsolver.rb new file mode 100755 index 0000000..ca2e619 --- /dev/null +++ b/sem4/embedded/eksamnen/schedsolver.rb @@ -0,0 +1,185 @@ +#!/usr/bin/env ruby + +require 'optparse' + +class Scheduler + def initialize(tasks) + @states = [] + @tasks = tasks + end + + def printHeader() + print "i".ljust(4, ' ') + @tasks.length.times do |i| + print "T#{i.to_s()}".ljust(4, ' ') + end + @tasks.length.times do |i| + print "R#{i.to_s()}".ljust(4, ' ') + end + @tasks.length.times do |i| + print "D#{i.to_s()}".ljust(4, ' ') + end + puts + end + + def printState(index, state) + print index.to_s().ljust(4, ' ') + @tasks.length.times do |i| + print state[:task] == i ? "|" : " " + print " "*3 + end + + state[:remain].each_with_index do |r, i| + print r.to_s().ljust(4, ' ') + + end + + @tasks.each do |task| + deadline = task[:deadline] - (index % task[:period]) + print deadline.to_s().ljust(4, ' ') + end + + puts + end + + def nextTask(index) + choices = [] + + if @states.length.zero? + choices = @tasks.length.times.to_a + else + @states.last[:remain].each_with_index do |r, i| + choices << i if r > 0 + end + end + + if choices.length.zero? + return nil + elsif choices.length == 1 + # If there is only one choice return that + return choices[0] + end + + + loop do + print "Next #{choices.to_s}:" + input = gets + if input == "\n" and @states.last + return @states.last[:task] + end + choice = Integer(input) + if choices.include?(choice) + return choice + end + end + end + + def calcNextState(index) + curtask = nextTask(index) + new = {:task => curtask, :remain => []} + @tasks.each_with_index do |task, i| + # Check if start of new period + if index % task[:period] == 0 + if @states.last and @states.last[:remain][i] > 0 + puts "Deadline missed in task #{i}" + exit + end + new[:remain] << task[:complete] + else + new[:remain] << @states.last[:remain][i] + end + end + + # Decrease the selected task + if curtask + new[:remain][curtask] -= 1 unless new[:remain][curtask].zero? + end + + return new + end + + def run() + 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| + new = calcNextState(i) + @states << new + + printState(i, new) + + end + end +end + +def taskFromString(str) + fields = str.split(",") + if fields.length < 2 + raise "#{str} does not contain enough fields" + end + + # Run for each field + def parseField(f, default = 0) + return f == nil ? Integer(default) : Integer(f) + end + + task = { + :period => parseField(fields[0]), + :complete => parseField(fields[1]), + :deadline => parseField(fields[2], fields[0]) + } + + return task +end + +class RmaSched < Scheduler + def nextTask(index) + smallestTask = nil + + @tasks.each_with_index do |task, i| + if @states.last and @states.last[:remain][i] == 0 + next + end + + smallestTask = i if !smallestTask or task[:period] < @tasks[i][:period] + 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 +end.parse! + +tasks = [] + +if options[:taskfile] + File.readlines(options[:taskfile]).each do |line| + tasks << taskFromString(line) + end +else + puts "T : period,completion time[,deadline]" + + loop do + print "T#{ tasks.length }: " + input = gets + if !input or input.delete_suffix!("\n") == "" + break + end + + tasks << taskFromString(input) + end +end + +puts tasks.inspect + +sch = RmaSched.new(tasks) +sch.run() |