Synthesis of Efficient Drinking Philosophers Algorithms
Jennifer A. Welch, Nancy Ann Lynch · 1989
A variant of the drinking l>hilos(,t>hers algorithm of Chandy and Misra is described and proved correct in a, modula.r way, using the I/0 automaton model of Lynch and Tuttle. The a.lgorithm of Cl'mn(ly and Misra is based on a particular dining philosophers algorithm, and relics on certain properties of its implementation. The drinking philosophers algorit,hm presented in this paper is able to use an arbitrary dining philosophers algorithm as a true subroutine; nothing about the implementation needs to be known, only that, it solves the dining philosophers problem. An important advantage of this modularity is that by substituting a more time-efficient dining philosophers algorithm tha.n the one used by Chandy and Misra, a drinking philosophers algorithn with 0(1) worst-case waiting time is obtained, whereas the drinking 1)hilosophcrs a.lgorit,hm of Chandy and Misra has O(n) worst-case waiting time (for ,. philosot)lints ). Formal definitions are given to distinguish the drinking and dining phil(sol)hcrs problems and to specify precisely varying degrees of concurrency.