SAP: An Efficient Scheduling Protocol for Web Servers

We present a new scheduling protocol that we call the “starvation avoidance protocol ” (SAP). SAP is designed for situations in which users primarily care about the completion time of a job, such as web serving. SAP is similar to the shortest remaining processing time (SRPT) protocol in that small jobs typically receive priority. However, unlike SRPT, SAP has a safeguarding feature that ensures that large jobs cannot be starved indefinitely. In particular, SAP guarantees that every job completes at least as early as it would under processor sharing (PS), a common web serving protocol. Indeed, SAP is strictly better than PS for every nonterminal job during a busy period. Thus, SAP provides an attractive protocol for web servers.