# US 2016/0253221 A1 · Pagerank 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/0253221 A1 - Document ID: US20160253221A1 - Status: Published application - Kind: A1 - Application number: 14/634,502 - 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/US20160253221A1 ## CPC - G06F 9/524: {Deadlock detection or avoidance} - G06F 11/3476: {Data logging (G06F11/14, G06F11/2205 take precedence)} - G06F 9/468: {Specific access rights for resources, e.g. using capability register} - G06F 9/5022: {Mechanisms to release resources} - G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores - 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; 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the iteratively updating the optimization priority score stops when predetermined criteria are met, wherein the predetermined the criteria comprises at least one of: a predetermined number of iterations; a predetermined period of time; or convergence. ### Claim 3 (depends on 2) The method of claim 2, wherein convergence occurs when the change in the optimization priority score of each node between iterations is less than a predetermined threshold. ### Claim 4 (depends on 1) The method of claim 1, wherein: the updating the optimization priority score further comprises summing the optimization priority scores of the nodes that the node blocks. ### Claim 5 (depends on 1) The method of claim 1, wherein: the updating the optimization priority score further comprises summing the products of the optimization priority score of each node blocked by the node and the normalized 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 normalized weight of the blocking relationship between a first node that blocks a second node is calculated by dividing the weight of the blocking relationship between the first node and the second node by the sum of the weights of all blocking relationships between the second node and nodes blocking the second node. ### Claim 7 (depends on 1) The method of claim 1, further comprising: producing a graph comprising an illustration representing each node, the optimization priority 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 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. ### Claim 9 (depends on 8) The computing device of claim 8, wherein the iteratively updating the optimization priority score stops when predetermined criteria are met, wherein the predetermined the criteria comprises at least one of: a predetermined number of iterations; a predetermined period of time; or convergence. ### Claim 10 (depends on 9) The computing device of claim 9, wherein convergence occurs when the change in the optimization priority score of each node between iterations is less than a predetermined threshold. ### Claim 11 (depends on 8) The computing device of claim 8, wherein: the updating the optimization priority score further comprises summing the optimization priority scores of the nodes that the node blocks. ### Claim 12 (depends on 8) The computing device of claim 8, wherein: the updating the optimization priority score further comprises summing the products of the optimization priority score of each node blocked by the node and the normalized 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 normalized weight of the blocking relationship between a first node that blocks a second node is calculated by dividing the weight of the blocking relationship between the first node and the second node by the sum of the weights of all blocking relationships between the second node and nodes blocking the second node. ### 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 optimization priority 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; 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. ### Claim 16 (depends on 15) The non-transitory computer readable storage medium of claim 15, wherein the iteratively updating the optimization priority score stops when predetermined criteria are met, wherein the predetermined the criteria comprises at least one of: a predetermined number of iterations; a predetermined period of time; or convergence. ### Claim 17 (depends on 16) The non-transitory computer readable storage medium of claim 16, wherein convergence occurs when the change in the optimization priority score of each node between iterations is less than a predetermined threshold. ### Claim 18 (depends on 15) The non-transitory computer readable storage medium of claim 15, wherein: the updating the optimization priority score further comprises summing the products of the optimization priority score of each node blocked by the node and the normalized 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 normalized weight of the blocking relationship between a first node that blocks a second node is calculated by dividing the weight of the blocking relationship between the first node and the second node by the sum of the weights of all blocking relationships between the second node and nodes blocking the second node. ### 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 optimization priority score of each node, and blocking relationships between the nodes.