Speaker: Dr. Andre Bondi (Visiting Professor at DISIM)
When: Tuesday, December 6, 2016 — 2:30pm
Where: Alan Turing building, Seminar Room.
Title: Predicting the Time to Migration into Deadlock for a Performance Antipattern Using a Discrete Time Markov Chain
Abstract: When processes join a common FCFS queue to acquire or release resources in an object pool of fixed size, deadlock occurs if the process at the head of the queue wishes to acquire a resource when the pool is empty, even if a process wishing to relinquish a resource is queued behind. This scenario has been called the Museum Checkroom antipattern. We describe a state machine representation of this problem. We use the representation to develop a discrete time Markov chain analysis to identify the load conditions under which deadlock is most likely to occur and how soon it is likely to occur. The analysis shows that deadlock is inevitable regardless of the load, and that the time to the onset of deadlock depends on combinations of the request rate for resources in pool, the average holding time of the resources, and the number of resources in the pool. We verify the intuition that deadlock will occur sooner at heavy loads or when the resource pool is small. A connection will be made between this problem and random walks with a single absorbing and a single reflecting barrier. Interesting numerical properties of the analysis will be illustrated. It will be shown that these can be anticipated from the structure of the problem.