15-410, S’04- 1 -Scheduling on MarsMar. 15, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL20b_Mars15-410“Delayed Impact”15-410, S’04- 2 -What Happened On Mars?Mars Pathfinder probe (1997)Mars Pathfinder probe (1997)Nice launchNice launchNice transitNice transitNice de-orbitNice de-orbitNice thump-down (inflatable air-bag)Nice thump-down (inflatable air-bag)Nice rover disembarkationNice rover disembarkationNice rover Nice rover spontaneous rebootsspontaneous reboots15-410, S’04- 3 -Internal Architecture“Information bus” (blackboard/whiteboard/...)“Information bus” (blackboard/whiteboard/...)High-priority bus manager threadMeteorological data gatheringMeteorological data gatheringOccasional activityLow-priority weather data threadCommunication with EarthCommunication with EarthMedium-priority communication threadWatchdog thread: “too quiet”? Watchdog thread: “too quiet”? RebootReboot15-410, S’04- 4 -What could go wrong?Weather dataWeather data locks “ bus” memory to publish locks “ bus” memory to publishHigh-priority High-priority bus managerbus manager must wait must wait15-410, S’04- 5 -What could go wrong?Bus memoryCPUWX Bus Comm15-410, S’04- 6 -What could go wrong?Bus memoryCPUWX Bus Comm15-410, S’04- 7 -What could go wrong?Weather dataWeather data locks “ bus” memory to publish locks “ bus” memory to publishHigh-priority High-priority bus managerbus manager must wait must waitInterruptInterrupt makes makes communicationcommunication runnable runnable“ Medium” priority, so preempts weather datacommunication then attempts to lock busHighest-priority runnable task, so it spin-waits15-410, S’04- 8 -What could go wrong?Bus memoryCPUWX Bus Comm(spin)15-410, S’04- 9 -What could go wrong?Bus memoryCPUWX Bus Comm(spin)TIME OUT15-410, S’04- 10 -What could go wrong?Bus memoryCPUWX Bus Comm(spin)TIME OUT15-410, S’04- 11 -Solution?VxWorks has two mutex flavorsVxWorks has two mutex flavorsNormalPriority InheritanceRover code initialized flavor via global variablesRover code initialized flavor via global variablesRover flew with “ debug” interpreter enabledRover flew with “ debug” interpreter enabledRead-eval loop waiting for commands% assign bus_mutex_flavor = MF_P_INHERITAll fixedAll fixed15-410, S’04- 12 -Weather Thread is BusyBus memoryCPUWX Bus Comm15-410, S’04- 13 -Bus Thread Waits: Priority Inherited!Bus memoryCPUWX Bus CommBoost15-410, S’04- 14 -Bus Thread Waits: Priority Inherited!Bus memoryCPUWX Bus CommBoost15-410, S’04- 15 -“ Low-Priority” Thread Finishes FastBus memoryCPUWX Bus Comm15-410, S’04- 16 -“ Low-Priority” Thread Finishes FastBus memoryCPUWX Bus Comm15-410, S’04- 17 -History of an IdeaPriority Inheritance Protocols: An Approach to Real-Priority Inheritance Protocols: An Approach to Real-Time SynchronizationTime SynchronizationIEEE Transactions on Computers 39:9Lui Sha (CMU SEI)Ragunathan Rajkumar (IBM Research -> CMU ECE)John Lehoczky (CMU Statistics)15-410, S’04- 18 -History of an IdeaEventsEvents1987-12 “ Manuscript” received1988-05 Revised1990-09 Published1997-07 Rescues Mars PathfinderHistory courtesy of Mike JonesHistory courtesy of Mike
View Full Document