CprE 458/558: Real-Time Systems(m, k) firm real-time tasksTask model and performance indexMK-RMS Schedulability Check [2]MK-RMS Schedulability - exact analysis [2]Scheduling ExampleExample (Cont.)Introduction (Cont.)Proposed scheduling architecture [3]Proposed scheduling architecture (Cont.)Feedback control algorithmOnline controller designFairness measureSimulation studiesSimulation studies (Cont.)Imprecise computation - summaryReferencesCprE 458/558: Real-Time Systems (G. Manimaran) 1CprE 458/558: Real-Time Systems (m, k)-firm tasks and QoS enhancementCprE 458/558: Real-Time Systems (G. Manimaran) 2 (m, k) firm real-time tasks•A periodic task is said to have an (m,k)-firm guarantee if it is adequate to meet the deadlines of m out of k consecutive instances of the task, where m ≤ k.•The adaptive QoS management problem–Admit the tasks to satisfy at least the (m,k) guarantee–Maximize the QoS of admitted tasks beyond the (m,k) property, at run-time, without violating (m,k) property of any of the admitted tasks.CprE 458/558: Real-Time Systems (G. Manimaran) 3Task model and performance index•Task Model - firm periodic tasks [1,2]•Tasks should meet mi deadlines for every Ki consecutive instances•Performance Index–Dynamic Failure Rate (DFR): for a task Ti, it is the percentage of instances of the task miss their (m,k) guarantee.–Marginal Quality Received (MQR):•To maximize the quality of tasks during overloading, is increased as much as possibleperiodptimecompckmpcTiiiiiii:.:,,, iiiiiiiiTtaskofMQRMQRusedvalueactualthemmkmmMQR::imCprE 458/558: Real-Time Systems (G. Manimaran) 4MK-RMS Schedulability Check [2]•Utilization-based MK-RMS-schedulability check (sufficient, but not necessary)MKLoad <= n(21/n -1)•Classification of mandatory and optional instances - Instances of task Ti activated at times api is mandatory if•Optional instance is assigned the lowest priority•Mandatory instances are assigned priority as per RMS ,2,1,0amkkmaaiiiiniiiiikpmcmkLoad1CprE 458/558: Real-Time Systems (G. Manimaran) 5MK-RMS Schedulability - exact analysis [2]•Theorem: Given such that Let•If , MK-RMS meets the (m,k)-firm guarantee requirement of11)()(0,:ijjijiiijijijjjjjijctnctWRnlorZlTTmklmklRnTTT ,,,21.21 nppp iiiTTW )(iiiiikmpcT ,,,CprE 458/558: Real-Time Systems (G. Manimaran) 6Scheduling ExampleTask 1Task 2RMS120120120(a) T1: <4,8,2,10> T2: <4,6,1,5>Task 1Task 2RMS120120120(b) T1: <4,8,4,10> T2: <4,6,2,5>Task 1Task 2RMS120120120(c) T1: <4,8,6,10> T2: <4,6,3,5>Task 1 misses its deadlineCprE 458/558: Real-Time Systems (G. Manimaran) 7Example (Cont.)•We can increase the values to increase the QoS when the system is underloaded, and decrease the values to handle overloading.•Feedback method can be used to adjust the values.–Regulated/measured variable:–Set point: desired value of –Control variable: estimation factor, , of imimimimetfDFRDFRCprE 458/558: Real-Time Systems (G. Manimaran) 8Introduction (Cont.)•Feedback control techniqueController ActuatorsControlledRT SystemSensorsSet PointsControlvariablesMeasured variablesRegulated variables+-disturbanceCprE 458/558: Real-Time Systems (G. Manimaran) 9Proposed scheduling architecture [3]PI ControllerActuatorSchedulerAdmission ControllerSubmitted tasksAccepted tasksAverage Dynamic Failure RateCPUCompleted tasks+-Set pointCprE 458/558: Real-Time Systems (G. Manimaran) 10Proposed scheduling architecture (Cont.)•Admit tasks based on minimum quality requirement•The actual execution time of tasks are normally less than or equal to the worst case execution time used in the admission test–Try to increase the quality as much as possible–Use feedback method to adjust .•Non-zero set point is used – achieve high CPU utilization and low dynamic failure rate• is zero with respect to – is changed with respect to the current laterDFRimDFRimimCprE 458/558: Real-Time Systems (G. Manimaran) 11Feedback control algorithm0.0]1,0[.::)()(11---initaltiitiitttttstetfinetfconfineparametercontrollerKfactorestimationetfmketfmmetfetfetfDFRDFRKetfCprE 458/558: Real-Time Systems (G. Manimaran) 12Online controller design•Initial Value of K: •Halve K when DFR fluctuate across set point 100.01.00.10.0maxsDFRetfK•K–high value will lead to fluctuation–Low value will lead to a long time to reach the final valueK on-linedesignSystemControllerControl signalOutputOutput changingobservationControllerparametersReferenceCprE 458/558: Real-Time Systems (G. Manimaran) 13Fairness measure•All tasks use the same value of all tasks are the same•Fairness index ( ) in terms of :etf)()(iiiiiiiimketfmmmketfmm MQRMQRf10::2)1(211ftas ksnofMQRaverageMQRTtaskofMQRMQRnMQRnMQRMQRfaiianiai•The higher the value of f for a task set, the better the fairness.CprE 458/558: Real-Time Systems (G. Manimaran) 14MQR performance: Load = 1.1 and MKLoad varied– MQR decreases as MKLoad increases–ACET < WCET can be exploited to increase MQR–Feedback algo offers better MQR than non-feedback algoSimulation studies•Feedback algorithm vs. iterative algorithmniiiiiniiikpmcmkLoadpcLoad11CprE 458/558: Real-Time Systems (G. Manimaran) 15Simulation studies (Cont.)Fairness (f): –Fairness obtained by the feedback approach is higher than that obtained by non-feedback algo (MK-RMS)CprE 458/558: Real-Time Systems (G. Manimaran) 16Imprecise computation - summary•Offers scheduling flexibility to achieve graceful degradation (i.e., means to achieve predictable timing faults without violating system spec)•Applicable only to a class of applications•Models–Imprecise computation - monotone model–Imprecise computation – 0/1 constraint model–(m,k)-firm modelCprE 458/558: Real-Time Systems (G. Manimaran) 17References[1] Reference [18] in chapter 4.[2] Overload management in real-time control applications using (m, k)-firm guaranteeRamanathan, P.; IEEE Transactions on Parallel and Distributed Systems, Volume 10, Issue 6, June 1999 Page(s):549 –