Donald Bren School of Information and Computer Sciences

Allocation of all resources to maximize the total value of the completion times for all jobs in a multiprogrammed computing system is investigated in this study. In traditional multiprogrammed operating systems, scheduling use of the central processor and main memory has been treated separately from allocation of other system resources. This study investigates the benefits of allocating all resources in a single framework using explicitly specified payoff functions.

A model of resource allocation and scheduling forms the basis of the investigation. To aid understanding and designing resource allocation strategies, the model provides for uniform treatment of all resources. Each process is modeled as a series of resource requests and releases. The process requests resources. The operating system must either grant the requests or suspend the process. The performance of the scheduler is represented by the set of response times produced when scheduling a job mix.

A new resource allocation strategy which overcomes deficiencies of existing schedulers is presented. Explicit specification of the value of jobs as a function of the time taken to complete them allows the use of utility theory evaluations in making resource allocation decisions and provides the system manager better control over the operation of the system.

Dynamic determination of the opportunity costs of resource assignments are used advantageously in making resource allocation decisions. Simulation experiments showed that value-based allocation is feasible. Because value-based scheduling gives the system manager more flexibility in specifying system goals, it is more adaptable to specific requirements than traditional schedulers. When its parameters were set to approximate the value function of a modern multilevel queue scheduler, the value-based scheduler performed as well as the multi level queue scheduler.