[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [Xen-devel] [Design RFC] Towards work-conserving RTDS scheduler
Hi Dario, I'm thinking about changing the current RTDS scheduler to work-conserving version as we briefly discussed before. Below is a design of the work-conserving RTDS. I'm hoping to get your feedback about the design ideas first before I start writing it in code. I think the code change should not be a lot as long as we don't provide the functionality of switching between work-conserving and non-work-conserving. Because the following design will keep the real-time property of the current RTDS scheduler, I don't see the reason why we should let users switch to non-work-conserving version. :-) Thank you very much and looking forward to your comments! --- Below is the design --- *** Motivation *** A scheduler is working-conserving if the scheduler always pick a "task" (i.e., VCPU in RTDS scheduler case) as long as there still exists a pending "task" that has not finished. The current RTDS scheduler is not work-conserving. The non-work-conserving property of the current RTDS scheduler prevents the scheduler from utilizing the system's *idle* resource. For example, when there is only one VCPU with period = 10ms and budget = 4ms, on one CPU, scheduled by the RTDS scheduler, the VCPU can only get 4ms for every 10ms. This leaves the CPU idle for 6ms in every 10ms. This is OK/safe because we assume the system administrator has already known the workload on the VCPU and believes the VCPU (period = 10ms, budget = 4ms) is enough to provide real-time guarantee to the workload on the VCPU. However, we can further improve the system's average performance without breaking the real-time property of the RTDS scheduler by utilizing the idle resource. *** Current RTDS scheduler in Xen *** 1) VCPU model: Each VCPU has period and budget 2) Scheduling policy: gEDF 3) Server mechanism: Deferrable server 4) Behavior: When VCPUs are schedulable on M cores, each VCPU is guaranteed to be able to provide budget time in each period. Each VCPU can run for * at most * budget time in each period *** Observations of current RTDS scheduler *** 1) gEDF is work-conserving algorithm, but 2) Deferrable server is not “work-conserving”: When system has idle resource, the deferrable server is not allowed to over-run. This property of deferrable server prevent the RTDS scheduler from using the idle resource in the system to improve the average response time of VCPUs. *** Requirement of the work-conserving RTDS scheduler *** 1) The new RTDS scheduler should be work-conserving, of course. 2) The new RTDS scheduler should not break any real-time guarantee provided by the current RTDS scheduler. *** Design of Work-Conserving RTDS Scheduler *** VCPU model 1) (Period, Budget): Guaranteed <Budget> time for each <Period> 2) Priority index: It indicates the current priority level of the VCPU. When a VCPU’s budget is depleted in the current period, its priority index will increase by 1 and its budget will be replenished. 3) A VCPU’s budget and priority index will be reset at the beginning of each period Scheduling policy: modified gEDF 1) Priority comparison: a) VCPUs with lower priority index has higher priority than VCPUs with higher priority index b) VCPUs with same priority index uses gEDF policy to decide the priority order 2) Scheduling point a) VCPU’s budget is depleted for the current priority index b) VCPU starts a new period c) VCPU is blocked or waked up 3) Scheduling decision is made when scheduler is invoked a) Always pick the current M highest-priority VCPUs to run on the M cores. ----------- Meng Xu PhD Student in Computer and Information Science University of Pennsylvania http://www.cis.upenn.edu/~mengxu/ _______________________________________________ Xen-devel mailing list Xen-devel@xxxxxxxxxxxxx https://lists.xen.org/xen-devel
|
Lists.xenproject.org is hosted with RackSpace, monitoring our |