Two critical aspects of real-time systems are how time is handled and the execution of actions with respect to time. The design of a real-time system must identify the timing requirements of the system and ensure that the system performance is both logically correct and timely.

Most developers concerned with timeliness of behavior express it in terms of actual execution time relative to a fixed budget called a time constraint. Often, the constraint is specified as a deadline, a single time value (specified from the onset of an initiating stimulus) by which the resulting action must complete. The two types of time constraints commonly used are hard and soft:

Usually a timing constraint is specified as a deadline, a milestone in time that somehow constrains the action execution.

In the RTP, actions may have the time-related properties shown in Table 1-1.

As Table 1-1 suggests, the basic concepts of timeliness in real-time systems are straightforward even if their analysis is not. Most time requirements come from bounds on the performance of reactive systems. The system must react in a timely way to external events. The reaction may be a simple digital actuation, such as turning on a light, or a complicated loop controlling dozens of actuators simultaneously. Typically, many subroutines or tasks must execute between the causative event and the resulting system action. External requirements bound the overall performance of the control path. Each of the processing activities in the control path is assigned a portion of the overall time budget. The sum^[9] of the time budgets for any path must be less than or equal to the overall performance constraint.

Because of the ease of analysis of hard deadlines, most timeliness analysis is done assuming hard deadlines and worst-case completion times. However, this can lead to overdesign of the hardware at a potentially much greater recurring cost than if a more detailed analysis were done.

In the design of real-time systems several time-related concepts must be identified and tracked. An action may be initiated by an external event. Real-time actions identify a concept of timely—usually in terms of a deadline specified in terms of a completion time following the initiating event. An action that completes prior to that deadline is said to be timely; one completing after that deadline is said to be late.

Actions are ultimately initiated by events associated with the reception of messages arising from objects outside the scope of the system. These messages have various arrival patterns that govern how the various instances of the messages arrive over time. The two most common classifications of arrival patterns are periodic and aperiodic (i.e., episodic). Periodic messages may vary from their defined pattern in a (small) random way. This is known as jitter.

Aperiodic arrivals are further classified into bounded, bursty, irregular, and stochastic (unbounded). In bounded arrival times a subsequent arrival is bounded between a minimum interarrival time and a maximum interarrival time. A bursty message arrival pattern indicates that the messages tend to clump together in time (statistically speaking, there is a positive correlation in time between the arrival of one message and the near arrival of the next).^[10] Bursty arrival patterns are characterized by a maximum burst length occurring within a specified burst interval. For example, a bouncy button might be characterized as giving up to 10 events within a 20ms burst interval. The maximum burst length is also sometimes specified with a probability density function (PDF) giving a likely distribution or frequency within the burst interval. Lastly, if the events arrivals are truly uncorrelated with each other, they may be modeled as arising randomly from a probability density function (PDF). This is the stochastic arrival pattern.

Knowing the arrival pattern of the messages leading to the execution of system actions is not enough to calculate schedulability, however. It is also important to know how long the action takes to execute. Here, too, a number of different measures are used in practice. It is very common to use a worst-case execution time in the analysis. This approach allows us to make very strong statements about absolute schedulability, but has disadvantages for the analysis of systems in which occasional lateness is either rare or tolerable. In the analysis of so-called soft real-time systems, it is more common to use average execution time to determine a statistic called mean lateness.

Actions often execute at the same time as other actions. We call this concurrency. Due to the complexity of systems, objects executing actions must send messages to communicate with objects executing other actions. In object terminology, a message is an abstraction of the communication between two objects. This may be realized in a variety of different ways. Synchronization patterns describe how different concurrent actions rendezvous and exchange messages. It is common to identify means for synchronizing an action initiated by a message sent between objects.

In modern real-time systems it cannot be assumed that the sender of a message and the receiver of that message are located in the same address space. They may be executing on the same processor, in the same thread, on the same processor but different threads, or on separate processors. This has implications for the ways in which the sender and receiver can exchange messages. The transmission of a message m may be thought of as having two events of interest—a send event followed by a receive event. Each of these events may be processed in either a synchronous or an asynchronous fashion, leading to four fundamental synchronization patterns, as shown in Figure 1-1. The sending of an event is synchronous if the sender waits until the message is sent before continuing and asynchronous if not.^[11] The reception of an event is synchronous if the receiver immediately processes it and asynchronous if that processing is delayed. An example of synch-synch pattern (synchronous send–synchronous receive) is a standard function or operation call. A message sent and received through a TCP/IP protocol stack is an example of an asynch-asynch transfer, because the message is typically queued to send and then queued during reception as well. A remote procedure call (RPC) is an example of a synch-asynch pattern; the sender waits until the receiver is ready and processes the message (and returns a result), but the receiver may not be ready when the message is sent.

Figure 1-1. Synchronization Patterns

In addition to these basic types, a balking rendezvous is a synch-synch rendezvous that aborts the message transfer if the receiver is not immediately ready to receive it, while a timed wait rendezvous is a balking rendezvous in which the sender waits for a specified duration for the receiver to receive and process the message before aborting. A blocking rendezvous is a synch-synch rendezvous in which the sender will wait (forever if need be) until the receiver accepts and processes the message.

In lay terms, concurrency is doing more than one thing at once. When concurrent actions are independent, life is easy. Life is, however, hard when the actions must share information or rendezvous with other concurrent actions. This is where concurrency modeling becomes complex.

