CS 452/652 Spring 2022 - Lecture 20
Jul 7, 2022
prev next
Though Experiment: Perfect Train Control?
- need exact problem specification, example:
- given a topology, a set of trains, and a list of destinations for each train
→ determine optimal schedule
- but: what is optimal?
- time to last train at last destination?
- average trip duration?
- many other criteria possible
- also: assume error-free operation
- with exact problem specification
- formulate and solve optimization problem - computational complexity
- centralized computation difficult for many real world control problems
- or: design ad-hoc solution accommodate uncertainty (our approach)
- our goal is not overall perfection (which is not even properly specified), but:
- build interesting multi-task, real-time application
- model decentralized aspects of real-world system
Design Approach
- reservation server
- continuous reservations (no leapfrogging)
- consider directionality of reservation
- reservation interface: train, segment → accepted
- no time information
- travel server
- travel plan with expected timing
- entire plan, disregard conflicts
- query interface: location, time → train(s)
- route server
- determine path & feasibility (e.g. short move?)
- take into account exclusions?
- compute only for slow/stopped trains? offload with lower priority
- sensor server
- receive sensor reports via notifier
- query travel server
- send notification to train
- train task
- source/dest → obtain route from route server
- file travel plan
- drive train
- reserve track segments
- reserve beyond error branches
- reservation denied: slow/stop
- reservation invariant: reservation distance > stop distance
- release track segments
- periodic or sensor-based updates
- leave segment → release segment
- pass turnout → release error path
- stop → release rest of path
- set train speed
- switch reserved turnouts
- handle sensor, timeout notifications
- any problem? stop/slow, make new plan (timing and/or routing)
- conflict resolution:
- deadlock → back off
- move/avoid conflict zone by changing speeds
- find alternative paths
- computational overhead with more trains?
- failure model
- sensor: spurious vs. silence
- turnout: single-direction vs. derailment
- can't fix everything...
Interrupt Strategy
- objectives
- avoid interrupts: performance and control
- avoid buffering in kernel
- clock/timer: interrupts always needed
- can count interrupts and deliver via AwaitEvent
- expectations and error checking?
- make clock server not the highest priority?
- UART: TX interrupt cannot be always on
- TX interrupt for every send? unnecessary...
- loop: try-send → enable interrupt → wait
- can still buffer characters in user-level
- RX interrupt?
- think of tight loop: RX arrival → response needed → RX next arrival
- make receiver notifier lower priority than response tasks: track vs. terminal?
- think about layered safety?
- emergency stop (speed 15); regular stop (speed 0); collision avoidance
- also for speed re destination & collisions
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?
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 A
- t1 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?