Pagerank algorithm lock analysis
AssigneeVMware, Inc.
InventorsJiaojiao Song, Zhelong Pan, Inna Rytsareva
Life of this patent
Estimating the term…
Abstract
A system is described for identifying key lock contention issues in computing devices. A computing device is executed and lock contention information relating to operations during execution of the computing device is recorded. The data is parsed and analyzed to determine blocking relationships between operations due to lock contention. Algorithms are implemented to analyze dependencies between operations based on the data and to identify key areas of optimization for performance improvement. Algorithms can be based on the Hyperlink-Induced Topic Search algorithm or the PageRank algorithm.
Claims20
A method comprising:
- executing a computing device for a predetermined time interval and recording data related to the execution of the computing device into a log;
- analyzing the data recorded into the log to identify blocking relationships between processes executing on the computing device, wherein blocking relationships comprise lock contention information related to a first process being blocked by a second process due to the first process being unable to acquire a lock on an object because the second process is holding the lock on the object;
- and
- plotting the data into a graph data structure comprising:
- a plurality of nodes, each node representing one of the processes executing on the computing device;
- and
- links between the nodes that indicate the blocking relationships between the processes;
- setting a predetermined initial optimization priority score for each node;
- iteratively updating the optimization priority score of each node based on the optimization priority scores of the nodes that the node blocks;
- and
- identifying a process to be optimized based on the optimization priority score of the node associated with the process.
A computing device, comprising:
- at least one processor;
- and
- memory including instructions that, when executed by the at least one processor, cause the computing device to:
- execute a computing device for a predetermined time interval and record data related to the execution of the computing device into a log;
- analyze the data recorded into the log to identify blocking relationships between processes executing on the computing device, wherein blocking relationships comprise lock contention information related to a first process being blocked by a second process due to the first process being unable to acquire a lock on an object because the second process is holding the lock on the object;
- and
- plot the data into a graph data structure comprising:
- a plurality of nodes, each node representing one of the processes executing on the computing device;
- and
- links between the nodes that indicate the blocking relationships between the processes;
- set a predetermined initial optimization priority score for each node;
- iteratively update the optimization priority score of each node based on the optimization priority scores of the nodes that the node blocks;
- and
- identify a process to be optimized based on the optimization priority score of the node associated with the process.
A non-transitory computer readable storage medium comprising one or more sequences of instructions, the instructions when executed by one or more processors causing the one or more processors to execute the operations of:
- executing a computing device for a predetermined time interval and recording data related to the execution of the computing device into a log;
- analyzing the data recorded into the log to identify blocking relationships between processes executing on the computing device, wherein blocking relationships comprise lock contention information related to a first process being blocked by a second process due to the first process being unable to acquire a lock on an object because the second process is holding the lock on the object;
- and
- plotting the data into a graph data structure comprising:
- a plurality of nodes, each node representing one of the processes executing on the computing device;
- and
- links between the nodes that indicate the blocking relationships between the processes;
- setting a predetermined initial optimization priority score for each node;
- iteratively updating the optimization priority score of each node based on the optimization priority scores of the nodes that the node blocks;
- and
- identifying a process to be optimized based on the optimization priority score of the node associated with the process.
Dependencies are inferred from the claim text.