Design of Multithreaded Software E-Book

Bo I. Sandén

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 623

Veröffentlichungsjahr: 2011

Beschreibung

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.

Leseprobe

Contents

Cover

Half Title page

Title page

Copyright page

Foreword

Preface

Acknowledgments

Program Excerpts

Headings and References

Exercises

Part I: Foundations

Chapter 1: Introduction

1.1 Entity-Life Modeling

1.2 Overview of This Book

1.3 Multithreading

1.4 Engineering the Intangible

1.5 The Development Process

1.6 Unified Modeling Language™

1.7 Conclusion

Chapter 2: Support for multithreading

2.1 Introduction

2.2 Concurrency in Java™

2.3 Concurrency in Ada

2.4 Pthreads

2.5 Conclusion

Exercises

Chapter 3: State modeling

3.1 Introduction

3.2 State-Modeling Terminology

3.3 Basic State Modeling

3.4 Superstates

3.5 Examples

3.6 State Modeling in Practice

3.7 State Machine Implementation

3.8 Conclusion

Exercises

Part II: The Elm Way

Chapter 4: Entity-Life Modeling

4.1 Introduction

4.2 Modeling Software on Event Threads

4.3 Discovering and Choosing Event-Thread Models

4.4 Event-Thread Patterns for Resource Sharing

*4.5 Portraying the World in Software

4.6 Conclusion

Appendix 4A: Summary of Terms

Exercises

Chapter 5: Design Patterns Based on Event Threads

5.1 Introduction

5.2 State Machines Without Software Activities

5.3 Sequential-Activities Design Pattern

5.4 Concurrent-Activities Design Pattern

5.5 Communicating State Machines

5.6 Conclusion

Exercises

Chapter 6: Event-thread patterns for resource sharing

6.1 Introduction

6.2 Resource-User-Thread Pattern

6.3 the Resource-Guard-Thread Pattern

6.4 Choosing and Combining Patterns

6.5 Examples With Dual Solutions

6.6 Data Stream Processing

6.7 Repository Problems

6.8 Conclusion

Exercises

Chapter 7: Simultaneous Exclusive Access to Multiple Resources

7.1 Introduction

7.2 the Deadlock Problem

7.3 Case Studies

7.4 Heuristics

7.5 More on Deadlock and Its Prevention

7.6 Conclusion

Exercises

Part III: Background and Discussion

Chapter 8: Real-Time Software Architectures and Data-Flow Design Approaches

8.1 Introduction

8.2 Real-Time Architectures

8.3 Data-Flow Design Approaches

8.4 Conclusion

Chapter 9: the Origins of Entity-Life Modeling

9.1 Introduction

9.2 Early Experiences with Software Development

9.3 the Jackson Methods

*9.4 Formal Models and Methods

9.5 Software Patterns

9.6 Conclusion

Exercises

Glossary

References

Index

Design of Multithreaded Software

Press Operating Committee

Chair

Linda Shafer

former Director, Software Quality InstituteThe University of Texas at Austin

Editor-in-Chief

Alan Clements

ProfessorUniversity of Teesside

Board Members

Mark J. Christensen, Independent Consultant James W. Cortada, IBM Institute for Business Value Richard E. (Dick) Fairley, Founder and Principal Associate,Software Engineering Management Associates (SEMA) Phillip Laplante, Professor of Software Engineering, Penn State University Evan Butterfi eld, Director of Products and Services Kate Guillemette, Product Development Editor, CS Press

IEEE Computer Society Publications

The world-renowned IEEE Computer Society publishes, promotes, and distributes a wide variety of authoritative computer science and engineering texts. These books are available from most retail outlets. Visit the CS Store at http://computer.org/store for a list of products.

IEEE Computer Society / Wiley Partnership

The IEEE Computer Society and Wiley partnership allows the CS Press authored book program to produce a number of exciting new titles in areas of computer science, computing and networking with a special focus on software engineering. IEEE Computer Society members continue to receive a 15% discount on these titles when purchased through Wiley or at wiley.com/ieeecs

To submit questions about the program or send proposals please e-mail [email protected] or write to Books, IEEE Computer Society, 10662 Los Vaqueros Circle, Los Alamitos, CA 90720-1314. Telephone [phone].

Additional information regarding the Computer Society authored book program can also be accessed from our web site at http://computer.org/cspress.

Java® is a registered trademark of Sun Microsystems, Inc.

