Scheduling Tasks for a Time Sharing Computer System with a Single Processor

Abstract

We consider a time sharing computer system with a single processor where tasks of K different types arrive at the system according to independent time homogeneous Poisson processes from outside. A task, after given a quantum for processing, leaves the system, or changes the type and rejoins the system according to specified probabilities. While many existing priority time sharing models determine the priorities of tasks strictly by their service time requirements, this paper develops a new scheduling rule wherein the importances or urgencies in addition to the service time requirements of tasks are counted, by imposing an appropriate reward structure on the system. Also presented is the algorithm thruough which to determine the rankings of K types according to this new scheduling rule.