Efficient timestamp solution for analyzing concurrent software systems

Patent metadata

Field	Value
Publication number	US-10620660-B2
Application number	US-201815935190-A
Country	US
Kind code	B2
Filing date	Mar 26, 2018
Priority date	Mar 26, 2018
Publication date	Apr 14, 2020
Grant date	Apr 14, 2020

Abstract

A method may include obtaining a concurrent application including processes, each including operations, and obtaining an initial hybrid timestamp for an initial operation of a process. The initial hybrid timestamp may include a vector list timestamp including vector clocks, each including a clock value for each of the processes. The method may further include determining a synchronization category for a next operation of the process, and in response to the synchronization category indicating that the next operation does not require inter-process synchronization, generating a next hybrid timestamp for the next operation. The next hybrid timestamp may include a differential timestamp relative to the initial hybrid timestamp.

First claim

What is claimed is:

1. A method, comprising:
obtaining a concurrent application comprising a plurality of processes, each comprising a plurality of operations;
obtaining an initial hybrid timestamp for an initial operation of a first process of the plurality of processes, wherein the initial hybrid timestamp comprises an initial vector list timestamp comprising an initial plurality of vector clocks each comprising a clock value for each of the plurality of processes;
determining, by a processor, a first synchronization category for a next operation of the first process; and
in response to the first synchronization category indicating that the next operation does not require inter-process synchronization, generating a next hybrid timestamp for the next operation, wherein the next hybrid timestamp comprises a differential timestamp relative to the initial hybrid timestamp.

2. The method of claim 1 , further comprising:
decompressing the next hybrid timestamp by generating a next vector list timestamp obtained by merging the differential timestamp into to the initial hybrid timestamp.

3. The method of claim 2 ,
wherein the next vector list timestamp comprises a next plurality of vector clocks each comprising a clock value for each of the plurality of processes, the next plurality of vector clocks comprising a first vector clock comprising a first clock value for the first process,
wherein the differential timestamp comprises a differential clock value for the first process, and
wherein merging the differential timestamp into to the initial hybrid timestamp comprises obtaining an updated clock value using the differential clock value and the first clock value.

4. The method of claim 3 , further comprising:
obtaining another hybrid timestamp for a potentially conflicting operation of a second process of the plurality of processes; and
determining a happens-before relation between the next operation and the potentially conflicting operation by comparing the next vector list timestamp and the another hybrid timestamp.

5. The method of claim 4 ,
wherein the another hybrid timestamp comprises another vector list timestamp comprising another plurality of vector clocks each comprising a clock value for each of the plurality of processes, the another plurality of vector clocks comprising a second vector clock comprising a second clock value for the second process, and
wherein comparing the next hybrid timestamp and the another hybrid timestamp comprises comparing the updated clock value and the second clock value.

6. The method of claim 4 , further comprising:
applying a dynamic partial order reduction analysis to the concurrent application using the happens-before relation.

7. The method of claim 1 , further comprising:
determining a second synchronization category for another operation of the first process; and
in response to the second synchronization category indicating that the another operation is synchronized with a second process of the plurality of processes, generating another hybrid timestamp for the another operation comprising another vector list timestamp.

8. The method of claim 7 ,
wherein the another vector list timestamp comprises another plurality of vector clocks each comprising a clock value for each of the plurality of processes, the another plurality of vector clocks comprising a second vector clock comprising a second clock value for the second process,
wherein the method further comprises:
in response to the second synchronization category indicating that the another operation is synchronized with the second process, updating the second clock value for the second process.

9. A system, comprising:
a memory, coupled to a processor, comprising a repository comprising:
a concurrent application comprising a plurality of processes, each comprising a plurality of operations,
an initial hybrid timestamp for an initial operation of a first process of the plurality of processes, wherein the initial hybrid timestamp comprises an initial vector list timestamp comprising an initial plurality of vector clocks each comprising a clock value for each of the plurality of processes, and
a next hybrid timestamp for a next operation of the first process, wherein the next hybrid timestamp comprises a differential timestamp relative to the initial hybrid timestamp; and

a timestamp generator executing on the processor configured to:
determine a first synchronization category for the next operation; and
in response to the first synchronization category indicating that the next operation does not require inter-process synchronization, generate the next hybrid timestamp.

10. The system of claim 9 , wherein the timestamp generator is further configured to:
decompress the next hybrid timestamp by generating a next vector list timestamp obtained by merging the differential timestamp into to the initial hybrid timestamp.

11. The system of claim 10 ,
wherein the next vector list timestamp comprises a next plurality of vector clocks each comprising a clock value for each of the plurality of processes, the next plurality of vector clocks comprising a first vector clock comprising a first clock value for the first process,
wherein the differential timestamp comprises a differential clock value for the first process, and
wherein merging the differential timestamp into to the initial hybrid timestamp comprises obtaining an updated clock value using the differential clock value and the first clock value.

12. The system of claim 11 , wherein the timestamp generator is further configured to:
obtain another hybrid timestamp for a potentially conflicting operation of a second process of the plurality of processes; and
determine a happens-before relation between the next operation and the potentially conflicting operation by comparing the next vector list timestamp and the another hybrid timestamp.

13. The system of claim 12 ,
wherein the another hybrid timestamp comprises another vector list timestamp comprising another plurality of vector clocks each comprising a clock value for each of the plurality of processes, the another plurality of vector clocks comprising a second vector clock comprising a second clock value for the second process, and
wherein comparing the next hybrid timestamp and the another hybrid timestamp comprises comparing the updated clock value and the second clock value.

14. The system of claim 12 , further comprising a model checker configured to:
apply a dynamic partial order reduction analysis to the concurrent application using the happens-before relation.

15. The system of claim 9 , wherein the timestamp generator is further configured to:
determine a second synchronization category for another operation of the first process; and
in response to the second synchronization category indicating that the another operation is synchronized with a second process of the plurality of processes:
generate another hybrid timestamp for the another operation comprising another vector list timestamp comprising another plurality of vector clocks each comprising a clock value for each of the plurality of processes, the another plurality of vector clocks comprising a second vector clock comprising a second clock value for the second process; and
update the second clock value for the second process.

16. A non-transitory computer readable medium comprising instructions that, when executed by a processor, perform:
obtaining a concurrent application comprising a plurality of processes, each comprising a plurality of operations;
obtaining an initial hybrid tim

Assignees

• Oracle Int Corp

Inventors

• Zhao Yang
• Allen Nicholas John
• Cifuentes Cristina Nicole
• Keynes Nathan Robert Albert

Classifications

• G06F1/12 Primary

  Synchronisation of different clock signals {provided by a plurality of clock generators} · CPC title

• G06F2209/484

  Precedence · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title