Method for quality of service controllable real-time scheduling

In a real-time scheduling mechanism for scheduling a plurality of tasks T, a method for 1-task-look-ahead substitutable checking, wherein the plurality of tasks T include respective mandatory portions M and optional portions O, the mandatory portions M of the plurality of tasks T are scheduled in a reservation list according to a model so that each of the mandatory portions Mi scheduled in the reservation list has a starting time si and an ending time fi, and after the mandatory portion Mi of each of the tasks Ti is completed, the method is performed on the task Ti, wherein, for each of the tasks Ti, the mandatory portion Mi has a processing time mi, the optional portion Oi has a processing time oi, and the subscript i indexes a sequence of starting time for the mandatory portions M scheduled in the reservation list, the method comprising the steps of:

• (a) determining an effective interval ti according to the starting time si+1 of the mandatory portion Mi+1 of a task Ti+1, the ending time fi of the mandatory portion Mi of the task Ti, and an interval for the processing time oi of the optional portion Oi of the task Ti;
• (b) moving the mandatory portion Mi+1 to a location in the reservation list by setting the starting time si+1 of the mandatory portion Mi+1 to be the ending time fi of the mandatory portion Mi and by changing the ending time fi+1 of the mandatory portion Mi+correspondingly;
• (c) determining an effective interval ti+1 according to the starting time si+2 of the mandatory portion Mi+2 of a task Ti+2, the ending time fi+1 of the mandatory portion Mi+1, and an interval for the processing time oi+1 of the optional portion Oi+1 of the task Ti+1;
• and
• (d) comparing the effective interval ti with the effective interval ti+1;
• if the effective interval ti is less than the effective interval ti+1, the optional portion Oi of the task Ti is 1-task-look-ahead substitutable;
• if the effective interval ti is greater than the effective interval ti+1, the optional portion Oi of the task Ti is not 1-task-look-ahead substitutable.

In a real-time scheduling mechanism for scheduling a plurality of tasks, a method for k-tasks-look-ahead substitutable checking, where k is an integer greater than one, wherein the plurality of tasks T include respective mandatory portions M and optional portions O, the mandatory portions M of the plurality of tasks T are scheduled in a reservation list according to a model so that each of the mandatory portions Mi scheduled in the reservation list has a starting time si and an ending time f1, and after the mandatory portion Mi of each of the tasks Ti is completed, the method is performed on the task Ti, wherein, for each of the tasks Ti, the mandatory portion Mi has a processing time mi, the optional portion Oi has a processing time o1, and the subscript i indexes a sequence of starting time for the mandatory portions M scheduled in the reservation list, the method comprising the steps of:

• (a) determining an effective interval ti according to the starting time si+1 of the mandatory portion Mi+1 of a task Ti+1, the ending time fi of the mandatory portion Mi of the task Ti, and an interval for the processing time oi of the optional portion O1 of the task Ti;
• (b) setting A to be one;
• (c) moving the mandatory portion Mi+A of a task Ti+A to a location in the reservation list by setting the starting time Si+A of the mandatory portion Mi+A to be the ending time fi+A−1 of the mandatory portion Mi+A−1 of a task Ti+A−1 and by changing the ending time fi+A of the mandatory portion Mi+A correspondingly;
• (d) determining an effective interval ti+A according to the starting time si+A−1 of the mandatory portion Mi+A−1 of a task Ti+A−1, the ending time fi+A−1 of the mandatory portion Mi+A−1, and an interval for the processing time Oi+A of the optional portion Oi+A of the task Ti+A;
• (e) if A is less than k, incrementing A by one and proceeding to said step (c);
• (f) determining an effective interval r by using the effective intervals ti+1 to ti+k;
• and
• (g) comparing the effective interval ti with the effective interval r;
• if the effective interval ti is less than the effective interval r, the optional portion Oi of the task Ti is k-tasks-look-ahead substitutable;
• if the effective interval ti is greater than the effective interval r, the optional portion Oi of the task Ti is not k-tasks-look-ahead substitutable.

In a real-time scheduling mechanism for scheduling a plurality of tasks, a method for k-tasks-look-ahead substitutable checking, where k is an integer greater than one, wherein mandatory portions M of the plurality of tasks T are scheduled in a reservation list according to a model so that each of the mandatory portions Mi scheduled in the reservation list has a starting time si and an ending time fi, wherein each of the tasks Ti further has an optional portion Oi with processing time o1, and after the mandatory portion Mi of each of the tasks Ti is completed, the method is performed on the task Ti, where i indexes a sequence of starting time for the mandatory portions M scheduled in the reservation list, the method comprising the steps of:

• (a) determining an effective interval ti according to the starting time si+1 of the mandatory portion Mi+1 of a task Ti+1, the ending time fi of the mandatory portion Mi of the task Ti, and an interval for the processing time oi of the optional portion Oi of the task Ti;
• (b) setting A to be one;
• (c) changing the location of the mandatory portion MiA of a task Ti+A in the reservation list by setting the starting time Si+A of the mandatory portion Mi+A to be the ending time fi+A−1 of the mandatory portion Mi+A−1 of a task Ti+A−1 and by changing the ending time fi+A of the mandatory portion Mi+A correspondingly;
• (d) determining an effective interval ti+A according to the starting time si+A−1 of the mandatory portion Mi+A−1 of a task Ti+A−1, the ending time fi+A−1 of the mandatory portion Mi+A−1, and an interval for the processing time Oi+A of the optional portion Oi+A of the task Ti+A;
• (e) comparing the effective interval ti with the effective interval ti+A;
• if the effective interval ti is less than the effective interval ti+A, the optional portion Oi of the task Ti is k-tasks-look-ahead substitutable;
• if the effective interval ti is greater than the effective interval ti+A, the optional portion Oi of the task Ti is not k-tasks-look-ahead substitutable;
• (f) ending the method if the optional portion O1 of the task Ti is k-tasks-look-ahead substitutable;
• and
• (g) if A is less than k, incrementing A by one and proceeding to said step (c);

In an on-line scheduler for scheduling n tasks, T1 to Tn, with a reservation list, a real-time scheduling method, wherein the reservation list has at most u tasks to be put into, each of the tasks Th has a mandatory portion Mh, an optional portion Oh, a mandatory portion processing time mh, and a deadline dh, where n is an integer greater than one and h is an integer not less than zero and not greater than n, the real-time scheduling method comprising:

• a1. determining whether there are any mandatory portions in the reservation list;
• if not, proceeding to step d3;
• a2. determining whether there is a mandatory portion waiting to be put into the reservation list;
• if so, putting the mandatory portion into the reservation list according to an imprecise computation model so that the reservation list hasp mandatory portions, wherein p is an integer not greater than u, and the p mandatory portions have respective starting times denoted by s with subscripts identical to subscripts of the p mandatory portions;
• b1. determining whether there is a mandatory portion Mi in the reservation list is scheduled to be executed immediately, where i is not less than one and not greater than p;
• if so, proceeding to step b3;
• b2. selecting a mandatory portion Mi from the p mandatory portions M in the reservation list according to the starting times of the mandatory portions M, and updating the starting time si of the mandatory portion Mi;
• b3. starting to execute the mandatory portion Mi and executing said step a2 until the mandatory portion Mi is completed;
• c1. determining whether the optional portion Oi of the task Ti is k-tasks-look-ahead substitutable;
• if not, proceeding to step c4;
• c2. removing the task Ti from the on-line scheduler;
• c3. proceeding to said step a1;
• c4. starting to execute the optional portion Oi of the task Ti, executing said step a2, and then executing step c8 after the execution of said step a2;
• c5. determining whether a mandatory portion Mj is to be executed according to the reservation list, where j is an integer not less than one and not greater than p and not equal to i;
• if so, proceeding to step c8;
• c6. determining whether the task Ti is completed;
• if so, proceeding to step c8;
• c7. determining whether the deadline di of the task Ti is reached;
• if not, proceeding with said step c4;
• c8. removing the task Ti from the on-line scheduler;
• d1. determining whether there is a task in the on-line scheduler;
• if not, proceeding to step d3;
• d2. proceeding to said step a1;
• and
• d3. ending the method.

In an on-line scheduler for scheduling n tasks, T1 to Tn, with a reservation list, a real-time scheduling method, wherein the reservation list has at most u tasks to be scheduled in, each of the tasks Th has a mandatory portion Mh, an optional portion Oh, a mandatory portion processing time mh, and a deadline dh, where n is an integer greater than one and h is an integer not less than zero and not greater than n, the real-time scheduling method comprising:

• a1. determining whether there are any mandatory portions in the reservation list;
• if not, proceeding to step d3;
• a2. determining whether there is a mandatory portion waiting to be put into the reservation list;
• if so, putting the mandatory portion into the reservation list according to an imprecise computation model so that the reservation list hasp mandatory portions, wherein each of the p mandatory portions Mk has a starting time sk and an ending time ek, where p is an integer not greater than u and k is an integer not greater than u;
• b1. determining whether there is a mandatory portion Mi in the reservation list is scheduled to be executed immediately, where i is not less than one and not greater than p;
• if so, proceeding to step b3;
• b2. selecting a mandatory portion Mi from the p mandatory portions M in the reservation list according to the starting times of the mandatory portions M, and updating the starting time si of the mandatory portion Mi;
• b3. starting to execute the mandatory portion Mi and executing said step a2 until the mandatory portion Mi is completed;
• c1. determining whether the optional portion Oi of the task Ti is k-tasks-look-ahead substitutable;
• if not, proceeding to step c12;
• c2. selecting a mandatory portion Mq from the reservation list, wherein a starting time sq of the mandatory portion Mq is a minimum among the starting times which are greater than the ending time ei of the mandatory portion Mi, and q is an integer not less than one and not greater than p;
• c3. determining a spare interval gi, wherein the spare interval gi is defined by the starting time sq and the ending time ei and has a length defined by the difference between the starting time sq and the ending time ei;
• c4. determining an insertion time vi, wherein the insertion time vi is defined by the difference between the deadline di and the length of the spare interval gi;
• c5. determining whether the insertion time vi is greater than the ending time e1 and less than the deadline di;
• if so, proceeding to step c8;
• c6. removing the task Ti from the on-line scheduler;
• c7. proceeding to said step a1;
• c8. starting to execute the mandatory portion Mq and executing said step a2 until the mandatory portion Mq is completed;
• c9. starting to execute the optional portion Oi of the task Ti, executing said step a2, and then executing step c11 after the execution of said step a2;
• c10. determining whether a mandatory portion Mj is to be executed according to the reservation list, where j is an integer not less than one and not greater than p and not equal to i;
• if so, proceeding to step c13;
• c11. determining whether the task Ti is completed;
• if so, proceeding to step c13;
• c12. determining whether the deadline di of the task Ti is reached;
• if not, proceeding to said step c9;
• c13. removing the task Ti from the on-line scheduler;
• d1. determining whether there are any tasks in the on-line scheduler;
• if not, proceeding to step d3;
• d2. proceeding to said step a1;
• and
• d3. ending the method.

In an on-line scheduler for scheduling n tasks, T1 to Tn, with a reservation list, a real-time scheduling method, wherein the reservation list has at most u tasks to be put into, each of the tasks Th has a mandatory portion Mh, an optional portion Oh, a mandatory portion processing time mh, and a deadline dh, where n is an integer greater than one and h is an integer not less than one and not greater than n, the real-time scheduling method comprising:

• a1. determining whether there are any mandatory portions in the reservation list;
• if not, proceeding to step d3;
• a2. determining whether there is a mandatory portion waiting to be put into the reservation list;
• if so, putting the mandatory portion M into the reservation list according to an imprecise computation model so that the reservation list hasp mandatory portions, wherein p is an integer greater than r and not greater than u, and each of the p mandatory portions Mk has a starting time sk and an ending time ek, where p is an integer not greater than u and k is an integer not greater than u;
• b1. determining whether there is a the mandatory portion Mi in the reservation list is scheduled to be executed immediately, where i is not less than one and not greater than p;
• if so, proceeding to step b3;
• b2. selecting a mandatory portion Mi from the p mandatory portions in the reservation list according to the starting times of the mandatory portions M, and updating the starting time si of the mandatory portion Mi;
• b3. starting to execute the mandatory portion Mi and executing said step a2 until the mandatory portion Mi is completed;
• c1. determining whether the optional portion Oi of the task Ti is k-tasks-look-ahead substitutable;
• if not, proceeding to step c7;
• c2. determining a block separation number bi, wherein the block separation number bi is one plus the number of a mandatory portion set in the reservation list;
• c3. selecting a mandatory portion Mq from the reservation list, wherein the mandatory portion Mq belongs to the mandatory portion set, and the starting time Sq of the mandatory portion Mq is a minimum among starting times associated with the mandatory portion set and is greater than the ending time ei, and subscript q is an integer not less than one and not greater than p;
• c4. determining a spare interval gi, wherein the spare interval gi is defined by the starting time sq and the ending time ei and has a length defined by the difference between the starting time sq and the ending time ei;
• c5. determining an optional-portion processing period ot, wherein the optional-portion processing period ot is defined by the length of the spare interval gi divided by the block separation number bi;
• c6. starting to execute the optional portion Oi of the task Ti for the optional-portion processing period ot, and executing said step a2 until the optional portion Oi of the task Ti has been executed for optional-portion processing period ot;
• c7. removing the task Ti from on-line scheduler;
• c8. starting to execute a task Tr associated with one of the mandatory portion set beginning from the mandatory portion Mq according to the starting times of the mandatory portions in the mandatory portion set, until all of the mandatory portions in the mandatory portion set are executed and all optional portions associated with the mandatory portions in the mandatory portion set are executed for the optional-portion processing period ot;
• d1. determining whether there are any tasks in the on-line scheduler;
• if not, proceeding to step d3;
• d2. proceeding to said step a1;
• and
• d3. ending the method.

A method for quality-of-service-controllable real-time scheduling, the method comprising the steps of:

• (a) regulating the number of input tasks which are to be forwarded to an on-line scheduling unit through a regulating unit;
• (b) by the on-line scheduling unit, selecting a real-time scheduling method, scheduling tasks forwarded to the on-line scheduling unit according to the real-time scheduling method, and outputting a scheduling result;
• and
• (c) by an evaluating unit, evaluating the scheduling result, feeding a first set of parameters into the regulating unit for a coarse adjustment, and feeding a second set of parameters into the on-line scheduler for a fine adjustment.