THE REJECTION RATE FOR TASKS WITH RANDOM ARRIVALS, DEADLINES, AND PREEMPTIVE SCHEDULING

Random arrivals and hard deadlines for completion of a response may occur in safety related computer systems dealing with alarms (e.g., nuclear power plants) or in tracking systems (e.g., air traffic control or missile tracking systems). With random arrivals it cannot be guaranteed that all responses will be completed on time, because of congestion; we assume these tasks are rejected and lost. The design goal is to keep congestion low enough to make the probability of rejection acceptably small. These designs, it turns out, must have low processor utilization. The present study analyzes rejection probabilities at utilizations up to 20% and rejection probabilities up to about 10%, for various well-known preemptive scheduling disciplines (shortest job first, earliest due date, and least laxity first) as well as first-come, first-served. Good approximations are found for the rejection probability and for a number of other properties, such as the distribution of time-to-go at rejection. © 1990 IEEE