Programmers and models typically think of the units of concurrency as threads, tasks, or processes. These are OS concepts, and as such available as primitive services in the operating system. It is interesting that the RTP does not discuss these concepts directly. Instead, the RTP talks about an active resource (a resource that is capable of generating its own stimuli asynchronously from other activities). A concurrent Unit is a kind of active resource that associates with a scenario (a sequenced set of actions that it executes) and owns at least one queue for holding incoming stimuli that are waiting to be accepted and processed. Sounds like a thread to me ;-)

As a practical matter, «active» objects contain such concurrentUnits, have the responsibility to start and stop their execution, and, just as important, delegate incoming stimuli to objects contained within the «active» objects via the composition relationship. What this means is that we will create an «active» object for each thread we want to run, and we will add passive (nonactive) objects to it via composition when we want them to execute in the context of that thread. Figure 1-2 shows a typical task diagram in UML.^[12] The boxes with thick borders are the «active» objects. The resource is shown with the annotation «resource», called a stereotype. In the figure, an icon is used to indicate the semaphore rather than the alternative «stereotype» annotation. We will discuss the UML notions of objects and relations in much more detail in the next chapter.

Figure 1-2. «active» Objects and Threads

A simple analysis of execution times is usually inadequate to determine schedulability (the ability of an action to always meet its timing constraints). Most timeliness analysis is based, explicitly or implicitly, on a client-resource model in which a client requires a specified QoS from a resource and a resource offers a QoS. Assuming the offered and required values are correct, schedulability analysis is primarily a job of ensuring that offered QoS is always at least as good as required. See Figure 1-3.

Figure 1-3. Required and Offered Quality of Service

A resource from [7] is defined to be “an element whose service capacity is limited, directly or indirectly, by the finite capacities of the underlying physical computing environment.” Resource is a fundamental concept, one that appears many times in real-time systems. Much of the design of a real-time system is devoted to ensuring that resources act in accordance with their preconditional invariant assumptions about exclusivity of access and quality of service.

The execution times used in the analysis must take into account the blocking time, that is, the length of time an action of a specific priority is blocked from completion by a lower-priority action owning a required resource.

At the best of, uh, times, time itself is an elusive concept. While we lay folks talk about it passing, with concepts like past, present, and future, most philosophers reject the notion. There seem to be two schools of thought on the issue. The first holds that time is a landscape with a fixed past and future. Others feel it is a relationship between system (world) states as causal rules play out. Whatever it may be,^[13] with respect to real-time systems, we are concerned with capturing the passage of time using milestones (usually deadlines) and measuring time. So we will treat time as if it flowed and we could measure it.

The RTP treats time as an ordered series of time instants. A timeValue corresponds to such a physical instant of time and may be either dense (meaning that a timeValue exists between any two timeValues) or discrete (meaning there exist timeValue pairs that do not have another timeValue between them). A timeValue measures one or more physical instants. A duration is the interval between two physical instants; that is, it has both starting and ending physical instants. A timeInterval may be either absolute (same as a duration) or relative. So what's the difference between a duration and a timeInterval? A duration has a start and end physical instant, while a timeInterval has a start and end timeValue. Confusing? You bet!

Fortunately, the concepts are not as difficult to use in practice as they are to define precisely. In models, you'll always refer to timeValues because that's what you measure, so timeIntervals will be used more than durations.

Speaking of measuring time....We use two mechanisms to measure time: clocks and timers. All time is with reference to some clock that has a starting origin. It might be the standard calendar clock, or it might be time since reboot. If there are multiple clocks, they will be slightly different, so in distributed systems we have to worry about synchronizing them. Clocks can differ in a couple of ways. They can have a different reference point and be out of synch for that reason—this is called clock offset. They may also progress at different rates, which is known as skew. Skew, of course can change over time, and that is known as clock drift. Offset, skew, and drift of a timing mechanism are all with respect to a reference clock. Clocks can be read, set, or reset (to an initial state), but mostly they must march merrily along. Timers, on the other hand, have an origin (as do clocks) but they also generate timeout events. The current time of a timer is the amount of time that must elapse before a timeout occurs. A timer is always associated with a particular clock. A retriggerable timer resets after a timeout event and starts again from its nominal timeout value, while a nonretriggerable timer generates a single timeout event and then stops.

There are two kinds of time events: a timeout event and a clock interrupt. A clock interrupt is a periodic event generated by the clock representing the fundamental timing frequency. A timeout event is the result of achieving a specified time from the start of the timer.

It might seem odd at first, but the concepts of concurrency are not the same as the concepts of scheduling. Scheduling is a more detailed view with the responsibility of executing the mechanisms necessary to make concurrency happen. A scheduling context includes an execution engine (scheduler) that executes a scheduling policy, such as round robin, cyclic executive, or preemptive. In addition, the execution engine owns a number of resources, some of which are scheduled in accordance with the policy in force. These resources have actions, and the actions execute at some priority with respect to other actions in the same or other resources.

Operating systems, of course, provide the execution engine and the policies from which we select the one(s) we want to execute. The developer provides the schedulable resources in the forms of tasks («active» objects) and resources that may or may not be protected from simultaneous access via mechanisms such as monitors or semaphores. Such systems are fairly easy to put together, but there is (or should be!) concern about the schedulability of the system, that is, whether or not the system can be guaranteed to meet its timeliness requirements.

Determining a scheduling strategy is crucial for efficient scheduling of real-time systems. Systems no more loaded than 30% have failed because of poorly chosen scheduling policies.^[14] Scheduling policies may be stable, optimal, responsive, and/or robust. A stable policy is one in which, in an overload situation, it is possible to a priori predict which task(s) will miss their timeliness requirements. Policies may also be optimal.^[15] A responsive policy is one in which incoming events are handled in a timely way. Lastly, by robust, we mean that the timeliness of one task is not affected by the misbehavior of another. For example, in a round robin scheduling policy, a single misbehaving task can prevent any other task in the system from running.

