Print Email Download Reference This Send to Kindle Reddit This
submit to reddit

Non Preemption Scheduling Of Periodic Computer Science Essay

Many papers have been published in the field of real-time scheduling; these include surveys of published literature. Unfortunately much of the published work consists of scheduling algorithms that are defined for systems that are extremely constrained and consequently of limited use for real applications.

We exhibit a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. We then show that any set of periodic or sporadic tasks that satisfies conditions C can be scheduled with an earliest deadline first (EDF) scheduling algorithm.

We also address the question of schedulability of a set of tasks with specified release times. For sets of sporadic tasks with specified release times, we show that the conditions C are again necessary and sufficient for schedulability. However, for sets of periodic tasks with specified release times, the conditions C, while sufficient, are not necessary. In fact, we show that determining whether a set of periodic tasks with specified release times is schedulable is intractable (i.e., NP-hard in the strong sense). Moreover, we show that the existence of a universal algorithm for scheduling periodic tasks with specified release times would imply that P = NP.

This paper examines a fundamental problem in the theory of real-time scheduling, that of scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time.

1. INTRODUCTION:

Many industrial applications with real-time demands are composed of mixed sets of tasks with a variety of requirements. Different classes of scheduling algorithm used in real-time systems:[1]

Clock-driven

– Primarily used for hard real-time systems where all properties of all jobs are known at design time, such that offline scheduling techniques can be used

Weighted round-robin

– Primarily used for scheduling real-time traffic in high-speed, switched networks

Priority-driven

– Primarily used for more dynamic real-time systems with a mix of time based

and event-based activities, where the system must adapt to changing conditions and events.

The priority driven scheduling can be in the form of standard timing constraints, such as period and deadline, to express application specific or non temporal constraints, reliability, performance, etc. Arrival patterns determine whether tasks will be treated as periodic or sporadic task [2].

The concept of a task that is invoked repeatedly is central to both the design and analysis of real-time systems. In particular, formal studies of real-time systems frequently represent the time-constrained processing requirements of the system as a set of periodic or sporadic tasks with deadlines [3]. A periodic task is invoked at regular intervals, while a sporadic task is invoked at arbitrary times but with a specified minimum time interval between invocations. Sporadic tasks are equivalent to synchronous periodic task sets. For them, the worst case is when they all arrive at their maximum frequency and starting synchronously [4].

In this paper we consider a fundamental real-time scheduling problem, that of non-preemptive scheduling of a set of periodic or sporadic tasks on a uniprocessor. We will also demonstrate on the efficient use of the Earliest Dead Line First algorithm.

2. RELATED WORK:

Previous work in the area of real-time scheduling has mainly focused on the analysis of preemptive scheduling algorithms. A well-known result is that the preemptive EDF algorithm is universal for all sets of concrete periodic tasks for which the release times are all 0. This result generalizes to all periodic task sets (i.e., for concrete periodic tasks with arbitrary release times) . The extension of the preemptive problem to multiprocessors was considered in and work with non-preemptive scheduling algorithms[5] has typically been confined to consideration of models where processes are invoked only once, there is a recedence order between the processes, and each process requires only a single unit of computation time and must be completed before a deadline.

EDF is an optimal algorithm for single processors. The most important (and analyzed) dynamic priority algorithm is Earliest Deadline First (EDF). The priority of a job (instance) is inversely proportional to its absolute deadline; In other words, the highest priority job is the one with the earliest deadline; If two tasks have the same absolute deadlines, chose one of the two at random (ties can be broken arbitrary). The priority is dynamic since it changes for different jobs of the same task.

Non-preemptive scheduling algorithms are easier to implement than preemptive algorithms, and can exhibit dramatically lower overhead at run-time. Non-preemptive scheduling on a uni-processor naturally guarantees exclusive access to shared resources and data, thus eliminating both the need for synchronization and its associated overhead.

3. ANALYSIS OF PROBLEM:

3.1. Deadline Characteristics

In the development of application programs it is usual to map system timing requirements onto process deadlines. The issue of meeting deadlines therefore becomes one of process scheduling, with two distinct forms of process structure being immediately isolated:

(a) Periodic Processes

(b) Sporadic Processes

Periodic processes, as their name implies, execute on a regular basis; they are characterized by:

(i) their period;

(ii) their required execution time (per period).

The execution time may be given in terms of an average measurement and (or) a worst case execution time. For example a periodic process may need to execute every second using, on average, 100ms of CPU time; this may rise to 300ms in extreme instances.

