# US 2016/0253370 A1 · Hyperlink-induced topic search algorithm lock analysis > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2016/0253370 A1 - Document ID: US20160253370A1 - Status: Published application - Kind: A1 - Application number: 14/634,473 - Filed: 2015-02-27 - Published: 2016-09-01 - Earliest claimed: 2015-02-27 - Assignees: VMware, Inc. - Applicants: VMware, Inc. - Inventors: Jiaojiao Song; Zhelong Pan; Inna Rytsareva - Web page: https://patentgrep.com/patent/US20160253370A1 ## CPC - G06F 11/34: Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation {; Recording or statistical evaluation of user activity, e.g. usability assessment} - G06F 9/524: {Deadlock detection or avoidance} - G06F 11/323: {Visualisation of programs or trace data} - G06F 11/3409: {for performance assessment} - G06F 11/3476: {Data logging (G06F11/14, G06F11/2205 take precedence)} - G06F 16/1774: {Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files} - G06F 16/2336: {Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps} - G06F 17/40: Data acquisition and logging (for input to computer G06F3/00) - G06F 2201/825: the problem or solution involving locking - G06F 2201/865: Monitoring of software - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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; 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 criminal score for each node; setting a predetermined initial victim score for each node; and iteratively updating the criminal score and the victim score of each node, wherein the criminal score is updated based on the victim scores of the nodes that the node blocks and the victim score is updated based on the criminal scores of the nodes that block the node. ### Claim 2 (depends on 1) The method of claim 1, further comprising: identifying a process to be optimized based on the updated criminal score and the updated victim score of the node associated with the process. ### Claim 3 (depends on 1) The method of claim 1, wherein the iteratively updating the criminal score and the victim score stops when predetermined criteria are met, wherein the predetermined criteria comprises at least one of: a predetermined number of iterations; a predetermined period of time; or convergence. ### Claim 4 (depends on 1) The method of claim 1, wherein: the updating the criminal score further comprises summing the victim scores of the nodes that the node blocks; and the updating the victim score further comprises summing the criminal scores of the nodes that block the node. ### Claim 5 (depends on 1) The method of claim 1, wherein: the updating the criminal score further comprises summing the products of the victim score of each node blocked by the node and the weight of the blocking relationship; and the updating the victim score further comprises summing the products of the criminal score of each node blocking the node and the weight of the blocking relationship; wherein the weight of the blocking relationship between two nodes is based on at least one of the frequency of blocking between the two nodes or the blocking time between the two nodes. ### Claim 6 (depends on 5) The method of claim 5, wherein: the updating the criminal score further comprises normalizing the sum of the products of the victim score of each node blocked by the node and the weight of the blocking relationship; and the updating the victim score further comprises normalizing the sum of the products of the criminal score of each node blocking the node and the weight of the blocking relationship. ### Claim 7 (depends on 1) The method of claim 1, further comprising: producing a graph comprising an illustration representing each node, the criminal score of each node, the victim score of each node, and blocking relationships between the nodes. ### Claim 8 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 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; 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 criminal score for each node; set a predetermined initial victim score for each node; and iteratively update the criminal score and the victim score of each node, wherein the criminal score is updated based on the victim scores of the nodes that the node blocks and the victim score is updated based on the criminal scores of the nodes that block the node. ### Claim 9 (depends on 8) The computing device of claim 8, wherein the memory further includes instructions that when executed by the at least one processor, cause the computing device to: identify a process to be optimized based on the updated criminal score and the updated victim score of the node associated with the process. ### Claim 10 (depends on 8) The computing device of claim 8, wherein the iteratively updating the criminal score and the victim score stops when predetermined criteria are met, wherein the predetermined criteria comprises at least one of: a predetermined number of iterations; a predetermined period of time; or convergence. ### Claim 11 (depends on 8) The computing device of claim 8, wherein: the updating the criminal score further comprises summing the victim scores of the nodes that the node blocks; and the updating the victim score further comprises summing the criminal scores of the nodes that block the node. ### Claim 12 (depends on 8) The computing device of claim 8, wherein: the updating the criminal score further comprises summing the products of the victim score of each node blocked by the node and the weight of the blocking relationship; and the updating the victim score further comprises summing the products of the criminal score of each node blocking the node and the weight of the blocking relationship; wherein the weight of the blocking relationship between two nodes is based on at least one of the frequency of blocking between the two nodes or the blocking time between the two nodes. ### Claim 13 (depends on 12) The computing device of claim 12, wherein: the updating the criminal score further comprises normalizing the sum of the products of the victim score of each node blocked by the node and the weight of the blocking relationship; and the updating the victim score further comprises normalizing the sum of the products of the criminal score of each node blocking the node and the weight of the blocking relationship. ### Claim 14 (depends on 8) The computing device of claim 8, wherein the memory further includes instructions that when executed by the at least one processor, cause the computing device to: produce a graph comprising an illustration representing each node, the criminal score of each node, the victim score of each node, and blocking relationships between the nodes. ### Claim 15 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; 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 criminal score for each node; setting a predetermined initial victim score for each node; and iteratively updating the criminal score and the victim score of each node, wherein the criminal score is updated based on the victim scores of the nodes that the node blocks and the victim score is updated based on the criminal scores of the nodes that block the node. ### Claim 16 (depends on 15) The non-transitory computer readable storage medium of claim 15, further comprising instructions that when executed by the one or more processors, cause the one or more processors to execute the operations of: identifying a process to be optimized based on the updated criminal score and the updated victim score of the node associated with the process. ### Claim 17 (depends on 15) The non-transitory computer readable storage medium of claim 15, wherein the iteratively updating the criminal score and the victim score stops when predetermined criteria are met, wherein the predetermined criteria comprises at least one of: a predetermined number of iterations; a predetermined period of time; or convergence. ### Claim 18 (depends on 15) The non-transitory computer readable storage medium of claim 15, wherein: the updating the criminal score further comprises summing the products of the victim score of each node blocked by the node and the weight of the blocking relationship; and the updating the victim score further comprises summing the products of the criminal score of each node blocking the node and the weight of the blocking relationship; wherein the weight of the blocking relationship between two nodes is based on at least one of the frequency of blocking between the two nodes or the blocking time between the two nodes. ### Claim 19 (depends on 18) The non-transitory computer readable storage medium of claim 18, wherein: the updating the criminal score further comprises normalizing the sum of the products of the victim score of each node blocked by the node and the weight of the blocking relationship; and the updating the victim score further comprises normalizing the sum of the products of the criminal score of each node blocking the node and the weight of the blocking relationship. ### Claim 20 (depends on 15) The non-transitory computer readable storage medium of claim 15, further comprising instructions that when executed by the one or more processors, cause the one or more processors to execute the operations of: producing a graph comprising an illustration representing each node, the criminal score of each node, the victim score of each node, and blocking relationships between the nodes.