The Earliest Eligible Virtual Deadline First (EEVDF) proportional share resource allocation algorithm proposed by Stoica et al. provides the theoretical foundations needed to achieve real-time performance in time-shared operating systems. Two problems encountered when trying to apply EEVDF to a time-sharing system with real-time and non-real-time constraints are solved. First, a polynomial-time algorithm is presented that efficiently solves the problem of assigning weights to real-time clients in a system that supports both real-time and non-real-time clients. Second, a method is presented to re-compute virtual deadlines when clients enter or leave a dynamic, proportional share system that is scheduled using the EEVDF algorithm.
