Functional Parameters

FUNCTIONAL PARAMETERS

While scheduling and resource access control decisions are made disregarding most functional characteristics of jobs, several functional properties can affect these decisions. The workload model must explicitly describe these relevant properties which is done by the values of functional parameters.

These includes:

1. Preemptivity of jobs,
2. Criticality of jobs,
3. Optional execution, and
4. Laxity type and laxity function.

Preemptivity of Jobs

Preemptivity of jobs means whether a currently executing job can be momentarily stopped and a new job having hyper priority can be executed or not. One of the higher priority job completes execution, the preemptive jobs resumes execution. During this process, currently executing job is stored in the memory and the job with higher priority is brought into the processor. This process is called context switch and the time required to perform context switch is called switching time.

Criticality of Jobs

All the jobs may not be equally important. The importance (criticality) of a job is represented by a positive number that indicates how critical the job is with respect to other jobs. The more critical the jobs, the larger its importance. Priority and weight are used to indicate the importance. The more important a job, the higher it’s priority or the larger its weight.

During overload, less critical jobs are sacrificed so that critical jobs meet their deadline. Therefore, weighted performance measures such as weighted average response time or weighted average tardiness is used and optimized by scheduling and resource control algorithms.

Optional Execution

Optional means not mandatory. Therefore, optional job or optional portion of a job can be discarded even when executing. But the not optional or mandatory jobs must be executed to completion. The optional jobs are not critical and can be sacrificed to stop system degradation. If an optional job completes late or is not executed at all, the system performance may degrade but functions satisfactorily.

Laxity Type and Laxity Function

Laxity type of a job means whether its timing constraints are hard or soft. Laxity type is supplemented by a usefulness function. This function gives the usefulness of the result produced by the job as a function of its tardiness. The tardiness is the difference between the completion time and deadline of the job.

In the graph, the dark lines are called hard real time jobs. In this case, the result becomes zero or negative as soon as the job is tardy. Therefore, in the second case, it is better not to execute the job for example release of bomb by a fighter plane.

In the graph, the dotted lines shows that the usefulness decreases gradually and becomes zero. For example, withdrawing money from ATM machines.

The dashed line is a function that decreases faster and becomes negative. Such cases can occur while obtaining the stock price.

The usefulness function is used to describe qualitatively the real time performance objective of the system. It can be helpful while choosing and implementing scheduling strategies. The usefulness means to specify the timing constraints for hard real time system and it should be small.

Resource Parameter of Jobs and Parameter of Resources

Resource parameter gives the resource requirements. Basic component available for an application are processors and resources. Processor is required throughout its execution. Similarly, it requires other resources. The resource parameter of a job gives the type of processor, the unit of each resource type required and the time intervals during its execution when the units are required. The information provided by resource parameter is used to support the resource management decision.

Preemptivity of resource

Resource parameters are used to view the processors and the resources from the perspective of the applications that execute on them. One of the resource parameters is preemptivity. A resource is non-preemptable if each unit of the resource is constrained to be used serially. Once a unit of resource is allocated to a job, other jobs needing it must wait until the job completes its use.

If a job can use every unit of resource in a interleaved fashion, the resource is called preemptable. For example, the lock in a database and token ring are non-preemptable, and sending message using ATM is preemptable.

Resource Graph

A graph that is used to describe the configuration of the resources is called resource graph. It gives the amount of resources available to execute the application, attribute of resources and rules governing their usage. In a resource graph, there is a vertex R_i, for every processor or resource R_i in the system. The attributes of the vertex are the parameters of the resource. The resource type of the resource gives whether the resource is a processor or (passive) resource, and its number gives the number of available units. Edges in a resource graph represent the relationship among resources. Different types of edges are used to describe different configuration of the system.

There are two types of edges. An edge from vertex R_i to R_k means R_k is a component of R_i. This edge is called is-a-port-of-edges. Subgraph containing all the is-a-part-of-edges is a major component which contains sub-components represented by vertices in the tree.

The edges that represent connectivity between components are called accessibility edges. E.g. if there is a connection between two CPUs in two computers, then each CPU is accessible from other computer and there is an accessibility edge from each component to CPU on other computer as shown in model of RTS in above figure. Each accessibility edge may have several parameters whose value help to complete the description of interconnection of the resources. E.g. cost of sending a unit of data from a job executing on Pi to a job executing on P_k can be represented by a parameter of an accessibility edge from P_i to P_k.

Scheduling hierarchy, Scheduler and Schedule

Jobs are scheduled and allocated resources according to a chosen set of scheduling algorithms and resource access control protocols. The scheduler is a module that implements these algorithms. It specifically assigns jobs to processors. The total amount of time assigned to a schedule is the total length of all the time intervals during which the job is scheduled on a processor. A schedule is an assignment of all jobs in the system on the available processors.

The task graph at the top, resource graph at the bottom and in between them scheduling algorithm and resource access control protocol used by an operating system is called scheduling algorithm. Therefore, it gives information about the precedence constraints. Functional and resource parameters of a job, and interdependence of processors as shown in the figure below.

If a scheduler produces only valid schedules then it is called correctness of a schedule. A valid schedule is the one that satisfies the following conditions.

• Every processor is assigned at most one job at any time.
• Every job is assigned at most one processor at any time.
• No job is scheduled before its release time.
• The total amount of processor time assigned to every job is equal to its maximum or actual execution time.
• All the precedence and resource usage constraints are satisfied.

The assumptions here is that jobs do not run in parallel on more than one processor to speed up their execution.

Feasibility, Optimality and Performance measures of Scheduling

A valid schedule is also a feasible schedule if every job meets its timing constraints or completes by its deadline. A job is a schedulable according to a scheduling algorithm, if the scheduler always produces a feasible schedule.

Miss Rate: The percentage of jobs that are executed but completed too late.

Loss Rate: The percentage of jobs that are not executed at all or discarded.

Loss rate cab be minimized provided the miss rate is below some threshold. A performance measure that captures this tradeoff is called invalid rate. It is sum of the miss rate and loss rate and gives percentage of all the jobs that do not produce a useful record. It should be as minimal as possible in order to make the soft real time system optimal.

A hard real time system is optimal if the algorithm always produces a feasible schedule when the given set of jobs has feasible schedule. If an optimal algorithm fails to find a feasible schedule then the given sets of jobs can’t feasibly be scheduled by any algorithm.

The other performance measures are maximum and average tardiness, response time, miss/loss and invalid rates.

Lateness of job is the difference between its completion time and its deadline. It is negative if the job completes early, positive if completes late. The tardiness can never be negative though it is also a difference between its completion time and its deadline. To keep jitters in completion time small, use scheduling algorithms which minimizes the average absolute lateness of jobs.

Scheduling jobs with same release time and deadline means scheduling to minimize the completion time of the job which completes last among all the jobs. The response time of this job is the response time of the set of jobs as a whole and is often called makespan of the schedule. Makespan is used to compare scheduling algorithms and the algorithm with shorter makespan is better. If the makespan is less than or equal to the length of their feasible interval, the job can meet their deadline.

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.