Priority Inversion on Mars

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Ad

Priority Inversion on Mars
Jim Huang ( 黃敬群 ) <jserv.tw@gmail.com>
Mar 15, 2016 / NCKU, Taiwan

Mars Pathfinder• Mission
– Demonstrate new landing techniques: parachute and airbags
– Take pictures
– Analyze soil sample...

Mars Pathfinder
• Mars Pathfinder was originally designed as a
technology demonstration of a way to deliver an
instrumente...

Pictures taken from an early Mars rover

Mars Pathfinder Timeline
• November 16, 1996
– Russian Mars '96 orbiter/landers launched.
• November 17, 1996
– Mars '96 f...

New York Times: July 15, 1997
Mary Beth Murrill, a spokeswoman for NASA's Jet Propulsion
Laboratory, said transmission of ...

Pathfinder Configurations
• Spacecraft ran IBM RS6000 processor and WindRiver's
VxWorks RTOS
– 20 MIPS 128 MB of DRAM
for ...

Rover Sojourner
• The rover, capable of autonomous navigation and performance
of tasks, communicated with Earth via the la...

VMEbus
CPU
RS6000
Radio
Camera
Mil1553
Cruise stage
controls
thrusters,
valves,
a sun sensor,
a star scanner
Lander
interf...

Pathfinder Configurations
CPU
1553 bus
.
Vme bus
Interface cards
(radio, camera etc.)
Cruise part of
the equipment
Lander ...

Pathfinder used VxWorks RTOS
• Threads for the 1553 bus for data collection,
scheduled on every 1/8th sec cycle.
• 3 perio...

NASA Pathfinder
• fault-tolerance
– a watchdog timer was used to reset the system in the event
that the computer / softwar...

Pathfinder Problem
• Within a few days of landing, when Pathfinder started gathering
meteorological data, spacecraft began...

Pathfinder Problem
• Most of the time this combination worked fine
• However, with the following scenario:
– Data gatherin...

VxWorks RTOS
• Multiple tasks, each with an associated priority
– Higher priority tasks get to run before lower-priority t...

VxWorks RTOS
• Multiple tasks, each with an associated priority
– Higher priority tasks get to run before lower-priority t...

VxWorks RTOS
• Multiple tasks, each with an associated priority
– Higher priority tasks get to run before lower-priority t...

Priority Inversion
Information Bus
Mutex
Weather
Data Thread
Communication
Thread
Information Bus
Thread
Low priority Med ...

Priority Inversion
Information Bus
Mutex
Weather
Data Thread
Communication
Thread
Information Bus
Thread
Low priority Med ...

Priority Inversion
Information Bus
Mutex
• What happens when threads have different priorities?
• Comm thread runs for a l...

Pathfinder incident: Priority Inversion
Classical priority inversion problem due to shared system bus!
task 1 (high)
task ...

Priority Inversion
Unbounded Priority Inversion

Variant: Air transportation
• Priority(my_plane) < Priority(obama_plane)
• I arrived at the airport first and called sem_w...

