Grade of Service of Non-Critical Tasks

Get Complete Project Material File(s) Now! »

Chapter 3 Fairness in Processing

Chapter Overview

This chapter explores the issues of fairness in non-critical task execution in mixed-criticality systems. Firstly some background is given into the concept of mixed-criticality systems, tasks, deadlines and priorities. A new measure for the evalua-tion of the Grade of Service of task execution for a non-critical task is presented. The Grade of Service is then used to create a penalty formula to allow for tasks to be prioritised between each other based on the highest penalty value. Four di erent algorithms are tested across various combinations of tasks and proces-sor utilisations with both system-wide Grade of Service and system-wide fairness evaluated. The newly-developed algorithms were shown to ensure a more propor-tionate and fair distribution of system resources between non-critical tasks in an over-utilised system.

Background

Embedded systems have become increasingly more proli c in the modern age. Em-bedded systems are digital systems which are embedded in a product to perform a speci c function or functions and have made their way into many elds such as avionics, vehicles, industrial automata, communication, robotics, and consumer electronics. The reliability of embedded systems is dependent on its intended function. The majority of embedded systems are non-critical, meaning that their failure to operate correctly leads to negligible consequences and can therefore place less emphasis on their reliability. However, systems such as medical implements and industrial controllers must be reliable, as their failure to operate correctly may lead to catastrophic consequences – these systems are called safety-critical [72]. The designs of safety-critical embedded systems [73] are cemented in meeting in-creasingly stringent safety standards and guarantees [74{76]. When a device serves both safety-critical and non-critical purposes, it is said to be of mixed-criticality. Examples of safety-critical, non-critical, and mixed-criticality embedded systems are shown in Figure 3
Timing Needs of Embedded Systems
Embedded systems all possess timing needs which are speci c to their function. These timing needs can be completely separate from their level of criticality. Four example embedded devices are displayed in Figure 3.2. The four needs are ex-plained below:
Robotic Surgery: High-Speed High-Criticality
A robotic surgeon is a high-speed device as it requires both accurate and precise movements in cutting implements such as lasers. It is also of high-criticality as a missed deadline may cause injury to a person.
Pacemaker: Low-Speed High-Criticality
A pacemaker is relatively low-speed in terms of processing speed [77, 78]. It is, however, a safety-critical device as a missed deadline may trigger widely varying types of reactions to a patient [79].
High-Speed Camera: High-Speed Low-Criticality
A high-speed camera may take thousands or even millions of frames of footage per second [80], and therefore has need of extremely fast process-ing. However, the criticality level of the device is low as a missed deadline will lead to a slower frame-rate which is not reasonably catastrophic.
Calculator: Low-Speed Low-Criticality
A calculator is a low-speed device [81] of low-criticality. Calculators are usually used for solving relatively simple equations and can therefore have a low processing speed and still be t for their purpose. A missed deadline in a calculator results in a longer wait for the answer which is not catastrophic.

Timing Discrepancies

It can be seen that a successful embedded system needs to not only meet its timing requirements, but also meet its reliability requirements – which are not necessarily coupled with timing. Therefore to build a successful embedded system, one must understand the timing behaviour of both the computations and the physical components of the device. There exists a discrepancy between the concept of time in the physical world and the digital world.
A physical process such as the movement of a motor in a vehicle, or the contraction of a muscle in a heart, can be described using ordinary di erential equations – that is, the systems run on a concept of continuous time which is input to determine the current state of the physical component.
The timing component of a digital processor is much more indirect and complex. Embedded processors execute code such as C [82]. A digital processor does not take in time as an input, instead the notion of time is nothing more than the side-e ect of executing the program on a particular processor [83]. A di erent processor, clock-speed, input, optimisation scheme, or environment may yield a di erent notion of time [84] – it is therefore not practical to try to quantify timing predictability as the value will change depending on many factors [71].
There are workarounds to attempt to create a notion of time within processors. One such method is to break down the programming execution into discrete time-steps called ticks. These time-steps include enough processing time for all tasks to be executed. So long as the time-steps are faster than the speed of the particular environment, then the processor will appear to be working in real-time – this is the synchrony hypothesis [85].

Static Timing Analysis

For an implementation to be reliable (and therefore be able to house a safety-critical application), the timing qualities of all tasks in the program on a speci c processor must be known or approximated in order to be able to cater to them. This is achieved through the process of Static Timing Analysis [86].
The execution of any task on the system can vary greatly depending on such things as inputs, environment, execution-path, cache-hits or cache-misses and a multitude of other factors. Therefore the execution of any task is not one individual value, but a range of values. Figure 3.3 shows an example program’s execution
times as a probability distribution. The solid curve shows (under an assumption of omniscience about the program’s execution), what the actual execution times and their respective probabilities are. However, it is not practical to test for all possible inputs, states, environments, or any other variable that a device may receive. Therefore a test-set of inputs is used. This test-set results in a subset of all possible execution times of the device (shown by the dashed line in Figure 3.3). The shortest execution time is called the Best-Case Execution Time (BCET) while the longest execution time is called the Worst-Case Execution Time (WCET).
It is unlikely that the actual BCET or WCET would be in the measured set. Even if the BCET or WCET were in the measured set, there would be no way to determine that they are the actual BCET or WCET without rst evaluating all possible inputs rst. Therefore, the BCET and WCET are both over-estimated from the measured BCET and WCET in order to safely account for the inclusion of their actual values. Relying on the measured WCET, for example, would be unsafe as the program may execute for a longer time and therefore break the alloted time for a program tick.
Therefore the estimation of the BCET, and especially the WCET are imperative for static time analysis.

Deadlines

Yip et al. [2] identi es three levels of task criticality based on its timing needs: life-critical, mission-critical, and non-critical. These levels of criticality and their timing needs are illustrated in Figure 3.4
Life-Critical: No deadline-miss tolerance
A Life-Critical task is a task of the highest priority. Each task is equipped with a single deadline which must be guaranteed to be met.
Mission-Critical: Bounded deadline-miss tolerance
A Mission-Critical task contains a deadline which is able to be missed with a nite bound for the deadline miss. The scheduler should aim to complete task execution by the deadline, however, there exists a bound in which exe-cution can complete beyond the deadline and still be acceptable. The initial deadline is a soft-deadline whereas the miss bound is the task’s hard-deadline.
Non-Critical: Unbounded deadline-miss tolerance
A Non-Critical task has unbounded deadline-miss tolerance. The concept of a deadline does not even directly apply to a non-critical task, as it is acceptable for it to never be serviced. However, a non-critical task usually has a period which can act as a pseudo-deadline – which can be missed. For the purposes of this thesis, a non-critical task’s period shall be its deadline.

Mixed-Criticality Systems

A mixed criticality system [87] contains tasks of di ering criticalities and caters to the necessary safety and guarantees of each task respectively. By containing tasks of di ering criticalities, a scheduler is then required to give di erent level of guarantees for each task depending on its requirements. The criticality of a task is the level of assurance required against its failure to meet its requirements [87] – in the case of IEC 61508 [88] there are four di erent Safety Integrity Levels (SILs).
A simple solution to scheduling a mixed-criticality system is to assign a high pri-ority and o er the same stringent guarantees for all tasks. Doing so, however, will result in over-provisioning of resources where lesser resources would have su ced for the purpose of the system.
The scheduling of mixed criticality systems, however, is not a simple matter. Ear-liest Deadline First (EDF) [89] scheduling is a ubiquitous and e cient method of scheduling tasks. However, since a task’s priority is directly tied in to its dead-line in relation to the present moment, then a task with high criticality receives a lower priority than a task with lower criticality – this phenomena is called criticality inversion [90].
Therefore, many scheduling algorithms exist which aim to place priority on cer-tain tasks of similar criticality or allocate resources fairly. Baruah et al. [91] apply a logical weight to all tasks and use the notion of proportionate fairness for scheduling and resource allocation. Joe-Wong et al. [92] create a formula for the trade-o between fairness and e ciency based on the axiomatic theory of fairness in network resource allocation [93] with a modi er for throughput. Coluccia et al. is one example of max-min fairness being applied to resource allocation, while Je ay et al. [95] use rate-based scheduling for aperiodic tasks.

Slack and Non-Critical Tasks

As discussed in Section 3.2.2, the allotted time by a static scheduler for a task is an over-approximation of its WCET. Therefore, when a task completes earlier than its allotted time, which is determined by its WCET, the remaining time (termed slack) becomes free for the execution of other tasks [96]. Due to conservative estimations of execution times used when scheduling the system, slack can become prevalent. This fact allows for the accommodation of low criticality tasks to utilise the slack, and research has been conducted into the e cient scheduling of mixed-criticality systems [97, 98].
Su et al. [99] uses slack to meet soft deadlines. This work is further extended by Yip et al. [2] to accommodate non-critical tasks where a task is assigned one of three levels of criticality based on their timing needs: life, mission or non-critical. Life-critical tasks have no deadline-miss tolerance, mission-critical tasks have a bounded deadline-miss tolerance, and non-critical tasks have an unbounded deadline-miss tolerance as shown in Figure 3.4. Fleming et al. [100] explore the notion of task importance. Task importance is assigned to low-criticality tasks, and tasks with low criticality are discarded in reverse-order of importance.

Motivation

The research of mixed-criticality systems is usually aimed at hard deadlines and high priorities. However, when the hard deadlines of a system are met, the remain-ing tasks with soft deadlines are executed on a best-e ort basis and not necessarily re ective of a task’s needs in comparison to other non-critical tasks.
This gives rise to several limitations for non-critical tasks in mixed-criticality set-tings:
Non-critical tasks have unbounded deadline miss tolerance, but there is no intermediate goal that is to be striven for when deadline misses are bound to occur.
Non-critical tasks are either tiered in priority above one another [100] or are contending against one another with the same priority.
When non-critical deadlines cannot always be met, the system designer has limited input into how the best-e ort priorities are proportioned between non-critical tasks.
After a thorough literature review, no instance of a quanti able measure for the performance or schedulability or low-priority or non-critical tasks in mixed-criticality systems could be found. Burns [101] explores the state of the art of the eld of Mixed-Criticality Systems, and make little mention of non-critical systems, save for cases where the performance of non-critical tasks were improved [102, 103] through modi cations to memory controllers, however there is still no standard and accepted method when it comes to how a non-critical task performance is evalu-ated. The case for life and mission critical tasks is quite intuitive, that is, they are critical to the operation of a system. A non-critical task does not require the same guarantees. However, once life and mission critical tasks have been guaranteed, there is room for the prioritisation and optimisation of the execution behaviour of non-critical tasks to ensure better service to the non-critical functionality of a system.

Grade of Service of Non-Critical Tasks

In this section, the case for treating non-critical tasks as a service is given followed by a measure to quantify the Grade of Service of non-critical tasks on an individual basis.

Contents
Abstract 
Acknowledgements 
List of Figures 
List of Tables 
Abbreviations 
Co-Authorship Forms 
1 Introduction 
1.1 Fairness
1.2 Motivation
1.3 Thesis Outline
2 Fairness in Vehicular Networks 
2.1 Chapter Overview
2.2 Background
2.3 Evaluation of MAC Protocol Fairness through Network Simulators
2.4 Results
2.5 Worst Case Fairness
2.6 Discussion
3 Fairness in Processing 
3.1 Chapter Overview
3.2 Background
3.3 Grade of Service of Non-Critical Tasks
3.4 Using GoS for Dynamic Scheduling
3.5 Results
3.6 Discussion
4 Trac, Scheduling, and Fairness 
4.1 Chapter Overview
4.2 Background
4.3 A Computer Systems Approach to Trac Control
4.4 Experiment
4.5 Results
4.6 Discussion
5 Conclusions and Outlook 
5.1 Contributions
5.2 Recommendations for Future Work
GET THE COMPLETE PROJECT
From Worst-Case Gini Coe cient to Preemptive Multitasking: Consideration for Fairness and E ciency in Intelligent Transportation Systems