The Role of Virtual Time in Real-time Scheduling

Abstract:

The BERT scheduler is designed to schedule a mix of best effort and
real-time processes. BERT is based on manipulating how tasks run in
the fair queueing fluid model and tracking the changes using virtual
time. This paper makes two contributions. First, it builds on results
in real-time scheduling to show two properties of BERT: (1) important
real-time tasks are schedulable with regard to their finish times in
the fluid model and (2) unimportant tasks have bounded workahead. BERT
relies on these two properties when making scheduling
decisions. Second, it draws attention to the thread that connects the
fluid model and the BERT implementation: virtual time. Virtual
time is multifaceted and powerful abstraction and we use our results
for BERT to argue that it can form the basis for designing,
implementing, and analyzing new real-time scheduling algorithms.