Efficiently scheduling X clients

The X server is charged with providing window system services to many applications simultaneously, and needs a scheduling mechanism to distribute it's limited resources among these applications. The original scheduling mechanism was simplistic and caused graphics-intensive applications to starve interactive applications. A new scheduling mechanism has been designed which fairly distributes time among the requesting applications while at the same time increasing performance by a small amount. Descriptions of the original and new scheduling mechanism and empirical measurements demonstrating the effects of scheduling within the X server are included along with a discussion on how the design was arrived at.