Modeling Restricted Processor Sharing in a Computer System with Non-exponential Service Times

A computer system often has to handle computational jobs with highly varying CPU service time requirements. In principle, unrestricted processor sharing can be useful in handling such demands. In practice, it must be implemented by round-robin, and there is an overhead cost (e.g., cache thrashing and operating system management of job switching) to implementing this scheme. Furthermore, significant main-memory thrashing (i.e., increased paging activities) may occur with many jobs inside the system. To bound the cache thrashing overhead, the number of jobs actively sharing the processors has to be restricted. This is essentially restricted processor sharing. Similarly, to bound the main-memory thrashing overhead, the total number of jobs granted access to the system at any time has to be restricted as well. Because of these population size constraints, the existing analytical results for Jackson networks do not apply here. The goal of this research, therefore, is to develop analytical models for systems under the above mentioned constraints and the impact of memory thrashing overhead.

The left state is in So, denoting the system being idle. The middle three states are
in Si, denoting one job in the system. Similarly, the right six states are in S2,
denoting two jobs in the system. Such a system corresponds to a quasi-birth-
death ...