Many different kinds of scheduling policies are used. Scheduling policies can be divided into two categories: fair policies and priority policies. The first category schedules things in such a way that all tasks progress more or less evenly. Examples of fair policies are shown in Table 1-2.

In contrast, priority-driven policies are unfair because some tasks (those of higher priority) are scheduled preferentially to others. In a priority schedule, the priority is used to select which task will run when more than one task is ready to run. In a preemptive priority schedule, when a ready task has a priority higher than that of the running task, the scheduler preempts the running task (and places it in a queue of tasks ready to run, commonly known as the “ready queue”) and runs the highest-priority ready task. Priority schedulers are responsive to incoming events as long as the priority of the task triggered by the event is a higher priority than the currently running tasks. In such systems, interrupts are usually given the highest priority.

Two competing concepts are importance and urgency. Importance refers to the value of a specific action's completion to correct system performance. Certainly, correctly adjusting the control surface of an aircraft in a timely manner is of greater importance than providing flicker-free video on a cabin DVD display. The urgency of an action refers to the nearness of its deadline for that action without regard to its importance. The urgency of displaying the next video frame might be much higher than the moment-by-moment actuation control of the control surfaces, for example. It is possible to have highly important, yet not urgent actions, and highly urgent but not important ones mixed freely within a single system. Most scheduling executives, however, provide only a single means for scheduling actions—priority. Priority is an implementation-level solution offered to manage both importance and urgency.

All of the priority-based scheduling schemes in Table 1-3 are based on urgency. It is possible to also weight them by importance by multiplying them by an importance factor w_j and then set the task priority equal to the product of the unweighted priority and the importance factor. For example, in RMS scheduling the task priority would be set to

Equation 1-1. Importance-Weighted Priority

Where p_j is the priority of task j, w_j is some measure of the importance of the completion of the task, and C_j is the period of task j. [10] provides a reasonably rigorous treatment of weighted scheduling policies for generalized scheduling algorithms. Note that some operating systems use ascending priority values to indicate higher priority while others use descending priorities to indicate higher priority.

Since essentially all real-time systems running multiple tasks must coordinate those tasks and share resources, the manner in which those resources are managed is crucial not only to the correct operation of the system but also to its schedulability. The fundamental issue is the protection of the resource from corruption due to interleaved writing of the values or from a reader getting an incorrect value because it read partway through an update from another task. Of course, for physical resources, there may be other integrity concerns as well, due to the nature of the physical process being managed. The most common basic solution is to serialize the access to the resource and prevent simultaneous access. There are a number of technical means to accomplish this. For example, access can be made atomic—that is, no other task is allowed to run when one task owns a resource. Such accesses are made during what is called a critical section. This approach completely prevents simultaneous access but is best suited when the access times for the resource are very short relative to the action completion and deadline times [11]. Atomic access also breaks the priority-based scheduling assumption of infinite preemptibility (that is, when a task will run as soon as it is ready to run and the highest priority ready task in the system). However, if the critical section isn't too long, then a mild violation of the assumption won't affect schedulability appreciably. When a resource must be used for longer periods of time, the use of critical sections is not recommended.

Another common approach to access serialization is to queue the requests. That is useful when the running task doesn't have to precisely synchronize with the resource, but wants to send it a message. Queuing a message is a “send-and-forget” kind of rendezvous that works well for some problems and not for others, depending on whether the resource (typically running in its own thread in this case) and the client must be tightly coupled with respect to time. For example, sending a time-stamped log entry to a logging database via a queue allows the sending task to send the message and go on about its business, knowing that eventually the database will handle the log entry. This would not be appropriate in a real-time control algorithm in which a sensor value is being used to control a medical laser, however.

A third common approach to access serialization is protect the resource with a mutual exclusion (mutex) semaphore. The semaphore is an OS object that protects a resource. When access is made to an unlocked resource, the semaphore allows the access and locks it. Should another task come along and attempt to access the resource, the semaphore detects it and blocks the second task from accessing the resource—the OS suspends the task allowing the original resource client to complete. Once complete, the resource is unlocked, and the OS then allows the highest-priority task waiting on that resource to access it, while preventing other tasks from accessing that resource. When a task is allowed to run (because it owns a needed resource) even though a higher-priority task is ready to run, the higher-priority task is said to be blocked.

While this approach works very well, it presents a problem for schedulability called unbounded priority inversion. When a task is blocked, the system is said to be in a condition of priority inversion because a lower-priority task is running even though a higher-priority task is ready to run. In Figure 1-4, we see two tasks sharing a resource,^[17] HighPriorityTask and the LowPriorityTask. In the model presented here, a low-priority value means the task is a high priority. Note that there is a set of tasks on intermediate priority, Task1 through Task_n, and that these tasks do not require the resource. Therefore, if LowPriorityTask runs and locks the resource, and then HighPriorityTask wants to run, it must block to allow LowPriorityTask to complete its use of the resource and release it. However, the other tasks in the system are of higher priority than LowPriorityTask and then can (and will) preempt LowPriority Task when they become ready to run. This, in effect, means that the highest priority task in the system is blocked not only by the LowPriority Task, but potentially by every other task in the system. Because there is no bound on the number of these intermediate priority tasks, this is called unbounded priority inversion. There are strategies for bounding the priority inversion and most of these are based on the temporary elevation of the priority of the blocking task (in this case, LowPriority Task). Figure 1-5 illustrates the problem in the simple implementation of semaphore-based blocking.

Figure 1-4. Priority Inversion Model

Figure 1-5. Priority Inversion Scenario

As mentioned, there are a number of solutions to the unbounded priority inversion problem. In one of them, the Highest Locker Pattern of [11] (see also [9,12]), each resource has an additional attribute—its priority ceiling. This is the priority just above that of the highest-priority task that can ever access the resource. The priority ceiling for each resource is determined at design time. When the resource is locked, the priority of the locking task is temporarily elevated to the priority ceiling of the resource. This prevents intermediate priority tasks from preempting the locking task as long as it owns the resource. When the resource is released, the locking task's priority is reduced to either its nominal priority or to the highest priority ceiling of any resources that remain locked by that task. There are other solutions with different pros and cons that the interested reader can review.

An important aspect of schedulability is determining whether or not a particular task set can be scheduled, that is, can it be guaranteed to always meet its timeliness requirements? Because timeliness requirements are usually expressed as deadlines, that is the case we will consider here.

When a task set is scheduled using RMS, then certain assumptions are made. First, the tasks are time-driven (i.e., periodic). If the tasks are not periodic, it is common to model the aperiodic tasks using the minimum interarrival time as the period. While this works, it is often an overly strong condition—that is, systems that fail this test may none theless be schedulable and always meet their deadlines, depending on the frequency with which the minimum arrival time actually occurs. The other assumptions include infinite preemptibility (meaning that a task will run immediately if it is now the highest-priority task ready to run) and the deadline occurs at the end of the period. In addition, the tasks are independent—that is, there is no blocking. When these things are true, then Equation 1-2 provides a strong condition for schedulability. By strong, we mean that if the inequality is true, then the system is schedulable; however, just because it's not true does not imply necessarily that the system is not schedulable. More detailed analysis might be warranted for those cases.

Equation 1-2. Basic Rate Monotonic Analysis

In Equation 1-2, C_j is the execution time for the task. In a worst-case analysis, this must be the worst-case execution time (i.e., worst-case completion time). T_j is the period of the task, and n is the number of tasks. The ratio C_j/T_j is called the utilization of the task. The expression on the right side of the inequality is called the utilization bound for the task set (note that 2 is raised to the power of (1/n)). The utilization bound converges to about 0.69 as the number of tasks grows. It is less than 1.0 because in the worst case, the periods of the tasks are prime with respect to each other. If the task periods are all multiples of each other (for example, periods of 10, 100, 500), then a utilization bound of 100% can be used for this special case (also for the case of dynamic priority policies, such as EDS). As an example, consider the case in which we have four tasks, as described in Table 1-4.

The sum of the utilizations from the table is 0.7. The utilization bound for four tasks is 0.757; therefore, we can guarantee that this set of tasks will always meet its deadlines.

The most common serious violation of the assumptions for Equation 1-2 is the independence of tasks. When one task can block another (resource sharing being the most common reason for that), then blocking must be incorporated into the calculation, as shown in Equation 1-3.

In this equation, B_j is the worst-case blocking for task j. Note that there is no blocking term for the lowest-priority task (task n). This is because the lowest-priority task can never be blocked (since it is normally preempted by every other task in the system).

Equation 1-3. Rate Monotonic Analysis with Blocking

As mentioned above, it is necessary to take into account any chained blocking in the blocking term. That is, if one task can preempt a blocking task then the blocking term for the blocking task must take this into account. For example, in the model shown in Figure 1-5, the blocking term for HighPriorityTask must include the time that Low PriorityTask locks the resource plus the sum of the worst-case execution time for all the intermediate-priority tasks (because they can preempt LowPriorityTask while it owns the resource), unless some special measure is used to bound the priority inversion.

Detailed treatment of the analysis of schedulability is beyond the scope of this book. The interested reader is referred to [5,9,12], for a more detailed discussion of timeliness and schedulability analysis.

Performance modeling is similar to modeling schedulability. However, our concerns are not meeting specific timeliness requirements but capturing performance requirements and ensuring that performance is adequate. Performance modeling is important for specifying performance requirements, such as bandwidth, throughput, or resource utilization, as well as estimating performance of design solutions. The measures of performance commonly employed are resource utilization, waiting times, execution demands on the hardware infrastructure, response times, and average or burst throughput—often expressed as statistical or stochastic parameters. Performance modeling is often done by examining scenarios (system responses in specific circumstances such as a specific load with specified arrival times) and estimating or calculating the system response properties. Performance analysis is done either by application of queuing models to compute average utilization and throughput or via simulation. This often requires modeling the underlying computational hardware and communications media as well.

One key concept for performance modeling is workload. The workload is a measure of the demand for the execution of a particular scenario on available resources, including computational resources (including properties such as context switch time, some measure of processing rate, and whether the resource is preemptible). The priority, importance, and response times of each scenario are required for this kind of analysis. The properties of the resources used by the scenarios that must be modeled are capacity, utilization (percentage of usage of total available capacity), access time, response time, throughput, and how the resources are scheduled or arbitrated. Chapter 4 discusses the UML Profile for Schedulability, Performance, and Time, and its application for modeling performance aspects.

The current state-of-the-art in software development process relies on a small number of important principles:

Using these six principles, even the most demanding and complex real-time and embedded system can be effectively developed. Most development methodologies in practice today utilize these principles—some more effectively than others, mind you—and the approach I recommend is no different.

