Browse Prior Art Database

Replay of interleavings that didn't happen Disclosure Number: IPCOM000029263D
Original Publication Date: 2004-Jun-21
Included in the Prior Art Database: 2004-Jun-21
Document File: 1 page(s) / 36K

Publishing Venue



Forcing replay of a given execution of a multithreaded program is a valuable tool for debugging. Currently there are algorithms to force replay of an actual past execution. Forcing replay of a possible execution, an outcome or result that did not spontaneously occur, is of additional value for debugging.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 70% of the total text.

Page 1 of 1

Replay of interleavings that didn't happen

A multithreaded program can have different outcomes depending on the thread interleaving. Currently there are algorithms to force replay of an actual past execution, according to information recorded in that execution. In certain circumstances, however, one can know of a possible alternative execution or result, one that is possibly incorrect. Forcing replay of that execution, or of an execution that ended with this result, is of additional value for debugging.

    At various critical points in the program, a variable can have several values, each resulting from different interleaving(s) up to that point. From previous work (cite - alternative replay) it is possible to know what these values are and to force one of them. The algorithm keeps enough information to know what interleaving results in any of the values. Thus it is possible to "replay" that interleaving and show it to the developer, although it never actually happened in any "spontaneous" run.

    The algorithm from "alternative histories" can show the possible values that a 'read' operation can read, the possible values of the variable. This set of values may be presented to the developer, either as the final result of a given piece of the program (e.g. if this value is printed as output) or in any intermediary read operation, by a debugger program. Suppose the developer thinks that a given value should not be possible and suspects a bug. The developer can then ask to...