The activation of an sporadic process is, essentially, a random event and is usually triggered by an action external to the system. Sporadic processes also have timing constraints associated with them; i.e. having started execution they must complete within a predefined time period. Often these processes deal with critical events in the system’s environment and hence their deadlines are particularly important.

The maximum response time of a process is termed the deadline. Between the invocation of a process and its deadline, the process requires a certain amount of computation time to complete its execution. Computation times may be static, or vary within a given maximum and minimum (which may be infinity and arbitrarily close to zero). The computation time (which excludes contention between processes) must not be greater than the time between the invocation and deadline of a process. Hence, the following relationship should hold for all processes:

C D

Where,

C - computation time

D - deadline

For each periodic processes, its period must be at least equal to its deadline. That is, one invocation of a process is complete before successive invocations. This is termed a runnability constraint. Hence, for periodic processes, the following relationship holds:

C D T

Where,

T - period of the process

Non-periodic processes can be invoked at any time.

3.2 Why non-preemptive?

Non-preemptive scheduling is more efficient than preemptive scheduling since preemption incurs context switching overhead which can be significant in fine-grained multithreading systems. There are various basic Real-Time Scheduling, First Come First Served (FCFS) is the simple “first in first out” queue , long average waiting time , negative for I/O bound processes , nonpreemptive. The Round Robin (RR) is the scheduling algorithm having the property first come first served with preemption and some time quantum. The performance (i.e. average waiting time)of Round Robin is proportional to the size of the time quantum. The next scheduling algorithm is Shortest Job First (SJF) which is optimal with respect to average waiting time. Shortest job first also requires profiling of the execution times of tasks.

3.3 Task Scheduling:

This section discusses scheduling algorithms employed in real-time operating systems. We note that predictability requires bounded operating system primitives. A feasibility analysis of the schedule may be possible in some instances. Task scheduling can be either performed preemptively or nonpreemptively and either statically or dynamically. For small applications, task execution times can be estimated prior to execution and the preliminary task schedules statically determined. Typical parameters associated with tasks are:

• Average execution time

• Worst case execution time

• Dispatch costs

• Arrival time

• Period (for periodic tasks).

The objective of scheduling is to minimize or maximize certain objectives. Typical objectives minimized are: schedule-length and average tardiness or laxity. Alternatively, maximizing average earliness and number of arrivals that meet deadlines can be objectives. Scheduling approaches have been classified into: static table driven approach, static priority driven preemptive approach, dynamic planning based approach, dynamic best effort approach, scheduling with fault tolerance and resource reclaiming.

3.4 Scheduler Characteristics

A scheduler provides an algorithm or policy for ordering the execution of the outstanding processes on the processor according to some pre-defined criteria. Scheduling algorithms themselves can be characterized as being either static or dynamic. A static approach calculates (or pre-determines) schedules for the system. It requires prior knowledge of a process’s characteristics but requires little run-time overhead. By comparison a dynamic method determines schedules at run-time thereby furnishing a more flexible system that can deal with non-predicted events. It has higher run-time cost but can give greater processor utilization.

As a basis for discussing scheduling a system model is required. A common model in the literature is given as follows.

A process set T has elements {1...i...n} where n is the cardinality of T. Each i has the following characteristics.

Di - deadline

Pi - period

Ci - computation time

The first and the most effectively widely used dynamic priority-driven scheduling algorithm is the Earliest Deadline First. An important class of scheduling algorithms is the class of dynamic priority algorithms. In dynamic priority algorithms, the priority of a task can change during its execution .Fixed priority algorithms are a sub-class of the more general class of dynamic priority algorithms: the priority of a task does not change. The most important (and analyzed) dynamic priority algorithm is Earliest Deadline First (EDF) The priority of a job (istance) is inversely proportional to its absolute deadline; In other words, the highest priority job is the one with the earliest deadline; If two tasks have the same absolute deadlines, chose one of the two at random (ties can be broken arbitrarly).The priority is dynamic since it changes for different jobs of the same task.

3.5 Dynamic Online Scheduling

The alternative to making all scheduling decisions offline is to make them as the system is running. EDF dynamic online scheduling algorithms are now discussed.

Earliest Deadline First (EDF):

The EDF is effective for both preemptive and non-preemptive scheduling periodic, and sporadic tasks. The non-preemptive EDF is optimal for sporadic non-preemptive tasks. Scheduling periodic and sporadic non-preemptive tasks is NP-hard Approach near optimal for non-preemptive scheduling on a uniprocessor system. Earliest Deadline First (EDF) or Least Time to Go is a dynamic scheduling algorithm used in real-time operating systems. It places processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.

