In computer systems, recording instructions and playing them back in exactly the same order as when the instructions were originally executed is sometimes referred to as deterministic record/replay. Deterministic record/replay has many useful applications. For example, a deterministic record/replay mechanism can allow the programmer to debug and diagnose undesirable behaviors, such as system crashes, and can also allow the system administrator to track security breaches and analyze intrusion behavior.
Implementing deterministic replay is a challenging task, particularly in multi-processor environments where concurrency and race conditions are frequently encountered. The most straightforward way to implement record/replay is to record every single instruction. A great amount of information would have to be recorded, making the technique highly inefficient and impractical. Some existing implementations of record/replay use a global lock to limit the execution of each thread to a predetermined number of instructions, such that a small amount of information is sufficient for replaying the processor's executions (for example, 50 instructions by thread A, 50 instructions by thread B, etc.). These limitations can change the concurrency behavior of the program. Therefore, the recordings from such a record/replay mechanism do not accurately reflect what actually happens in a real run-time environment where the program runs without any execution recording. For example, a hash table or some other shared memory structure may be accessed by multiple threads/processors concurrently, and the accessing threads and their operations may involve varying time lengths and/or number of instructions. Some existing recorders may only allow one processor to access the hash table for 50 instructions and keep the other processors waiting, then allow the next processor to access the hash table for 50 instructions exclusively. Thus, the access to the hash table is effectively serialized by the recorder.