The microcycle is the “spiral” portion of the process, lasting usually four to six weeks (although if it's somewhat shorter or longer than this, it really doesn't matter) and resulting in a single incremental version of the system (called a prototype) that meets a specific mission. The prototype mission is usually a combination of some set of use cases (capabilities or coherent sets of requirements), reduction of some specific risks, and/or the addition of some set of technologies.

The microcycle, or spiral, shown in Figure 1-8, is divided into five primary microphases:

Figure 1-8. ROPES Spiral

We can see that there is a systems engineering subphase in the analysis microphase. This does not mean or imply that it is only during this period that system engineers are doing useful work. Rather, it defines a particular set of activities resulting in a particular set of artifacts released at the end of the subphase. The workflow of the systems engineer is discussed in more detail later in this book.

The spiral approach is a depth-first approach of system development. Although in the first party phase, the expected use cases are named and roughly scoped, they are not detailed until the project matures to that point in the schedule. Thus, development proceeds without a detailed understanding of all of the requirements; instead, the focus is on the higher-risk issues and requirements, so that they are completely understood before those of lesser risk and significance are detailed. The early testing of the high-risk and high-importance aspects of the system reduces risk optimally, and the early and frequent testing ensures that the system produced is of high quality.

The major activities in the ROPES spiral are:

These activities may be arranged in many different ways. Such an arrangement defines the development process used for the project. The iterative development process looks like Figure 1-8.

The iterative development process model shown in Figure 1-8 is known as ROPES, for rapid object-oriented process for embedded systems (see [5] for a more complete description). Each iteration produces work products, known as artifacts. A single iteration pass, along with the generated artifacts, is shown in Figure 1-9. This model is somewhat simplified in that it doesn't show the subphases of analysis and design, but does capture the important project artifacts, how they are created and used.

Figure 1-9. ROPES Process Artifacts

Rhapsody from I-Logix^[22] is an advanced model creation tool with integrated product-quality code generation and design-level testing capabilities built in. Rhapsody was developed specifically to aid in the development of real-time and embedded systems, and integrates smoothly into the ROPES process model. Fully constructive tools, such as Rhapsody assist by providing support for all of the precepts mentioned at the beginning of this section. Although the UML in general and the ROPES process in particular can be applied using manual means for translation of models into code and debugging and testing that code, the use of such powerful automated tools greatly enhances their effectiveness. shows how a fully constructive tool can aid in the generation of development phase artifacts. Table 1-5 shows which artifacts are created in the various phases of the ROPES process.

There are two primary reasons projects are estimated and scheduled. These two reasons are incompatible and mutually exclusive. Nevertheless, they are often combined—with disastrous results.

The primary reason for estimating and scheduling projects is to plan—and this requires the understanding of the cost and resource and time-based properties of the project. For example:

These are legitimate business questions and can only be answered with accurate schedules constructed from reasonable estimates.

The other primary use for schedules is motivation. Motivational (i.e., optimistic) schedules are used to inspire workers to apply their lazy selves to the project at hand and not goof off. Also to donate their nonwork time (i.e., professional time) to the project. To accomplish this motivation, the project requires a sense of urgency, and this is instilled by constructing a schedule that is unachievable without Herculean efforts, if at all. An accurate schedule is actually an impediment to this motivational goal, so that the two primary uses for schedules are in fact at odds with each other.

The real difficulty arises when a schedule is used for both purposes. The schedule is constructed to be optimistic but then used as if it were an accurate planning tool. The first step to estimating and scheduling projects is to select for which of these purposes the schedule is to be used. If it is to be used to plan, then the goal should be an accurate schedule. If it is to motivate, then an urgent schedule should be created. If both are needed, then you need to create two different schedules.

In reality, the only really appropriate use for schedules is for planning. In my experience, the vast majority of engineers are highly motivated, hardworking professionals^[23] who respond best to being treated as if they were. For this reason, we will assume that our goal is the first purpose—the creation of schedules that are accurate and reasonable so that they are useful tools for planning. We will relegate the use of motivational schedules to the Dilbertesque business environments where they belong.

As a group, we engineers fail miserably at accurately estimating how long things will take. Studies of just how bad we are at this abound in the literature. In one 1995 study, 53% of all projects were almost 200% over budget and 31% were cancelled after being started. Other and more recent studies confirm these results. In a more recent study, 87% of the projects missed functionality expectations, 73% were delivered late, and a full 18% of the projects were so off the mark that they were cancelled after development had completed.

There are many reasons why this is true. The primary reason for such incredibly poor estimation success, in my experience, is because engineers are actively encouraged not to be accurate. For example, one manager told me, in response to my estimate for a project, “That's the wrong number. Go do it again.” Of course, this anti-accuracy bias is based in the desire for motivational, rather than accurate, schedules. While the desire itself may be well meant (such as maximizing fourth-quarter revenue), one cannot ignore the facts without consequence.

Even if being done with the best of intentions, estimation is hard! Estimation is inherently more inaccurate than observation for obvious reasons. Good estimation is possible, but it will never be as accurate as hindsight in principle. A good estimate must come to embrace uncertainty as a way of life but understand that the more you know the more accurate your estimates will be. The further along you are in the project, the more accurate your estimates will be. Schedule management must in principle include refinement of estimates and the schedule over time, resulting in ever-increasing accurate forecasts. In practice, few engineers are trained in estimation or even rewarded for accuracy; in fact, far too often, engineers are actively encouraged to give inaccurately low estimates.

The ROPES process provides means for both constructing estimates and for improving one's ability to estimate. These (sub)processes are known as BERT and ERNIE.

Constructing Estimates: The BERT Approach

Bruce's Evaluation and Review Technique (BERT) is the ROPES way of constructing estimates. Estimates are always applied to estimable work units (EWUs). EWUs are small, atomic tasks typically no more than 80 hours in duration.^[24] The engineer estimating the work provides three estimates:

• The mean (50%) estimate

• The optimistic (20%) estimate

• The pessimistic (80%) estimate

Of these, the most important is the 50% estimate. This estimate is the one that the engineer will beat half of the time. The central limit theorem of statistics states that if all of the estimates are truly 50% estimates, then overall the project will come in on time. However, this estimate alone does not provide all necessary information. You would also like a measure of the perceived risk associated with the estimate. This is provided by the 20% and 80% estimates. The former is the time that the engineer will beat only 20% of the time, while the latter will be beat 80% of the time. The difference between these two estimates is a measure of the confidence the engineer has in the estimate. The more the engineer knows, the smaller that difference will be.

These estimates are then combined to come up with the estimate actually used in the schedule using equation 1-4.

Equation 1-4. Computing Used Estimate for Scheduling

The estimate confidence (EC) factor is based on the particular engineer's accuracy history. An ideal estimator would have an EC value of 1.00. Typical EC values range from 1.5 to 5.0. As an estimator's ability to estimate improves, that number gets smaller over time, (hopefully) approaching 1.00.

A schedule is a sequenced arrangement of EWUs taking into account which can be run in parallel and which must be serialized. Further, the schedule must take into account inherent dependencies, level of risk, and the availability of personnel.

The waterfall lifecycle scheduling is often considered more accurate by naïve managers because schedules are constructed early and may be tracked against for the remainder of the project. However, this ignores the fundamental rule of scheduling: The more you know, the more accurate you can be. Early schedules are inherently inaccurate because you know less than you do one third, one half, or even seven eights of the way through a project than you do at the end. So it is ridiculous in principle to state at the outset of a project that it will be done in 18 months, 3 days, 6 hours, 42 minutes, and 13 seconds. Nevertheless, managers often act as if they can dictate the passage of time and the invention of software.

The BERT and ERNIE approach can be applied to waterfall or spiral projects. In either approach, though, early estimates will be less accurate than later refinements, when later refinements take into account information gleaned from observing the progress of the project. In principle, I believe the following accuracies for a waterfall lifecycle are achievable:^[25]

When schedules are first constructed, in the concept phase, “10 person-years” means, in fact, anywhere from 5 to 15 person-years. If you need a hard number, then go with 15, but if your estimation process is fairly good, then 10 will be the most accurate single number you can provide.

In the spiral approach, the milestones are not the end of these waterfall phases, but instead planned prototypes. If you plan for 10 prototypes, then your first working schedule will have 10 primary milestones, one for each prototype. On average, these will usually be four to six weeks apart, but some may be longer or shorter, depending on their scope. If you want to construct larger-scale milestones, similar to preliminary design review (PDR) and critical design review (CDR) called out by some development methodologies, then you (somewhat arbitrarily) say that one prototype (say 3) will form the basis of the PDR and a later one (say 6) will form the basis of the CDR.

The ROPES scheduling approach uses the Central Limit Theorem from statistics, which states that if you take enough samples from a population, your accumulated samples will form a Gaussian distribution. What that means is that if you have enough estimates of the pieces and they are in fact 50% estimates, then half of them will be early, half of them will be late, and overall, your project will be on time.

That having been said, schedules must be not only tracked against, but also managed and maintained. Assessment and realignment of the schedule is one of the primary activities done in the so-called party phase of the ROPES microcycle.

Figure 1-12 shows a constructed schedule using prototypes as the primary scheduling points on a Gantt chart. Each prototype has a mission, defined to be a set of requirements (normally one to a small number of use cases) to be developed and a set of risks to be reduced. In the figure, the first such prototype, called “Hello World,” is subdivided into the microcycle phases, each with some time attached to it. We see that in this particular example, PDR, CDR, and customer review activities are specifically scheduled. This schedule is tracked against on a daily, or at least weekly, basis, and modified to incorporate new information as it becomes available. The net result is a self-correcting schedule that improves over time.

Figure 1-12. Sample Schedule

Other scheduling views are important as well—especially the resource view that shows how your people are mapped against the schedule. Special care must be taken to ensure that they are neither over- nor underutilized in your schedule.

Figure 1-13 is a resource histogram showing the loading of a resource over time.^[26] In the example, you want to be sure to neither over- nor underutilize the resource. This means that for a typical eight-hour workday, you should not assume more than four to six hours of productive work effort per day, the actual value of which varies according to the business environment. You should also not assume that a work year is more than 45 weeks, to account for sick and vacation time,^[27] training, and other business activities that may be not directly related to your project.

Figure 1-13. Resource Histogram

Figure 1-12 shows a highly serial set of prototypes. It is possible to run some prototypes in parallel and merge them together in a future prototype. This makes the schedule a bit more complex, but it may be more optimal. The important thing is to come up with a plan that you actually intend to follow. This allows you to be more accurate and to effectively track against the plan to see how you're doing.

Tracking against the schedule is crucial. In virtually all things, the earlier you try to correct something, the cheaper and easier it is. This is especially true with schedules. This means that you must schedule what actually is supposed to happen and must identify deviations from that plan. If you have a schedule but it does not reflect how the work is being done, you cannot track against it. The work against the EWUs (such as the “Design Phase of Prototype 3”) must be tracked if you want to be able to make adjustments, either to take advantage of the fact that it is coming in early or to adjust for the fact that it appears to be coming in late. The earlier you have this information, the easier that adjustment process will be.

