A Mixed PS-FCFS Policy for CPU IntensiveWorkloads

Round robin (RR) is a widely adopted scheduling policy in modern computer systems. The scheduler handles the concurrency by alternating the run processes in such a way that they can use the processor continuously for at most a quantum of time. When the processor is assigned to another process, a context switch occurs. Although modern architectures handle context switches quite efficiently, the processes may incur in some indirect costs mainly due to cache overwriting. RR is widely appreciated both in case of interactive and CPU intensive processes. In the latter case, with respect to the First-Come-First-Served approach (FCFS), RR does not penalise the small jobs. In this paper, we study a scheduling policy, namely PS-FCFS, that fixes a maximum level of parallelism N and leaves the remaining jobs in a FCFS queue. The idea is that of exploiting the advantages of RR without incurring in heavy slowdowns because of context switches. We propose a queueing model for PS-FCFS allowing us to: (i) find the optimal level of multiprogramming and (ii) study important properties of this policy such as the mean performance measures and results about its sensitivity to the moments of the jobs' service demands.