User:Pennpanda

Real-Time-Deferrable-Server(RTDS)-Based CPU Scheduler

Introduction

The Real-Time Deferrable Server (rtds) scheduler is a real-time CPU scheduler built to provide guaranteed CPU capacity to guest VMs on SMP hosts. It is introduced with name rtds in Xen 4.5 as an experimental scheduler.

[WARN] The scheduler has been included as an experimental and in-development feature.

Description

Each VCPU of each domain is assigned a budget and a period. The VCPU with <budget>, <period> is supposed to run for <budget>us (not necessarily continuously) in every <period>us.

Note: The VCPUs of the same domain have the same parameters right now.

Usage

The xl sched-rtds command can be used to tune the per VM guest scheduler parameters.

• xl sched-rtds -d <domain> :List the parameter of the specified <domain>
• xl sched-rtds -d <domain> -p <period> -b <budget> : Set each VCPU's budget to <budget>us and period to <period>us of the specified <domain>

Algorithm

The design of this rtds scheduler is as follows:

Each VCPU has a dedicated period and budget. The deadline of a VCPU is at the end of each period; A VCPU has its budget replenished at the beginning of each period; While scheduled, a VCPU burns its budget. The VCPU needs to finish its budget before its deadline in each period; The VCPU discards its unused budget at the end of each period. If a VCPU runs out of budget in a period, it has to wait until next period.

Each VCPU is implemented as a deferable server. When a VCPU has a task running on it, its budget is continuously burned; When a VCPU has no task but with budget left, its budget is preserved.

This scheduler follows the Preemptive Global Earliest Deadline First (EDF) theory in real-time field to schedule these VCPUs. At any scheduling point, the VCPU with earlier deadline has higher priority. The scheduler always picks the highest priority VCPU to run on a feasible PCPU. A PCPU is feasible to a VCPU if the PCPU is idle or has a lower-priority VCPU running on it.

Queue scheme: A global runqueue and a global depletedq for each CPU pool. The runqueue holds all runnable VCPUs with budget and sorted by deadline; The depletedq holds all VCPUs without budget and unsorted.

TODO

The following features will be implemented after Xen 4.5

   # Burn budget in finer granularity instead of 1ms; [medium]
   # Use separate timer per VCPU for each VCPU's budget replenishment, 

instead of scanning the full runqueue every now and then [medium]

   # Handle time stolen from domU by hypervisor. When it runs on a machine 

with many sockets and lots of cores, the spin-lock for global RunQ used in rtds scheduler could eat up time from domU, which could make domU have less budget than it requires. [not sure about difficulty right now]

   # Toolstack supports assigning/display each VCPU's parameters of each 

domain.

Glossary of Terms

• us: microsecond
• Host: The physical hardware running Xen and hosting guest VMs.
• VM/domU: Guest virtual machine.
• VCPU: Virtual CPU (one or more per VM).
• CPU/PCPU: Physical host CPU.
• Period: The period when a VCPU's budget is replenished or discarded.
• Budget: The amount of time a VCPU can execute within its period.

Also See

• Scheduler Subcommands
• RT-Xen website
• Blog descripting RT-Xen