Adjusting the schedule may involve

Schedules are dynamic entities that change over time. They are never completely accurate, except perhaps in hindsight, but a good scheduler can take advantage of the elasticity of a schedule and use it to guide the management of the project to a successful conclusion.

The reasons for worrying about model organization are to

At first blush, it might appear that the first two issues—contributing and using aspects of a common model—are dealt with by configuration management (CM). This is only partially true. CM does provide locks and checks such that only one worker can own the “write token” to a particular model element and other users can only have a “read token.” However, this is a little like saying that C solves all your programming problems because it provides basic programmatic elements such as assignment, branching, looping, and so on. CM does not say anything about what model elements ought to be configuration items (CIs), only that if a model element is a CI, then certain policies of usage apply. Effective model organization uses the CM infrastructure but provides a higher-level set of principles that allow the model to be used effectively.

For example, it would be awkward in the extreme if the entire model were the only CI. Then only a single worker could update the model at a time. This is clearly unacceptable in a team environment. The other extreme would be to make every model element at CI—for example, every class and use case would be a separate CI. Again, in simple systems, this can work because there are only a few dozen total model elements, so it is not too onerous to explicitly check out each element on which you need to work. However, this does not work well on even medium-scale systems. You would hate to have to individually list 30 or 40 classes when you wanted to work on a large collaboration realizing a use case.

The UML provides an obvious organizational unit for a CI—the package. A UML package is a model element that contains other model elements. It is essentially a bag into which we can throw elements that have some real semantic meaning in our model, such as use cases, classes, objects, diagrams, and so on. However, UML does not provide any criteria for what should go into one package versus another. So while we might want to make packages CIs in our CM system, this begs the question as to what policies and criteria we should use to decide how to organize our packages—what model elements should go into one package versus another.

A simple solution would be to assign one package per worker. Everything that Sam works on is in SamPackage, everything that Julie works on is in JuliePackage, and so on. For very small project teams, this is in fact a viable policy. But again, this begs the question of what Sam should work on versus Julie. It can also be problematic if Susan wants to update a few classes of Sam's while Sam is working on some others in SamPackage. Further, this adds artificial dependencies of the model structure on the project team organization. This will make it more difficult to make changes to the project team (say to add or remove workers) and will really limit the reusability of the model.

It makes sense to examine the user workflow when modeling or manipulating model elements in order to decide how best to organize the model. After all, we would like to optimize the workflow of the users as much as possible, decoupling the model organization from irrelevant concerns. The specific set of workflows depends, of course, on the development process used, but there are a number of common workflows:

When working on related requirements and use cases, the worker typically needs to work on one or more related use cases and actors. When detailing a use case, a worker will work on a single use case and detailed views—a set of scenarios and often either an activity diagram or a statechart (or some other formal specification language). When elaborating a collaboration, the user will need to create a set of classes related to a single use case, as well as refining the scenarios bound to that use case. These workflows suggest that one way to organize the requirements and analysis model is around the use cases. Use packages to divide up the use cases into coherent sets (such as those related by generalization, «includes», or «extends» relations, or by associating with a common set of actors). In this case, a package would contain a use case and the detailing model elements—actors, activity diagrams, statecharts, and sequence diagrams.

The next set of workflows (realizing requirements) focus on classes, which may be used in either analysis or design. A domain, in the ROPES process, is a subject area with a common vocabulary, such as User Interface, Device I/O, or Alarm Management. Each domain contains many classes, and system-level use case collaborations will contain classes from several different domains. Many domains require rather specialized expertise, such as low-level device drivers, aircraft navigation and guidance, or communication protocols. It makes sense from a workflow standpoint (as well as a logical standpoint) to group such elements together because a single worker or set of workers will develop and manipulate them. Grouping classes by domains and making the domains CIs may make sense for many projects.

Architectural workflows also require effective access to the model. Here, the architecture is broken up into the logical architecture (organization of types, classes, and other design-time model elements) and physical architecture (organization of instances, objects, subsystems, and other runtime elements). It is common for the logical architecture to be organized by domains and the physical architecture to be organized around components or subsystems. If the model is structured this way, then a domain, subsystem, or component is made a CI and assigned to a single worker or team. If the element is large enough, then it may be further subdivided into subpackages of finer granularity based on subtopic within a domain, subcomponents, or some other criterion such as team organization.

Testing workflows are often neglected in the model organization, usually to the detriment of the project. Testing teams need only read-only access to the model elements under test, but nevertheless they do need to manage test plans, test procedures, test results, test scripts, and test fixtures, often at multiple levels of abstraction. Testing is often done at many different levels of abstraction but can be categorized into three primary levels: unit testing (often done by the worker responsible for the model element under test), integration (internal interface testing), and validation (black-box system level testing). Unit-level testing is usually accomplished by the owner of the model element under test or a “testing buddy” (a peer in the development organization). The tests are primarily white-box, design, or code-level tests and often use additional model elements constructed as test fixtures. It is important to retain these testing fixture model elements so that as the system evolves, we can continue to test the model elements. Since these elements are white box and tightly coupled with the implementation of the model elements, it makes the most sense to colocate them with the model elements they test. So, if a class myClass has some testing support classes, such as myClass_tester and myClass_stub, they should be located close together. If the same worker is responsible for all, then perhaps they should be located within the same package (or another package in the same scope). If a testing buddy is responsible, then it is better to have it in another package but make sure that it is in the same CI as the model elements under test.

