Analysis and Optimization of a Queueing Model of a Real-Time Computer Control System

A single processor provides service to jobs of several different priority classes. The priority ordering remains constant over time; however, the type of priority, i. e., preemptive or nonpreemptive, may depend upon the stage of processing of the job occupying the processor. We allow these preemptible and nonpreemptible intervals to be specified in a relatively arbitrary fashion. If a job is interrupted, a setup time must be incurred before processing can be continued on the job. If arrivals from all classes constitute independent Poisson streams, we are able to obtain expressions for the steady-state expected time in system for jobs of each class. These expressions are then analyzed to determine the optimum manner for assigning the preemptible and nonpreemptible intervals. When setup times are zero and preemptible portions are preemptive-resume, the optimal policy is fairly simple. When setup times are nonzero, the form of the optimal policy is not clear; however, numerical evaluations suggest that at high loads, e.g., greater than 0.9, one should allow much less preemption or time-sharing than one might suspect.