However, when the system is overloaded, the set of processes that will miss deadlines is largely unpredictable (it will be a function of the exact deadlines and time at which the overload occurs.) This is a considerable disadvantage to a real time systems designer. The algorithm is also difficult to implement in hardware and there is a tricky issue of representing deadlines in different ranges (deadlines must be rounded to finite amounts, typically a few bytes at most). Therefore EDF is not commonly found in industrial real-time computer systems.

Instead, most real-time computer systems use fixed priority scheduling (usually rate-monotonic scheduling). With fixed priorities, it is easy to predict that overload conditions will cause the low-priority processes to miss deadlines, while the highest-priority process will still meet its deadline. There is a significant body of research dealing with EDF scheduling in real-time computing; it is possible to calculate worst case response times of processes in EDF, to deal with other types of processes than periodic processes and to use servers to regulate overloads.

4. IMPLICATION:

EDF is an optimal scheduling algorithm on preemptive uniprocessors, in the following sense: if a collection of independent jobs, each characterized by an arrival time, an execution requirement, and a deadline, can be scheduled (by any algorithm) such that all the jobs complete by their deadlines, the EDF will schedule this collection of jobs such that they all complete by their deadlines.

With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. Thus, the schedulability test for EDF is:

where the are the worst-case computation-times of the n processes and the are their respective inter-arrival periods (assumed to be equal to the relative deadlines).

That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. So, compared to fixed priority scheduling techniques like rate-monotonic scheduling, EDF can guarantee all the deadlines in the system at higher loading with nonpreemptive scheduling.

There is not need to define priorities. Remember that in FP, in case of offsets, there is not an optimal priority assignment that is valid for all task sets. In general, EDF has less context switches. In the previous example, you can try to count the number of context switches in the first interval of time: in particular, at time 4 there is no context switch in EDF, while there is one in FP. Optimality of EDF. We can fully utilize the processor, less idle times.

The algorithm used for scheduling is: the process with the (current) closest deadline is assigned the highest priority in the system and therefore executes. The schedulability constraint is given thus:

Hence, 100% processor utilisation is possible. This is a sufficient and necessary condition for schedulability.

"the deadline driven scheduling algorithm is optimum in the sense that if a set of processes can be scheduled by any algorithm, it can be scheduled by the deadline driven algorithm."

Throughout this paper we assume time is discrete and clock ticks are indexed by the natural numbers. Task invocations occur and task executions begin at clock ticks; each of the parameters C and P is expressed as a multiple of (the interval between) clock ticks. We show that periodic and sporadic task sets have the same requirements for schedulability. Having identified necessary conditions for schedulability, we then exhibit an algorithm which schedules any set of periodic or sporadic tasks that satisfy the necessity conditions. We propose to implementation and analysis of EDF algorithm for task scheduling.

4.1 Schedulability bound with EDF:

Given a task set of periodic or sporadic tasks, with relative deadlines equal to periods, the task set is schedulable by EDF if and only if,

EDF is an optimal algorithm, in the sense that if a task set if schedulable, then it is schedulable by EDF. In fact, if U > 1 no algorithm can successfully schedule the task set;

if U _ 1, then the task set is schedulable by EDF (and maybe by other algorithms). In particular, EDF can schedule all task sets that can be scheduled by FP, but not vice versa.

5. APPLICATION:

Digital control systems periodically performs the following job:

senses the system status and

actuates the system according to its current status

Multimedia applications periodically performs the following job:

reads, decompresses, and displays video and audio streams

In practice, periodic tasks are commonly found in applications such as avionics and process control when accurate control requires continual sampling and processing of data.

Periodic and sporadic tasks were used, for example, to represent the timing constraints in an interactive 3-dimensional graphics display system used for research in virtual worlds.

6. SUMMARY:

Non-preemptive scheduling problems arise in many forms in concurrent and real-time systems. Moreover, as nonpreemptive schedulers are easier to implement and analyze, it is important to understand the requirements of scheduling tasks nonpreemptively. In this project we will examined the problem of scheduling a set of periodic or sporadic tasks without preemption on a uniprocessor. The earliest deadline first algorithm is universal for sets of sporadic and periodic tasks.. The universality is with respect to the class of scheduling algorithms that do not use inserted idle time. Unless P =NP, there does not exist a universal non-preemptive scheduling algorithm for periodic tasks. Given a set of sporadic, periodic, one can efficiently determine if the tasks will be schedulable.

Print Email Download Reference This Send to Kindle Reddit This

Share This Essay

To share this essay on Reddit, Facebook, Twitter, or Google+ just click on the buttons below:

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays