Chapter 1
Introduction

"Begin at the beginning," the King said gravely, "and go on till you come to the end; then stop."

LEWIS CARROLL, ALICE'S ADVENTURES IN WONDERLAND, 1865

"Begin at the middle," Mason said.

ERLE STANLEY GARDNER, THE CASE OF THE FUGITIVE NURSE, 19541

1.1 ENTITY-LIFE MODELING

At first sight, the idea of any rules or principles being superimposed on the creative mind seems more likely to hinder than to help, but this is quite untrue in practice. Disciplined thinking focuses inspiration rather than blinkers it.

GLEGG, 1969

Much threaded software deals with events occurring either in the real world or in some simulated world. Such problem environments are commonly rich in structures on which we can build the software. This book shows what structures to look for. It introduces entity-life modeling (ELM), an approach for designing dynamically scheduled, multithreaded software.

With ELM, we pattern the threads in the software on event threads found in the problem domain and a thread architecture on an event-thread model of the domain. An event thread often represents the life history of some entity in the domain, whence the term entity-life modeling. Here are its main properties:

1. ELM bases multithreading on a simple, intuitive principle in the manner of object orientation where we model classes in the software as well as their relationships on domain objects and their relationships. ELM puts thread structuring on par with class structuring.
2. ELM is practical. It proposes no new definition of concurrency but builds on threading concepts that programmers have used for decades. Such classic multithreading involves two kinds of participants:
3. 1. Threads, such as those in Java or C#, Pthreads, or Ada tasks.2
4. 2. Shared objects that are "thread safe." This means that each object enforces mutual exclusion on the threads that attempt to call its operations. In Java, such objects are called synchronized; in Ada, protected. I shall use the neutral term safe objects.

   Classic multithreading is directly implementable, which is important in real-time and systems programming. It's also flexible; indeed, it lets us write "wildly nondeterministic" programs (Lee, 2006). The guard against that is design discipline:

5. To rein in the untrammeled nondeterminism, ELM requires that all threads be part of a thread architecture, which is a defined structure of threads and safe objects. ELM helps designers quickly identify the major candidate thread architectures for a given problem. Choosing the right architecture can make a critical difference: One architecture may require a much greater programming effort than another and may incur much greater runtime overhead.
6. ELM is a constructive approach to threading. Classic multithreading isn't as tractable formally as other concurrency models where, for instance, deadlock can be detected analytically. With ELM, we deal with deadlock as a practical issue and construct the thread architecture to be deadlock free.
7. ELM is a design principle, not a stepwise method. It bases thread architectures directly on the problem domain. You don't have to take on faith that some long procession of steps will lead to a workable solution.

Because object orientation is now widely accepted, I assume in parts of the book that control threads operate on instances of classes. But ELM isn't limited to object-oriented software; you can use it just as well in C or even an assembly language as long as threads and mutual exclusion are supported. Safe objects needn't be instances of classes but can be singleton modules, as in some of the Ada examples. ELM doesn't rely on such potentially costly, object-oriented features as dynamic binding-but doesn't preclude them either.

ELM threads capture a dynamic aspect of the problem domain that objects don't handle well. It makes thread modeling into a conceptual tool that differs from and complements object orientation. It attempts to make threading a practical, working abstraction that is as productive and expressive, if not as ubiquitous, as objects. Like object orientation, ELM promotes conceptual continuity from problem analysis through implementation: Event threads in the problem domain become control threads in the software.

ELM frees threading from such technical constraints of the day as limited processing capacity. This leaves such inherent concurrency issues as deadlock prevention and the general desire to make the architecture tractable.

1.1.1 Reactive Systems

ELM targets reactive systems. According to Harel, certain systems exhibit a "reactive behavior, whereby the system is not adequately described by specifying the output that results from a set of inputs but, rather, requires specifying the relationship of inputs and outputs over time. Typically, such descriptions involve complex sequences of events, actions, conditions, and information flow, often with explicit timing constraints, that combine to form the system's overall behavior" (Harel and Pnueli, 1985; Harel et al., 1990, p. 403)

Such a sequence of events is an event thread and can be described by a state machine together with the actions. Many actions impact the world outside the software. Unlike computations, they are often irreversible.

Reactive systems include those that operate in real time in the widest sense, such as embedded control systems as well as telephone switches; interactive systems from automated teller machines and gas pumps to travel reservation systems (Wieringa, 2003); and event-processing systems (Sommerville, 2007) such as many games. ELM also applies to discrete-event simulation based on the process interaction worldview.3 In other words, ELM finds multithreaded solutions in problem environments that are inherently concurrent.

1.2 OVERVIEW OF THIS BOOK

The book has three main parts: foundations, the ELM way, and background and discussion. Part I has three chapters:

1. Chapter 1 positions ELM within the field of software engineering. Section 1.6 ends the chapter by introducing relevant parts of the Unified Modeling Language (UML).
2. Chapter 2 covers the threading support in Ada and Java (including real-time Java) and discusses Pthreads briefly. Because ELM is tailored to how threads actually work, this is an important point of reference: In order to understand ELM and compare it with other design approaches, we must comprehend threading in some depth.
3. Chapter 3 deals with state modeling. Although a fair number of books cover it, I often find the treatment lacking. Many books make little distinction between a state diagram and a flowchart or a UML activity diagram.

Part II consists of four chapters, each focused on an aspect of ELM itself:

1. Chapter 4 introduces ELM, its rationale, and background.
2. Chapter 5 shows how to design software based on event threads and introduces the sequential-activities and concurrent-activities design patterns.
3. Chapter 6 introduces two event-thread patterns for resource sharing: the resource-user-thread and resource-guard-thread patterns. When we analyze a problem with shared domain resources, we can often choose one pattern or the other.
4. Chapter 7 extends the discussion of resource sharing to the case where an entity has simultaneous exclusive access to multiple resources. The focus is on deadlock prevention.

Part III has two chapters:

1. Chapter 8 discusses real-time software design and multithreading in general.
2. Chapter 9 traces the origins of ELM and is for those interested in methodology evolution. It gets a little personal as I relate the professional experiences that led me to develop ELM.

I try to contain most preaching and speculation in Chapters 1, 8, and 9 and keep the other chapters matter-of-fact. Yet I also want to convey the creative joy of software design and suggest possibilities that go beyond my examples. No doubt, ELM seems much more dry and forbidding in theory than in its application.

Should you consider reading the book cover to cover, be warned that Part I-particularly the massive Chapter 2-is quite comprehensive and included mostly for reference. Not all the information about threading in various languages is necessary for understanding the rest of the book.

For an overview of ELM, go straight to Part II, Chapter 4. Part II and Chapter 4 in particular define the terminology we need to discuss ELM. They give many examples of the realities from which the abstractions are drawn. Not all solutions are mine, but I put them in a systematic framework. Programmers like to design by analogy or by tweaking existing software. Some of the examples may be close enough to the reader's own problems for such reuse by reediting.

1.3 MULTITHREADING

As multiprocessors4 are becoming widespread, more programmers are confronted with threading. Many have easy access to Java, whose thread support works for many simple applications. Threads let us benefit from multiprocessors to speed up execution. They are also useful on a uniprocessor where one thread can compute while others may be waiting for...