CS 452/652 Winter 2020 - Lecture 23

Priorities (cont'd)

Priority Inversion

• lower-priority tasks indirectly keeps higher-priority task from running
• performance (latency) problem
• correctness problem (starvation), if system fully loaded
• examples: lower number = higher priority
• example scenario B
  • t11 sends to t10, then t5 preempts
  • t5 preempts work done for t1
  • ⇒ adjust server priority to current client's priority
• example scenario B
  • t10 sends to t1, then t5 wants to run
  • t1 runs on behalf of t10, so t5 should be able to preempt
  • ⇒ adjust server priority to current client's priority
• example scenario C
  • t10 runs on behalf of t8, t7 preempts, then t5 wants to send to t10
  • t7 keeps t10 from completing its computation, t5 blocked
  • ⇒ boost server priority to waiting client's priority
• also: priority-based Send queues?

Sensor Processing

• intuition: run sensor querying at highest possible priority
• caveat: track communication is half-duplex
• sensor reports → track commands
• ordering track commands vs. next sensor query?

Kernel Testing

• repeat speed measurements as kernel testing method
  • should see similar measurements
• test reliability of train commands
  • speed variation and timing
  • change direction and verify using sensors
  • add lights on/off to increase command intensity

Routing

• Floyd-Warshall Algorithm
  • brute-force iteration of links with O(N³) complexity
  • ok for dense graphs
• Dijkstra's Algorithm
  • less computational overhead for sparse graphs
  • notation:
    

    N	set of nodes
    N'	set of 'visited' nodes
    c(u,v)	link cost u→v, possibly ∞
    D(u,v)	path cost u→v
    P(u,v)	2nd-last hop on path from u→v

    
    
  • algorithm at Node u

    N' = { u }
    D(u,v) = c(u,v) for all neighbours v of u
    loop:
      find w not in N' with minimum D(u,w)
      add w to N'
      for all v not in N' and adjacent to w:
        if (D(u,w) + c(w,v) < D(u,v)):
            D(u,v) = D(u,w) + c(w,v)
            P(u,v) = w
    until N' == N
    

  • invariant at step k: N' contains nearest k destinations
    → i.e., the shortest paths to k destinations are known
  • result: trace previous hops P(u,v) backwards to obtain full path and next hop information
  • complexity
    • O(N) for 'find w', but heap-sort could reduce to O(log N)
    • O(E) for 'for all v'
    • O(N) for running the algorithm for all nodes
    • worst-case O(N³), with heap O(N² log N)
    • sparse graph: E << N (cf. Floyd-Warshall)
  • example taken from Slide 4-83 of Kurose/Ross textbook slides