Date: December 7, 3pm, GSSI Room B
Speaker: Dr. Andre B. Bondi
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.
Bio: Dr. Bondi is spending the fall 2016 semester as a Visiting Professor in DSIM at the University of L’Aquila. He has considerable industrial experience in R&D and consulting environments. He spent many years at AT&T (Bell) Labs and Siemens Corporate Technology. In between, he held senior performance positions at two startups. After receiving his PhD in computer science at Purdue University, he was an Assistant Professor at the University of California, Santa Barbara. Dr. Bondi also holds an M.Sc. in statistics from University College London and a B.Sc. in mathematics from the University of Exeter. His recent book, Foundations of Software and System Performance Engineering, was published by Addison Wesley in 2014. Dr. Bondi holds nine US patents. He received the Computer Measurement Group’s A. A. Michelson Award in November 2016.