Michael B. Jones is Director of Identity Partnerships at Microsoft. He is working with a broad coalition of people across multiple industries to build the Internet’s missing Identity layer. He represents Microsoft on the Information Card Foundation and OpenID Foundation boards of directors. He just completed terms as president of the USENIX Association board of directors and board member of the Computing Research Association (CRA). He was a member of the Systems and Networking Research Group at Microsoft Research from 1992 to 2005. His research covered diverse topics in operating systems and distributed systems, including scalable peer-to-peer based event notification, real-time scheduling for open systems, and designing an early distributed fault-tolerant video server. He has organized and chaired numerous computer science research conferences, has a large set of publications, and has authored patents covering a diverse set of inventions. He is an active director of Asia Images, a specialty stock photography company.
Michael earned his Ph.D. in Computer Science from Carnegie Mellon University in 1992, where he was a member of the Mach project. He was a technical reviewer for the POSIX threads standards. His interests include digital identity, privacy-protecting systems, distributed systems, networking, operating systems, adaptive real-time systems, musical performance, outdoor activities, and his fellow human beings
The Problems You’re Having May Not Be the Problems You Think You’re Having: Results from a Latency Study of Windows NTMike Jones, John Regehr, Institute of Electrical and Electronics Engineers, Inc., March 1, 1999,
Adaptive Real-Time Resource Management Supporting Composition of Independently Authored Time-Critical ServicesMike Jones, in In Proceedings of the Fourth Workshop on Workstation Operating Systems (WWOS-IV), IEEE, October 1, 1993,
March 9, 2012
Rich Draves, Avie Tevanian, David Black, Mike Jones, and Joe Barrera
June 22, 2006
Brigham Young University
SkipNet and applications
SkipNet is an overlay network providing both practical locality properties and efficient communication. This release contains sources for the SkipNet overlay network and two other technologies built using it: the Overlook distributed name service, and the FUSE lightweight distributed failure notification system, plus applications exercising them. The SkipNet code and applications can be run in…
Size: 14 MB
- Participant, Identity Interop at Burton Group Catalyst Conference, San Diego, CA, July 2010.
- Sponsor and Participant, OpenID Summit EU, London, UK, June 2010.
- Participant, Internet Identity Workshop, Mountain View, CA, May 2010.
- Presenter and Organizer, 2010 Open Identity Summit West, Mountain View, CA, April 2010.
- Presenter, MIX10 Conference, Las Vegas, NV, March 2010.
- Exhibitor, OASIS Interop at RSA Security Conference, San Francisco, CA, March 2010.
- Participant, 2010 OpenID User Experience (UX) Summit, at Sears, Chicago, IL, February 2010
- Participant, Internet Identity Workshop, Mountain View, CA, November 2009.
- Presenter, 2009 OpenID Summit, at Yahoo, Mountain View, CA, November 2009.
- Participant, Digital Identity World, Las Vegas, NV, September, 2009.
- Participant, Burton Group Catalyst Conference, San Diego, CA, July 2009.
- Participant, Internet Identity Workshop, Mountain View, CA, May 2009.
- Participant, European Identity Conference, and Presenter at OASIS workshop, Munich, Germany, May 2009.
- Exhibitor, RSA Security Conference, San Francisco, CA, April 2009.
- Presenter, RSA Pre-Conference Workshop: Harnessing the Power of Digital Identity, San Francisco, CA, April 2009.
- Participant, OSIS Identity Interop, San Francisco, CA, April 2009.
- Participant, Burton Group Catalyst Conference, San Diego, CA, June 2008.
- Presenter, Internet Safety Task Force, Berkman Center for Internet and Society, Harvard, June 2008.
- Participant, Internet Identity Workshop, Mountain View, CA, May 2008.
- Exhibitor, RSA Security Conference, San Francisco, CA, April 2008.
- Exhibitor, GSM World Congress, Barcelona, February 2008.
- Exhibitor, Burton Group Catalyst Conference, Barcelona, October 2007.
- Participant, Microsoft Professional Developers Conference, (PDC), Los Angeles, CA, October 2007.
- Participant, Digital Identity World, San Francisco, CA, September 2007.
- Presenter and Exhibitor, Burton Group Catalyst Conference, San Francisco, CA, June 2007.
- Participant, ITU Focus Group on Identity Management, Mountain View, CA, May 2007.
- Participant, Internet Identity Workshop, Mountain View, CA, May 2007.
- Steering Committee, Eleventh Workshop on Hot Topics in Operating Systems (HotOS-XI), San Diego, CA, May 2007.
- Presenter, MIX ’07, Las Vegas, NV, April-May 2007.
- Presenter, Federal Trade Commission Workshop: Proof Positive: New Directions for ID Authentication, Washington, DC, April 2007.
- Steering Committee, Fourth USENIX Symposium on Networked Systems Design & Implementation, Cambridge, MA, April 2007.
- Presenter, Novell Brainshare Conference, Salt Lake City, UT, March 2007.
- Participant, ITU Focus Group on Identity Management, Geneva, Switzerland, February 2007.
- Participant, RSA Security Conference, San Francisco, February 2007.
- Participant, Mobile Identity Workshop, San Francisco, January 2007.
- Participant, Internet Dating Conference, Miami, FL, January 2007.
- Presenter, Burton Group Catalyst Conference, Barcelona, October 2006.
- Participant, Digital ID World Conference, Santa Clara, CA, September 2006.
- Participant, Berkman Center Identity Mashup Conference, Cambridge, MA, June 2006.
- Participant, Burton Group Catalyst Conference, San Francisco, June 2006.
- Presenter, JavaOne Conference, San Francisco, May 2006.
- Participant, Internet Identity Workshop, Mountain View, CA, May 2006.
- Presenter, Domain Roundtable Conference, Seattle, April 2006.
- Participant, MIX ’06, Las Vegas, NV, March 2006.
- Presenter, W3C Workshop on Secure Web Authentication, New York, NY, March 2006.
- Participant, PC Forum, Carlsbad, CA, March 2006.
- Participant, RSA Security Conference, San Jose, CA, February 2006.
- Presenter, Digital ID World for Financial Services, New York, NY, November 2005.
- Participant, Internet Identity Workshop, Berkeley, CA, October 2005.
- Presenter, Internet2 Member Meeting, Philadelphia, PA, September 2005.
- Presenter, Microsoft Professional Developers Conference (PDC), Los Angeles, September 2005.
- Participant, Digital ID World Conference, San Francisco, May 2005.
- Participant, Identity Gang Meeting at PC Forum, March 2005.
- Steering Committee, Seventh Symposium on Operating Systems Design and Implementation (OSDI ’06), Seattle, WA, November 2006.
- Program Committee, W3C Workshop on Transparency and Usability of Web Authentication, New York City, March 2006.
- Steering Committee, Third Symposium on Networked Systems Design and Implementation (NSDI ’06), San Jose, CA, May 2006.
- Steering Committee, Tenth Workshop on Hot Topics in Operating Systems (HotOS-X), Santa Fe, NM, June 2005.
- Steering Committee, Third International Conference on Mobile Systems, Applications, and Services (MobiSys ’05), Seattle, WA, June 2005.
- Attended Fourth Annual Digital ID World, San Francisco, CA, May 2005.
- Steering Committee, Second Symposium on Networked Systems Design and Implementation (NSDI ’05), Boston, MA, May 2005.
- Steering Committee, Sixth Symposium on Operating Systems Design and Implementation (OSDI ’04), San Francisco, CA, December 2004.
- Attended 18th Large Installation System Administration Conference (LISA ’04), Atlanta, GA, November 2004.
- Attended CRA Snowbird Conference, Snowbird, UT, July 2004.
- Steering Committee, Second International Conference on Mobile Systems, Applications, and Services (MobiSys ’04), Boston, MA, June 2004.
- Steering Committee, First Symposium on Networked Systems Design and Implementation (NSDI ’04), San Francisco, CA, March 2004.
- Attended 17th Large Installation System Administration Conference (LISA ’03), San Diego, CA, October 2003.
- Attended 19th ACM Symposium on Operating Systems Principles, Bolton Landing, NY, October 2003.
- Program Chair, Ninth Workshop on Hot Topics in Operating Systems (HotOS-IX), Kauai, Hawaii, May 2003.
- Steering Committee, First International Conference on Mobile Systems, Applications, and Services (MobiSys ’03), San Francisco, CA, May 2003.
- Attended Fourth USENIX Symposium on Internet Technologies and Systems (USITS ’03), Seattle, WA, March 2003.
- Steering Committee, Fifth Symposium on Operating Systems Design and Implementation (OSDI ’02), Boston, MA, December 2002.
- Steering Committee, Second Workshop on Industrial Experiences with Systems Software (WIESS ’02), December 2002.
- Attended ACM SIGCOMM 2002, Pittsburgh, PA, August 2002.
- Attended CRA Snowbird Conference, Snowbird, UT, July 2002.
- Presenter, 22nd International Conference on Distributed Computing Systems (ICDCS), Vienna, Austria, July 2002.
- Program Committee, 2002 USENIX Annual Technical Conference, Monterey, CA, June 2002.
- Program Committee, 18th ACM Symposium on Operating Systems Principles (SOSP ’01), Lake Louise, AB, October 2001.
- Attended ACM SIGCOMM 2001, San Diego, CA, August 2001.
- Paper, SIGMETRICS 2001 / Performance 2001, Cambridge, MA, June 2001.
- Presenter and Program Committee, Seventh IEEE Real-Time Technology and Application Symposium (RTAS 2001), Taipei, Taiwan, May-June 2001.
- Paper and Steering Committee, Eighth Workshop on Hot Topics in Operating Systems (HotOS-VIII), Schloss Elmau, Oberbayern, Germany, May 2001.
- Vice Chair, IEEE Computer Society Technical Committee on Operating Systems and Application Environments (TCOS), January 1999-April 2001.
- Attended 21st IEEE Real-Time Systems Symposium (RTSS 2000), Orlando, Florida, November 2000.
- Co-Chair with Frans Kaashoek of the Fourth USENIX Symposium on Operating Systems Design and Implementation (OSDI 2000), San Diego, October 2000.
- Steering Committee, First Workshop on Industrial Experiences with Systems Software (WIESS’2000), co-located with OSDI 2000.
- Steering Committee, Fourth USENIX Windows Systems Symposium, Seattle, August 2000.
- Program Committee, Sixth IEEE Real-Time Technology and Application Symposium (RTAS 2000), Washington D.C., May-June 2000.
- Program Committee, Eighth International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS 2000), Cancun, Mexico, May 2000.
- Panelist, Third IEEE International Symposium on Object-oriented Real-time distributed Computing (ISORC 2000), Newport Beach, CA, March 2000.
- Invited Speaker, IFIP WG 10.4 (Dependable Computing and Fault Tolerance) Workshop on Time and Dependability, Fort de France, Martinique, January 2000.
- 17th ACM Symposium on Operating Systems Principles (SOSP ’99), Kiawah Island Resort, near Charleston, SC, December 1999.
- Program Committee, 20th IEEE Real-Time Systems Symposium, Phoenix, Arizona, December 1999.
- Steering and Program Committees, Third USENIX Windows NT Symposium, Seattle, July 1999.
- Program Committee, Ninth International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV ’99), Basking Ridge, New Jersey, June 1999.
- Program Committee and Invited Speaker, Fifth IEEE Real-Time Technology and Applications Symposium, Vancouver, BC, June 1999.
- Steering Committee, Seventh Workshop on Hot Topics in Operating Systems (HotOS-VII), Rio Rico, Arizona, March 1999.
- Program Committee, Third USENIX Symposium on Operating Systems Design and Implementation (OSDI ’99), New Orleans, February 1999.
- Presenter, 19th IEEE Real-Time Systems Symposium, Madrid, December 1998.
- Invited participant, National Academy of Engineering Fourth Annual Symposium on Frontiers of Engineering, Irvine, September 1998.
- Presenter, DARPA Windows NT Research Workshop, August 1998.
- Steering and Program Committees, Second USENIX Windows NT Symposium in Seattle, August,1998.
- Program Committee, Eighth International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV ’98), Cambridge, England, July 1998.
- Program Committee and Panel Organizer, Fourth IEEE Real-Time Technology and Applications Symposium (RTAS ’98), Denver, June 1998.
- Panelist, 18th IEEE Real-Time Systems Symposium, San Francisco, December 1997.
- Co-Chair with Ed Lazowska of the first USENIX Windows NT Workshop, Seattle, August 1997.
- Program Committee, Third IEEE Real-Time Technology and Applications Symposium (RTAS ’97), Montreal, June 1997.
- Program Committee, Seventh International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV ’97), St. Louis, May 1997.
- Steering Committee, Sixth Workshop on Hot Topics in Operating Systems (HotOS-VI), Cape Cod, May 1997.
- Invited Speaker, 17th IEEE Real-Time Systems Symposium, Washington D.C., December 1996.
- Co-Local Arrangements Chair, Fifth IEEE International Workshop on Object-Orientation in Operating Systems (IWOOOS ’96), Seattle, October 1996.
- Invited participant in the Real-Time Working Group of the ACM Workshop on Strategic Directions in Computing Research, MIT, June 1996. Here’s my position statement.
- Program Committee, Second IEEE Real-Time Technology and Applications Symposium (RTAS ’96), Boston, June 1996.
- Program Committee and Work-In-Progress Session Czar, 15th ACM Symposium on Operating Systems Principles (SOSP ’95), Copper Mountain Resort, December 1995.
- General Chair, Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), Orcas Island, May 1995.
Research Projects at Microsoft Research
- Singularity: My most recent research work was with the Singularity project. Singularity is a research operating system that only loads and runs type-safe managed code.
- Herald: I worked from 2001 through 2004 on the Herald project. Herald’s goal was to build a publish/subscribe event notification service deployed as a self-configuring federation of peers designed to scale to Internet size and to provide timely delivery of notifications.
- Consumer Real-Time: I worked for several years in the area of Consumer Real-Time. My goal was to make it possible to develop independent real-time applications independently, while enabling their predictable concurrent execution, both with each other and with non-real-time applications. This project began with the Rialto work using the Microsoft Interactive TV kernel and continued with Rialto/NT, which was based on Windows NT.
- Rialto: Rialto’s goal was to make it possible to develop independent real-time applications independently, while enabling their predictable concurrent execution, both with each other and with non-real-time applications. Towards this end, we built a small real-time operating system designed to support advanced consumer multimedia applications, and used it as a test-bed to experiment with CPU scheduling and resource negotiation abstractions.
- Tiger: We built a scalable, fault-tolerant distributed multimedia file system using commodity hardware. Both Rialto and Tiger were used in Microsoft’s Interactive TV trial with NTT in Yokosuka, Japan.
Research Projects at Carnegie Mellon University, etc.
- Interposition Agents: I built A Toolkit for Interposing User Code at the System Interface (my Ph.D. thesis system at CMU).
- Mach: The CMU Mach operating system project built a multi-threaded, multiprocessor, microkernel operating system that was used as the basis for NextStep and MacOS X.
- Taos: I worked on the Distributed Name Service for the Taos distributed operating system at the DEC Systems Research Center (DEC SRC).
- SPICE: The CMU Scientific Personal Integrated Computing Environment (SPICE) project built message-based operating system and applications for a networked “3M” workstation, one with a megapixel display, a megabyte of memory, and a 1 Mips processor.
Offices Held and Ongoing Roles
- Board member of the Information Card Foundation.
- Board member and executive committee member of the OpenID Foundation.
Offices Recently Held
- Board officer of the USENIX Association, 2000-2008 (Treasurer 2000-2002, Vice President 2002-2004, Board President, 2004-2008).
- Board member of the Computing Research Association, 2002-2008.
- I was pleased to have Chip Killian from Duke University and UCSD work with me on the Singularity project during the summer of 2004. He ported the Rialto real-time scheduler into the Singularity kernel.
- It was a pleasure to have Dejan Kostic from Duke University work with me on the Herald project during the summer of 2003. His work on FUSE: A Lightweight Guaranteed Distributed Failure Notification System was published at OSDI ’04.
- I was again thrilled to have Stefan Saroiu from the University of Washington work with me again during the summer of 2002, this time on the Herald project. His work included SkipNet: A Scalable Overlay Network with Practical Locality Properties, which received the best paper award at USITS ’03.
- I was pleased to have Krishna Gummadi from the University of Washington working with me on the Herald project during the summer of 2001.
- I was thrilled with the work that Stefan Saroiu from the University of Washington did with me during the summer of 2000. He performed a detailed study of the performance characteristics and resource requirements of a popular soft modem, and showed that scheduling the modem’s signal processing computations with a real-time scheduler can improve the timing predictability of other applications running concurrently with it. He presented a paper on this work at SIGMETRICS 2001.
- During the summers of 1998 and 1999 I was pleased to have John Regehr from the University of Virginia working with me as a research intern. Among other accomplishments, during his 1998 internship we co-authored a paper on latency in Windows NT for NOSSDAV ’98 and fed a timer latency bug fix he developed back to the Windows NT developers. Continuing our collaboration after his initial internship, we presented additional latency results at HotOS-VII and co-authored a paper on Rialto-style scheduling on Windows NT for the Third USENIX Windows NT Symposium. During the summer of 1999 John also continued development of the Rialto/NT scheduler as well as studied the effectiveness of applying CPU Reservations to a digital audio player application. Since his internship, we co-authored the position paper Operating System Support for Multimedia: The Programming Model Matters with his advisor Jack Stankovic.
- It was great working with George Candea from MIT LCS during the summer of 1997 on several real-time projects, including a system we called Vassal that allows run-time loading of new scheduling policies, which is described in our paper in the Second USENIX Windows NT Symposium. The paper was given the best student paper award.
- I was delighted at the work Daniela Rosu and Marcel-Catalin Rosu from the Georgia Tech College of Computing did with me during the summer of ’96, culminating in our joint SOSP paper on CPU Reservations and Time Constraints.
Just for fun
Amazing photos from the Palio
See what it’s like to have front row seats at the oldest continuously run horse race in the world — the Palio in Siena Italy. In the race we attended in August 2007, 5 of the 10 starting jockeys completed the 3-lap bareback, no-holds-barred race around the town square. I could have touched one of them as he came unseated. Amazing!
After a successful computing archaeology effort, as of September 2002,
the original bboard post in which the smiley :-) was invented
by Scott Fahlman in September 1982 is back online!
The First Smiley
The smiley 🙂 and its many variants are an important (and fun!) part of the worldwide online social culture — allowing emotions to be conveyed in plain text. It has been in widespread use since the early ’80s, when it was first proposed. Yet the original message in which the smiley was invented had been lost — until now. 🙂 After a significant effort to locate it, on September 10, 2002 the original post made by Scott Fahlman on CMU CS general bboard was retrieved by Jeff Baird from an October 1982 backup tape of the spice vax (cmu-750x).
Here is Scott’s original post:
19-Sep-82 11:44 Scott E Fahlman :-)From: Scott E Fahlman
I propose that the following character sequence for joke markers: 🙂 Read it sideways. Actually, it is probably more economical to markthings that are NOT jokes, given current trends. For this, use 🙁
To see the post in context you can read the “joke” thread on the bboard that led to the invention of the smiley. For even more context you can view the full contents of the bboard from the October 1982 spice vax backup tape. Also, see Scott’s page about the smiley.
Credits: Many people were involved in this computing archaeology success story. I (Mike Jones) kicked off the effort in February 2002 by looking through some old bboard program (Bags) sources, figuring out the filename that the post would likely be found under (/usr/cmu/lib/bb/general.bb), and asking Howard Wactlar, the former CMU SCS facilities director, whether the file could still be restored. Scott Fahlman provided data narrowing the probable span of time during which the post was made. Howard and Bob Cosgrove, the current director, determined that backup tapes from that period (1981-1983) still existed and asked Jeff Baird of the facilities staff to try to find and restore the post. Dave Livingston of facilities located a working 9-track tape drive and a machine to use it on. Kirk Berthold and Michael Riley in CS operations managed retrieving tapes from off-site archival storage. Grad student Dan Pelleg’s FreeBSD machine was used to read the 4.1BSD dump format tapes using a compatibility mode in the restore program. (Later in the effort a NetBSD machine was used to do the same thing.) Dale Moore looked for the post on Tops-20 backup tapes from CMU-20C. But by all accounts, Jeff Baird should get most of the credit for doing the hard work of locating and retrieving the data. He kept asking for more tapes, reading those that could still be read, narrowing the date range, and sticking with it until the post was found. Thanks all for your efforts to restore this part of computing history, and especially, thanks Jeff!
— Mike Jones (who worked at CMU when the post was made and remembers thinking when he read it “what a good idea!”) – September 12, 2002
Real-World (Out of This World) Story
The Mars Pathfinder mission was widely proclaimed as “flawless” in the early days after its July 4th, 1997 landing on the Martian surface. Successes included its unconventional “landing” — bouncing onto the Martian surface surrounded by airbags, deploying the Sojourner rover, and gathering and transmitting voluminous data back to Earth, including the panoramic pictures that were such a hit on the Web. But a few days into the mission, not long after Pathfinder started gathering meteorological data, the spacecraft began experiencing system resets. The press reported these failures in terms such as “software glitches” and “the computer was trying to do too many things at once”. Read What really happened on Mars? Also, be sure to read this follow-up message from Glenn Reeves of JPL, who led the software team for the Mars Pathfinder spacecraft.
What Really Happened On Mars?
From: Mike Jones email@example.com; Sent: Sunday, December 07, 1997 6:47 PM Subject: What really happened on Mars?
The Mars Pathfinder mission was widely proclaimed as “flawless” in the early days after its July 4th, 1997 landing on the Martian surface. Successes included its unconventional “landing” — bouncing onto the Martian surface surrounded by airbags, deploying the Sojourner rover, and gathering and transmitting voluminous data back to Earth, including the panoramic pictures that were such a hit on the Web. But a few days into the mission, not long after Pathfinder started gathering meteorological data, the spacecraft began experiencing total system resets, each resulting in losses of data. The press reported these failures in terms such as “software glitches” and “the computer was trying to do too many things at once”.
This week at the IEEE Real-Time Systems Symposium I heard a fascinating keynote address by David Wilner, Chief Technical Officer of Wind River Systems. Wind River makes VxWorks, the real-time embedded systems kernel that was used in the Mars Pathfinder mission. In his talk, he explained in detail the actual software problems that caused the total system resets of the Pathfinder spacecraft, how they were diagnosed, and how they were solved. I wanted to share his story with each of you.
VxWorks provides preemptive priority scheduling of threads. Tasks on the Pathfinder spacecraft were executed as threads with priorities that were assigned in the usual manner reflecting the relative urgency of these tasks.
Pathfinder contained an “information bus”, which you can think of as a shared memory area used for passing information between different components of the spacecraft. A bus management task ran frequently with high priority to move certain kinds of data in and out of the information bus. Access to the bus was synchronized with mutual exclusion locks (mutexes).
The meteorological data gathering task ran as an infrequent, low priority thread, and used the information bus to publish its data. When publishing its data, it would acquire a mutex, do writes to the bus, and release the mutex. If an interrupt caused the information bus thread to be scheduled while this mutex was held, and if the information bus thread then attempted to acquire this same mutex in order to retrieve published data, this would cause it to block on the mutex, waiting until the meteorological thread released the mutex before it could continue. The spacecraft also contained a communications task that ran with medium priority.
Most of the time this combination worked fine. However, very infrequently it was possible for an interrupt to occur that caused the (medium priority) communications task to be scheduled during the short interval while the (high priority) information bus thread was blocked waiting for the (low priority) meteorological data thread. In this case, the long-running communications task, having higher priority than the meteorological task, would prevent it from running, consequently preventing the blocked information bus task from running. After some time had passed, a watchdog timer would go off, notice that the data bus task had not been executed for some time, conclude that something had gone drastically wrong, and initiate a total system reset.
This scenario is a classic case of priority inversion.
HOW WAS THIS DEBUGGED?
VxWorks can be run in a mode where it records a total trace of all interesting system events, including context switches, uses of synchronization objects, and interrupts. After the failure, JPL engineers spent hours and hours running the system on the exact spacecraft replica in their lab with tracing turned on, attempting to replicate the precise conditions under which they believed that the reset occurred. Early in the morning, after all but one engineer had gone home, the engineer finally reproduced a system reset on the replica. Analysis of the trace revealed the priority inversion.
HOW WAS THE PROBLEM CORRECTED?
When created, a VxWorks mutex object accepts a boolean parameter that indicates whether priority inheritance should be performed by the mutex. The mutex in question had been initialized with the parameter off; had it been on, the low-priority meteorological thread would have inherited the priority of the high-priority data bus thread blocked on it while it held the mutex, causing it be scheduled with higher priority than the medium-priority communications task, thus preventing the priority inversion. Once diagnosed, it was clear to the JPL engineers that using priority inheritance would prevent the resets they were seeing.
VxWorks contains a C language interpreter intended to allow developers to type in C expressions and functions to be executed on the fly during system debugging. The JPL engineers fortuitously decided to launch the spacecraft with this feature still enabled. By coding convention, the initialization parameter for the mutex in question (and those for two others which could have caused the same problem) were stored in global variables, whose addresses were in symbol tables also included in the launch software, and available to the C interpreter. A short C program was uploaded to the spacecraft, which when interpreted, changed the values of these variables from FALSE to TRUE. No more system resets occurred.
ANALYSIS AND LESSONS
First and foremost, diagnosing this problem as a black box would have been impossible. Only detailed traces of actual system behavior enabled the faulty execution sequence to be captured and identified.
Secondly, leaving the “debugging” facilities in the system saved the day. Without the ability to modify the system in the field, the problem could not have been corrected.
Finally, the engineer’s initial analysis that “the data bus task executes very frequently and is time-critical — we shouldn’t spend the extra time in it to perform priority inheritance” was exactly wrong. It is precisely in such time critical and important situations where correctness is essential, even at some additional performance cost.
HUMAN NATURE, DEADLINE PRESSURES
David told us that the JPL engineers later confessed that one or two system resets had occurred in their months of pre-flight testing. They had never been reproducible or explainable, and so the engineers, in a very human-nature response of denial, decided that they probably weren’t important, using the rationale “it was probably caused by a hardware glitch”.
Part of it too was the engineers’ focus. They were extremely focused on ensuring the quality and flawless operation of the landing software. Should it have failed, the mission would have been lost. It is entirely understandable for the engineers to discount occasional glitches in the less-critical land-mission software, particularly given that a spacecraft reset was a viable recovery strategy at that phase of the mission.
THE IMPORTANCE OF GOOD THEORY/ALGORITHMS
David also said that some of the real heroes of the situation were some people from CMU who had published a paper he’d heard presented many years ago who first identified the priority inversion problem and proposed the solution. He apologized for not remembering the precise details of the paper or who wrote it. Bringing things full circle, it turns out that the three authors of this result were all in the room, and at the end of the talk were encouraged by the program chair to stand and be acknowledged. They were Lui Sha, John Lehoczky, and Raj Rajkumar. When was the last time you saw a room of people cheer a group of computer science theorists for their significant practical contribution to advancing human knowledge? 🙂 It was quite a moment.
For the record, the paper was:
L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. In IEEE Transactions on Computers, vol. 39, pp. 1175-1185, Sep. 1990.
Note: This note was widely circulated after I sent it to a few friends in the systems community. Among other places, it appeared in Peter G. Neumann’s moderated Risks Forum (comp.risks) on Tuesday, 9 December 1997 in issue RISKS-19.49.
Follow-Up Message from Glenn Reeves of JPL
From: Glenn E Reeves[SMTP:Glenn.E.Reeves@jpl.nasa.gov]
Sent: Monday, December 15, 1997 10:28 AM
To: firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; Mike Jones; firstname.lastname@example.org; email@example.com; David.Cummings@andrew.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; John Krumm; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; Thomas Blumer; shep@sunne.East.Sun.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; Richard A Volpe; Richard V Welch; Henry W Stone; Allen R Sirota; Kim P Gostelow; Robert D Rasmussen; David J Eisenman; Daniel E Erickson; Udo Wehmeier; Peter R Gluck; David E Smyth; Robert C Barry; Steven A Stolper; Alfred D Schoepke; David C Gruel; Guy S Beutelschies; Robert M Manning; Friedrich A Krug; Samuel H Zingales; Steven M Collins; J Morgan Parker
Subject: Re: [Fwd: FW: What really happened on Mars?]
What really happened on Mars ?
By now most of you have read Mike’s (email@example.com) summary of Dave Wilner’s comments given at the IEEE Real-Time Systems Symposium. I don’t know Mike and I didn’t attend the symposium (though I really wish I had now) and I have not talked to Dave Wilner since before the talk. However, I did lead the software team for the Mars Pathfinder spacecraft. So, instead of trying to find out what was said I will just tell you what happened. You can make your own judgments.
I sent this message out to everyone who was a recipient of Mike’s original that I had an email address for. Please pass it on to anyone you sent the first one to. Mike, I hope you will post this wherever you posted the original.
Since I want to make sure the problem is clearly understood I need to step through each of the areas which contributed to the problem.
The simplified view of the Mars Pathfinder hardware architecture looks like this. A single CPU controls the spacecraft. It resides on a VME bus which also contains interface cards for the radio, the camera, and an interface to a 1553 bus. The 1553 bus connects to two places : The “cruise stage” part of the spacecraft and the “lander” part of the spacecraft. The hardware on the cruise part of the spacecraft controls thrusters, valves, a sun sensor, and a star scanner. The hardware on the lander part provides an interface to accelerometers, a radar altimeter, and an instrument for meteorological science known as the ASI/MET. The hardware which we used to interface to the 1553 bus (at both ends) was inherited from the Cassini spacecraft. This hardware came with a specific paradigm for its usage : the software will schedule activity at an 8 Hz rate. This **feature** dictated the architecture of the software which controls both the 1553 bus and the devices attached to it.
THE SOFTWARE ARCHITECTURE
The software to control the 1553 bus and the attached instruments was implemented as two tasks. The first task controlled the setup of transactions on the 1553 bus (called the bus scheduler or bc_sched task) and the second task handled the collection of the transaction results i.e. the data. The second task is referred to as the bc_dist (for distribution) task. A typical timeline for the bus activity for a single cycle is shown below. It is not to scale. This cycle was constantly repeated.
The *** are periods when tasks other than the ones listed are executing. Yes, there is some idle time.
t1 – bus hardware starts via hardware control on the 8 Hz boundary. The transactions for the this cycle had been set up by the previous execution of the bc_sched task.t2 – 1553 traffic is complete and the bc_dist task is awakened.t3 – bc_dist task has completed all of the data distributiont4 – bc_sched task is awakened to setup transactions for the next cyclet5 – bc_sched activity is complete
The bc_sched and bc_dist tasks check each cycle to be sure that the other had completed its execution. The bc_sched task is the highest priority task in the system (except for the vxWorks “tExec” task). The bc_dist is third highest (a task controlling the entry and landing is second). All of the tasks which perform other spacecraft functions are lower. Science functions, such as imaging, image compression, and the ASI/MET task are still lower.
Data is collected from devices connected to the 1553 bus only when they are powered. Most of the tasks in the system that access the information collected over the 1553 do so via a double buffered shared memory mechanism into which the bc_dist task places the latest data. The exception to this is the ASI/MET task which is delivered its information via an interprocess communication mechanism (IPC). The IPC mechanism uses the vxWorks pipe() facility. Tasks wait on one or more IPC “queues” for messages to arrive. Tasks use the select() mechanism to wait for message arrival. Multiple queues are used when both high and lower priority messages are required. Most of the IPC traffic in the system is not for the delivery of real-time data. However, again, the exception to this is the use of the IPC mechanism with the ASI/MET task. The cause of the reset on Mars was in the use and configuration of the IPC mechanism.
The failure was identified by the spacecraft as a failure of the bc_dist task to complete its execution before the bc_sched task started. The reaction to this by the spacecraft was to reset the computer. This reset reinitializes all of the hardware and software. It also terminates the execution of the current ground commanded activities. No science or engineering data is lost that has already been collected (the data in RAM is recovered so long as power is not lost). However, the remainder of the activities for that day were not accomplished until the next day.
The failure turned out to be a case of priority inversion (how we discovered this and how we fixed it are covered later). The higher priority bc_dist task was blocked by the much lower priority ASI/MET task that was holding a shared resource. The ASI/MET task had acquired this resource and then been preempted by several of the medium priority tasks. When the bc_sched task was activated, to setup the transactions for the next 1553 bus cycle, it detected that the bc_dist task had not completed its execution. The resource that caused this problem was a mutual exclusion semaphore used within the select() mechanism to control access to the list of file descriptors that the select() mechanism was to wait on.
The select mechanism creates a mutual exclusion semaphore to protect the “wait list” of file descriptors for those devices which support select. The vxWorks pipe() mechanism is such a device and the IPC mechanism we used is based on using pipes. The ASI/MET task had called select, which had called pipeIoctl(), which had called selNodeAdd(), which was in the process of giving the mutex semaphore. The ASI/ MET task was preempted and semGive() was not completed. Several medium priority tasks ran until the bc_dist task was activated. The bc_dist task attempted to send the newest ASI/MET data via the IPC mechanism which called pipeWrite(). pipeWrite() blocked, taking the mutex semaphore. More of the medium priority tasks ran, still not allowing the ASI/MET task to run, until the bc_sched task was awakened. At that point, the bc_sched task determined that the bc_dist task had not completed its cycle (a hard deadline in the system) and declared the error that initiated the reset.
HOW WE FOUND IT
The software that flies on Mars Pathfinder has several debug features within it that are used in the lab but are not used on the flight spacecraft (not used because some of them produce more information than we can send back to Earth). These features were not “fortuitously” left enabled but remain in the software by design. We strongly believe in the “test what you fly and fly what you test” philosophy.
One of these tools is a trace/log facility which was originally developed to find a bug in an early version of the vxWorks port (Wind River ported vxWorks to the RS6000 processor for us for this mission). This trace/log facility was built by David Cummings who was one of the software engineers on the task. Lisa Stanley, of Wind River, took this facility and instrumented the pipe services, msgQ services, interrupt handling, select services, and the tExec task. The facility initializes at startup and continues to collect data (in ring buffers) until told to stop. The facility produces a voluminous dump of information when asked.
After the problem occurred on Mars we did run the same set of activities over and over again in the lab. The bc_sched was already coded so as to stop the trace/log collection and dump the data (even though we knew we could not get the dump in flight) for this error. So, when we went into the lab to test it we did not have to change the software.
In less that 18 hours we were able to cause the problem to occur. Once we were able to reproduce the failure the priority inversion problem was obvious.
HOW WAS THE PROBLEM CORRECTED
Once we understood the problem the fix appeared obvious : change the creation flags for the semaphore so as to enable priority inheritance. The Wind River folks, for many of their services, supply global configuration variables for parameters such as the “options” parameter for the semMCreate used by the select service (although this is not documented and those who do not have vxWorks source code or have not studied the source code might be unaware of this feature). However, the fix is not so obvious for several reasons :
- The code for this is in the selectLib() and is common for all device creations. When you change this global variable all of the select semaphores created after that point will be created with the new options. There was no easy way in our initialization logic to only modify the semaphore associated with the pipe used for bc_dist task to ASI/MET task communications.
- If we make this change, and it is applied on a global basis, how will this change the behavior of the rest of the system ?
- The priority inheritance option was deliberately left out by Wind River in the default selectLib() service for optimum performance. How will performance degrade if we turn priority inheritance on ?
- Was there some intrinsic behavior of the select mechanism itself that would change if priority inheritance was enabled ?
We did end up modifying the global variable to include the priority inheritance option. This corrected the problem. We asked Wind River to analyze the potential impacts for (3) and (4). They concluded that the performance impact would be minimal and that the behavior of select() would not change so long as there was always only one task waiting for any particular file descriptor. This is true in our system. I believe that the debate at Wind River still continues on whether the priority inheritance option should be on as the default. For (1) and (2) the change did alter the characteristics of all of the select semaphores. We concluded, both by analysis and test, that there was no adverse behavior. We tested the system extensively before we changed the software on the spacecraft.
HOW WE CHANGED THE SOFTWARE ON THE SPACECRAFT
No, we did not use the vxWorks shell to change the software (although the shell is usable on the spacecraft). The process of “patching” the software on the spacecraft is a specialized process. It involves sending the differences between what you have onboard and what you want (and have on Earth) to the spacecraft. Custom software on the spacecraft (with a whole bunch of validation) modifies the onboard copy. If you want more info you can send me email.
WHY DIDN’T WE CATCH IT BEFORE LAUNCH ?
The problem would only manifest itself when ASI/MET data was being collected and intermediate tasks were heavily loaded. Our before launch testing was limited to the “best case” high data rates and science activities. The fact that data rates from the surface were higher than anticipated and the amount of science activities proportionally greater served to aggravate the problem. We did not expect nor test the “better than we could have ever imagined” case.
HUMAN NATURE, DEADLINE PRESSURES
We did see the problem before landing but could not get it to repeat when we tried to track it down. It was not forgotten nor was it deemed unimportant. Yes, we were concentrating heavily on the entry and landing software. Yes, we considered this problem lower priority. Yes, we would have liked to have everything perfect before landing. However, I don’t see any problem here other than we ran out of time to get the lower priority issues completed.
We did have one other thing on our side; we knew how robust our system was because that is the way we designed it.
We knew that if this problem occurred we would reset. We built in mechanisms to recover the current activity so that there would be no interruptions in the science data (although this wasn’t used until later in the landed mission). We built in the ability (and tested it) to go through multiple resets while we were going through the Martian atmosphere. We designed the software to recover from radiation induced errors in the memory or the processor. The spacecraft would have even done a 60 day mission on its own, including deploying the rover, if the radio receiver had broken when we landed. There are a large number of safeguards in the system to ensure robust, continued operation in the event of a failure of this type. These safeguards allowed us to designate problems of this nature as lower priority.
We had our priorities right.
ANALYSIS AND LESSONS
Did we (the JPL team) make an error in assuming how the select/pipe mechanism would work ? Yes, probably. But there was no conscious decision to not have the priority inheritance option enabled. We just missed it. There are several other places in the flight software where similar protection is required for critical data structures and the semaphores do have priority inversion protection. A good lesson when you fly COTS stuff – make sure you know how it works.
Mike is quite correct in saying that we could not have figured this out **ever** if we did not have the tools to give us the insight. We built many of the tools into the software for exactly this type of problem. We always planned to leave them in. In fact, the shell (and the stdout stream) were very useful the entire mission. If you want more detail send me a note.
SETTING THE RECORD STRAIGHT
First, I want to make sure that everyone understands how I feel in regard to Wind River. These folks did a fantastic job for us. They were enthusiastic and supported us when we came to them and asked them to do an affordable port of vxWorks. They delivered the alpha version in 3 months. When we had a problem they put some of the brightest engineers I have ever worked with on the problem. Our communication with them was fantastic. If they had not done such a professional job the Mars Pathfinder mission would not have been the success that it is.
Second, Dave Wilner did talk to me about this problem before he gave his talk. I could not find my notes where I had detailed the description of the problem. So, I winged it and I sure did get it wrong. Sorry Dave.
First, thanks to Mike for writing a very nice description of the talk. I think I have had probably 400 people send me copies. You gave me the push to write the part of the Mars Pathfinder End-of-Mission report that I had been procrastinating doing.
A special thanks to Steve Stolper for helping me do this.
The biggest thanks should go to the software team that I had the privilege of leading and whose expertise allowed us to succeed :
- Pam Yoshioka
- Dave Cummings
- Don Meyer
- Karl Schneider
- Greg Welz
- Rick Achatz
- Kim Gostelow
- Dave Smyth
- Steve Stolper
- Miguel San Martin
- Sam Sirlin
- Brian Lazara (WRS)
- Mike Deliman (WRS)
- Lisa Stanley (WRS)
Mars Pathfinder Flight Software Cognizant Engineer
- OASIS IMI 1.0 Standard: The OASIS Identity Metasystem Interoperability (IMI) 1.0 standard was approved on July 1, 2009.
- Information Card Foundation Board: In June 2008 I joined the Information Card Foundation board of directors as Microsoft’s representative, as announced on June 24th. Also see my personal perspective on the Information Card Foundation launch.
- OpenID Foundation Board: In January 2008 I joined the OpenID Foundation board of directors as Microsoft’s representative, as announced on February 7th. Also see my personal blog post supporting the announcement and Microsoft’s post at PressPass.
- Blogging: In April 2007 I launched self-issued.info, a blog for digital identity discussions. I hope you’ll find the content there useful, thought-provoking, and sometimes just plain fun. Let the conversation begin…
- Tighter Focus on Identity: In March 2007, I moved from the Web Services Interoperability team to the Federated Identity team (both within Microsoft’s Connected Systems Division). This move enables me to focus full-time on Digital Identity. I’m passionate about Identity and see it as a key enabler for making the online world both more personal and more valuable. I’m working with strategic customers and partners to drive adoption of privacy-enhancing, ubiquitously-accepted, easy-to-use identity solutions.
- Microsoft / OpenID Collaboration: Read about the Microsoft / OpenID collaboration on Kim Cameron’s blog and read thetranscript of Bill Gates’ and Craig Mundie’s speech announcing this at the RSA Security conference. We’re working together to bring the benefits of phishing-resistant authentication methods, such as Windows CardSpace, to the growing community of OpenID users.
- CardSpace One-Pager Published: This paper is a one-page introduction to Microsoft’s CardSpace software, which facilitates user-centric identity interactions online through an easy-to-use visual “Information Card” metaphor.
Michael B. Jones. A One-Page Introduction to Windows CardSpace, January 2007.
- Information Card Web Specification Published: This specification documents the web interfaces utilized by browsers and web applications that support Information Cards. The information in this document is not specific to any one browser or platform.
Michael B. Jones. A Guide to Supporting Information Cards within Web Applications and Browsers as of the Information Card Profile V1.0, December 2006.
- Identity Metasystem Design Rationale Paper Published: Many of the problems facing the Internet today stem from the lack of a widely deployed, easily understood, secure identity solution. Microsoft’s CardSpace software and the Identity Metasystem vision underlying it are aimed at filling this gap using technology all can adopt and solutions all can endorse, putting users in control of their identity interactions on the Internet. The design decisions presented in this paper are intended to result in a widely accepted, broadly applicable, inclusive, comprehensible, privacy-enhancing, security-enhancing identity solution for the Internet. We present them and the rationale behind them to facilitate review of these design decisions by the security, privacy, and policy communities, so that people will better understand Microsoft’s implementations, and to help guide others when building interoperating implementations.
Kim Cameron and Michael B. Jones. Design Rationale behind the Identity Metasystem Architecture, January 2006.
- Identity Metasystem Whitepaper Published: Kim Cameron and I authored the Microsoft whitepaper Microsoft’s Vision for an Identity Metasystem published on May 12, 2005. It describes our initiative with the rest of the industry to interconnect today’s diverse collection of identity systems into an interoperable Identity Metasystem, analogous to how the Internet Protocol tied together individual network technologies such as Ethernet, Token Ring, and X.25 (and enabled new technologies, such as 802.11 wireless to be easily incorporated as they were invented). The Identity Metasystem and Microsoft’s “InfoCard” identity selector client will help prevent phishing by ensuring that sites strongly authenticate themselves to users in a non-spoofable manner.
- From Research to Products: After 12+ years as a member of the Systems and Networking Research Group at Microsoft Research, in early 2005 I decided that it was time to find a position that would use the full range of both my technical and inter-personal, coalition-building skills. And I found a great one! At the beginning of March 2005 I started a new position at Microsoft as Director of Distributed Systems Customer Strategy and Evangelism. This position is a great fit for me because it’s very much a collaborative cross-group and multi-company, multi-platform effort. I’m working with people all over Microsoft and with numerous customers and partners across a tremendous range of industries worldwide.