Real-Time Systems

Check out more papers on Computer Engineering
Contents

Software Metrics for the Design of Real-Time Systems

ABSTRACT

Real-time systems are vital systems. All systems are special cases of Real-Time Systems. Real-Time Design Metrics are challenging, central components of high quality and patterned real-time systems' engineering field. The design phase is the most influential phases of the lifecycle. Research done in this phase of the lifecycle enables quick troubleshooting and is also cheaper (as the real-time software isn't coded at this stage). This thesis presents a proposal of metrics for Real-Time Systems' Design Phase. The eight metrics that have been proposed are: Flow Control Metric, Trend of WCET Metric, Basic Cycle Time Metric, RTA Structure Metric, Message Activation Rate Metric, Task Activation Metric and Upper Bound Metric. These metrics have been analyzed for change in values and the corresponding trends have been presented. Also this thesis has catered more to the non-functional requirements of RTS. The ones that have been taken into consideration particularly are: Fault Tolerance, Performability, Timeliness, Quality, Performance, Efficiency and Predictibility.

PREFACE

This thesis is the final work of my Master's study at the Department of Computer Science and Engineering, University of Engineering and Technology, Lahore. It serves as a documentation of my work during the study, which has been made during my Master's study.

This piece of writing consists of 8 chapters: Introduction, Literature Survey, Problem Statement, Proposed Solution, References, Results and Discussions, Conclusion, Future Recommendations and References. The titles of each chapter are self-explanatory and give insight into their contents.

The motivation to write in this active area of research stems from the fact that the design phase of any project is its most vital and wide-spread phase. If the problem can be diagnosed, removed and re-evaluated at the design phase itself, then the cost of production of the projects falls drastically. To aid in this problem prognosis, we have employed the knowledge of metrics. Moreover, every system is a special case of Real-Time Systems, so research done in the field of Real-Time Systems indirectly caters to a wide range of audience.

As Robert Frost rightly said, ‘The artist in me cries out for design.'

We have also built up our research from the knowledge of other people who have already worked in this area for a long time. As Socrates advised, ‘Employ your time in improving yourself by other men's writings so that you shall come easily by what others have labored hard for.'

CHAPTER ONE
1. INTRODUCTION
1.1 Overview

Real-Time Systems have been widely employed in today's world. We encounter them subconsciously and like all other computer applications, they do make our life easier also. What makes these systems differ from other systems is the time constraint-RTS (Real-Time Systems) are time-bound. In other words a ‘late' answer is a wrong answer. This doesn't apply that these systems are ‘always' expected to be super-fast. They simply have to match the timing constraints that have been specified in the design phase. More insight about this interesting behavior is presented in the next chapter.

1.2 Motivation

What made us get attracted to this active area of research is that every system, if studied closely, is a loosely-constrained version of a Real-Time System. So research done in this area can be helpful to all systems under software engineering. Moreover, the design phase was chosen to be researched upon. We saw a lack of substantial research done in this area and we saw the need for improvement. Thus this thesis makes an attempt to devise meaningful metrics pertaining to the design phase of Real-Time Systems. The focus will mainly be on looking out for the non-functional requirements of Real-Time Systems.

1.3 Contribution

We have attempted to devise meaningful metrics by carrying out extensive research on the available literature pertaining to the design phase of Real-Time Systems. These metrics will then be analyzed with different values and then the changing trends in these metrics will be noticed.

1.4 Organization of Thesis

The rest of the thesis is organized in the form of eight chapters. Chapter 1 is about the Introduction.

Chapter 2 pertains to Literature Survey.

Chapter 3 describes the Problem Statement of our study.

Chapter 4 lays out the Proposed Solution.

Chapter 5 gives insight about the Results and Discussions.

Chapter 6 gives the Conclusion.

Chapter 7 gives the Future Recommendations.

Chapter 8 enlists the References.

CHAPTER TWO

2. lITERATURE SURVEY

A real-time application (RTA) is an application program that functions within a time frame that the user senses as immediate or current. The latency must be less than a defined value, usually measured in seconds. Whether or not a given application qualifies as an RTA depends on the worst-case execution time (WCET), the maximum length of time a defined task or set of tasks requires on a given hardware platform [1]. The use of RTAs is called real-time computing (RTC) [2]. Real-time software systems contain computations that depend not only on how they are done but also when they are done. Increasing software systems' complexity makes it difficult to ensure the application will complete tasks correctly and on-time. This proves to be an added responsibility.

A metric is a measure of some property of an entity. You cannot control anything unless you measure it. The objective of this thesis is to discuss the design metrics for the software phase of real time applications.

A real-time system is one in which the correctness of the computations not only depends on their logical correctness, but also on the time at which the result is produced. In other words, a late answer is a wrong answer.

As an example of a real-time system, consider a computer-controlled machine on the production line at a bottling plant. The machine's function is simply to cap each bottle as it passes within the machine's field of motion on a continuously moving conveyor belt. If the machine operates too quickly, the bottle won't be there yet. If the machine operates too slowly, the bottle will be too far along for the machine to reach it. Stopping the conveyor belt is a costly operation, because the entire production line must correspondingly be stopped. Therefore, the range of motion of the machine coupled with the speed of the conveyor belt establishes a window of opportunity for the machine to put the cap on the bottle.

2.1 Specific Features of Real-Time Systems

The major characteristics of real-time systems include the following [6] :

Timeliness is important. The system performs its functions within the specified time-limit.

It ought to be reactive. The system continuously responds to events from the external environment that drives the “execution” of the system.

The concurrent execution of threads of control is vital, where different parts of the software run in parallel.

It usually has very high requirements on most of the non functional requirements, such as reliability, fault tolerance and performance.

It ought to be non deterministic.

It also ought to be deadline-driven.

2.2 Period VS Deadline

A window of opportunity imposes timing constraints on the operation of the machine. Applications with these kinds of timing constraints are considered real time. In this case, the timing constraints are in the form of a period and deadline.

The period is the amount of time between each iteration of a regularly repeated task. Such repeated tasks are called periodic tasks.

Suppose bottles pass under the machine at a rate of five per second. This means a new bottle shows up every 200ms. Thus, the period of the task is 200ms. Note that whether bottles pass once per second or 100 times per second, it doesn't change the fact that this is a real-time system. Real time does not mean fast; it means that a system has timing constraints that must be met to avoid failure.

The deadline is a constraint on the latest time at which the operation must complete. Suppose the window of opportunity is 150ms. The deadline is then 150ms after the start time of the operation. In our example, the start time is defined as the moment the bottle enters the range of the machine. This bottle example has physical constraints, namely the speed of the conveyor belt and the machine's range of motion, that dictate the period and deadline of the task.

In many real-time systems, the period is a design parameter. Consider a cruise control mechanism on an automobile. The basic operation of cruise control is to keep the speed of the vehicle constant. Suppose the driver selects 60mph as the desired speed. If the vehicle is going slower than 60mph, then the embedded computer sends a signal to the engine controller to accelerate. If the vehicle is going faster than 60mph, it sends a signal to decelerate. A question to ask is: how often does the computer check if the current speed is too slow or too fast? The answer is called the control rate (or frequency). It is defined by the control system designer, who will try to find a rate that is fast enough to meet specifications, but not so fast that it adds unnecessary cost to the system. The period is then the reciprocal of the rate (that is, period = 1/rate). The deadline is typically the beginning of the next cycle of a periodic task, because, to start the new cycle, it needs to be finished with the old one.

Communication systems also have real-time constraints. Suppose a multimedia application needs to compress video data at a rate of 30 frames per second. Before it processes a new frame, it needs to finish processing the old frame, otherwise data might get lost in the form of dropped frames. The period of such a task is the frame rate. Processing the old frame must complete before processing on the new frame can begin. Therefore, the deadline is the beginning of the next frame. [7]

2.3 Aperiodic Tasks

Not all real-time tasks are periodic. Aperiodic tasks, also called aperiodic servers, respond to randomly arriving events. Consider anti-lock braking. If the driver presses the brake pedal, the car must respond very quickly. The response time is the time between the moment the brake pedal is pressed, and the moment the anti-lock braking software actuates the brakes. If the response time was one second, an accident might occur. So the fastest possible response is desired. But, like the cruise control algorithm, fastest is not necessarily best, because it is also desirable to keep the cost of parts down by using small microcontrollers. What is important is for the application requirements to specify a worst-case response time. The hardware and software is then designed to meet those specifications.

Note that many aperiodic tasks can be converted to periodic tasks. This is basically the same transformation as converting an interrupt handler to a polling task. Instead of reacting to an external event the moment it occurs, the software polls the external input regularly, perhaps tens or hundreds of times per second. If the awaited event is detected, the appropriated computation is carried out.

2.4 Hard or Soft?

A real-time system can be classified as either hard or soft. The distinction, however, is somewhat fuzzy. As illustrated in 1, the meaning of real-time spans a spectrum. At one end of the spectrum is non-real-time, where there are no important deadlines (meaning all deadlines can be missed). The other end is hard real-time, where no deadlines can be missed. Every application falls somewhere between the two endpoints.

A hard real-time system is one in which one or more activities must never miss a deadline or timing constraint, otherwise the system fails. Failure includes damage to the equipment, major loss in revenues, or even injury or death to users of the system. One example of a hard real-time system is a flight controller. If action in response to new events is not taken within the allotted time, it could lead to an unstable aircraft, which could, in turn, lead to a crash; by no standard is this acceptable.

In contrast, a soft real-time system is one that has timing requirements, but occasionally missing them has negligible effects, as application requirements as a whole continue to be met. Consider again the cruise control application. Suppose the software fails to measure current velocity in time for the control algorithm to use it. The control algorithm can still use the old value, because the amount that the velocity would have changed between the last sample and this sample is so small that it can still operate correctly. Missing several consecutive samples, on the other hand, could be a problem, as the cruise control would likely stop meeting application requirements because it is not able to maintain the desired speed within a proper error tolerance [6].

2.5 Predictable VS Deterministic

Two more terms often used to describe real-time systems are predictable and deterministic. These terms are related, but because they are often interchanged or used improperly (as compared to their official definition in real-time systems theory), they are often a source of confusion.

Real-time systems researchers generally use the term predictable to refer to a system whose timing behavior is always within an acceptable range. The behavior is specified on a system-wide basis, such as “all tasks will meet all deadlines.” Generally, the period, deadline, and worst-case execution time of each task need to be known to create a predictable system. An appropriate scheduling algorithm with a corresponding schedulability analysis is used to ensure a system is predictable.

A deterministic system is a special case of a predictable system. Not only is the timing behavior within a certain range, but that timing behavior can be pre-determined. For example, a system can be designed with pre-allocated time slots for each task. Execution for each task occurs only during those time slots. Such a system must have execution time for every task known, as well as no anomalies that might cause deviation from the pre-determined behavior. That is, of course, difficult to achieve. Fortunately, determinism is not essential to build predictable real-time systems.

2.5 Time-triggered VS Event-triggered

There are two fundamentally different principles that determine the activation of tasks in a real-time system, event-triggered and time-triggered. In event-triggered systems, all activities are activated in reaction to relevant events external to the system. When a significant event in the outside world happens, it is detected by some sensor, which then causes the attached device (processor) to get an interrupt signal. For soft real-time systems with lots of computing power to spare, this approach is simple, and works well. The main problem with event-triggered systems is that they fail under heavy load conditions, i.e., when many events are happening at once. Event-triggered designs give a faster response at low load but more overhead and chance of failure at high load. This approach is more suitable for dynamic environments, where dynamic activities can arrive at any time.

In a time-triggered system, all activities are activated at certain points in time that are known as a priori. Accordingly, all nodes in time-triggered systems have a common notion of time, based on synchronized clocks. One of the most important advantages of time-triggered systems is the deterministic temporal behaviour of the system, which eases system validation and verification considerably. Time-triggered systems are suitable in static environments in which the system behaviour can be completely known in advance.

2.6 Design Lifecycle of a System

A software development life cycle is the process followed when developing information systems, from the initial stage of information gathering, all the way through to maintenance and support of the system.

The literature mentions an inverse waterfall sort of model to describe the design of a typical system. This is explained comprehensively in detail in a study guide for Information Systems [10] and also in [8] and [9].

This process is known as the "V" model of systems development.[10] At each testing stage (see diagram, above), the corresponding planning stage is referred to, ensuring the system accurately meets the goals specified in the analysis and design stages.

If seen, analytically, we will realize that any system when need to be designed goes through the following phases [12]:

Conceptual Design

The Conceptual Design stage is where an identified need is examined, requirements for potential solutions are defined, potential solutions are evaluated and a System Specification is developed. The System Specification represents the 'technical requirements' that will provide overall guidance for system design. Because this document governs all future development, the stage cannot be completed until a Conceptual Design Review has determined that the System Specification properly addresses the motivating need.

Key steps within the Conceptual Design stage include:

Need Identification

Feasibility Analysis

System Requirements Analysis

System Specification

Conceptual Design Review

Preliminary System Design

During this stage of the system lifecycle, subsystems that perform the desired system functions are designed and specified in compliance with the system specification. Interfaces between subsystems are defined, as well as overall test and evaluation requirements[3]. At the completion of this stage, a Development Specification is produced that is sufficient to perform detailed design and development.

Key steps within the Preliminary Design stage include:

Functional Analysis

Requirements Allocation

Detailed Trade-Off Studies

Synthesis of System Options

Preliminary Design of Engineering Models

Development Specification

Preliminary Design Review

Detail Design and Development

This stage includes the development of detailed designs that brings initial design work into a completed with form of specifications. This work includes the specification of interfaces between the system and its intended environment and a comprehensive evaluation of the systems logistical, maintenance and support requirements. The Detail Design and Development is responsible for producing the Product, Process and Material Specifications and may result in substantial changes to the Development Specification.

Key steps within the Detail Design and Development stage include:

Detailed Design

Detailed Synthesis

Development of Engineering and Prototype Models

Revision of Development Specification

Product, Process and Material Specification

Critical Design Review

Production/Construction

During the Production and/or Construction stage the product is built or assembled in accordance with the requirements specified in the Product, Process and Material Specifications and is deployed and tested within the operational target environment. System assessments are conducted in order to correct deficiencies and adapt the system for continued improvement.

Key steps within the Production/Construction stage include:

Production and/or Construction of System Components

Acceptance Testing

System Distribution and Operation

Operational Testing and Evaluation

System Assessment

Utilization and Support

Once fully deployed, the system is used for its intended operational role and maintained within its operational environment.

Key steps within the Utilization and Support stage include:

System Operation in the User Environment

Maintenance and Logistics Support

System Modifications for Improvement

System Assessment

Phase-Out and Disposal

Once deployed, the effectiveness and efficiency of the system must be continuously evaluated to determine when the product has met its maximum effective lifecycle. Considerations include: Continued existence of operational need, matching between operational requirements and system performance, feasibility of system phase-out versus maintenance, and availability of alternative systems.

Waterfall Lifecycle Model, the Spiral Model and all other such models more or less follow this same outline of developing a system. We have seen here the general design strategy and now we head to see how does the design phase differ for Real-Time Systems, as all this high time constraints cannot be catered to by the normal design strategy presented here.

2.7 Design Lifecycle of a Real-Time System

Reactive and real-time systems involve concurrency, have strict requirements, must be reliable, and involve software and hardware components [4].

Reactive systems are computer systems that continuously react to their physical environment, at a speed determined by the environment. This class of systems has been introduced to distinguish them from transformational systems (input, process and output). Reactive Systems include, among others, telephones, communication networks, computer operating systems, man-machine interfaces, etc.

Real-time Systems (RTSs) have reactive behaviour. An RTS involves control of one or more physical devices with essential timing requirements. The correctness of an RTS depends both on the time in which computations are performed as well as the logical correctness of the results. Severe consequences may occur if the requirements of a real-time system are not met. Requirements from an RTS are diverse, ranging from intricacies of interfaces to providing guarantees of safety and reliability of operation.

Real-Time Systems have the following characteristics [6],

They are high in non-functional requirements, viz reliability, fault-tolerance etc.

They are timely, performing within the specified time.

They ought to be reactive.

They ought to handle the execution of threads concurrently.

They ought to be non deterministic.

They ought to be deadline-driven.

These characteristics lead to a difference in the design model, viz each design phase is validated by simulation or verification before going on to the next phase [14].

J. F. Peters and S. Ramanna [13] pointed out the need for a different design strategy for real-time systems by stating that for real-time systems, the original SDLC (System Design Lifecycle) undergoes some changes. They stated that real-time relevant logic must be incorporated at the design phase itself. Thus at the design level it is vital to take into consideration factors which can make the design better via metrics.

2.8 Contrasting the Difference in Design

Ramanna and Peters [13] have further contrasted the designs and given suggestions how to remove the flaws from the orthodox design strategy. This fact is explained diagrammatically below.

The 2 diagrams given above are self-explanatory and give a good deal of insight into the strategy adopted.

2.9 Issues in Real-Time System Design

Designing real-time systems is a challenging task. Most of the challenge comes from the fact that Real-time systems have to interact with real world entities. These interactions can get fairly complex. A typical real-time system might be interacting with thousands of such entities at the same time. For example, a telephone switching system routinely handles calls from tens of thousands of subscriber. The system has to connect each call differently. Also, the exact sequence of events in the call might vary a lot.

In the following sections we will be discussing these very issues [15]...

Real-time Response

Recovering from Failures

Working with Distributed Architectures

Asynchronous Communication

Race Conditions and Timing.

2.9.1 Real-Time Response

Realtime systems have to respond to external interactions in a predetermined amount of time. Successful completion of an operation depends upon the correct and timely operation of the system. Design the hardware and the software in the system to meet the Realtime requirements. For example, a telephone switching system must feed dial tone to thousands of subscribers within a recommended limit of one second. To meet these requirements, the off hook detection mechanism and the software message communication involved have to work within the limited time budget. The system has to meet these requirements for all the calls being set up at any given time.

The designers have to focus very early on the Realtime response requirements. During the architecture design phase, the hardware and software engineers work together to select the right system architecture that will meet the requirements. This involves deciding inter connectivity of the processors, link speeds, processor speeds, etc. The main questions to be asked are:

Is the architecture suitable? If message communication involves too many nodes, it is likely that the system may not be able to meet the real-time requirement due to even mild congestion. Thus a simpler architecture has a better chance of meeting the real-time requirements.

Are the link speeds adequate? Generally, loading a link more than 40-50% is a bad idea. A higher link utilization causes the queues to build up on different nodes, thus causing variable amounts of delays in message communication.

Are the processing components powerful enough? A CPU with really high utilization will lead to unpredictable real-time behaviour. Also, it is possible that the high priority tasks in the system will starve the low priority tasks of any CPU time. This can cause the low priority tasks to misbehave. As with link, keep the peak CPU utilization below 50 %.

Is the Operating System suitable? Assign high priority to tasks that are involved in processing real-time critical events. Consider preemptive scheduling if real-time requirements are stringent. When choosing the operating system, the interrupt latency and scheduling variance should be verified.

Scheduling variance refers to the predictability in task scheduling times. For example, a telephone switching system is expected to feed dialtone in less than 500 ms. This would typically involve scheduling three to five tasks within the stipulated time. Most operating systems would easily meet these numbers as far as the mean dialtone delay is concerned. But general purpose operating systems would have much higher standard deviation in the dialtone numbers.

Interrupt Latency refers to the delay with which the operating system can handle interrupts and schedule tasks to respond to the interrupt. Again, real-time operating systems would have much lower interrupt latency.

2.9.2 Recovering from Failures

Realtime systems must function reliably in event of failures. These failures can be internal as well as external. The following sections discuss the issues involved in handling these failures.

2.9.3 Internal Failures

Internal failures can be due to hardware and software failures in the system. The different types of failures you would typically expect are:

Software Failures in a Task: Unlike desktop applications, RTAs do not have the luxury of popping a dialog box and exiting on detecting a failure. Design the tasks to safeguard against error conditions. This becomes even more important in a real-time system because sequence of events can result in a large number of scenarios. It may not be possible to test all the cases in the laboratory environment. Thus apply defensive checks to recover from error conditions. Also, some software error conditions might lead to a task hitting a processor exception. In such cases, it might sometimes be possible to just rollback the task to its previous saved state.

Processor Restart: Most Realtime systems are made up of multiple nodes. It is not possible to bring down the complete system on failure of a single node thus design the software to handle independent failure of any of the nodes. This involves two activities:

Handling Processor Failure: When a processor fails, other processors have to be notified about the failure. These processors will then abort any interactions with the failed processor node. For example, if a control processor fails, the telephone switch clears all calls involving that processor.

Recovering Context for the Failed Processor: When the failed processor comes back up, it will have to recover all its lost context from other processors in the system. There is always a chance of inconsistencies between different processors in the system. In such cases, the system runs audits to resolve any inconsistencies. Taking our switch example, once the control processor comes up it will recover the status of subscriber ports from other processors. To avoid any inconsistencies, the system initiates audits to crosscheck data-structures on the different control processors.

Board Failure: Realtime systems are expected to recover from hardware failures. The system should be able to detect and recover from board failures. When a board fails, the system notifies the operator about it. Also, the system should be able to switch in a spare for the failed board. (If the board has a spare)

Link Failure: Most of the communication in real-time systems takes place over links connecting the different processing nodes in the system. Again, the system isolates a link failure and reroutes messages so that link failure does not disturb the message communication.

2.9.4 External Failures

Realtime systems have to perform in the real world. Thus they should recover from failures in the external environment. Different types of failures that can take place in the environment are:

Invalid Behavior of External Entities: When a Realtime system interacts with external entities, it should be able to handle all possible failure conditions from these entities. A good example of this is the way a telephone switching systems handle calls from subscribers. In this case, the system is interacting with humans, so it should handle all kinds of failures, like:

Subscriber goes off hook but does not dial

Toddler playing with the phone!

Subscriber hangs up before completing dialing.

Inter Connectivity Failure: Many times a real-time system is distributed across several locations. External links might connect these locations. Handling of these conditions is similar to handling of internal link failures. The major difference is that such failures might be for an extended duration and many times it might not be possible to reroute the messages.

2.9.5 Asynchronous Communication

Remote procedure calls (RPC) are used in computer systems to simplify software design. RPC allows a programmer to call procedures on a remote machine with the same semantics as local procedure calls. RPCs really simplify the design and development of conventional systems, but they are of very limited use in real-time systems. The main reason is that most communication in the real world is asynchronous in nature, i.e. very few message interactions can be classified into the query response paradigm that works so well using RPCs.

Thus most real-time systems support state machine based design where multiple messages can be received in a single state. The next state is determined by the contents of the received message. State machines provide a very flexible mechanism to handle asynchronous message interactions. The flexibility comes with its own complexities.

2.9.6 Race Conditions and Timing

It is said that the three most important things in real-time system design are timing, timing and timing. A brief look at any protocol will underscore the importance of timing. All the steps in a protocol are described with exact timing specification for each stage. Most protocols will also specify how the timing should vary with increasing load. Realtime systems deal with timing issues by using timers. Timers are started to monitor the progress of events. If the expected event takes place, the timer is stopped. If the expected event does not take place, the timer will timeout and recovery action will be triggered.

A race condition occurs when the state of a resource depends on timing factors that are not predictable. This is best explained with an example. Telephone exchanges have two way trunks which can be used by any of the two exchanges connected by the trunk. The problem is that both ends can allocate the trunk at more or less the same time, thus resulting in a race condition. Here the same trunk has been allocated for a incoming and an outgoing call. This race condition can be easily resolved by defining rules on who gets to keep the resource when such a clash occurs. The race condition can be avoided by requiring the two exchanges to work from different ends of the pool. Thus there will be no clashes under low load. Under high load race conditions will be hit which will be resolved by the pre-defined rules.

A more conservative design would partition the two way trunk pool into two one way pools. This would avoid the race condition but would fragment the resource pool.

The main issue here is identifying race conditions. Most race conditions are not as simple as this one. Some of them are subtle and can only be identified by careful examination of the design.

2.9.7 Flow Control

Flow control is concerned with the synchronization of the speed of the sender of information with the speed of the receiver, such that the receiver can follow the sender. Since the controlled object in many real-time systems is not in the sphere of control of the computer system, there is no possibility to limit the occurrence of events in the controlled object in case the computer system cannot follow therefore provisions must be made such that correlated event showers can be buffered at the interface between the controlled object and the computer system.

Several engineering solutions have been applied to restrict the flow of events at this interface. These include hardware implemented low pass filters, intermediate buffering of events in hardware and/or software, etc. However, it is still one of the difficult design problems to devise a flow control schema for a real time system that protects the computer system from overload situations caused by a faulty sensor or a correlated event shower and at the same time makes sure that no important events are suppressed by the flow control mechanism.

2.9.8 Maximum Execution Time of Programs

A given deadline for the delivery of the result of a computation can only be guaranteed if an upper data independent bound on the execution time of the corresponding real-time program is known apriori. For two reasons this bound should he tight: Firstly, the result should be based on recent input data and secondly, in systems based on static scheduling, the resource reservation should not be overly pessimistic. Since all, of the commonly used programming languages allow the design of non-terminating programs, some language restrictions have to be put in place if the maximum execution time of a program is able to be derived from an analysis of the program code. The recent trends in the field of microprocessor architectures (caches, pipelining) that lead to an increase in the speed of the average computation time at the expense of a long maximum execution time further complicate the problem of the establishment of tight execution time bounds.

2.9.9 Scheduling

In general, the problem of deciding whether a set of real-time tasks whose execution is constrained by some dependency relation (e.g., mutual exclusion), is schedulable belongs to the class of NP-complete problems [5]. Finding a feasible schedule, provided it exists, is another difficult problem. The known analytical solutions to the dynamic scheduling problem [6] assume stringent constraints on the interaction properties of task sets that are difficult to meet in distributed real-time systems.

2.9.10 Testing for Timeliness

In many real-time system projects more than 50% of the resources are spent on testing. It is very difficult to design a constructive test suite to systematically test the temporal behavior of a complex real-time system if no temporal encapsulation is enforced by the system architecture.

2.9.11 Error Detection

In a real-time computer system we have to detect value errors and timing errors before an erroneous output is delivered to the control object. Error detection has to be performed by the receiver and by the sender of information. The provision of an error detection schema that will detect all errors specified in the fault hypothesis with a small latency is another difficult design problem.

This thesis undertakes real-time systems and so we are set to define such systems. We will break down each term; define it individually and then head on for a complete definition.

A system is a mapping of a set of inputs into a set of outputs. Every real-world entity can be mapped as a system.

Real-time refers to the correct response provided within a pre-determined time frame.

Hence, we may say that a real-time system is one in which its proper functioning is based on the correctness of the outputs and their timeliness. Quoting Phillip Laplante [13], the definition is as follows:

‘A real-time system is a system that must satisfy explicit (bounded) response-time constraints or risk severe consequences, including failure.'

Failure for a real-time system doesn't simply mean that the requirements were not met. Usually it means life-threatening situations where the simple loss of not meeting the temporal deadline defined by the designer/programmer leads to loss of lives.

According to Sommerville [16], another way to look at real-time systems is to view them as a stimulus/response system. All the inputs take the role as stimuli, and the outputs as responses. Stimuli may be periodic or aperiodic. Periodic stimuli occur at predictable time intervals. Aperiodic stimuli occur irregularly and are usually signalled using the computer's interrupt mechanism.

As an example of a real-time system, consider a computer-controlled machine on the production line at a bottling plant. The machine's function is simply to cap each bottle as it passes within the machine's field of motion on a continuously moving conveyor belt. If the machine operates too quickly, the bottle won't be there yet. If the machine operates too slowly, the bottle will be too far along for the machine to reach it. Stopping the conveyor belt is a costly operation, because the entire production line must correspondingly be stopped. Therefore, the range of motion of the machine coupled with the speed of the conveyor belt establishes a window of opportunity for the machine to put a cap on the bottle. This window of opportunity distinguishes a real-time system from a non-real one. It indicates that the response has to lie within the time-frame provided otherwise the system is a failed one. It doesn't imply that the system has to be fast to be real-time. It simply has to meet the timing requirement set for it. This window of opportunity is in the form of a time-frame known as a period and deadline.

Real-time systems can be classified into three sub-categories [16]:

Hard Real-Time Systems

‘A hard real-time system is one in which failure to meet a single deadline may lead to complete and catastrophic system failure.'

For instance, an avionics weapons delivery system in which pressing a button launches an air-to-air missile. Missing the deadline to launch the missile within a specified time after pressing the button can cause the target to be missed, which will result in catastrophe.

Soft Real-Time Systems

‘A soft real-time system is one in which performance is degraded but not destroyed by failure to meet response-time constraints.'

E.g. An automated teller machine.u Missing even many deadlines will not lead to catastrophe failure, only degraded performance.

Firm Real-Time Systems

‘A firm real-time system is one in which a few missed deadlines will not lead to total failure, but missing more than a few may lead to complete and catastrophic system failure.'

E.g. An embedded navigation controller for an autonomous robot weed killer. Missing critical navigation deadline causes the robot to veer hopelessly out of control and damage crops.

All applications fall somewhere within these definitions. Rather the demarcation amongst these types is a bit fuzzy. As illustrated in 6, the meaning of real-time spans a spectrum. At one end of the spectrum is non real-time, where there are no important deadline. The other end is hard real-time, where no deadlines can be missed.

In USA ‘real-time' refers to on-line terminal services such as ATMs, database enquiry and on-line reservation and payment systems. Real-time system comprises of parallel or concurrent activities.

Embedded Real-Time Systems are those type of RTS that are based on specialized hardware and lack an operating system. An embedded RTS is called organic if it is not for a specialized hardware. It is known as loosely coupled/ semi-detached if they can be made organic with the re-write of a few modules.

Real-time Systems are usually event-based. An event in real-time software is anything that causes a change in flow. Real-time systems are always susceptible to change in their normal course of action. This is the reason why the notion of events is used to explain their functioning. Events can be of two types, viz:

1. Synchronous-these are the events which occur at predictable intervals.

2. Asynchronous- these occur at unpredictable events (caused by external sources).

2.10 Other Design Methodologies for RTS

Sommerville [16] proposes a design strategy for real-time systems which is event based. The stages are as follows:

1. Identify the stimuli to be processed and what responses are desired for each.

2. Then determine for each stimuli the timing constraints.

3. Cluster the stimuli and responses together based on behaviour. With each such class associate a process.

4. Identify or design any algorithms to carry out this set of concurrent processes.

5. Design a scheduling system which will ensure that processes are started in time to meet their deadlines.

6. Employ a real-time executive to integrate the system.

Sommerville further also indicates the general components of a real-time executive. He says that these components can be used fully or partially depending on the size of the real-time system.

1. A real-time clock-

This provides information to schedule processes periodically.

2. An interrupt handler

This manages aperiodic requests for service.

3. A scheduler

This component is responsible for examining the processes which can be executed and choosing one of these for execution.

4. A resource manager

Given a process which is scheduled for execution, the resource manager allocates appropriate memory and processor resources.

5. A despatcher

This component is responsible for starting the execution of a process.

6. A configuration manager

This is responsible for the dynamic reconfiguration of the system's hardware.

7. A fault manager

This component is responsible for detecting hardware and software faults and take appropriate action to recover from these faults.

The real-time executive has also to be set to accommodate two types of priority levels for real-time systems:

1. The interrupt level-this is for those processes that need immediate attention on the part of processing. The processes handled by interrupts are usually the ones associated with the foreground processes.

2. Clock level- this level is allocated to periodic processes.

Mani B. Srivasta et al [17] identifies two distinct phases in the real-time systems' design phase. Firstly, the high-level system specification is mapped onto a set of inter-communicating hardware and software modules. Secondly, these identified modules are generated using a mix of mapping, synthesis and library based techniques.

A UML based design methodology for Real-Time and Embedded Systems is presented by Gjalt de Jong [18]. He has combined the informal strengths of UML with the formal strengths of SDL. Then using O-O concepts, he has identified software components.

2.11 Design and Design only

The design of real-time systems prefers the K.I.S.S (Keep It Simple Stupid) principle. In addition to this point of view, Rob Williams [19] states, ‘If you follow a good design technique, appropriate questions will emerge at the right moment, disciplining your thought process.'

Designing a real-time software entails five major phases[15], viz:

1. Software Architecture Definition

Once it has been decided that a real-time software is to be designed a suitable architecture is chosen. Then the UML based use-case design is carried out, where the system is treated as a black-box and all the users(mechanical or human) are considered as actors. The use-case diagram then shows all the possible interactions amongst the users and the system.

2. Co-Design

Next, for all the hardware, decide what software functionality needs to be allotted to which processor and/or link. The aim is that the resources should not get overloaded; also the system should remain scalable. Similar modules ought to be placed nearby as this reduces delay and eases inter-process message communication.

3. Defining Software Subsystems

These are purely software based, compared to the design decisions mentioned beforehand whose choice depended on hardware considerations too. Determine all the features needed by the system. Group them together and consider whether any sub-system can be made to simplify the design. Also, identify the tasks (along with their respective roles) that will implement the features identified.

4. Feature Design

Once the tasks and features have been done with, what needs to be designed is how the messages will interact amongst these tasks. Some of these tasks will be controlling the other ones by keeping a record of the activity of the feature. For this the concept of running timers is to be employed. The mechanism is such that timers are started to monitor the progress of events. If the desired event/task is carried out as per plan, the timer is stopped otherwise the timer times out and some recovery action comes into play. This recovery action is usually in the form of some roll-back activity. Message interfaces need to be specified in detail (all the fields and possible values).

5. Task Design

Once the tasks are identified it needs to be decided which state machine model will be employed to implement it. We are all aware that real-time systems are mostly state-based systems, so this decision is also vital to complete the design process. The state machine chosen can be either for single, multiple or complex tasks. Moreover the model can be either flat or hierarchical. This is also pivotal as here lies the basis of scheduling rules which are important for the smooth functioning of a real-time software.

Kopetz et.al (1991) [22] present a methodology for the design of real-time systems by breaking down the process from specification to the fine-grained task, message and protocol-level. Mars is the underlying architecture for the proposed design methodology. All the aspects of an engineered hard real-time system are considered, viz: predictability, testability, fault-tolerance (fail-stop or fail-operational), consideration of the complete system (both hardware and software), system decomposability (from abstraction to smaller modules) and evaluability (through an early dependability and timing analysis).

Previous design methodologies include SDARTS, DARTS, SDL, SCR, MASCOT, EPOS, SREM and so on. None of these methodologies provided all the characteristics mentioned above so the authors came up with a novel methodology constricted with some basic assumptions. The design methodology is explained diagrammatically below:

This entire process indirectly sets-up an off-line scheduling system which is the key to fulfilling the timing constraints for real-time systems. However, this indirect off-line scheduling does not suffice for predictable hard real-time systems and other issues also need to be considered simultaneously, viz: static and dynamic scheduling. Other crucial parameters include the following[22]:

TRANSACTION LEVEL

* MART (MAximum Response Time)

* MINT (Minimum INTerval)

TASK LEVEL

* MAXTE (estimated maximum execution time)

* MAXTC (calculated maximum execution time)

DATA LEVEL

* Validity (period of time for which data is valid or holds true)

SYSTEM LEVEL

* Maximum execution time of the communication protocol between tasks.

* CPU availability (CPU time usable for application tasks)

* System overheads, i.e: task switching, periodic clock interrupt, CPU cycles used by DMA eg for network access and so on.

OVERALL

* MAXT (execution time: calculated based on a value extracted by all of the timing values given above)

The importance of testing design is also emphasized by these authors. They recommend a testing scenario where each component, cluster (open-looped cluster test and closed-loop cluster test) or task is tested once right after its design and once after the implementation is sought. As we know, the testing done at design has a lower cost (by all means) hence the method is commendable. Other tests mentioned are the system test and the field test.

Finally the authors mention a software, which supports design through MARS, called MARDS. How MARDS aids in the design process is explained through this paper.

Zage points out in a paper [20] that the design phase of a software has two major aspects, viz the architectural design and the detailed design. The author has drawn an analogy between designing a software and constructing a true-to-life model of a building. To assist in devising a better design or tracing out errors in the design already made, two metrics have been developed by the team at Ball State University.

First is the external metric, De, that is based on information extracted during the architectural design, viz “hierarchical module diagrams, dataflow, functional descriptions and interface descriptions”. This basically caters to the inter-modular structure.

Second is the internal metric, DI, that is based on information available after the detailed design, viz all the information given above as well as “any chosen algorithms or the pseudo code developed”. This basically caters to the internal structure of the modules.

Then the author has come up with a composite metric to measure ‘design quality' for a design G.

D(G) = De + Di

where De = e1 (inflow * outflow) + e2 (fan-in * fan-out)

and Di = i1 (CC) + i2 (DSM) + i3 (I/O)

D(G) stands for the design quality,

CC stands for Central Calls,

DSM stands for Data-Structure Manipulations and

I/O refers to the external device accesses.

Moreover, inflow tells about the number of data entities passed to the module, outflow tells about the number of data entities passed from the module, fan-in tells the number of super-ordinate modules directly connected to the given module and fan-out tells the number of sub-ordinate modules directly connected to the given module and both e and i are the weighting factors and can take any values depending on the influence of the parameters involved.

To the calculation of Di, even more crucial parameters could have been added, like ‘cyclomatic complexity, nesting levels, knot counts, live variable counts and declaration-use pairs and so on.' However, the author was not in favour of it as he clearly quotes an important aspect of metrics wherein, trying to cover too many features via metric, muzzles up the result. Similarly, trying to associate just one feature with a metric, doesn't extract any vital information at all.

This metrics suitability to detect potential ‘stress-points' and error-prone modules was then tested against a large-scale software (its suitability for a small-scale software had already been proved). When tested for a large one interesting results were drawn. It was noted that with the calculation of De and Di, the outliers were usually the stress-points. When the outliers were way too many that the standard deviation and the mean didn't have nay sync with each other, the author introduced a method of identifying ‘X-less algorithms'. Once these were identified and marked straightaway as outliers, the rest of the calculations were performed on the remaining modules. These then provided with a better and evenly-distributed result, proving the importance of this metric.

In the end to prove the mettle of this metric even more, the author decided to test a part of it (Di) against a time-based metric called cyclomatic complexity V(G). It was found that Di served the purpose the best so far, even more than V(G). These results were then tallied with LOC-lines of code metric that was available after the generation of the code. As far as overall D(G) metric was concerned, it proved to extract 100% module-error concentrations for large-scale software.

The author also provides a solution to all the modules which do turn out to be error-prone, by saying that the design should be re-tailored or then the coding of such modules should be handed over to the most experienced programmers on the team or the testing-time on the modules should be increased.

However, I would like to point out here that if the solution lied in increasing the testing phase then why to go into such details trying to unfathom the problems at the design phase itself. We should be looking for a solution at the design phase and simply go into re-tailoring the design and running the metrics again.

Design metrics should be in conformance with the requirements set in the preliminary analysis phase. MDD is being used by real-time software developers to assure accurate real-time performance of complex systems. Using the UML (UML 2.1), developers are able to use the abstraction of models to address and understand complexity. The application is simulated to ensure algorithms perform properly; the model is then used to automatically generate real-time code that strictly adhered to design.

The chosen metrics should be able to follow the SMART test, wherein the chosen metric should be S=Smart, M=Measurable, A=Attainable, R=Realistic and T=Timely.

To be able to measure a real-time system, factors that need to be taken into consideration are as follows: timeliness, performance, reactive or not, accuracy, predictability, deterministic or no, maintainability, adaptability, robustness, efficiency, accuracy, reliability, cost-friendly nature, quality-assurance, performance, risk-management, complexity, reliability, fault-tolerance and performance etc.

Fohler et al (2002) [34] suggest a metric for control performance (QoC) based on real-time timing constraints. Only closed-loop control systems have been considered.

Timing constraints and values determine the performance and areas of improvement for such a system. They say that the temporal values are of two types: fixed (task periods-time delay and task deadlines-sampling period) and flexible (sets of feasible instance separation- extracted from the type of controller chosen and response times).

During the design many values qualify in accordance with the timing constraints. Deviations from these values lead to system errors. Two types of system errors are pointed out, namely the IAE (Integral of the Absolute value of the Error) and ITAE (Integral of the Time-weighted Absolute value of the Error).

One of these errors is used to quantify the QoC metric. The QoC metric allows the decisions to be based on both temporal and control information.

A strategy has been devised to improve the performance of real-time closed-loop control systems, viz: instead of time values (fixed or flexible), choose a set of values (<instance separation, response time>) at the design stage and then hand it over to the scheduler to choose the correct/ closest value-set pair. Moreover, the ability to change values at run-time allows improvement of the system.
2.12 Steps to Attain Useful Metrics for RTS

Measurement. Lies at the heart of everything. Standards such as ISO 9000 and SEI's Capability Maturity Model uses metrics too.

As Grady (26) states, “Without such measures for managing software, it is difficult for any organization to understand whether it is successful.” The paper by Linda Westfall (27) outlines “12 Steps to Useful Software Metrics.”Basing our research on these steps, we outline twelve steps for software metrics of real-time systems. The discussion is presented hereforth.

Firstly, identify who has to use the metric. If the metric does not have a user for whom it is being produced, the entire effort is futile. For the software of real-time systems the users can be people related to functional management, project management, the end prosuct.

Secondly, determine which entity precisely needs to be measured? To aid in this process the ‘goal/question/metric' ( 27) ( 28) paradigm may be employed.

Thirdly, structure relevant questions, the answers of which will lead towards the goal(s) determined in the previous step.

Fourthly, for the real-time system software, formulate the objective according to the following formula(27):

Fifthly, hunt for standard definitions of the attributes and/or entities. If there aren't any available or if ambiguity hangs above them, then go ahead and define these things yourself from the perspective of real-time systems. There is a concise set of related definitions available in the IEEE Glossary of Software Engineering Terminology (29).

Sixthly, choose between direct measurement or indirect measurement.

Seventhly, if the measurement method is indirect, break it down to an atomic level so that it is clearly known that which entities need to be measured to achieve the desired goal.

Eighthly, define thresholds, variances, control limits and so. Be specific by giving percentages.and so on.

Ninthly, from the real-time perspective decide the method of reporting. As (27) states, “define the reporting format, data extraction and reporting cycle, reporting mechanisms, distribution and availability.”

Tenth, determine any additional qualifiers that will be needed if the metric has to be given a wider spectrum than the one allotted to it.

Eleventhly, we ought to be concerned about the collection of data. Since the metrics that have been devised here are concerned with the design phase of real-time systems, thus the collection of data is meager as compared to the entire life-cycle.

Lastly, keep the ethics alive. Make the selection of metrics, collections of data and intervening into professionals easy.

CHAPTER THREE
3. PROBLEM STATEMENT

Real-time systems are an integral part of the world of computing. Every system can benefit from the research done in the area of real-time systems, as normal systems are special cases of RTS. If every system is ‘gifted' with the added burden of timing constraints and all the other peculiar features of RTS, then each one of those could be called a RTS. Due to this, any work done on RTSs, can be beneficial to all the systems.

The work that this thesis entails revolves around the design phase of RTS (only the design phase of application software to be precise).The SDLC includes the following major phases, viz. analysis, design, development, implementation and testing. The software engineering cycle for RTS adopts a slight difference thanks to the crucial timing constraints that have to be met. There are different design strategies (already devised) which are discussed in the Literature Review section of this thesis (please refer for further insight).

With this difference in design methodologies, devising metrics (measurement methods) helps designers to choose and re-evaluate their designs well before implementation. The design phase is the longest phase of the lifecycle as it lends itself into the mid of analysis, as well as to the mid of development. It can also be called the spinal-cord or backbone of the entire SDLC as here lies the core architecture of the software which is to be developed. This makes it quite crucial too.

Metrics at the design phase have been proposed earlier, namely feature-point metrics, fuzzy-logic based metrics [35] etc.; but what is needed is a unified approach. If the problem can be located, via metrics at the design phase then we can save on investments (monetary, time and so on) and ‘nip the evil in the bud.' This act of identifying problem areas early also helps in predicting the difficulties and complications, which may occur later in software development. Hence such metrics solve the problems of not only the design phase but of all the other phases as well.

Experts have put forward a number of software design metrics for real-time systems, and they are working and trying to propose new strategies and methodologies for measurements in this industry. As [36] points out that metrics have been traditionally classified into three levels based on measurement theory, namely : product, process and resource metrics. Product metrics are classified under architecture, runtime and documentation metrics. Process metrics are further classified into management, life-cycle and case metrics. Resource metrics are classified further as personnel, software and hardware metrics. Therefore, this research attempts to analyze such design quality metrics that can be applied to design phase of real-time systems in order to predict flaws and improve the quality of real-time software applications.

CHAPTER FOUR
4. pROPOSED SOLUTION

The areas enumerated in the previous chapter will be looked into, to devise metrics to assist in measuring solid results. Measuring Flow Control is vital in the design of real-time systems, especially for Performance and Availability measurement. The thing that is important is that the receiver should allow for the transmission delay which the sender process goes through. H. Kopetz [33] proposes in his paper that a buffer, implemented in hardware or software, can fulfil this purpose. He says that this has been done in the past by the implementation of low-pass filters. We will simply propose a metric which measures whether the buffer is accommodating all the events which come in, without putting any to waste, or sending them unignored or uncatered to.

This takes the form of a constraint, which if fulfilled can ensure the smooth execution of flow of events.

Mathematically this metric can be expressed as follows:

The size of the buffer should also be limited, i.e, it should not exceed more than the size of the program.

This metric can be helpful in avoiding overloads by sensors or event showers or both. It also helps in priority-based identification of events before-hand, so that nothing important goes missing.

During the design of real-time software knowing the upper -bound on the WCET (Worst Case Execution Time) helps to have Predictability in a system. The WCET value ought to be less than a certain threshold. The threshold is set according to a prediction made on the basis of knowledge related to experts working in the same area. If the ‘device accesses' and the ‘context switches' are low then the WCET will be met, as the discrepancies will be low.

Trend_of_WCET = No._of_device_accesses + No._of _context_switches

Mathematically, this can be represented as follows:

T(WCET) = N(Ad) + N(Cs)

where Ad = no. of device accesses

and Cs = no. of context switches

The measurement of the WCET (Worst Case Execution Time) or MET(Maximum Execution Time) of a RT-software can be based on different approaches depending whether the design architecture is event-based or time-triggered. If it is event-based then the calculation will be based on the choice of the processor [21] and other factors like the OS which is under use, which sort of pre-emptive scheduling strategy does it use or how does it synchronize tasks [22]. Moreover, it is difficult to compute the MET and WCET of tasks without taking into account its interaction with other counterpart tasks[23]. However in January 2009, Maaita, Adi Abdelhalim [30] has proposed techniques for enhancing the temporal predictability of real-time systems for a time-triggered software architecture.

The WCET can be estimated at the design phase of a real-time system. It is said that at this stage the estimate is not very accurate [ ]but nevertheless it is an important estimate. Traditionally, the estimate of the WCET requires the factors explained in the previous paragraph. However, a newer approach uses cyclic dependency between tasks, ‘iterative convergence' and a ‘probabilistic schedulability envelope' [24]

Basic Cycle Time is the time which serves as the lower bound for the real-time executive, contrary to the WCET which serves as the upper bound.

Hence, it goes without saying that the acceptable limit for a task is between the basic cycle of time and WCET.

A metric has been devised that measures the Basic Cycle Time, viz

Gp-1-Gp = B.C.T

where Gp-1 is the time taken for the completion of the predecessor event,

and Gp is the time taken for the completion of the current event under execution.

The measurement of the design quality of a RTS is of utmost importance too. We have come up with a composite metric to measure ‘design quality' for a design G. This has been named as RTA Structure Metric.

Z(G) = Ze + Zi + Zt

where Ze = e1 (inflow * outflow) + e2 (fan-in * fan-out)

and Zi = i1 (CC) + i2 (DSM) + i3 (I/O)

and Zt = in-1 (tn-1) - in (tn)

Ze tells the relative number of data transactions between modules

Zi gives an aggregate of the number of central calls, direct manipulations as well as number of inputs and outputs to and from the module.

Zt is the time taken for a module/event to be carried out.

Computing this metric straightforwardly can help us determine the design quality of a RTS. Khan et al. [31] has provided us with insight regarding the ambiguity associated with the term ‘quality'. He states that quality is still a multi-dimensional and multi-faceted term, as it means different things to different people. The way quality is understood is a matter of perception. The identification of such markers which can aid in assessing quality of a system, can depend on many things including management objectives, goals set for the end product and the choice of the design of a system. Different quality attributes are related to each phase of the SDLC and it is elementary to decide the focus of study to a specific part. This is exactly what we have done. We have narrowed down the study of the quality metrics to that of the design phase (as this was our area of concern). Next, we have used parameters such as Zt, Zi and Ze (as explained above). These are using the temporal perspective as well as other vital information as fan-in, fan-out and so on.

The M.A.R (Message Activation Rate) and T.A.R (Task Activation Rate) are two entities that will be used as metrics. These rates will be determined by two parameters, viz the maximum deviation of the finishing time of two consecutive event instances, and the maximum deviation of the finishing time among all instances.

H. Kopetz [32] proposed in his paper Twelve Principles for the Design of Safety-Critical Real-Time Systems, a methodology for fault-tolerance. Based on this methodology metrics have been derived. He states a Swiss-Cheese Model for fault-tolerance of a real-time system. He suggests that once something goes wrong with a system, it should be provided with back-up plans. The normal functioning, when it gets hampered should be self-healing. Even if the self-healing process fails, then there should be a strategy for never giving-up. Amidst all these diagnostic capabilities, if a system event that caused the problem hasn't been able to self-heal the system then it can be declared as a ‘catastrophic system event.' A metric that measures the upper bound (UB) on the restarting of the system can easily help to identify the event that caused all the trouble in the first place. This event then can be either deleted or then be notified to the designer/programmer for suitable changes. This proposal of this metric can then be officially stated as follows:

If Restart Value > Upper Bound (prefixed)

Then Event == Fault

Redesign Event.

The Event here refers to the event responsible for the delay in the restart value.

Detection of the event responsible for the delay in meeting the Upper Bound, calls for a detailed analysis of appropriate detection algorithms, which is beyond the scope of discussion of this thesis.

CHAPTER FIVE
5. rESULTS and DISCUSSIONS

Since real-time systems are becoming more persistent, it is necessary that software engineers have quantitative measurements for accessing the quality of designs at both the architectural and component level. The measurement process is to drive the real-time software measures and metrics that are appropriate for the representation of real-time software that is being measured. Metrics have a lot of characteristics in order to improve the design process and enhance the development process as well.

5.1 METRICS ANALYSIS

In this thesis, we have reviewed software metrics thoroughly. We also looked at the importance of measurement and saw why it was utterly necessary to concentrate on the design phase of real-time systems. We found out that by focusing on the design phase we could actually target and troubleshoot the problem areas of the entire life-cycle of real-time systems. We also deeply analyzed real-time design metrics proposed by different authors and experts in literature. Given below are results and discussions for all of these different devised metrics.

5.2 FLOW CONTROL METRIC (FCM)

This metric caters to performance and availability criterion. It measures the time an event waits in a buffer.

This metric measures whether the buffer is allowing for the delay.

We take the ideal size of the buffer to be X.

Now we will put different values for the other variable parameters, viz Nb and N(e)b and see the trend in the result for T(e)b .

If Nb = 100 and N(e)b=100

T(e)b= 1

This indicates that it takes unit time (unity X=1), if the size of the buffer is such that it can accommodate all events equally, without having to make them wait in a queue.

If Nb = 100 and N(e)b=2

T(e)b= 0.2

This indicates that it takes 0.2 units of time (unity X=0.2), if the size of the buffer is too large as compared to the number of events that have to wait in the queue. This also indicates wastage of resources at the design phase. We can take these trend changes of values into account, to devise the optimum value for the size of the buffer and also to check whether the value of the size of the buffer at the design phase is optimum or no.

5.3 TREND OF WCET METRIC

Area of Concern: PREDICTABILITY

Metric: Measures the Trend of WCET by bringing into account the no. of device accesses and no. of context switches.

Background and Working:

This metric helps in giving an upper bound for the time allocated to the Real-Time Executive. The lesser the value of T(WCET), the lower will be the upper bound of RT-Executive.

Trend_of_WCET = No._of_device_accesses + No._of _context_switches

Mathematical Representation:

T(WCET) = N(Ad) + N(Cs)

For verification purposes, we take the value of the T(WCET) to be X once again.

Now we take different values for the 2 variables, viz No._of_device_accesses and No._of _context_switches.

If No._of_device_accesses=100 and No._of _context_switches=100

X=200 [A very high value of the WCET]

If No._of_device_accesses=100 and No._of _context_switches=2

X=102 [A moderate value of the WCET]

If No._of_device_accesses=2 and No._of _context_switches=100

X=102 [A moderate value of WCET]

If No._of_device_accesses=2 and No._of _context_switches=2

X=4 [An extremely small value for WCET]

Hence, we can conclude that as we vary the values of the 2 independent variables, the values of the dependent variable X varies accordingly. The trend in the variation can be seen above. Since this metric involves simple calculations (a simple ‘+' operator is employed).

5.4 BASIC CYCLE-TIME METRIC

Area of Concern: TIMELINESS, PERFORMANCE and EFFICIENCY

Metric: Determines the lower bound of the RT-executive's time of operation.

Background and Working:

This metric measures the difference between the previous task and the current one.

Mathematical Representation:

To verify this value we take B.C.T once again to be X.

We find out that as Gp-1 takes values that are greater than Gp, then the value of B.C.T and X, tally with the expected results in the design phase. This is a constraint and what we expect to find.

5.5 RTA STRUCTURE METRIC

Area of Concern: QUALITY

Metric: Measures the inflow, outflow, fan-in, fan-out, direct manipulations, I/Os, central calls and time-taken

Background and Working:

Provides an aggregate of the above mentioned features.

Mathematical Representation:

Z(G) = Ze + Zi + Zt

where Ze = e1 (inflow * outflow) + e2 (fan-in * fan-out)

and Zi = i1 (CC) + i2 (DSM) + i3 (I/O)

and Zt = in-1 (tn-1) - in (tn)

For verification purposes, we take Z(G) as X. Now we notice that for the value of X to remain predictable we should know the values of the dependable components. We will deal all the 3 components of X separately below.

Let the value of Ze be A.

Ze = A = e1 (inflow * outflow) + e2 (fan-in * fan-out)

If we get high values of A, this implies all the dependable parameters: inflow, outflow, fan-in and fan-out, possess high values. If we get low values, this implies that all the dependable parameters have low values. If we aim for moderate values, then we ought to look for values in at least one of the two dependable parameters to be low.

The same discussion holds true for the following equations:

Zi = i1 (CC) + i2 (DSM) + i3 (I/O)

Zt = in-1 (tn-1) - in (tn)

Following this discussion we come to know that X=A+B+C. The same discussion here also implies that the value of X can be moderated if we predict the values of the dependables: A, B and C with accuracy.

5.6 MESSAGE ACTIVATION RATE METRIC

Area of Concern: TIMELINESS

Metric: Measures the activation rate of instances.

Background and Working:

Maximum deviation of the finishing time of two consecutive instances.

Maximum deviation of the finishing time among all instances.

5.7 TASK ACTIVATION METRIC

Area of Concern: PERFORMABILITY (Meyer, 79)

Metric: Measures the activation rate of tasks

Background and Working:

This calculates the task activation rate and then computes the total task activation rate. If our system is to be designed keeping in mind this value then it can be handled for peak-load performance also.

Mathematical Representation:

5.8 UPPER BOUND METRIC

Area of Concern: FAULT TOLERANCE

Measures: This metric measures the upper bound on the restarting of the system allows to find the faulty event in the design phase.

Mathematical Representation:

If Restart Value > Upper Bound (prefixed)

Then Event == Fault

Redesign Event.

CHAPTER SIX
6. CONCLUSION

Real-Time Systems have been an object of attraction for both researchers and developers alike. The reason is that Real-Time Systems are used at places where, even a small error can become life-threatening. A slightly delayed response from the pre-prescribed temporal value becomes totally unacceptable. Moreover, every system is a special case of Real-Time Systems. Both of these factors indicate the importance of Real-Time Systems.

Although this is such an important area, unfortunately not much work has been carried out to enhance the utility of real-time software products and to minimize errors early at initial stages of the development lifecycle of Real-Time Systems. Since Real-Time Systems are becoming deployed at a greater scale, it is necessary that software engineers have quantitative measurements for accessing the quality of designs at both the architecture and component level.

This thesis proposed eight metrics pertaining to the design phase, namely: Flow Control Metric, Trend of WCET Metric, Basic Cycle Time Metric, RTA Structure Metric, Message Activation Rate Metric, Task Activation Metric and Upper Bound Metric. Their details are mentioned in the previous chapter. We have also presented a detailed analysis of the literature currently available about Real-Time Systems. We also conclude that employment of Real-Time Design Metrics at the design phase is the only way to cut down on development costs as well as to predict flaws easily.

CHAPTER SEVEN
7. FUTURE RECOMMENDATIONS

Measurement of Real-Time Systems has become widely known and very well-accepted in today's era. Every system is a special case of a real-time system. This makes the research presented in this thesis cater to a wide range of audience. It has been admitted that using measurements and metrics in software applications enables developers and designers to get better insight into the flaws and errors of the developing application well in advance. That is why the technique that we have proposed, of employing metrics at the design phase, helps in eliminating flaws really quickly and without making the cost of troubleshooting too high. It also indicates the probability of the issues which can appear at the later stages of the development cycle. It helps in classifying, analyzing and distributing different attributes of the real-time software application with less effort and time.

Real-Time Design Metrics have been studied and analyzed by many experts and practitioners in the past. Since these metrics have been seen to have shortcomings and limitations, we would suggest these issues to be resolved to get maximum benefits from these metrics. Many of these metrics lack any theoretical as well as empirical validation. This is the reason that they cannot be of any use to the industries. We also noted that, to make matters worse, some metrics had and still have ambiguous definitions, and some have very different interpretations for the same metric.

As future recommendation, we would suggest to remove this ambiguity and get unanimous standards granted. If properly implemented, real-time design metrics bring the promise of better and cheaper software. The most obvious extension to this research is to analyze the degree to which these metrics can correlate with indicators as software performance and design quality. Also the eight metrics that have been presented in this thesis, can be actually tested on live real-time systems and their results noted. These metrics, once verified by different experts in industry, can be adopted by real-time systems' industry gurus.

There is also need to congregate metrics of Real-Time Systems at different levels from requirement engineering to deployment. It would promote deeper understanding about the evolution of real-time applications and their complexity. Advances in any of the areas of real-time systems need to be correlated with devising metrics for that particular area. This strategy would be highly promising for research in the immediate future.

CHAPTER EIGHT
8. REFERENCES

[1] Puschner, P. and Koza Ch., 1989. Calculating the Maximum Execution Time of Real-Time Programs.

[2] Blanchard and Fabrycky, 2006. Systems Engineering and Analysis, Fourth Edition. Prentice Hall, 19.

[3] Dr. Joahn Gouws, 2007. Introduction to Engineering, System Engineering. Melikon Pvt Ltd.

[4] Halbwachs, N., 1993. Synchronous Programming of Reactive Systems. Dordrecht: Kluwer Academic Publishers.

[5] Garey. M.R.J,ohnson. D.S.. Complexity Results for Multiprocessor Scheduling under Resource.

[6] Sha, L., Rajkumar, R., Lehoczky, J.P.. Priority Inheritence Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers. Vol. 39, No. 9, Sept. 1990, pp. 1175-1185.

[7] Dan Ionescu, Aurell Cornell, 2007. Real-Time Systems-Modelling, Design and Applications. Amast Series of Computing

[8] 1997, The V-Model. Development Standard for IT-Systems for the Federal Republic of Germany.

[9] Christian Bucanac, 1999. The V-Model. University of Karlskrona/Ronneby.

[10] 2006, The Technical V-Model. Developing Systems Study Guide.

[11] www.soi.wide.ad.jp/class/20040034/slides11/0/3/.html

[12] https://en.wikipedia.org/wiki/V-Model_(software_development)

[13] J.F. Peters, S. Ramanna, 1997. Enhanced IEEE System Life Cycle: A Reactive Real-Time Systems Development Model, IEEE Conference on Communications, Power and Computing.

[14] Remy Kocik, Yves Sorel. A Methodology to Reduce the Design Lifecycle of Real-Time Embedded Control Systems.

[15] https://www.eventhelix.com/RealtimeMantra/

[16] Ian Sommerville. Software Engineering. Prentice Hall

[17] Mani B. Srivasta et.al. On-Line Scheduling of Hard Real-Time Tasks on Variable Voltage Processor. University of California, L.A.

[18] Gjalt de Jong et. al.,2002. A UML-based design methodology for real-time and embedded systems. Proceedings on the Conference on Design and Automation.

[19] Rob Williams,2006. Real-Time Systems Development.

[20] Zage, 1993. Evaluating Design Metrics On Large-Scale Software. IEEE.

[21] Puschner Peter and Burns Alan. A Review of Worst-Case Execution Time Analysis. The International Journal of Time-Critical Computing Systems, 18, pp. 115-128, 2000.

[22] Kopetz H. The Design of Fault-Tolerant Real-Time Systems. IEEE Computer Society Press, 2004.

[23] Sha L., Rajkumar R, Lehoczky JP. Priority Inheritance Protocols: An Approach to Real-Time Synchronization . IEEE Transactions on Computers, Vol. 39, No. 9, pp. 1175-1185, 1990.

[24] Min-Young Nam, Chang-Gun Lee, Kanghee Kim, Marco Caccamo, “Time-Parameterized Sensing Task Model for Real-Time Tracking,” rtss, pp.245-255, 26th IEEE International Real-Time Symposium (RTSS ‘05), 2005.

[25] Kangsun Lee, Paul A. Fishwick, “Building a Model for Real-Time Simulation,” Elsevier, FGCS Future Generation Computer Systems 17 (2001) 585-600

[26] Robert B. Grady, 1992, Practical Software Metrics for Project Management and Process Improvement, Prentice-Hall, Englewood Cliffs.

[27] Linda Westfall, 2005, 12 Steps to Useful Software Metrics, The Westfall Team.

[28] V. R. Basili, H. D. Rombach, 1988, The TAME Project: Towards Improvement-Oriented Software Environments. In IEEE Transactions in Software Engineering 14 (6), November.

[29] IEEE Standard Glossary of Software Engineering Terminology, ANSI/IEEE Std 610-1990, The Institute of Electrical and Electronics Engineers, New York, NY, 1990.

[30] Maaita, Adi Abdelhalim, Techniques for Enhancing the Temporal Predictability of Real-Time Embedded Systems Employing a Time-Triggered Software Architecture, 2009.

[31] R. A. Khan, K. Mustafa, S. I. Ahson; “Software Quality: Concepts and Practices”; published by N. K Mehra for Narousa House Pvt Ltd.; 2006.

[32] H. Kopetz, Twelve Principles for the Design of Safety-Critical Real-Time Systems, 2004.

[33] H. Kopetz, The Design of Fault-Tolerant Real-Time Systems, 1994.

[34] Fohler, et. al., 2002. A control performance metric for real-time timing constraints. 14th Euromicro Conference.

[35] Anupama Raman, Afzel Noore, 2003. Software Metrics for Real-Time Systems Using Fuzzy Sets. IEEE

[36] Saba Iqbal. Design Metrics for Non-Web Based Systems Using Object Oriented Approach.

[37] K. Lee, 1993. Modelling a Real-Time System using OOPM/RT. ACM

Did you like this example?

Cite this page

Real-Time Systems. (2017, Jun 26). Retrieved October 15, 2024 , from
https://studydriver.com/real-time-systems/

Save time with Studydriver!

Get in touch with our top writers for a non-plagiarized essays written to satisfy your needs

Get custom essay

Stuck on ideas? Struggling with a concept?

A professional writer will make a clear, mistake-free paper for you!

Get help with your assignment
Leave your email and we will send a sample to you.
Stop wasting your time searching for samples!
You can find a skilled professional who can write any paper for you.
Get unique paper

Hi!
I'm Amy :)

I can help you save hours on your homework. Let's start by finding a writer.

Find Writer