Look into deeper
• VxWorks 5.x
• 2 tasks to control the 1553 bus and the attached
instruments.
– bc_sched task (called the...

28
Marsrobot general communication pattern
time
t1 - bus hardware starts via hardware control on the 8 Hz boundary.
The tr...

1553 communication
• Powered 1553 devices deliver data.
• Tasks in the system that access the information
collected over t...

VMEbus
CPU
RS6000
Radio
Camera
Mil1553
Cruise stage
controls
thrusters,
valves,
a sun sensor,
a star scanner
Lander
interf...

Dedicated systems' tasking model
P3
Thread
P4
started
thread
Shared
data
D Mailbox
D4 message queue
data usage

bc-dist
bc-sched
Spacecraft
function
taks 1
Spacecraft
function
tasks
Science
function
task 1
Science
function
tasks
Share...

IPC Mechanism
• Tasks wait on one or more IPC "queues" for messages
to arrive using the VxWorks select() mechanism to wait...

VxWorks select()
• Pending on multiple file descriptiors:
this routine permits a task to pend until one of a set of file
d...

Marsrobot
Shared ressource for
Communication
Using select()
Thread AThread A
Thread BThread B
Thread CThread C
Low priorit...

The problem, again
• Priority inversion occurs when a thread of low priority
blocks the execution of threads of higher pri...

Bounded Priority Inversion
• Suppose a high priority thread becomes blocked
waiting for an event to happen. A low priority...

ISR A
HIGH:
TASK A (40)
LOW
TASK C (30)
Bounded priority inversion
time
Lock
MUTEX (m)
Lock
MUTEX (m)
run
blocked
ready
Un...

Unbounded Priority Inversion
• Here the high level thread can be blocked indefinitely
by a medium priority thread.
• The m...

ISR A
HIGH:
TASK A (40)
LOW
TASK C (30)
Unbounded priority inversion
time
Lock
MUTEX (m)
Lock
MUTEX (m)
run
blocked
ready
...

Pathfinder Failure
• The failure was identified by the spacecraft as a failure
of the bc_dist task to complete its executi...

Comm thread
pre-emption
HIGH:
Bus thread
bc_sched
Marsrobot normal operation
time
Lock
SystemMUTEX (m)
run
blocked
ready
M...

Comm thread
pre-emption
HIGH:
Bus thread
bc_sched
LOW
Tasks
Marsrobot priority inversion
time
Lock
SystemMUTEX (m)
run
blo...

Priority Inversion
• The higher priority bc_dist task was blocked by the much lower
priority ASI/MET task that was holding...

Priority Inversion
• The select() mechanism creates a system_mutex to protect the "wait list" of
file descriptors for thos...

Mars PathFinder Solutions

As suspected, the Pathfinder computer, struggling
with several activities at once, reset itself each time
it could not car...

What is the Fix?
• Problem with priority inversion:
– A high priority thread is stuck waiting for a low priority thread
to...

What was the problem fixed?
• JPL had a replica of the Pathfinder system on the ground
– Special tracing mode maintrains l...

Debug the problem
• On replica on earth
• Total Tracing on
– Context switches
– Uses of synchronisation objects
– Interrup...

Bug Detection
• The software that flies on Mars Pathfinder has several
debug features within it that are used in the lab b...

Deadlock
• With priority inversion, eventually the system makes progress
– e.g., Comm thread eventually finishes and rest ...

Deadlock Definition
• Two kinds of resources:
– Preemptible: Can take away from a thread
• e.g., the CPU
– Non-preemptible...

Conditions for Deadlock
• Limited access to a resource
– Means some threads will have to wait to access a shared resource
...

Get rid of deadlock
• Unlimited access to a resource?
– Requires that all resources allow arbitrary number of concurrent
a...

Resource Access Protocols

Priority Inversion
Priority Inheritance

Resource Access Protocols
• Critical sections: sections of code at which
exclusive access to some resource must be
guarant...

Reference
• Mars pathfinder failure, Martin TIMMERMAN
• Operating Systems, Paulo Marques, Departamento de
Eng. Informática...

Share SlideShare

Facebook
Twitter
LinkedIn

Embed

Size (px)

Show related SlideShares at end

WordPress Shortcode

Link

Share
Email

How to write good autotests by Þorgeir Ingvarsson 20270 views
Amusing Geometry in Test Automation by Þorgeir Ingvarsson 16722 views
The Dangers of Cucumber by Þorgeir Ingvarsson 39393 views
中輟生談教育: 完全用開放原始碼軟體進行嵌入式系統教學 by National Cheng Ku... 26697 views
Making Linux do Hard Real-time by National Cheng Ku... 48596 views
進階嵌入式系統開發與實做 (2014 年秋季 ) 課程說明 by National Cheng Ku... 8437 views

Top clipped slide

1 of 59 Ad

1 of 59 Ad