ACHIEVING TIME BASED FAIRNESS FOR EVENT SCHEDULING IN NON PREEMPTIVE EVENT DRIVEN SCHEDULING SYSTEMS
Publication Date: 2015-Dec-02
The IP.com Prior Art Database
Vikram Munishwar: AUTHOR [+4]
Mechanisms and systems are provided to achieve fairness in an event driven computing system for events with variable processing time so that no high priority events will be starved due to low priority events that take significantly more processing time than high priority events Existing non preemptive scheduling systems do not focus on this issue which is prominent in event batching systems Two approaches are proposed which track the time used by each queue with and without the traditional metric of the number of events processed from each queue These approaches are time based Weighted Round Robin WRR scheduling and time credit based WRR scheduling approaches Time based WRR scheduling allows applications to allocate a time interval for each queue after which the next queue is scheduled The advantage of a time credit based WRR scheduling approach is that it takes the queue priority values from the application and converges towards assigning appropriate time intervals for all queues in real time
Page 01 of 12
ACHIEVING TIME-BASED FAIRNESS FOR EVENT-SCHEDULING IN NON- PREEMPTIVE EVENT-DRIVEN SCHEDULING
CISCO SYSTEMS, INC.
Mechanisms and systems are provided to achieve fairness in an event driven computing system for events with variable processing time so that no high-priority events will be starved due to low-priority events that take significantly more processing time than high-priority events. Existing non-preemptive scheduling systems do not focus on this issue, which is prominent in event batching systems. Two approaches are proposed which track the time used by each queue with and without the traditional metric of the number of events processed from each queue. These approaches are time-based Weighted Round Robin (WRR) scheduling and time-credit based WRR scheduling approaches. Time-based WRR scheduling allows applications to allocate a time-interval for each queue after which the next queue is scheduled. The advantage of a time-credit based WRR scheduling approach is that it takes the queue priority values from the application and converges towards assigning appropriate time-intervals for all queues in real-time.
In event-driven programming paradigm, a flow of a computing program is determined by events. The events can be classified into different types and fed into different queues for scheduling. Examples of such queues include networking queues that handle network events/packets, internal queues that handle system events and application queues that handle application-generated events.
Copyright 2015 Cisco Systems, Inc.
Page 02 of 12
As different queues may have different priorities, the queue-scheduling policy needs to ensure that weighted fairness is maintained proportional to the queue priorities over a period of time. Conventional queue scheduling policies primarily operate at event granularity. Specifically, queue priorities are translated to a number of events to be processed from those queues before moving ahead to the next queue.
Based on these general principles, the following variations of scheduling policies are defined:
(1) First-In First-Out (FIFO) scheduling: In FIFO scheduling, events/tasks are processed in the order of their arrival, irrespective of their priority. Embedded operating systems, such as the "TinyOS" operating system and the "Contiki" operating system, rely on FIFO scheduling to schedule their tasks/events.
(2) Round Robin (RR) scheduling: In RR scheduling, all queues are allocated the same priority. Hence, the number of events processed per queue remains the same over time.
(3) Weighted Round Robin (WRR) scheduling: In WRR scheduling, each queue is assigned a different priority/weight, which is translated to the number of events that a queue can schedule in one cycle of round robin scheduling.
(4) Strict Priority Scheduling: Similar to WRR, in strict priority scheduling, each queue is...