LEGO® is a registered trademark of the LEGO Group.

POSIX® is a registered trademark of IEEE.

UML® is a registered trademark of Object Management Group, Inc.

UNIX® is a registered trademark of The Open Group.

Copyright © 2011 by the IEEE Computer Society

Published by John Wiley & Sons, Inc., Hoboken, New Jersey. All rights reserved

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data is available.

ISBN 978-0470-87659-6

oBook ISBN: 978-0470-90491-6

ePDF ISBN: 978-0470-90490-9

Foreword

As computer-based systems become ever more ambitious and ever more complex, it is vital to keep a firm grasp of the fundamental ideas of their conception and design. This book focuses on one of the most fundamental ideas of all. The world we inhabit, and our experiences in it, have an inescapable time dimension. To deal properly with the world and to satisfy the functional requirements of the systems we build, we must master the intrinsic complexities of this time dimension. Many sequential processes progress in parallel in the world, interacting wherever events in two processes involve the same entity. The computer software must mirror, respect, and exploit this sequentiality and concurrency, and also add its own interacting processes to implement the additional behaviour and control necessary to satisfy the requirements.

Bo Sandén has written a splendid book that should be read by every developer of systems that interact with the real world. The multithreading theme that gives the book its title treats the identification and design of individual threads—that is, of concurrent processes—and the synchronisation and control of their interactions at common entities. The book succeeds excellently in this difficult area, expounding patterns of thread interaction that clarify both the problems they address and the solutions they offer.

The developer of a system of this kind must give explicit consideration both to the real world and to the world inside the computer and must recognise clearly that these are distinct, though interrelated, worlds. In some development approaches these distinct worlds are subtly confused, especially where the software itself embodies a model—that is, a surrogate or simulation—of the real world. Some writers on object-oriented development take too little thought for the distinction between a software object and the real-world entity it models. Their readers are then disinclined to pay enough attention to the real world, and the resulting systems are not quite fit for purpose. In this book, Sandén has taken care to make a clear and explicit distinction between event threads in the real world and the related control threads in the software: He gives both the real world and the software world the attention that is their due. This is a book for designers and programmers who want to align their software faithfully to the real-world requirements that they are striving to satisfy.

The central justification of a focus on threads and concurrency is the fundamental role of time in the world and in the computer, but it has another virtue too. The thread structure—capturing the role of each thread and its interactions with other threads—forms an excellent basis for the software architecture. An object structure alone cannot inform an architecture. Sandén points out that a thread structure can embody the key idea of a software architecture, clearly exposing the concept and underlying principle of the system design. This notion chimes well with the notion of the operational principle of a machine expounded by the physical chemist and philosopher Michael Polanyi. The operational principle of a machine specifies “how its characteristic parts—its organs—fulfill their special function in combining to an overall operation which achieves the purpose of the machine. It describes how each organ acts on another organ within this context.” An object structure alone cannot reveal the operational principle of a system, but the thread structure, where threads are associated either with objects or with execution of system functions, can reveal it clearly and memorably. The book has several problem examples that illustrate architectural choice by presenting alternative thread structures embodying alternative operational principles.

MICHAEL A. JACKSON

LondonOctober 2010

Preface

Where I am not understood, it shall be concluded that something very useful and profound is couched underneath.

JONATHAN SWIFT

This book is an introduction to 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. They include embedded systems as well as such interactive systems as cruise controllers and automated teller machines. ELM is also useful for process interaction simulation software.

ELM is a systematic approach to threading. It doesn’t attempt to make multithreading look easy but uses its full power. My goal has been to present it clearly and precisely. Not everyone in the information technology trade must understand threading. Few even venture beyond scripting and mark-up languages to traditional programming. Even with all the multiprocessors we now have, it’s enough if a few understand concurrency and set up a project infrastructure that takes advantage of multiprocessing. Others can work within such a structure.

Part I covers two fundamentals: program language thread support and state diagramming. These are necessary for understanding ELM and are there chiefly as references. If you have never used threads, then a language text in Ada, C#, or Java may be the best starting point. The book is based on the following major papers on ELM:

J. R. Carter and B. I. Sandén, “Practical uses of Ada-95 concurrency features,” IEEE Concurrency, vol. 6 no. 4, pp. 47–56, Oct./Dec. 1998.

A. Q. Dinh, “A development method for real-time software in a parallel environment.” Ph.D. thesis, George Mason University, Fairfax, VA, 1994.

B. I. Sandén, “An entity-life modeling approach to the design of concurrent software,” CACM, vol. 32, no. 3, pp. 330–343, Mar. 1989a.

B. I. Sandén, “Entity-life modeling and structured analysis in real-time software design—A comparison,” CACM, vol. 32, no. 12, pp. 1458–1466, Dec. 1989b.

B. I. Sandén, “Modeling concurrent software,” IEEE Software, pp. 93–100, Sept. 1997.

B. I. Sandén, “A design pattern for state machines and concurrent activities,” inProc. 6th International Conference on Reliable Software Technologies—Ada-Europe 2001, Leuven, Belgium, May 14–18, 2001, D. Craeynest and A. Strohmeier, Eds., Lecture Notes in Computer Science, vol. 2043, Springer-Verlag, 2001, pp. 203–214.

B. I. Sandén, “Entity-life modeling: Modeling a thread architecture on the problem environment,” IEEESoftware, pp. 70–78, July/Aug. 2003.

B. I. Sandén and J. Zalewski, “Designing state-based systems with entity-life modeling,” Journal of Systems and Software, vol. 79, no. 1, pp. 69–78, Jan. 2006.

For me, the book in progress has served as a mind tool that let me penetrate all aspects of ELM, much more so than individual papers where a single case study must often suffice.

ACKNOWLEDGMENTS

Among those who have supported and encouraged the work on ELM in various ways over the years or otherwise have been helpful to the book project are Ben Brosgol, Anhtuan Dinh, Stephen Ferg, John Harbaugh, Jan Hext, John McCormick, Melvin Neville, Tony Robertiello, Jim Rogers, Alexander Romanovsky, Ray Schneider, Rob Scott, Alfred Strohmeier, Janusz Zalewski, and many excellent students in the graduate programs at George Mason University and Colorado Technical University and in external courses and tutorials.

In particular, Jeff Carter gave detailed feedback on the ELM chapters. Jörg Kienzle’s and Janusz Zalewski’s feedback greatly improved Chapters 4, 5, and 8. I also appreciate the many constructive and encouraging comments from anonymous paper reviewers.

I have quoted several works by Michael Jackson, who wrote the Foreword to this book. His recent books have also led me on to other readings. David Rine pointed me to Blum’s definitive work, Software Engineering. Fred Brooks’s The Mythical Man-month led me to such unlikely yet inspiring sources as Sayers’s The Mind of the Maker and Glegg’s The Design of Design.

Jessica Pierson helped me with line editing and found many imprecise turns of phrase. We went back and forth over some sentences and paragraphs, which was a great learning experience for me. If something still appears unclear, I must have added it afterward. She also took on the index as her personal project. Together with Martha Hall and Janusz Zalewski, she also helped me track down the sources of many quotes.

The quote that opens Section 2.2 is from Mezz Mezzrow and Bernard Wolfe, Really the Blues. Copyright © Mezz Mezzrow and Bernard Wolfe. Reprinted by arrangement with Citadel Press/Kensington Publishing Corp.www.kensingtonbooks.com

The quote that opens Section 9.2.1 is from Neal Stephenson, SNOW CRASH. Penguin Books 1993. Copyright © Neal Stephenson, 1992. Reproduced by permission of Penguin Books, Ltd.

PROGRAM EXCERPTS

Those program excerpts that are included are mostly in Ada, which may appear biased since ELM is language independent. The reason is that I no longer make a point of implementing all examples as I did when I wrote my previous book Software Construction. Readers are invited to implement each example in their language of choice as an invigorating exercise.

HEADINGS AND REFERENCES

Headings of sections that belong in a certain chapter but are unnecessary for basic understanding are marked with an asterisk.

Comments and suggestions are welcome at [email protected]. My current examples are mostly limited to traditional, soft real time and include various control systems. Examples illustrating other applications of multithreading would be useful.

EXERCISES

Most chapters are followed by exercises, which range from simple illustrations of central concepts from the chapter to realistic examples. Some of the latter are quite open ended and may require some research. They are based on real applications, and full specifications would be unwieldy.

BO I. SANDÉN

Colorado Springs, Colorado

December 2010

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, 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 eventthreads 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:

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.

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:

1.Threads, such as those in Java or C#, Pthreads, or Ada tasks.2

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:

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.

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.

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)