# CS 452/652 Winter 2020 - Lecture 23

March 4, 2020 prev next

### 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(N3) complexity
• ok for dense graphs
• Dijkstra's Algorithm
• less computational overhead for sparse graphs
• notation:
Nset 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(N3), with heap O(N2 log N)
• sparse graph: E << N (cf. Floyd-Warshall)
• example taken from Slide 4-83 of Kurose/Ross textbook slides