Victim selection for deadlock detection
A mechanism and system are described for either releasing held resources in the case of a deadlock or to postpone requests for resources when a potential deadlock is detected. One technique involves a three pass algorithm for selecting a candidate, where the candidate is either a possessory entity or resource is used. The three passes are as follows: (1) determining the subset of candidates, which have the CAN-BE-VICTIM flag set on; (2) If pass one results in a subset with more than one candidates in it, process that subset to determine a second subset of candidates based on resource priority associated with a resource type; (3) If the second pass results in a subset with more than one candidate in it, process that subset to select the candidate that has been running or held the shortest length of time.
1. A method for selecting a victim to be used during resolution of a deadlock, the method comprising the steps of:
initially establishing a plurality of resources involved in said deadlock as a set of candidates to be said victim;
performing a first filtering pass that removes candidates from said set based on CAN-BE-VICTIM flags associated with said candidates;
if more than a single candidate remains in said set after said first filtering pass, then performing a second filtering pass that removes candidates from said set based on priorities associated with said candidates; and
if more than a single candidate remains in said set after said second filtering pass, then performing a third filtering pass that removes candidates from said set based on runtimes associated with possessory entities associated with said candidates; and
when said set has been filtered to include a single candidate, selecting said candidate as said victim.
2. The method of claim 1 wherein at least a portion of the priority of a given resource is established dynamically.
3. The method of claim 2 wherein said portion is established based on which other resources are held by a possessory entity associated with the given resource.
4. The method of claim 1 wherein at least a portion of the priority of a given resource is established statically.
5. The method of claim 4 wherein said portion is established based on the type of the given resource.
6. A method for selecting a victim to be used during resolution of a deadlock, the method comprising the steps of:
initially establishing a plurality of candidates involved in said deadlock as candidates to be said victim;
filtering said plurality of candidates based on one or more factors until a single candidate remains as a candidate to be said victim, wherein the step of filtering comprises filtering each candidate of the plurality of candidates by taking into account, for each candidate, at least one factor of the one or more factors;
selecting said single candidate as the victim to be used during resolution of said deadlock; and
wherein the step of filtering further includes removing from said plurality of candidates any candidates that have a CAN-BE-VICTIM flag that indicates the candidate cannot be a victim.
7. The method of claim 6 wherein the step of filtering further includes removing from said plurality of candidates all the candidates that are associated with possessory entities have been running for a duration of time that is relatively longer than the duration of time that possessory entities associated with the other candidates have been running.
8. The method of claim 6 wherein the step for filtering further comprises the computer-implemented steps of:
performing a first pass to filter out any candidates that have a CAN-BE-VICTIM flag indicating that one is not candidate for termination;
if more than one candidate is left after performing the first pass, then performing a second pass to filter out any candidates whose resource priority is higher than the resource priority of at least one of the other candidates;
if more than one candidate is left after performing the second pass, then performing a third pass to filter out all the candidates except the candidate that has been running for the shortest duration of time.
9. The method of claim 6 wherein the step of filtering includes filtering based on priorities established for said candidates.
10. The method of claim 9 wherein at least a portion of the priority of a given candidate is established dynamically.
11. The method of claim 10 wherein said portion is established based on which resources other than said candidate are held by a possessory entity associated with the given candidate.
12. The method of claim 9 wherein at least a portion of the priority of a given candidate is established statically.
13. The method of claim 12 wherein said portion is established based on the type of the given candidate.
14. A method for selecting a victim to be used during resolution of a deadlock, the method comprising the steps of:
initially establishing a plurality of candidates involved in said deadlock as candidates to be said victim, wherein the plurality of candidates are a plurality of possessory entities involved in said deadlock;
filtering said plurality of candidates based on one or more factors until a single candidate remains as a candidate to be said victim, wherein the step of filtering comprises filtering each candidate of the plurality of candidates by taking into account, for each candidate, at least one factor of the one or more factors;
selecting said single candidate as the victim to be used during resolution of said deadlock; and
wherein the step of filtering further includes removing from said plurality of candidates the candidates ho 1 ding at least one resource whose resource priority is higher than the resource priority of at least one resource held by at least one of the other candidates.
15. The method of claim 14 wherein the step of filtering further includes removing from said plurality of candidates all the candidates that are associated with possessory entities have been running for a duration of time that is relatively longer than the duration of time that possessory entities associated with the other candidates have been running.
16. The method of claim 14 wherein the step for filtering further comprises the computer-implemented steps of:
performing a first pass to filter out any candidates that have a CAN-BE-VICTIM flag indicating that one is not candidate for termination;
if more than one candidate is left after performing the first pass, then performing a second pass to filter out any candidates whose resource priority is higher than the resource priority of at least one of the other candidates;
if more than one candidate is left after performing the second pass, then performing a third pass to filter out all the candidates except the candidate that has been running for the shortest duration of time.
17. A computer-readable storage medium carrying instructions for selecting a victim to be used during resolution of a deadlock, the computer-readable medium comprising instructions for performing the steps of:
initially establishing a plurality of resources involved in said deadlock as a set of candidates to be said victim;
performing a first filtering pass that removes candidates from said set based on CAN-BE-VICTIM flags associated with said candidates;
if more than a single candidate remains in said set after said first filtering pass, then performing a second filtering pass that removes candidates from said set based on priorities associated with said candidates; and
if more than a single candidate remains in said set after said second filtering pass, then performing a third filtering pass that removes candidates from said set based on runtimes associated with possessory entities associated with said candidates; and
when said set has been filtered to include a single candidate, selecting said candidate as said victim.
18. The computer-readable storage medium of claim 17 wherein at least a portion of the priority of a given resource is established dynamically.
19. The computer-readable storage medium of claim 18 wherein said portion is established based on which other resources are held by a possessory entity associated with the given resource.
20. The computer-readable storage medium of claim 17 wherein at least a portion of the priority of a given resource is established statically.
21. The computer-readable storage medium of claim 20 wherein said portion is established based on the type of the given resource.
22. A computer-readable storage medium carrying instructions for selecting a victim to be used during resolution of a deadlock, the computer-readable medium carrying instructions for performing the steps of:
initially establishing a plurality of candidates involved in said deadlock as candidates to be said victim;
filtering said plurality of candidates based on one or more factors until a single candidate remains as a candidate to be said victim, wherein the step of filtering comprises filtering each candidate of the plurality of candidates by taking into account, for each candidate, at least one factor of the one or more factors;
selecting said single candidate as the victim to be used during resolution of said deadlock; and
wherein the step of filtering further includes removing from said plurality of candidates any candidates that have a CAN-BE-VICTIM flag that indicates the candidate cannot be a victim.
23. The computer-readable storage medium of claim 22 wherein the step of filtering further includes removing from said plurality of candidates all the candidates that are associated with possessory entities have been running for a duration of time that is relatively longer than the duration of time that possessory entities associated with the other candidates have been running.
24. The computer-readable storage medium of claim 22 wherein the step for filtering further comprises the computer-implemented steps of:
performing a first pass to filter out any candidates that have a CAN-BE-VICTIM flag indicating that one is not candidate for termination;
if more than one candidate is left after performing the first pass, then performing a second pass to filter out any candidates whose resource priority is higher than the resource priority of at least one of the other candidates;
if more than one candidate is left after performing the second pass, then performing a third pass to filter out all the candidates except the candidate that has been running for the shortest duration of time.
25. The computer-readable storage medium of claim 22 wherein the step of filtering includes filtering based on priorities established for said candidates.
26. The computer-readable storage medium of claim 25 wherein at least a portion of the priority of a given candidate is established dynamically.
27. The computer-readable storage medium of claim 26 wherein said portion is established based on which resources other than said candidate are held by a possessory entity associated with the given candidate.
28. The computer-readable storage medium of claim 25 wherein at least a portion of the priority of a given candidate is established statically.
29. The computer-readable storage medium of claim 28 wherein said portion is established based on the type of the given candidate.
30. A computer-readable storage medium carrying instructions for selecting a victim to be used during resolution of a deadlock, the computer-readable medium carrying instructions for performing the steps of:
initially establishing a plurality of candidates involved in said deadlock as candidates to be said victim, wherein the plurality of candidates are a plurality of possessory entities involved in said deadlock;
filtering said plurality of candidates based on one or more factors until a single candidate remains as a candidate to be said victim, wherein the step of filtering comprises filtering each candidate of the plurality of candidates by taking into account, for each candidate, at least one factor of the one or more factors;
selecting said single candidate as the victim to be used during resolution of said deadlock; and
wherein the step of filtering further includes removing from said plurality of candidates the candidates holding at least one resource whose resource priority is higher than the resource priority of at least one resource held by at least one of the other candidates.
31. The computer-readable storage medium of claim 30 wherein the step of filtering further includes removing from said plurality of candidates all the candidates that are associated with possessory entities have been running for a duration of time that is relatively longer than the duration of time that possessory entities associated with the other candidates have been running.
32. The computer-readable storage medium of claim 30 wherein the step for filtering further comprises the computer-implemented steps of:
performing a first pass to filter out any candidates that have a CAN-BE-VICTIM flag indicating that one is not candidate for termination;
if more than one candidate is left after performing the first pass, then performing a second pass to filter out any candidates whose resource priority is higher than the resource priority of at least one of the other candidates;
if more than one candidate is left after performing the second pass, then performing a third pass to filter out all the candidates except the candidate that has been running for the shortest duration of time.