From fc90ff2c6e8ee40701761a1da153496500d34cb0 Mon Sep 17 00:00:00 2001
From: Julian T <julian@jtle.dk>
Date: Fri, 5 Jun 2020 00:26:44 +0200
Subject: Added exam assignments for emb

---
 sem4/embedded/eksamnen/M7opg.md       |   0
 sem4/embedded/eksamnen/notes.md       | 161 +++++++++++++++++++++++++++++
 sem4/embedded/eksamnen/schedsolver.rb | 185 ++++++++++++++++++++++++++++++++++
 3 files changed, 346 insertions(+)
 create mode 100644 sem4/embedded/eksamnen/M7opg.md
 create mode 100644 sem4/embedded/eksamnen/notes.md
 create mode 100755 sem4/embedded/eksamnen/schedsolver.rb

(limited to 'sem4')

diff --git a/sem4/embedded/eksamnen/M7opg.md b/sem4/embedded/eksamnen/M7opg.md
new file mode 100644
index 0000000..e69de29
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()
-- 
cgit v1.2.3