Show simple item record

dc.contributor.authorZhang, Yutingen_US
dc.contributor.authorWest, Richarden_US
dc.contributor.authorQi, Xinen_US
dc.date.accessioned2011-10-20T04:19:15Z
dc.date.available2011-10-20T04:19:15Z
dc.date.issued2004-03-23
dc.identifier.urihttps://hdl.handle.net/2144/1541
dc.description.abstractThis paper presents a new approach to window-constrained scheduling, suitable for multimedia and weakly-hard real-time systems. We originally developed an algorithm, called Dynamic Window-Constrained Scheduling (DWCS), that attempts to guarantee no more than x out of y deadlines are missed for real-time jobs such as periodic CPU tasks, or delay-constrained packet streams. While DWCS is capable of generating a feasible window-constrained schedule that utilizes 100% of resources, it requires all jobs to have the same request periods (or intervals between successive service requests). We describe a new algorithm called Virtual Deadline Scheduling (VDS), that provides window-constrained service guarantees to jobs with potentially different request periods, while still maximizing resource utilization. VDS attempts to service m out of k job instances by their virtual deadlines, that may be some finite time after the corresponding real-time deadlines. Notwithstanding, VDS is capable of outperforming DWCS and similar algorithms, when servicing jobs with potentially different request periods. Additionally, VDS is able to limit the extent to which a fraction of all job instances are serviced late. Results from simulations show that VDS can provide better window-constrained service guarantees than other related algorithms, while still having as good or better delay bounds for all scheduled jobs. Finally, an implementation of VDS in the Linux kernel compares favorably against DWCS for a range of scheduling loads.en_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2004-013
dc.titleA Virtual Deadline Scheduler for Window-Constrained Service Guaranteesen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record