Multi-granularity resource reservations

Resource reservation has been recently supported by many real-time operating systems to provide applications with guaranteed and timely access to system resources. Typically, reservations are based on the worst-case requirements, and therefore can inflate resource demands unnecessarily. Many multimedia applications such as MPEG video streams (1) have high worst-case to average-case demand ratio and (2) can tolerate some deadline misses. To support such applications, we propose a "multi-granularity" reservation model. Instead of the classical {C, T, D} model of resource reservation, the multi-granular reserve specification is given by {{C,T,D},...,{C^x, epsi^xT_i},...,{C^y, epsi^yT _i}} which represents a guarantee of the highest-granularity reserve for C units of resource during every successive periodic interval of T only as long as the resource usage by each of its low-granularity reserves (e.g., C^x units of resource in every recurring time of epsi^xT_i, epsi^x isin Z⁺) is maintained. This multi-granular reservation approach delivers higher system utilization than the pessimistic strategy of worst-case reservation and better temporal isolation than other stochastic and heuristic guarantees in the literature. We perform a detailed schedulability analysis of this model using deadline-monotonic scheduling and derive an appropriate admission control test. We also present detailed analyses and simulation results comparing our reservation scheme for MPEG-4 streams with average-case resource reservation, constant bandwidth server (CBS), and (m, k)-firm guarantee