Real Time Task Scheduling
#1

[attachment=12530]
1). Introduction
A real time system is used when rigid time requirements have been placed on the operation of a processor or the flow of data; thus it is often used as a control device in a dedicated application.
The purpose of real time computing is to execute, by the appropriate deadlines its critical control tasks.The allocation/scheduling problem is: Given a set of tasks, task precedence constraints, resource requirements, task characteristics and deadlines we are asked to devise a feasible allocation/schedule on a given computer.
It’s an ongoing topic of research and the vast majority of assignment/scheduling problems on systems with more than two processors are NP-complete.
2). Basic Terminologies:
Task: Formally speaking a task consumes resources and puts out one or more resources. Each task has resource requirements. All tasks require some execution time on a processor. Tasks may have precedence constraints. Also a task may require a certain amount of memory or access to a bus.Sometimes, a resource must be exclusively held by a task. (i.e. the task must have the sole possession of it).In other cases the resources are non exclusive. The same physical resource may be exclusive or nonexclusive depending on the operation to be performed on it. For instance memory object (or anything else to which the writing is not atomic) that is being read is nonexclusive. However while it is being written into, it must be held exclusively by the writing task.
The release time of a task is the time at which all the data that are required to begin executing are available, and the deadline is the time by which the task must complete its execution .The deadline may be hard or soft depending on the nature of the corresponding task .
The relative deadline of a task is the absolute deadline minus the release time. That is, if task Ti a relative deadline di and is released at time t, it must be executed by time t+di .The absolute deadline is the time by which the task must be completed.So, in this case the absolute deadline is t+di .
Types of Tasks: A task may be periodic, sporadic or aperiodic.
• Periodic Task: A task Ti is periodic if it is released periodically, say every Pi seconds. Pi is called the period of task Ti. The periodicity constraint requires the task to run exactly once every period; it does not require that the tasks be run exactly one period apart. Quite commonly the period of a task is also it’s deadline.
• Sporadic Task: The task is sporadic if it is not periodic but may be invoked at irregular intervals. Sporadic tasks are characterized by an upper bound on the rate at which they may be invoked. This is commonly specified by requiring that the successive invocations of a sporadic task Ti be separated in time by at least t(i) seconds.
• Aperiodic Tasks: Sporadic tasks are sometimes also called aperiodic.Sometimes aperiodic tasks are supposed to be those tasks which are not periodic and which also have no upper bound on their invocation rate.
3) Fixed Priority Scheduling – A Simple Model :
Consider a simple, real-time program which periodically receives inputs from a device every T units of time, computes a result and sends it to another device. Assume that there is a deadline of D time units between th arrival of an input and the dispatch of the corresponding output.
For the program to meet this deadline, the computation of the result must take always place in less than D time units: in other words, for every possible execution path through the program, the time taken for the execution of the section of code between the input and output statements must be less than D time units.
If that section of the program consists solely of assignment statements, it would be possible to obtain a very accurate estimate of its execution time as there will be just one path between the statements. In general, however, a program will have a control structure with several possible execution paths.
For example, consider the following structured if statement:
1 Sensor_Input.Read(Reading);
2 if Reading = 5 then Sensor_Output.Write(20)
3 elseif Reading < 10 then Sensor_Output.Write(25)
4 else ...
5 Sensor_Output.Write( ...)
6 end if;
There are a number of possible execution paths through this statement: e.g. there is one path through lines 1, 2 and 6 and another through lines 1, 2, 3 and 6. Paths will generally differ in the number of boolean tests and assignment statements executed and so, on most computers, will take different execution times.
In some cases, as in the previous example, the execution time of each path can be computed statically, possibly even by a compiler. But there are statements where this is not possible:
Sensor_Input.Read(Reading);
while X > Reading + Y loop
...
end
Finding all the possible paths through this statement may not be easy: even if it is known that there are m different paths for any one iteration of this while loop, the actual number of iterations will depend on the input value in Reading. But if the range of possible input values is known, it may then be possible to find the total number of paths through the loop. Since we are concerned with real-time programs, let us assume that the program has been constructed so that all such loops will terminate and therefore that the
Number of paths is finite.
So, after a simple examination of alternative and iterative statements, we can conclude that:
• It is not possible to know in advance exactly how long a program execution will take, but
• It may be possible to find the range of possible values of the execution time.
Rather than deal with all possible execution times, one solution is to use just the longest possible, or worst-case, execution time for the program. If the program will meet its deadline for this worst-case execution, it will meet the deadline for any execution.
Worst-case
Assume that the worst-case upper bound to the execution time can be computed for any real-time program.
Computational model
We can now redefine the simple real-time program as follows: program P receives an event from a sensor every T units of time (i.e. the inter-arrival time is T) and in the worst case an event requires C units of computation time (Figure 2.1).
Assume that the processing of each event must always be completed before the arrival of the next event (i.e. there is no buffering). Let the deadline for completing the computation be D (Figure 2.2).
If D < C, the deadline cannot be met. If T < D, the program must still process each event in a time <T if no events are to be lost. Thus the deadline is effectively bounded by T and we need to handle only those cases where
C <D < T.
Now consider a program which receives events from two sensors (Figure 2.3). Inputs from Sensor 1 come every T1 time units and each needs C1 time units for computation; events from Sensor 2 come every T2 time units and each needs C2 time units. Assume the deadlines are the same as the periods, i.e. T1 time units for Sensor 1 and T2 time units for Sensor 2. Under what conditions will these deadlines be met?
More generally, if a program receives events from n such devices, how can it be determined if the deadline for each device will be satisfied? Before we begin to analyze this problem, we first define a program model and a system
model. This allows us to study the problem of timing analysis in a limited context.
Program model
Assume that a real-time program consists of a number of independent tasks that do not share data or communicate with each other. A task is periodically invoked by the occurrence of a particular event.
System model
Assume that the system has one processor; the system periodically receives events from the external environment and these are not buffered. Each event is an invocation for a particular task. Note that events may be periodically produced by the environment or the system may have a timer that periodically creates the events.
Let the tasks of program P be 1, 2,….. n.
Let the inter-arrival time, or period, for invocations to task i be Ti and let the computation time for each such invocation be Ci.
We shall use the following terminology:
• A task is released when it has a waiting invocation.
• A task is ready as long as the processing associated with an invocation has not been completed.
• A processor is idle when it is not executing a task.
Static scheduling
One way to schedule the program is to analyze its tasks statically and determine their timing properties. These times can be used to create a fixed scheduling table according to which tasks will be despatched for execution at run-time. Thus, the order of execution of tasks is fixed and it is assumed that their execution times are also fixed.
Typically, if tasks 1, 2,….., n have periods of T1, T2,….., Tn, the table must cover scheduling for a length of time equal to the least common multiple of the periods, i.e. LCM({T1, T2,…..., Tn}), as that is the time in which each task will have an integral number of invocations. If any of the Ti are co-primes, this length of time can be extremely large so where possible it is advisable to choose values of Ti that are small multiples of a common value.

Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: java code for task scheduling problem using genetic algorithm, online task management system in pdf, genetic algorithm task scheduling source code, er diagram of task management system, client profile task, time scheduling software, task management system project report free download,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
Question Space-time Adaptive Processing (STAP) computer science crazy 2 3,146 16-10-2013, 03:09 PM
Last Post: Guest
  RTX51 Real-time Operating System project report helper 1 2,269 24-11-2012, 03:59 PM
Last Post: RAGHAVENDRA K S
  Real Time Systems with Linux/RTAI computer science crazy 1 2,922 01-11-2012, 02:25 PM
Last Post: seminar details
  RTOS - Real Time Operating Systems full report project report tiger 6 11,832 22-10-2012, 01:54 PM
Last Post: seminar details
  Satellite Image Time Series Analysis Under Time Warping computer girl 0 383 06-06-2012, 05:23 PM
Last Post: computer girl
  Conflict-free scheduling and routing of automated guided vehicles in mesh topologies computer girl 0 829 05-06-2012, 12:52 PM
Last Post: computer girl
  Minimizing File Download Time in Stochastic peer-to-peer networks electronics seminars 7 7,285 15-03-2012, 12:32 PM
Last Post: seminar paper
  REAL TIME OPERATING SYSTEM computer science crazy 1 2,221 25-02-2012, 10:29 AM
Last Post: seminar paper
  Real-Time Operating Systems project report helper 1 1,447 25-02-2012, 10:29 AM
Last Post: seminar paper
  Real time operating systems ajukrishnan 1 3,182 25-02-2012, 10:28 AM
Last Post: seminar paper

Forum Jump: