About Matching Signature

[Chengnian Sun]

Hi,

I found the criteria for matching a signature is based on "this consists of finding a set of (thread, lock, stack) tuples in the RAG cache that provide an exact cover of the signature. All thread-lock-stack tuples in the instance must correspond to distinct threads and locks."

My question is why to perform a cycle detection to check whether a signature is matched. Is it because the cost is high?

Thanks.

--
Best Regards.

Chengnian SUN.

[Horatiu Jula]

Hi,

Signature matching does not have anything to do with cycle detection.

Signature matching goes as follows. Say there is a signature
{cs1,cs2}. In lockGrantees[cs] we keep the set of (thread,lock) tuples
representing the locks that were granted with call stack cs and the
threads to which they were granted. The signature is instantiated if
and only if there is a tuple (t1,l1) in lockGrantees[cs1] and a tuple
(t2,l2) in lockGrantees[cs2], where t1 != t2 and l1 != l2.

Maybe the name "RAG cache" was confusing. What we call "RAG cache" is
basically the lockGrantees data structure , which is updated
synchronously , while the RAG is updated asynchronously. The RAG is
used only for deadlock detection, while the RAG cache (lockGrantees)
is used only for deadlock avoidance.

Horatiu

> Hi,
>
> I found the criteria for matching a signature is based on "this consists of
> finding a set of (thread, lock, stack) tuples in the RAG cache that provide
> an exact cover of the signature. All thread-lock-stack tuples in the

> instance must correspond to *distinct *threads and locks."

[Chengnian Sun]

Hi Horatiu,

Thanks for your timely reply.

Chengnian.