Design of Multithreaded Software

The Entity-Life Modeling Approach

Bo I. Sanden

• Publisher: Wiley-IEEE Computer Society Pr
• Year: 2011
• Print ISBN: 9780470876596
• eBook ISBN: 9781118102732
• Edition: 1
• Topic: Computer Science
• Subtopic: Systems Architecture
• Index: Computer Science

This book assumes familiarity with threads (in a language such as Ada, C#, or Java) and introduces the entity-life modeling (ELM) design approach for certain kinds of multithreaded software. ELM focuses on "reactive systems," which continuously interact with the problem environment. These "reactive systems" include embedded systems, as well as such interactive systems as cruise controllers and automated teller machines.

Part I covers two fundamentals: program-language thread support and state diagramming. These are necessary for understanding ELM and are provided primarily for reference. Part II covers ELM from different angles. Part III positions ELM relative to other design approaches.

PART I
FOUNDATIONS

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, 1954¹

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.²
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 ...

Table of contents

• Cover
• Table of Contents
• Title
• Copyright
• Foreword
• Preface
• PART I: FOUNDATIONS
• PART II: THE ELM WAY
• PART III: BACKGROUND AND DISCUSSION
• Glossary
• References
• Index
• End User License Agreement