Performance of Concurrent Servers Generated Automatically from Sequential Servers

Concurrent servers in a multiprocessor system, concurrent graphical user interfaces, and operating systems containing concurrent objects are fairer on a uniprocessor and can yield better performance on a multiprocessor than their sequential counterparts. However, concurrent servers are more difficult to implement correctly. Our contribution is a tool that generates correct concurrent servers from correct sequential ones. The only restriction on the sequential servers is that they must be programmed in a slightly restricted subset of Modula-3 in the Generic Server Format using the Defensive Object Model. Our tool uses well known static analysis techniques from compiler theory to insert locks that are guaranteed to be free from deadlock. It uses information obtained from exception handling statements to insert synchronization primitives. The tool produces very readable Modula-3 programs that are subsequently compiled using standard Modula-3 compilers. In addition to describing the rationale, design, and implementation of our tool, this paper presents performance comparisons between hand-tuned and automatically generated queues and search structures. Moreover, we report on the lessons that were learned from automatically generating various concurrent servers.