Integration and validation tests are not so tightly coupled as at the unit level, but clearly the testing team may construct model elements and other artifacts to assist in the execution of those tests. These tests are typically performed by different workers than the creators of the model elements they test. Thus, independent access is required and they should be in different CIs.

It is important to be able to efficiently construct and test prototypes during the development process. This involves both tests against the architecture (the integration and testing activities) and against the entire prototype's requirements (validation testing activities). There may be any number of model elements specifically constructed for a particular prototype that need not be used anywhere else. It makes sense to include these in a locale specific to that build or prototype. Other artifacts, such as test fixtures that are going to be reused or evolved and apply to many or all prototypes should be stored in a locale that allows them to be accessed independently from a specific prototype. Tools such as I-Logix iNotion™ provide company-wide repositories, access, and control over the complete sets of management, development, marketing, and manufacturing artifacts.

In the preceding discussion, we see that a number of factors influence how we organize our models: the project team organization, system size, architecture, how we test our software, and our project lifecycle. Let us now consider some common ways to organize models and see where they fit well and where they fit poorly.

The model organization shown in Figure 1-14 is the simplest organization we will consider. The system is broken down by use cases, of which there are only three in the example. The model is organized into four high-level packages: one for the system level and one per use case. For a simple system with three to 10 use cases, and perhaps one to six developers, this model can be used with little difficulty. The advantages of this organization are its simplicity and the ease with which requirements can be traced from the high level through the realizing elements. The primary disadvantages of this approach are that it doesn't scale up to medium- or large-scale systems. Other disadvantages include difficulty in reuse of model elements and that there is no place to put elements common to multiple use case collaborations, hence a tendency to reinvent similar objects. Finally, there is no place to put larger-scale architectural organizations in the model, and this further limits its scalability to large systems.

Figure 1-14. Use Case-Based Model Organization

The model organization shown in Figure 1-15 is meant to address some of the limitations of the use case-based approach. It is still targeted toward small systems, but adds a Framework package for shared and common elements. The Framework package has subpackages for usage points (classes that will be used to provide services for the targeted application environment) and extension points (classes that will be subclassed by classes in the use case packages). It should be noted that there are other ways to organize the Framework area that work well too. For example, Frameworks often consist of sets of coherent patterns—the subpackaging of the Framework can be organized around those patterns. This organization is particularly apt when constructing small applications against a common Framework. This organization does have some of the same problems with respect to reuse as the use case-based model organization.

Figure 1-15. Framework-Based Model Organization

As mentioned early on, if the system is simple enough, virtually any organization can be made to work. Workflow and collaboration issues can be worked out ad hoc and everybody can get their work done without serious difficulty. A small application might be 10 to 100 classes realizing 3 to 10 use cases. Using another measure, it might be on the order of 10,000 or so lines of code.

One of the characteristics of successful large systems (more than, say, 300 classes) is that they are architecture-centric. That is, architectural schemes and principles play an important role in organizing and managing the application. In the ROPES process, there are two primary subdivisions of architecture—logical and physical.^[28] The logical model organizes types and classes (things that exist at design time), while the physical model organizes objects, components, tasks, and subsystems (things that exist at runtime). When reusability of design classes is an important goal of the system development, it is extremely helpful to maintain this distinction in the model organization.

The next model organization, shown in Figure 1-16, is suitable for large-scale systems. The major packages for the model are

Figure 1-16. Logical Model-Based Model Organization

The system package contains elements common to the overall system—system level use cases, subsystem organization (shown as an object diagram), and system-level actors. The logical model is organized into subpackages called domains. Each domain contains classes and types organized around a single subject matter, such as User Interface, Alarms, Hardware Interfaces, Bus Communication, and so on. Domains have domain owners—those workers responsible for the content of a specific domain. Every class in the system ends up in a single domain. Class generalization hierarchies almost always remain within a single domain, although they may cross package boundaries within a domain.

The physical model is organized around the largest-scale pieces of the system—the subsystems. In large systems, subsystems are usually developed by independent teams, thus it makes sense to maintain this distinction in the model. Subsystems are constructed primarily of instances of classes from multiple domains. Put another way, each subsystem contains (by composition) objects instantiated from different domains in the system.

The last major package is builds. This area is decomposed into subpackages, one per prototype. This allows easy management of the different incremental prototypes. Also included in this area are the test fixtures, test plans, procedures, and other things used to test each specific build for both the integration and validation testing of that prototype.

The primary advantage of this model organization is that it scales up to very large systems very nicely because it can be used recursively to as many levels of abstraction as necessary. The separation of the logical and physical models means that the classes in the domains may be reused in many different deployments, while the use of the physical model area allows the decomposition of system use cases to smaller subsystem-level use cases and interface specifications.

The primary disadvantage that I have seen in the application of this model organization is that the difference between the logical and physical models seems tenuous for some developers. The model organization may be overly complex when reuse is not a major concern for the system. It also often happens that many of the subsystems depend very heavily (although never entirely) on a single domain, and this model organization requires the subsystem team to own two different pieces of the model. For example, guidance and navigation is a domain rich with classes, but it is usually also one or more subsystems.

The last model organization to be presented, shown in Figure 1-17, is similar to the previous one, except that it blurs the distinction between the logical and physical models. This can be appropriate when most or all subsystems are each dominated by a single domain. In this case, the domain package is decomposed into one package for each domain, and each of these is further decomposed into the subsystems that it dominates. For common classes, such as bus communication and other infrastructure classes, a separate shared Framework package is provided to organize them, similar to the Framework-based model organization shown in Figure 1-15.

Figure 1-17. Physical Model-Based Model Organization